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