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