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