Back to index

openldap  2.4.31
idl.c
Go to the documentation of this file.
00001 /* idl.c - ldap id list handling routines */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2000-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 
00017 #include "portable.h"
00018 
00019 #include <stdio.h>
00020 #include <ac/string.h>
00021 
00022 #include "back-bdb.h"
00023 #include "idl.h"
00024 
00025 #define IDL_MAX(x,y) ( (x) > (y) ? (x) : (y) )
00026 #define IDL_MIN(x,y) ( (x) < (y) ? (x) : (y) )
00027 #define IDL_CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) )
00028 
00029 #define IDL_LRU_DELETE( bdb, e ) do { \
00030        if ( (e) == (bdb)->bi_idl_lru_head ) { \
00031               if ( (e)->idl_lru_next == (bdb)->bi_idl_lru_head ) { \
00032                      (bdb)->bi_idl_lru_head = NULL; \
00033               } else { \
00034                      (bdb)->bi_idl_lru_head = (e)->idl_lru_next; \
00035               } \
00036        } \
00037        if ( (e) == (bdb)->bi_idl_lru_tail ) { \
00038               if ( (e)->idl_lru_prev == (bdb)->bi_idl_lru_tail ) { \
00039                      assert( (bdb)->bi_idl_lru_head == NULL ); \
00040                      (bdb)->bi_idl_lru_tail = NULL; \
00041               } else { \
00042                      (bdb)->bi_idl_lru_tail = (e)->idl_lru_prev; \
00043               } \
00044        } \
00045        (e)->idl_lru_next->idl_lru_prev = (e)->idl_lru_prev; \
00046        (e)->idl_lru_prev->idl_lru_next = (e)->idl_lru_next; \
00047 } while ( 0 )
00048 
00049 static int
00050 bdb_idl_entry_cmp( const void *v_idl1, const void *v_idl2 )
00051 {
00052        const bdb_idl_cache_entry_t *idl1 = v_idl1, *idl2 = v_idl2;
00053        int rc;
00054 
00055        if ((rc = SLAP_PTRCMP( idl1->db, idl2->db ))) return rc;
00056        if ((rc = idl1->kstr.bv_len - idl2->kstr.bv_len )) return rc;
00057        return ( memcmp ( idl1->kstr.bv_val, idl2->kstr.bv_val , idl1->kstr.bv_len ) );
00058 }
00059 
00060 #if IDL_DEBUG > 0
00061 static void idl_check( ID *ids )
00062 {
00063        if( BDB_IDL_IS_RANGE( ids ) ) {
00064               assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
00065        } else {
00066               ID i;
00067               for( i=1; i < ids[0]; i++ ) {
00068                      assert( ids[i+1] > ids[i] );
00069               }
00070        }
00071 }
00072 
00073 #if IDL_DEBUG > 1
00074 static void idl_dump( ID *ids )
00075 {
00076        if( BDB_IDL_IS_RANGE( ids ) ) {
00077               Debug( LDAP_DEBUG_ANY,
00078                      "IDL: range ( %ld - %ld )\n",
00079                      (long) BDB_IDL_RANGE_FIRST( ids ),
00080                      (long) BDB_IDL_RANGE_LAST( ids ) );
00081 
00082        } else {
00083               ID i;
00084               Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
00085 
00086               for( i=1; i<=ids[0]; i++ ) {
00087                      if( i % 16 == 1 ) {
00088                             Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
00089                      }
00090                      Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
00091               }
00092 
00093               Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
00094        }
00095 
00096        idl_check( ids );
00097 }
00098 #endif /* IDL_DEBUG > 1 */
00099 #endif /* IDL_DEBUG > 0 */
00100 
00101 unsigned bdb_idl_search( ID *ids, ID id )
00102 {
00103 #define IDL_BINARY_SEARCH 1
00104 #ifdef IDL_BINARY_SEARCH
00105        /*
00106         * binary search of id in ids
00107         * if found, returns position of id
00108         * if not found, returns first postion greater than id
00109         */
00110        unsigned base = 0;
00111        unsigned cursor = 1;
00112        int val = 0;
00113        unsigned n = ids[0];
00114 
00115 #if IDL_DEBUG > 0
00116        idl_check( ids );
00117 #endif
00118 
00119        while( 0 < n ) {
00120               unsigned pivot = n >> 1;
00121               cursor = base + pivot + 1;
00122               val = IDL_CMP( id, ids[cursor] );
00123 
00124               if( val < 0 ) {
00125                      n = pivot;
00126 
00127               } else if ( val > 0 ) {
00128                      base = cursor;
00129                      n -= pivot + 1;
00130 
00131               } else {
00132                      return cursor;
00133               }
00134        }
00135        
00136        if( val > 0 ) {
00137               ++cursor;
00138        }
00139        return cursor;
00140 
00141 #else
00142        /* (reverse) linear search */
00143        int i;
00144 
00145 #if IDL_DEBUG > 0
00146        idl_check( ids );
00147 #endif
00148 
00149        for( i=ids[0]; i; i-- ) {
00150               if( id > ids[i] ) {
00151                      break;
00152               }
00153        }
00154 
00155        return i+1;
00156 #endif
00157 }
00158 
00159 int bdb_idl_insert( ID *ids, ID id )
00160 {
00161        unsigned x;
00162 
00163 #if IDL_DEBUG > 1
00164        Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
00165        idl_dump( ids );
00166 #elif IDL_DEBUG > 0
00167        idl_check( ids );
00168 #endif
00169 
00170        if (BDB_IDL_IS_RANGE( ids )) {
00171               /* if already in range, treat as a dup */
00172               if (id >= BDB_IDL_RANGE_FIRST(ids) && id <= BDB_IDL_RANGE_LAST(ids))
00173                      return -1;
00174               if (id < BDB_IDL_RANGE_FIRST(ids))
00175                      ids[1] = id;
00176               else if (id > BDB_IDL_RANGE_LAST(ids))
00177                      ids[2] = id;
00178               return 0;
00179        }
00180 
00181        x = bdb_idl_search( ids, id );
00182        assert( x > 0 );
00183 
00184        if( x < 1 ) {
00185               /* internal error */
00186               return -2;
00187        }
00188 
00189        if ( x <= ids[0] && ids[x] == id ) {
00190               /* duplicate */
00191               return -1;
00192        }
00193 
00194        if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
00195               if( id < ids[1] ) {
00196                      ids[1] = id;
00197                      ids[2] = ids[ids[0]-1];
00198               } else if ( ids[ids[0]-1] < id ) {
00199                      ids[2] = id;
00200               } else {
00201                      ids[2] = ids[ids[0]-1];
00202               }
00203               ids[0] = NOID;
00204        
00205        } else {
00206               /* insert id */
00207               AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
00208               ids[x] = id;
00209        }
00210 
00211 #if IDL_DEBUG > 1
00212        idl_dump( ids );
00213 #elif IDL_DEBUG > 0
00214        idl_check( ids );
00215 #endif
00216 
00217        return 0;
00218 }
00219 
00220 int bdb_idl_delete( ID *ids, ID id )
00221 {
00222        unsigned x;
00223 
00224 #if IDL_DEBUG > 1
00225        Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
00226        idl_dump( ids );
00227 #elif IDL_DEBUG > 0
00228        idl_check( ids );
00229 #endif
00230 
00231        if (BDB_IDL_IS_RANGE( ids )) {
00232               /* If deleting a range boundary, adjust */
00233               if ( ids[1] == id )
00234                      ids[1]++;
00235               else if ( ids[2] == id )
00236                      ids[2]--;
00237               /* deleting from inside a range is a no-op */
00238 
00239               /* If the range has collapsed, re-adjust */
00240               if ( ids[1] > ids[2] )
00241                      ids[0] = 0;
00242               else if ( ids[1] == ids[2] )
00243                      ids[1] = 1;
00244               return 0;
00245        }
00246 
00247        x = bdb_idl_search( ids, id );
00248        assert( x > 0 );
00249 
00250        if( x <= 0 ) {
00251               /* internal error */
00252               return -2;
00253        }
00254 
00255        if( x > ids[0] || ids[x] != id ) {
00256               /* not found */
00257               return -1;
00258 
00259        } else if ( --ids[0] == 0 ) {
00260               if( x != 1 ) {
00261                      return -3;
00262               }
00263 
00264        } else {
00265               AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
00266        }
00267 
00268 #if IDL_DEBUG > 1
00269        idl_dump( ids );
00270 #elif IDL_DEBUG > 0
00271        idl_check( ids );
00272 #endif
00273 
00274        return 0;
00275 }
00276 
00277 static char *
00278 bdb_show_key(
00279        DBT           *key,
00280        char          *buf )
00281 {
00282        if ( key->size == 4 /* LUTIL_HASH_BYTES */ ) {
00283               unsigned char *c = key->data;
00284               sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
00285               return buf;
00286        } else {
00287               return key->data;
00288        }
00289 }
00290 
00291 /* Find a db/key pair in the IDL cache. If ids is non-NULL,
00292  * copy the cached IDL into it, otherwise just return the status.
00293  */
00294 int
00295 bdb_idl_cache_get(
00296        struct bdb_info      *bdb,
00297        DB                   *db,
00298        DBT                  *key,
00299        ID                   *ids )
00300 {
00301        bdb_idl_cache_entry_t idl_tmp;
00302        bdb_idl_cache_entry_t *matched_idl_entry;
00303        int rc = LDAP_NO_SUCH_OBJECT;
00304 
00305        DBT2bv( key, &idl_tmp.kstr );
00306        idl_tmp.db = db;
00307        ldap_pvt_thread_rdwr_rlock( &bdb->bi_idl_tree_rwlock );
00308        matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
00309                                   bdb_idl_entry_cmp );
00310        if ( matched_idl_entry != NULL ) {
00311               if ( matched_idl_entry->idl && ids )
00312                      BDB_IDL_CPY( ids, matched_idl_entry->idl );
00313               matched_idl_entry->idl_flags |= CACHE_ENTRY_REFERENCED;
00314               if ( matched_idl_entry->idl )
00315                      rc = LDAP_SUCCESS;
00316               else
00317                      rc = DB_NOTFOUND;
00318        }
00319        ldap_pvt_thread_rdwr_runlock( &bdb->bi_idl_tree_rwlock );
00320 
00321        return rc;
00322 }
00323 
00324 void
00325 bdb_idl_cache_put(
00326        struct bdb_info      *bdb,
00327        DB                   *db,
00328        DBT                  *key,
00329        ID                   *ids,
00330        int                  rc )
00331 {
00332        bdb_idl_cache_entry_t idl_tmp;
00333        bdb_idl_cache_entry_t *ee, *eprev;
00334 
00335        if ( rc == DB_NOTFOUND || BDB_IDL_IS_ZERO( ids ))
00336               return;
00337 
00338        DBT2bv( key, &idl_tmp.kstr );
00339 
00340        ee = (bdb_idl_cache_entry_t *) ch_malloc(
00341               sizeof( bdb_idl_cache_entry_t ) );
00342        ee->db = db;
00343        ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) );
00344        BDB_IDL_CPY( ee->idl, ids );
00345 
00346        ee->idl_lru_prev = NULL;
00347        ee->idl_lru_next = NULL;
00348        ee->idl_flags = 0;
00349        ber_dupbv( &ee->kstr, &idl_tmp.kstr );
00350        ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
00351        if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee,
00352               bdb_idl_entry_cmp, avl_dup_error ))
00353        {
00354               ch_free( ee->kstr.bv_val );
00355               ch_free( ee->idl );
00356               ch_free( ee );
00357               ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
00358               return;
00359        }
00360        ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
00361        /* LRU_ADD */
00362        if ( bdb->bi_idl_lru_head ) {
00363               assert( bdb->bi_idl_lru_tail != NULL );
00364               assert( bdb->bi_idl_lru_head->idl_lru_prev != NULL );
00365               assert( bdb->bi_idl_lru_head->idl_lru_next != NULL );
00366 
00367               ee->idl_lru_next = bdb->bi_idl_lru_head;
00368               ee->idl_lru_prev = bdb->bi_idl_lru_head->idl_lru_prev;
00369               bdb->bi_idl_lru_head->idl_lru_prev->idl_lru_next = ee;
00370               bdb->bi_idl_lru_head->idl_lru_prev = ee;
00371        } else {
00372               ee->idl_lru_next = ee->idl_lru_prev = ee;
00373               bdb->bi_idl_lru_tail = ee;
00374        }
00375        bdb->bi_idl_lru_head = ee;
00376 
00377        if ( bdb->bi_idl_cache_size >= bdb->bi_idl_cache_max_size ) {
00378               int i;
00379               eprev = bdb->bi_idl_lru_tail;
00380               for ( i = 0; (ee = eprev) != NULL && i < 10; i++ ) {
00381                      eprev = ee->idl_lru_prev;
00382                      if ( eprev == ee ) {
00383                             eprev = NULL;
00384                      }
00385                      if ( ee->idl_flags & CACHE_ENTRY_REFERENCED ) {
00386                             ee->idl_flags ^= CACHE_ENTRY_REFERENCED;
00387                             continue;
00388                      }
00389                      if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee,
00390                                 bdb_idl_entry_cmp ) == NULL ) {
00391                             Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: "
00392                                    "AVL delete failed\n",
00393                                    0, 0, 0 );
00394                      }
00395                      IDL_LRU_DELETE( bdb, ee );
00396                      i++;
00397                      --bdb->bi_idl_cache_size;
00398                      ch_free( ee->kstr.bv_val );
00399                      ch_free( ee->idl );
00400                      ch_free( ee );
00401               }
00402               bdb->bi_idl_lru_tail = eprev;
00403               assert( bdb->bi_idl_lru_tail != NULL
00404                      || bdb->bi_idl_lru_head == NULL );
00405        }
00406        bdb->bi_idl_cache_size++;
00407        ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
00408        ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
00409 }
00410 
00411 void
00412 bdb_idl_cache_del(
00413        struct bdb_info      *bdb,
00414        DB                   *db,
00415        DBT                  *key )
00416 {
00417        bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp;
00418        DBT2bv( key, &idl_tmp.kstr );
00419        idl_tmp.db = db;
00420        ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
00421        matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
00422                                   bdb_idl_entry_cmp );
00423        if ( matched_idl_entry != NULL ) {
00424               if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry,
00425                                 bdb_idl_entry_cmp ) == NULL ) {
00426                      Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
00427                             "AVL delete failed\n",
00428                             0, 0, 0 );
00429               }
00430               --bdb->bi_idl_cache_size;
00431               ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
00432               IDL_LRU_DELETE( bdb, matched_idl_entry );
00433               ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
00434               free( matched_idl_entry->kstr.bv_val );
00435               if ( matched_idl_entry->idl )
00436                      free( matched_idl_entry->idl );
00437               free( matched_idl_entry );
00438        }
00439        ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
00440 }
00441 
00442 void
00443 bdb_idl_cache_add_id(
00444        struct bdb_info      *bdb,
00445        DB                   *db,
00446        DBT                  *key,
00447        ID                   id )
00448 {
00449        bdb_idl_cache_entry_t *cache_entry, idl_tmp;
00450        DBT2bv( key, &idl_tmp.kstr );
00451        idl_tmp.db = db;
00452        ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
00453        cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
00454                                   bdb_idl_entry_cmp );
00455        if ( cache_entry != NULL ) {
00456               if ( !BDB_IDL_IS_RANGE( cache_entry->idl ) &&
00457                      cache_entry->idl[0] < BDB_IDL_DB_MAX ) {
00458                      size_t s = BDB_IDL_SIZEOF( cache_entry->idl ) + sizeof(ID);
00459                      cache_entry->idl = ch_realloc( cache_entry->idl, s );
00460               }
00461               bdb_idl_insert( cache_entry->idl, id );
00462        }
00463        ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
00464 }
00465 
00466 void
00467 bdb_idl_cache_del_id(
00468        struct bdb_info      *bdb,
00469        DB                   *db,
00470        DBT                  *key,
00471        ID                   id )
00472 {
00473        bdb_idl_cache_entry_t *cache_entry, idl_tmp;
00474        DBT2bv( key, &idl_tmp.kstr );
00475        idl_tmp.db = db;
00476        ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
00477        cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
00478                                   bdb_idl_entry_cmp );
00479        if ( cache_entry != NULL ) {
00480               bdb_idl_delete( cache_entry->idl, id );
00481               if ( cache_entry->idl[0] == 0 ) {
00482                      if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) cache_entry,
00483                                           bdb_idl_entry_cmp ) == NULL ) {
00484                             Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
00485                                    "AVL delete failed\n",
00486                                    0, 0, 0 );
00487                      }
00488                      --bdb->bi_idl_cache_size;
00489                      ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
00490                      IDL_LRU_DELETE( bdb, cache_entry );
00491                      ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
00492                      free( cache_entry->kstr.bv_val );
00493                      free( cache_entry->idl );
00494                      free( cache_entry );
00495               }
00496        }
00497        ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
00498 }
00499 
00500 int
00501 bdb_idl_fetch_key(
00502        BackendDB     *be,
00503        DB                   *db,
00504        DB_TXN        *txn,
00505        DBT                  *key,
00506        ID                   *ids,
00507        DBC                     **saved_cursor,
00508        int                     get_flag )
00509 {
00510        struct bdb_info *bdb = (struct bdb_info *) be->be_private;
00511        int rc;
00512        DBT data, key2, *kptr;
00513        DBC *cursor;
00514        ID *i;
00515        void *ptr;
00516        size_t len;
00517        int rc2;
00518        int flags = bdb->bi_db_opflags | DB_MULTIPLE;
00519        int opflag;
00520 
00521        /* If using BerkeleyDB 4.0, the buf must be large enough to
00522         * grab the entire IDL in one get(), otherwise BDB will leak
00523         * resources on subsequent get's.  We can safely call get()
00524         * twice - once for the data, and once to get the DB_NOTFOUND
00525         * result meaning there's no more data. See ITS#2040 for details.
00526         * This bug is fixed in BDB 4.1 so a smaller buffer will work if
00527         * stack space is too limited.
00528         *
00529         * configure now requires Berkeley DB 4.1.
00530         */
00531 #if DB_VERSION_FULL < 0x04010000
00532 #      define BDB_ENOUGH 5
00533 #else
00534        /* We sometimes test with tiny IDLs, and BDB always wants buffers
00535         * that are at least one page in size.
00536         */
00537 # if BDB_IDL_DB_SIZE < 4096
00538 #   define BDB_ENOUGH 2048
00539 # else
00540 #      define BDB_ENOUGH 1
00541 # endif
00542 #endif
00543        ID buf[BDB_IDL_DB_SIZE*BDB_ENOUGH];
00544 
00545        char keybuf[16];
00546 
00547        Debug( LDAP_DEBUG_ARGS,
00548               "bdb_idl_fetch_key: %s\n", 
00549               bdb_show_key( key, keybuf ), 0, 0 );
00550 
00551        assert( ids != NULL );
00552 
00553        if ( saved_cursor && *saved_cursor ) {
00554               opflag = DB_NEXT;
00555        } else if ( get_flag == LDAP_FILTER_GE ) {
00556               opflag = DB_SET_RANGE;
00557        } else if ( get_flag == LDAP_FILTER_LE ) {
00558               opflag = DB_FIRST;
00559        } else {
00560               opflag = DB_SET;
00561        }
00562 
00563        /* only non-range lookups can use the IDL cache */
00564        if ( bdb->bi_idl_cache_size && opflag == DB_SET ) {
00565               rc = bdb_idl_cache_get( bdb, db, key, ids );
00566               if ( rc != LDAP_NO_SUCH_OBJECT ) return rc;
00567        }
00568 
00569        DBTzero( &data );
00570 
00571        data.data = buf;
00572        data.ulen = sizeof(buf);
00573        data.flags = DB_DBT_USERMEM;
00574 
00575        /* If we're not reusing an existing cursor, get a new one */
00576        if( opflag != DB_NEXT ) {
00577               rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
00578               if( rc != 0 ) {
00579                      Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
00580                             "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
00581                      return rc;
00582               }
00583        } else {
00584               cursor = *saved_cursor;
00585        }
00586        
00587        /* If this is a LE lookup, save original key so we can determine
00588         * when to stop. If this is a GE lookup, save the key since it
00589         * will be overwritten.
00590         */
00591        if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
00592               DBTzero( &key2 );
00593               key2.flags = DB_DBT_USERMEM;
00594               key2.ulen = sizeof(keybuf);
00595               key2.data = keybuf;
00596               key2.size = key->size;
00597               AC_MEMCPY( keybuf, key->data, key->size );
00598               kptr = &key2;
00599        } else {
00600               kptr = key;
00601        }
00602        len = key->size;
00603        rc = cursor->c_get( cursor, kptr, &data, flags | opflag );
00604 
00605        /* skip presence key on range inequality lookups */
00606        while (rc == 0 && kptr->size != len) {
00607               rc = cursor->c_get( cursor, kptr, &data, flags | DB_NEXT_NODUP );
00608        }
00609        /* If we're doing a LE compare and the new key is greater than
00610         * our search key, we're done
00611         */
00612        if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->data,
00613               key->data, key->size ) > 0 ) {
00614               rc = DB_NOTFOUND;
00615        }
00616        if (rc == 0) {
00617               i = ids;
00618               while (rc == 0) {
00619                      u_int8_t *j;
00620 
00621                      DB_MULTIPLE_INIT( ptr, &data );
00622                      while (ptr) {
00623                             DB_MULTIPLE_NEXT(ptr, &data, j, len);
00624                             if (j) {
00625                                    ++i;
00626                                    BDB_DISK2ID( j, i );
00627                             }
00628                      }
00629                      rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
00630               }
00631               if ( rc == DB_NOTFOUND ) rc = 0;
00632               ids[0] = i - ids;
00633               /* On disk, a range is denoted by 0 in the first element */
00634               if (ids[1] == 0) {
00635                      if (ids[0] != BDB_IDL_RANGE_SIZE) {
00636                             Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
00637                                    "range size mismatch: expected %d, got %ld\n",
00638                                    BDB_IDL_RANGE_SIZE, ids[0], 0 );
00639                             cursor->c_close( cursor );
00640                             return -1;
00641                      }
00642                      BDB_IDL_RANGE( ids, ids[2], ids[3] );
00643               }
00644               data.size = BDB_IDL_SIZEOF(ids);
00645        }
00646 
00647        if ( saved_cursor && rc == 0 ) {
00648               if ( !*saved_cursor )
00649                      *saved_cursor = cursor;
00650               rc2 = 0;
00651        }
00652        else
00653               rc2 = cursor->c_close( cursor );
00654        if (rc2) {
00655               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
00656                      "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
00657               return rc2;
00658        }
00659 
00660        if( rc == DB_NOTFOUND ) {
00661               return rc;
00662 
00663        } else if( rc != 0 ) {
00664               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
00665                      "get failed: %s (%d)\n",
00666                      db_strerror(rc), rc, 0 );
00667               return rc;
00668 
00669        } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
00670               /* size not multiple of ID size */
00671               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
00672                      "odd size: expected %ld multiple, got %ld\n",
00673                      (long) sizeof( ID ), (long) data.size, 0 );
00674               return -1;
00675 
00676        } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
00677               /* size mismatch */
00678               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
00679                      "get size mismatch: expected %ld, got %ld\n",
00680                      (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
00681               return -1;
00682        }
00683 
00684        if ( bdb->bi_idl_cache_max_size ) {
00685               bdb_idl_cache_put( bdb, db, key, ids, rc );
00686        }
00687 
00688        return rc;
00689 }
00690 
00691 
00692 int
00693 bdb_idl_insert_key(
00694        BackendDB     *be,
00695        DB                   *db,
00696        DB_TXN        *tid,
00697        DBT                  *key,
00698        ID                   id )
00699 {
00700        struct bdb_info *bdb = (struct bdb_info *) be->be_private;
00701        int    rc;
00702        DBT data;
00703        DBC *cursor;
00704        ID lo, hi, nlo, nhi, nid;
00705        char *err;
00706 
00707        {
00708               char buf[16];
00709               Debug( LDAP_DEBUG_ARGS,
00710                      "bdb_idl_insert_key: %lx %s\n", 
00711                      (long) id, bdb_show_key( key, buf ), 0 );
00712        }
00713 
00714        assert( id != NOID );
00715 
00716        DBTzero( &data );
00717        data.size = sizeof( ID );
00718        data.ulen = data.size;
00719        data.flags = DB_DBT_USERMEM;
00720 
00721        BDB_ID2DISK( id, &nid );
00722 
00723        rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
00724        if ( rc != 0 ) {
00725               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
00726                      "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
00727               return rc;
00728        }
00729        data.data = &nlo;
00730        /* Fetch the first data item for this key, to see if it
00731         * exists and if it's a range.
00732         */
00733        rc = cursor->c_get( cursor, key, &data, DB_SET );
00734        err = "c_get";
00735        if ( rc == 0 ) {
00736               if ( nlo != 0 ) {
00737                      /* not a range, count the number of items */
00738                      db_recno_t count;
00739                      rc = cursor->c_count( cursor, &count, 0 );
00740                      if ( rc != 0 ) {
00741                             err = "c_count";
00742                             goto fail;
00743                      }
00744                      if ( count >= BDB_IDL_DB_MAX ) {
00745                      /* No room, convert to a range */
00746                             DBT key2 = *key;
00747                             db_recno_t i;
00748 
00749                             key2.dlen = key2.ulen;
00750                             key2.flags |= DB_DBT_PARTIAL;
00751 
00752                             BDB_DISK2ID( &nlo, &lo );
00753                             data.data = &nhi;
00754 
00755                             rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
00756                             if ( rc != 0 && rc != DB_NOTFOUND ) {
00757                                    err = "c_get next_nodup";
00758                                    goto fail;
00759                             }
00760                             if ( rc == DB_NOTFOUND ) {
00761                                    rc = cursor->c_get( cursor, key, &data, DB_LAST );
00762                                    if ( rc != 0 ) {
00763                                           err = "c_get last";
00764                                           goto fail;
00765                                    }
00766                             } else {
00767                                    rc = cursor->c_get( cursor, key, &data, DB_PREV );
00768                                    if ( rc != 0 ) {
00769                                           err = "c_get prev";
00770                                           goto fail;
00771                                    }
00772                             }
00773                             BDB_DISK2ID( &nhi, &hi );
00774                             /* Update hi/lo if needed, then delete all the items
00775                              * between lo and hi
00776                              */
00777                             if ( id < lo ) {
00778                                    lo = id;
00779                                    nlo = nid;
00780                             } else if ( id > hi ) {
00781                                    hi = id;
00782                                    nhi = nid;
00783                             }
00784                             data.data = &nid;
00785                             /* Don't fetch anything, just position cursor */
00786                             data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
00787                             data.dlen = data.ulen = 0;
00788                             rc = cursor->c_get( cursor, key, &data, DB_SET );
00789                             if ( rc != 0 ) {
00790                                    err = "c_get 2";
00791                                    goto fail;
00792                             }
00793                             rc = cursor->c_del( cursor, 0 );
00794                             if ( rc != 0 ) {
00795                                    err = "c_del range1";
00796                                    goto fail;
00797                             }
00798                             /* Delete all the records */
00799                             for ( i=1; i<count; i++ ) {
00800                                    rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_DUP );
00801                                    if ( rc != 0 ) {
00802                                           err = "c_get next_dup";
00803                                           goto fail;
00804                                    }
00805                                    rc = cursor->c_del( cursor, 0 );
00806                                    if ( rc != 0 ) {
00807                                           err = "c_del range";
00808                                           goto fail;
00809                                    }
00810                             }
00811                             /* Store the range marker */
00812                             data.size = data.ulen = sizeof(ID);
00813                             data.flags = DB_DBT_USERMEM;
00814                             nid = 0;
00815                             rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
00816                             if ( rc != 0 ) {
00817                                    err = "c_put range";
00818                                    goto fail;
00819                             }
00820                             nid = nlo;
00821                             rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
00822                             if ( rc != 0 ) {
00823                                    err = "c_put lo";
00824                                    goto fail;
00825                             }
00826                             nid = nhi;
00827                             rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
00828                             if ( rc != 0 ) {
00829                                    err = "c_put hi";
00830                                    goto fail;
00831                             }
00832                      } else {
00833                      /* There's room, just store it */
00834                             goto put1;
00835                      }
00836               } else {
00837                      /* It's a range, see if we need to rewrite
00838                       * the boundaries
00839                       */
00840                      hi = id;
00841                      data.data = &nlo;
00842                      rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
00843                      if ( rc != 0 ) {
00844                             err = "c_get lo";
00845                             goto fail;
00846                      }
00847                      BDB_DISK2ID( &nlo, &lo );
00848                      if ( id > lo ) {
00849                             data.data = &nhi;
00850                             rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
00851                             if ( rc != 0 ) {
00852                                    err = "c_get hi";
00853                                    goto fail;
00854                             }
00855                             BDB_DISK2ID( &nhi, &hi );
00856                      }
00857                      if ( id < lo || id > hi ) {
00858                             /* Delete the current lo/hi */
00859                             rc = cursor->c_del( cursor, 0 );
00860                             if ( rc != 0 ) {
00861                                    err = "c_del";
00862                                    goto fail;
00863                             }
00864                             data.data = &nid;
00865                             rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
00866                             if ( rc != 0 ) {
00867                                    err = "c_put lo/hi";
00868                                    goto fail;
00869                             }
00870                      }
00871               }
00872        } else if ( rc == DB_NOTFOUND ) {
00873 put1:         data.data = &nid;
00874               rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA );
00875               /* Don't worry if it's already there */
00876               if ( rc != 0 && rc != DB_KEYEXIST ) {
00877                      err = "c_put id";
00878                      goto fail;
00879               }
00880        } else {
00881               /* initial c_get failed, nothing was done */
00882 fail:
00883               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
00884                      "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
00885               cursor->c_close( cursor );
00886               return rc;
00887        }
00888        /* If key was added (didn't already exist) and using IDL cache,
00889         * update key in IDL cache.
00890         */
00891        if ( !rc && bdb->bi_idl_cache_max_size ) {
00892               bdb_idl_cache_add_id( bdb, db, key, id );
00893        }
00894        rc = cursor->c_close( cursor );
00895        if( rc != 0 ) {
00896               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
00897                      "c_close failed: %s (%d)\n",
00898                      db_strerror(rc), rc, 0 );
00899        }
00900        return rc;
00901 }
00902 
00903 int
00904 bdb_idl_delete_key(
00905        BackendDB     *be,
00906        DB                   *db,
00907        DB_TXN        *tid,
00908        DBT                  *key,
00909        ID                   id )
00910 {
00911        struct bdb_info *bdb = (struct bdb_info *) be->be_private;
00912        int    rc;
00913        DBT data;
00914        DBC *cursor;
00915        ID lo, hi, tmp, nid, nlo, nhi;
00916        char *err;
00917 
00918        {
00919               char buf[16];
00920               Debug( LDAP_DEBUG_ARGS,
00921                      "bdb_idl_delete_key: %lx %s\n", 
00922                      (long) id, bdb_show_key( key, buf ), 0 );
00923        }
00924        assert( id != NOID );
00925 
00926        if ( bdb->bi_idl_cache_size ) {
00927               bdb_idl_cache_del( bdb, db, key );
00928        }
00929 
00930        BDB_ID2DISK( id, &nid );
00931 
00932        DBTzero( &data );
00933        data.data = &tmp;
00934        data.size = sizeof( id );
00935        data.ulen = data.size;
00936        data.flags = DB_DBT_USERMEM;
00937 
00938        rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
00939        if ( rc != 0 ) {
00940               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
00941                      "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
00942               return rc;
00943        }
00944        /* Fetch the first data item for this key, to see if it
00945         * exists and if it's a range.
00946         */
00947        rc = cursor->c_get( cursor, key, &data, DB_SET );
00948        err = "c_get";
00949        if ( rc == 0 ) {
00950               if ( tmp != 0 ) {
00951                      /* Not a range, just delete it */
00952                      if (tmp != nid) {
00953                             /* position to correct item */
00954                             tmp = nid;
00955                             rc = cursor->c_get( cursor, key, &data, DB_GET_BOTH );
00956                             if ( rc != 0 ) {
00957                                    err = "c_get id";
00958                                    goto fail;
00959                             }
00960                      }
00961                      rc = cursor->c_del( cursor, 0 );
00962                      if ( rc != 0 ) {
00963                             err = "c_del id";
00964                             goto fail;
00965                      }
00966               } else {
00967                      /* It's a range, see if we need to rewrite
00968                       * the boundaries
00969                       */
00970                      data.data = &nlo;
00971                      rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
00972                      if ( rc != 0 ) {
00973                             err = "c_get lo";
00974                             goto fail;
00975                      }
00976                      BDB_DISK2ID( &nlo, &lo );
00977                      data.data = &nhi;
00978                      rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
00979                      if ( rc != 0 ) {
00980                             err = "c_get hi";
00981                             goto fail;
00982                      }
00983                      BDB_DISK2ID( &nhi, &hi );
00984                      if ( id == lo || id == hi ) {
00985                             if ( id == lo ) {
00986                                    id++;
00987                                    lo = id;
00988                             } else if ( id == hi ) {
00989                                    id--;
00990                                    hi = id;
00991                             }
00992                             if ( lo >= hi ) {
00993                             /* The range has collapsed... */
00994                                    rc = db->del( db, tid, key, 0 );
00995                                    if ( rc != 0 ) {
00996                                           err = "del";
00997                                           goto fail;
00998                                    }
00999                             } else {
01000                                    if ( id == lo ) {
01001                                           /* reposition on lo slot */
01002                                           data.data = &nlo;
01003                                           cursor->c_get( cursor, key, &data, DB_PREV );
01004                                    }
01005                                    rc = cursor->c_del( cursor, 0 );
01006                                    if ( rc != 0 ) {
01007                                           err = "c_del";
01008                                           goto fail;
01009                                    }
01010                             }
01011                             if ( lo <= hi ) {
01012                                    BDB_ID2DISK( id, &nid );
01013                                    data.data = &nid;
01014                                    rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
01015                                    if ( rc != 0 ) {
01016                                           err = "c_put lo/hi";
01017                                           goto fail;
01018                                    }
01019                             }
01020                      }
01021               }
01022        } else {
01023               /* initial c_get failed, nothing was done */
01024 fail:
01025               if ( rc != DB_NOTFOUND ) {
01026               Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
01027                      "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
01028               }
01029               cursor->c_close( cursor );
01030               return rc;
01031        }
01032        rc = cursor->c_close( cursor );
01033        if( rc != 0 ) {
01034               Debug( LDAP_DEBUG_ANY,
01035                      "=> bdb_idl_delete_key: c_close failed: %s (%d)\n",
01036                      db_strerror(rc), rc, 0 );
01037        }
01038 
01039        return rc;
01040 }
01041 
01042 
01043 /*
01044  * idl_intersection - return a = a intersection b
01045  */
01046 int
01047 bdb_idl_intersection(
01048        ID *a,
01049        ID *b )
01050 {
01051        ID ida, idb;
01052        ID idmax, idmin;
01053        ID cursora = 0, cursorb = 0, cursorc;
01054        int swap = 0;
01055 
01056        if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
01057               a[0] = 0;
01058               return 0;
01059        }
01060 
01061        idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
01062        idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
01063        if ( idmin > idmax ) {
01064               a[0] = 0;
01065               return 0;
01066        } else if ( idmin == idmax ) {
01067               a[0] = 1;
01068               a[1] = idmin;
01069               return 0;
01070        }
01071 
01072        if ( BDB_IDL_IS_RANGE( a ) ) {
01073               if ( BDB_IDL_IS_RANGE(b) ) {
01074               /* If both are ranges, just shrink the boundaries */
01075                      a[1] = idmin;
01076                      a[2] = idmax;
01077                      return 0;
01078               } else {
01079               /* Else swap so that b is the range, a is a list */
01080                      ID *tmp = a;
01081                      a = b;
01082                      b = tmp;
01083                      swap = 1;
01084               }
01085        }
01086 
01087        /* If a range completely covers the list, the result is
01088         * just the list. If idmin to idmax is contiguous, just
01089         * turn it into a range.
01090         */
01091        if ( BDB_IDL_IS_RANGE( b )
01092               && BDB_IDL_RANGE_FIRST( b ) <= BDB_IDL_RANGE_FIRST( a )
01093               && BDB_IDL_RANGE_LAST( b ) >= BDB_IDL_RANGE_LAST( a ) ) {
01094               if (idmax - idmin + 1 == a[0])
01095               {
01096                      a[0] = NOID;
01097                      a[1] = idmin;
01098                      a[2] = idmax;
01099               }
01100               goto done;
01101        }
01102 
01103        /* Fine, do the intersection one element at a time.
01104         * First advance to idmin in both IDLs.
01105         */
01106        cursora = cursorb = idmin;
01107        ida = bdb_idl_first( a, &cursora );
01108        idb = bdb_idl_first( b, &cursorb );
01109        cursorc = 0;
01110 
01111        while( ida <= idmax || idb <= idmax ) {
01112               if( ida == idb ) {
01113                      a[++cursorc] = ida;
01114                      ida = bdb_idl_next( a, &cursora );
01115                      idb = bdb_idl_next( b, &cursorb );
01116               } else if ( ida < idb ) {
01117                      ida = bdb_idl_next( a, &cursora );
01118               } else {
01119                      idb = bdb_idl_next( b, &cursorb );
01120               }
01121        }
01122        a[0] = cursorc;
01123 done:
01124        if (swap)
01125               BDB_IDL_CPY( b, a );
01126 
01127        return 0;
01128 }
01129 
01130 
01131 /*
01132  * idl_union - return a = a union b
01133  */
01134 int
01135 bdb_idl_union(
01136        ID     *a,
01137        ID     *b )
01138 {
01139        ID ida, idb;
01140        ID cursora = 0, cursorb = 0, cursorc;
01141 
01142        if ( BDB_IDL_IS_ZERO( b ) ) {
01143               return 0;
01144        }
01145 
01146        if ( BDB_IDL_IS_ZERO( a ) ) {
01147               BDB_IDL_CPY( a, b );
01148               return 0;
01149        }
01150 
01151        if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
01152 over:         ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
01153               idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
01154               a[0] = NOID;
01155               a[1] = ida;
01156               a[2] = idb;
01157               return 0;
01158        }
01159 
01160        ida = bdb_idl_first( a, &cursora );
01161        idb = bdb_idl_first( b, &cursorb );
01162 
01163        cursorc = b[0];
01164 
01165        /* The distinct elements of a are cat'd to b */
01166        while( ida != NOID || idb != NOID ) {
01167               if ( ida < idb ) {
01168                      if( ++cursorc > BDB_IDL_UM_MAX ) {
01169                             goto over;
01170                      }
01171                      b[cursorc] = ida;
01172                      ida = bdb_idl_next( a, &cursora );
01173 
01174               } else {
01175                      if ( ida == idb )
01176                             ida = bdb_idl_next( a, &cursora );
01177                      idb = bdb_idl_next( b, &cursorb );
01178               }
01179        }
01180 
01181        /* b is copied back to a in sorted order */
01182        a[0] = cursorc;
01183        cursora = 1;
01184        cursorb = 1;
01185        cursorc = b[0]+1;
01186        while (cursorb <= b[0] || cursorc <= a[0]) {
01187               if (cursorc > a[0])
01188                      idb = NOID;
01189               else
01190                      idb = b[cursorc];
01191               if (cursorb <= b[0] && b[cursorb] < idb)
01192                      a[cursora++] = b[cursorb++];
01193               else {
01194                      a[cursora++] = idb;
01195                      cursorc++;
01196               }
01197        }
01198 
01199        return 0;
01200 }
01201 
01202 
01203 #if 0
01204 /*
01205  * bdb_idl_notin - return a intersection ~b (or a minus b)
01206  */
01207 int
01208 bdb_idl_notin(
01209        ID     *a,
01210        ID     *b,
01211        ID *ids )
01212 {
01213        ID ida, idb;
01214        ID cursora = 0, cursorb = 0;
01215 
01216        if( BDB_IDL_IS_ZERO( a ) ||
01217               BDB_IDL_IS_ZERO( b ) ||
01218               BDB_IDL_IS_RANGE( b ) )
01219        {
01220               BDB_IDL_CPY( ids, a );
01221               return 0;
01222        }
01223 
01224        if( BDB_IDL_IS_RANGE( a ) ) {
01225               BDB_IDL_CPY( ids, a );
01226               return 0;
01227        }
01228 
01229        ida = bdb_idl_first( a, &cursora ),
01230        idb = bdb_idl_first( b, &cursorb );
01231 
01232        ids[0] = 0;
01233 
01234        while( ida != NOID ) {
01235               if ( idb == NOID ) {
01236                      /* we could shortcut this */
01237                      ids[++ids[0]] = ida;
01238                      ida = bdb_idl_next( a, &cursora );
01239 
01240               } else if ( ida < idb ) {
01241                      ids[++ids[0]] = ida;
01242                      ida = bdb_idl_next( a, &cursora );
01243 
01244               } else if ( ida > idb ) {
01245                      idb = bdb_idl_next( b, &cursorb );
01246 
01247               } else {
01248                      ida = bdb_idl_next( a, &cursora );
01249                      idb = bdb_idl_next( b, &cursorb );
01250               }
01251        }
01252 
01253        return 0;
01254 }
01255 #endif
01256 
01257 ID bdb_idl_first( ID *ids, ID *cursor )
01258 {
01259        ID pos;
01260 
01261        if ( ids[0] == 0 ) {
01262               *cursor = NOID;
01263               return NOID;
01264        }
01265 
01266        if ( BDB_IDL_IS_RANGE( ids ) ) {
01267               if( *cursor < ids[1] ) {
01268                      *cursor = ids[1];
01269               }
01270               return *cursor;
01271        }
01272 
01273        if ( *cursor == 0 )
01274               pos = 1;
01275        else
01276               pos = bdb_idl_search( ids, *cursor );
01277 
01278        if( pos > ids[0] ) {
01279               return NOID;
01280        }
01281 
01282        *cursor = pos;
01283        return ids[pos];
01284 }
01285 
01286 ID bdb_idl_next( ID *ids, ID *cursor )
01287 {
01288        if ( BDB_IDL_IS_RANGE( ids ) ) {
01289               if( ids[2] < ++(*cursor) ) {
01290                      return NOID;
01291               }
01292               return *cursor;
01293        }
01294 
01295        if ( ++(*cursor) <= ids[0] ) {
01296               return ids[*cursor];
01297        }
01298 
01299        return NOID;
01300 }
01301 
01302 #ifdef BDB_HIER
01303 
01304 /* Add one ID to an unsorted list. We ensure that the first element is the
01305  * minimum and the last element is the maximum, for fast range compaction.
01306  *   this means IDLs up to length 3 are always sorted...
01307  */
01308 int bdb_idl_append_one( ID *ids, ID id )
01309 {
01310        if (BDB_IDL_IS_RANGE( ids )) {
01311               /* if already in range, treat as a dup */
01312               if (id >= BDB_IDL_RANGE_FIRST(ids) && id <= BDB_IDL_RANGE_LAST(ids))
01313                      return -1;
01314               if (id < BDB_IDL_RANGE_FIRST(ids))
01315                      ids[1] = id;
01316               else if (id > BDB_IDL_RANGE_LAST(ids))
01317                      ids[2] = id;
01318               return 0;
01319        }
01320        if ( ids[0] ) {
01321               ID tmp;
01322 
01323               if (id < ids[1]) {
01324                      tmp = ids[1];
01325                      ids[1] = id;
01326                      id = tmp;
01327               }
01328               if ( ids[0] > 1 && id < ids[ids[0]] ) {
01329                      tmp = ids[ids[0]];
01330                      ids[ids[0]] = id;
01331                      id = tmp;
01332               }
01333        }
01334        ids[0]++;
01335        if ( ids[0] >= BDB_IDL_UM_MAX ) {
01336               ids[0] = NOID;
01337               ids[2] = id;
01338        } else {
01339               ids[ids[0]] = id;
01340        }
01341        return 0;
01342 }
01343 
01344 /* Append sorted list b to sorted list a. The result is unsorted but
01345  * a[1] is the min of the result and a[a[0]] is the max.
01346  */
01347 int bdb_idl_append( ID *a, ID *b )
01348 {
01349        ID ida, idb, tmp, swap = 0;
01350 
01351        if ( BDB_IDL_IS_ZERO( b ) ) {
01352               return 0;
01353        }
01354 
01355        if ( BDB_IDL_IS_ZERO( a ) ) {
01356               BDB_IDL_CPY( a, b );
01357               return 0;
01358        }
01359 
01360        if ( b[0] == 1 ) {
01361               return bdb_idl_append_one( a, BDB_IDL_FIRST( b ));
01362        }
01363 
01364        ida = BDB_IDL_LAST( a );
01365        idb = BDB_IDL_LAST( b );
01366        if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ||
01367               a[0] + b[0] >= BDB_IDL_UM_MAX ) {
01368               a[2] = IDL_MAX( ida, idb );
01369               a[1] = IDL_MIN( a[1], b[1] );
01370               a[0] = NOID;
01371               return 0;
01372        }
01373 
01374        if ( ida > idb ) {
01375               swap = idb;
01376               a[a[0]] = idb;
01377               b[b[0]] = ida;
01378        }
01379 
01380        if ( b[1] < a[1] ) {
01381               tmp = a[1];
01382               a[1] = b[1];
01383        } else {
01384               tmp = b[1];
01385        }
01386        a[0]++;
01387        a[a[0]] = tmp;
01388 
01389        {
01390               int i = b[0] - 1;
01391               AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
01392               a[0] += i;
01393        }
01394        if ( swap ) {
01395               b[b[0]] = swap;
01396        }
01397        return 0;
01398 }
01399 
01400 #if 1
01401 
01402 /* Quicksort + Insertion sort for small arrays */
01403 
01404 #define SMALL 8
01405 #define       SWAP(a,b)     itmp=(a);(a)=(b);(b)=itmp
01406 
01407 void
01408 bdb_idl_sort( ID *ids, ID *tmp )
01409 {
01410        int *istack = (int *)tmp;
01411        int i,j,k,l,ir,jstack;
01412        ID a, itmp;
01413 
01414        if ( BDB_IDL_IS_RANGE( ids ))
01415               return;
01416 
01417        ir = ids[0];
01418        l = 1;
01419        jstack = 0;
01420        for(;;) {
01421               if (ir - l < SMALL) {       /* Insertion sort */
01422                      for (j=l+1;j<=ir;j++) {
01423                             a = ids[j];
01424                             for (i=j-1;i>=1;i--) {
01425                                    if (ids[i] <= a) break;
01426                                    ids[i+1] = ids[i];
01427                             }
01428                             ids[i+1] = a;
01429                      }
01430                      if (jstack == 0) break;
01431                      ir = istack[jstack--];
01432                      l = istack[jstack--];
01433               } else {
01434                      k = (l + ir) >> 1;   /* Choose median of left, center, right */
01435                      SWAP(ids[k], ids[l+1]);
01436                      if (ids[l] > ids[ir]) {
01437                             SWAP(ids[l], ids[ir]);
01438                      }
01439                      if (ids[l+1] > ids[ir]) {
01440                             SWAP(ids[l+1], ids[ir]);
01441                      }
01442                      if (ids[l] > ids[l+1]) {
01443                             SWAP(ids[l], ids[l+1]);
01444                      }
01445                      i = l+1;
01446                      j = ir;
01447                      a = ids[l+1];
01448                      for(;;) {
01449                             do i++; while(ids[i] < a);
01450                             do j--; while(ids[j] > a);
01451                             if (j < i) break;
01452                             SWAP(ids[i],ids[j]);
01453                      }
01454                      ids[l+1] = ids[j];
01455                      ids[j] = a;
01456                      jstack += 2;
01457                      if (ir-i+1 >= j-1) {
01458                             istack[jstack] = ir;
01459                             istack[jstack-1] = i;
01460                             ir = j-1;
01461                      } else {
01462                             istack[jstack] = j-1;
01463                             istack[jstack-1] = l;
01464                             l = i;
01465                      }
01466               }
01467        }
01468 }
01469 
01470 #else
01471 
01472 /* 8 bit Radix sort + insertion sort
01473  * 
01474  * based on code from http://www.cubic.org/docs/radix.htm
01475  * with improvements by mbackes@symas.com and hyc@symas.com
01476  *
01477  * This code is O(n) but has a relatively high constant factor. For lists
01478  * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
01479  * Much faster than quicksort for lists longer than ~100. Insertion
01480  * sort is actually superior for lists <50.
01481  */
01482 
01483 #define BUCKETS      (1<<8)
01484 #define SMALL 50
01485 
01486 void
01487 bdb_idl_sort( ID *ids, ID *tmp )
01488 {
01489        int count, soft_limit, phase = 0, size = ids[0];
01490        ID *idls[2];
01491        unsigned char *maxv = (unsigned char *)&ids[size];
01492 
01493        if ( BDB_IDL_IS_RANGE( ids ))
01494               return;
01495 
01496        /* Use insertion sort for small lists */
01497        if ( size <= SMALL ) {
01498               int i,j;
01499               ID a;
01500 
01501               for (j=1;j<=size;j++) {
01502                      a = ids[j];
01503                      for (i=j-1;i>=1;i--) {
01504                             if (ids[i] <= a) break;
01505                             ids[i+1] = ids[i];
01506                      }
01507                      ids[i+1] = a;
01508               }
01509               return;
01510        }
01511 
01512        tmp[0] = size;
01513        idls[0] = ids;
01514        idls[1] = tmp;
01515 
01516 #if BYTE_ORDER == BIG_ENDIAN
01517     for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
01518 #else
01519     for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
01520 #endif
01521 
01522        for (
01523 #if BYTE_ORDER == BIG_ENDIAN
01524        count = sizeof(ID)-1; count >= soft_limit; --count
01525 #else
01526        count = 0; count <= soft_limit; ++count
01527 #endif
01528        ) {
01529               unsigned int num[BUCKETS], * np, n, sum;
01530               int i;
01531         ID *sp, *source, *dest;
01532         unsigned char *bp, *source_start;
01533 
01534               source = idls[phase]+1;
01535               dest = idls[phase^1]+1;
01536               source_start =  ((unsigned char *) source) + count;
01537 
01538         np = num;
01539         for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
01540 
01541               /* count occurences of every byte value */
01542               bp = source_start;
01543         for ( i = size; i > 0; --i, bp += sizeof(ID) )
01544                             num[*bp]++;
01545 
01546               /* transform count into index by summing elements and storing
01547                * into same array
01548                */
01549         sum = 0;
01550         np = num;
01551         for ( i = BUCKETS; i > 0; --i ) {
01552                 n = *np;
01553                 *np++ = sum;
01554                 sum += n;
01555         }
01556 
01557               /* fill dest with the right values in the right place */
01558               bp = source_start;
01559         sp = source;
01560         for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
01561                 np = num + *bp;
01562                 dest[*np] = *sp++;
01563                 ++(*np);
01564         }
01565               phase ^= 1;
01566        }
01567 
01568        /* copy back from temp if needed */
01569        if ( phase ) {
01570               ids++; tmp++;
01571               for ( count = 0; count < size; ++count ) 
01572                      *ids++ = *tmp++;
01573        }
01574 }
01575 #endif /* Quick vs Radix */
01576 
01577 #endif /* BDB_HIER */