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