git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/idl.c

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