1 /* idl.c - ldap id list handling routines */
4 * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
5 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
11 #include <ac/string.h>
16 #define IDL_MAX(x,y) ( x > y ? x : y )
17 #define IDL_MIN(x,y) ( x < y ? x : y )
19 #define IDL_CMP(x,y) ( x < y ? -1 : ( x > y ? 1 : 0 ) )
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; \
26 bdb->bi_idl_lru_head = e->idl_lru_next; \
28 if ( e->idl_lru_next != NULL ) { \
29 e->idl_lru_next->idl_lru_prev = e->idl_lru_prev; \
31 bdb->bi_idl_lru_tail = e->idl_lru_prev; \
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); \
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); \
48 bdb_idl_entry_cmp( const void *v_idl1, const void *v_idl2 )
50 const bdb_idl_cache_entry_t *idl1 = v_idl1, *idl2 = v_idl2;
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 ) );
60 static void idl_check( ID *ids )
62 if( BDB_IDL_IS_RANGE( ids ) ) {
63 assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
66 for( i=1; i < ids[0]; i++ ) {
67 assert( ids[i+1] > ids[i] );
73 static void idl_dump( ID *ids )
75 if( BDB_IDL_IS_RANGE( ids ) ) {
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 );
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 ) );
90 LDAP_LOG( INDEX, INFO, "IDL: size %ld", (long) ids[0], 0, 0 );
92 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
95 for( i=1; i<=ids[0]; i++ ) {
97 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
100 LDAP_LOG( INDEX, INFO, "%02lx",(long)ids[i], 0, 0 );
102 Debug( LDAP_DEBUG_ANY, " %02lx", (long) ids[i], 0, 0 );
106 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
111 #endif /* IDL_DEBUG > 1 */
112 #endif /* IDL_DEBUG > 0 */
114 unsigned bdb_idl_search( ID *ids, ID id )
116 #define IDL_BINARY_SEARCH 1
117 #ifdef IDL_BINARY_SEARCH
119 * binary search of id in ids
120 * if found, returns position of id
121 * if not found, returns first postion greater than id
134 cursor = base + pivot;
135 val = IDL_CMP( id, ids[cursor + 1] );
140 } else if ( val > 0 ) {
156 /* (reverse) linear search */
163 for( i=ids[0]; i; i-- ) {
173 int bdb_idl_insert( ID *ids, ID id )
175 unsigned x = bdb_idl_search( ids, id );
179 LDAP_LOG( INDEX, DETAIL1, "insert: %04lx at %d\n", (long) id, x, 0 );
181 Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
195 if ( x <= ids[0] && ids[x] == id ) {
200 if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
203 ids[2] = ids[ids[0]-1];
204 } else if ( ids[ids[0]-1] < id ) {
207 ids[2] = ids[ids[0]-1];
213 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
227 static int idl_delete( ID *ids, ID id )
229 unsigned x = bdb_idl_search( ids, id );
233 LDAP_LOG( INDEX, DETAIL1, "delete: %04lx at %d\n", (long) id, x, 0 );
235 Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
249 if( x > ids[0] || ids[x] != id ) {
253 } else if ( --ids[0] == 0 ) {
259 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
277 if ( key->size == sizeof( ID ) ) {
278 unsigned char *c = key->data;
279 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
294 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
302 int flags = bdb->bi_db_opflags | DB_MULTIPLE;
303 #ifdef SLAP_IDL_CACHE
304 bdb_idl_cache_entry_t idl_tmp;
307 /* buf must be large enough to grab the entire IDL in one
308 * get(), otherwise BDB 4 will leak resources on subsequent
309 * get's. We can safely call get() twice - once for the data,
310 * and once to get the DB_NOTFOUND result meaning there's
311 * no more data. See ITS#2040 for details. This bug is fixed
312 * in BDB 4.1 so a smaller buffer will work if stack space is
315 ID buf[BDB_IDL_DB_SIZE*5];
320 LDAP_LOG( INDEX, ARGS,
321 "bdb_idl_fetch_key: %s\n",
322 bdb_show_key( key, buf ), 0, 0 );
324 Debug( LDAP_DEBUG_ARGS,
325 "bdb_idl_fetch_key: %s\n",
326 bdb_show_key( key, buf ), 0, 0 );
329 assert( ids != NULL );
331 #ifdef SLAP_IDL_CACHE
332 if ( bdb->bi_idl_cache_max_size ) {
333 bdb_idl_cache_entry_t *matched_idl_entry;
334 DBT2bv( key, &idl_tmp.kstr );
336 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex );
337 matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
339 if ( matched_idl_entry != NULL ) {
340 BDB_IDL_CPY( ids, matched_idl_entry->idl );
341 IDL_LRU_DELETE( bdb, matched_idl_entry );
342 IDL_LRU_ADD( bdb, matched_idl_entry );
343 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex );
346 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex );
353 data.ulen = sizeof(buf);
354 data.flags = DB_DBT_USERMEM;
359 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
362 LDAP_LOG( INDEX, ERR,
363 "bdb_idl_fetch_key: cursor failed: %s (%d)\n",
364 db_strerror(rc), rc, 0 );
366 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
367 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
371 rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
377 DB_MULTIPLE_INIT( ptr, &data );
379 DB_MULTIPLE_NEXT(ptr, &data, j, len);
382 AC_MEMCPY( i, j, sizeof(ID) );
385 rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
387 if ( rc == DB_NOTFOUND ) rc = 0;
389 /* On disk, a range is denoted by 0 in the first element */
391 if (ids[0] != BDB_IDL_RANGE_SIZE) {
393 LDAP_LOG( INDEX, ERR,
394 "=> bdb_idl_fetch_key: range size mismatch: "
395 "expected %ld, got %ld\n",
396 BDB_IDL_RANGE_SIZE, ids[0], 0 );
398 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
399 "range size mismatch: expected %d, got %ld\n",
400 BDB_IDL_RANGE_SIZE, ids[0], 0 );
402 cursor->c_close( cursor );
405 BDB_IDL_RANGE( ids, ids[2], ids[3] );
407 data.size = BDB_IDL_SIZEOF(ids);
409 rc2 = cursor->c_close( cursor );
412 LDAP_LOG( INDEX, ERR,
413 "bdb_idl_fetch_key: close failed: %s (%d)\n",
414 db_strerror(rc2), rc2, 0 );
416 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
417 "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
421 if( rc == DB_NOTFOUND ) {
424 } else if( rc != 0 ) {
426 LDAP_LOG( INDEX, ERR,
427 "bdb_idl_fetch_key: get failed: %s (%d)\n",
428 db_strerror(rc), rc, 0 );
430 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
431 "get failed: %s (%d)\n",
432 db_strerror(rc), rc, 0 );
436 } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
437 /* size not multiple of ID size */
439 LDAP_LOG( INDEX, ERR,
440 "bdb_idl_fetch_key: odd size: expected %ld multiple, got %ld\n",
441 (long) sizeof( ID ), (long) data.size, 0 );
443 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
444 "odd size: expected %ld multiple, got %ld\n",
445 (long) sizeof( ID ), (long) data.size, 0 );
449 } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
452 LDAP_LOG( INDEX, ERR,
453 "bdb_idl_fetch_key: get size mismatch: expected %ld, got %ld\n",
454 (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
456 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
457 "get size mismatch: expected %ld, got %ld\n",
458 (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
463 #ifdef SLAP_IDL_CACHE
464 if ( bdb->bi_idl_cache_max_size ) {
465 bdb_idl_cache_entry_t *ee;
466 ee = (bdb_idl_cache_entry_t *) malloc( sizeof( bdb_idl_cache_entry_t ) );
468 ee->idl = (ID*) malloc ( BDB_IDL_SIZEOF ( ids ) );
469 ee->idl_lru_prev = NULL;
470 ee->idl_lru_next = NULL;
471 BDB_IDL_CPY( ee->idl, ids );
472 ber_dupbv( &ee->kstr, &idl_tmp.kstr );
473 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex );
474 if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee,
475 bdb_idl_entry_cmp, avl_dup_error )) {
476 free( ee->kstr.bv_val );
480 IDL_LRU_ADD( bdb, ee );
481 if ( ++bdb->bi_idl_cache_size > bdb->bi_idl_cache_max_size ) {
483 while ( bdb->bi_idl_lru_tail != NULL && i < 10 ) {
484 ee = bdb->bi_idl_lru_tail;
485 avl_delete( &bdb->bi_idl_tree, (caddr_t) ee,
487 IDL_LRU_DELETE( bdb, ee );
489 --bdb->bi_idl_cache_size;
490 free( ee->kstr.bv_val );
496 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex );
512 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
522 LDAP_LOG( INDEX, ARGS,
523 "bdb_idl_insert_key: %lx %s\n",
524 (long) id, bdb_show_key( key, buf ), 0 );
526 Debug( LDAP_DEBUG_ARGS,
527 "bdb_idl_insert_key: %lx %s\n",
528 (long) id, bdb_show_key( key, buf ), 0 );
532 assert( id != NOID );
534 #ifdef SLAP_IDL_CACHE
535 if ( bdb->bi_idl_cache_size ) {
536 bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp;
537 DBT2bv( key, &idl_tmp.kstr );
539 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex );
540 matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
542 if ( matched_idl_entry != NULL ) {
543 avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry,
545 --bdb->bi_idl_cache_size;
546 IDL_LRU_DELETE( bdb, matched_idl_entry );
547 free( matched_idl_entry->kstr.bv_val );
548 free( matched_idl_entry->idl );
549 free( matched_idl_entry );
551 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex );
556 data.size = sizeof( ID );
557 data.ulen = data.size;
558 data.flags = DB_DBT_USERMEM;
560 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
563 LDAP_LOG( INDEX, ERR,
564 "bdb_idl_insert_key: cursor failed: %s (%d)\n",
565 db_strerror(rc), rc, 0 );
567 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
568 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
573 /* Fetch the first data item for this key, to see if it
574 * exists and if it's a range.
576 rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
580 /* not a range, count the number of items */
582 rc = cursor->c_count( cursor, &count, 0 );
587 if ( count >= BDB_IDL_DB_MAX ) {
588 /* No room, convert to a range */
591 key2.dlen = key2.ulen;
592 key2.flags |= DB_DBT_PARTIAL;
596 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
597 if ( rc != 0 && rc != DB_NOTFOUND ) {
598 err = "c_get next_nodup";
601 if ( rc == DB_NOTFOUND ) {
602 rc = cursor->c_get( cursor, key, &data, DB_LAST );
608 rc = cursor->c_get( cursor, key, &data, DB_PREV );
618 rc = db->del( db, tid, key, 0 );
625 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
631 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
637 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
643 /* There's room, just store it */
647 /* It's a range, see if we need to rewrite
652 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
659 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
665 if ( id < lo || id > hi ) {
666 /* Delete the current lo/hi */
667 rc = cursor->c_del( cursor, 0 );
673 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
680 } else if ( rc == DB_NOTFOUND ) {
681 put1: data.data = &id;
682 rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA );
683 /* Don't worry if it's already there */
684 if ( rc != 0 && rc != DB_KEYEXIST ) {
689 /* initial c_get failed, nothing was done */
692 LDAP_LOG( INDEX, ERR,
693 "bdb_idl_insert_key: %s failed: %s (%d)\n",
694 err, db_strerror(rc), rc );
696 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
697 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
699 cursor->c_close( cursor );
702 rc = cursor->c_close( cursor );
705 LDAP_LOG( INDEX, ERR,
706 "bdb_idl_insert_key: c_close failed: %s (%d)\n",
707 db_strerror(rc), rc, 0 );
709 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
710 "c_close failed: %s (%d)\n",
711 db_strerror(rc), rc, 0 );
725 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
735 LDAP_LOG( INDEX, ARGS,
736 "bdb_idl_delete_key: %lx %s\n",
737 (long) id, bdb_show_key( key, buf ), 0 );
739 Debug( LDAP_DEBUG_ARGS,
740 "bdb_idl_delete_key: %lx %s\n",
741 (long) id, bdb_show_key( key, buf ), 0 );
744 assert( id != NOID );
746 #ifdef SLAP_IDL_CACHE
747 if ( bdb->bi_idl_cache_max_size ) {
748 bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp;
749 DBT2bv( key, &idl_tmp.kstr );
751 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_mutex );
752 matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
754 if ( matched_idl_entry != NULL ) {
755 avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry,
757 --bdb->bi_idl_cache_size;
758 IDL_LRU_DELETE( bdb, matched_idl_entry );
759 free( matched_idl_entry->kstr.bv_val );
760 free( matched_idl_entry->idl );
761 free( matched_idl_entry );
763 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_mutex );
769 data.size = sizeof( id );
770 data.ulen = data.size;
771 data.flags = DB_DBT_USERMEM;
773 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
776 LDAP_LOG( INDEX, ERR,
777 "bdb_idl_delete_key: cursor failed: %s (%d)\n",
778 db_strerror(rc), rc, 0 );
780 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
781 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
785 /* Fetch the first data item for this key, to see if it
786 * exists and if it's a range.
788 rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
792 /* Not a range, just delete it */
794 /* position to correct item */
796 rc = cursor->c_get( cursor, key, &data,
797 DB_GET_BOTH | DB_RMW );
803 rc = cursor->c_del( cursor, 0 );
809 /* It's a range, see if we need to rewrite
814 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
821 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
827 if ( id == lo || id == hi ) {
831 } else if ( id == hi ) {
836 /* The range has collapsed... */
837 rc = db->del( db, tid, key, 0 );
843 rc = cursor->c_del( cursor, 0 );
851 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
860 /* initial c_get failed, nothing was done */
862 if ( rc != DB_NOTFOUND ) {
864 LDAP_LOG( INDEX, ERR,
865 "bdb_idl_delete_key: %s failed: %s (%d)\n",
866 err, db_strerror(rc), rc );
868 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
869 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
872 cursor->c_close( cursor );
875 rc = cursor->c_close( cursor );
878 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: c_close failed: %s (%d)\n",
879 db_strerror(rc), rc, 0 );
881 Debug( LDAP_DEBUG_ANY,
882 "=> bdb_idl_delete_key: c_close failed: %s (%d)\n",
883 db_strerror(rc), rc, 0 );
892 * idl_intersection - return a = a intersection b
895 bdb_idl_intersection(
901 ID cursora = 0, cursorb = 0, cursorc;
904 if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
909 idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
910 idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
911 if ( idmin > idmax ) {
914 } else if ( idmin == idmax ) {
920 if ( BDB_IDL_IS_RANGE( a ) ) {
921 if ( BDB_IDL_IS_RANGE(b) ) {
922 /* If both are ranges, just shrink the boundaries */
927 /* Else swap so that b is the range, a is a list */
935 /* If a range completely covers the list, the result is
936 * just the list. If idmin to idmax is contiguous, just
937 * turn it into a range.
939 if ( BDB_IDL_IS_RANGE( b )
940 && BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
941 && BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
942 if (idmax - idmin + 1 == a[0])
951 /* Fine, do the intersection one element at a time.
952 * First advance to idmin in both IDLs.
954 cursora = cursorb = idmin;
955 ida = bdb_idl_first( a, &cursora );
956 idb = bdb_idl_first( b, &cursorb );
959 while( ida <= idmax || idb <= idmax ) {
962 ida = bdb_idl_next( a, &cursora );
963 idb = bdb_idl_next( b, &cursorb );
964 } else if ( ida < idb ) {
965 ida = bdb_idl_next( a, &cursora );
967 idb = bdb_idl_next( b, &cursorb );
980 * idl_union - return a = a union b
988 ID cursora = 0, cursorb = 0, cursorc;
990 if ( BDB_IDL_IS_ZERO( b ) ) {
994 if ( BDB_IDL_IS_ZERO( a ) ) {
999 if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
1000 over: ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
1001 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
1008 ida = bdb_idl_first( a, &cursora );
1009 idb = bdb_idl_first( b, &cursorb );
1013 /* The distinct elements of a are cat'd to b */
1014 while( ida != NOID || idb != NOID ) {
1016 if( ++cursorc > BDB_IDL_UM_MAX ) {
1020 ida = bdb_idl_next( a, &cursora );
1024 ida = bdb_idl_next( a, &cursora );
1025 idb = bdb_idl_next( b, &cursorb );
1029 /* b is copied back to a in sorted order */
1034 while (cursorb <= b[0] || cursorc <= a[0]) {
1039 if (cursorb <= b[0] && b[cursorb] < idb)
1040 a[cursora++] = b[cursorb++];
1053 * bdb_idl_notin - return a intersection ~b (or a minus b)
1062 ID cursora = 0, cursorb = 0;
1064 if( BDB_IDL_IS_ZERO( a ) ||
1065 BDB_IDL_IS_ZERO( b ) ||
1066 BDB_IDL_IS_RANGE( b ) )
1068 BDB_IDL_CPY( ids, a );
1072 if( BDB_IDL_IS_RANGE( a ) ) {
1073 BDB_IDL_CPY( ids, a );
1077 ida = bdb_idl_first( a, &cursora ),
1078 idb = bdb_idl_first( b, &cursorb );
1082 while( ida != NOID ) {
1083 if ( idb == NOID ) {
1084 /* we could shortcut this */
1085 ids[++ids[0]] = ida;
1086 ida = bdb_idl_next( a, &cursora );
1088 } else if ( ida < idb ) {
1089 ids[++ids[0]] = ida;
1090 ida = bdb_idl_next( a, &cursora );
1092 } else if ( ida > idb ) {
1093 idb = bdb_idl_next( b, &cursorb );
1096 ida = bdb_idl_next( a, &cursora );
1097 idb = bdb_idl_next( b, &cursorb );
1105 ID bdb_idl_first( ID *ids, ID *cursor )
1109 if ( ids[0] == 0 ) {
1114 if ( BDB_IDL_IS_RANGE( ids ) ) {
1115 if( *cursor < ids[1] ) {
1124 pos = bdb_idl_search( ids, *cursor );
1126 if( pos > ids[0] ) {
1134 ID bdb_idl_next( ID *ids, ID *cursor )
1136 if ( BDB_IDL_IS_RANGE( ids ) ) {
1137 if( ids[2] < ++(*cursor) ) {
1143 if ( ++(*cursor) <= ids[0] ) {
1144 return ids[*cursor];