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 #if IDL_DEBUG > 0
  22 static void idl_check( ID *ids )
  23 {
  24         if( BDB_IDL_IS_RANGE( ids ) ) {
  25                 assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
  26         } else {
  27                 ID i;
  28                 for( i=1; i < ids[0]; i++ ) {
  29                         assert( ids[i+1] > ids[i] );
  30                 }
  31         }
  32 }
  33
  34 #if IDL_DEBUG > 1
  35 static void idl_dump( ID *ids )
  36 {
  37         if( BDB_IDL_IS_RANGE( ids ) ) {
  38                 Debug( LDAP_DEBUG_ANY,
  39                         "IDL: range ( %ld - %ld )\n",
  40                         (long) BDB_IDL_RANGE_FIRST( ids ),
  41                         (long) BDB_IDL_RANGE_LAST( ids ) );
  42
  43         } else {
  44                 ID i;
  45                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  46
  47                 for( i=1; i<=ids[0]; i++ ) {
  48                         if( i % 16 == 1 ) {
  49                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  50                         }
  51                         Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
  52                 }
  53
  54                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  55         }
  56
  57         idl_check( ids );
  58 }
  59 #endif /* IDL_DEBUG > 1 */
  60 #endif /* IDL_DEBUG > 0 */
  61
  62 unsigned bdb_idl_search( ID *ids, ID id )
  63 {
  64 #define IDL_BINARY_SEARCH 1
  65 #ifdef IDL_BINARY_SEARCH
  66         /*
  67          * binary search of id in ids
  68          * if found, returns position of id
  69          * if not found, returns first postion greater than id
  70          */
  71         unsigned base = 0;
  72         unsigned cursor = 0;
  73         int val = 0;
  74         unsigned n = ids[0];
  75
  76 #if IDL_DEBUG > 0
  77         idl_check( ids );
  78 #endif
  79
  80         while( 0 < n ) {
  81                 int pivot = n >> 1;
  82                 cursor = base + pivot;
  83                 val = IDL_CMP( id, ids[cursor + 1] );
  84
  85                 if( val < 0 ) {
  86                         n = pivot;
  87
  88                 } else if ( val > 0 ) {
  89                         base = cursor + 1;
  90                         n -= pivot + 1;
  91
  92                 } else {
  93                         return cursor + 1;
  94                 }
  95         }
  96
  97         if( val > 0 ) {
  98                 return cursor + 2;
  99         } else {
 100                 return cursor + 1;
 101         }
 102
 103 #else
 104         /* (reverse) linear search */
 105         int i;
 106
 107 #if IDL_DEBUG > 0
 108         idl_check( ids );
 109 #endif
 110
 111         for( i=ids[0]; i; i-- ) {
 112                 if( id > ids[i] ) {
 113                         break;
 114                 }
 115         }
 116
 117         return i+1;
 118 #endif
 119 }
 120
 121 int bdb_idl_insert( ID *ids, ID id )
 122 {
 123         unsigned x = bdb_idl_search( ids, id );
 124
 125 #if IDL_DEBUG > 1
 126         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
 127         idl_dump( ids );
 128 #elif IDL_DEBUG > 0
 129         idl_check( ids );
 130 #endif
 131
 132         assert( x > 0 );
 133
 134         if( x < 1 ) {
 135                 /* internal error */
 136                 return -2;
 137         }
 138
 139         if ( x <= ids[0] && ids[x] == id ) {
 140                 /* duplicate */
 141                 return -1;
 142         }
 143
 144         if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
 145                 if( id < ids[1] ) {
 146                         ids[1] = id;
 147                         ids[2] = ids[ids[0]-1];
 148                 } else if ( ids[ids[0]-1] < id ) {
 149                         ids[2] = id;
 150                 } else {
 151                         ids[2] = ids[ids[0]-1];
 152                 }
 153                 ids[0] = NOID;
 154
 155         } else {
 156                 /* insert id */
 157                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 158                 ids[x] = id;
 159         }
 160
 161 #if IDL_DEBUG > 1
 162         idl_dump( ids );
 163 #elif IDL_DEBUG > 0
 164         idl_check( ids );
 165 #endif
 166
 167         return 0;
 168 }
 169
 170 static int idl_delete( ID *ids, ID id )
 171 {
 172         unsigned x = bdb_idl_search( ids, id );
 173
 174 #if IDL_DEBUG > 1
 175         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 176         idl_dump( ids );
 177 #elif IDL_DEBUG > 0
 178         idl_check( ids );
 179 #endif
 180
 181         assert( x > 0 );
 182
 183         if( x <= 0 ) {
 184                 /* internal error */
 185                 return -2;
 186         }
 187
 188         if( x > ids[0] || ids[x] != id ) {
 189                 /* not found */
 190                 return -1;
 191
 192         } else if ( --ids[0] == 0 ) {
 193                 if( x != 1 ) {
 194                         return -3;
 195                 }
 196
 197         } else {
 198                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 199         }
 200
 201 #if IDL_DEBUG > 1
 202         idl_dump( ids );
 203 #elif IDL_DEBUG > 0
 204         idl_check( ids );
 205 #endif
 206
 207         return 0;
 208 }
 209
 210 int
 211 bdb_idl_fetch_key(
 212         BackendDB       *be,
 213         DB                      *db,
 214         DB_TXN          *tid,
 215         DBT                     *key,
 216         ID                      *ids )
 217 {
 218         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 219         int rc;
 220         DBT data;
 221
 222         assert( ids != NULL );
 223
 224         DBTzero( &data );
 225
 226 #ifdef BDB_IDL_MULTI
 227         {
 228                 DBC *cursor;
 229                 ID buf[BDB_IDL_DB_SIZE];
 230                 ID *i;
 231                 void *ptr;
 232                 size_t len;
 233                 int rc2;
 234                 int flags = bdb->bi_db_opflags | DB_MULTIPLE;
 235                 data.data = buf;
 236                 data.ulen = sizeof(buf);
 237                 data.flags = DB_DBT_USERMEM;
 238
 239                 if ( tid )
 240                         flags |= DB_RMW;
 241
 242                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 243                 if( rc != 0 ) {
 244                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 245                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 246                         return rc;
 247                 }
 248                 rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
 249                 if (rc == 0) {
 250                         i = ids;
 251                         while (rc == 0) {
 252                                 u_int8_t *j;
 253
 254                                 DB_MULTIPLE_INIT( ptr, &data );
 255                                 while (ptr) {
 256                                         DB_MULTIPLE_NEXT(ptr, &data, j, len);
 257                                         if (j) {
 258                                                 ++i;
 259                                                 AC_MEMCPY( i, j, sizeof(ID) );
 260                                         }
 261                                 }
 262                                 rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
 263                         }
 264                         if ( rc == DB_NOTFOUND ) rc = 0;
 265                         ids[0] = i - ids;
 266                         /* On disk, a range is denoted by 0 in the first element */
 267                         if (ids[1] == 0) {
 268                                 if (ids[0] != BDB_IDL_RANGE_SIZE) {
 269                                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 270                                                 "range size mismatch: expected %ld, got %ld\n",
 271                                                 BDB_IDL_RANGE_SIZE, ids[0], 0 );
 272                                         cursor->c_close( cursor );
 273                                         return -1;
 274                                 }
 275                                 BDB_IDL_RANGE( ids, ids[2], ids[3] );
 276                         }
 277                         data.size = BDB_IDL_SIZEOF(ids);
 278                 }
 279                 rc2 = cursor->c_close( cursor );
 280                 if (rc2) {
 281                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 282                                 "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
 283                         return rc2;
 284                 }
 285         }
 286 #else
 287         data.data = ids;
 288         data.ulen = BDB_IDL_UM_SIZEOF;
 289         data.flags = DB_DBT_USERMEM;
 290         /* fetch it */
 291         rc = db->get( db, tid, key, &data, bdb->bi_db_opflags );
 292 #endif
 293
 294         if( rc == DB_NOTFOUND ) {
 295                 return rc;
 296
 297         } else if( rc != 0 ) {
 298                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 299                         "get failed: %s (%d)\n",
 300                         db_strerror(rc), rc, 0 );
 301                 return rc;
 302
 303         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 304                 /* size not multiple of ID size */
 305                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 306                         "odd size: expected %ld multiple, got %ld\n",
 307                         (long) sizeof( ID ), (long) data.size, 0 );
 308                 return -1;
 309
 310         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 311                 /* size mismatch */
 312                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 313                         "get size mismatch: expected %ld, got %ld\n",
 314                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 315                 return -1;
 316         }
 317
 318         return rc;
 319 }
 320
 321 int
 322 bdb_idl_insert_key(
 323         BackendDB       *be,
 324         DB                      *db,
 325         DB_TXN          *tid,
 326         DBT                     *key,
 327         ID                      id )
 328 {
 329         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 330         int     rc;
 331         DBT data;
 332 #ifndef BDB_IDL_MULTI
 333         ID ids[BDB_IDL_DB_SIZE];
 334 #endif
 335
 336 #if 0
 337         /* for printable keys only */
 338         Debug( LDAP_DEBUG_ARGS,
 339                 "=> bdb_idl_insert_key: %s %ld\n",
 340                 (char *)key->data, (long) id, 0 );
 341 #endif
 342
 343         assert( id != NOID );
 344
 345         DBTzero( &data );
 346 #ifdef BDB_IDL_MULTI
 347         {
 348                 ID buf[BDB_IDL_DB_SIZE];
 349                 DBC *cursor;
 350                 ID lo, hi;
 351                 char *err;
 352
 353                 data.size = sizeof( ID );
 354                 data.ulen = data.size;
 355                 data.flags = DB_DBT_USERMEM;
 356
 357                 rc = bdb_idl_fetch_key( be, db, tid, key, buf );
 358                 if ( rc && rc != DB_NOTFOUND )
 359                         return rc;
 360
 361                 /* If it never existed, or there's room in the current key,
 362                  * just store it.
 363                  */
 364                 if ( rc == DB_NOTFOUND || ( !BDB_IDL_IS_RANGE(buf) &&
 365                         BDB_IDL_N(buf) < BDB_IDL_DB_MAX ) ) {
 366                         data.data = &id;
 367                         rc = db->put( db, tid, key, &data, DB_NODUPDATA );
 368                 } else if ( BDB_IDL_IS_RANGE(buf) ) {
 369                         /* If it's a range and we're outside the boundaries,
 370                          * rewrite the range boundaries.
 371                          */
 372                         if ( id < BDB_IDL_RANGE_FIRST(buf) ||
 373                                 id > BDB_IDL_RANGE_LAST(buf) ) {
 374                                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 375                                 if ( rc != 0 ) {
 376                                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 377                                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 378                                         return rc;
 379                                 }
 380                                 if ( id < BDB_IDL_RANGE_FIRST(buf) ) {
 381                                         data.data = buf+1;
 382                                 } else {
 383                                         data.data = buf+2;
 384                                 }
 385                                 rc = cursor->c_get( cursor, key, &data, DB_GET_BOTH | DB_RMW );
 386                                 if ( rc != 0 ) {
 387                                         err = "c_get";
 388 fail:                           Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 389                                                 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 390                                         if ( cursor ) cursor->c_close( cursor );
 391                                         return rc;
 392                                 }
 393                                 data.data = &id;
 394                                 /* We should have been able to just overwrite the old
 395                                  * value with the new, but apparently we have to delete
 396                                  * it first.
 397                                  */
 398                                 rc = cursor->c_del( cursor, 0 );
 399                                 if ( rc ) {
 400                                         err = "c_del";
 401                                         goto fail;
 402                                 }
 403                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 404                                 if ( rc ) {
 405                                         err = "c_put";
 406                                         goto fail;
 407                                 }
 408                                 rc = cursor->c_close( cursor );
 409                                 if ( rc ) {
 410                                         cursor = NULL;
 411                                         err = "c_close";
 412                                         goto fail;
 413                                 }
 414                         }
 415                 } else {                /* convert to a range */
 416                         lo = BDB_IDL_FIRST(buf);
 417                         hi = BDB_IDL_LAST(buf);
 418
 419                         if (id < lo)
 420                                 lo = id;
 421                         else if (id > hi)
 422                                 hi = id;
 423
 424                         cursor = NULL;
 425
 426                         /* Delete all of the old IDL so we can replace with a range */
 427                         rc = db->del( db, tid, key, 0 );
 428                         if ( rc ) {
 429                                 err = "del";
 430                                 goto fail;
 431                         }
 432
 433                         /* Write the range */
 434                         data.data = &id;
 435                         id = 0;
 436                         rc = db->put( db, tid, key, &data, 0 );
 437                         if ( rc ) {
 438                                 err = "put #1";
 439                                 goto fail;
 440                         }
 441                         id = lo;
 442                         rc = db->put( db, tid, key, &data, 0 );
 443                         if ( rc ) {
 444                                 err = "put #2";
 445                                 goto fail;
 446                         }
 447                         id = hi;
 448                         rc = db->put( db, tid, key, &data, 0 );
 449                         if ( rc ) {
 450                                 err = "put #3";
 451                                 goto fail;
 452                         }
 453                 }
 454         }
 455 #else
 456         data.data = ids;
 457         data.ulen = sizeof ids;
 458         data.flags = DB_DBT_USERMEM;
 459
 460         /* fetch the key for read/modify/write */
 461         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 462
 463         if( rc == DB_NOTFOUND ) {
 464                 ids[0] = 1;
 465                 ids[1] = id;
 466                 data.size = 2 * sizeof( ID );
 467
 468         } else if ( rc != 0 ) {
 469                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 470                         "get failed: %s (%d)\n",
 471                         db_strerror(rc), rc, 0 );
 472                 return rc;
 473
 474         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 475                 /* size not multiple of ID size */
 476                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 477                         "odd size: expected %ld multiple, got %ld\n",
 478                         (long) sizeof( ID ), (long) data.size, 0 );
 479                 return -1;
 480
 481         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 482                 /* size mismatch */
 483                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 484                         "get size mismatch: expected %ld, got %ld\n",
 485                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 486                 return -1;
 487
 488         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 489                 if( id < ids[1] ) {
 490                         ids[1] = id;
 491                 } else if ( ids[2] > id ) {
 492                         ids[2] = id;
 493                 } else {
 494                         return 0;
 495                 }
 496
 497         } else {
 498                 rc = bdb_idl_insert( ids, id );
 499
 500                 if( rc == -1 ) {
 501                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 502                                 0, 0, 0 );
 503                         return 0;
 504                 }
 505                 if( rc != 0 ) {
 506                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 507                                 "bdb_idl_insert failed (%d)\n",
 508                                 rc, 0, 0 );
 509
 510                         return rc;
 511                 }
 512
 513                 data.size = BDB_IDL_SIZEOF( ids );
 514         }
 515
 516         /* store the key */
 517         rc = db->put( db, tid, key, &data, 0 );
 518 #endif
 519         if( rc == DB_KEYEXIST ) rc = 0;
 520
 521         if( rc != 0 ) {
 522                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 523                         "put failed: %s (%d)\n",
 524                         db_strerror(rc), rc, 0 );
 525         }
 526         return rc;
 527 }
 528
 529 int
 530 bdb_idl_delete_key(
 531         BackendDB       *be,
 532         DB                      *db,
 533         DB_TXN          *tid,
 534         DBT                     *key,
 535         ID                      id )
 536 {
 537         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 538         int     rc;
 539         DBT data;
 540 #ifndef BDB_IDL_MULTI
 541         ID ids[BDB_IDL_DB_SIZE];
 542 #endif
 543
 544 #if 0
 545         /* for printable keys only */
 546         Debug( LDAP_DEBUG_ARGS,
 547                 "=> bdb_idl_delete_key: %s %ld\n",
 548                 (char *)key->data, (long) id, 0 );
 549 #endif
 550
 551         assert( id != NOID );
 552
 553         DBTzero( &data );
 554 #ifdef BDB_IDL_MULTI
 555         {
 556                 DBC *cursor;
 557
 558                 data.data = &id;
 559                 data.size = sizeof( id );
 560                 data.ulen = data.size;
 561                 data.flags = DB_DBT_USERMEM;
 562
 563                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 564                 rc = cursor->c_get( cursor, key, &data, bdb->bi_db_opflags |
 565                         DB_GET_BOTH | DB_RMW  );
 566                 if (rc == 0)
 567                         rc = cursor->c_del( cursor, 0 );
 568                 rc = cursor->c_close( cursor );
 569         }
 570 #else
 571         data.data = ids;
 572         data.ulen = sizeof( ids );
 573         data.flags = DB_DBT_USERMEM;
 574
 575         /* fetch the key for read/modify/write */
 576         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 577
 578         if ( rc != 0 ) {
 579                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 580                         "get failed: %s (%d)\n",
 581                         db_strerror(rc), rc, 0 );
 582                 return rc;
 583
 584         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 585                 /* size not multiple of ID size */
 586                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 587                         "odd size: expected %ld multiple, got %ld\n",
 588                         (long) sizeof( ID ), (long) data.size, 0 );
 589                 return -1;
 590
 591         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 592                 return 0;
 593
 594         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 595                 /* size mismatch */
 596                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 597                         "get size mismatch: expected %ld, got %ld\n",
 598                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 599                 return -1;
 600
 601         } else {
 602                 rc = idl_delete( ids, id );
 603
 604                 if( rc != 0 ) {
 605                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 606                                 "idl_delete failed (%d)\n",
 607                                 rc, 0, 0 );
 608                         return rc;
 609                 }
 610
 611                 if( ids[0] == 0 ) {
 612                         /* delete the key */
 613                         rc = db->del( db, tid, key, 0 );
 614                         if( rc != 0 ) {
 615                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 616                                         "delete failed: %s (%d)\n",
 617                                         db_strerror(rc), rc, 0 );
 618                         }
 619                         return rc;
 620                 }
 621
 622                 data.size = (ids[0]+1) * sizeof( ID );
 623         }
 624
 625         /* store the key */
 626         rc = db->put( db, tid, key, &data, 0 );
 627
 628 #endif /* BDB_IDL_MULTI */
 629
 630         if( rc != 0 ) {
 631                 Debug( LDAP_DEBUG_ANY,
 632                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 633                         db_strerror(rc), rc, 0 );
 634         }
 635
 636         return rc;
 637 }
 638
 639
 640 /*
 641  * idl_intersection - return a = a intersection b
 642  */
 643 int
 644 bdb_idl_intersection(
 645         ID *a,
 646         ID *b )
 647 {
 648         ID ida, idb;
 649         ID idmax, idmin;
 650         ID cursora = 0, cursorb = 0, cursorc;
 651         int swap = 0;
 652
 653         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 654                 a[0] = 0;
 655                 return 0;
 656         }
 657
 658         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 659         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 660         if ( idmin > idmax ) {
 661                 a[0] = 0;
 662                 return 0;
 663         } else if ( idmin == idmax ) {
 664                 a[0] = 1;
 665                 a[1] = idmin;
 666                 return 0;
 667         }
 668
 669         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 670                 a[1] = idmin;
 671                 a[2] = idmax;
 672                 return 0;
 673         }
 674
 675         if ( BDB_IDL_IS_RANGE( a ) ) {
 676                 ID *tmp = a;
 677                 a = b;
 678                 b = tmp;
 679                 swap = 1;
 680         }
 681
 682         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 683                 BDB_IDL_LAST( b ) >= idmax) {
 684                 if (idmax - idmin + 1 == a[0])
 685                 {
 686                         a[0] = NOID;
 687                         a[1] = idmin;
 688                         a[2] = idmax;
 689                 }
 690                 goto done;
 691         }
 692
 693         ida = bdb_idl_first( a, &cursora );
 694         idb = bdb_idl_first( b, &cursorb );
 695         cursorc = 0;
 696
 697         while( ida < idmin )
 698                 ida = bdb_idl_next( a, &cursora );
 699         while( idb < idmin )
 700                 idb = bdb_idl_next( b, &cursorb );
 701
 702         while( ida <= idmax || idb <= idmax ) {
 703                 if( ida == idb ) {
 704                         a[++cursorc] = ida;
 705                         ida = bdb_idl_next( a, &cursora );
 706                         idb = bdb_idl_next( b, &cursorb );
 707                 } else if ( ida < idb ) {
 708                         ida = bdb_idl_next( a, &cursora );
 709                 } else {
 710                         idb = bdb_idl_next( b, &cursorb );
 711                 }
 712         }
 713         a[0] = cursorc;
 714 done:
 715         if (swap)
 716                 BDB_IDL_CPY( b, a );
 717
 718         return 0;
 719 }
 720
 721
 722 /*
 723  * idl_union - return a = a union b
 724  */
 725 int
 726 bdb_idl_union(
 727         ID      *a,
 728         ID      *b )
 729 {
 730         ID ida, idb;
 731         ID cursora = 0, cursorb = 0, cursorc;
 732
 733         if ( BDB_IDL_IS_ZERO( b ) ) {
 734                 return 0;
 735         }
 736
 737         if ( BDB_IDL_IS_ZERO( a ) ) {
 738                 BDB_IDL_CPY( a, b );
 739                 return 0;
 740         }
 741
 742         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 743 over:           a[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 744                 a[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 745                 return 0;
 746         }
 747
 748         ida = bdb_idl_first( a, &cursora );
 749         idb = bdb_idl_first( b, &cursorb );
 750
 751         cursorc = b[0];
 752
 753         /* The distinct elements of a are cat'd to b */
 754         while( ida != NOID || idb != NOID ) {
 755                 if ( ida < idb ) {
 756                         if( ++cursorc > BDB_IDL_UM_MAX ) {
 757                                 a[0] = NOID;
 758                                 goto over;
 759                         }
 760                         b[cursorc] = ida;
 761                         ida = bdb_idl_next( a, &cursora );
 762
 763                 } else {
 764                         if ( ida == idb )
 765                                 ida = bdb_idl_next( a, &cursora );
 766                         idb = bdb_idl_next( b, &cursorb );
 767                 }
 768         }
 769
 770         /* b is copied back to a in sorted order */
 771         a[0] = cursorc;
 772         cursora = 1;
 773         cursorb = 1;
 774         cursorc = b[0]+1;
 775         while (cursorb <= b[0] || cursorc <= a[0]) {
 776                 if (cursorc > a[0])
 777                         idb = NOID;
 778                 else
 779                         idb = b[cursorc];
 780                 if (b[cursorb] < idb)
 781                         a[cursora++] = b[cursorb++];
 782                 else {
 783                         a[cursora++] = idb;
 784                         cursorc++;
 785                 }
 786         }
 787
 788         return 0;
 789 }
 790
 791
 792 #if 0
 793 /*
 794  * bdb_idl_notin - return a intersection ~b (or a minus b)
 795  */
 796 int
 797 bdb_idl_notin(
 798         ID      *a,
 799         ID      *b,
 800         ID *ids )
 801 {
 802         ID ida, idb;
 803         ID cursora = 0, cursorb = 0;
 804
 805         if( BDB_IDL_IS_ZERO( a ) ||
 806                 BDB_IDL_IS_ZERO( b ) ||
 807                 BDB_IDL_IS_RANGE( b ) )
 808         {
 809                 BDB_IDL_CPY( ids, a );
 810                 return 0;
 811         }
 812
 813         if( BDB_IDL_IS_RANGE( a ) ) {
 814                 BDB_IDL_CPY( ids, a );
 815                 return 0;
 816         }
 817
 818         ida = bdb_idl_first( a, &cursora ),
 819         idb = bdb_idl_first( b, &cursorb );
 820
 821         ids[0] = 0;
 822
 823         while( ida != NOID ) {
 824                 if ( idb == NOID ) {
 825                         /* we could shortcut this */
 826                         ids[++ids[0]] = ida;
 827                         ida = bdb_idl_next( a, &cursora );
 828
 829                 } else if ( ida < idb ) {
 830                         ids[++ids[0]] = ida;
 831                         ida = bdb_idl_next( a, &cursora );
 832
 833                 } else if ( ida > idb ) {
 834                         idb = bdb_idl_next( b, &cursorb );
 835
 836                 } else {
 837                         ida = bdb_idl_next( a, &cursora );
 838                         idb = bdb_idl_next( b, &cursorb );
 839                 }
 840         }
 841
 842         return 0;
 843 }
 844 #endif
 845
 846 ID bdb_idl_first( ID *ids, ID *cursor )
 847 {
 848         ID pos;
 849
 850         if ( ids[0] == 0 ) {
 851                 *cursor = NOID;
 852                 return NOID;
 853         }
 854
 855         if ( BDB_IDL_IS_RANGE( ids ) ) {
 856                 if( *cursor < ids[1] ) {
 857                         *cursor = ids[1];
 858                 }
 859                 return *cursor;
 860         }
 861
 862         if ( *cursor == 0 )
 863                 pos = 1;
 864         else
 865                 pos = bdb_idl_search( ids, *cursor );
 866
 867         if( pos > ids[0] ) {
 868                 return NOID;
 869         }
 870
 871         *cursor = pos;
 872         return ids[pos];
 873 }
 874
 875 ID bdb_idl_next( ID *ids, ID *cursor )
 876 {
 877         if ( BDB_IDL_IS_RANGE( ids ) ) {
 878                 if( ids[2] < ++(*cursor) ) {
 879                         return NOID;
 880                 }
 881                 return *cursor;
 882         }
 883
 884         if ( ++(*cursor) <= ids[0] ) {
 885                 return ids[*cursor];
 886         }
 887
 888         return NOID;
 889 }