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-2005 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 #if 0   /* unused */
 246 static int idl_delete( ID *ids, ID id )
 247 {
 248         unsigned x = bdb_idl_search( ids, id );
 249
 250 #if IDL_DEBUG > 1
 251 #ifdef NEW_LOGGING
 252         LDAP_LOG( INDEX, DETAIL1, "delete: %04lx at %d\n", (long) id, x, 0 );
 253 #else
 254         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 255         idl_dump( ids );
 256 #endif
 257 #elif IDL_DEBUG > 0
 258         idl_check( ids );
 259 #endif
 260
 261         assert( x > 0 );
 262
 263         if( x <= 0 ) {
 264                 /* internal error */
 265                 return -2;
 266         }
 267
 268         if( x > ids[0] || ids[x] != id ) {
 269                 /* not found */
 270                 return -1;
 271
 272         } else if ( --ids[0] == 0 ) {
 273                 if( x != 1 ) {
 274                         return -3;
 275                 }
 276
 277         } else {
 278                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 279         }
 280
 281 #if IDL_DEBUG > 1
 282         idl_dump( ids );
 283 #elif IDL_DEBUG > 0
 284         idl_check( ids );
 285 #endif
 286
 287         return 0;
 288 }
 289 #endif  /* unused */
 290
 291 static char *
 292 bdb_show_key(
 293         DBT             *key,
 294         char            *buf )
 295 {
 296         if ( key->size == 4 /* LUTIL_HASH_BYTES */ ) {
 297                 unsigned char *c = key->data;
 298                 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
 299                 return buf;
 300         } else {
 301                 return key->data;
 302         }
 303 }
 304
 305 /* Find a db/key pair in the IDL cache. If ids is non-NULL,
 306  * copy the cached IDL into it, otherwise just return the status.
 307  */
 308 int
 309 bdb_idl_cache_get(
 310         struct bdb_info *bdb,
 311         DB                      *db,
 312         DBT                     *key,
 313         ID                      *ids )
 314 {
 315         bdb_idl_cache_entry_t idl_tmp;
 316         bdb_idl_cache_entry_t *matched_idl_entry;
 317         int rc = LDAP_NO_SUCH_OBJECT;
 318
 319         DBT2bv( key, &idl_tmp.kstr );
 320         idl_tmp.db = db;
 321         ldap_pvt_thread_rdwr_rlock( &bdb->bi_idl_tree_rwlock );
 322         matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
 323                                       bdb_idl_entry_cmp );
 324         if ( matched_idl_entry != NULL ) {
 325                 if ( matched_idl_entry->idl && ids )
 326                         BDB_IDL_CPY( ids, matched_idl_entry->idl );
 327                 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
 328                 IDL_LRU_DELETE( bdb, matched_idl_entry );
 329                 IDL_LRU_ADD( bdb, matched_idl_entry );
 330                 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
 331                 if ( matched_idl_entry->idl )
 332                         rc = LDAP_SUCCESS;
 333                 else
 334                         rc = DB_NOTFOUND;
 335         }
 336         ldap_pvt_thread_rdwr_runlock( &bdb->bi_idl_tree_rwlock );
 337
 338         return rc;
 339 }
 340
 341 void
 342 bdb_idl_cache_put(
 343         struct bdb_info *bdb,
 344         DB                      *db,
 345         DBT                     *key,
 346         ID                      *ids,
 347         int                     rc )
 348 {
 349         bdb_idl_cache_entry_t idl_tmp;
 350         bdb_idl_cache_entry_t *ee;
 351
 352         DBT2bv( key, &idl_tmp.kstr );
 353
 354         ee = (bdb_idl_cache_entry_t *) ch_malloc(
 355                 sizeof( bdb_idl_cache_entry_t ) );
 356         ee->db = db;
 357         if ( rc == DB_NOTFOUND) {
 358                 ee->idl = NULL;
 359         } else {
 360                 ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) );
 361                 BDB_IDL_CPY( ee->idl, ids );
 362         }
 363         ee->idl_lru_prev = NULL;
 364         ee->idl_lru_next = NULL;
 365         ber_dupbv( &ee->kstr, &idl_tmp.kstr );
 366         ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
 367         if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee,
 368                 bdb_idl_entry_cmp, avl_dup_error ))
 369         {
 370                 ch_free( ee->kstr.bv_val );
 371                 ch_free( ee->idl );
 372                 ch_free( ee );
 373                 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
 374                 return;
 375         }
 376         ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
 377         IDL_LRU_ADD( bdb, ee );
 378         if ( ++bdb->bi_idl_cache_size > bdb->bi_idl_cache_max_size ) {
 379                 int i = 0;
 380                 while ( bdb->bi_idl_lru_tail != NULL && i < 10 ) {
 381                         ee = bdb->bi_idl_lru_tail;
 382                         if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee,
 383                                     bdb_idl_entry_cmp ) == NULL ) {
 384 #ifdef NEW_LOGGING
 385                                 LDAP_LOG( INDEX, ERR,
 386                                         "bdb_idl_cache_put: AVL delete failed\n",
 387                                         0, 0, 0 );
 388 #else
 389                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: "
 390                                         "AVL delete failed\n",
 391                                         0, 0, 0 );
 392 #endif
 393                         }
 394                         IDL_LRU_DELETE( bdb, ee );
 395                         i++;
 396                         --bdb->bi_idl_cache_size;
 397                         ch_free( ee->kstr.bv_val );
 398                         ch_free( ee->idl );
 399                         ch_free( ee );
 400                 }
 401         }
 402
 403         ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
 404         ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
 405 }
 406
 407 void
 408 bdb_idl_cache_del(
 409         struct bdb_info *bdb,
 410         DB                      *db,
 411         DBT                     *key )
 412 {
 413         bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp;
 414         DBT2bv( key, &idl_tmp.kstr );
 415         idl_tmp.db = db;
 416         ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
 417         matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
 418                                       bdb_idl_entry_cmp );
 419         if ( matched_idl_entry != NULL ) {
 420                 if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry,
 421                                     bdb_idl_entry_cmp ) == NULL ) {
 422 #ifdef NEW_LOGGING
 423                         LDAP_LOG( INDEX, ERR,
 424                                 "bdb_idl_cache_del: AVL delete failed\n",
 425                                 0, 0, 0 );
 426 #else
 427                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
 428                                 "AVL delete failed\n",
 429                                 0, 0, 0 );
 430 #endif
 431                 }
 432                 --bdb->bi_idl_cache_size;
 433                 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
 434                 IDL_LRU_DELETE( bdb, matched_idl_entry );
 435                 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
 436                 free( matched_idl_entry->kstr.bv_val );
 437                 if ( matched_idl_entry->idl )
 438                         free( matched_idl_entry->idl );
 439                 free( matched_idl_entry );
 440         }
 441         ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
 442 }
 443
 444 int
 445 bdb_idl_fetch_key(
 446         BackendDB       *be,
 447         DB                      *db,
 448         DB_TXN          *tid,
 449         DBT                     *key,
 450         ID                      *ids )
 451 {
 452         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 453         int rc;
 454         DBT data;
 455         DBC *cursor;
 456         ID *i;
 457         void *ptr;
 458         size_t len;
 459         int rc2;
 460         int flags = bdb->bi_db_opflags | DB_MULTIPLE;
 461
 462         /* If using BerkeleyDB 4.0, the buf must be large enough to
 463          * grab the entire IDL in one get(), otherwise BDB will leak
 464          * resources on subsequent get's.  We can safely call get()
 465          * twice - once for the data, and once to get the DB_NOTFOUND
 466          * result meaning there's no more data. See ITS#2040 for details.
 467          * This bug is fixed in BDB 4.1 so a smaller buffer will work if
 468          * stack space is too limited.
 469          *
 470          * configure now requires Berkeley DB 4.1.
 471          */
 472 #if (DB_VERSION_MAJOR == 4) && (DB_VERSION_MINOR == 0)
 473 #       define BDB_ENOUGH 5
 474 #else
 475 #       define BDB_ENOUGH 1
 476 #endif
 477         ID buf[BDB_IDL_DB_SIZE*BDB_ENOUGH];
 478
 479         char keybuf[16];
 480
 481 #ifdef NEW_LOGGING
 482         LDAP_LOG( INDEX, ARGS,
 483                 "bdb_idl_fetch_key: %s\n",
 484                 bdb_show_key( key, keybuf ), 0, 0 );
 485 #else
 486         Debug( LDAP_DEBUG_ARGS,
 487                 "bdb_idl_fetch_key: %s\n",
 488                 bdb_show_key( key, keybuf ), 0, 0 );
 489 #endif
 490
 491         assert( ids != NULL );
 492
 493         if ( bdb->bi_idl_cache_size ) {
 494                 rc = bdb_idl_cache_get( bdb, db, key, ids );
 495                 if ( rc != LDAP_NO_SUCH_OBJECT ) return rc;
 496         }
 497
 498         DBTzero( &data );
 499
 500         data.data = buf;
 501         data.ulen = sizeof(buf);
 502         data.flags = DB_DBT_USERMEM;
 503
 504         if ( tid ) flags |= DB_RMW;
 505
 506         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 507         if( rc != 0 ) {
 508 #ifdef NEW_LOGGING
 509                 LDAP_LOG( INDEX, ERR,
 510                         "bdb_idl_fetch_key: cursor failed: %s (%d)\n",
 511                         db_strerror(rc), rc, 0 );
 512 #else
 513                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 514                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 515 #endif
 516                 return rc;
 517         }
 518
 519         rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
 520         if (rc == 0) {
 521                 i = ids;
 522                 while (rc == 0) {
 523                         u_int8_t *j;
 524
 525                         DB_MULTIPLE_INIT( ptr, &data );
 526                         while (ptr) {
 527                                 DB_MULTIPLE_NEXT(ptr, &data, j, len);
 528                                 if (j) {
 529                                         ++i;
 530                                         AC_MEMCPY( i, j, sizeof(ID) );
 531                                 }
 532                         }
 533                         rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
 534                 }
 535                 if ( rc == DB_NOTFOUND ) rc = 0;
 536                 ids[0] = i - ids;
 537                 /* On disk, a range is denoted by 0 in the first element */
 538                 if (ids[1] == 0) {
 539                         if (ids[0] != BDB_IDL_RANGE_SIZE) {
 540 #ifdef NEW_LOGGING
 541                                 LDAP_LOG( INDEX, ERR,
 542                                         "=> bdb_idl_fetch_key: range size mismatch: "
 543                                         "expected %ld, got %ld\n",
 544                                         BDB_IDL_RANGE_SIZE, ids[0], 0 );
 545 #else
 546                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 547                                         "range size mismatch: expected %d, got %ld\n",
 548                                         BDB_IDL_RANGE_SIZE, ids[0], 0 );
 549 #endif
 550                                 cursor->c_close( cursor );
 551                                 return -1;
 552                         }
 553                         BDB_IDL_RANGE( ids, ids[2], ids[3] );
 554                 }
 555                 data.size = BDB_IDL_SIZEOF(ids);
 556         }
 557
 558         rc2 = cursor->c_close( cursor );
 559         if (rc2) {
 560 #ifdef NEW_LOGGING
 561                 LDAP_LOG( INDEX, ERR,
 562                         "bdb_idl_fetch_key: close failed: %s (%d)\n",
 563                         db_strerror(rc2), rc2, 0 );
 564 #else
 565                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 566                         "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
 567 #endif
 568                 return rc2;
 569         }
 570
 571         if( rc == DB_NOTFOUND ) {
 572                 return rc;
 573
 574         } else if( rc != 0 ) {
 575 #ifdef NEW_LOGGING
 576                 LDAP_LOG( INDEX, ERR,
 577                         "bdb_idl_fetch_key: get failed: %s (%d)\n",
 578                         db_strerror(rc), rc, 0 );
 579 #else
 580                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 581                         "get failed: %s (%d)\n",
 582                         db_strerror(rc), rc, 0 );
 583 #endif
 584                 return rc;
 585
 586         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 587                 /* size not multiple of ID size */
 588 #ifdef NEW_LOGGING
 589                 LDAP_LOG( INDEX, ERR,
 590                         "bdb_idl_fetch_key: odd size: expected %ld multiple, got %ld\n",
 591                         (long) sizeof( ID ), (long) data.size, 0 );
 592 #else
 593                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 594                         "odd size: expected %ld multiple, got %ld\n",
 595                         (long) sizeof( ID ), (long) data.size, 0 );
 596 #endif
 597                 return -1;
 598
 599         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 600                 /* size mismatch */
 601 #ifdef NEW_LOGGING
 602                 LDAP_LOG( INDEX, ERR,
 603                         "bdb_idl_fetch_key: get size mismatch: expected %ld, got %ld\n",
 604                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 605 #else
 606                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 607                         "get size mismatch: expected %ld, got %ld\n",
 608                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 609 #endif
 610                 return -1;
 611         }
 612
 613         if ( bdb->bi_idl_cache_max_size ) {
 614                 bdb_idl_cache_put( bdb, db, key, ids, rc );
 615         }
 616
 617         return rc;
 618 }
 619
 620
 621 int
 622 bdb_idl_insert_key(
 623         BackendDB       *be,
 624         DB                      *db,
 625         DB_TXN          *tid,
 626         DBT                     *key,
 627         ID                      id )
 628 {
 629         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 630         int     rc;
 631         DBT data;
 632         DBC *cursor;
 633         ID lo, hi, tmp;
 634         char *err;
 635
 636         {
 637                 char buf[16];
 638 #ifdef NEW_LOGGING
 639                 LDAP_LOG( INDEX, ARGS,
 640                         "bdb_idl_insert_key: %lx %s\n",
 641                         (long) id, bdb_show_key( key, buf ), 0 );
 642 #else
 643                 Debug( LDAP_DEBUG_ARGS,
 644                         "bdb_idl_insert_key: %lx %s\n",
 645                         (long) id, bdb_show_key( key, buf ), 0 );
 646 #endif
 647         }
 648
 649         assert( id != NOID );
 650
 651         if ( bdb->bi_idl_cache_size ) {
 652                 bdb_idl_cache_del( bdb, db, key );
 653         }
 654
 655         DBTzero( &data );
 656         data.size = sizeof( ID );
 657         data.ulen = data.size;
 658         data.flags = DB_DBT_USERMEM;
 659
 660         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 661         if ( rc != 0 ) {
 662 #ifdef NEW_LOGGING
 663                 LDAP_LOG( INDEX, ERR,
 664                         "bdb_idl_insert_key: cursor failed: %s (%d)\n",
 665                         db_strerror(rc), rc, 0 );
 666 #else
 667                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 668                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 669 #endif
 670                 return rc;
 671         }
 672         data.data = &tmp;
 673         /* Fetch the first data item for this key, to see if it
 674          * exists and if it's a range.
 675          */
 676         rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 677         err = "c_get";
 678         if ( rc == 0 ) {
 679                 if ( tmp != 0 ) {
 680                         /* not a range, count the number of items */
 681                         db_recno_t count;
 682                         rc = cursor->c_count( cursor, &count, 0 );
 683                         if ( rc != 0 ) {
 684                                 err = "c_count";
 685                                 goto fail;
 686                         }
 687                         if ( count >= BDB_IDL_DB_MAX ) {
 688                         /* No room, convert to a range */
 689                                 DBT key2 = *key;
 690
 691                                 key2.dlen = key2.ulen;
 692                                 key2.flags |= DB_DBT_PARTIAL;
 693
 694                                 lo = tmp;
 695                                 data.data = &hi;
 696                                 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
 697                                 if ( rc != 0 && rc != DB_NOTFOUND ) {
 698                                         err = "c_get next_nodup";
 699                                         goto fail;
 700                                 }
 701                                 if ( rc == DB_NOTFOUND ) {
 702                                         rc = cursor->c_get( cursor, key, &data, DB_LAST );
 703                                         if ( rc != 0 ) {
 704                                                 err = "c_get last";
 705                                                 goto fail;
 706                                         }
 707                                 } else {
 708                                         rc = cursor->c_get( cursor, key, &data, DB_PREV );
 709                                         if ( rc != 0 ) {
 710                                                 err = "c_get prev";
 711                                                 goto fail;
 712                                         }
 713                                 }
 714                                 if ( id < lo )
 715                                         lo = id;
 716                                 else if ( id > hi )
 717                                         hi = id;
 718                                 rc = db->del( db, tid, key, 0 );
 719                                 if ( rc != 0 ) {
 720                                         err = "del";
 721                                         goto fail;
 722                                 }
 723                                 data.data = &id;
 724                                 id = 0;
 725                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 726                                 if ( rc != 0 ) {
 727                                         err = "c_put 0";
 728                                         goto fail;
 729                                 }
 730                                 id = lo;
 731                                 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 732                                 if ( rc != 0 ) {
 733                                         err = "c_put lo";
 734                                         goto fail;
 735                                 }
 736                                 id = hi;
 737                                 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 738                                 if ( rc != 0 ) {
 739                                         err = "c_put hi";
 740                                         goto fail;
 741                                 }
 742                         } else {
 743                         /* There's room, just store it */
 744                                 goto put1;
 745                         }
 746                 } else {
 747                         /* It's a range, see if we need to rewrite
 748                          * the boundaries
 749                          */
 750                         hi = id;
 751                         data.data = &lo;
 752                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 753                         if ( rc != 0 ) {
 754                                 err = "c_get lo";
 755                                 goto fail;
 756                         }
 757                         if ( id > lo ) {
 758                                 data.data = &hi;
 759                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 760                                 if ( rc != 0 ) {
 761                                         err = "c_get hi";
 762                                         goto fail;
 763                                 }
 764                         }
 765                         if ( id < lo || id > hi ) {
 766                                 /* Delete the current lo/hi */
 767                                 rc = cursor->c_del( cursor, 0 );
 768                                 if ( rc != 0 ) {
 769                                         err = "c_del";
 770                                         goto fail;
 771                                 }
 772                                 data.data = &id;
 773                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 774                                 if ( rc != 0 ) {
 775                                         err = "c_put lo/hi";
 776                                         goto fail;
 777                                 }
 778                         }
 779                 }
 780         } else if ( rc == DB_NOTFOUND ) {
 781 put1:           data.data = &id;
 782                 rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA );
 783                 /* Don't worry if it's already there */
 784                 if ( rc != 0 && rc != DB_KEYEXIST ) {
 785                         err = "c_put id";
 786                         goto fail;
 787                 }
 788         } else {
 789                 /* initial c_get failed, nothing was done */
 790 fail:
 791 #ifdef NEW_LOGGING
 792                 LDAP_LOG( INDEX, ERR,
 793                         "bdb_idl_insert_key: %s failed: %s (%d)\n",
 794                         err, db_strerror(rc), rc );
 795 #else
 796                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 797                         "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 798 #endif
 799                 cursor->c_close( cursor );
 800                 return rc;
 801         }
 802         rc = cursor->c_close( cursor );
 803         if( rc != 0 ) {
 804 #ifdef NEW_LOGGING
 805                 LDAP_LOG( INDEX, ERR,
 806                         "bdb_idl_insert_key: c_close failed: %s (%d)\n",
 807                         db_strerror(rc), rc, 0 );
 808 #else
 809                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 810                         "c_close failed: %s (%d)\n",
 811                         db_strerror(rc), rc, 0 );
 812 #endif
 813         }
 814         return rc;
 815 }
 816
 817 int
 818 bdb_idl_delete_key(
 819         BackendDB       *be,
 820         DB                      *db,
 821         DB_TXN          *tid,
 822         DBT                     *key,
 823         ID                      id )
 824 {
 825         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 826         int     rc;
 827         DBT data;
 828         DBC *cursor;
 829         ID lo, hi, tmp;
 830         char *err;
 831
 832         {
 833                 char buf[16];
 834 #ifdef NEW_LOGGING
 835                 LDAP_LOG( INDEX, ARGS,
 836                         "bdb_idl_delete_key: %lx %s\n",
 837                         (long) id, bdb_show_key( key, buf ), 0 );
 838 #else
 839                 Debug( LDAP_DEBUG_ARGS,
 840                         "bdb_idl_delete_key: %lx %s\n",
 841                         (long) id, bdb_show_key( key, buf ), 0 );
 842 #endif
 843         }
 844         assert( id != NOID );
 845
 846         if ( bdb->bi_idl_cache_max_size ) {
 847                 bdb_idl_cache_del( bdb, db, key );
 848         }
 849
 850         DBTzero( &data );
 851         data.data = &tmp;
 852         data.size = sizeof( id );
 853         data.ulen = data.size;
 854         data.flags = DB_DBT_USERMEM;
 855
 856         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 857         if ( rc != 0 ) {
 858 #ifdef NEW_LOGGING
 859                 LDAP_LOG( INDEX, ERR,
 860                         "bdb_idl_delete_key: cursor failed: %s (%d)\n",
 861                         db_strerror(rc), rc, 0 );
 862 #else
 863                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 864                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 865 #endif
 866                 return rc;
 867         }
 868         /* Fetch the first data item for this key, to see if it
 869          * exists and if it's a range.
 870          */
 871         rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 872         err = "c_get";
 873         if ( rc == 0 ) {
 874                 if ( tmp != 0 ) {
 875                         /* Not a range, just delete it */
 876                         if (tmp != id) {
 877                                 /* position to correct item */
 878                                 tmp = id;
 879                                 rc = cursor->c_get( cursor, key, &data,
 880                                         DB_GET_BOTH | DB_RMW  );
 881                                 if ( rc != 0 ) {
 882                                         err = "c_get id";
 883                                         goto fail;
 884                                 }
 885                         }
 886                         rc = cursor->c_del( cursor, 0 );
 887                         if ( rc != 0 ) {
 888                                 err = "c_del id";
 889                                 goto fail;
 890                         }
 891                 } else {
 892                         /* It's a range, see if we need to rewrite
 893                          * the boundaries
 894                          */
 895                         data.data = &lo;
 896                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 897                         if ( rc != 0 ) {
 898                                 err = "c_get lo";
 899                                 goto fail;
 900                         }
 901                         data.data = &hi;
 902                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 903                         if ( rc != 0 ) {
 904                                 err = "c_get hi";
 905                                 goto fail;
 906                         }
 907                         if ( id == lo || id == hi ) {
 908                                 if ( id == lo ) {
 909                                         id++;
 910                                         lo = id;
 911                                 } else if ( id == hi ) {
 912                                         id--;
 913                                         hi = id;
 914                                 }
 915                                 if ( lo >= hi ) {
 916                                 /* The range has collapsed... */
 917                                         rc = db->del( db, tid, key, 0 );
 918                                         if ( rc != 0 ) {
 919                                                 err = "del";
 920                                                 goto fail;
 921                                         }
 922                                 } else {
 923                                         if ( id == lo ) {
 924                                                 /* reposition on lo slot */
 925                                                 data.data = &lo;
 926                                                 cursor->c_get( cursor, key, &data, DB_PREV );
 927                                                 lo = id;
 928                                         }
 929                                         rc = cursor->c_del( cursor, 0 );
 930                                         if ( rc != 0 ) {
 931                                                 err = "c_del";
 932                                                 goto fail;
 933                                         }
 934                                 }
 935                                 if ( lo <= hi ) {
 936                                         data.data = &id;
 937                                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 938                                         if ( rc != 0 ) {
 939                                                 err = "c_put lo/hi";
 940                                                 goto fail;
 941                                         }
 942                                 }
 943                         }
 944                 }
 945         } else {
 946                 /* initial c_get failed, nothing was done */
 947 fail:
 948                 if ( rc != DB_NOTFOUND ) {
 949 #ifdef NEW_LOGGING
 950                 LDAP_LOG( INDEX, ERR,
 951                         "bdb_idl_delete_key: %s failed: %s (%d)\n",
 952                         err, db_strerror(rc), rc );
 953 #else
 954                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 955                         "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 956 #endif
 957                 }
 958                 cursor->c_close( cursor );
 959                 return rc;
 960         }
 961         rc = cursor->c_close( cursor );
 962         if( rc != 0 ) {
 963 #ifdef NEW_LOGGING
 964                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: c_close failed: %s (%d)\n",
 965                         db_strerror(rc), rc, 0 );
 966 #else
 967                 Debug( LDAP_DEBUG_ANY,
 968                         "=> bdb_idl_delete_key: c_close failed: %s (%d)\n",
 969                         db_strerror(rc), rc, 0 );
 970 #endif
 971         }
 972
 973         return rc;
 974 }
 975
 976
 977 /*
 978  * idl_intersection - return a = a intersection b
 979  */
 980 int
 981 bdb_idl_intersection(
 982         ID *a,
 983         ID *b )
 984 {
 985         ID ida, idb;
 986         ID idmax, idmin;
 987         ID cursora = 0, cursorb = 0, cursorc;
 988         int swap = 0;
 989
 990         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 991                 a[0] = 0;
 992                 return 0;
 993         }
 994
 995         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 996         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 997         if ( idmin > idmax ) {
 998                 a[0] = 0;
 999                 return 0;
1000         } else if ( idmin == idmax ) {
1001                 a[0] = 1;
1002                 a[1] = idmin;
1003                 return 0;
1004         }
1005
1006         if ( BDB_IDL_IS_RANGE( a ) ) {
1007                 if ( BDB_IDL_IS_RANGE(b) ) {
1008                 /* If both are ranges, just shrink the boundaries */
1009                         a[1] = idmin;
1010                         a[2] = idmax;
1011                         return 0;
1012                 } else {
1013                 /* Else swap so that b is the range, a is a list */
1014                         ID *tmp = a;
1015                         a = b;
1016                         b = tmp;
1017                         swap = 1;
1018                 }
1019         }
1020
1021         /* If a range completely covers the list, the result is
1022          * just the list. If idmin to idmax is contiguous, just
1023          * turn it into a range.
1024          */
1025         if ( BDB_IDL_IS_RANGE( b )
1026                 && BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
1027                 && BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
1028                 if (idmax - idmin + 1 == a[0])
1029                 {
1030                         a[0] = NOID;
1031                         a[1] = idmin;
1032                         a[2] = idmax;
1033                 }
1034                 goto done;
1035         }
1036
1037         /* Fine, do the intersection one element at a time.
1038          * First advance to idmin in both IDLs.
1039          */
1040         cursora = cursorb = idmin;
1041         ida = bdb_idl_first( a, &cursora );
1042         idb = bdb_idl_first( b, &cursorb );
1043         cursorc = 0;
1044
1045         while( ida <= idmax || idb <= idmax ) {
1046                 if( ida == idb ) {
1047                         a[++cursorc] = ida;
1048                         ida = bdb_idl_next( a, &cursora );
1049                         idb = bdb_idl_next( b, &cursorb );
1050                 } else if ( ida < idb ) {
1051                         ida = bdb_idl_next( a, &cursora );
1052                 } else {
1053                         idb = bdb_idl_next( b, &cursorb );
1054                 }
1055         }
1056         a[0] = cursorc;
1057 done:
1058         if (swap)
1059                 BDB_IDL_CPY( b, a );
1060
1061         return 0;
1062 }
1063
1064
1065 /*
1066  * idl_union - return a = a union b
1067  */
1068 int
1069 bdb_idl_union(
1070         ID      *a,
1071         ID      *b )
1072 {
1073         ID ida, idb;
1074         ID cursora = 0, cursorb = 0, cursorc;
1075
1076         if ( BDB_IDL_IS_ZERO( b ) ) {
1077                 return 0;
1078         }
1079
1080         if ( BDB_IDL_IS_ZERO( a ) ) {
1081                 BDB_IDL_CPY( a, b );
1082                 return 0;
1083         }
1084
1085         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
1086 over:           ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
1087                 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
1088                 a[0] = NOID;
1089                 a[1] = ida;
1090                 a[2] = idb;
1091                 return 0;
1092         }
1093
1094         ida = bdb_idl_first( a, &cursora );
1095         idb = bdb_idl_first( b, &cursorb );
1096
1097         cursorc = b[0];
1098
1099         /* The distinct elements of a are cat'd to b */
1100         while( ida != NOID || idb != NOID ) {
1101                 if ( ida < idb ) {
1102                         if( ++cursorc > BDB_IDL_UM_MAX ) {
1103                                 goto over;
1104                         }
1105                         b[cursorc] = ida;
1106                         ida = bdb_idl_next( a, &cursora );
1107
1108                 } else {
1109                         if ( ida == idb )
1110                                 ida = bdb_idl_next( a, &cursora );
1111                         idb = bdb_idl_next( b, &cursorb );
1112                 }
1113         }
1114
1115         /* b is copied back to a in sorted order */
1116         a[0] = cursorc;
1117         cursora = 1;
1118         cursorb = 1;
1119         cursorc = b[0]+1;
1120         while (cursorb <= b[0] || cursorc <= a[0]) {
1121                 if (cursorc > a[0])
1122                         idb = NOID;
1123                 else
1124                         idb = b[cursorc];
1125                 if (cursorb <= b[0] && b[cursorb] < idb)
1126                         a[cursora++] = b[cursorb++];
1127                 else {
1128                         a[cursora++] = idb;
1129                         cursorc++;
1130                 }
1131         }
1132
1133         return 0;
1134 }
1135
1136
1137 #if 0
1138 /*
1139  * bdb_idl_notin - return a intersection ~b (or a minus b)
1140  */
1141 int
1142 bdb_idl_notin(
1143         ID      *a,
1144         ID      *b,
1145         ID *ids )
1146 {
1147         ID ida, idb;
1148         ID cursora = 0, cursorb = 0;
1149
1150         if( BDB_IDL_IS_ZERO( a ) ||
1151                 BDB_IDL_IS_ZERO( b ) ||
1152                 BDB_IDL_IS_RANGE( b ) )
1153         {
1154                 BDB_IDL_CPY( ids, a );
1155                 return 0;
1156         }
1157
1158         if( BDB_IDL_IS_RANGE( a ) ) {
1159                 BDB_IDL_CPY( ids, a );
1160                 return 0;
1161         }
1162
1163         ida = bdb_idl_first( a, &cursora ),
1164         idb = bdb_idl_first( b, &cursorb );
1165
1166         ids[0] = 0;
1167
1168         while( ida != NOID ) {
1169                 if ( idb == NOID ) {
1170                         /* we could shortcut this */
1171                         ids[++ids[0]] = ida;
1172                         ida = bdb_idl_next( a, &cursora );
1173
1174                 } else if ( ida < idb ) {
1175                         ids[++ids[0]] = ida;
1176                         ida = bdb_idl_next( a, &cursora );
1177
1178                 } else if ( ida > idb ) {
1179                         idb = bdb_idl_next( b, &cursorb );
1180
1181                 } else {
1182                         ida = bdb_idl_next( a, &cursora );
1183                         idb = bdb_idl_next( b, &cursorb );
1184                 }
1185         }
1186
1187         return 0;
1188 }
1189 #endif
1190
1191 ID bdb_idl_first( ID *ids, ID *cursor )
1192 {
1193         ID pos;
1194
1195         if ( ids[0] == 0 ) {
1196                 *cursor = NOID;
1197                 return NOID;
1198         }
1199
1200         if ( BDB_IDL_IS_RANGE( ids ) ) {
1201                 if( *cursor < ids[1] ) {
1202                         *cursor = ids[1];
1203                 }
1204                 return *cursor;
1205         }
1206
1207         if ( *cursor == 0 )
1208                 pos = 1;
1209         else
1210                 pos = bdb_idl_search( ids, *cursor );
1211
1212         if( pos > ids[0] ) {
1213                 return NOID;
1214         }
1215
1216         *cursor = pos;
1217         return ids[pos];
1218 }
1219
1220 ID bdb_idl_next( ID *ids, ID *cursor )
1221 {
1222         if ( BDB_IDL_IS_RANGE( ids ) ) {
1223                 if( ids[2] < ++(*cursor) ) {
1224                         return NOID;
1225                 }
1226                 return *cursor;
1227         }
1228
1229         if ( ++(*cursor) <= ids[0] ) {
1230                 return ids[*cursor];
1231         }
1232
1233         return NOID;
1234 }
1235
1236 /* Add one ID to an unsorted list. We still maintain a lo/hi reference
1237  * for fast range compaction.
1238  */
1239 int bdb_idl_append_one( ID *ids, ID id )
1240 {
1241         unsigned x;
1242
1243         if (BDB_IDL_IS_RANGE( ids )) {
1244                 /* if already in range, treat as a dup */
1245                 if (id >= BDB_IDL_FIRST(ids) && id <= BDB_IDL_LAST(ids))
1246                         return -1;
1247                 if (id < BDB_IDL_FIRST(ids))
1248                         ids[1] = id;
1249                 else if (id > BDB_IDL_LAST(ids))
1250                         ids[2] = id;
1251                 return 0;
1252         }
1253         if ( ids[0] ) {
1254                 ID tmp;
1255
1256                 if (id < ids[1]) {
1257                         tmp = ids[1];
1258                         ids[1] = id;
1259                         id = tmp;
1260                 } else if ( ids[0] > 1 && id > ids[2] ) {
1261                         tmp = ids[2];
1262                         ids[2] = id;
1263                         id = tmp;
1264                 }
1265         }
1266         ids[0]++;
1267         if ( ids[0] >= BDB_IDL_UM_MAX ) {
1268                 ids[0] = NOID;
1269         } else {
1270                 ids[ids[0]] = id;
1271         }
1272         return 0;
1273 }
1274
1275 /* Append unsorted list b to unsorted list a. Both lists must have their
1276  * lowest value in slot 1 and highest value in slot 2.
1277  */
1278 int bdb_idl_append( ID *a, ID *b )
1279 {
1280         ID ida, idb;
1281
1282         if ( BDB_IDL_IS_ZERO( b ) ) {
1283                 return 0;
1284         }
1285
1286         if ( BDB_IDL_IS_ZERO( a ) ) {
1287                 BDB_IDL_CPY( a, b );
1288                 return 0;
1289         }
1290
1291         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ||
1292                 a[0] + b[0] >= BDB_IDL_UM_MAX ) {
1293                 ida = IDL_MIN( a[1], b[1] );
1294                 idb = IDL_MAX( a[2], b[2] );
1295                 a[0] = NOID;
1296                 a[1] = ida;
1297                 a[2] = idb;
1298                 return 0;
1299         }
1300
1301         if ( b[1] < a[1] ) {
1302                 ida = a[1];
1303                 a[1] = b[1];
1304         } else {
1305                 ida = b[1];
1306         }
1307         a[0]++;
1308         a[a[0]] = ida;
1309
1310         if ( b[0] > 1 && b[2] > a[2] ) {
1311                 ida = a[2];
1312                 a[2] = b[2];
1313         } else {
1314                 ida = b[2];
1315         }
1316         a[0]++;
1317         a[a[0]] = ida;
1318
1319         if ( b[0] > 2 ) {
1320                 int i = b[0] - 2;
1321                 AC_MEMCPY(a+a[0]+1, b+3, i * sizeof(ID));
1322                 a[0] += i;
1323         }
1324         return 0;
1325
1326 }
1327
1328 /* Sort an IDL using HeapSort */
1329 static void
1330 siftDown(ID *ids, int root, int bottom)
1331 {
1332         int child;
1333         ID temp;
1334
1335         temp = ids[root];
1336         while ((child=root*2) <= bottom) {
1337                 if (child < bottom && ids[child] < ids[child + 1])
1338                         child++;
1339
1340                 if (temp >= ids[child])
1341                         break;
1342                 ids[root] = ids[child];
1343                 root = child;
1344         }
1345         ids[root] = temp;
1346 }
1347
1348 void
1349 bdb_idl_sort( ID *ids )
1350 {
1351         int i;
1352         ID temp;
1353
1354         if ( BDB_IDL_IS_RANGE( ids ))
1355                 return;
1356
1357         for (i = ids[0] / 2; i >= 1; i--)
1358                 siftDown(ids, i, ids[0]);
1359
1360         for (i = ids[0]; i > 1; i--)
1361         {
1362                 temp = ids[i];
1363                 ids[i] = ids[1];
1364                 ids[1] = temp;
1365                 siftDown(ids, 1, i-1);
1366         }
1367 }