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