From 888731e6c3a0976d6c0838cd4a60964df0368844 Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Wed, 26 Oct 2005 08:31:38 +0000 Subject: [PATCH] Use sorted array for indexed attrs instead of AVL tree --- servers/slapd/back-bdb/attr.c | 137 ++++++++++++++++------------- servers/slapd/back-bdb/back-bdb.h | 3 +- servers/slapd/back-bdb/init.c | 2 +- servers/slapd/back-bdb/proto-bdb.h | 9 +- servers/slapd/back-bdb/tools.c | 24 +++-- 5 files changed, 96 insertions(+), 79 deletions(-) diff --git a/servers/slapd/back-bdb/attr.c b/servers/slapd/back-bdb/attr.c index f058c1f596..bad6c11d2b 100644 --- a/servers/slapd/back-bdb/attr.c +++ b/servers/slapd/back-bdb/attr.c @@ -25,26 +25,49 @@ #include "back-bdb.h" #include "lutil.h" - -static int -ainfo_type_cmp( - const void *v_desc, - const void *v_a -) +unsigned +bdb_attr_slot( struct bdb_info *bdb, AttributeDescription *ad ) { - const AttributeDescription *desc = v_desc; - const AttrInfo *a = v_a; - return SLAP_PTRCMP(desc, a->ai_desc); + unsigned base = 0, cursor = 0; + unsigned n = bdb->bi_nattrs; + int val; + + while ( 0 < n ) { + int pivot = n >> 1; + cursor = base + pivot; + + val = SLAP_PTRCMP( ad, bdb->bi_attrs[cursor]->ai_desc ); + if ( val < 0 ) { + n = pivot; + } else if ( val > 0 ) { + base = cursor + 1; + n -= pivot + 1; + } else { + return cursor; + } + } + if ( val > 0 ) + ++cursor; + return cursor; } static int -ainfo_cmp( - const void *v_a, - const void *v_b -) +ainfo_insert( struct bdb_info *bdb, AttrInfo *a ) { - const AttrInfo *a = v_a, *b = v_b; - return SLAP_PTRCMP(a->ai_desc, b->ai_desc); + unsigned x = bdb_attr_slot( bdb, a->ai_desc ); + + /* Is it a dup? */ + if ( x < bdb->bi_nattrs && bdb->bi_attrs[x]->ai_desc == a->ai_desc ) + return -1; + + bdb->bi_attrs = ch_realloc( bdb->bi_attrs, ( bdb->bi_nattrs+1 ) * + sizeof( AttrInfo * )); + if ( x < bdb->bi_nattrs ) + AC_MEMCPY( &bdb->bi_attrs[x+1], &bdb->bi_attrs[x], + ( bdb->bi_nattrs - x ) * sizeof( AttrInfo *)); + bdb->bi_attrs[x] = a; + bdb->bi_nattrs++; + return 0; } AttrInfo * @@ -52,8 +75,9 @@ bdb_attr_mask( struct bdb_info *bdb, AttributeDescription *desc ) { - - return avl_find( bdb->bi_attrs, desc, ainfo_type_cmp ); + unsigned i = bdb_attr_slot( bdb, desc ); + return ( i < bdb->bi_nattrs && bdb->bi_attrs[i]->ai_desc == desc ) ? + bdb->bi_attrs[i] : NULL; } int @@ -220,7 +244,7 @@ bdb_attr_index_config( #ifdef LDAP_COMP_MATCH if ( cr ) { - a_cr = avl_find( bdb->bi_attrs, ad, ainfo_type_cmp ); + a_cr = bdb_attr_mask( bdb, ad ); if ( a_cr ) { /* * AttrInfo is already in AVL @@ -242,12 +266,10 @@ bdb_attr_index_config( } } #endif - rc = avl_insert( &bdb->bi_attrs, (caddr_t) a, - ainfo_cmp, avl_dup_error ); - + rc = ainfo_insert( bdb, a ); if( rc ) { if ( bdb->bi_flags & BDB_IS_OPEN ) { - AttrInfo *b = avl_find( bdb->bi_attrs, ad, ainfo_type_cmp ); + AttrInfo *b = bdb_attr_mask( bdb, ad ); /* If we were editing this attr, reset it */ b->ai_indexmask &= ~BDB_INDEX_DELETING; /* If this is leftover from a previous add, commit it */ @@ -298,17 +320,19 @@ static AttrInfo aidef = { &addef }; void bdb_attr_index_unparse( struct bdb_info *bdb, BerVarray *bva ) { + int i; + if ( bdb->bi_defaultmask ) { aidef.ai_indexmask = bdb->bi_defaultmask; bdb_attr_index_unparser( &aidef, bva ); } - avl_apply( bdb->bi_attrs, bdb_attr_index_unparser, bva, -1, AVL_INORDER ); + for ( i=0; ibi_nattrs; i++ ) + bdb_attr_index_unparser( bdb->bi_attrs[i], bva ); } -static void -bdb_attrinfo_free( void *v ) +void +bdb_attr_info_free( AttrInfo *ai ) { - AttrInfo *ai = v; #ifdef LDAP_COMP_MATCH free( ai->ai_cr ); #endif @@ -316,52 +340,41 @@ bdb_attrinfo_free( void *v ) } void -bdb_attr_index_destroy( Avlnode *tree ) +bdb_attr_index_destroy( struct bdb_info *bdb ) { - avl_free( tree, bdb_attrinfo_free ); -} + int i; -void bdb_attr_index_free( struct bdb_info *bdb, AttributeDescription *ad ) -{ - AttrInfo *ai; + for ( i=0; ibi_nattrs; i++ ) + bdb_attr_info_free( bdb->bi_attrs[i] ); - ai = avl_delete( &bdb->bi_attrs, ad, ainfo_type_cmp ); - if ( ai ) - bdb_attrinfo_free( ai ); + free( bdb->bi_attrs ); } -/* Get a list of AttrInfo's to delete */ - -typedef struct Alist { - struct Alist *next; - AttrInfo *ptr; -} Alist; - -static int -bdb_attrinfo_flush( void *v1, void *arg ) +void bdb_attr_index_free( struct bdb_info *bdb, AttributeDescription *ad ) { - AttrInfo *ai = v1; - - if ( ai->ai_indexmask & BDB_INDEX_DELETING ) { - Alist **al = arg; - Alist *a = ch_malloc( sizeof( Alist )); - a->ptr = ai; - a->next = *al; - *al = a; + unsigned i; + + i = bdb_attr_slot( bdb, ad ); + if ( i < bdb->bi_nattrs && bdb->bi_attrs[i]->ai_desc == ad ) { + bdb_attr_info_free( bdb->bi_attrs[i] ); + bdb->bi_nattrs--; + for (; ibi_nattrs; i++) + bdb->bi_attrs[i] = bdb->bi_attrs[i+1]; } - return 0; } void bdb_attr_flush( struct bdb_info *bdb ) { - Alist *al = NULL, *a2; - - avl_apply( bdb->bi_attrs, bdb_attrinfo_flush, &al, -1, AVL_INORDER ); - - while (( a2 = al )) { - al = al->next; - avl_delete( &bdb->bi_attrs, a2->ptr, ainfo_cmp ); - bdb_attrinfo_free( a2->ptr ); - ch_free( a2 ); + int i; + + for ( i=0; ibi_nattrs; i++ ) { + if ( bdb->bi_attrs[i]->ai_indexmask & BDB_INDEX_DELETING ) { + int j; + bdb_attr_info_free( bdb->bi_attrs[i] ); + bdb->bi_nattrs--; + for (j=i; jbi_nattrs; j++) + bdb->bi_attrs[j] = bdb->bi_attrs[j+1]; + i--; + } } } diff --git a/servers/slapd/back-bdb/back-bdb.h b/servers/slapd/back-bdb/back-bdb.h index 7091d343db..2992b95511 100644 --- a/servers/slapd/back-bdb/back-bdb.h +++ b/servers/slapd/back-bdb/back-bdb.h @@ -166,7 +166,8 @@ struct bdb_info { slap_mask_t bi_defaultmask; Cache bi_cache; - Avlnode *bi_attrs; + struct bdb_attrinfo **bi_attrs; + int bi_nattrs; void *bi_search_stack; int bi_search_stack_depth; int bi_linear_index; diff --git a/servers/slapd/back-bdb/init.c b/servers/slapd/back-bdb/init.c index a982d23bbd..3fbf91bf6d 100644 --- a/servers/slapd/back-bdb/init.c +++ b/servers/slapd/back-bdb/init.c @@ -606,7 +606,7 @@ bdb_db_destroy( BackendDB *be ) if( bdb->bi_dbenv_home ) ch_free( bdb->bi_dbenv_home ); if( bdb->bi_db_config_path ) ch_free( bdb->bi_db_config_path ); - bdb_attr_index_destroy( bdb->bi_attrs ); + bdb_attr_index_destroy( bdb ); ldap_pvt_thread_rdwr_destroy ( &bdb->bi_cache.c_rwlock ); ldap_pvt_thread_mutex_destroy( &bdb->bi_cache.lru_mutex ); diff --git a/servers/slapd/back-bdb/proto-bdb.h b/servers/slapd/back-bdb/proto-bdb.h index b6555523e9..8b47f977e9 100644 --- a/servers/slapd/back-bdb/proto-bdb.h +++ b/servers/slapd/back-bdb/proto-bdb.h @@ -32,25 +32,32 @@ LDAP_BEGIN_DECL #define bdb_attr_mask BDB_SYMBOL(attr_mask) #define bdb_attr_flush BDB_SYMBOL(attr_flush) +#define bdb_attr_slot BDB_SYMBOL(attr_slot) #define bdb_attr_index_config BDB_SYMBOL(attr_index_config) #define bdb_attr_index_destroy BDB_SYMBOL(attr_index_destroy) #define bdb_attr_index_free BDB_SYMBOL(attr_index_free) #define bdb_attr_index_unparse BDB_SYMBOL(attr_index_unparse) +#define bdb_attr_info_free BDB_SYMBOL(attr_info_free) AttrInfo *bdb_attr_mask( struct bdb_info *bdb, AttributeDescription *desc ); void bdb_attr_flush( struct bdb_info *bdb ); +unsigned bdb_attr_slot( struct bdb_info *bdb, + AttributeDescription *desc ); + int bdb_attr_index_config LDAP_P(( struct bdb_info *bdb, const char *fname, int lineno, int argc, char **argv )); void bdb_attr_index_unparse LDAP_P(( struct bdb_info *bdb, BerVarray *bva )); -void bdb_attr_index_destroy LDAP_P(( Avlnode *tree )); +void bdb_attr_index_destroy LDAP_P(( struct bdb_info *bdb )); void bdb_attr_index_free LDAP_P(( struct bdb_info *bdb, AttributeDescription *ad )); +void bdb_attr_info_free( AttrInfo *ai ); + /* * config.c */ diff --git a/servers/slapd/back-bdb/tools.c b/servers/slapd/back-bdb/tools.c index e49fa8d27d..24bff1427b 100644 --- a/servers/slapd/back-bdb/tools.c +++ b/servers/slapd/back-bdb/tools.c @@ -36,7 +36,7 @@ static dn_id hbuf[HOLE_SIZE], *holes = hbuf; static unsigned nhmax = HOLE_SIZE; static unsigned nholes; -static Avlnode *index_attrs, index_dummy; +static int index_nattrs; #define bdb_tool_idl_cmp BDB_SYMBOL(tool_idl_cmp) #define bdb_tool_idl_flush_one BDB_SYMBOL(tool_idl_flush_one) @@ -115,8 +115,6 @@ int bdb_tool_entry_close( return 0; } -static int bdb_reindex_cmp(const void *a, const void *b) { return 0; } - ID bdb_tool_entry_next( BackendDB *be ) { @@ -134,14 +132,13 @@ ID bdb_tool_entry_next( /* If we're doing linear indexing and there are more attrs to * index, and we're at the end of the database, start over. */ - if ( bdb->bi_attrs == &index_dummy ) { - if ( index_attrs && rc == DB_NOTFOUND ) { - /* optional - do a checkpoint here? */ - index_dummy.avl_data = avl_delete(&index_attrs, NULL, bdb_reindex_cmp); - rc = cursor->c_get( cursor, &key, &data, DB_FIRST ); - } + if ( index_nattrs && rc == DB_NOTFOUND ) { + /* optional - do a checkpoint here? */ + bdb_attr_info_free( bdb->bi_attrs[0] ); + bdb->bi_attrs[0] = bdb->bi_attrs[index_nattrs]; + index_nattrs--; + rc = cursor->c_get( cursor, &key, &data, DB_FIRST ); if ( rc ) { - bdb->bi_attrs = NULL; return NOID; } } else { @@ -468,10 +465,9 @@ int bdb_tool_entry_reindex( } /* Get the first attribute to index */ - if (bi->bi_linear_index && !index_attrs && bi->bi_attrs != &index_dummy) { - index_attrs = bi->bi_attrs; - bi->bi_attrs = &index_dummy; - index_dummy.avl_data = avl_delete(&index_attrs, NULL, bdb_reindex_cmp); + if (bi->bi_linear_index && !index_nattrs) { + index_nattrs = bi->bi_nattrs - 1; + bi->bi_nattrs = 1; } e = bdb_tool_entry_get( be, id ); -- 2.39.5