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