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