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-2011 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#define IDL_CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) ) 28 29#define IDL_LRU_DELETE( bdb, e ) do { \ 30 if ( (e) == (bdb)->bi_idl_lru_head ) { \ 31 if ( (e)->idl_lru_next == (bdb)->bi_idl_lru_head ) { \ 32 (bdb)->bi_idl_lru_head = NULL; \ 33 } else { \ 34 (bdb)->bi_idl_lru_head = (e)->idl_lru_next; \ 35 } \ 36 } \ 37 if ( (e) == (bdb)->bi_idl_lru_tail ) { \ 38 if ( (e)->idl_lru_prev == (bdb)->bi_idl_lru_tail ) { \ 39 assert( (bdb)->bi_idl_lru_head == NULL ); \ 40 (bdb)->bi_idl_lru_tail = NULL; \ 41 } else { \ 42 (bdb)->bi_idl_lru_tail = (e)->idl_lru_prev; \ 43 } \ 44 } \ 45 (e)->idl_lru_next->idl_lru_prev = (e)->idl_lru_prev; \ 46 (e)->idl_lru_prev->idl_lru_next = (e)->idl_lru_next; \ 47} while ( 0 ) 48 49static int 50bdb_idl_entry_cmp( const void *v_idl1, const void *v_idl2 ) 51{ 52 const bdb_idl_cache_entry_t *idl1 = v_idl1, *idl2 = v_idl2; 53 int rc; 54 55 if ((rc = SLAP_PTRCMP( idl1->db, idl2->db ))) return rc; 56 if ((rc = idl1->kstr.bv_len - idl2->kstr.bv_len )) return rc; 57 return ( memcmp ( idl1->kstr.bv_val, idl2->kstr.bv_val , idl1->kstr.bv_len ) ); 58} 59 60#if IDL_DEBUG > 0 61static void idl_check( ID *ids ) 62{ 63 if( BDB_IDL_IS_RANGE( ids ) ) { 64 assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) ); 65 } else { 66 ID i; 67 for( i=1; i < ids[0]; i++ ) { 68 assert( ids[i+1] > ids[i] ); 69 } 70 } 71} 72 73#if IDL_DEBUG > 1 74static void idl_dump( ID *ids ) 75{ 76 if( BDB_IDL_IS_RANGE( ids ) ) { 77 Debug( LDAP_DEBUG_ANY, 78 "IDL: range ( %ld - %ld )\n", 79 (long) BDB_IDL_RANGE_FIRST( ids ), 80 (long) BDB_IDL_RANGE_LAST( ids ) ); 81 82 } else { 83 ID i; 84 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 ); 85 86 for( i=1; i<=ids[0]; i++ ) { 87 if( i % 16 == 1 ) { 88 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 ); 89 } 90 Debug( LDAP_DEBUG_ANY, " %02lx", (long) ids[i], 0, 0 ); 91 } 92 93 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 ); 94 } 95 96 idl_check( ids ); 97} 98#endif /* IDL_DEBUG > 1 */ 99#endif /* IDL_DEBUG > 0 */ 100 101unsigned bdb_idl_search( ID *ids, ID id ) 102{ 103#define IDL_BINARY_SEARCH 1 104#ifdef IDL_BINARY_SEARCH 105 /* 106 * binary search of id in ids 107 * if found, returns position of id 108 * if not found, returns first postion greater than id 109 */ 110 unsigned base = 0; 111 unsigned cursor = 1; 112 int val = 0; 113 unsigned n = ids[0]; 114 115#if IDL_DEBUG > 0 116 idl_check( ids ); 117#endif 118 119 while( 0 < n ) { 120 unsigned pivot = n >> 1; 121 cursor = base + pivot + 1; 122 val = IDL_CMP( id, ids[cursor] ); 123 124 if( val < 0 ) { 125 n = pivot; 126 127 } else if ( val > 0 ) { 128 base = cursor; 129 n -= pivot + 1; 130 131 } else { 132 return cursor; 133 } 134 } 135 136 if( val > 0 ) { 137 ++cursor; 138 } 139 return cursor; 140 141#else 142 /* (reverse) linear search */ 143 int i; 144 145#if IDL_DEBUG > 0 146 idl_check( ids ); 147#endif 148 149 for( i=ids[0]; i; i-- ) { 150 if( id > ids[i] ) { 151 break; 152 } 153 } 154 155 return i+1; 156#endif 157} 158 159int bdb_idl_insert( ID *ids, ID id ) 160{ 161 unsigned x; 162 163#if IDL_DEBUG > 1 164 Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 ); 165 idl_dump( ids ); 166#elif IDL_DEBUG > 0 167 idl_check( ids ); 168#endif 169 170 if (BDB_IDL_IS_RANGE( ids )) { 171 /* if already in range, treat as a dup */ 172 if (id >= BDB_IDL_RANGE_FIRST(ids) && id <= BDB_IDL_RANGE_LAST(ids)) 173 return -1; 174 if (id < BDB_IDL_RANGE_FIRST(ids)) 175 ids[1] = id; 176 else if (id > BDB_IDL_RANGE_LAST(ids)) 177 ids[2] = id; 178 return 0; 179 } 180 181 x = bdb_idl_search( ids, id ); 182 assert( x > 0 ); 183 184 if( x < 1 ) { 185 /* internal error */ 186 return -2; 187 } 188 189 if ( x <= ids[0] && ids[x] == id ) { 190 /* duplicate */ 191 return -1; 192 } 193 194 if ( ++ids[0] >= BDB_IDL_DB_MAX ) { 195 if( id < ids[1] ) { 196 ids[1] = id; 197 ids[2] = ids[ids[0]-1]; 198 } else if ( ids[ids[0]-1] < id ) { 199 ids[2] = id; 200 } else { 201 ids[2] = ids[ids[0]-1]; 202 } 203 ids[0] = NOID; 204 205 } else { 206 /* insert id */ 207 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) ); 208 ids[x] = id; 209 } 210 211#if IDL_DEBUG > 1 212 idl_dump( ids ); 213#elif IDL_DEBUG > 0 214 idl_check( ids ); 215#endif 216 217 return 0; 218} 219 220int bdb_idl_delete( ID *ids, ID id ) 221{ 222 unsigned x; 223 224#if IDL_DEBUG > 1 225 Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 ); 226 idl_dump( ids ); 227#elif IDL_DEBUG > 0 228 idl_check( ids ); 229#endif 230 231 if (BDB_IDL_IS_RANGE( ids )) { 232 /* If deleting a range boundary, adjust */ 233 if ( ids[1] == id ) 234 ids[1]++; 235 else if ( ids[2] == id ) 236 ids[2]--; 237 /* deleting from inside a range is a no-op */ 238 239 /* If the range has collapsed, re-adjust */ 240 if ( ids[1] > ids[2] ) 241 ids[0] = 0; 242 else if ( ids[1] == ids[2] ) 243 ids[1] = 1; 244 return 0; 245 } 246 247 x = bdb_idl_search( ids, id ); 248 assert( x > 0 ); 249 250 if( x <= 0 ) { 251 /* internal error */ 252 return -2; 253 } 254 255 if( x > ids[0] || ids[x] != id ) { 256 /* not found */ 257 return -1; 258 259 } else if ( --ids[0] == 0 ) { 260 if( x != 1 ) { 261 return -3; 262 } 263 264 } else { 265 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) ); 266 } 267 268#if IDL_DEBUG > 1 269 idl_dump( ids ); 270#elif IDL_DEBUG > 0 271 idl_check( ids ); 272#endif 273 274 return 0; 275} 276 277static char * 278bdb_show_key( 279 DBT *key, 280 char *buf ) 281{ 282 if ( key->size == 4 /* LUTIL_HASH_BYTES */ ) { 283 unsigned char *c = key->data; 284 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] ); 285 return buf; 286 } else { 287 return key->data; 288 } 289} 290 291/* Find a db/key pair in the IDL cache. If ids is non-NULL, 292 * copy the cached IDL into it, otherwise just return the status. 293 */ 294int 295bdb_idl_cache_get( 296 struct bdb_info *bdb, 297 DB *db, 298 DBT *key, 299 ID *ids ) 300{ 301 bdb_idl_cache_entry_t idl_tmp; 302 bdb_idl_cache_entry_t *matched_idl_entry; 303 int rc = LDAP_NO_SUCH_OBJECT; 304 305 DBT2bv( key, &idl_tmp.kstr ); 306 idl_tmp.db = db; 307 ldap_pvt_thread_rdwr_rlock( &bdb->bi_idl_tree_rwlock ); 308 matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp, 309 bdb_idl_entry_cmp ); 310 if ( matched_idl_entry != NULL ) { 311 if ( matched_idl_entry->idl && ids ) 312 BDB_IDL_CPY( ids, matched_idl_entry->idl ); 313 matched_idl_entry->idl_flags |= CACHE_ENTRY_REFERENCED; 314 if ( matched_idl_entry->idl ) 315 rc = LDAP_SUCCESS; 316 else 317 rc = DB_NOTFOUND; 318 } 319 ldap_pvt_thread_rdwr_runlock( &bdb->bi_idl_tree_rwlock ); 320 321 return rc; 322} 323 324void 325bdb_idl_cache_put( 326 struct bdb_info *bdb, 327 DB *db, 328 DBT *key, 329 ID *ids, 330 int rc ) 331{ 332 bdb_idl_cache_entry_t idl_tmp; 333 bdb_idl_cache_entry_t *ee, *eprev; 334 335 if ( rc == DB_NOTFOUND || BDB_IDL_IS_ZERO( ids )) 336 return; 337 338 DBT2bv( key, &idl_tmp.kstr ); 339 340 ee = (bdb_idl_cache_entry_t *) ch_malloc( 341 sizeof( bdb_idl_cache_entry_t ) ); 342 ee->db = db; 343 ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) ); 344 BDB_IDL_CPY( ee->idl, ids ); 345 346 ee->idl_lru_prev = NULL; 347 ee->idl_lru_next = NULL; 348 ee->idl_flags = 0; 349 ber_dupbv( &ee->kstr, &idl_tmp.kstr ); 350 ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock ); 351 if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee, 352 bdb_idl_entry_cmp, avl_dup_error )) 353 { 354 ch_free( ee->kstr.bv_val ); 355 ch_free( ee->idl ); 356 ch_free( ee ); 357 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock ); 358 return; 359 } 360 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock ); 361 /* LRU_ADD */ 362 if ( bdb->bi_idl_lru_head ) { 363 assert( bdb->bi_idl_lru_tail != NULL ); 364 assert( bdb->bi_idl_lru_head->idl_lru_prev != NULL ); 365 assert( bdb->bi_idl_lru_head->idl_lru_next != NULL ); 366 367 ee->idl_lru_next = bdb->bi_idl_lru_head; 368 ee->idl_lru_prev = bdb->bi_idl_lru_head->idl_lru_prev; 369 bdb->bi_idl_lru_head->idl_lru_prev->idl_lru_next = ee; 370 bdb->bi_idl_lru_head->idl_lru_prev = ee; 371 } else { 372 ee->idl_lru_next = ee->idl_lru_prev = ee; 373 bdb->bi_idl_lru_tail = ee; 374 } 375 bdb->bi_idl_lru_head = ee; 376 377 if ( bdb->bi_idl_cache_size >= bdb->bi_idl_cache_max_size ) { 378 int i; 379 eprev = bdb->bi_idl_lru_tail; 380 for ( i = 0; (ee = eprev) != NULL && i < 10; i++ ) { 381 eprev = ee->idl_lru_prev; 382 if ( eprev == ee ) { 383 eprev = NULL; 384 } 385 if ( ee->idl_flags & CACHE_ENTRY_REFERENCED ) { 386 ee->idl_flags ^= CACHE_ENTRY_REFERENCED; 387 continue; 388 } 389 if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee, 390 bdb_idl_entry_cmp ) == NULL ) { 391 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: " 392 "AVL delete failed\n", 393 0, 0, 0 ); 394 } 395 IDL_LRU_DELETE( bdb, ee ); 396 i++; 397 --bdb->bi_idl_cache_size; 398 ch_free( ee->kstr.bv_val ); 399 ch_free( ee->idl ); 400 ch_free( ee ); 401 } 402 bdb->bi_idl_lru_tail = eprev; 403 assert( bdb->bi_idl_lru_tail != NULL 404 || bdb->bi_idl_lru_head == NULL ); 405 } 406 bdb->bi_idl_cache_size++; 407 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock ); 408 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock ); 409} 410 411void 412bdb_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 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: " 427 "AVL delete failed\n", 428 0, 0, 0 ); 429 } 430 --bdb->bi_idl_cache_size; 431 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock ); 432 IDL_LRU_DELETE( bdb, matched_idl_entry ); 433 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock ); 434 free( matched_idl_entry->kstr.bv_val ); 435 if ( matched_idl_entry->idl ) 436 free( matched_idl_entry->idl ); 437 free( matched_idl_entry ); 438 } 439 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock ); 440} 441 442void 443bdb_idl_cache_add_id( 444 struct bdb_info *bdb, 445 DB *db, 446 DBT *key, 447 ID id ) 448{ 449 bdb_idl_cache_entry_t *cache_entry, idl_tmp; 450 DBT2bv( key, &idl_tmp.kstr ); 451 idl_tmp.db = db; 452 ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock ); 453 cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp, 454 bdb_idl_entry_cmp ); 455 if ( cache_entry != NULL ) { 456 if ( !BDB_IDL_IS_RANGE( cache_entry->idl ) && 457 cache_entry->idl[0] < BDB_IDL_DB_MAX ) { 458 size_t s = BDB_IDL_SIZEOF( cache_entry->idl ) + sizeof(ID); 459 cache_entry->idl = ch_realloc( cache_entry->idl, s ); 460 } 461 bdb_idl_insert( cache_entry->idl, id ); 462 } 463 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock ); 464} 465 466void 467bdb_idl_cache_del_id( 468 struct bdb_info *bdb, 469 DB *db, 470 DBT *key, 471 ID id ) 472{ 473 bdb_idl_cache_entry_t *cache_entry, idl_tmp; 474 DBT2bv( key, &idl_tmp.kstr ); 475 idl_tmp.db = db; 476 ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock ); 477 cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp, 478 bdb_idl_entry_cmp ); 479 if ( cache_entry != NULL ) { 480 bdb_idl_delete( cache_entry->idl, id ); 481 if ( cache_entry->idl[0] == 0 ) { 482 if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) cache_entry, 483 bdb_idl_entry_cmp ) == NULL ) { 484 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: " 485 "AVL delete failed\n", 486 0, 0, 0 ); 487 } 488 --bdb->bi_idl_cache_size; 489 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock ); 490 IDL_LRU_DELETE( bdb, cache_entry ); 491 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock ); 492 free( cache_entry->kstr.bv_val ); 493 free( cache_entry->idl ); 494 free( cache_entry ); 495 } 496 } 497 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock ); 498} 499 500int 501bdb_idl_fetch_key( 502 BackendDB *be, 503 DB *db, 504 DB_TXN *txn, 505 DBT *key, 506 ID *ids, 507 DBC **saved_cursor, 508 int get_flag ) 509{ 510 struct bdb_info *bdb = (struct bdb_info *) be->be_private; 511 int rc; 512 DBT data, key2, *kptr; 513 DBC *cursor; 514 ID *i; 515 void *ptr; 516 size_t len; 517 int rc2; 518 int flags = bdb->bi_db_opflags | DB_MULTIPLE; 519 int opflag; 520 521 /* If using BerkeleyDB 4.0, the buf must be large enough to 522 * grab the entire IDL in one get(), otherwise BDB will leak 523 * resources on subsequent get's. We can safely call get() 524 * twice - once for the data, and once to get the DB_NOTFOUND 525 * result meaning there's no more data. See ITS#2040 for details. 526 * This bug is fixed in BDB 4.1 so a smaller buffer will work if 527 * stack space is too limited. 528 * 529 * configure now requires Berkeley DB 4.1. 530 */ 531#if DB_VERSION_FULL < 0x04010000 532# define BDB_ENOUGH 5 533#else 534 /* We sometimes test with tiny IDLs, and BDB always wants buffers 535 * that are at least one page in size. 536 */ 537# if BDB_IDL_DB_SIZE < 4096 538# define BDB_ENOUGH 2048 539# else 540# define BDB_ENOUGH 1 541# endif 542#endif 543 ID buf[BDB_IDL_DB_SIZE*BDB_ENOUGH]; 544 545 char keybuf[16]; 546 547 Debug( LDAP_DEBUG_ARGS, 548 "bdb_idl_fetch_key: %s\n", 549 bdb_show_key( key, keybuf ), 0, 0 ); 550 551 assert( ids != NULL ); 552 553 if ( saved_cursor && *saved_cursor ) { 554 opflag = DB_NEXT; 555 } else if ( get_flag == LDAP_FILTER_GE ) { 556 opflag = DB_SET_RANGE; 557 } else if ( get_flag == LDAP_FILTER_LE ) { 558 opflag = DB_FIRST; 559 } else { 560 opflag = DB_SET; 561 } 562 563 /* only non-range lookups can use the IDL cache */ 564 if ( bdb->bi_idl_cache_size && opflag == DB_SET ) { 565 rc = bdb_idl_cache_get( bdb, db, key, ids ); 566 if ( rc != LDAP_NO_SUCH_OBJECT ) return rc; 567 } 568 569 DBTzero( &data ); 570 571 data.data = buf; 572 data.ulen = sizeof(buf); 573 data.flags = DB_DBT_USERMEM; 574 575 /* If we're not reusing an existing cursor, get a new one */ 576 if( opflag != DB_NEXT ) { 577 rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); 578 if( rc != 0 ) { 579 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " 580 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 ); 581 return rc; 582 } 583 } else { 584 cursor = *saved_cursor; 585 } 586 587 /* If this is a LE lookup, save original key so we can determine 588 * when to stop. If this is a GE lookup, save the key since it 589 * will be overwritten. 590 */ 591 if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) { 592 DBTzero( &key2 ); 593 key2.flags = DB_DBT_USERMEM; 594 key2.ulen = sizeof(keybuf); 595 key2.data = keybuf; 596 key2.size = key->size; 597 AC_MEMCPY( keybuf, key->data, key->size ); 598 kptr = &key2; 599 } else { 600 kptr = key; 601 } 602 len = key->size; 603 rc = cursor->c_get( cursor, kptr, &data, flags | opflag ); 604 605 /* skip presence key on range inequality lookups */ 606 while (rc == 0 && kptr->size != len) { 607 rc = cursor->c_get( cursor, kptr, &data, flags | DB_NEXT_NODUP ); 608 } 609 /* If we're doing a LE compare and the new key is greater than 610 * our search key, we're done 611 */ 612 if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->data, 613 key->data, key->size ) > 0 ) { 614 rc = DB_NOTFOUND; 615 } 616 if (rc == 0) { 617 i = ids; 618 while (rc == 0) { 619 u_int8_t *j; 620 621 DB_MULTIPLE_INIT( ptr, &data ); 622 while (ptr) { 623 DB_MULTIPLE_NEXT(ptr, &data, j, len); 624 if (j) { 625 ++i; 626 BDB_DISK2ID( j, i ); 627 } 628 } 629 rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP ); 630 } 631 if ( rc == DB_NOTFOUND ) rc = 0; 632 ids[0] = i - ids; 633 /* On disk, a range is denoted by 0 in the first element */ 634 if (ids[1] == 0) { 635 if (ids[0] != BDB_IDL_RANGE_SIZE) { 636 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " 637 "range size mismatch: expected %d, got %ld\n", 638 BDB_IDL_RANGE_SIZE, ids[0], 0 ); 639 cursor->c_close( cursor ); 640 return -1; 641 } 642 BDB_IDL_RANGE( ids, ids[2], ids[3] ); 643 } 644 data.size = BDB_IDL_SIZEOF(ids); 645 } 646 647 if ( saved_cursor && rc == 0 ) { 648 if ( !*saved_cursor ) 649 *saved_cursor = cursor; 650 rc2 = 0; 651 } 652 else 653 rc2 = cursor->c_close( cursor ); 654 if (rc2) { 655 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " 656 "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 ); 657 return rc2; 658 } 659 660 if( rc == DB_NOTFOUND ) { 661 return rc; 662 663 } else if( rc != 0 ) { 664 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " 665 "get failed: %s (%d)\n", 666 db_strerror(rc), rc, 0 ); 667 return rc; 668 669 } else if ( data.size == 0 || data.size % sizeof( ID ) ) { 670 /* size not multiple of ID size */ 671 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " 672 "odd size: expected %ld multiple, got %ld\n", 673 (long) sizeof( ID ), (long) data.size, 0 ); 674 return -1; 675 676 } else if ( data.size != BDB_IDL_SIZEOF(ids) ) { 677 /* size mismatch */ 678 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " 679 "get size mismatch: expected %ld, got %ld\n", 680 (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 ); 681 return -1; 682 } 683 684 if ( bdb->bi_idl_cache_max_size ) { 685 bdb_idl_cache_put( bdb, db, key, ids, rc ); 686 } 687 688 return rc; 689} 690 691 692int 693bdb_idl_insert_key( 694 BackendDB *be, 695 DB *db, 696 DB_TXN *tid, 697 DBT *key, 698 ID id ) 699{ 700 struct bdb_info *bdb = (struct bdb_info *) be->be_private; 701 int rc; 702 DBT data; 703 DBC *cursor; 704 ID lo, hi, nlo, nhi, nid; 705 char *err; 706 707 { 708 char buf[16]; 709 Debug( LDAP_DEBUG_ARGS, 710 "bdb_idl_insert_key: %lx %s\n", 711 (long) id, bdb_show_key( key, buf ), 0 ); 712 } 713 714 assert( id != NOID ); 715 716 DBTzero( &data ); 717 data.size = sizeof( ID ); 718 data.ulen = data.size; 719 data.flags = DB_DBT_USERMEM; 720 721 BDB_ID2DISK( id, &nid ); 722 723 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags ); 724 if ( rc != 0 ) { 725 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: " 726 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 ); 727 return rc; 728 } 729 data.data = &nlo; 730 /* Fetch the first data item for this key, to see if it 731 * exists and if it's a range. 732 */ 733 rc = cursor->c_get( cursor, key, &data, DB_SET ); 734 err = "c_get"; 735 if ( rc == 0 ) { 736 if ( nlo != 0 ) { 737 /* not a range, count the number of items */ 738 db_recno_t count; 739 rc = cursor->c_count( cursor, &count, 0 ); 740 if ( rc != 0 ) { 741 err = "c_count"; 742 goto fail; 743 } 744 if ( count >= BDB_IDL_DB_MAX ) { 745 /* No room, convert to a range */ 746 DBT key2 = *key; 747 db_recno_t i; 748 749 key2.dlen = key2.ulen; 750 key2.flags |= DB_DBT_PARTIAL; 751 752 BDB_DISK2ID( &nlo, &lo ); 753 data.data = &nhi; 754 755 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP ); 756 if ( rc != 0 && rc != DB_NOTFOUND ) { 757 err = "c_get next_nodup"; 758 goto fail; 759 } 760 if ( rc == DB_NOTFOUND ) { 761 rc = cursor->c_get( cursor, key, &data, DB_LAST ); 762 if ( rc != 0 ) { 763 err = "c_get last"; 764 goto fail; 765 } 766 } else { 767 rc = cursor->c_get( cursor, key, &data, DB_PREV ); 768 if ( rc != 0 ) { 769 err = "c_get prev"; 770 goto fail; 771 } 772 } 773 BDB_DISK2ID( &nhi, &hi ); 774 /* Update hi/lo if needed, then delete all the items 775 * between lo and hi 776 */ 777 if ( id < lo ) { 778 lo = id; 779 nlo = nid; 780 } else if ( id > hi ) { 781 hi = id; 782 nhi = nid; 783 } 784 data.data = &nid; 785 /* Don't fetch anything, just position cursor */ 786 data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; 787 data.dlen = data.ulen = 0; 788 rc = cursor->c_get( cursor, key, &data, DB_SET ); 789 if ( rc != 0 ) { 790 err = "c_get 2"; 791 goto fail; 792 } 793 rc = cursor->c_del( cursor, 0 ); 794 if ( rc != 0 ) { 795 err = "c_del range1"; 796 goto fail; 797 } 798 /* Delete all the records */ 799 for ( i=1; i<count; i++ ) { 800 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_DUP ); 801 if ( rc != 0 ) { 802 err = "c_get next_dup"; 803 goto fail; 804 } 805 rc = cursor->c_del( cursor, 0 ); 806 if ( rc != 0 ) { 807 err = "c_del range"; 808 goto fail; 809 } 810 } 811 /* Store the range marker */ 812 data.size = data.ulen = sizeof(ID); 813 data.flags = DB_DBT_USERMEM; 814 nid = 0; 815 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST ); 816 if ( rc != 0 ) { 817 err = "c_put range"; 818 goto fail; 819 } 820 nid = nlo; 821 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST ); 822 if ( rc != 0 ) { 823 err = "c_put lo"; 824 goto fail; 825 } 826 nid = nhi; 827 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST ); 828 if ( rc != 0 ) { 829 err = "c_put hi"; 830 goto fail; 831 } 832 } else { 833 /* There's room, just store it */ 834 goto put1; 835 } 836 } else { 837 /* It's a range, see if we need to rewrite 838 * the boundaries 839 */ 840 hi = id; 841 data.data = &nlo; 842 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP ); 843 if ( rc != 0 ) { 844 err = "c_get lo"; 845 goto fail; 846 } 847 BDB_DISK2ID( &nlo, &lo ); 848 if ( id > lo ) { 849 data.data = &nhi; 850 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP ); 851 if ( rc != 0 ) { 852 err = "c_get hi"; 853 goto fail; 854 } 855 BDB_DISK2ID( &nhi, &hi ); 856 } 857 if ( id < lo || id > hi ) { 858 /* Delete the current lo/hi */ 859 rc = cursor->c_del( cursor, 0 ); 860 if ( rc != 0 ) { 861 err = "c_del"; 862 goto fail; 863 } 864 data.data = &nid; 865 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST ); 866 if ( rc != 0 ) { 867 err = "c_put lo/hi"; 868 goto fail; 869 } 870 } 871 } 872 } else if ( rc == DB_NOTFOUND ) { 873put1: data.data = &nid; 874 rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA ); 875 /* Don't worry if it's already there */ 876 if ( rc != 0 && rc != DB_KEYEXIST ) { 877 err = "c_put id"; 878 goto fail; 879 } 880 } else { 881 /* initial c_get failed, nothing was done */ 882fail: 883 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: " 884 "%s failed: %s (%d)\n", err, db_strerror(rc), rc ); 885 cursor->c_close( cursor ); 886 return rc; 887 } 888 /* If key was added (didn't already exist) and using IDL cache, 889 * update key in IDL cache. 890 */ 891 if ( !rc && bdb->bi_idl_cache_max_size ) { 892 bdb_idl_cache_add_id( bdb, db, key, id ); 893 } 894 rc = cursor->c_close( cursor ); 895 if( rc != 0 ) { 896 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: " 897 "c_close failed: %s (%d)\n", 898 db_strerror(rc), rc, 0 ); 899 } 900 return rc; 901} 902 903int 904bdb_idl_delete_key( 905 BackendDB *be, 906 DB *db, 907 DB_TXN *tid, 908 DBT *key, 909 ID id ) 910{ 911 struct bdb_info *bdb = (struct bdb_info *) be->be_private; 912 int rc; 913 DBT data; 914 DBC *cursor; 915 ID lo, hi, tmp, nid, nlo, nhi; 916 char *err; 917 918 { 919 char buf[16]; 920 Debug( LDAP_DEBUG_ARGS, 921 "bdb_idl_delete_key: %lx %s\n", 922 (long) id, bdb_show_key( key, buf ), 0 ); 923 } 924 assert( id != NOID ); 925 926 if ( bdb->bi_idl_cache_size ) { 927 bdb_idl_cache_del( bdb, db, key ); 928 } 929 930 BDB_ID2DISK( id, &nid ); 931 932 DBTzero( &data ); 933 data.data = &tmp; 934 data.size = sizeof( id ); 935 data.ulen = data.size; 936 data.flags = DB_DBT_USERMEM; 937 938 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags ); 939 if ( rc != 0 ) { 940 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: " 941 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 ); 942 return rc; 943 } 944 /* Fetch the first data item for this key, to see if it 945 * exists and if it's a range. 946 */ 947 rc = cursor->c_get( cursor, key, &data, DB_SET ); 948 err = "c_get"; 949 if ( rc == 0 ) { 950 if ( tmp != 0 ) { 951 /* Not a range, just delete it */ 952 if (tmp != nid) { 953 /* position to correct item */ 954 tmp = nid; 955 rc = cursor->c_get( cursor, key, &data, DB_GET_BOTH ); 956 if ( rc != 0 ) { 957 err = "c_get id"; 958 goto fail; 959 } 960 } 961 rc = cursor->c_del( cursor, 0 ); 962 if ( rc != 0 ) { 963 err = "c_del id"; 964 goto fail; 965 } 966 } else { 967 /* It's a range, see if we need to rewrite 968 * the boundaries 969 */ 970 data.data = &nlo; 971 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP ); 972 if ( rc != 0 ) { 973 err = "c_get lo"; 974 goto fail; 975 } 976 BDB_DISK2ID( &nlo, &lo ); 977 data.data = &nhi; 978 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP ); 979 if ( rc != 0 ) { 980 err = "c_get hi"; 981 goto fail; 982 } 983 BDB_DISK2ID( &nhi, &hi ); 984 if ( id == lo || id == hi ) { 985 if ( id == lo ) { 986 id++; 987 lo = id; 988 } else if ( id == hi ) { 989 id--; 990 hi = id; 991 } 992 if ( lo >= hi ) { 993 /* The range has collapsed... */ 994 rc = db->del( db, tid, key, 0 ); 995 if ( rc != 0 ) { 996 err = "del"; 997 goto fail; 998 } 999 } else { 1000 if ( id == lo ) { 1001 /* reposition on lo slot */ 1002 data.data = &nlo; 1003 cursor->c_get( cursor, key, &data, DB_PREV ); 1004 } 1005 rc = cursor->c_del( cursor, 0 ); 1006 if ( rc != 0 ) { 1007 err = "c_del"; 1008 goto fail; 1009 } 1010 } 1011 if ( lo <= hi ) { 1012 BDB_ID2DISK( id, &nid ); 1013 data.data = &nid; 1014 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST ); 1015 if ( rc != 0 ) { 1016 err = "c_put lo/hi"; 1017 goto fail; 1018 } 1019 } 1020 } 1021 } 1022 } else { 1023 /* initial c_get failed, nothing was done */ 1024fail: 1025 if ( rc != DB_NOTFOUND ) { 1026 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: " 1027 "%s failed: %s (%d)\n", err, db_strerror(rc), rc ); 1028 } 1029 cursor->c_close( cursor ); 1030 return rc; 1031 } 1032 rc = cursor->c_close( cursor ); 1033 if( rc != 0 ) { 1034 Debug( LDAP_DEBUG_ANY, 1035 "=> bdb_idl_delete_key: c_close failed: %s (%d)\n", 1036 db_strerror(rc), rc, 0 ); 1037 } 1038 1039 return rc; 1040} 1041 1042 1043/* 1044 * idl_intersection - return a = a intersection b 1045 */ 1046int 1047bdb_idl_intersection( 1048 ID *a, 1049 ID *b ) 1050{ 1051 ID ida, idb; 1052 ID idmax, idmin; 1053 ID cursora = 0, cursorb = 0, cursorc; 1054 int swap = 0; 1055 1056 if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) { 1057 a[0] = 0; 1058 return 0; 1059 } 1060 1061 idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) ); 1062 idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) ); 1063 if ( idmin > idmax ) { 1064 a[0] = 0; 1065 return 0; 1066 } else if ( idmin == idmax ) { 1067 a[0] = 1; 1068 a[1] = idmin; 1069 return 0; 1070 } 1071 1072 if ( BDB_IDL_IS_RANGE( a ) ) { 1073 if ( BDB_IDL_IS_RANGE(b) ) { 1074 /* If both are ranges, just shrink the boundaries */ 1075 a[1] = idmin; 1076 a[2] = idmax; 1077 return 0; 1078 } else { 1079 /* Else swap so that b is the range, a is a list */ 1080 ID *tmp = a; 1081 a = b; 1082 b = tmp; 1083 swap = 1; 1084 } 1085 } 1086 1087 /* If a range completely covers the list, the result is 1088 * just the list. If idmin to idmax is contiguous, just 1089 * turn it into a range. 1090 */ 1091 if ( BDB_IDL_IS_RANGE( b ) 1092 && BDB_IDL_RANGE_FIRST( b ) <= BDB_IDL_RANGE_FIRST( a ) 1093 && BDB_IDL_RANGE_LAST( b ) >= BDB_IDL_RANGE_LAST( a ) ) { 1094 if (idmax - idmin + 1 == a[0]) 1095 { 1096 a[0] = NOID; 1097 a[1] = idmin; 1098 a[2] = idmax; 1099 } 1100 goto done; 1101 } 1102 1103 /* Fine, do the intersection one element at a time. 1104 * First advance to idmin in both IDLs. 1105 */ 1106 cursora = cursorb = idmin; 1107 ida = bdb_idl_first( a, &cursora ); 1108 idb = bdb_idl_first( b, &cursorb ); 1109 cursorc = 0; 1110 1111 while( ida <= idmax || idb <= idmax ) { 1112 if( ida == idb ) { 1113 a[++cursorc] = ida; 1114 ida = bdb_idl_next( a, &cursora ); 1115 idb = bdb_idl_next( b, &cursorb ); 1116 } else if ( ida < idb ) { 1117 ida = bdb_idl_next( a, &cursora ); 1118 } else { 1119 idb = bdb_idl_next( b, &cursorb ); 1120 } 1121 } 1122 a[0] = cursorc; 1123done: 1124 if (swap) 1125 BDB_IDL_CPY( b, a ); 1126 1127 return 0; 1128} 1129 1130 1131/* 1132 * idl_union - return a = a union b 1133 */ 1134int 1135bdb_idl_union( 1136 ID *a, 1137 ID *b ) 1138{ 1139 ID ida, idb; 1140 ID cursora = 0, cursorb = 0, cursorc; 1141 1142 if ( BDB_IDL_IS_ZERO( b ) ) { 1143 return 0; 1144 } 1145 1146 if ( BDB_IDL_IS_ZERO( a ) ) { 1147 BDB_IDL_CPY( a, b ); 1148 return 0; 1149 } 1150 1151 if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) { 1152over: ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) ); 1153 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) ); 1154 a[0] = NOID; 1155 a[1] = ida; 1156 a[2] = idb; 1157 return 0; 1158 } 1159 1160 ida = bdb_idl_first( a, &cursora ); 1161 idb = bdb_idl_first( b, &cursorb ); 1162 1163 cursorc = b[0]; 1164 1165 /* The distinct elements of a are cat'd to b */ 1166 while( ida != NOID || idb != NOID ) { 1167 if ( ida < idb ) { 1168 if( ++cursorc > BDB_IDL_UM_MAX ) { 1169 goto over; 1170 } 1171 b[cursorc] = ida; 1172 ida = bdb_idl_next( a, &cursora ); 1173 1174 } else { 1175 if ( ida == idb ) 1176 ida = bdb_idl_next( a, &cursora ); 1177 idb = bdb_idl_next( b, &cursorb ); 1178 } 1179 } 1180 1181 /* b is copied back to a in sorted order */ 1182 a[0] = cursorc; 1183 cursora = 1; 1184 cursorb = 1; 1185 cursorc = b[0]+1; 1186 while (cursorb <= b[0] || cursorc <= a[0]) { 1187 if (cursorc > a[0]) 1188 idb = NOID; 1189 else 1190 idb = b[cursorc]; 1191 if (cursorb <= b[0] && b[cursorb] < idb) 1192 a[cursora++] = b[cursorb++]; 1193 else { 1194 a[cursora++] = idb; 1195 cursorc++; 1196 } 1197 } 1198 1199 return 0; 1200} 1201 1202 1203#if 0 1204/* 1205 * bdb_idl_notin - return a intersection ~b (or a minus b) 1206 */ 1207int 1208bdb_idl_notin( 1209 ID *a, 1210 ID *b, 1211 ID *ids ) 1212{ 1213 ID ida, idb; 1214 ID cursora = 0, cursorb = 0; 1215 1216 if( BDB_IDL_IS_ZERO( a ) || 1217 BDB_IDL_IS_ZERO( b ) || 1218 BDB_IDL_IS_RANGE( b ) ) 1219 { 1220 BDB_IDL_CPY( ids, a ); 1221 return 0; 1222 } 1223 1224 if( BDB_IDL_IS_RANGE( a ) ) { 1225 BDB_IDL_CPY( ids, a ); 1226 return 0; 1227 } 1228 1229 ida = bdb_idl_first( a, &cursora ), 1230 idb = bdb_idl_first( b, &cursorb ); 1231 1232 ids[0] = 0; 1233 1234 while( ida != NOID ) { 1235 if ( idb == NOID ) { 1236 /* we could shortcut this */ 1237 ids[++ids[0]] = ida; 1238 ida = bdb_idl_next( a, &cursora ); 1239 1240 } else if ( ida < idb ) { 1241 ids[++ids[0]] = ida; 1242 ida = bdb_idl_next( a, &cursora ); 1243 1244 } else if ( ida > idb ) { 1245 idb = bdb_idl_next( b, &cursorb ); 1246 1247 } else { 1248 ida = bdb_idl_next( a, &cursora ); 1249 idb = bdb_idl_next( b, &cursorb ); 1250 } 1251 } 1252 1253 return 0; 1254} 1255#endif 1256 1257ID bdb_idl_first( ID *ids, ID *cursor ) 1258{ 1259 ID pos; 1260 1261 if ( ids[0] == 0 ) { 1262 *cursor = NOID; 1263 return NOID; 1264 } 1265 1266 if ( BDB_IDL_IS_RANGE( ids ) ) { 1267 if( *cursor < ids[1] ) { 1268 *cursor = ids[1]; 1269 } 1270 return *cursor; 1271 } 1272 1273 if ( *cursor == 0 ) 1274 pos = 1; 1275 else 1276 pos = bdb_idl_search( ids, *cursor ); 1277 1278 if( pos > ids[0] ) { 1279 return NOID; 1280 } 1281 1282 *cursor = pos; 1283 return ids[pos]; 1284} 1285 1286ID bdb_idl_next( ID *ids, ID *cursor ) 1287{ 1288 if ( BDB_IDL_IS_RANGE( ids ) ) { 1289 if( ids[2] < ++(*cursor) ) { 1290 return NOID; 1291 } 1292 return *cursor; 1293 } 1294 1295 if ( ++(*cursor) <= ids[0] ) { 1296 return ids[*cursor]; 1297 } 1298 1299 return NOID; 1300} 1301 1302#ifdef BDB_HIER 1303 1304/* Add one ID to an unsorted list. We ensure that the first element is the 1305 * minimum and the last element is the maximum, for fast range compaction. 1306 * this means IDLs up to length 3 are always sorted... 1307 */ 1308int bdb_idl_append_one( ID *ids, ID id ) 1309{ 1310 if (BDB_IDL_IS_RANGE( ids )) { 1311 /* if already in range, treat as a dup */ 1312 if (id >= BDB_IDL_RANGE_FIRST(ids) && id <= BDB_IDL_RANGE_LAST(ids)) 1313 return -1; 1314 if (id < BDB_IDL_RANGE_FIRST(ids)) 1315 ids[1] = id; 1316 else if (id > BDB_IDL_RANGE_LAST(ids)) 1317 ids[2] = id; 1318 return 0; 1319 } 1320 if ( ids[0] ) { 1321 ID tmp; 1322 1323 if (id < ids[1]) { 1324 tmp = ids[1]; 1325 ids[1] = id; 1326 id = tmp; 1327 } 1328 if ( ids[0] > 1 && id < ids[ids[0]] ) { 1329 tmp = ids[ids[0]]; 1330 ids[ids[0]] = id; 1331 id = tmp; 1332 } 1333 } 1334 ids[0]++; 1335 if ( ids[0] >= BDB_IDL_UM_MAX ) { 1336 ids[0] = NOID; 1337 ids[2] = id; 1338 } else { 1339 ids[ids[0]] = id; 1340 } 1341 return 0; 1342} 1343 1344/* Append sorted list b to sorted list a. The result is unsorted but 1345 * a[1] is the min of the result and a[a[0]] is the max. 1346 */ 1347int bdb_idl_append( ID *a, ID *b ) 1348{ 1349 ID ida, idb, tmp, swap = 0; 1350 1351 if ( BDB_IDL_IS_ZERO( b ) ) { 1352 return 0; 1353 } 1354 1355 if ( BDB_IDL_IS_ZERO( a ) ) { 1356 BDB_IDL_CPY( a, b ); 1357 return 0; 1358 } 1359 1360 ida = BDB_IDL_LAST( a ); 1361 idb = BDB_IDL_LAST( b ); 1362 if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) || 1363 a[0] + b[0] >= BDB_IDL_UM_MAX ) { 1364 a[2] = IDL_MAX( ida, idb ); 1365 a[1] = IDL_MIN( a[1], b[1] ); 1366 a[0] = NOID; 1367 return 0; 1368 } 1369 1370 if ( b[0] > 1 && ida > idb ) { 1371 swap = idb; 1372 a[a[0]] = idb; 1373 b[b[0]] = ida; 1374 } 1375 1376 if ( b[1] < a[1] ) { 1377 tmp = a[1]; 1378 a[1] = b[1]; 1379 } else { 1380 tmp = b[1]; 1381 } 1382 a[0]++; 1383 a[a[0]] = tmp; 1384 1385 if ( b[0] > 1 ) { 1386 int i = b[0] - 1; 1387 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID)); 1388 a[0] += i; 1389 } 1390 if ( swap ) { 1391 b[b[0]] = swap; 1392 } 1393 return 0; 1394} 1395 1396#if 1 1397 1398/* Quicksort + Insertion sort for small arrays */ 1399 1400#define SMALL 8 1401#define SWAP(a,b) itmp=(a);(a)=(b);(b)=itmp 1402 1403void 1404bdb_idl_sort( ID *ids, ID *tmp ) 1405{ 1406 int *istack = (int *)tmp; 1407 int i,j,k,l,ir,jstack; 1408 ID a, itmp; 1409 1410 if ( BDB_IDL_IS_RANGE( ids )) 1411 return; 1412 1413 ir = ids[0]; 1414 l = 1; 1415 jstack = 0; 1416 for(;;) { 1417 if (ir - l < SMALL) { /* Insertion sort */ 1418 for (j=l+1;j<=ir;j++) { 1419 a = ids[j]; 1420 for (i=j-1;i>=1;i--) { 1421 if (ids[i] <= a) break; 1422 ids[i+1] = ids[i]; 1423 } 1424 ids[i+1] = a; 1425 } 1426 if (jstack == 0) break; 1427 ir = istack[jstack--]; 1428 l = istack[jstack--]; 1429 } else { 1430 k = (l + ir) >> 1; /* Choose median of left, center, right */ 1431 SWAP(ids[k], ids[l+1]); 1432 if (ids[l] > ids[ir]) { 1433 SWAP(ids[l], ids[ir]); 1434 } 1435 if (ids[l+1] > ids[ir]) { 1436 SWAP(ids[l+1], ids[ir]); 1437 } 1438 if (ids[l] > ids[l+1]) { 1439 SWAP(ids[l], ids[l+1]); 1440 } 1441 i = l+1; 1442 j = ir; 1443 a = ids[l+1]; 1444 for(;;) { 1445 do i++; while(ids[i] < a); 1446 do j--; while(ids[j] > a); 1447 if (j < i) break; 1448 SWAP(ids[i],ids[j]); 1449 } 1450 ids[l+1] = ids[j]; 1451 ids[j] = a; 1452 jstack += 2; 1453 if (ir-i+1 >= j-1) { 1454 istack[jstack] = ir; 1455 istack[jstack-1] = i; 1456 ir = j-1; 1457 } else { 1458 istack[jstack] = j-1; 1459 istack[jstack-1] = l; 1460 l = i; 1461 } 1462 } 1463 } 1464} 1465 1466#else 1467 1468/* 8 bit Radix sort + insertion sort 1469 * 1470 * based on code from http://www.cubic.org/docs/radix.htm 1471 * with improvements by mbackes@symas.com and hyc@symas.com 1472 * 1473 * This code is O(n) but has a relatively high constant factor. For lists 1474 * up to ~50 Quicksort is slightly faster; up to ~100 they are even. 1475 * Much faster than quicksort for lists longer than ~100. Insertion 1476 * sort is actually superior for lists <50. 1477 */ 1478 1479#define BUCKETS (1<<8) 1480#define SMALL 50 1481 1482void 1483bdb_idl_sort( ID *ids, ID *tmp ) 1484{ 1485 int count, soft_limit, phase = 0, size = ids[0]; 1486 ID *idls[2]; 1487 unsigned char *maxv = (unsigned char *)&ids[size]; 1488 1489 if ( BDB_IDL_IS_RANGE( ids )) 1490 return; 1491 1492 /* Use insertion sort for small lists */ 1493 if ( size <= SMALL ) { 1494 int i,j; 1495 ID a; 1496 1497 for (j=1;j<=size;j++) { 1498 a = ids[j]; 1499 for (i=j-1;i>=1;i--) { 1500 if (ids[i] <= a) break; 1501 ids[i+1] = ids[i]; 1502 } 1503 ids[i+1] = a; 1504 } 1505 return; 1506 } 1507 1508 tmp[0] = size; 1509 idls[0] = ids; 1510 idls[1] = tmp; 1511 1512#if BYTE_ORDER == BIG_ENDIAN 1513 for (soft_limit = 0; !maxv[soft_limit]; soft_limit++); 1514#else 1515 for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--); 1516#endif 1517 1518 for ( 1519#if BYTE_ORDER == BIG_ENDIAN 1520 count = sizeof(ID)-1; count >= soft_limit; --count 1521#else 1522 count = 0; count <= soft_limit; ++count 1523#endif 1524 ) { 1525 unsigned int num[BUCKETS], * np, n, sum; 1526 int i; 1527 ID *sp, *source, *dest; 1528 unsigned char *bp, *source_start; 1529 1530 source = idls[phase]+1; 1531 dest = idls[phase^1]+1; 1532 source_start = ((unsigned char *) source) + count; 1533 1534 np = num; 1535 for ( i = BUCKETS; i > 0; --i ) *np++ = 0; 1536 1537 /* count occurences of every byte value */ 1538 bp = source_start; 1539 for ( i = size; i > 0; --i, bp += sizeof(ID) ) 1540 num[*bp]++; 1541 1542 /* transform count into index by summing elements and storing 1543 * into same array 1544 */ 1545 sum = 0; 1546 np = num; 1547 for ( i = BUCKETS; i > 0; --i ) { 1548 n = *np; 1549 *np++ = sum; 1550 sum += n; 1551 } 1552 1553 /* fill dest with the right values in the right place */ 1554 bp = source_start; 1555 sp = source; 1556 for ( i = size; i > 0; --i, bp += sizeof(ID) ) { 1557 np = num + *bp; 1558 dest[*np] = *sp++; 1559 ++(*np); 1560 } 1561 phase ^= 1; 1562 } 1563 1564 /* copy back from temp if needed */ 1565 if ( phase ) { 1566 ids++; tmp++; 1567 for ( count = 0; count < size; ++count ) 1568 *ids++ = *tmp++; 1569 } 1570} 1571#endif /* Quick vs Radix */ 1572 1573#endif /* BDB_HIER */ 1574