X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=servers%2Fslapd%2Fback-ldbm%2Fidl.c;h=dbcc8f41b7a18eb96df3ff9112b39b427be4a0c5;hb=b0b3eff457f0e431c4fd094d3d9cfeb6383df91d;hp=7df466cb253a77c5c551d488a8fe74b703378fc0;hpb=59a288abb596a33b55c4dd967faedcb95e7fef6c;p=openldap diff --git a/servers/slapd/back-ldbm/idl.c b/servers/slapd/back-ldbm/idl.c index 7df466cb25..dbcc8f41b7 100644 --- a/servers/slapd/back-ldbm/idl.c +++ b/servers/slapd/back-ldbm/idl.c @@ -1,4 +1,18 @@ /* idl.c - ldap id list handling routines */ +/* $OpenLDAP$ */ +/* This work is part of OpenLDAP Software . + * + * Copyright 1998-2003 The OpenLDAP Foundation. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted only as authorized by the OpenLDAP + * Public License. + * + * A copy of this license is available in the file LICENSE in the + * top-level directory of the distribution or, alternatively, at + * . + */ #include "portable.h" @@ -7,12 +21,75 @@ #include #include -#include "ldapconfig.h" #include "slap.h" #include "back-ldbm.h" +static ID_BLOCK* idl_dup( ID_BLOCK *idl ); + +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 ); + + * (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 ) +{ + unsigned int i; + + for( i=1; i <= sizeof(id); i++) { + ((unsigned char *)cont->dptr)[i] = (unsigned char)(id & 0xFF); + id >>= 8; + } + +} + +static void cont_free( Datum *cont ) +{ + ch_free( cont->dptr ); +} + +#ifdef LDBM_DEBUG_IDL +static void idl_check(ID_BLOCK *idl) +{ + int i, max; + ID_BLOCK last; + + if( ID_BLOCK_ALLIDS(idl) ) + { + return; + } +#ifndef USE_INDIRECT_NIDS + if( ID_BLOCK_INDIRECT(idl) ) + { + for ( max = 0; !ID_BLOCK_NOID(idl, max); max++ ) ; + } else +#endif + { + max = ID_BLOCK_NIDS(idl); + } + if ( max <= 1 ) + { + return; + } + + for( last = ID_BLOCK_ID(idl, 0), i = 1; + i < max; + 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 * -idl_alloc( int nids ) +idl_alloc( unsigned int nids ) { ID_BLOCK *new; @@ -24,85 +101,111 @@ idl_alloc( int nids ) return( new ); } + +/* Allocate an empty ALLIDS ID_BLOCK */ 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 ); } +/* Free an ID_BLOCK */ 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; } free( (char *) idl ); } + +/* Fetch an single ID_BLOCK from the cache */ static ID_BLOCK * idl_fetch_one( Backend *be, - struct dbcache *db, + DBCache *db, Datum key ) { Datum data; ID_BLOCK *idl; - ldbm_datum_init( data ); - /* Debug( LDAP_DEBUG_TRACE, "=> idl_fetch_one\n", 0, 0, 0 ); */ data = ldbm_cache_fetch( db, key ); + if( data.dptr == NULL ) { + return NULL; + } + 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); + } - return( idl ); + ldbm_datum_free( db->dbc_db, data ); + + return idl; } + +/* Fetch a set of ID_BLOCKs from the cache + * if not INDIRECT + * if block return is an ALLIDS block, + * return an new ALLIDS block + * otherwise + * return block + * construct super block from all blocks referenced by INDIRECT block + * return super block + */ ID_BLOCK * idl_fetch( Backend *be, - struct dbcache *db, + DBCache *db, Datum key ) { - Datum data, k2; + Datum data; ID_BLOCK *idl; ID_BLOCK **tmp; - char *kstr; - int i, nids; - - ldbm_datum_init( k2 ); - ldbm_datum_init( data ); + unsigned i, nids, nblocks; - /* Debug( LDAP_DEBUG_TRACE, "=> idl_fetch\n", 0, 0, 0 ); */ + idl = idl_fetch_one( be, db, key ); - data = ldbm_cache_fetch( db, key ); + if ( idl == NULL ) { + return NULL; + } - if ( (idl = (ID_BLOCK *) data.dptr) == NULL ) { - return( NULL ); + if ( ID_BLOCK_ALLIDS(idl) ) { + /* all ids block */ + return( idl ); } - /* regular block */ if ( ! ID_BLOCK_INDIRECT( idl ) ) { - /* - Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %d ids (%d max)\n", - ID_BLOCK_NIDS(idl), ID_BLOCK_NMAX(idl), 0 ); - */ - - /* make sure we have the current value of highest id */ - if ( ID_BLOCK_ALLIDS(idl) ) { - idl_free( idl ); - idl = idl_allids( be ); - } + /* regular block */ return( idl ); } @@ -112,28 +215,36 @@ 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++ ) + for ( nblocks = 0; !ID_BLOCK_NOID(idl, nblocks); nblocks++ ) ; /* NULL */ - tmp = (ID_BLOCK **) ch_malloc( (i + 1) * sizeof(ID_BLOCK *) ); +#else + nblocks = ID_BLOCK_NIDS(idl); +#endif + tmp = (ID_BLOCK **) ch_malloc( nblocks * sizeof(ID_BLOCK *) ); /* read in all the blocks */ - kstr = (char *) ch_malloc( key.dsize + 20 ); + cont_alloc( &data, &key ); nids = 0; - for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ ) { - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, ID_BLOCK_ID(idl, i) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; - - if ( (tmp[i] = idl_fetch_one( be, db, k2 )) == NULL ) { + for ( i = 0; i < nblocks; i++ ) { + 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 of (%s) returns NULL\n", k2.dptr, 0, 0 ); + "idl_fetch: one returned NULL\n", 0, 0, 0 ); +#endif + continue; } nids += ID_BLOCK_NIDS(tmp[i]); } - tmp[i] = NULL; + cont_free( &data ); idl_free( idl ); /* allocate space for the big block */ @@ -142,12 +253,12 @@ idl_fetch( nids = 0; /* copy in all the ids from the component blocks */ - for ( i = 0; tmp[i] != NULL; i++ ) { + for ( i = 0; i < nblocks; i++ ) { if ( tmp[i] == NULL ) { continue; } - SAFEMEMCPY( + AC_MEMCPY( (char *) &ID_BLOCK_ID(idl, nids), (char *) &ID_BLOCK_ID(tmp[i], 0), ID_BLOCK_NIDS(tmp[i]) * sizeof(ID) ); @@ -157,100 +268,148 @@ idl_fetch( } free( (char *) tmp ); - Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %lu ids (%lu max)\n", - ID_BLOCK_NIDS(idl), ID_BLOCK_NMAX(idl), 0 ); + assert( ID_BLOCK_NIDS(idl) == nids ); + +#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_NMAXN(idl), 0 ); +#endif + return( idl ); } + +/* store a single block */ static int idl_store( Backend *be, - struct dbcache *db, + DBCache *db, Datum key, ID_BLOCK *idl ) { 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); -#ifdef LDBM_DEBUG - Statslog( LDAP_DEBUG_STATS, "<= idl_store(): rc=%d\n", - rc, 0, 0, 0, 0 ); -#endif - flags = LDBM_REPLACE; - if( li->li_dbcachewsync ) flags |= LDBM_SYNC; 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. + */ static void idl_split_block( ID_BLOCK *b, ID id, - ID_BLOCK **n1, - ID_BLOCK **n2 + ID_BLOCK **right, + ID_BLOCK **left ) { - unsigned int i; + unsigned int nr, nl; /* find where to split the block */ - for ( i = 0; i < ID_BLOCK_NIDS(b) && id > ID_BLOCK_ID(b, i); i++ ) - ; /* NULL */ + nr = idl_find(b, id); + if ( ID_BLOCK_ID(b,nr) < id ) + nr++; + + nl = ID_BLOCK_NIDS(b) - nr; - *n1 = idl_alloc( i == 0 ? 1 : i ); - *n2 = idl_alloc( ID_BLOCK_NIDS(b) - i + (i == 0 ? 0 : 1)); + *right = idl_alloc( nr == 0 ? 1 : nr ); + *left = idl_alloc( nl + (nr == 0 ? 0 : 1)); /* * everything before the id being inserted in the first block * unless there is nothing, in which case the id being inserted * goes there. */ - SAFEMEMCPY( - (char *) &ID_BLOCK_ID(*n1, 0), - (char *) &ID_BLOCK_ID(b, 0), - i * sizeof(ID) ); - ID_BLOCK_NIDS(*n1) = (i == 0 ? 1 : i); - - if ( i == 0 ) { - ID_BLOCK_ID(*n1, 0) = id; + if ( nr == 0 ) { + ID_BLOCK_NIDS(*right) = 1; + ID_BLOCK_ID(*right, 0) = id; } else { - ID_BLOCK_ID(*n2, 0) = id; + AC_MEMCPY( + (char *) &ID_BLOCK_ID(*right, 0), + (char *) &ID_BLOCK_ID(b, 0), + nr * sizeof(ID) ); + ID_BLOCK_NIDS(*right) = nr; + ID_BLOCK_ID(*left, 0) = id; } /* the id being inserted & everything after in the second block */ - SAFEMEMCPY( - (char *) &ID_BLOCK_ID(*n2, (i == 0 ? 0 : 1)), - (char *) &ID_BLOCK_ID(b, i), - (ID_BLOCK_NIDS(b) - i) * sizeof(ID) ); - ID_BLOCK_NIDS(*n2) = ID_BLOCK_NIDS(b) - i + (i == 0 ? 0 : 1); + 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 } + /* * idl_change_first - called when an indirect block's first key has * changed, meaning it needs to be stored under a new key, and the * header block pointing to it needs updating. */ - static int idl_change_first( Backend *be, - struct dbcache *db, + 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; @@ -259,53 +418,64 @@ 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, - "ldbm_delete of (%s) returns %d\n", bkey.dptr, rc, - 0 ); + "idl_change_first: ldbm_cache_delete returned %d\n", + rc, 0, 0 ); +#endif + return( rc ); } /* write block with new key */ - sprintf( bkey.dptr, "%c%s%ld", CONT_PREFIX, hkey.dptr, ID_BLOCK_ID(b, 0) ); - bkey.dsize = strlen( bkey.dptr ) + 1; + 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_store of (%s) returns %d\n", bkey.dptr, rc, 0 ); + "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_store of (%s) returns %d\n", hkey.dptr, rc, 0 ); + "idl_change_first: idl_store returned %d\n", rc, 0, 0 ); +#endif + return( rc ); } return( 0 ); } + int idl_insert_key( Backend *be, - struct dbcache *db, + DBCache *db, Datum key, ID id ) { - int i, j, first, rc; + int i, j, first, rc = 0; ID_BLOCK *idl, *tmp, *tmp2, *tmp3; - char *kstr; Datum k2; - ldbm_datum_init( k2 ); - if ( (idl = idl_fetch_one( be, db, key )) == NULL ) { -#ifdef LDBM_DEBUG - Statslog( LDAP_DEBUG_STATS, "=> idl_insert_key(): no key yet\n", - 0, 0, 0, 0, 0 ); -#endif - idl = idl_alloc( 1 ); ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)++) = id; rc = idl_store( be, db, key, idl ); @@ -314,8 +484,14 @@ idl_insert_key( return( rc ); } - /* regular block */ + if ( ID_BLOCK_ALLIDS( idl ) ) { + /* ALLIDS */ + idl_free( idl ); + return 0; + } + if ( ! ID_BLOCK_INDIRECT( idl ) ) { + /* regular block */ switch ( idl_insert( &idl, id, db->dbc_maxids ) ) { case 0: /* id inserted - store the updated block */ case 1: @@ -332,41 +508,41 @@ idl_insert_key( idl_free( idl ); idl = idl_allids( be ); rc = idl_store( be, db, key, idl ); - idl_free( idl ); - - return( rc ); + break; } idl_split_block( idl, id, &tmp, &tmp2 ); 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 ); - /* store the first id block */ - kstr = (char *) ch_malloc( key.dsize + 20 ); - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, - ID_BLOCK_ID(tmp, 0) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; + cont_alloc( &k2, &key ); + cont_id( &k2, ID_BLOCK_ID(tmp, 0) ); + rc = idl_store( be, db, k2, tmp ); - /* store the second id block */ - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, - ID_BLOCK_ID(tmp2, 0) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; + cont_id( &k2, ID_BLOCK_ID(tmp2, 0) ); rc = idl_store( be, db, k2, tmp2 ); - free( kstr ); + cont_free( &k2 ); + idl_free( tmp ); idl_free( tmp2 ); break; @@ -384,9 +560,15 @@ idl_insert_key( * need to write a new "header" block. */ - /* select the block to try inserting into */ - for ( i = 0; !ID_BLOCK_NOID(idl, i) && id > ID_BLOCK_ID(idl, i); i++ ) +#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--; first = 0; @@ -394,14 +576,26 @@ idl_insert_key( first = 1; } + /* At this point, the following condition must be true: + * ID_BLOCK_ID(idl, i) <= id && id < ID_BLOCK_ID(idl, i+1) + * except when i is the first or the last block. + */ + /* get the block */ - kstr = (char *) ch_malloc( key.dsize + 20 ); - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, ID_BLOCK_ID(idl, i) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; + cont_alloc( &k2, &key ); + cont_id( &k2, ID_BLOCK_ID(idl, i) ); + if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) { - Debug( LDAP_DEBUG_ANY, "nonexistent continuation block (%s)\n", - k2.dptr, 0, 0 ); +#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 ); +#endif + + cont_free( &k2 ); + idl_free( idl ); return( -1 ); } @@ -409,8 +603,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_store of (%s) returns %d\n", k2.dptr, rc, 0 ); + "idl_insert_key: idl_store returned %d\n", rc, 0, 0 ); +#endif + } break; @@ -425,7 +625,8 @@ idl_insert_key( rc = idl_change_first( be, db, key, idl, i, k2, tmp ); break; - case 2: /* id not inserted - already there */ + case 2: /* id not inserted - already there, do nothing */ + rc = 0; break; case 3: /* id not inserted - block is full */ @@ -435,72 +636,138 @@ 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 + Datum k3; /* read it in */ - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, - ID_BLOCK_ID(idl, i + 1) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; - if ( (tmp2 = idl_fetch_one( be, db, k2 )) == NULL ) { + cont_alloc( &k3, &key ); + cont_id( &k3, ID_BLOCK_ID(idl, i + 1) ); + if ( (tmp2 = idl_fetch_one( be, db, k3 )) == 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_fetch_one (%s) returns NULL\n", - k2.dptr, 0, 0 ); - break; + "idl_insert_key: idl_fetch_one returned NULL\n", + 0, 0, 0 ); +#endif + + /* split the original block */ + cont_free( &k3 ); + goto split; + } + + /* If the new id is less than the last id in the + * current block, it must not be put into the next + * block. Push the last id of the current block + * into the next block instead. + */ + if (id < ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1)) { + ID id2 = ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1); + + --ID_BLOCK_NIDS(tmp); + /* This must succeed since we just popped one + * ID off the end of it. + */ + rc = idl_insert( &tmp, id, db->dbc_maxids ); + + 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 + + } + + id = id2; + /* This new id will necessarily be inserted + * as the first id of the next block by the + * following switch() statement. + */ } switch ( (rc = idl_insert( &tmp2, id, db->dbc_maxids )) ) { case 1: /* id inserted first in block */ rc = idl_change_first( be, db, key, idl, - i + 1, k2, tmp2 ); + i + 1, k3, tmp2 ); /* FALL */ case 2: /* id already there - how? */ - case 0: /* id inserted */ + case 0: /* id inserted: this can never be + * the result of idl_insert, because + * we guaranteed that idl_change_first + * 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, - "id %lu already in next block\n", + "idl_insert_key: id %ld already in next block\n", id, 0, 0 ); +#endif + } - free( kstr ); + idl_free( tmp ); idl_free( tmp2 ); + cont_free( &k3 ); + cont_free( &k2 ); idl_free( idl ); return( 0 ); case 3: /* split the original block */ - idl_free( tmp2 ); break; } + idl_free( tmp2 ); + cont_free( &k3 ); } +split: /* * must split the block, write both new blocks + update * and write the indirect header block. */ - /* count how many indirect blocks */ + 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++ ) { - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, - ID_BLOCK_ID(idl, j) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; +#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 ); } @@ -510,7 +777,7 @@ idl_insert_key( idl = idl_allids( be ); rc = idl_store( be, db, key, idl ); - free( kstr ); + cont_free( &k2 ); idl_free( idl ); idl_free( tmp ); return( rc ); @@ -520,10 +787,14 @@ idl_insert_key( 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) ); @@ -531,26 +802,28 @@ idl_insert_key( 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 */ - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, - ID_BLOCK_ID(tmp2, 0) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; + cont_id( &k2, ID_BLOCK_ID(tmp2, 0) ); rc = idl_store( be, db, k2, tmp2 ); /* store the second id block */ - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, - ID_BLOCK_ID(tmp3, 0) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; + cont_id( &k2, ID_BLOCK_ID(tmp3, 0) ); rc = idl_store( be, db, k2, tmp3 ); idl_free( tmp2 ); @@ -558,79 +831,85 @@ idl_insert_key( break; } - free( kstr ); + cont_free( &k2 ); idl_free( tmp ); idl_free( idl ); return( rc ); } + /* * idl_insert - insert an id into an id list. - * returns 0 id inserted + * + * returns + * 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 */ - int -idl_insert( ID_BLOCK **idl, ID id, int maxids ) +idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids ) { - unsigned int i, j; + unsigned int i; if ( ID_BLOCK_ALLIDS( *idl ) ) { return( 2 ); /* already there */ } - /* is it already there? XXX bin 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 */ - for ( j = ID_BLOCK_NIDS(*idl); j != i; j-- ) { - ID_BLOCK_ID(*idl, j) = ID_BLOCK_ID(*idl, j-1); - } + 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 */ } + int idl_delete_key ( - Backend *be, - struct dbcache *db, - Datum key, - ID id + Backend *be, + DBCache *db, + Datum key, + ID id ) { - Datum k2; - ID_BLOCK *idl, *tmp; + Datum data; + ID_BLOCK *idl; unsigned i; int j, nids; - char *kstr; if ( (idl = idl_fetch_one( be, db, key ) ) == NULL ) { @@ -638,86 +917,112 @@ idl_delete_key ( return -1; } - if ( ! ID_BLOCK_INDIRECT( idl ) ) - { - for ( i=0; i < ID_BLOCK_NIDS(idl); i++ ) - { - if ( ID_BLOCK_ID(idl, i) == id ) - { - SAFEMEMCPY ( + if ( ID_BLOCK_ALLIDS( idl ) ) { + idl_free( idl ); + return 0; + } + + if ( ! ID_BLOCK_INDIRECT( idl ) ) { + i = idl_find(idl, id); + if ( ID_BLOCK_ID(idl, i) == id ) { + if( --ID_BLOCK_NIDS(idl) == 0 ) { + ldbm_cache_delete( db, key ); + + } else { + AC_MEMCPY( &ID_BLOCK_ID(idl, i), &ID_BLOCK_ID(idl, i+1), - (ID_BLOCK_NIDS(idl)-(i+1)) * sizeof(ID) ); + (ID_BLOCK_NIDS(idl)-i) * sizeof(ID) ); - ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)-1) = NOID; - ID_BLOCK_NIDS(idl)--; + ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID; - if ( ID_BLOCK_NIDS(idl) ) - idl_store( be, db, key, idl ); - else - ldbm_cache_delete( db, key ); - 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; } /* 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 */ - kstr = (char *) ch_malloc( key.dsize + 20 ); - for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) + for ( j = 0; j= 0; j = -1) /* execute once */ +#endif { - ldbm_datum_init( k2 ); - sprintf( kstr, "%c%s%ld", CONT_PREFIX, key.dptr, ID_BLOCK_ID(idl, j) ); - k2.dptr = kstr; - k2.dsize = strlen( kstr ) + 1; - - if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) { + ID_BLOCK *tmp; + 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_fetch of (%s) returns NULL\n", k2.dptr, 0, 0 ); + "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, k2, tmp ); + 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 - { - ldbm_cache_delete( db, k2 ); - 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 ); - } - return 0; + idl_store( be, db, key, idl ); } + idl_free( tmp ); + cont_free( &data ); + idl_free( idl ); + return 0; } + idl_free( tmp ); } + + cont_free( &data ); + idl_free( idl ); return -1; } + +/* return a duplicate of a single ID_BLOCK */ static ID_BLOCK * idl_dup( ID_BLOCK *idl ) { @@ -727,26 +1032,32 @@ 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 ); } + +/* return the smaller ID_BLOCK */ static ID_BLOCK * idl_min( ID_BLOCK *a, ID_BLOCK *b ) { return( ID_BLOCK_NIDS(a) > ID_BLOCK_NIDS(b) ? b : a ); } + /* * idl_intersection - return a intersection b */ - ID_BLOCK * idl_intersection( Backend *be, @@ -766,19 +1077,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; } } @@ -788,13 +1112,17 @@ idl_intersection( } ID_BLOCK_NIDS(n) = ni; +#ifdef LDBM_DEBUG_IDL + idl_check(n); +#endif + return( n ); } + /* * idl_union - return a union b */ - ID_BLOCK * idl_union( Backend *be, @@ -815,6 +1143,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; @@ -823,7 +1156,10 @@ idl_union( n = idl_alloc( ID_BLOCK_NIDS(a) + ID_BLOCK_NIDS(b) ); - for ( ni = 0, ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a) && bi < ID_BLOCK_NIDS(b); ) { + for ( ni = 0, ai = 0, bi = 0; + ai < ID_BLOCK_NIDS(a) && bi < ID_BLOCK_NIDS(b); + ) + { if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) { ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai++); @@ -844,18 +1180,22 @@ idl_union( } ID_BLOCK_NIDS(n) = ni; +#ifdef LDBM_DEBUG_IDL + idl_check(n); +#endif + return( n ); } + /* * idl_notin - return a intersection ~b (or a minus b) */ - ID_BLOCK * idl_notin( Backend *be, - ID_BLOCK *a, - ID_BLOCK *b + ID_BLOCK *a, + ID_BLOCK *b ) { unsigned int ni, ai, bi; @@ -873,7 +1213,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 ) { @@ -883,11 +1223,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 { @@ -921,40 +1261,60 @@ idl_notin( } ID_BLOCK_NIDS(n) = ni; +#ifdef LDBM_DEBUG_IDL + idl_check(n); +#endif + return( n ); } +/* return the first ID in the block + * if ALLIDS block + * NIDS > 1 return 1 + * otherwise return NOID + * otherwise return first ID + * + * cursor is set to 1 + */ ID -idl_firstid( ID_BLOCK *idl ) +idl_firstid( ID_BLOCK *idl, ID *cursor ) { + *cursor = 1; + if ( idl == NULL || ID_BLOCK_NIDS(idl) == 0 ) { return( NOID ); } if ( ID_BLOCK_ALLIDS( idl ) ) { - return( ID_BLOCK_NIDS(idl) == 1 ? NOID : 1 ); + return( ID_BLOCK_NIDS(idl) > 1 ? 1 : NOID ); } return( ID_BLOCK_ID(idl, 0) ); } +/* return next ID + * if ALLIDS block, cursor is id. + * increment id + * if id < NIDS return id + * otherwise NOID. + * otherwise cursor is index into block + * if index < nids + * return id at index then increment + */ ID -idl_nextid( ID_BLOCK *idl, ID id ) +idl_nextid( ID_BLOCK *idl, ID *cursor ) { - unsigned int i; - if ( ID_BLOCK_ALLIDS( idl ) ) { - return( ++id < ID_BLOCK_NIDS(idl) ? id : NOID ); + if( ++(*cursor) < ID_BLOCK_NIDS(idl) ) { + return *cursor; + } else { + return NOID; + } } - for ( i = 0; i < ID_BLOCK_NIDS(idl) && ID_BLOCK_ID(idl, i) < id; i++ ) { - ; /* NULL */ + if ( *cursor < ID_BLOCK_NIDS(idl) ) { + return( ID_BLOCK_ID(idl, (*cursor)++) ); } - i++; - if ( i >= ID_BLOCK_NIDS(idl) ) { - return( NOID ); - } else { - return( ID_BLOCK_ID(idl, i) ); - } + return( NOID ); }