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 #ifdef NEW_LOGGING
  39                 LDAP_LOG( INDEX, INFO, "IDL: range (%ld - %ld)\n",
  40                         (long) BDB_IDL_RANGE_FIRST( ids ),
  41                         (long) BDB_IDL_RANGE_LAST( ids ), 0 );
  42 #else
  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 #endif
  48
  49         } else {
  50                 ID i;
  51 #ifdef NEW_LOGGING
  52                 LDAP_LOG( INDEX, INFO, "IDL: size %ld", (long) ids[0], 0, 0 );
  53 #else
  54                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  55 #endif
  56
  57                 for( i=1; i<=ids[0]; i++ ) {
  58                         if( i % 16 == 1 ) {
  59                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  60                         }
  61 #ifdef NEW_LOGGING
  62                         LDAP_LOG( INDEX, INFO, "%02lx",(long)ids[i], 0, 0 );
  63 #else
  64                         Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
  65 #endif
  66                 }
  67
  68                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  69         }
  70
  71         idl_check( ids );
  72 }
  73 #endif /* IDL_DEBUG > 1 */
  74 #endif /* IDL_DEBUG > 0 */
  75
  76 unsigned bdb_idl_search( ID *ids, ID id )
  77 {
  78 #define IDL_BINARY_SEARCH 1
  79 #ifdef IDL_BINARY_SEARCH
  80         /*
  81          * binary search of id in ids
  82          * if found, returns position of id
  83          * if not found, returns first postion greater than id
  84          */
  85         unsigned base = 0;
  86         unsigned cursor = 0;
  87         int val = 0;
  88         unsigned n = ids[0];
  89
  90 #if IDL_DEBUG > 0
  91         idl_check( ids );
  92 #endif
  93
  94         while( 0 < n ) {
  95                 int pivot = n >> 1;
  96                 cursor = base + pivot;
  97                 val = IDL_CMP( id, ids[cursor + 1] );
  98
  99                 if( val < 0 ) {
 100                         n = pivot;
 101
 102                 } else if ( val > 0 ) {
 103                         base = cursor + 1;
 104                         n -= pivot + 1;
 105
 106                 } else {
 107                         return cursor + 1;
 108                 }
 109         }
 110
 111         if( val > 0 ) {
 112                 return cursor + 2;
 113         } else {
 114                 return cursor + 1;
 115         }
 116
 117 #else
 118         /* (reverse) linear search */
 119         int i;
 120
 121 #if IDL_DEBUG > 0
 122         idl_check( ids );
 123 #endif
 124
 125         for( i=ids[0]; i; i-- ) {
 126                 if( id > ids[i] ) {
 127                         break;
 128                 }
 129         }
 130
 131         return i+1;
 132 #endif
 133 }
 134
 135 int bdb_idl_insert( ID *ids, ID id )
 136 {
 137         unsigned x = bdb_idl_search( ids, id );
 138
 139 #if IDL_DEBUG > 1
 140 #ifdef NEW_LOGGING
 141         LDAP_LOG( INDEX, DETAIL1, "insert: %04lx at %d\n", (long) id, x, 0 );
 142 #else
 143         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
 144         idl_dump( ids );
 145 #endif
 146 #elif IDL_DEBUG > 0
 147         idl_check( ids );
 148 #endif
 149
 150         assert( x > 0 );
 151
 152         if( x < 1 ) {
 153                 /* internal error */
 154                 return -2;
 155         }
 156
 157         if ( x <= ids[0] && ids[x] == id ) {
 158                 /* duplicate */
 159                 return -1;
 160         }
 161
 162         if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
 163                 if( id < ids[1] ) {
 164                         ids[1] = id;
 165                         ids[2] = ids[ids[0]-1];
 166                 } else if ( ids[ids[0]-1] < id ) {
 167                         ids[2] = id;
 168                 } else {
 169                         ids[2] = ids[ids[0]-1];
 170                 }
 171                 ids[0] = NOID;
 172
 173         } else {
 174                 /* insert id */
 175                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 176                 ids[x] = id;
 177         }
 178
 179 #if IDL_DEBUG > 1
 180         idl_dump( ids );
 181 #elif IDL_DEBUG > 0
 182         idl_check( ids );
 183 #endif
 184
 185         return 0;
 186 }
 187
 188 #if 0   /* unused */
 189 static int idl_delete( ID *ids, ID id )
 190 {
 191         unsigned x = bdb_idl_search( ids, id );
 192
 193 #if IDL_DEBUG > 1
 194 #ifdef NEW_LOGGING
 195         LDAP_LOG( INDEX, DETAIL1, "delete: %04lx at %d\n", (long) id, x, 0 );
 196 #else
 197         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 198         idl_dump( ids );
 199 #endif
 200 #elif IDL_DEBUG > 0
 201         idl_check( ids );
 202 #endif
 203
 204         assert( x > 0 );
 205
 206         if( x <= 0 ) {
 207                 /* internal error */
 208                 return -2;
 209         }
 210
 211         if( x > ids[0] || ids[x] != id ) {
 212                 /* not found */
 213                 return -1;
 214
 215         } else if ( --ids[0] == 0 ) {
 216                 if( x != 1 ) {
 217                         return -3;
 218                 }
 219
 220         } else {
 221                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 222         }
 223
 224 #if IDL_DEBUG > 1
 225         idl_dump( ids );
 226 #elif IDL_DEBUG > 0
 227         idl_check( ids );
 228 #endif
 229
 230         return 0;
 231 }
 232 #endif  /* unused */
 233
 234 static char *
 235 bdb_show_key(
 236         DBT             *key,
 237         char            *buf )
 238 {
 239         if ( key->size == sizeof( ID ) ) {
 240                 unsigned char *c = key->data;
 241                 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
 242                 return buf;
 243         } else {
 244                 return key->data;
 245         }
 246 }
 247
 248 int
 249 bdb_idl_fetch_key(
 250         BackendDB       *be,
 251         DB                      *db,
 252         DB_TXN          *tid,
 253         DBT                     *key,
 254         ID                      *ids )
 255 {
 256         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 257         int rc;
 258         DBT data;
 259         DBC *cursor;
 260         ID *i;
 261         void *ptr;
 262         size_t len;
 263         int rc2;
 264         int flags = bdb->bi_db_opflags | DB_MULTIPLE;
 265
 266         /* buf must be large enough to grab the entire IDL in one
 267          * get(), otherwise BDB 4 will leak resources on subsequent
 268          * get's. We can safely call get() twice - once for the data,
 269          * and once to get the DB_NOTFOUND result meaning there's
 270          * no more data. See ITS#2040 for details. This bug is fixed
 271          * in BDB 4.1 so a smaller buffer will work if stack space is
 272          * too limited.
 273          */
 274         ID buf[BDB_IDL_DB_SIZE*5];
 275
 276         {
 277                 char buf[16];
 278 #ifdef NEW_LOGGING
 279                 LDAP_LOG( INDEX, ARGS,
 280                         "bdb_idl_fetch_key: %s\n",
 281                         bdb_show_key( key, buf ), 0, 0 );
 282 #else
 283                 Debug( LDAP_DEBUG_ARGS,
 284                         "bdb_idl_fetch_key: %s\n",
 285                         bdb_show_key( key, buf ), 0, 0 );
 286 #endif
 287         }
 288         assert( ids != NULL );
 289
 290         DBTzero( &data );
 291
 292         data.data = buf;
 293         data.ulen = sizeof(buf);
 294         data.flags = DB_DBT_USERMEM;
 295
 296         if ( tid )
 297                 flags |= DB_RMW;
 298
 299         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 300         if( rc != 0 ) {
 301 #ifdef NEW_LOGGING
 302                 LDAP_LOG( INDEX, ERR,
 303                         "bdb_idl_fetch_key: cursor failed: %s (%d)\n",
 304                         db_strerror(rc), rc, 0 );
 305 #else
 306                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 307                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 308 #endif
 309                 return rc;
 310         }
 311         rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
 312         if (rc == 0) {
 313                 i = ids;
 314                 while (rc == 0) {
 315                         u_int8_t *j;
 316
 317                         DB_MULTIPLE_INIT( ptr, &data );
 318                         while (ptr) {
 319                                 DB_MULTIPLE_NEXT(ptr, &data, j, len);
 320                                 if (j) {
 321                                         ++i;
 322                                         AC_MEMCPY( i, j, sizeof(ID) );
 323                                 }
 324                         }
 325                         rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
 326                 }
 327                 if ( rc == DB_NOTFOUND ) rc = 0;
 328                 ids[0] = i - ids;
 329                 /* On disk, a range is denoted by 0 in the first element */
 330                 if (ids[1] == 0) {
 331                         if (ids[0] != BDB_IDL_RANGE_SIZE) {
 332 #ifdef NEW_LOGGING
 333                                 LDAP_LOG( INDEX, ERR,
 334                                         "=> bdb_idl_fetch_key: range size mismatch: "
 335                                         "expected %ld, got %ld\n",
 336                                         BDB_IDL_RANGE_SIZE, ids[0], 0 );
 337 #else
 338                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 339                                         "range size mismatch: expected %d, got %ld\n",
 340                                         BDB_IDL_RANGE_SIZE, ids[0], 0 );
 341 #endif
 342                                 cursor->c_close( cursor );
 343                                 return -1;
 344                         }
 345                         BDB_IDL_RANGE( ids, ids[2], ids[3] );
 346                 }
 347                 data.size = BDB_IDL_SIZEOF(ids);
 348         }
 349         rc2 = cursor->c_close( cursor );
 350         if (rc2) {
 351 #ifdef NEW_LOGGING
 352                 LDAP_LOG( INDEX, ERR,
 353                         "bdb_idl_fetch_key: close failed: %s (%d)\n",
 354                         db_strerror(rc2), rc2, 0 );
 355 #else
 356                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 357                         "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
 358 #endif
 359                 return rc2;
 360         }
 361         if( rc == DB_NOTFOUND ) {
 362                 return rc;
 363
 364         } else if( rc != 0 ) {
 365 #ifdef NEW_LOGGING
 366                 LDAP_LOG( INDEX, ERR,
 367                         "bdb_idl_fetch_key: get failed: %s (%d)\n",
 368                         db_strerror(rc), rc, 0 );
 369 #else
 370                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 371                         "get failed: %s (%d)\n",
 372                         db_strerror(rc), rc, 0 );
 373 #endif
 374                 return rc;
 375
 376         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 377                 /* size not multiple of ID size */
 378 #ifdef NEW_LOGGING
 379                 LDAP_LOG( INDEX, ERR,
 380                         "bdb_idl_fetch_key: odd size: expected %ld multiple, got %ld\n",
 381                         (long) sizeof( ID ), (long) data.size, 0 );
 382 #else
 383                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 384                         "odd size: expected %ld multiple, got %ld\n",
 385                         (long) sizeof( ID ), (long) data.size, 0 );
 386 #endif
 387                 return -1;
 388
 389         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 390                 /* size mismatch */
 391 #ifdef NEW_LOGGING
 392                 LDAP_LOG( INDEX, ERR,
 393                         "bdb_idl_fetch_key: get size mismatch: expected %ld, got %ld\n",
 394                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 395 #else
 396                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 397                         "get size mismatch: expected %ld, got %ld\n",
 398                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 399 #endif
 400                 return -1;
 401         }
 402
 403         return rc;
 404 }
 405
 406
 407 int
 408 bdb_idl_insert_key(
 409         BackendDB       *be,
 410         DB                      *db,
 411         DB_TXN          *tid,
 412         DBT                     *key,
 413         ID                      id )
 414 {
 415         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 416         int     rc;
 417         DBT data;
 418         DBC *cursor;
 419         ID lo, hi, tmp;
 420         char *err;
 421
 422         {
 423                 char buf[16];
 424 #ifdef NEW_LOGGING
 425                 LDAP_LOG( INDEX, ARGS,
 426                         "bdb_idl_insert_key: %lx %s\n",
 427                         (long) id, bdb_show_key( key, buf ), 0 );
 428 #else
 429                 Debug( LDAP_DEBUG_ARGS,
 430                         "bdb_idl_insert_key: %lx %s\n",
 431                         (long) id, bdb_show_key( key, buf ), 0 );
 432 #endif
 433         }
 434
 435         assert( id != NOID );
 436
 437         DBTzero( &data );
 438         data.size = sizeof( ID );
 439         data.ulen = data.size;
 440         data.flags = DB_DBT_USERMEM;
 441
 442         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 443         if ( rc != 0 ) {
 444 #ifdef NEW_LOGGING
 445                 LDAP_LOG( INDEX, ERR,
 446                         "bdb_idl_insert_key: cursor failed: %s (%d)\n",
 447                         db_strerror(rc), rc, 0 );
 448 #else
 449                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 450                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 451 #endif
 452                 return rc;
 453         }
 454         data.data = &tmp;
 455         /* Fetch the first data item for this key, to see if it
 456          * exists and if it's a range.
 457          */
 458         rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 459         err = "c_get";
 460         if ( rc == 0 ) {
 461                 if ( tmp != 0 ) {
 462                         /* not a range, count the number of items */
 463                         db_recno_t count;
 464                         rc = cursor->c_count( cursor, &count, 0 );
 465                         if ( rc != 0 ) {
 466                                 err = "c_count";
 467                                 goto fail;
 468                         }
 469                         if ( count >= BDB_IDL_DB_MAX ) {
 470                         /* No room, convert to a range */
 471                                 DBT key2 = *key;
 472
 473                                 key2.dlen = key2.ulen;
 474                                 key2.flags |= DB_DBT_PARTIAL;
 475
 476                                 lo = tmp;
 477                                 data.data = &hi;
 478                                 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
 479                                 if ( rc != 0 && rc != DB_NOTFOUND ) {
 480                                         err = "c_get next_nodup";
 481                                         goto fail;
 482                                 }
 483                                 if ( rc == DB_NOTFOUND ) {
 484                                         rc = cursor->c_get( cursor, key, &data, DB_LAST );
 485                                         if ( rc != 0 ) {
 486                                                 err = "c_get last";
 487                                                 goto fail;
 488                                         }
 489                                 } else {
 490                                         rc = cursor->c_get( cursor, key, &data, DB_PREV );
 491                                         if ( rc != 0 ) {
 492                                                 err = "c_get prev";
 493                                                 goto fail;
 494                                         }
 495                                 }
 496                                 if ( id < lo )
 497                                         lo = id;
 498                                 else if ( id > hi )
 499                                         hi = id;
 500                                 rc = db->del( db, tid, key, 0 );
 501                                 if ( rc != 0 ) {
 502                                         err = "del";
 503                                         goto fail;
 504                                 }
 505                                 data.data = &id;
 506                                 id = 0;
 507                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 508                                 if ( rc != 0 ) {
 509                                         err = "c_put 0";
 510                                         goto fail;
 511                                 }
 512                                 id = lo;
 513                                 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 514                                 if ( rc != 0 ) {
 515                                         err = "c_put lo";
 516                                         goto fail;
 517                                 }
 518                                 id = hi;
 519                                 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 520                                 if ( rc != 0 ) {
 521                                         err = "c_put hi";
 522                                         goto fail;
 523                                 }
 524                         } else {
 525                         /* There's room, just store it */
 526                                 goto put1;
 527                         }
 528                 } else {
 529                         /* It's a range, see if we need to rewrite
 530                          * the boundaries
 531                          */
 532                         hi = id;
 533                         data.data = &lo;
 534                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 535                         if ( rc != 0 ) {
 536                                 err = "c_get lo";
 537                                 goto fail;
 538                         }
 539                         if ( id > lo ) {
 540                                 data.data = &hi;
 541                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 542                                 if ( rc != 0 ) {
 543                                         err = "c_get hi";
 544                                         goto fail;
 545                                 }
 546                         }
 547                         if ( id < lo || id > hi ) {
 548                                 /* Delete the current lo/hi */
 549                                 rc = cursor->c_del( cursor, 0 );
 550                                 if ( rc != 0 ) {
 551                                         err = "c_del";
 552                                         goto fail;
 553                                 }
 554                                 data.data = &id;
 555                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 556                                 if ( rc != 0 ) {
 557                                         err = "c_put lo/hi";
 558                                         goto fail;
 559                                 }
 560                         }
 561                 }
 562         } else if ( rc == DB_NOTFOUND ) {
 563 put1:           data.data = &id;
 564                 rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA );
 565                 /* Don't worry if it's already there */
 566                 if ( rc != 0 && rc != DB_KEYEXIST ) {
 567                         err = "c_put id";
 568                         goto fail;
 569                 }
 570         } else {
 571                 /* initial c_get failed, nothing was done */
 572 fail:
 573 #ifdef NEW_LOGGING
 574                 LDAP_LOG( INDEX, ERR,
 575                         "bdb_idl_insert_key: %s failed: %s (%d)\n",
 576                         err, db_strerror(rc), rc );
 577 #else
 578                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 579                         "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 580 #endif
 581                 cursor->c_close( cursor );
 582                 return rc;
 583         }
 584         rc = cursor->c_close( cursor );
 585         if( rc != 0 ) {
 586 #ifdef NEW_LOGGING
 587                 LDAP_LOG( INDEX, ERR,
 588                         "bdb_idl_insert_key: c_close failed: %s (%d)\n",
 589                         db_strerror(rc), rc, 0 );
 590 #else
 591                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 592                         "c_close failed: %s (%d)\n",
 593                         db_strerror(rc), rc, 0 );
 594 #endif
 595         }
 596         return rc;
 597 }
 598
 599 int
 600 bdb_idl_delete_key(
 601         BackendDB       *be,
 602         DB                      *db,
 603         DB_TXN          *tid,
 604         DBT                     *key,
 605         ID                      id )
 606 {
 607         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 608         int     rc;
 609         DBT data;
 610         DBC *cursor;
 611         ID lo, hi, tmp;
 612         char *err;
 613
 614         {
 615                 char buf[16];
 616 #ifdef NEW_LOGGING
 617                 LDAP_LOG( INDEX, ARGS,
 618                         "bdb_idl_delete_key: %lx %s\n",
 619                         (long) id, bdb_show_key( key, buf ), 0 );
 620 #else
 621                 Debug( LDAP_DEBUG_ARGS,
 622                         "bdb_idl_delete_key: %lx %s\n",
 623                         (long) id, bdb_show_key( key, buf ), 0 );
 624 #endif
 625         }
 626         assert( id != NOID );
 627
 628         DBTzero( &data );
 629         data.data = &tmp;
 630         data.size = sizeof( id );
 631         data.ulen = data.size;
 632         data.flags = DB_DBT_USERMEM;
 633
 634         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 635         if ( rc != 0 ) {
 636 #ifdef NEW_LOGGING
 637                 LDAP_LOG( INDEX, ERR,
 638                         "bdb_idl_delete_key: cursor failed: %s (%d)\n",
 639                         db_strerror(rc), rc, 0 );
 640 #else
 641                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 642                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 643 #endif
 644                 return rc;
 645         }
 646         /* Fetch the first data item for this key, to see if it
 647          * exists and if it's a range.
 648          */
 649         rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 650         err = "c_get";
 651         if ( rc == 0 ) {
 652                 if ( tmp != 0 ) {
 653                         /* Not a range, just delete it */
 654                         if (tmp != id) {
 655                                 /* position to correct item */
 656                                 tmp = id;
 657                                 rc = cursor->c_get( cursor, key, &data,
 658                                         DB_GET_BOTH | DB_RMW  );
 659                                 if ( rc != 0 ) {
 660                                         err = "c_get id";
 661                                         goto fail;
 662                                 }
 663                         }
 664                         rc = cursor->c_del( cursor, 0 );
 665                         if ( rc != 0 ) {
 666                                 err = "c_del id";
 667                                 goto fail;
 668                         }
 669                 } else {
 670                         /* It's a range, see if we need to rewrite
 671                          * the boundaries
 672                          */
 673                         hi = 0;
 674                         data.data = &lo;
 675                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 676                         if ( rc != 0 ) {
 677                                 err = "c_get lo";
 678                                 goto fail;
 679                         }
 680                         if ( id > lo ) {
 681                                 data.data = &hi;
 682                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 683                                 if ( rc != 0 ) {
 684                                         err = "c_get hi";
 685                                         goto fail;
 686                                 }
 687                         }
 688                         if ( id == lo || id == hi ) {
 689                                 if ( id == lo ) {
 690                                         id++;
 691                                         lo = id;
 692                                 } else if ( id == hi ) {
 693                                         id--;
 694                                         hi = id;
 695                                 }
 696                                 if ( lo >= hi ) {
 697                                 /* The range has collapsed... */
 698                                         rc = db->del( db, tid, key, 0 );
 699                                         if ( rc != 0 ) {
 700                                                 err = "del";
 701                                                 goto fail;
 702                                         }
 703                                 } else {
 704                                         rc = cursor->c_del( cursor, 0 );
 705                                         if ( rc != 0 ) {
 706                                                 err = "c_del";
 707                                                 goto fail;
 708                                         }
 709                                 }
 710                                 if ( lo <= hi ) {
 711                                         data.data = &id;
 712                                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 713                                         if ( rc != 0 ) {
 714                                                 err = "c_put lo/hi";
 715                                                 goto fail;
 716                                         }
 717                                 }
 718                         }
 719                 }
 720         } else {
 721                 /* initial c_get failed, nothing was done */
 722 fail:
 723                 if ( rc != DB_NOTFOUND ) {
 724 #ifdef NEW_LOGGING
 725                 LDAP_LOG( INDEX, ERR,
 726                         "bdb_idl_delete_key: %s failed: %s (%d)\n",
 727                         err, db_strerror(rc), rc );
 728 #else
 729                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 730                         "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 731 #endif
 732                 }
 733                 cursor->c_close( cursor );
 734                 return rc;
 735         }
 736         rc = cursor->c_close( cursor );
 737         if( rc != 0 ) {
 738 #ifdef NEW_LOGGING
 739                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: c_close failed: %s (%d)\n",
 740                         db_strerror(rc), rc, 0 );
 741 #else
 742                 Debug( LDAP_DEBUG_ANY,
 743                         "=> bdb_idl_delete_key: c_close failed: %s (%d)\n",
 744                         db_strerror(rc), rc, 0 );
 745 #endif
 746         }
 747
 748         return rc;
 749 }
 750
 751
 752 /*
 753  * idl_intersection - return a = a intersection b
 754  */
 755 int
 756 bdb_idl_intersection(
 757         ID *a,
 758         ID *b )
 759 {
 760         ID ida, idb;
 761         ID idmax, idmin;
 762         ID cursora = 0, cursorb = 0, cursorc;
 763         int swap = 0;
 764
 765         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 766                 a[0] = 0;
 767                 return 0;
 768         }
 769
 770         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 771         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 772         if ( idmin > idmax ) {
 773                 a[0] = 0;
 774                 return 0;
 775         } else if ( idmin == idmax ) {
 776                 a[0] = 1;
 777                 a[1] = idmin;
 778                 return 0;
 779         }
 780
 781         if ( BDB_IDL_IS_RANGE( a ) ) {
 782                 if ( BDB_IDL_IS_RANGE(b) ) {
 783                 /* If both are ranges, just shrink the boundaries */
 784                         a[1] = idmin;
 785                         a[2] = idmax;
 786                         return 0;
 787                 } else {
 788                 /* Else swap so that b is the range, a is a list */
 789                         ID *tmp = a;
 790                         a = b;
 791                         b = tmp;
 792                         swap = 1;
 793                 }
 794         }
 795
 796         /* If a range completely covers the list, the result is
 797          * just the list. If idmin to idmax is contiguous, just
 798          * turn it into a range.
 799          */
 800         if ( BDB_IDL_IS_RANGE( b )
 801                 && BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
 802                 && BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
 803                 if (idmax - idmin + 1 == a[0])
 804                 {
 805                         a[0] = NOID;
 806                         a[1] = idmin;
 807                         a[2] = idmax;
 808                 }
 809                 goto done;
 810         }
 811
 812         /* Fine, do the intersection one element at a time.
 813          * First advance to idmin in both IDLs.
 814          */
 815         cursora = cursorb = idmin;
 816         ida = bdb_idl_first( a, &cursora );
 817         idb = bdb_idl_first( b, &cursorb );
 818         cursorc = 0;
 819
 820         while( ida <= idmax || idb <= idmax ) {
 821                 if( ida == idb ) {
 822                         a[++cursorc] = ida;
 823                         ida = bdb_idl_next( a, &cursora );
 824                         idb = bdb_idl_next( b, &cursorb );
 825                 } else if ( ida < idb ) {
 826                         ida = bdb_idl_next( a, &cursora );
 827                 } else {
 828                         idb = bdb_idl_next( b, &cursorb );
 829                 }
 830         }
 831         a[0] = cursorc;
 832 done:
 833         if (swap)
 834                 BDB_IDL_CPY( b, a );
 835
 836         return 0;
 837 }
 838
 839
 840 /*
 841  * idl_union - return a = a union b
 842  */
 843 int
 844 bdb_idl_union(
 845         ID      *a,
 846         ID      *b )
 847 {
 848         ID ida, idb;
 849         ID cursora = 0, cursorb = 0, cursorc;
 850
 851         if ( BDB_IDL_IS_ZERO( b ) ) {
 852                 return 0;
 853         }
 854
 855         if ( BDB_IDL_IS_ZERO( a ) ) {
 856                 BDB_IDL_CPY( a, b );
 857                 return 0;
 858         }
 859
 860         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 861 over:           ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 862                 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 863                 a[0] = NOID;
 864                 a[1] = ida;
 865                 a[2] = idb;
 866                 return 0;
 867         }
 868
 869         ida = bdb_idl_first( a, &cursora );
 870         idb = bdb_idl_first( b, &cursorb );
 871
 872         cursorc = b[0];
 873
 874         /* The distinct elements of a are cat'd to b */
 875         while( ida != NOID || idb != NOID ) {
 876                 if ( ida < idb ) {
 877                         if( ++cursorc > BDB_IDL_UM_MAX ) {
 878                                 goto over;
 879                         }
 880                         b[cursorc] = ida;
 881                         ida = bdb_idl_next( a, &cursora );
 882
 883                 } else {
 884                         if ( ida == idb )
 885                                 ida = bdb_idl_next( a, &cursora );
 886                         idb = bdb_idl_next( b, &cursorb );
 887                 }
 888         }
 889
 890         /* b is copied back to a in sorted order */
 891         a[0] = cursorc;
 892         cursora = 1;
 893         cursorb = 1;
 894         cursorc = b[0]+1;
 895         while (cursorb <= b[0] || cursorc <= a[0]) {
 896                 if (cursorc > a[0])
 897                         idb = NOID;
 898                 else
 899                         idb = b[cursorc];
 900                 if (cursorb <= b[0] && b[cursorb] < idb)
 901                         a[cursora++] = b[cursorb++];
 902                 else {
 903                         a[cursora++] = idb;
 904                         cursorc++;
 905                 }
 906         }
 907
 908         return 0;
 909 }
 910
 911
 912 #if 0
 913 /*
 914  * bdb_idl_notin - return a intersection ~b (or a minus b)
 915  */
 916 int
 917 bdb_idl_notin(
 918         ID      *a,
 919         ID      *b,
 920         ID *ids )
 921 {
 922         ID ida, idb;
 923         ID cursora = 0, cursorb = 0;
 924
 925         if( BDB_IDL_IS_ZERO( a ) ||
 926                 BDB_IDL_IS_ZERO( b ) ||
 927                 BDB_IDL_IS_RANGE( b ) )
 928         {
 929                 BDB_IDL_CPY( ids, a );
 930                 return 0;
 931         }
 932
 933         if( BDB_IDL_IS_RANGE( a ) ) {
 934                 BDB_IDL_CPY( ids, a );
 935                 return 0;
 936         }
 937
 938         ida = bdb_idl_first( a, &cursora ),
 939         idb = bdb_idl_first( b, &cursorb );
 940
 941         ids[0] = 0;
 942
 943         while( ida != NOID ) {
 944                 if ( idb == NOID ) {
 945                         /* we could shortcut this */
 946                         ids[++ids[0]] = ida;
 947                         ida = bdb_idl_next( a, &cursora );
 948
 949                 } else if ( ida < idb ) {
 950                         ids[++ids[0]] = ida;
 951                         ida = bdb_idl_next( a, &cursora );
 952
 953                 } else if ( ida > idb ) {
 954                         idb = bdb_idl_next( b, &cursorb );
 955
 956                 } else {
 957                         ida = bdb_idl_next( a, &cursora );
 958                         idb = bdb_idl_next( b, &cursorb );
 959                 }
 960         }
 961
 962         return 0;
 963 }
 964 #endif
 965
 966 ID bdb_idl_first( ID *ids, ID *cursor )
 967 {
 968         ID pos;
 969
 970         if ( ids[0] == 0 ) {
 971                 *cursor = NOID;
 972                 return NOID;
 973         }
 974
 975         if ( BDB_IDL_IS_RANGE( ids ) ) {
 976                 if( *cursor < ids[1] ) {
 977                         *cursor = ids[1];
 978                 }
 979                 return *cursor;
 980         }
 981
 982         if ( *cursor == 0 )
 983                 pos = 1;
 984         else
 985                 pos = bdb_idl_search( ids, *cursor );
 986
 987         if( pos > ids[0] ) {
 988                 return NOID;
 989         }
 990
 991         *cursor = pos;
 992         return ids[pos];
 993 }
 994
 995 ID bdb_idl_next( ID *ids, ID *cursor )
 996 {
 997         if ( BDB_IDL_IS_RANGE( ids ) ) {
 998                 if( ids[2] < ++(*cursor) ) {
 999                         return NOID;
1000                 }
1001                 return *cursor;
1002         }
1003
1004         if ( ++(*cursor) <= ids[0] ) {
1005                 return ids[*cursor];
1006         }
1007
1008         return NOID;
1009 }