X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=servers%2Fslapd%2Fback-ldbm%2Fidl.c;h=a070f46adf399002cb42b59d386bad7cc9bb4f01;hb=9fc4a749dcecda7176cea4859fa8f51bbc91feff;hp=7d18956361435b776a8467c62ff17ab0284e9684;hpb=a56c161bdbc1443808039d0eaf9b84474a243352;p=openldap diff --git a/servers/slapd/back-ldbm/idl.c b/servers/slapd/back-ldbm/idl.c index 7d18956361..a070f46adf 100644 --- a/servers/slapd/back-ldbm/idl.c +++ b/servers/slapd/back-ldbm/idl.c @@ -1,7 +1,7 @@ /* idl.c - ldap id list handling routines */ /* $OpenLDAP$ */ /* - * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved. + * Copyright 1998-2002 The OpenLDAP Foundation, All Rights Reserved. * COPYING RESTRICTIONS APPLY, see COPYRIGHT file */ @@ -17,31 +17,54 @@ static ID_BLOCK* idl_dup( ID_BLOCK *idl ); -static void cont_alloc( Datum cont, Datum key ) +static void cont_alloc( Datum *cont, Datum *key ) { - ldbm_datum_init( cont ); - cont.dsize = 1 + sizeof(ID) + key.dsize; - cont.dptr = ch_malloc( cont.dsize ); + ldbm_datum_init( *cont ); + cont->dsize = 1 + sizeof(ID) + key->dsize; + cont->dptr = ch_malloc( cont->dsize ); - memcpy( &((unsigned char *)cont.dptr)[1 + sizeof(ID)], - key.dptr, key.dsize ); + * (unsigned char *) cont->dptr = SLAP_INDEX_CONT_PREFIX; + + AC_MEMCPY( &((unsigned char *)cont->dptr)[1 + sizeof(ID)], + key->dptr, key->dsize ); } -static void cont_id( Datum cont, ID id ) +static void cont_id( Datum *cont, ID id ) { - int i; + unsigned int i; for( i=1; i <= sizeof(id); i++) { - ((unsigned char *)cont.dptr)[i] = (unsigned char)(id & 0xFF); + ((unsigned char *)cont->dptr)[i] = (unsigned char)(id & 0xFF); id >>= 8; } } -static void cont_free( Datum cont ) +static void cont_free( Datum *cont ) +{ + ch_free( cont->dptr ); +} + +#ifdef LDBM_DEBUG_IDL +static void idl_check(ID_BLOCK *idl) { - ch_free( cont.dptr ); + int i; + ID_BLOCK last; + + if( ID_BLOCK_INDIRECT(idl) || ID_BLOCK_ALLIDS(idl) + || ID_BLOCK_NIDS(idl) <= 1 ) + { + return; + } + + for( last = ID_BLOCK_ID(idl, 0), i = 1; + i < ID_BLOCK_NIDS(idl); + last = ID_BLOCK_ID(idl, i), i++ ) + { + assert (last < ID_BLOCK_ID(idl, i) ); + } } +#endif /* Allocate an ID_BLOCK with room for nids ids */ ID_BLOCK * @@ -63,10 +86,14 @@ ID_BLOCK * idl_allids( Backend *be ) { ID_BLOCK *idl; + ID id; idl = idl_alloc( 0 ); ID_BLOCK_NMAX(idl) = ID_BLOCK_ALLIDS_VALUE; - ID_BLOCK_NIDS(idl) = next_id_get( be ); + if ( next_id_get( be, &id ) ) { + return NULL; + } + ID_BLOCK_NIDS(idl) = id; return( idl ); } @@ -76,9 +103,14 @@ void idl_free( ID_BLOCK *idl ) { if ( idl == NULL ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, INFO, "idl_free: called with NULL pointer\n" , 0,0,0); +#else Debug( LDAP_DEBUG_TRACE, "idl_free: called with NULL pointer\n", 0, 0, 0 ); +#endif + return; } @@ -105,7 +137,13 @@ idl_fetch_one( return NULL; } - idl = idl_dup((ID_BLOCK *) data.dptr); + idl = (ID_BLOCK *) data.dptr; + if ( ID_BLOCK_ALLIDS(idl) ) { + /* make sure we have the current value of highest id */ + idl = idl_allids( be ); + } else { + idl = idl_dup((ID_BLOCK *) data.dptr); + } ldbm_datum_free( db->dbc_db, data ); @@ -115,9 +153,9 @@ idl_fetch_one( /* Fetch a set of ID_BLOCKs from the cache * if not INDIRECT - * if block return is an ALLIDS block, + * if block return is an ALLIDS block, * return an new ALLIDS block - * otherwise + * otherwise * return block * construct super block from all blocks referenced by INDIRECT block * return super block @@ -132,7 +170,8 @@ idl_fetch( Datum data; ID_BLOCK *idl; ID_BLOCK **tmp; - int i, nids; + int nids; + unsigned i; idl = idl_fetch_one( be, db, key ); @@ -142,10 +181,6 @@ idl_fetch( if ( ID_BLOCK_ALLIDS(idl) ) { /* all ids block */ - /* make sure we have the current value of highest id */ - idl_free( idl ); - idl = idl_allids( be ); - return( idl ); } @@ -160,27 +195,41 @@ idl_fetch( * a big id list containing all the ids, which we will return. */ +#ifndef USE_INDIRECT_NIDS /* count the number of blocks & allocate space for pointers to them */ for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ ) ; /* NULL */ +#else + i = ID_BLOCK_NIDS(idl); +#endif tmp = (ID_BLOCK **) ch_malloc( (i + 1) * sizeof(ID_BLOCK *) ); /* read in all the blocks */ - cont_alloc( data, key ); + cont_alloc( &data, &key ); nids = 0; +#ifndef USE_INDIRECT_NIDS for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ ) { - cont_id( data, ID_BLOCK_ID(idl, i) ); +#else + for ( i = 0; i < ID_BLOCK_NIDS(idl); i++ ) { +#endif + cont_id( &data, ID_BLOCK_ID(idl, i) ); if ( (tmp[i] = idl_fetch_one( be, db, data )) == NULL ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, INFO, + "idl_fetch: idl_fetch_one returned NULL\n", 0,0,0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_fetch: one returned NULL\n", 0, 0, 0 ); +#endif + continue; } nids += ID_BLOCK_NIDS(tmp[i]); } tmp[i] = NULL; - cont_free( data ); + cont_free( &data ); idl_free( idl ); /* allocate space for the big block */ @@ -194,7 +243,7 @@ idl_fetch( continue; } - SAFEMEMCPY( + AC_MEMCPY( (char *) &ID_BLOCK_ID(idl, nids), (char *) &ID_BLOCK_ID(tmp[i], 0), ID_BLOCK_NIDS(tmp[i]) * sizeof(ID) ); @@ -204,8 +253,19 @@ idl_fetch( } free( (char *) tmp ); +#ifdef LDBM_DEBUG_IDL + idl_check(idl); +#endif + +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, ENTRY, + "idl_fetch: %ld ids (%ld max)\n", + ID_BLOCK_NIDS(idl), ID_BLOCK_NMAXN(idl), 0 ); +#else Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %ld ids (%ld max)\n", - ID_BLOCK_NIDS(idl), ID_BLOCK_NMAX(idl), 0 ); + ID_BLOCK_NIDS(idl), ID_BLOCK_NMAXN(idl), 0 ); +#endif + return( idl ); } @@ -221,27 +281,55 @@ idl_store( { int rc, flags; Datum data; - struct ldbminfo *li = (struct ldbminfo *) be->be_private; + +#ifdef LDBM_DEBUG_IDL + idl_check(idl); +#endif ldbm_datum_init( data ); /* Debug( LDAP_DEBUG_TRACE, "=> idl_store\n", 0, 0, 0 ); */ data.dptr = (char *) idl; - data.dsize = (ID_BLOCK_IDS_OFFSET + ID_BLOCK_NMAX(idl)) * sizeof(ID); + data.dsize = (ID_BLOCK_IDS_OFFSET + ID_BLOCK_NMAXN(idl)) * sizeof(ID); + flags = LDBM_REPLACE; + rc = ldbm_cache_store( db, key, data, flags ); + #ifdef LDBM_DEBUG Statslog( LDAP_DEBUG_STATS, "<= idl_store(): rc=%d\n", rc, 0, 0, 0, 0 ); #endif - flags = LDBM_REPLACE; - rc = ldbm_cache_store( db, key, data, flags ); - /* Debug( LDAP_DEBUG_TRACE, "<= idl_store %d\n", rc, 0, 0 ); */ return( rc ); } +/* Binary search for id in block, return index + * an index is always returned, even with no match. If no + * match, the returned index is the insertion point. + */ +static unsigned int +idl_find( + ID_BLOCK *b, + ID id +) +{ + int lo=0, hi=ID_BLOCK_NIDS(b)-1, nr=0; + + for (;lo<=hi;) + { + nr = ( lo + hi ) / 2; + if (ID_BLOCK_ID(b, nr) == id) + break; + if (ID_BLOCK_ID(b, nr) > id) + hi = nr - 1; + else + lo = nr + 1; + } + return nr; +} + /* split the block at id * locate ID greater than or equal to id. */ @@ -255,9 +343,10 @@ idl_split_block( { unsigned int nr, nl; - /* find where to split the block *//* XXX linear search XXX */ - for ( nr = 0; nr < ID_BLOCK_NIDS(b) && id > ID_BLOCK_ID(b, nr); nr++ ) - ; /* NULL */ + /* find where to split the block */ + nr = idl_find(b, id); + if ( ID_BLOCK_ID(b,nr) < id ) + nr++; nl = ID_BLOCK_NIDS(b) - nr; @@ -273,7 +362,7 @@ idl_split_block( ID_BLOCK_NIDS(*right) = 1; ID_BLOCK_ID(*right, 0) = id; } else { - SAFEMEMCPY( + AC_MEMCPY( (char *) &ID_BLOCK_ID(*right, 0), (char *) &ID_BLOCK_ID(b, 0), nr * sizeof(ID) ); @@ -282,11 +371,16 @@ idl_split_block( } /* the id being inserted & everything after in the second block */ - SAFEMEMCPY( + AC_MEMCPY( (char *) &ID_BLOCK_ID(*left, (nr == 0 ? 0 : 1)), (char *) &ID_BLOCK_ID(b, nr), nl * sizeof(ID) ); ID_BLOCK_NIDS(*left) = nl + (nr == 0 ? 0 : 1); + +#ifdef LDBM_DEBUG_IDL + idl_check(*right); + idl_check(*left); +#endif } @@ -300,10 +394,10 @@ idl_change_first( Backend *be, DBCache *db, Datum hkey, /* header block key */ - ID_BLOCK *h, /* header block */ + ID_BLOCK *h, /* header block */ int pos, /* pos in h to update */ Datum bkey, /* data block key */ - ID_BLOCK *b /* data block */ + ID_BLOCK *b /* data block */ ) { int rc; @@ -312,26 +406,44 @@ idl_change_first( /* delete old key block */ if ( (rc = ldbm_cache_delete( db, bkey )) != 0 ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, INFO, + "idl_change_first: ldbm_cache_delete returned %d\n", rc, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_change_first: ldbm_cache_delete returned %d\n", rc, 0, 0 ); +#endif + return( rc ); } /* write block with new key */ - cont_id( bkey, ID_BLOCK_ID(b, 0) ); + cont_id( &bkey, ID_BLOCK_ID(b, 0) ); if ( (rc = idl_store( be, db, bkey, b )) != 0 ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, INFO, + "idl_change_first: idl_store returned %d\n", rc, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_change_first: idl_store returned %d\n", rc, 0, 0 ); +#endif + return( rc ); } /* update + write indirect header block */ ID_BLOCK_ID(h, pos) = ID_BLOCK_ID(b, 0); if ( (rc = idl_store( be, db, hkey, h )) != 0 ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, INFO, + "idl_change_first: idl_store returned %s\n", rc, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_change_first: idl_store returned %d\n", rc, 0, 0 ); +#endif + return( rc ); } @@ -347,7 +459,7 @@ idl_insert_key( ID id ) { - int i, j, first, rc; + int i, j, first, rc = 0; ID_BLOCK *idl, *tmp, *tmp2, *tmp3; Datum k2; @@ -391,25 +503,33 @@ idl_insert_key( idl_free( idl ); /* create the header indirect block */ +#ifndef USE_INDIRECT_NIDS idl = idl_alloc( 3 ); ID_BLOCK_NMAX(idl) = 3; ID_BLOCK_NIDS(idl) = ID_BLOCK_INDIRECT_VALUE; ID_BLOCK_ID(idl, 0) = ID_BLOCK_ID(tmp, 0); ID_BLOCK_ID(idl, 1) = ID_BLOCK_ID(tmp2, 0); ID_BLOCK_ID(idl, 2) = NOID; +#else + idl = idl_alloc( 2 ); + ID_BLOCK_NMAX(idl) = 2 | ID_BLOCK_INDIRECT_VALUE; + ID_BLOCK_NIDS(idl) = 2; + ID_BLOCK_ID(idl, 0) = ID_BLOCK_ID(tmp, 0); + ID_BLOCK_ID(idl, 1) = ID_BLOCK_ID(tmp2, 0); +#endif /* store it */ rc = idl_store( be, db, key, idl ); - cont_alloc( k2, key ); - cont_id( k2, ID_BLOCK_ID(tmp, 0) ); + cont_alloc( &k2, &key ); + cont_id( &k2, ID_BLOCK_ID(tmp, 0) ); rc = idl_store( be, db, k2, tmp ); - cont_id( k2, ID_BLOCK_ID(tmp2, 0) ); + cont_id( &k2, ID_BLOCK_ID(tmp2, 0) ); rc = idl_store( be, db, k2, tmp2 ); - cont_free( k2 ); + cont_free( &k2 ); idl_free( tmp ); idl_free( tmp2 ); @@ -428,9 +548,15 @@ idl_insert_key( * need to write a new "header" block. */ +#ifndef USE_INDIRECT_NIDS /* select the block to try inserting into *//* XXX linear search XXX */ for ( i = 0; !ID_BLOCK_NOID(idl, i) && id > ID_BLOCK_ID(idl, i); i++ ) ; /* NULL */ +#else + i = idl_find(idl, id); + if (ID_BLOCK_ID(idl, i) < id) + i++; +#endif if ( i != 0 ) { i--; @@ -440,13 +566,19 @@ idl_insert_key( } /* get the block */ - cont_alloc( k2, key ); - cont_id( k2, ID_BLOCK_ID(idl, i) ); + cont_alloc( &k2, &key ); + cont_id( &k2, ID_BLOCK_ID(idl, i) ); if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, ERR, + "idl_insert_key: nonexistent continuation block\n", 0, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_insert_key: nonexistent continuation block\n", 0, 0, 0 ); - cont_free( k2 ); +#endif + + cont_free( &k2 ); idl_free( idl ); return( -1 ); } @@ -455,8 +587,14 @@ idl_insert_key( switch ( idl_insert( &tmp, id, db->dbc_maxids ) ) { case 0: /* id inserted ok */ if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, ERR, + "ids_insert_key: idl_store returned %d\n", rc, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_insert_key: idl_store returned %d\n", rc, 0, 0 ); +#endif + } break; @@ -482,17 +620,27 @@ idl_insert_key( * into the beginning of the first block. */ +#ifndef USE_INDIRECT_NIDS /* is there a next block? */ if ( !first && !ID_BLOCK_NOID(idl, i + 1) ) { +#else + if ( !first && (unsigned long)(i + 1) < ID_BLOCK_NIDS(idl) ) { +#endif /* read it in */ - cont_alloc( k2, key ); - cont_id( k2, ID_BLOCK_ID(idl, i) ); + cont_alloc( &k2, &key ); + cont_id( &k2, ID_BLOCK_ID(idl, i) ); if ( (tmp2 = idl_fetch_one( be, db, k2 )) == NULL ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, ERR, + "idl_insert_key: idl_fetch_one returned NULL\n", 0, 0, 0); +#else Debug( LDAP_DEBUG_ANY, "idl_insert_key: idl_fetch_one returned NULL\n", 0, 0, 0 ); +#endif + /* split the original block */ - cont_free( k2 ); + cont_free( &k2 ); goto split; } @@ -503,9 +651,6 @@ idl_insert_key( */ if (id < ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1)) { ID id2 = ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1); - Datum k3; - - ldbm_datum_init( k3 ); --ID_BLOCK_NIDS(tmp); /* This must succeed since we just popped one @@ -513,15 +658,16 @@ idl_insert_key( */ rc = idl_insert( &tmp, id, db->dbc_maxids ); - k3.dptr = ch_malloc(k2.dsize); - k3.dsize = k2.dsize; - memcpy(k3.dptr, k2.dptr, k3.dsize); - if ( (rc = idl_store( be, db, k3, tmp )) != 0 ) { + if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, ERR, + "idl_insert_key: idl_store returned %d\n", rc, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_insert_key: idl_store returned %d\n", rc, 0, 0 ); - } +#endif - free( k3.dptr ); + } id = id2; /* This new id will necessarily be inserted @@ -544,12 +690,18 @@ idl_insert_key( * will always be called. */ if ( rc == 2 ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, INFO, + "idl_insert_key: id %ld is already in next block\n", + id, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_insert_key: id %ld already in next block\n", id, 0, 0 ); +#endif + } - assert( 0 ); /* not yet implemented */ idl_free( tmp ); idl_free( tmp2 ); idl_free( idl ); @@ -571,23 +723,31 @@ split: rc = 0; /* optimistic */ +#ifndef USE_INDIRECT_NIDS /* count how many indirect blocks *//* XXX linear count XXX */ for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) ; /* NULL */ +#else + j = ID_BLOCK_NIDS(idl); +#endif /* check it against all-id thresholed */ if ( j + 1 > db->dbc_maxindirect ) { /* * we've passed the all-id threshold, meaning * that this set of blocks should be replaced - * by a single "all-id" block. our job: delete + * by a single "all-id" block. our job: delete * all the indirect blocks, and replace the header * block by an all-id block. */ /* delete all indirect blocks */ +#ifndef USE_INDIRECT_NIDS for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) { - cont_id( k2, ID_BLOCK_ID(idl, j) ); +#else + for ( j = 0; (unsigned long) j < ID_BLOCK_NIDS(idl); j++ ) { +#endif + cont_id( &k2, ID_BLOCK_ID(idl, j) ); rc = ldbm_cache_delete( db, k2 ); } @@ -597,7 +757,7 @@ split: idl = idl_allids( be ); rc = idl_store( be, db, key, idl ); - cont_free( k2 ); + cont_free( &k2 ); idl_free( idl ); idl_free( tmp ); return( rc ); @@ -607,10 +767,14 @@ split: idl_free( tmp ); /* create a new updated indirect header block */ - tmp = idl_alloc( ID_BLOCK_NMAX(idl) + 1 ); + tmp = idl_alloc( ID_BLOCK_NMAXN(idl) + 1 ); +#ifndef USE_INDIRECT_NIDS ID_BLOCK_NIDS(tmp) = ID_BLOCK_INDIRECT_VALUE; +#else + ID_BLOCK_NMAX(tmp) |= ID_BLOCK_INDIRECT_VALUE; +#endif /* everything up to the split block */ - SAFEMEMCPY( + AC_MEMCPY( (char *) &ID_BLOCK_ID(tmp, 0), (char *) &ID_BLOCK_ID(idl, 0), i * sizeof(ID) ); @@ -618,20 +782,28 @@ split: ID_BLOCK_ID(tmp, i) = ID_BLOCK_ID(tmp2, 0); ID_BLOCK_ID(tmp, i + 1) = ID_BLOCK_ID(tmp3, 0); /* everything after the split block */ - SAFEMEMCPY( +#ifndef USE_INDIRECT_NIDS + AC_MEMCPY( (char *) &ID_BLOCK_ID(tmp, i + 2), (char *) &ID_BLOCK_ID(idl, i + 1), - (ID_BLOCK_NMAX(idl) - i - 1) * sizeof(ID) ); + (ID_BLOCK_NMAXN(idl) - i - 1) * sizeof(ID) ); +#else + AC_MEMCPY( + (char *) &ID_BLOCK_ID(tmp, i + 2), + (char *) &ID_BLOCK_ID(idl, i + 1), + (ID_BLOCK_NIDS(idl) - i - 1) * sizeof(ID) ); + ID_BLOCK_NIDS(tmp) = ID_BLOCK_NIDS(idl) + 1; +#endif /* store the header block */ rc = idl_store( be, db, key, tmp ); /* store the first id block */ - cont_id( k2, ID_BLOCK_ID(tmp2, 0) ); + cont_id( &k2, ID_BLOCK_ID(tmp2, 0) ); rc = idl_store( be, db, k2, tmp2 ); /* store the second id block */ - cont_id( k2, ID_BLOCK_ID(tmp3, 0) ); + cont_id( &k2, ID_BLOCK_ID(tmp3, 0) ); rc = idl_store( be, db, k2, tmp3 ); idl_free( tmp2 ); @@ -639,7 +811,7 @@ split: break; } - cont_free( k2 ); + cont_free( &k2 ); idl_free( tmp ); idl_free( idl ); return( rc ); @@ -650,7 +822,7 @@ split: * idl_insert - insert an id into an id list. * * returns - * 0 id inserted + * 0 id inserted * 1 id inserted, first id in block has changed * 2 id not inserted, already there * 3 id not inserted, block must be split @@ -664,39 +836,43 @@ idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids ) return( 2 ); /* already there */ } - /* is it already there? *//* XXX linear search XXX */ - for ( i = 0; i < ID_BLOCK_NIDS(*idl) && id > ID_BLOCK_ID(*idl, i); i++ ) { - ; /* NULL */ - } - if ( i < ID_BLOCK_NIDS(*idl) && ID_BLOCK_ID(*idl, i) == id ) { + /* is it already there? */ + i = idl_find(*idl, id); + if ( ID_BLOCK_ID(*idl, i) == id ) { return( 2 ); /* already there */ } + if ( ID_BLOCK_NIDS(*idl) && ID_BLOCK_ID(*idl, i) < id ) + i++; /* do we need to make room for it? */ - if ( ID_BLOCK_NIDS(*idl) == ID_BLOCK_NMAX(*idl) ) { + if ( ID_BLOCK_NIDS(*idl) == ID_BLOCK_NMAXN(*idl) ) { /* make room or indicate block needs splitting */ - if ( ID_BLOCK_NMAX(*idl) >= maxids ) { + if ( ID_BLOCK_NMAXN(*idl) >= maxids ) { return( 3 ); /* block needs splitting */ } ID_BLOCK_NMAX(*idl) *= 2; - if ( ID_BLOCK_NMAX(*idl) > maxids ) { + if ( ID_BLOCK_NMAXN(*idl) > maxids ) { ID_BLOCK_NMAX(*idl) = maxids; } *idl = (ID_BLOCK *) ch_realloc( (char *) *idl, - (ID_BLOCK_NMAX(*idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) ); + (ID_BLOCK_NMAXN(*idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) ); } /* make a slot for the new id */ - SAFEMEMCPY( &ID_BLOCK_ID(*idl, i+1), &ID_BLOCK_ID(*idl, i), - (ID_BLOCK_NIDS(*idl) - i) * sizeof(ID) ); + AC_MEMCPY( &ID_BLOCK_ID(*idl, i+1), &ID_BLOCK_ID(*idl, i), + (ID_BLOCK_NIDS(*idl) - i) * sizeof(ID) ); ID_BLOCK_ID(*idl, i) = id; ID_BLOCK_NIDS(*idl)++; (void) memset( (char *) &ID_BLOCK_ID((*idl), ID_BLOCK_NIDS(*idl)), '\0', - (ID_BLOCK_NMAX(*idl) - ID_BLOCK_NIDS(*idl)) * sizeof(ID) ); + (ID_BLOCK_NMAXN(*idl) - ID_BLOCK_NIDS(*idl)) * sizeof(ID) ); + +#ifdef LDBM_DEBUG_IDL + idl_check(*idl); +#endif return( i == 0 ? 1 : 0 ); /* inserted - first id changed or not */ } @@ -704,10 +880,10 @@ idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids ) int idl_delete_key ( - Backend *be, - DBCache *db, - Datum key, - ID id + Backend *be, + DBCache *db, + Datum key, + ID id ) { Datum data; @@ -727,27 +903,26 @@ idl_delete_key ( } if ( ! ID_BLOCK_INDIRECT( idl ) ) { - for ( i=0; i < ID_BLOCK_NIDS(idl); i++ ) { - if ( ID_BLOCK_ID(idl, i) == id ) { - if( --ID_BLOCK_NIDS(idl) == 0 ) { - ldbm_cache_delete( db, key ); - - } else { - SAFEMEMCPY ( - &ID_BLOCK_ID(idl, i), - &ID_BLOCK_ID(idl, i+1), - (ID_BLOCK_NIDS(idl)-i) * sizeof(ID) ); + i = idl_find(idl, id); + if ( ID_BLOCK_ID(idl, i) == id ) { + if( --ID_BLOCK_NIDS(idl) == 0 ) { + ldbm_cache_delete( db, key ); - ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID; + } else { + AC_MEMCPY( + &ID_BLOCK_ID(idl, i), + &ID_BLOCK_ID(idl, i+1), + (ID_BLOCK_NIDS(idl)-i) * sizeof(ID) ); - idl_store( be, db, key, idl ); - } + ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID; - idl_free( idl ); - return 0; + idl_store( be, db, key, idl ); } - /* We didn't find the ID. Hmmm... */ + + idl_free( idl ); + return 0; } + /* We didn't find the ID. Hmmm... */ idl_free( idl ); return -1; } @@ -755,61 +930,73 @@ idl_delete_key ( /* We have to go through an indirect block and find the ID in the list of IDL's */ + cont_alloc( &data, &key ); +#ifndef USE_INDIRECT_NIDS for ( nids = 0; !ID_BLOCK_NOID(idl, nids); nids++ ) ; /* NULL */ - cont_alloc( data, key ); - - for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) + for ( j = 0; j= 0; j = -1) /* execute once */ +#endif { ID_BLOCK *tmp; - cont_id( data, ID_BLOCK_ID(idl, j) ); + cont_id( &data, ID_BLOCK_ID(idl, j) ); if ( (tmp = idl_fetch_one( be, db, data )) == NULL ) { +#ifdef NEW_LOGGING + LDAP_LOG( INDEX, INFO, + "idl_delete_key: idl_fetch_one returned NULL\n", 0, 0, 0 ); +#else Debug( LDAP_DEBUG_ANY, "idl_delete_key: idl_fetch of returned NULL\n", 0, 0, 0 ); +#endif + continue; } /* Now try to find the ID in tmp */ - for ( i=0; i < ID_BLOCK_NIDS(tmp); i++ ) + + i = idl_find(tmp, id); + if ( ID_BLOCK_ID(tmp, i) == id ) { - if ( ID_BLOCK_ID(tmp, i) == id ) - { - SAFEMEMCPY( - &ID_BLOCK_ID(tmp, i), - &ID_BLOCK_ID(tmp, i+1), - (ID_BLOCK_NIDS(tmp)-(i+1)) * sizeof(ID)); - ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp)-1 ) = NOID; - ID_BLOCK_NIDS(tmp)--; - - if ( ID_BLOCK_NIDS(tmp) ) { - idl_store ( be, db, data, tmp ); - - } else { - ldbm_cache_delete( db, data ); - SAFEMEMCPY( - &ID_BLOCK_ID(idl, j), - &ID_BLOCK_ID(idl, j+1), - (nids-(j+1)) * sizeof(ID)); - ID_BLOCK_ID(idl, nids-1) = NOID; - nids--; - if ( ! nids ) - ldbm_cache_delete( db, key ); - else - idl_store( be, db, key, idl ); - } - idl_free( tmp ); - cont_free( data ); - idl_free( idl ); - return 0; + AC_MEMCPY( + &ID_BLOCK_ID(tmp, i), + &ID_BLOCK_ID(tmp, i+1), + (ID_BLOCK_NIDS(tmp)-(i+1)) * sizeof(ID)); + ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp)-1 ) = NOID; + ID_BLOCK_NIDS(tmp)--; + + if ( ID_BLOCK_NIDS(tmp) ) { + idl_store ( be, db, data, tmp ); + + } else { + ldbm_cache_delete( db, data ); + AC_MEMCPY( + &ID_BLOCK_ID(idl, j), + &ID_BLOCK_ID(idl, j+1), + (nids-(j+1)) * sizeof(ID)); + ID_BLOCK_ID(idl, nids-1) = NOID; + nids--; +#ifdef USE_INDIRECT_NIDS + ID_BLOCK_NIDS(idl)--; +#endif + if ( ! nids ) + ldbm_cache_delete( db, key ); + else + idl_store( be, db, key, idl ); } + idl_free( tmp ); + cont_free( &data ); + idl_free( idl ); + return 0; } idl_free( tmp ); } - cont_free( data ); + cont_free( &data ); idl_free( idl ); return -1; } @@ -825,12 +1012,16 @@ idl_dup( ID_BLOCK *idl ) return( NULL ); } - new = idl_alloc( ID_BLOCK_NMAX(idl) ); + new = idl_alloc( ID_BLOCK_NMAXN(idl) ); - SAFEMEMCPY( + AC_MEMCPY( (char *) new, (char *) idl, - (ID_BLOCK_NMAX(idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) ); + (ID_BLOCK_NMAXN(idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) ); + +#ifdef LDBM_DEBUG_IDL + idl_check(new); +#endif return( new ); } @@ -866,23 +1057,32 @@ idl_intersection( if ( ID_BLOCK_ALLIDS( b ) ) { return( idl_dup( a ) ); } + if ( ID_BLOCK_NIDS(a) == 0 || ID_BLOCK_NIDS(b) == 0 ) { + return( NULL ); + } n = idl_dup( idl_min( a, b ) ); - for ( ni = 0, ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) { - for ( ; - bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai); - bi++ ) - { - ; /* NULL */ - } - - if ( bi == ID_BLOCK_NIDS(b) ) { - break; - } +#ifdef LDBM_DEBUG_IDL + idl_check(a); + idl_check(b); +#endif + for ( ni = 0, ai = 0, bi = 0; ; ) { if ( ID_BLOCK_ID(b, bi) == ID_BLOCK_ID(a, ai) ) { ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai); + ai++; + bi++; + if ( ai >= ID_BLOCK_NIDS(a) || bi >= ID_BLOCK_NIDS(b) ) + break; + } else if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) { + ai++; + if ( ai >= ID_BLOCK_NIDS(a) ) + break; + } else { + bi++; + if ( bi >= ID_BLOCK_NIDS(b) ) + break; } } @@ -892,6 +1092,10 @@ idl_intersection( } ID_BLOCK_NIDS(n) = ni; +#ifdef LDBM_DEBUG_IDL + idl_check(n); +#endif + return( n ); } @@ -919,6 +1123,11 @@ idl_union( return( idl_allids( be ) ); } +#ifdef LDBM_DEBUG_IDL + idl_check(a); + idl_check(b); +#endif + if ( ID_BLOCK_NIDS(b) < ID_BLOCK_NIDS(a) ) { n = a; a = b; @@ -951,6 +1160,10 @@ idl_union( } ID_BLOCK_NIDS(n) = ni; +#ifdef LDBM_DEBUG_IDL + idl_check(n); +#endif + return( n ); } @@ -961,8 +1174,8 @@ idl_union( ID_BLOCK * idl_notin( Backend *be, - ID_BLOCK *a, - ID_BLOCK *b + ID_BLOCK *a, + ID_BLOCK *b ) { unsigned int ni, ai, bi; @@ -980,7 +1193,7 @@ idl_notin( ni = 0; for ( ai = 1, bi = 0; - ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n) && bi < ID_BLOCK_NMAX(b); + ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAXN(n) && bi < ID_BLOCK_NMAXN(b); ai++ ) { if ( ID_BLOCK_ID(b, bi) == ai ) { @@ -990,11 +1203,11 @@ idl_notin( } } - for ( ; ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n); ai++ ) { + for ( ; ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAXN(n); ai++ ) { ID_BLOCK_ID(n, ni++) = ai; } - if ( ni == ID_BLOCK_NMAX(n) ) { + if ( ni == ID_BLOCK_NMAXN(n) ) { idl_free( n ); return( idl_allids( be ) ); } else { @@ -1028,6 +1241,10 @@ idl_notin( } ID_BLOCK_NIDS(n) = ni; +#ifdef LDBM_DEBUG_IDL + idl_check(n); +#endif + return( n ); } @@ -1038,7 +1255,7 @@ idl_notin( * otherwise return first ID * * cursor is set to 1 - */ + */ ID idl_firstid( ID_BLOCK *idl, ID *cursor ) {