1 /* idl.c - ldap id list handling routines */
4 * Copyright 1998-2002 The OpenLDAP Foundation, All Rights Reserved.
5 * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
12 #include <ac/string.h>
13 #include <ac/socket.h>
16 #include "back-ldbm.h"
18 static ID_BLOCK* idl_dup( ID_BLOCK *idl );
20 static void cont_alloc( Datum *cont, Datum *key )
22 ldbm_datum_init( *cont );
23 cont->dsize = 1 + sizeof(ID) + key->dsize;
24 cont->dptr = ch_malloc( cont->dsize );
26 * (unsigned char *) cont->dptr = SLAP_INDEX_CONT_PREFIX;
28 AC_MEMCPY( &((unsigned char *)cont->dptr)[1 + sizeof(ID)],
29 key->dptr, key->dsize );
32 static void cont_id( Datum *cont, ID id )
36 for( i=1; i <= sizeof(id); i++) {
37 ((unsigned char *)cont->dptr)[i] = (unsigned char)(id & 0xFF);
43 static void cont_free( Datum *cont )
45 ch_free( cont->dptr );
49 static void idl_check(ID_BLOCK *idl)
54 if( ID_BLOCK_INDIRECT(idl) || ID_BLOCK_ALLIDS(idl)
55 || ID_BLOCK_NIDS(idl) <= 1 )
60 for( last = ID_BLOCK_ID(idl, 0), i = 1;
61 i < ID_BLOCK_NIDS(idl);
62 last = ID_BLOCK_ID(idl, i), i++ )
64 assert (last < ID_BLOCK_ID(idl, i) );
69 /* Allocate an ID_BLOCK with room for nids ids */
71 idl_alloc( unsigned int nids )
75 /* nmax + nids + space for the ids */
76 new = (ID_BLOCK *) ch_calloc( (ID_BLOCK_IDS_OFFSET + nids), sizeof(ID) );
77 ID_BLOCK_NMAX(new) = nids;
78 ID_BLOCK_NIDS(new) = 0;
84 /* Allocate an empty ALLIDS ID_BLOCK */
86 idl_allids( Backend *be )
92 ID_BLOCK_NMAX(idl) = ID_BLOCK_ALLIDS_VALUE;
93 if ( next_id_get( be, &id ) ) {
96 ID_BLOCK_NIDS(idl) = id;
101 /* Free an ID_BLOCK */
103 idl_free( ID_BLOCK *idl )
107 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
108 "idl_free: called with NULL pointer\n" ));
110 Debug( LDAP_DEBUG_TRACE,
111 "idl_free: called with NULL pointer\n",
118 free( (char *) idl );
122 /* Fetch an single ID_BLOCK from the cache */
133 /* Debug( LDAP_DEBUG_TRACE, "=> idl_fetch_one\n", 0, 0, 0 ); */
135 data = ldbm_cache_fetch( db, key );
137 if( data.dptr == NULL ) {
141 idl = (ID_BLOCK *) data.dptr;
142 if ( ID_BLOCK_ALLIDS(idl) ) {
143 /* make sure we have the current value of highest id */
144 idl = idl_allids( be );
146 idl = idl_dup((ID_BLOCK *) data.dptr);
149 ldbm_datum_free( db->dbc_db, data );
155 /* Fetch a set of ID_BLOCKs from the cache
157 * if block return is an ALLIDS block,
158 * return an new ALLIDS block
161 * construct super block from all blocks referenced by INDIRECT block
177 idl = idl_fetch_one( be, db, key );
183 if ( ID_BLOCK_ALLIDS(idl) ) {
188 if ( ! ID_BLOCK_INDIRECT( idl ) ) {
194 * this is an indirect block which points to other blocks.
195 * we need to read in all the blocks it points to and construct
196 * a big id list containing all the ids, which we will return.
199 #ifndef USE_INDIRECT_NIDS
200 /* count the number of blocks & allocate space for pointers to them */
201 for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ )
204 i = ID_BLOCK_NIDS(idl);
206 tmp = (ID_BLOCK **) ch_malloc( (i + 1) * sizeof(ID_BLOCK *) );
208 /* read in all the blocks */
209 cont_alloc( &data, &key );
211 #ifndef USE_INDIRECT_NIDS
212 for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ ) {
214 for ( i = 0; i < ID_BLOCK_NIDS(idl); i++ ) {
216 cont_id( &data, ID_BLOCK_ID(idl, i) );
218 if ( (tmp[i] = idl_fetch_one( be, db, data )) == NULL ) {
220 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
221 "idl_fetch: idl_fetch_one returned NULL\n" ));
223 Debug( LDAP_DEBUG_ANY,
224 "idl_fetch: one returned NULL\n", 0, 0, 0 );
230 nids += ID_BLOCK_NIDS(tmp[i]);
236 /* allocate space for the big block */
237 idl = idl_alloc( nids );
238 ID_BLOCK_NIDS(idl) = nids;
241 /* copy in all the ids from the component blocks */
242 for ( i = 0; tmp[i] != NULL; i++ ) {
243 if ( tmp[i] == NULL ) {
248 (char *) &ID_BLOCK_ID(idl, nids),
249 (char *) &ID_BLOCK_ID(tmp[i], 0),
250 ID_BLOCK_NIDS(tmp[i]) * sizeof(ID) );
251 nids += ID_BLOCK_NIDS(tmp[i]);
255 free( (char *) tmp );
257 #ifdef LDBM_DEBUG_IDL
262 LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
263 "idl_fetch: %ld ids (%ld max)\n",
264 ID_BLOCK_NIDS(idl), ID_BLOCK_NMAXN(idl) ));
266 Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %ld ids (%ld max)\n",
267 ID_BLOCK_NIDS(idl), ID_BLOCK_NMAXN(idl), 0 );
274 /* store a single block */
286 #ifdef LDBM_DEBUG_IDL
290 ldbm_datum_init( data );
292 /* Debug( LDAP_DEBUG_TRACE, "=> idl_store\n", 0, 0, 0 ); */
294 data.dptr = (char *) idl;
295 data.dsize = (ID_BLOCK_IDS_OFFSET + ID_BLOCK_NMAXN(idl)) * sizeof(ID);
297 flags = LDBM_REPLACE;
298 rc = ldbm_cache_store( db, key, data, flags );
301 Statslog( LDAP_DEBUG_STATS, "<= idl_store(): rc=%d\n",
305 /* Debug( LDAP_DEBUG_TRACE, "<= idl_store %d\n", rc, 0, 0 ); */
309 /* Binary search for id in block, return index
310 * an index is always returned, even with no match. If no
311 * match, the returned index is the insertion point.
319 int lo=0, hi=ID_BLOCK_NIDS(b)-1, nr=0;
323 nr = ( lo + hi ) / 2;
324 if (ID_BLOCK_ID(b, nr) == id)
326 if (ID_BLOCK_ID(b, nr) > id)
334 /* split the block at id
335 * locate ID greater than or equal to id.
347 /* find where to split the block */
348 nr = idl_find(b, id);
349 if ( ID_BLOCK_ID(b,nr) < id )
352 nl = ID_BLOCK_NIDS(b) - nr;
354 *right = idl_alloc( nr == 0 ? 1 : nr );
355 *left = idl_alloc( nl + (nr == 0 ? 0 : 1));
358 * everything before the id being inserted in the first block
359 * unless there is nothing, in which case the id being inserted
363 ID_BLOCK_NIDS(*right) = 1;
364 ID_BLOCK_ID(*right, 0) = id;
367 (char *) &ID_BLOCK_ID(*right, 0),
368 (char *) &ID_BLOCK_ID(b, 0),
370 ID_BLOCK_NIDS(*right) = nr;
371 ID_BLOCK_ID(*left, 0) = id;
374 /* the id being inserted & everything after in the second block */
376 (char *) &ID_BLOCK_ID(*left, (nr == 0 ? 0 : 1)),
377 (char *) &ID_BLOCK_ID(b, nr),
379 ID_BLOCK_NIDS(*left) = nl + (nr == 0 ? 0 : 1);
381 #ifdef LDBM_DEBUG_IDL
389 * idl_change_first - called when an indirect block's first key has
390 * changed, meaning it needs to be stored under a new key, and the
391 * header block pointing to it needs updating.
397 Datum hkey, /* header block key */
398 ID_BLOCK *h, /* header block */
399 int pos, /* pos in h to update */
400 Datum bkey, /* data block key */
401 ID_BLOCK *b /* data block */
406 /* Debug( LDAP_DEBUG_TRACE, "=> idl_change_first\n", 0, 0, 0 ); */
408 /* delete old key block */
409 if ( (rc = ldbm_cache_delete( db, bkey )) != 0 ) {
411 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
412 "idl_change_first: ldbm_cache_delete returned %d\n", rc ));
414 Debug( LDAP_DEBUG_ANY,
415 "idl_change_first: ldbm_cache_delete returned %d\n",
422 /* write block with new key */
423 cont_id( &bkey, ID_BLOCK_ID(b, 0) );
425 if ( (rc = idl_store( be, db, bkey, b )) != 0 ) {
427 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
428 "idl_change_first: idl_store returned %d\n", rc ));
430 Debug( LDAP_DEBUG_ANY,
431 "idl_change_first: idl_store returned %d\n", rc, 0, 0 );
437 /* update + write indirect header block */
438 ID_BLOCK_ID(h, pos) = ID_BLOCK_ID(b, 0);
439 if ( (rc = idl_store( be, db, hkey, h )) != 0 ) {
441 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
442 "idl_change_first: idl_store returned %s\n", rc ));
444 Debug( LDAP_DEBUG_ANY,
445 "idl_change_first: idl_store returned %d\n", rc, 0, 0 );
463 int i, j, first, rc = 0;
464 ID_BLOCK *idl, *tmp, *tmp2, *tmp3;
467 if ( (idl = idl_fetch_one( be, db, key )) == NULL ) {
468 idl = idl_alloc( 1 );
469 ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)++) = id;
470 rc = idl_store( be, db, key, idl );
476 if ( ID_BLOCK_ALLIDS( idl ) ) {
482 if ( ! ID_BLOCK_INDIRECT( idl ) ) {
484 switch ( idl_insert( &idl, id, db->dbc_maxids ) ) {
485 case 0: /* id inserted - store the updated block */
487 rc = idl_store( be, db, key, idl );
490 case 2: /* id already there - nothing to do */
494 case 3: /* id not inserted - block must be split */
495 /* check threshold for marking this an all-id block */
496 if ( db->dbc_maxindirect < 2 ) {
498 idl = idl_allids( be );
499 rc = idl_store( be, db, key, idl );
503 idl_split_block( idl, id, &tmp, &tmp2 );
506 /* create the header indirect block */
507 #ifndef USE_INDIRECT_NIDS
508 idl = idl_alloc( 3 );
509 ID_BLOCK_NMAX(idl) = 3;
510 ID_BLOCK_NIDS(idl) = ID_BLOCK_INDIRECT_VALUE;
511 ID_BLOCK_ID(idl, 0) = ID_BLOCK_ID(tmp, 0);
512 ID_BLOCK_ID(idl, 1) = ID_BLOCK_ID(tmp2, 0);
513 ID_BLOCK_ID(idl, 2) = NOID;
515 idl = idl_alloc( 2 );
516 ID_BLOCK_NMAX(idl) = 2 | ID_BLOCK_INDIRECT_VALUE;
517 ID_BLOCK_NIDS(idl) = 2;
518 ID_BLOCK_ID(idl, 0) = ID_BLOCK_ID(tmp, 0);
519 ID_BLOCK_ID(idl, 1) = ID_BLOCK_ID(tmp2, 0);
523 rc = idl_store( be, db, key, idl );
525 cont_alloc( &k2, &key );
526 cont_id( &k2, ID_BLOCK_ID(tmp, 0) );
528 rc = idl_store( be, db, k2, tmp );
530 cont_id( &k2, ID_BLOCK_ID(tmp2, 0) );
531 rc = idl_store( be, db, k2, tmp2 );
545 * this is an indirect block which points to other blocks.
546 * we need to read in the block into which the id should be
547 * inserted, then insert the id and store the block. we might
548 * have to split the block if it is full, which means we also
549 * need to write a new "header" block.
552 #ifndef USE_INDIRECT_NIDS
553 /* select the block to try inserting into *//* XXX linear search XXX */
554 for ( i = 0; !ID_BLOCK_NOID(idl, i) && id > ID_BLOCK_ID(idl, i); i++ )
557 i = idl_find(idl, id);
558 if (ID_BLOCK_ID(idl, i) < id)
570 cont_alloc( &k2, &key );
571 cont_id( &k2, ID_BLOCK_ID(idl, i) );
573 if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) {
575 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
576 "idl_insert_key: nonexistent continuation block\n" ));
578 Debug( LDAP_DEBUG_ANY, "idl_insert_key: nonexistent continuation block\n",
588 switch ( idl_insert( &tmp, id, db->dbc_maxids ) ) {
589 case 0: /* id inserted ok */
590 if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) {
592 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
593 "ids_insert_key: idl_store returned %d\n", rc ));
595 Debug( LDAP_DEBUG_ANY,
596 "idl_insert_key: idl_store returned %d\n", rc, 0, 0 );
602 case 1: /* id inserted - first id in block has changed */
604 * key for this block has changed, so we have to
605 * write the block under the new key, delete the
606 * old key block + update and write the indirect
610 rc = idl_change_first( be, db, key, idl, i, k2, tmp );
613 case 2: /* id not inserted - already there, do nothing */
617 case 3: /* id not inserted - block is full */
619 * first, see if it will fit in the next block,
620 * without splitting, unless we're trying to insert
621 * into the beginning of the first block.
624 #ifndef USE_INDIRECT_NIDS
625 /* is there a next block? */
626 if ( !first && !ID_BLOCK_NOID(idl, i + 1) ) {
628 if ( !first && (unsigned long)(i + 1) < ID_BLOCK_NIDS(idl) ) {
631 cont_alloc( &k2, &key );
632 cont_id( &k2, ID_BLOCK_ID(idl, i) );
633 if ( (tmp2 = idl_fetch_one( be, db, k2 )) == NULL ) {
635 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
636 "idl_insert_key: idl_fetch_one returned NULL\n"));
638 Debug( LDAP_DEBUG_ANY,
639 "idl_insert_key: idl_fetch_one returned NULL\n",
643 /* split the original block */
648 /* If the new id is less than the last id in the
649 * current block, it must not be put into the next
650 * block. Push the last id of the current block
651 * into the next block instead.
653 if (id < ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1)) {
654 ID id2 = ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1);
656 --ID_BLOCK_NIDS(tmp);
657 /* This must succeed since we just popped one
658 * ID off the end of it.
660 rc = idl_insert( &tmp, id, db->dbc_maxids );
662 if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) {
664 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
665 "idl_insert_key: idl_store returned %d\n", rc ));
667 Debug( LDAP_DEBUG_ANY,
668 "idl_insert_key: idl_store returned %d\n", rc, 0, 0 );
674 /* This new id will necessarily be inserted
675 * as the first id of the next block by the
676 * following switch() statement.
680 switch ( (rc = idl_insert( &tmp2, id,
681 db->dbc_maxids )) ) {
682 case 1: /* id inserted first in block */
683 rc = idl_change_first( be, db, key, idl,
687 case 2: /* id already there - how? */
688 case 0: /* id inserted: this can never be
689 * the result of idl_insert, because
690 * we guaranteed that idl_change_first
691 * will always be called.
695 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
696 "idl_insert_key: id %ld is already in next block\n",
699 Debug( LDAP_DEBUG_ANY,
700 "idl_insert_key: id %ld already in next block\n",
711 case 3: /* split the original block */
720 * must split the block, write both new blocks + update
721 * and write the indirect header block.
724 rc = 0; /* optimistic */
727 #ifndef USE_INDIRECT_NIDS
728 /* count how many indirect blocks *//* XXX linear count XXX */
729 for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ )
732 j = ID_BLOCK_NIDS(idl);
735 /* check it against all-id thresholed */
736 if ( j + 1 > db->dbc_maxindirect ) {
738 * we've passed the all-id threshold, meaning
739 * that this set of blocks should be replaced
740 * by a single "all-id" block. our job: delete
741 * all the indirect blocks, and replace the header
742 * block by an all-id block.
745 /* delete all indirect blocks */
746 #ifndef USE_INDIRECT_NIDS
747 for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) {
749 for ( j = 0; (unsigned long) j < ID_BLOCK_NIDS(idl); j++ ) {
751 cont_id( &k2, ID_BLOCK_ID(idl, j) );
753 rc = ldbm_cache_delete( db, k2 );
756 /* store allid block in place of header block */
758 idl = idl_allids( be );
759 rc = idl_store( be, db, key, idl );
767 idl_split_block( tmp, id, &tmp2, &tmp3 );
770 /* create a new updated indirect header block */
771 tmp = idl_alloc( ID_BLOCK_NMAXN(idl) + 1 );
772 #ifndef USE_INDIRECT_NIDS
773 ID_BLOCK_NIDS(tmp) = ID_BLOCK_INDIRECT_VALUE;
775 ID_BLOCK_NMAX(tmp) |= ID_BLOCK_INDIRECT_VALUE;
777 /* everything up to the split block */
779 (char *) &ID_BLOCK_ID(tmp, 0),
780 (char *) &ID_BLOCK_ID(idl, 0),
782 /* the two new blocks */
783 ID_BLOCK_ID(tmp, i) = ID_BLOCK_ID(tmp2, 0);
784 ID_BLOCK_ID(tmp, i + 1) = ID_BLOCK_ID(tmp3, 0);
785 /* everything after the split block */
786 #ifndef USE_INDIRECT_NIDS
788 (char *) &ID_BLOCK_ID(tmp, i + 2),
789 (char *) &ID_BLOCK_ID(idl, i + 1),
790 (ID_BLOCK_NMAXN(idl) - i - 1) * sizeof(ID) );
793 (char *) &ID_BLOCK_ID(tmp, i + 2),
794 (char *) &ID_BLOCK_ID(idl, i + 1),
795 (ID_BLOCK_NIDS(idl) - i - 1) * sizeof(ID) );
796 ID_BLOCK_NIDS(tmp) = ID_BLOCK_NIDS(idl) + 1;
799 /* store the header block */
800 rc = idl_store( be, db, key, tmp );
802 /* store the first id block */
803 cont_id( &k2, ID_BLOCK_ID(tmp2, 0) );
804 rc = idl_store( be, db, k2, tmp2 );
806 /* store the second id block */
807 cont_id( &k2, ID_BLOCK_ID(tmp3, 0) );
808 rc = idl_store( be, db, k2, tmp3 );
823 * idl_insert - insert an id into an id list.
827 * 1 id inserted, first id in block has changed
828 * 2 id not inserted, already there
829 * 3 id not inserted, block must be split
832 idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids )
836 if ( ID_BLOCK_ALLIDS( *idl ) ) {
837 return( 2 ); /* already there */
840 /* is it already there? */
841 i = idl_find(*idl, id);
842 if ( ID_BLOCK_ID(*idl, i) == id ) {
843 return( 2 ); /* already there */
845 if ( ID_BLOCK_NIDS(*idl) && ID_BLOCK_ID(*idl, i) < id )
848 /* do we need to make room for it? */
849 if ( ID_BLOCK_NIDS(*idl) == ID_BLOCK_NMAXN(*idl) ) {
850 /* make room or indicate block needs splitting */
851 if ( ID_BLOCK_NMAXN(*idl) >= maxids ) {
852 return( 3 ); /* block needs splitting */
855 ID_BLOCK_NMAX(*idl) *= 2;
856 if ( ID_BLOCK_NMAXN(*idl) > maxids ) {
857 ID_BLOCK_NMAX(*idl) = maxids;
859 *idl = (ID_BLOCK *) ch_realloc( (char *) *idl,
860 (ID_BLOCK_NMAXN(*idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
863 /* make a slot for the new id */
864 AC_MEMCPY( &ID_BLOCK_ID(*idl, i+1), &ID_BLOCK_ID(*idl, i),
865 (ID_BLOCK_NIDS(*idl) - i) * sizeof(ID) );
867 ID_BLOCK_ID(*idl, i) = id;
868 ID_BLOCK_NIDS(*idl)++;
870 (char *) &ID_BLOCK_ID((*idl), ID_BLOCK_NIDS(*idl)),
872 (ID_BLOCK_NMAXN(*idl) - ID_BLOCK_NIDS(*idl)) * sizeof(ID) );
874 #ifdef LDBM_DEBUG_IDL
878 return( i == 0 ? 1 : 0 ); /* inserted - first id changed or not */
895 if ( (idl = idl_fetch_one( be, db, key ) ) == NULL )
897 /* It wasn't found. Hmm... */
901 if ( ID_BLOCK_ALLIDS( idl ) ) {
906 if ( ! ID_BLOCK_INDIRECT( idl ) ) {
907 i = idl_find(idl, id);
908 if ( ID_BLOCK_ID(idl, i) == id ) {
909 if( --ID_BLOCK_NIDS(idl) == 0 ) {
910 ldbm_cache_delete( db, key );
914 &ID_BLOCK_ID(idl, i),
915 &ID_BLOCK_ID(idl, i+1),
916 (ID_BLOCK_NIDS(idl)-i) * sizeof(ID) );
918 ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID;
920 idl_store( be, db, key, idl );
926 /* We didn't find the ID. Hmmm... */
931 /* We have to go through an indirect block and find the ID
934 cont_alloc( &data, &key );
935 #ifndef USE_INDIRECT_NIDS
936 for ( nids = 0; !ID_BLOCK_NOID(idl, nids); nids++ )
939 for ( j = 0; j<nids; j++ )
941 nids = ID_BLOCK_NIDS(idl);
942 for ( j = idl_find(idl, id); j >= 0; j = -1) /* execute once */
946 cont_id( &data, ID_BLOCK_ID(idl, j) );
948 if ( (tmp = idl_fetch_one( be, db, data )) == NULL ) {
950 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
951 "idl_delete_key: idl_fetch_one returned NULL\n" ));
953 Debug( LDAP_DEBUG_ANY,
954 "idl_delete_key: idl_fetch of returned NULL\n", 0, 0, 0 );
960 Now try to find the ID in tmp
963 i = idl_find(tmp, id);
964 if ( ID_BLOCK_ID(tmp, i) == id )
967 &ID_BLOCK_ID(tmp, i),
968 &ID_BLOCK_ID(tmp, i+1),
969 (ID_BLOCK_NIDS(tmp)-(i+1)) * sizeof(ID));
970 ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp)-1 ) = NOID;
971 ID_BLOCK_NIDS(tmp)--;
973 if ( ID_BLOCK_NIDS(tmp) ) {
974 idl_store ( be, db, data, tmp );
977 ldbm_cache_delete( db, data );
979 &ID_BLOCK_ID(idl, j),
980 &ID_BLOCK_ID(idl, j+1),
981 (nids-(j+1)) * sizeof(ID));
982 ID_BLOCK_ID(idl, nids-1) = NOID;
984 #ifdef USE_INDIRECT_NIDS
985 ID_BLOCK_NIDS(idl)--;
988 ldbm_cache_delete( db, key );
990 idl_store( be, db, key, idl );
1006 /* return a duplicate of a single ID_BLOCK */
1008 idl_dup( ID_BLOCK *idl )
1012 if ( idl == NULL ) {
1016 new = idl_alloc( ID_BLOCK_NMAXN(idl) );
1021 (ID_BLOCK_NMAXN(idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
1023 #ifdef LDBM_DEBUG_IDL
1031 /* return the smaller ID_BLOCK */
1033 idl_min( ID_BLOCK *a, ID_BLOCK *b )
1035 return( ID_BLOCK_NIDS(a) > ID_BLOCK_NIDS(b) ? b : a );
1040 * idl_intersection - return a intersection b
1049 unsigned int ai, bi, ni;
1052 if ( a == NULL || b == NULL ) {
1055 if ( ID_BLOCK_ALLIDS( a ) ) {
1056 return( idl_dup( b ) );
1058 if ( ID_BLOCK_ALLIDS( b ) ) {
1059 return( idl_dup( a ) );
1062 n = idl_dup( idl_min( a, b ) );
1064 #ifdef LDBM_DEBUG_IDL
1069 for ( ni = 0, ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
1071 bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
1077 if ( bi == ID_BLOCK_NIDS(b) ) {
1081 if ( ID_BLOCK_ID(b, bi) == ID_BLOCK_ID(a, ai) ) {
1082 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1090 ID_BLOCK_NIDS(n) = ni;
1092 #ifdef LDBM_DEBUG_IDL
1101 * idl_union - return a union b
1110 unsigned int ai, bi, ni;
1114 return( idl_dup( b ) );
1117 return( idl_dup( a ) );
1119 if ( ID_BLOCK_ALLIDS( a ) || ID_BLOCK_ALLIDS( b ) ) {
1120 return( idl_allids( be ) );
1123 #ifdef LDBM_DEBUG_IDL
1128 if ( ID_BLOCK_NIDS(b) < ID_BLOCK_NIDS(a) ) {
1134 n = idl_alloc( ID_BLOCK_NIDS(a) + ID_BLOCK_NIDS(b) );
1136 for ( ni = 0, ai = 0, bi = 0;
1137 ai < ID_BLOCK_NIDS(a) && bi < ID_BLOCK_NIDS(b);
1140 if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) {
1141 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai++);
1143 } else if ( ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai) ) {
1144 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi++);
1147 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1152 for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
1153 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1155 for ( ; bi < ID_BLOCK_NIDS(b); bi++ ) {
1156 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi);
1158 ID_BLOCK_NIDS(n) = ni;
1160 #ifdef LDBM_DEBUG_IDL
1169 * idl_notin - return a intersection ~b (or a minus b)
1178 unsigned int ni, ai, bi;
1184 if ( b == NULL || ID_BLOCK_ALLIDS( b )) {
1185 return( idl_dup( a ) );
1188 if ( ID_BLOCK_ALLIDS( a ) ) {
1189 n = idl_alloc( SLAPD_LDBM_MIN_MAXIDS );
1192 for ( ai = 1, bi = 0;
1193 ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAXN(n) && bi < ID_BLOCK_NMAXN(b);
1196 if ( ID_BLOCK_ID(b, bi) == ai ) {
1199 ID_BLOCK_ID(n, ni++) = ai;
1203 for ( ; ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAXN(n); ai++ ) {
1204 ID_BLOCK_ID(n, ni++) = ai;
1207 if ( ni == ID_BLOCK_NMAXN(n) ) {
1209 return( idl_allids( be ) );
1211 ID_BLOCK_NIDS(n) = ni;
1219 for ( ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
1221 bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
1227 if ( bi == ID_BLOCK_NIDS(b) ) {
1231 if ( ID_BLOCK_ID(b, bi) != ID_BLOCK_ID(a, ai) ) {
1232 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1236 for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
1237 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1239 ID_BLOCK_NIDS(n) = ni;
1241 #ifdef LDBM_DEBUG_IDL
1248 /* return the first ID in the block
1251 * otherwise return NOID
1252 * otherwise return first ID
1254 * cursor is set to 1
1257 idl_firstid( ID_BLOCK *idl, ID *cursor )
1261 if ( idl == NULL || ID_BLOCK_NIDS(idl) == 0 ) {
1265 if ( ID_BLOCK_ALLIDS( idl ) ) {
1266 return( ID_BLOCK_NIDS(idl) > 1 ? 1 : NOID );
1269 return( ID_BLOCK_ID(idl, 0) );
1273 * if ALLIDS block, cursor is id.
1275 * if id < NIDS return id
1277 * otherwise cursor is index into block
1279 * return id at index then increment
1282 idl_nextid( ID_BLOCK *idl, ID *cursor )
1284 if ( ID_BLOCK_ALLIDS( idl ) ) {
1285 if( ++(*cursor) < ID_BLOCK_NIDS(idl) ) {
1292 if ( *cursor < ID_BLOCK_NIDS(idl) ) {
1293 return( ID_BLOCK_ID(idl, (*cursor)++) );