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