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

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