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 ) ) {
 780                 if ( BDB_IDL_IS_RANGE(b) ) {
 781                 /* If both are ranges, just shrink the boundaries */
 782                         a[1] = idmin;
 783                         a[2] = idmax;
 784                         return 0;
 785                 } else {
 786                 /* Else swap so that b is the range, a is a list */
 787                         ID *tmp = a;
 788                         a = b;
 789                         b = tmp;
 790                         swap = 1;
 791                 }
 792         }
 793
 794         /* If a range completely covers the list, the result is
 795          * just the list. If idmin to idmax is contiguous, just
 796          * turn it into a range.
 797          */
 798         if ( BDB_IDL_IS_RANGE( b )
 799                 && BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
 800                 && BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
 801                 if (idmax - idmin + 1 == a[0])
 802                 {
 803                         a[0] = NOID;
 804                         a[1] = idmin;
 805                         a[2] = idmax;
 806                 }
 807                 goto done;
 808         }
 809
 810         /* Fine, do the intersection one element at a time.
 811          * First advance to idmin in both IDLs.
 812          */
 813         cursora = cursorb = idmin;
 814         ida = bdb_idl_first( a, &cursora );
 815         idb = bdb_idl_first( b, &cursorb );
 816         cursorc = 0;
 817
 818         while( ida <= idmax || idb <= idmax ) {
 819                 if( ida == idb ) {
 820                         a[++cursorc] = ida;
 821                         ida = bdb_idl_next( a, &cursora );
 822                         idb = bdb_idl_next( b, &cursorb );
 823                 } else if ( ida < idb ) {
 824                         ida = bdb_idl_next( a, &cursora );
 825                 } else {
 826                         idb = bdb_idl_next( b, &cursorb );
 827                 }
 828         }
 829         a[0] = cursorc;
 830 done:
 831         if (swap)
 832                 BDB_IDL_CPY( b, a );
 833
 834         return 0;
 835 }
 836
 837
 838 /*
 839  * idl_union - return a = a union b
 840  */
 841 int
 842 bdb_idl_union(
 843         ID      *a,
 844         ID      *b )
 845 {
 846         ID ida, idb;
 847         ID cursora = 0, cursorb = 0, cursorc;
 848
 849         if ( BDB_IDL_IS_ZERO( b ) ) {
 850                 return 0;
 851         }
 852
 853         if ( BDB_IDL_IS_ZERO( a ) ) {
 854                 BDB_IDL_CPY( a, b );
 855                 return 0;
 856         }
 857
 858         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 859 over:           ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 860                 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 861                 a[0] = NOID;
 862                 a[1] = ida;
 863                 a[2] = idb;
 864                 return 0;
 865         }
 866
 867         ida = bdb_idl_first( a, &cursora );
 868         idb = bdb_idl_first( b, &cursorb );
 869
 870         cursorc = b[0];
 871
 872         /* The distinct elements of a are cat'd to b */
 873         while( ida != NOID || idb != NOID ) {
 874                 if ( ida < idb ) {
 875                         if( ++cursorc > BDB_IDL_UM_MAX ) {
 876                                 goto over;
 877                         }
 878                         b[cursorc] = ida;
 879                         ida = bdb_idl_next( a, &cursora );
 880
 881                 } else {
 882                         if ( ida == idb )
 883                                 ida = bdb_idl_next( a, &cursora );
 884                         idb = bdb_idl_next( b, &cursorb );
 885                 }
 886         }
 887
 888         /* b is copied back to a in sorted order */
 889         a[0] = cursorc;
 890         cursora = 1;
 891         cursorb = 1;
 892         cursorc = b[0]+1;
 893         while (cursorb <= b[0] || cursorc <= a[0]) {
 894                 if (cursorc > a[0])
 895                         idb = NOID;
 896                 else
 897                         idb = b[cursorc];
 898                 if (cursorb <= b[0] && b[cursorb] < idb)
 899                         a[cursora++] = b[cursorb++];
 900                 else {
 901                         a[cursora++] = idb;
 902                         cursorc++;
 903                 }
 904         }
 905
 906         return 0;
 907 }
 908
 909
 910 #if 0
 911 /*
 912  * bdb_idl_notin - return a intersection ~b (or a minus b)
 913  */
 914 int
 915 bdb_idl_notin(
 916         ID      *a,
 917         ID      *b,
 918         ID *ids )
 919 {
 920         ID ida, idb;
 921         ID cursora = 0, cursorb = 0;
 922
 923         if( BDB_IDL_IS_ZERO( a ) ||
 924                 BDB_IDL_IS_ZERO( b ) ||
 925                 BDB_IDL_IS_RANGE( b ) )
 926         {
 927                 BDB_IDL_CPY( ids, a );
 928                 return 0;
 929         }
 930
 931         if( BDB_IDL_IS_RANGE( a ) ) {
 932                 BDB_IDL_CPY( ids, a );
 933                 return 0;
 934         }
 935
 936         ida = bdb_idl_first( a, &cursora ),
 937         idb = bdb_idl_first( b, &cursorb );
 938
 939         ids[0] = 0;
 940
 941         while( ida != NOID ) {
 942                 if ( idb == NOID ) {
 943                         /* we could shortcut this */
 944                         ids[++ids[0]] = ida;
 945                         ida = bdb_idl_next( a, &cursora );
 946
 947                 } else if ( ida < idb ) {
 948                         ids[++ids[0]] = ida;
 949                         ida = bdb_idl_next( a, &cursora );
 950
 951                 } else if ( ida > idb ) {
 952                         idb = bdb_idl_next( b, &cursorb );
 953
 954                 } else {
 955                         ida = bdb_idl_next( a, &cursora );
 956                         idb = bdb_idl_next( b, &cursorb );
 957                 }
 958         }
 959
 960         return 0;
 961 }
 962 #endif
 963
 964 ID bdb_idl_first( ID *ids, ID *cursor )
 965 {
 966         ID pos;
 967
 968         if ( ids[0] == 0 ) {
 969                 *cursor = NOID;
 970                 return NOID;
 971         }
 972
 973         if ( BDB_IDL_IS_RANGE( ids ) ) {
 974                 if( *cursor < ids[1] ) {
 975                         *cursor = ids[1];
 976                 }
 977                 return *cursor;
 978         }
 979
 980         if ( *cursor == 0 )
 981                 pos = 1;
 982         else
 983                 pos = bdb_idl_search( ids, *cursor );
 984
 985         if( pos > ids[0] ) {
 986                 return NOID;
 987         }
 988
 989         *cursor = pos;
 990         return ids[pos];
 991 }
 992
 993 ID bdb_idl_next( ID *ids, ID *cursor )
 994 {
 995         if ( BDB_IDL_IS_RANGE( ids ) ) {
 996                 if( ids[2] < ++(*cursor) ) {
 997                         return NOID;
 998                 }
 999                 return *cursor;
1000         }
1001
1002         if ( ++(*cursor) <= ids[0] ) {
1003                 return ids[*cursor];
1004         }
1005
1006         return NOID;
1007 }