git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/idl.c

   1 /* idl.c - ldap id list handling routines */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11 #include <ac/string.h>
  12
  13 #include "back-bdb.h"
  14 #include "idl.h"
  15
  16 #define IDL_MAX(x,y)    ( x > y ? x : y )
  17 #define IDL_MIN(x,y)    ( x < y ? x : y )
  18
  19 #define IDL_CMP(x,y)    ( x < y ? -1 : ( x > y ? 1 : 0 ) )
  20
  21 #ifndef IDL_DEBUG
  22         /* enable basic checks for now */
  23 #define IDL_DEBUG 1
  24 #endif
  25
  26 #if IDL_DEBUG > 0
  27 static void idl_check( ID *ids )
  28 {
  29         if( BDB_IDL_IS_RANGE( ids ) ) {
  30                 assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
  31         } else {
  32                 ID i;
  33                 for( i=1; i < ids[0]; i++ ) {
  34                         assert( ids[i+1] > ids[i] );
  35                 }
  36         }
  37 }
  38
  39 #if IDL_DEBUG > 1
  40 static void idl_dump( ID *ids )
  41 {
  42         if( BDB_IDL_IS_RANGE( ids ) ) {
  43                 Debug( LDAP_DEBUG_ANY,
  44                         "IDL: range ( %ld - %ld )\n",
  45                         (long) BDB_IDL_RANGE_FIRST( ids ),
  46                         (long) BDB_IDL_RANGE_LAST( ids ) );
  47
  48         } else {
  49                 ID i;
  50                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  51
  52                 for( i=1; i<=ids[0]; i++ ) {
  53                         if( i % 16 == 1 ) {
  54                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  55                         }
  56                         Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
  57                 }
  58
  59                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  60         }
  61
  62         idl_check( ids );
  63 }
  64 #endif /* IDL_DEBUG > 1 */
  65 #endif /* IDL_DEBUG > 0 */
  66
  67 unsigned bdb_idl_search( ID *ids, ID id )
  68 {
  69 #define IDL_BINARY_SEARCH 1
  70 #ifdef IDL_BINARY_SEARCH
  71         /*
  72          * binary search of id in ids
  73          * if found, returns position of id
  74          * if not found, returns first postion greater than id
  75          */
  76         unsigned base = 0;
  77         unsigned cursor = 0;
  78         int val = 0;
  79         unsigned n = ids[0];
  80
  81 #if IDL_DEBUG > 0
  82         idl_check( ids );
  83 #endif
  84
  85         while( 0 < n ) {
  86                 int pivot = n >> 1;
  87                 cursor = base + pivot;
  88                 val = IDL_CMP( id, ids[cursor + 1] );
  89
  90                 if( val < 0 ) {
  91                         n = pivot;
  92
  93                 } else if ( val > 0 ) {
  94                         base = cursor + 1;
  95                         n -= pivot + 1;
  96
  97                 } else {
  98                         return cursor + 1;
  99                 }
 100         }
 101
 102         if( val > 0 ) {
 103                 return cursor + 2;
 104         } else {
 105                 return cursor + 1;
 106         }
 107
 108 #else
 109         /* (reverse) linear search */
 110         int i;
 111
 112 #if IDL_DEBUG > 0
 113         idl_check( ids );
 114 #endif
 115
 116         for( i=ids[0]; i; i-- ) {
 117                 if( id > ids[i] ) {
 118                         break;
 119                 }
 120         }
 121
 122         return i+1;
 123 #endif
 124 }
 125
 126 int bdb_idl_insert( ID *ids, ID id )
 127 {
 128         unsigned x = bdb_idl_search( ids, id );
 129
 130 #if IDL_DEBUG > 1
 131         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
 132         idl_dump( ids );
 133 #elif IDL_DEBUG > 0
 134         idl_check( ids );
 135 #endif
 136
 137         assert( x > 0 );
 138
 139         if( x < 1 ) {
 140                 /* internal error */
 141                 return -2;
 142         }
 143
 144         if ( x <= ids[0] && ids[x] == id ) {
 145                 /* duplicate */
 146                 return -1;
 147         }
 148
 149         if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
 150                 if( id < ids[1] ) {
 151                         ids[1] = id;
 152                         ids[2] = ids[ids[0]-1];
 153                 } else if ( ids[ids[0]-1] < id ) {
 154                         ids[2] = id;
 155                 } else {
 156                         ids[2] = ids[ids[0]-1];
 157                 }
 158                 ids[0] = NOID;
 159
 160         } else {
 161                 /* insert id */
 162                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 163                 ids[x] = id;
 164         }
 165
 166 #if IDL_DEBUG > 1
 167         idl_dump( ids );
 168 #elif IDL_DEBUG > 0
 169         idl_check( ids );
 170 #endif
 171
 172         return 0;
 173 }
 174
 175 static int idl_delete( ID *ids, ID id )
 176 {
 177         unsigned x = bdb_idl_search( ids, id );
 178
 179 #if IDL_DEBUG > 1
 180         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 181         idl_dump( ids );
 182 #elif IDL_DEBUG > 0
 183         idl_check( ids );
 184 #endif
 185
 186         assert( x > 0 );
 187
 188         if( x <= 0 ) {
 189                 /* internal error */
 190                 return -2;
 191         }
 192
 193         if( x > ids[0] || ids[x] != id ) {
 194                 /* not found */
 195                 return -1;
 196
 197         } else if ( --ids[0] == 0 ) {
 198                 if( x != 1 ) {
 199                         return -3;
 200                 }
 201
 202         } else {
 203                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 204         }
 205
 206 #if IDL_DEBUG > 1
 207         idl_dump( ids );
 208 #elif IDL_DEBUG > 0
 209         idl_check( ids );
 210 #endif
 211
 212         return 0;
 213 }
 214
 215 int
 216 bdb_idl_fetch_key(
 217         BackendDB       *be,
 218         DB                      *db,
 219         DB_TXN          *tid,
 220         DBT                     *key,
 221         ID                      *ids )
 222 {
 223         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 224         int rc;
 225         DBT data;
 226
 227         assert( ids != NULL );
 228
 229         DBTzero( &data );
 230
 231 #ifdef BDB_IDL_MULTI
 232         {
 233                 ID buf[BDB_IDL_UM_SIZE];
 234                 ID *i, *j;
 235                 void *ptr;
 236                 size_t len;
 237                 data.data = buf;
 238                 data.ulen = BDB_IDL_UM_SIZEOF;
 239                 data.flags = DB_DBT_USERMEM;
 240                 rc = db->get( db, tid, key, &data, bdb->bi_db_opflags |
 241                         DB_MULTIPLE );
 242                 if (rc == 0) {
 243                         DB_MULTIPLE_INIT( ptr, &data );
 244                         i = ids;
 245                         while (ptr) {
 246                                 DB_MULTIPLE_NEXT(ptr, &data, j, len);
 247                                 if (j) {
 248                                         ++i;
 249                                         AC_MEMCPY( i, j, sizeof(ID) );
 250                                 }
 251                         }
 252                         if (ids[1] == 0) {
 253                                 BDB_IDL_RANGE( ids, ids[2], ids[3] );
 254                         } else {
 255                                 ids[0] = (i - ids);
 256                         }
 257                         data.size = BDB_IDL_SIZEOF(ids);
 258                 }
 259         }
 260 #else
 261         data.data = ids;
 262         data.ulen = BDB_IDL_UM_SIZEOF;
 263         data.flags = DB_DBT_USERMEM;
 264         /* fetch it */
 265         rc = db->get( db, tid, key, &data, bdb->bi_db_opflags );
 266
 267 #endif
 268         if( rc == DB_NOTFOUND ) {
 269                 return rc;
 270
 271         } else if( rc != 0 ) {
 272                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 273                         "get failed: %s (%d)\n",
 274                         db_strerror(rc), rc, 0 );
 275                 return rc;
 276
 277         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 278                 /* size not multiple of ID size */
 279                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 280                         "odd size: expected %ld multiple, got %ld\n",
 281                         (long) sizeof( ID ), (long) data.size, 0 );
 282                 return -1;
 283
 284         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 285                 /* size mismatch */
 286                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 287                         "get size mismatch: expected %ld, got %ld\n",
 288                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 289                 return -1;
 290         }
 291
 292         return rc;
 293 }
 294
 295 int
 296 bdb_idl_insert_key(
 297         BackendDB       *be,
 298         DB                      *db,
 299         DB_TXN          *tid,
 300         DBT                     *key,
 301         ID                      id )
 302 {
 303         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 304         int     rc;
 305         DBT data;
 306 #ifndef BDB_IDL_MULTI
 307         ID ids[BDB_IDL_DB_SIZE];
 308 #endif
 309
 310         /* for printable keys only */
 311         Debug( LDAP_DEBUG_ARGS,
 312                 "=> bdb_idl_insert_key: %s %ld\n",
 313                 (char *)key->data, (long) id, 0 );
 314
 315         assert( id != NOID );
 316
 317         DBTzero( &data );
 318 #ifdef BDB_IDL_MULTI
 319         /* FIXME: We really ought to count how many data items currently exist
 320          * for this key, and cap off with a range when we hit the max. We need
 321          * to use a 0 in the first slot to denote a range - since the data are
 322          * sorted in ascending order, the only way to get a flag into the
 323          * first slot is to use the smallest possible ID value. The fetch
 324          * function above can turn it into a "memory-format" range. We also
 325          * have to delete all of the existing data items when converting from
 326          * a list to a range. And of course, if it's already a range, we need
 327          * to read it in and process it instead of just doing the blind put
 328          * that we do right now...
 329          */
 330         data.data = &id;
 331         data.size = sizeof(id);
 332         data.flags = DB_DBT_USERMEM;
 333
 334         rc = db->put( db, tid, key, &data, DB_NODUPDATA );
 335 #else
 336         data.data = ids;
 337         data.ulen = sizeof ids;
 338         data.flags = DB_DBT_USERMEM;
 339
 340         /* fetch the key for read/modify/write */
 341         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 342
 343         if( rc == DB_NOTFOUND ) {
 344                 ids[0] = 1;
 345                 ids[1] = id;
 346                 data.size = 2 * sizeof( ID );
 347
 348         } else if ( rc != 0 ) {
 349                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 350                         "get failed: %s (%d)\n",
 351                         db_strerror(rc), rc, 0 );
 352                 return rc;
 353
 354         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 355                 /* size not multiple of ID size */
 356                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 357                         "odd size: expected %ld multiple, got %ld\n",
 358                         (long) sizeof( ID ), (long) data.size, 0 );
 359                 return -1;
 360
 361         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 362                 /* size mismatch */
 363                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 364                         "get size mismatch: expected %ld, got %ld\n",
 365                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 366                 return -1;
 367
 368         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 369                 if( id < ids[1] ) {
 370                         ids[1] = id;
 371                 } else if ( ids[2] > id ) {
 372                         ids[2] = id;
 373                 } else {
 374                         return 0;
 375                 }
 376
 377         } else {
 378                 rc = bdb_idl_insert( ids, id );
 379
 380                 if( rc == -1 ) {
 381                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 382                                 0, 0, 0 );
 383                         return 0;
 384                 }
 385                 if( rc != 0 ) {
 386                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 387                                 "bdb_idl_insert failed (%d)\n",
 388                                 rc, 0, 0 );
 389
 390                         return rc;
 391                 }
 392
 393                 data.size = BDB_IDL_SIZEOF( ids );
 394         }
 395
 396         /* store the key */
 397         rc = db->put( db, tid, key, &data, 0 );
 398 #endif
 399         if( rc == DB_KEYEXIST ) rc = 0;
 400
 401         if( rc != 0 ) {
 402                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 403                         "put failed: %s (%d)\n",
 404                         db_strerror(rc), rc, 0 );
 405         }
 406         return rc;
 407 }
 408
 409 int
 410 bdb_idl_delete_key(
 411         BackendDB       *be,
 412         DB                      *db,
 413         DB_TXN          *tid,
 414         DBT                     *key,
 415         ID                      id )
 416 {
 417         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 418         int     rc;
 419         DBT data;
 420 #ifndef BDB_IDL_MULTI
 421         ID ids[BDB_IDL_DB_SIZE];
 422 #endif
 423
 424         /* for printable keys only */
 425         Debug( LDAP_DEBUG_ARGS,
 426                 "=> bdb_idl_delete_key: %s %ld\n",
 427                 (char *)key->data, (long) id, 0 );
 428
 429         assert( id != NOID );
 430
 431         DBTzero( &data );
 432 #ifdef BDB_IDL_MULTI
 433         {
 434                 DBC *cursor;
 435
 436                 data.data = &id;
 437                 data.size = sizeof( id );
 438                 data.ulen = data.size;
 439                 data.flags = DB_DBT_USERMEM;
 440
 441                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 442                 rc = cursor->c_get( cursor, key, &data, bdb->bi_db_opflags |
 443                         DB_GET_BOTH | DB_RMW  );
 444                 if (rc == 0)
 445                         rc = cursor->c_del( cursor, 0 );
 446                 rc = cursor->c_close( cursor );
 447         }
 448 #else
 449         data.data = ids;
 450         data.ulen = sizeof( ids );
 451         data.flags = DB_DBT_USERMEM;
 452
 453         /* fetch the key for read/modify/write */
 454         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 455
 456         if ( rc != 0 ) {
 457                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 458                         "get failed: %s (%d)\n",
 459                         db_strerror(rc), rc, 0 );
 460                 return rc;
 461
 462         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 463                 /* size not multiple of ID size */
 464                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 465                         "odd size: expected %ld multiple, got %ld\n",
 466                         (long) sizeof( ID ), (long) data.size, 0 );
 467                 return -1;
 468
 469         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 470                 return 0;
 471
 472         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 473                 /* size mismatch */
 474                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 475                         "get size mismatch: expected %ld, got %ld\n",
 476                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 477                 return -1;
 478
 479         } else {
 480                 rc = idl_delete( ids, id );
 481
 482                 if( rc != 0 ) {
 483                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 484                                 "idl_delete failed (%d)\n",
 485                                 rc, 0, 0 );
 486                         return rc;
 487                 }
 488
 489                 if( ids[0] == 0 ) {
 490                         /* delete the key */
 491                         rc = db->del( db, tid, key, 0 );
 492                         if( rc != 0 ) {
 493                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 494                                         "delete failed: %s (%d)\n",
 495                                         db_strerror(rc), rc, 0 );
 496                         }
 497                         return rc;
 498                 }
 499
 500                 data.size = (ids[0]+1) * sizeof( ID );
 501         }
 502
 503         /* store the key */
 504         rc = db->put( db, tid, key, &data, 0 );
 505
 506 #endif /* BDB_IDL_MULTI */
 507
 508         if( rc != 0 ) {
 509                 Debug( LDAP_DEBUG_ANY,
 510                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 511                         db_strerror(rc), rc, 0 );
 512         }
 513
 514         return rc;
 515 }
 516
 517
 518 /*
 519  * idl_intersection - return a = a intersection b
 520  */
 521 int
 522 bdb_idl_intersection(
 523         ID *a,
 524         ID *b )
 525 {
 526         ID ida, idb;
 527         ID idmax, idmin;
 528         ID cursora = 0, cursorb = 0, cursorc;
 529         int swap = 0;
 530
 531         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 532                 a[0] = 0;
 533                 return 0;
 534         }
 535
 536         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 537         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 538         if ( idmin > idmax ) {
 539                 a[0] = 0;
 540                 return 0;
 541         } else if ( idmin == idmax ) {
 542                 a[0] = 1;
 543                 a[1] = idmin;
 544                 return 0;
 545         }
 546
 547         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 548                 a[1] = idmin;
 549                 a[2] = idmax;
 550                 return 0;
 551         }
 552
 553         if ( BDB_IDL_IS_RANGE( a ) ) {
 554                 ID *tmp = a;
 555                 a = b;
 556                 b = tmp;
 557                 swap = 1;
 558         }
 559
 560         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 561                 BDB_IDL_LAST( b ) >= idmax) {
 562                 if (idmax - idmin + 1 == a[0])
 563                 {
 564                         a[0] = NOID;
 565                         a[1] = idmin;
 566                         a[2] = idmax;
 567                 }
 568                 goto done;
 569         }
 570
 571         ida = bdb_idl_first( a, &cursora );
 572         idb = bdb_idl_first( b, &cursorb );
 573         cursorc = 0;
 574
 575         while( ida < idmin )
 576                 ida = bdb_idl_next( a, &cursora );
 577         while( idb < idmin )
 578                 idb = bdb_idl_next( b, &cursorb );
 579
 580         while( ida <= idmax || idb <= idmax ) {
 581                 if( ida == idb ) {
 582                         a[++cursorc] = ida;
 583                         ida = bdb_idl_next( a, &cursora );
 584                         idb = bdb_idl_next( b, &cursorb );
 585                 } else if ( ida < idb ) {
 586                         ida = bdb_idl_next( a, &cursora );
 587                 } else {
 588                         idb = bdb_idl_next( b, &cursorb );
 589                 }
 590         }
 591         a[0] = cursorc;
 592 done:
 593         if (swap)
 594                 BDB_IDL_CPY( b, a );
 595
 596         return 0;
 597 }
 598
 599
 600 /*
 601  * idl_union - return a = a union b
 602  */
 603 int
 604 bdb_idl_union(
 605         ID      *a,
 606         ID      *b )
 607 {
 608         ID ida, idb;
 609         ID cursora = 0, cursorb = 0, cursorc;
 610
 611         if ( BDB_IDL_IS_ZERO( b ) ) {
 612                 return 0;
 613         }
 614
 615         if ( BDB_IDL_IS_ZERO( a ) ) {
 616                 BDB_IDL_CPY( a, b );
 617                 return 0;
 618         }
 619
 620         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 621 over:           a[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 622                 a[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 623                 return 0;
 624         }
 625
 626         ida = bdb_idl_first( a, &cursora );
 627         idb = bdb_idl_first( b, &cursorb );
 628
 629         cursorc = b[0];
 630
 631         /* The distinct elements of a are cat'd to b */
 632         while( ida != NOID || idb != NOID ) {
 633                 if ( ida < idb ) {
 634                         if( ++cursorc > BDB_IDL_UM_MAX ) {
 635                                 a[0] = NOID;
 636                                 goto over;
 637                         }
 638                         b[cursorc] = ida;
 639                         ida = bdb_idl_next( a, &cursora );
 640
 641                 } else {
 642                         if ( ida == idb )
 643                                 ida = bdb_idl_next( a, &cursora );
 644                         idb = bdb_idl_next( b, &cursorb );
 645                 }
 646         }
 647
 648         /* b is copied back to a in sorted order */
 649         a[0] = cursorc;
 650         cursora = 1;
 651         cursorb = 1;
 652         cursorc = b[0]+1;
 653         while (cursorb <= b[0] || cursorc <= a[0]) {
 654                 if (cursorc > a[0])
 655                         idb = NOID;
 656                 else
 657                         idb = b[cursorc];
 658                 if (b[cursorb] < idb)
 659                         a[cursora++] = b[cursorb++];
 660                 else {
 661                         a[cursora++] = idb;
 662                         cursorc++;
 663                 }
 664         }
 665
 666         return 0;
 667 }
 668
 669
 670 #if 0
 671 /*
 672  * bdb_idl_notin - return a intersection ~b (or a minus b)
 673  */
 674 int
 675 bdb_idl_notin(
 676         ID      *a,
 677         ID      *b,
 678         ID *ids )
 679 {
 680         ID ida, idb;
 681         ID cursora = 0, cursorb = 0;
 682
 683         if( BDB_IDL_IS_ZERO( a ) ||
 684                 BDB_IDL_IS_ZERO( b ) ||
 685                 BDB_IDL_IS_RANGE( b ) )
 686         {
 687                 BDB_IDL_CPY( ids, a );
 688                 return 0;
 689         }
 690
 691         if( BDB_IDL_IS_RANGE( a ) ) {
 692                 BDB_IDL_CPY( ids, a );
 693                 return 0;
 694         }
 695
 696         ida = bdb_idl_first( a, &cursora ),
 697         idb = bdb_idl_first( b, &cursorb );
 698
 699         ids[0] = 0;
 700
 701         while( ida != NOID ) {
 702                 if ( idb == NOID ) {
 703                         /* we could shortcut this */
 704                         ids[++ids[0]] = ida;
 705                         ida = bdb_idl_next( a, &cursora );
 706
 707                 } else if ( ida < idb ) {
 708                         ids[++ids[0]] = ida;
 709                         ida = bdb_idl_next( a, &cursora );
 710
 711                 } else if ( ida > idb ) {
 712                         idb = bdb_idl_next( b, &cursorb );
 713
 714                 } else {
 715                         ida = bdb_idl_next( a, &cursora );
 716                         idb = bdb_idl_next( b, &cursorb );
 717                 }
 718         }
 719
 720         return 0;
 721 }
 722 #endif
 723
 724 ID bdb_idl_first( ID *ids, ID *cursor )
 725 {
 726         ID pos;
 727
 728         if ( ids[0] == 0 ) {
 729                 *cursor = NOID;
 730                 return NOID;
 731         }
 732
 733         if ( BDB_IDL_IS_RANGE( ids ) ) {
 734                 if( *cursor < ids[1] ) {
 735                         *cursor = ids[1];
 736                 }
 737                 return *cursor;
 738         }
 739
 740         if ( *cursor == 0 )
 741                 pos = 1;
 742         else
 743                 pos = bdb_idl_search( ids, *cursor );
 744
 745         if( pos > ids[0] ) {
 746                 return NOID;
 747         }
 748
 749         *cursor = pos;
 750         return ids[pos];
 751 }
 752
 753 ID bdb_idl_next( ID *ids, ID *cursor )
 754 {
 755         if ( BDB_IDL_IS_RANGE( ids ) ) {
 756                 if( ids[2] < ++(*cursor) ) {
 757                         return NOID;
 758                 }
 759                 return *cursor;
 760         }
 761
 762         if ( ++(*cursor) <= ids[0] ) {
 763                 return ids[*cursor];
 764         }
 765
 766         return NOID;
 767 }