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 int
 233 bdb_idl_fetch_key(
 234         BackendDB       *be,
 235         DB                      *db,
 236         DB_TXN          *tid,
 237         DBT                     *key,
 238         ID                      *ids )
 239 {
 240         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 241         int rc;
 242         DBT data;
 243
 244         assert( ids != NULL );
 245
 246         DBTzero( &data );
 247
 248 #ifdef BDB_IDL_MULTI
 249         {
 250                 DBC *cursor;
 251                 ID buf[BDB_PAGESIZE*4];
 252                 ID *i;
 253                 void *ptr;
 254                 size_t len;
 255                 int rc2;
 256                 int flags = bdb->bi_db_opflags | DB_MULTIPLE;
 257                 data.data = buf;
 258                 data.ulen = sizeof(buf);
 259                 data.flags = DB_DBT_USERMEM;
 260
 261                 if ( tid )
 262                         flags |= DB_RMW;
 263
 264                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 265                 if( rc != 0 ) {
 266 #ifdef NEW_LOGGING
 267                         LDAP_LOG( INDEX, ERR,
 268                                 "bdb_idl_fetch_key: cursor failed: %s (%d)\n",
 269                                 db_strerror(rc), rc, 0 );
 270 #else
 271                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 272                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 273 #endif
 274                         return rc;
 275                 }
 276                 rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
 277                 if (rc == 0) {
 278                         i = ids;
 279                         while (rc == 0) {
 280                                 u_int8_t *j;
 281
 282                                 DB_MULTIPLE_INIT( ptr, &data );
 283                                 while (ptr) {
 284                                         DB_MULTIPLE_NEXT(ptr, &data, j, len);
 285                                         if (j) {
 286                                                 ++i;
 287                                                 AC_MEMCPY( i, j, sizeof(ID) );
 288                                         }
 289                                 }
 290                                 rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
 291                         }
 292                         if ( rc == DB_NOTFOUND ) rc = 0;
 293                         ids[0] = i - ids;
 294                         /* On disk, a range is denoted by 0 in the first element */
 295                         if (ids[1] == 0) {
 296                                 if (ids[0] != BDB_IDL_RANGE_SIZE) {
 297 #ifdef NEW_LOGGING
 298                                         LDAP_LOG( INDEX, ERR,
 299                                                 "=> bdb_idl_fetch_key: range size mismatch: "
 300                                                 "expected %ld, got %ld\n",
 301                                                 BDB_IDL_RANGE_SIZE, ids[0], 0 );
 302 #else
 303                                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 304                                                 "range size mismatch: expected %d, got %ld\n",
 305                                                 BDB_IDL_RANGE_SIZE, ids[0], 0 );
 306 #endif
 307                                         cursor->c_close( cursor );
 308                                         return -1;
 309                                 }
 310                                 BDB_IDL_RANGE( ids, ids[2], ids[3] );
 311                         }
 312                         data.size = BDB_IDL_SIZEOF(ids);
 313                 }
 314                 rc2 = cursor->c_close( cursor );
 315                 if (rc2) {
 316 #ifdef NEW_LOGGING
 317                         LDAP_LOG( INDEX, ERR,
 318                                 "bdb_idl_fetch_key: close failed: %s (%d)\n",
 319                                 db_strerror(rc2), rc2, 0 );
 320 #else
 321                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 322                                 "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
 323 #endif
 324                         return rc2;
 325                 }
 326         }
 327 #else
 328         data.data = ids;
 329         data.ulen = BDB_IDL_UM_SIZEOF;
 330         data.flags = DB_DBT_USERMEM;
 331         /* fetch it */
 332         rc = db->get( db, tid, key, &data, bdb->bi_db_opflags );
 333 #endif
 334
 335         if( rc == DB_NOTFOUND ) {
 336                 return rc;
 337
 338         } else if( rc != 0 ) {
 339 #ifdef NEW_LOGGING
 340                 LDAP_LOG( INDEX, ERR,
 341                         "bdb_idl_fetch_key: get failed: %s (%d)\n",
 342                         db_strerror(rc), rc, 0 );
 343 #else
 344                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 345                         "get failed: %s (%d)\n",
 346                         db_strerror(rc), rc, 0 );
 347 #endif
 348                 return rc;
 349
 350         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 351                 /* size not multiple of ID size */
 352 #ifdef NEW_LOGGING
 353                 LDAP_LOG( INDEX, ERR,
 354                         "bdb_idl_fetch_key: odd size: expected %ld multiple, got %ld\n",
 355                         (long) sizeof( ID ), (long) data.size, 0 );
 356 #else
 357                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 358                         "odd size: expected %ld multiple, got %ld\n",
 359                         (long) sizeof( ID ), (long) data.size, 0 );
 360 #endif
 361                 return -1;
 362
 363         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 364                 /* size mismatch */
 365 #ifdef NEW_LOGGING
 366                 LDAP_LOG( INDEX, ERR,
 367                         "bdb_idl_fetch_key: get size mismatch: expected %ld, got %ld\n",
 368                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 369 #else
 370                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 371                         "get size mismatch: expected %ld, got %ld\n",
 372                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 373 #endif
 374                 return -1;
 375         }
 376
 377         return rc;
 378 }
 379
 380 int
 381 bdb_idl_insert_key(
 382         BackendDB       *be,
 383         DB                      *db,
 384         DB_TXN          *tid,
 385         DBT                     *key,
 386         ID                      id )
 387 {
 388         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 389         int     rc;
 390         DBT data;
 391 #ifndef BDB_IDL_MULTI
 392         ID ids[BDB_IDL_DB_SIZE];
 393 #endif
 394
 395 #if 0
 396         /* for printable keys only */
 397 #ifdef NEW_LOGGING
 398         LDAP_LOG( INDEX, ARGS, "bdb_idl_insert_key: %s %ld\n",
 399                 (char *)key->data, (long) id, 0 );
 400 #else
 401         Debug( LDAP_DEBUG_ARGS,
 402                 "=> bdb_idl_insert_key: %s %ld\n",
 403                 (char *)key->data, (long) id, 0 );
 404 #endif
 405 #endif
 406
 407         assert( id != NOID );
 408
 409         DBTzero( &data );
 410 #ifdef BDB_IDL_MULTI
 411         {
 412                 DBC *cursor;
 413                 ID lo, hi, tmp;
 414                 char *err;
 415
 416                 data.size = sizeof( ID );
 417                 data.ulen = data.size;
 418                 data.flags = DB_DBT_USERMEM;
 419
 420                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 421                 if ( rc != 0 ) {
 422 #ifdef NEW_LOGGING
 423                         LDAP_LOG( INDEX, ERR,
 424                                 "bdb_idl_insert_key: cursor failed: %s (%d)\n",
 425                                 db_strerror(rc), rc, 0 );
 426 #else
 427                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 428                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 429 #endif
 430                         return rc;
 431                 }
 432                 data.data = &tmp;
 433                 /* Fetch the first data item for this key, to see if it
 434                  * exists and if it's a range.
 435                  */
 436                 rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 437                 err = "c_get";
 438                 if ( rc == 0 ) {
 439                         if ( tmp != 0 ) {
 440                                 /* not a range, count the number of items */
 441                                 db_recno_t count;
 442                                 rc = cursor->c_count( cursor, &count, 0 );
 443                                 if ( rc != 0 ) {
 444                                         err = "c_count";
 445                                         goto fail;
 446                                 }
 447                                 if ( count >= BDB_IDL_DB_SIZE ) {
 448                                 /* No room, convert to a range */
 449                                         lo = tmp;
 450                                         data.data = &hi;
 451                                         rc = cursor->c_get( cursor, key, &data, DB_LAST );
 452                                         if ( rc != 0 ) {
 453                                                 err = "c_get last";
 454                                                 goto fail;
 455                                         }
 456                                         if ( id < lo )
 457                                                 lo = id;
 458                                         else if ( id > hi )
 459                                                 hi = id;
 460                                         rc = db->del( db, tid, key, 0 );
 461                                         if ( rc != 0 ) {
 462                                                 err = "del";
 463                                                 goto fail;
 464                                         }
 465                                         data.data = &id;
 466                                         id = 0;
 467                                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 468                                         if ( rc != 0 ) {
 469                                                 err = "c_put 0";
 470                                                 goto fail;
 471                                         }
 472                                         id = lo;
 473                                         rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 474                                         if ( rc != 0 ) {
 475                                                 err = "c_put lo";
 476                                                 goto fail;
 477                                         }
 478                                         id = hi;
 479                                         rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 480                                         if ( rc != 0 ) {
 481                                                 err = "c_put hi";
 482                                                 goto fail;
 483                                         }
 484                                 } else {
 485                                 /* There's room, just store it */
 486                                         goto put1;
 487                                 }
 488                         } else {
 489                                 /* It's a range, see if we need to rewrite
 490                                  * the boundaries
 491                                  */
 492                                 hi = id;
 493                                 data.data = &lo;
 494                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 495                                 if ( rc != 0 ) {
 496                                         err = "c_get lo";
 497                                         goto fail;
 498                                 }
 499                                 if ( id > lo ) {
 500                                         data.data = &hi;
 501                                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 502                                         if ( rc != 0 ) {
 503                                                 err = "c_get hi";
 504                                                 goto fail;
 505                                         }
 506                                 }
 507                                 if ( id < lo || id > hi ) {
 508                                         /* Delete the current lo/hi */
 509                                         rc = cursor->c_del( cursor, 0 );
 510                                         if ( rc != 0 ) {
 511                                                 err = "c_del";
 512                                                 goto fail;
 513                                         }
 514                                         data.data = &id;
 515                                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 516                                         if ( rc != 0 ) {
 517                                                 err = "c_put lo/hi";
 518                                                 goto fail;
 519                                         }
 520                                 }
 521                         }
 522                 } else if ( rc == DB_NOTFOUND ) {
 523 put1:                   data.data = &id;
 524                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 525                         /* Don't worry if it's already there */
 526                         if ( rc != 0 && rc != DB_KEYEXIST ) {
 527                                 err = "c_put id";
 528                                 goto fail;
 529                         }
 530                 } else {
 531                         /* initial c_get failed, nothing was done */
 532 fail:
 533 #ifdef NEW_LOGGING
 534                         LDAP_LOG( INDEX, ERR,
 535                                 "bdb_idl_insert_key: %s failed: %s (%d)\n",
 536                                 err, db_strerror(rc), rc );
 537 #else
 538                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 539                                 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 540 #endif
 541                         cursor->c_close( cursor );
 542                         return rc;
 543                 }
 544                 rc = cursor->c_close( cursor );
 545         }
 546 #else   /* !BDB_IDL_MULTI */
 547         data.data = ids;
 548         data.ulen = sizeof ids;
 549         data.flags = DB_DBT_USERMEM;
 550
 551         /* fetch the key for read/modify/write */
 552         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 553
 554         if( rc == DB_NOTFOUND ) {
 555                 ids[0] = 1;
 556                 ids[1] = id;
 557                 data.size = 2 * sizeof( ID );
 558
 559         } else if ( rc != 0 ) {
 560 #ifdef NEW_LOGGING
 561                 LDAP_LOG( INDEX, ERR, "bdb_idl_insert_key: get failed: %s (%d)\n",
 562                         db_strerror(rc), rc, 0 );
 563 #else
 564                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 565                         "get failed: %s (%d)\n",
 566                         db_strerror(rc), rc, 0 );
 567 #endif
 568                 return rc;
 569
 570         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 571                 /* size not multiple of ID size */
 572 #ifdef NEW_LOGGING
 573                 LDAP_LOG( INDEX, ERR,
 574                         "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 575                         (long) sizeof( ID ), (long) data.size, 0 );
 576 #else
 577                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 578                         "odd size: expected %ld multiple, got %ld\n",
 579                         (long) sizeof( ID ), (long) data.size, 0 );
 580 #endif
 581                 return -1;
 582
 583         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 584                 /* size mismatch */
 585 #ifdef NEW_LOGGING
 586                 LDAP_LOG( INDEX, ERR,
 587                         "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 588                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 589 #else
 590                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 591                         "get size mismatch: expected %ld, got %ld\n",
 592                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 593 #endif
 594                 return -1;
 595
 596         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 597                 if( id < ids[1] ) {
 598                         ids[1] = id;
 599                 } else if ( ids[2] > id ) {
 600                         ids[2] = id;
 601                 } else {
 602                         return 0;
 603                 }
 604
 605         } else {
 606                 rc = bdb_idl_insert( ids, id );
 607
 608                 if( rc == -1 ) {
 609 #ifdef NEW_LOGGING
 610                         LDAP_LOG( INDEX, DETAIL1, "bdb_idl_insert_key: dup\n", 0, 0, 0 );
 611 #else
 612                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 613                                 0, 0, 0 );
 614 #endif
 615                         return 0;
 616                 }
 617                 if( rc != 0 ) {
 618 #ifdef NEW_LOGGING
 619                         LDAP_LOG( INDEX, ERR,
 620                                 "bdb_idl_insert_key: insert failed: (%d)\n", rc, 0, 0 );
 621 #else
 622                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 623                                 "bdb_idl_insert failed (%d)\n",
 624                                 rc, 0, 0 );
 625 #endif
 626
 627                         return rc;
 628                 }
 629
 630                 data.size = BDB_IDL_SIZEOF( ids );
 631         }
 632
 633         /* store the key */
 634         rc = db->put( db, tid, key, &data, 0 );
 635 #endif
 636         if( rc == DB_KEYEXIST ) rc = 0;
 637
 638         if( rc != 0 ) {
 639 #ifdef NEW_LOGGING
 640                 LDAP_LOG( INDEX, ERR,
 641                         "bdb_idl_insert_key: put failed: %s (%d)\n",
 642                         db_strerror(rc), rc, 0 );
 643 #else
 644                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 645                         "put failed: %s (%d)\n",
 646                         db_strerror(rc), rc, 0 );
 647 #endif
 648         }
 649         return rc;
 650 }
 651
 652 int
 653 bdb_idl_delete_key(
 654         BackendDB       *be,
 655         DB                      *db,
 656         DB_TXN          *tid,
 657         DBT                     *key,
 658         ID                      id )
 659 {
 660         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 661         int     rc;
 662         DBT data;
 663 #ifndef BDB_IDL_MULTI
 664         ID ids[BDB_IDL_DB_SIZE];
 665 #endif
 666
 667 #if 0
 668         /* for printable keys only */
 669 #ifdef NEW_LOGGING
 670         LDAP_LOG( INDEX, ARGS, "bdb_idl_delete_key: %s %ld\n",
 671                 (char *)key->data, (long) id, 0 );
 672 #else
 673         Debug( LDAP_DEBUG_ARGS,
 674                 "=> bdb_idl_delete_key: %s %ld\n",
 675                 (char *)key->data, (long) id, 0 );
 676 #endif
 677 #endif
 678
 679         assert( id != NOID );
 680
 681         DBTzero( &data );
 682 #ifdef BDB_IDL_MULTI
 683         {
 684                 DBC *cursor;
 685                 ID lo, hi, tmp;
 686                 char *err;
 687
 688                 data.data = &tmp;
 689                 data.size = sizeof( id );
 690                 data.ulen = data.size;
 691                 data.flags = DB_DBT_USERMEM;
 692
 693                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 694                 if ( rc != 0 ) {
 695 #ifdef NEW_LOGGING
 696                         LDAP_LOG( INDEX, ERR,
 697                                 "bdb_idl_delete_key: cursor failed: %s (%d)\n",
 698                                 db_strerror(rc), rc, 0 );
 699 #else
 700                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 701                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 702 #endif
 703                         return rc;
 704                 }
 705                 /* Fetch the first data item for this key, to see if it
 706                  * exists and if it's a range.
 707                  */
 708                 rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 709                 err = "c_get";
 710                 if ( rc == 0 ) {
 711                         if ( tmp != 0 ) {
 712                                 /* Not a range, just delete it */
 713                                 if (tmp != id) {
 714                                         /* position to correct item */
 715                                         tmp = id;
 716                                         rc = cursor->c_get( cursor, key, &data,
 717                                                 DB_GET_BOTH | DB_RMW  );
 718                                 }
 719                                 if ( rc == 0 ) {
 720                                         rc = cursor->c_del( cursor, 0 );
 721                                         if ( rc != 0 ) {
 722                                                 err = "c_del id";
 723                                                 goto fail;
 724                                         }
 725                                 }
 726                         } else {
 727                                 /* It's a range, see if we need to rewrite
 728                                  * the boundaries
 729                                  */
 730                                 hi = 0;
 731                                 data.data = &lo;
 732                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 733                                 if ( rc != 0 ) {
 734                                         err = "c_get lo";
 735                                         goto fail;
 736                                 }
 737                                 if ( id > lo ) {
 738                                         data.data = &hi;
 739                                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 740                                         if ( rc != 0 ) {
 741                                                 err = "c_get hi";
 742                                                 goto fail;
 743                                         }
 744                                 }
 745                                 if ( id == lo || id == hi ) {
 746                                         if ( id == lo ) {
 747                                                 id++;
 748                                                 lo = id;
 749                                         } else if ( id == hi ) {
 750                                                 id--;
 751                                                 hi = id;
 752                                         }
 753                                         if ( lo >= hi ) {
 754                                         /* The range has collapsed... */
 755                                                 rc = db->del( db, tid, key, 0 );
 756                                                 if ( rc != 0 ) {
 757                                                         err = "del";
 758                                                         goto fail;
 759                                                 }
 760                                         } else {
 761                                                 rc = cursor->c_del( cursor, 0 );
 762                                                 if ( rc != 0 ) {
 763                                                         err = "c_del";
 764                                                         goto fail;
 765                                                 }
 766                                         }
 767                                         if ( lo <= hi ) {
 768                                                 data.data = &id;
 769                                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 770                                                 if ( rc != 0 ) {
 771                                                         err = "c_put lo/hi";
 772                                                         goto fail;
 773                                                 }
 774                                         }
 775                                 }
 776                         }
 777                 } else {
 778                         /* initial c_get failed, nothing was done */
 779 fail:
 780 #ifdef NEW_LOGGING
 781                         LDAP_LOG( INDEX, ERR,
 782                                 "bdb_idl_delete_key: %s failed: %s (%d)\n",
 783                                 err, db_strerror(rc), rc );
 784 #else
 785                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 786                                 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 787 #endif
 788                         cursor->c_close( cursor );
 789                         return rc;
 790                 }
 791                 rc = cursor->c_close( cursor );
 792         }
 793 #else
 794         data.data = ids;
 795         data.ulen = sizeof( ids );
 796         data.flags = DB_DBT_USERMEM;
 797
 798         /* fetch the key for read/modify/write */
 799         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 800
 801         if ( rc != 0 ) {
 802 #ifdef NEW_LOGGING
 803                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: get failed: %s (%d)\n",
 804                         db_strerror(rc), rc, 0 );
 805 #else
 806                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 807                         "get failed: %s (%d)\n",
 808                         db_strerror(rc), rc, 0 );
 809 #endif
 810                 return rc;
 811
 812         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 813                 /* size not multiple of ID size */
 814 #ifdef NEW_LOGGING
 815                 LDAP_LOG( INDEX, ERR,
 816                         "bdb_idl_delete_key: odd size: expected: %ld multiple, got %ld\n",
 817                         (long) sizeof( ID ), (long) data.size, 0 );
 818 #else
 819                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 820                         "odd size: expected %ld multiple, got %ld\n",
 821                         (long) sizeof( ID ), (long) data.size, 0 );
 822 #endif
 823                 return -1;
 824
 825         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 826                 return 0;
 827
 828         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 829                 /* size mismatch */
 830 #ifdef NEW_LOGGING
 831                 LDAP_LOG( INDEX, ERR,
 832                         "bdb_idl_delete_key: get size mismatch: expected: %ld, got %ld\n",
 833                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 834 #else
 835                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 836                         "get size mismatch: expected %ld, got %ld\n",
 837                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 838 #endif
 839                 return -1;
 840
 841         } else {
 842                 rc = idl_delete( ids, id );
 843
 844                 if( rc != 0 ) {
 845 #ifdef NEW_LOGGING
 846                         LDAP_LOG( INDEX, ERR,
 847                                 "bdb_idl_delete_key: delete failed: (%d)\n", rc, 0, 0 );
 848 #else
 849                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 850                                 "idl_delete failed (%d)\n",
 851                                 rc, 0, 0 );
 852 #endif
 853                         return rc;
 854                 }
 855
 856                 if( ids[0] == 0 ) {
 857                         /* delete the key */
 858                         rc = db->del( db, tid, key, 0 );
 859                         if( rc != 0 ) {
 860 #ifdef NEW_LOGGING
 861                                 LDAP_LOG( INDEX, ERR,
 862                                         "bdb_idl_delete_key: delete failed: %s (%d)\n",
 863                                         db_strerror(rc), rc, 0 );
 864 #else
 865                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 866                                         "delete failed: %s (%d)\n",
 867                                         db_strerror(rc), rc, 0 );
 868 #endif
 869                         }
 870                         return rc;
 871                 }
 872
 873                 data.size = (ids[0]+1) * sizeof( ID );
 874         }
 875
 876         /* store the key */
 877         rc = db->put( db, tid, key, &data, 0 );
 878
 879 #endif /* BDB_IDL_MULTI */
 880
 881         if( rc != 0 ) {
 882 #ifdef NEW_LOGGING
 883                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: put failed: %s (%d)\n",
 884                         db_strerror(rc), rc, 0 );
 885 #else
 886                 Debug( LDAP_DEBUG_ANY,
 887                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 888                         db_strerror(rc), rc, 0 );
 889 #endif
 890         }
 891
 892         return rc;
 893 }
 894
 895
 896 /*
 897  * idl_intersection - return a = a intersection b
 898  */
 899 int
 900 bdb_idl_intersection(
 901         ID *a,
 902         ID *b )
 903 {
 904         ID ida, idb;
 905         ID idmax, idmin;
 906         ID cursora = 0, cursorb = 0, cursorc;
 907         int swap = 0;
 908
 909         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 910                 a[0] = 0;
 911                 return 0;
 912         }
 913
 914         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 915         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 916         if ( idmin > idmax ) {
 917                 a[0] = 0;
 918                 return 0;
 919         } else if ( idmin == idmax ) {
 920                 a[0] = 1;
 921                 a[1] = idmin;
 922                 return 0;
 923         }
 924
 925         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 926                 a[1] = idmin;
 927                 a[2] = idmax;
 928                 return 0;
 929         }
 930
 931         if ( BDB_IDL_IS_RANGE( a ) ) {
 932                 ID *tmp = a;
 933                 a = b;
 934                 b = tmp;
 935                 swap = 1;
 936         }
 937
 938         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 939                 BDB_IDL_LAST( b ) >= idmax) {
 940                 if (idmax - idmin + 1 == a[0])
 941                 {
 942                         a[0] = NOID;
 943                         a[1] = idmin;
 944                         a[2] = idmax;
 945                 }
 946                 goto done;
 947         }
 948
 949         ida = bdb_idl_first( a, &cursora );
 950         idb = bdb_idl_first( b, &cursorb );
 951         cursorc = 0;
 952
 953         while( ida < idmin )
 954                 ida = bdb_idl_next( a, &cursora );
 955         while( idb < idmin )
 956                 idb = bdb_idl_next( b, &cursorb );
 957
 958         while( ida <= idmax || idb <= idmax ) {
 959                 if( ida == idb ) {
 960                         a[++cursorc] = ida;
 961                         ida = bdb_idl_next( a, &cursora );
 962                         idb = bdb_idl_next( b, &cursorb );
 963                 } else if ( ida < idb ) {
 964                         ida = bdb_idl_next( a, &cursora );
 965                 } else {
 966                         idb = bdb_idl_next( b, &cursorb );
 967                 }
 968         }
 969         a[0] = cursorc;
 970 done:
 971         if (swap)
 972                 BDB_IDL_CPY( b, a );
 973
 974         return 0;
 975 }
 976
 977
 978 /*
 979  * idl_union - return a = a union b
 980  */
 981 int
 982 bdb_idl_union(
 983         ID      *a,
 984         ID      *b )
 985 {
 986         ID ida, idb;
 987         ID cursora = 0, cursorb = 0, cursorc;
 988
 989         if ( BDB_IDL_IS_ZERO( b ) ) {
 990                 return 0;
 991         }
 992
 993         if ( BDB_IDL_IS_ZERO( a ) ) {
 994                 BDB_IDL_CPY( a, b );
 995                 return 0;
 996         }
 997
 998         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 999 over:           a[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
1000                 a[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
1001                 return 0;
1002         }
1003
1004         ida = bdb_idl_first( a, &cursora );
1005         idb = bdb_idl_first( b, &cursorb );
1006
1007         cursorc = b[0];
1008
1009         /* The distinct elements of a are cat'd to b */
1010         while( ida != NOID || idb != NOID ) {
1011                 if ( ida < idb ) {
1012                         if( ++cursorc > BDB_IDL_UM_MAX ) {
1013                                 a[0] = NOID;
1014                                 goto over;
1015                         }
1016                         b[cursorc] = ida;
1017                         ida = bdb_idl_next( a, &cursora );
1018
1019                 } else {
1020                         if ( ida == idb )
1021                                 ida = bdb_idl_next( a, &cursora );
1022                         idb = bdb_idl_next( b, &cursorb );
1023                 }
1024         }
1025
1026         /* b is copied back to a in sorted order */
1027         a[0] = cursorc;
1028         cursora = 1;
1029         cursorb = 1;
1030         cursorc = b[0]+1;
1031         while (cursorb <= b[0] || cursorc <= a[0]) {
1032                 if (cursorc > a[0])
1033                         idb = NOID;
1034                 else
1035                         idb = b[cursorc];
1036                 if (b[cursorb] < idb)
1037                         a[cursora++] = b[cursorb++];
1038                 else {
1039                         a[cursora++] = idb;
1040                         cursorc++;
1041                 }
1042         }
1043
1044         return 0;
1045 }
1046
1047
1048 #if 0
1049 /*
1050  * bdb_idl_notin - return a intersection ~b (or a minus b)
1051  */
1052 int
1053 bdb_idl_notin(
1054         ID      *a,
1055         ID      *b,
1056         ID *ids )
1057 {
1058         ID ida, idb;
1059         ID cursora = 0, cursorb = 0;
1060
1061         if( BDB_IDL_IS_ZERO( a ) ||
1062                 BDB_IDL_IS_ZERO( b ) ||
1063                 BDB_IDL_IS_RANGE( b ) )
1064         {
1065                 BDB_IDL_CPY( ids, a );
1066                 return 0;
1067         }
1068
1069         if( BDB_IDL_IS_RANGE( a ) ) {
1070                 BDB_IDL_CPY( ids, a );
1071                 return 0;
1072         }
1073
1074         ida = bdb_idl_first( a, &cursora ),
1075         idb = bdb_idl_first( b, &cursorb );
1076
1077         ids[0] = 0;
1078
1079         while( ida != NOID ) {
1080                 if ( idb == NOID ) {
1081                         /* we could shortcut this */
1082                         ids[++ids[0]] = ida;
1083                         ida = bdb_idl_next( a, &cursora );
1084
1085                 } else if ( ida < idb ) {
1086                         ids[++ids[0]] = ida;
1087                         ida = bdb_idl_next( a, &cursora );
1088
1089                 } else if ( ida > idb ) {
1090                         idb = bdb_idl_next( b, &cursorb );
1091
1092                 } else {
1093                         ida = bdb_idl_next( a, &cursora );
1094                         idb = bdb_idl_next( b, &cursorb );
1095                 }
1096         }
1097
1098         return 0;
1099 }
1100 #endif
1101
1102 ID bdb_idl_first( ID *ids, ID *cursor )
1103 {
1104         ID pos;
1105
1106         if ( ids[0] == 0 ) {
1107                 *cursor = NOID;
1108                 return NOID;
1109         }
1110
1111         if ( BDB_IDL_IS_RANGE( ids ) ) {
1112                 if( *cursor < ids[1] ) {
1113                         *cursor = ids[1];
1114                 }
1115                 return *cursor;
1116         }
1117
1118         if ( *cursor == 0 )
1119                 pos = 1;
1120         else
1121                 pos = bdb_idl_search( ids, *cursor );
1122
1123         if( pos > ids[0] ) {
1124                 return NOID;
1125         }
1126
1127         *cursor = pos;
1128         return ids[pos];
1129 }
1130
1131 ID bdb_idl_next( ID *ids, ID *cursor )
1132 {
1133         if ( BDB_IDL_IS_RANGE( ids ) ) {
1134                 if( ids[2] < ++(*cursor) ) {
1135                         return NOID;
1136                 }
1137                 return *cursor;
1138         }
1139
1140         if ( ++(*cursor) <= ids[0] ) {
1141                 return ids[*cursor];
1142         }
1143
1144         return NOID;
1145 }