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