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-2002 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                 DBC *cursor;
 234                 ID buf[BDB_IDL_UM_SIZE];
 235                 ID *i;
 236                 void *ptr;
 237                 size_t len;
 238                 int rc2;
 239                 int flags = bdb->bi_db_opflags | DB_MULTIPLE;
 240                 data.data = buf;
 241                 data.ulen = BDB_IDL_UM_SIZEOF;
 242                 data.flags = DB_DBT_USERMEM;
 243
 244                 if ( tid )
 245                         flags |= DB_RMW;
 246
 247                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 248                 if( rc != 0 ) {
 249                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 250                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 251                         return rc;
 252                 }
 253                 rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
 254                 if (rc == 0) {
 255                         i = ids;
 256                         while (rc == 0) {
 257                                 u_int8_t *j;
 258
 259                                 DB_MULTIPLE_INIT( ptr, &data );
 260                                 while (ptr) {
 261                                         DB_MULTIPLE_NEXT(ptr, &data, j, len);
 262                                         if (j) {
 263                                                 ++i;
 264                                                 AC_MEMCPY( i, j, sizeof(ID) );
 265                                         }
 266                                 }
 267                                 rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
 268                         }
 269                         if ( rc == DB_NOTFOUND ) rc = 0;
 270                         ids[0] = i - ids;
 271                         /* On disk, a range is denoted by 0 in the first element */
 272                         if (ids[1] == 0) {
 273                                 if (ids[0] != BDB_IDL_RANGE_SIZE) {
 274                                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 275                                                 "range size mismatch: expected %ld, got %ld\n",
 276                                                 BDB_IDL_RANGE_SIZE, ids[0], 0 );
 277                                         cursor->c_close( cursor );
 278                                         return -1;
 279                                 }
 280                                 BDB_IDL_RANGE( ids, ids[2], ids[3] );
 281                         }
 282                         data.size = BDB_IDL_SIZEOF(ids);
 283                 }
 284                 rc2 = cursor->c_close( cursor );
 285                 if (rc2) {
 286                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 287                                 "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
 288                         return rc2;
 289                 }
 290         }
 291 #else
 292         data.data = ids;
 293         data.ulen = BDB_IDL_UM_SIZEOF;
 294         data.flags = DB_DBT_USERMEM;
 295         /* fetch it */
 296         rc = db->get( db, tid, key, &data, bdb->bi_db_opflags );
 297 #endif
 298
 299         if( rc == DB_NOTFOUND ) {
 300                 return rc;
 301
 302         } else if( rc != 0 ) {
 303                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 304                         "get failed: %s (%d)\n",
 305                         db_strerror(rc), rc, 0 );
 306                 return rc;
 307
 308         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 309                 /* size not multiple of ID size */
 310                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 311                         "odd size: expected %ld multiple, got %ld\n",
 312                         (long) sizeof( ID ), (long) data.size, 0 );
 313                 return -1;
 314
 315         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 316                 /* size mismatch */
 317                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 318                         "get size mismatch: expected %ld, got %ld\n",
 319                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 320                 return -1;
 321         }
 322
 323         return rc;
 324 }
 325
 326 int
 327 bdb_idl_insert_key(
 328         BackendDB       *be,
 329         DB                      *db,
 330         DB_TXN          *tid,
 331         DBT                     *key,
 332         ID                      id )
 333 {
 334         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 335         int     rc;
 336         DBT data;
 337 #ifndef BDB_IDL_MULTI
 338         ID ids[BDB_IDL_DB_SIZE];
 339 #endif
 340
 341         /* for printable keys only */
 342         Debug( LDAP_DEBUG_ARGS,
 343                 "=> bdb_idl_insert_key: %s %ld\n",
 344                 (char *)key->data, (long) id, 0 );
 345
 346         assert( id != NOID );
 347
 348         DBTzero( &data );
 349 #ifdef BDB_IDL_MULTI
 350         {
 351                 ID buf[BDB_IDL_DB_MAX];
 352                 DBC *cursor;
 353                 ID lo, hi;
 354                 char *err;
 355
 356                 data.size = sizeof( ID );
 357                 data.ulen = data.size;
 358                 data.flags = DB_DBT_USERMEM;
 359
 360                 rc = bdb_idl_fetch_key( be, db, tid, key, buf );
 361                 if ( rc && rc != DB_NOTFOUND )
 362                         return rc;
 363
 364                 /* If it never existed, or there's room in the current key,
 365                  * just store it.
 366                  */
 367                 if ( rc == DB_NOTFOUND || ( !BDB_IDL_IS_RANGE(buf) &&
 368                         BDB_IDL_N(buf) < BDB_IDL_DB_MAX ) ) {
 369                         data.data = &id;
 370                         rc = db->put( db, tid, key, &data, DB_NODUPDATA );
 371                 } else if ( BDB_IDL_IS_RANGE(buf) ) {
 372                         /* If it's a range and we're outside the boundaries,
 373                          * rewrite the range boundaries.
 374                          */
 375                         if ( id < BDB_IDL_RANGE_FIRST(buf) ||
 376                                 id > BDB_IDL_RANGE_LAST(buf) ) {
 377                                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 378                                 if ( rc != 0 ) {
 379                                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 380                                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 381                                         return rc;
 382                                 }
 383                                 if ( id < BDB_IDL_RANGE_FIRST(buf) ) {
 384                                         data.data = buf+1;
 385                                 } else {
 386                                         data.data = buf+2;
 387                                 }
 388                                 rc = cursor->c_get( cursor, key, &data, DB_GET_BOTH | DB_RMW );
 389                                 if ( rc != 0 ) {
 390                                         err = "c_get";
 391 fail:                           Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 392                                                 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 393                                         if ( cursor ) cursor->c_close( cursor );
 394                                         return rc;
 395                                 }
 396                                 data.data = &id;
 397                                 /* We should have been able to just overwrite the old
 398                                  * value with the new, but apparently we have to delete
 399                                  * it first.
 400                                  */
 401                                 rc = cursor->c_del( cursor, 0 );
 402                                 if ( rc ) {
 403                                         err = "c_del";
 404                                         goto fail;
 405                                 }
 406                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 407                                 if ( rc ) {
 408                                         err = "c_put";
 409                                         goto fail;
 410                                 }
 411                                 rc = cursor->c_close( cursor );
 412                                 if ( rc ) {
 413                                         cursor = NULL;
 414                                         err = "c_close";
 415                                         goto fail;
 416                                 }
 417                         }
 418                 } else {                /* convert to a range */
 419                         lo = BDB_IDL_FIRST(buf);
 420                         hi = BDB_IDL_LAST(buf);
 421
 422                         if (id < lo)
 423                                 lo = id;
 424                         else if (id > hi)
 425                                 hi = id;
 426
 427                         cursor = NULL;
 428
 429                         /* Delete all of the old IDL so we can replace with a range */
 430                         rc = db->del( db, tid, key, 0 );
 431                         if ( rc ) {
 432                                 err = "del";
 433                                 goto fail;
 434                         }
 435
 436                         /* Write the range */
 437                         data.data = &id;
 438                         id = 0;
 439                         rc = db->put( db, tid, key, &data, 0 );
 440                         if ( rc ) {
 441                                 err = "put #1";
 442                                 goto fail;
 443                         }
 444                         id = lo;
 445                         rc = db->put( db, tid, key, &data, 0 );
 446                         if ( rc ) {
 447                                 err = "put #2";
 448                                 goto fail;
 449                         }
 450                         id = hi;
 451                         rc = db->put( db, tid, key, &data, 0 );
 452                         if ( rc ) {
 453                                 err = "put #3";
 454                                 goto fail;
 455                         }
 456                 }
 457         }
 458 #else
 459         data.data = ids;
 460         data.ulen = sizeof ids;
 461         data.flags = DB_DBT_USERMEM;
 462
 463         /* fetch the key for read/modify/write */
 464         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 465
 466         if( rc == DB_NOTFOUND ) {
 467                 ids[0] = 1;
 468                 ids[1] = id;
 469                 data.size = 2 * sizeof( ID );
 470
 471         } else if ( rc != 0 ) {
 472                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 473                         "get failed: %s (%d)\n",
 474                         db_strerror(rc), rc, 0 );
 475                 return rc;
 476
 477         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 478                 /* size not multiple of ID size */
 479                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 480                         "odd size: expected %ld multiple, got %ld\n",
 481                         (long) sizeof( ID ), (long) data.size, 0 );
 482                 return -1;
 483
 484         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 485                 /* size mismatch */
 486                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 487                         "get size mismatch: expected %ld, got %ld\n",
 488                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 489                 return -1;
 490
 491         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 492                 if( id < ids[1] ) {
 493                         ids[1] = id;
 494                 } else if ( ids[2] > id ) {
 495                         ids[2] = id;
 496                 } else {
 497                         return 0;
 498                 }
 499
 500         } else {
 501                 rc = bdb_idl_insert( ids, id );
 502
 503                 if( rc == -1 ) {
 504                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 505                                 0, 0, 0 );
 506                         return 0;
 507                 }
 508                 if( rc != 0 ) {
 509                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 510                                 "bdb_idl_insert failed (%d)\n",
 511                                 rc, 0, 0 );
 512
 513                         return rc;
 514                 }
 515
 516                 data.size = BDB_IDL_SIZEOF( ids );
 517         }
 518
 519         /* store the key */
 520         rc = db->put( db, tid, key, &data, 0 );
 521 #endif
 522         if( rc == DB_KEYEXIST ) rc = 0;
 523
 524         if( rc != 0 ) {
 525                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 526                         "put failed: %s (%d)\n",
 527                         db_strerror(rc), rc, 0 );
 528         }
 529         return rc;
 530 }
 531
 532 int
 533 bdb_idl_delete_key(
 534         BackendDB       *be,
 535         DB                      *db,
 536         DB_TXN          *tid,
 537         DBT                     *key,
 538         ID                      id )
 539 {
 540         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 541         int     rc;
 542         DBT data;
 543 #ifndef BDB_IDL_MULTI
 544         ID ids[BDB_IDL_DB_SIZE];
 545 #endif
 546
 547         /* for printable keys only */
 548         Debug( LDAP_DEBUG_ARGS,
 549                 "=> bdb_idl_delete_key: %s %ld\n",
 550                 (char *)key->data, (long) id, 0 );
 551
 552         assert( id != NOID );
 553
 554         DBTzero( &data );
 555 #ifdef BDB_IDL_MULTI
 556         {
 557                 DBC *cursor;
 558
 559                 data.data = &id;
 560                 data.size = sizeof( id );
 561                 data.ulen = data.size;
 562                 data.flags = DB_DBT_USERMEM;
 563
 564                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 565                 rc = cursor->c_get( cursor, key, &data, bdb->bi_db_opflags |
 566                         DB_GET_BOTH | DB_RMW  );
 567                 if (rc == 0)
 568                         rc = cursor->c_del( cursor, 0 );
 569                 rc = cursor->c_close( cursor );
 570         }
 571 #else
 572         data.data = ids;
 573         data.ulen = sizeof( ids );
 574         data.flags = DB_DBT_USERMEM;
 575
 576         /* fetch the key for read/modify/write */
 577         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 578
 579         if ( rc != 0 ) {
 580                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 581                         "get failed: %s (%d)\n",
 582                         db_strerror(rc), rc, 0 );
 583                 return rc;
 584
 585         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 586                 /* size not multiple of ID size */
 587                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 588                         "odd size: expected %ld multiple, got %ld\n",
 589                         (long) sizeof( ID ), (long) data.size, 0 );
 590                 return -1;
 591
 592         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 593                 return 0;
 594
 595         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 596                 /* size mismatch */
 597                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 598                         "get size mismatch: expected %ld, got %ld\n",
 599                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 600                 return -1;
 601
 602         } else {
 603                 rc = idl_delete( ids, id );
 604
 605                 if( rc != 0 ) {
 606                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 607                                 "idl_delete failed (%d)\n",
 608                                 rc, 0, 0 );
 609                         return rc;
 610                 }
 611
 612                 if( ids[0] == 0 ) {
 613                         /* delete the key */
 614                         rc = db->del( db, tid, key, 0 );
 615                         if( rc != 0 ) {
 616                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 617                                         "delete failed: %s (%d)\n",
 618                                         db_strerror(rc), rc, 0 );
 619                         }
 620                         return rc;
 621                 }
 622
 623                 data.size = (ids[0]+1) * sizeof( ID );
 624         }
 625
 626         /* store the key */
 627         rc = db->put( db, tid, key, &data, 0 );
 628
 629 #endif /* BDB_IDL_MULTI */
 630
 631         if( rc != 0 ) {
 632                 Debug( LDAP_DEBUG_ANY,
 633                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 634                         db_strerror(rc), rc, 0 );
 635         }
 636
 637         return rc;
 638 }
 639
 640
 641 /*
 642  * idl_intersection - return a = a intersection b
 643  */
 644 int
 645 bdb_idl_intersection(
 646         ID *a,
 647         ID *b )
 648 {
 649         ID ida, idb;
 650         ID idmax, idmin;
 651         ID cursora = 0, cursorb = 0, cursorc;
 652         int swap = 0;
 653
 654         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 655                 a[0] = 0;
 656                 return 0;
 657         }
 658
 659         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 660         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 661         if ( idmin > idmax ) {
 662                 a[0] = 0;
 663                 return 0;
 664         } else if ( idmin == idmax ) {
 665                 a[0] = 1;
 666                 a[1] = idmin;
 667                 return 0;
 668         }
 669
 670         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 671                 a[1] = idmin;
 672                 a[2] = idmax;
 673                 return 0;
 674         }
 675
 676         if ( BDB_IDL_IS_RANGE( a ) ) {
 677                 ID *tmp = a;
 678                 a = b;
 679                 b = tmp;
 680                 swap = 1;
 681         }
 682
 683         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 684                 BDB_IDL_LAST( b ) >= idmax) {
 685                 if (idmax - idmin + 1 == a[0])
 686                 {
 687                         a[0] = NOID;
 688                         a[1] = idmin;
 689                         a[2] = idmax;
 690                 }
 691                 goto done;
 692         }
 693
 694         ida = bdb_idl_first( a, &cursora );
 695         idb = bdb_idl_first( b, &cursorb );
 696         cursorc = 0;
 697
 698         while( ida < idmin )
 699                 ida = bdb_idl_next( a, &cursora );
 700         while( idb < idmin )
 701                 idb = bdb_idl_next( b, &cursorb );
 702
 703         while( ida <= idmax || idb <= idmax ) {
 704                 if( ida == idb ) {
 705                         a[++cursorc] = ida;
 706                         ida = bdb_idl_next( a, &cursora );
 707                         idb = bdb_idl_next( b, &cursorb );
 708                 } else if ( ida < idb ) {
 709                         ida = bdb_idl_next( a, &cursora );
 710                 } else {
 711                         idb = bdb_idl_next( b, &cursorb );
 712                 }
 713         }
 714         a[0] = cursorc;
 715 done:
 716         if (swap)
 717                 BDB_IDL_CPY( b, a );
 718
 719         return 0;
 720 }
 721
 722
 723 /*
 724  * idl_union - return a = a union b
 725  */
 726 int
 727 bdb_idl_union(
 728         ID      *a,
 729         ID      *b )
 730 {
 731         ID ida, idb;
 732         ID cursora = 0, cursorb = 0, cursorc;
 733
 734         if ( BDB_IDL_IS_ZERO( b ) ) {
 735                 return 0;
 736         }
 737
 738         if ( BDB_IDL_IS_ZERO( a ) ) {
 739                 BDB_IDL_CPY( a, b );
 740                 return 0;
 741         }
 742
 743         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 744 over:           a[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 745                 a[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 746                 return 0;
 747         }
 748
 749         ida = bdb_idl_first( a, &cursora );
 750         idb = bdb_idl_first( b, &cursorb );
 751
 752         cursorc = b[0];
 753
 754         /* The distinct elements of a are cat'd to b */
 755         while( ida != NOID || idb != NOID ) {
 756                 if ( ida < idb ) {
 757                         if( ++cursorc > BDB_IDL_UM_MAX ) {
 758                                 a[0] = NOID;
 759                                 goto over;
 760                         }
 761                         b[cursorc] = ida;
 762                         ida = bdb_idl_next( a, &cursora );
 763
 764                 } else {
 765                         if ( ida == idb )
 766                                 ida = bdb_idl_next( a, &cursora );
 767                         idb = bdb_idl_next( b, &cursorb );
 768                 }
 769         }
 770
 771         /* b is copied back to a in sorted order */
 772         a[0] = cursorc;
 773         cursora = 1;
 774         cursorb = 1;
 775         cursorc = b[0]+1;
 776         while (cursorb <= b[0] || cursorc <= a[0]) {
 777                 if (cursorc > a[0])
 778                         idb = NOID;
 779                 else
 780                         idb = b[cursorc];
 781                 if (b[cursorb] < idb)
 782                         a[cursora++] = b[cursorb++];
 783                 else {
 784                         a[cursora++] = idb;
 785                         cursorc++;
 786                 }
 787         }
 788
 789         return 0;
 790 }
 791
 792
 793 #if 0
 794 /*
 795  * bdb_idl_notin - return a intersection ~b (or a minus b)
 796  */
 797 int
 798 bdb_idl_notin(
 799         ID      *a,
 800         ID      *b,
 801         ID *ids )
 802 {
 803         ID ida, idb;
 804         ID cursora = 0, cursorb = 0;
 805
 806         if( BDB_IDL_IS_ZERO( a ) ||
 807                 BDB_IDL_IS_ZERO( b ) ||
 808                 BDB_IDL_IS_RANGE( b ) )
 809         {
 810                 BDB_IDL_CPY( ids, a );
 811                 return 0;
 812         }
 813
 814         if( BDB_IDL_IS_RANGE( a ) ) {
 815                 BDB_IDL_CPY( ids, a );
 816                 return 0;
 817         }
 818
 819         ida = bdb_idl_first( a, &cursora ),
 820         idb = bdb_idl_first( b, &cursorb );
 821
 822         ids[0] = 0;
 823
 824         while( ida != NOID ) {
 825                 if ( idb == NOID ) {
 826                         /* we could shortcut this */
 827                         ids[++ids[0]] = ida;
 828                         ida = bdb_idl_next( a, &cursora );
 829
 830                 } else if ( ida < idb ) {
 831                         ids[++ids[0]] = ida;
 832                         ida = bdb_idl_next( a, &cursora );
 833
 834                 } else if ( ida > idb ) {
 835                         idb = bdb_idl_next( b, &cursorb );
 836
 837                 } else {
 838                         ida = bdb_idl_next( a, &cursora );
 839                         idb = bdb_idl_next( b, &cursorb );
 840                 }
 841         }
 842
 843         return 0;
 844 }
 845 #endif
 846
 847 ID bdb_idl_first( ID *ids, ID *cursor )
 848 {
 849         ID pos;
 850
 851         if ( ids[0] == 0 ) {
 852                 *cursor = NOID;
 853                 return NOID;
 854         }
 855
 856         if ( BDB_IDL_IS_RANGE( ids ) ) {
 857                 if( *cursor < ids[1] ) {
 858                         *cursor = ids[1];
 859                 }
 860                 return *cursor;
 861         }
 862
 863         if ( *cursor == 0 )
 864                 pos = 1;
 865         else
 866                 pos = bdb_idl_search( ids, *cursor );
 867
 868         if( pos > ids[0] ) {
 869                 return NOID;
 870         }
 871
 872         *cursor = pos;
 873         return ids[pos];
 874 }
 875
 876 ID bdb_idl_next( ID *ids, ID *cursor )
 877 {
 878         if ( BDB_IDL_IS_RANGE( ids ) ) {
 879                 if( ids[2] < ++(*cursor) ) {
 880                         return NOID;
 881                 }
 882                 return *cursor;
 883         }
 884
 885         if ( ++(*cursor) <= ids[0] ) {
 886                 return ids[*cursor];
 887         }
 888
 889         return NOID;
 890 }