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