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