From a2195e5741eaa102449b75eb4d2a836225870b57 Mon Sep 17 00:00:00 2001 From: Pavel Pisa Date: Thu, 31 Dec 2009 10:55:44 +0100 Subject: [PATCH] uLUt: more elaborated hash table sizing implemented. Signed-off-by: Pavel Pisa --- ulut/ul_hashtab.h | 17 +++++++++++++++++ ulut/ul_hashtabchk.c | 3 ++- ulut/ul_hashtabcust.h | 26 +++++++++++++++++++++----- ulut/ul_hashtabprim.c | 21 +++++++++++++++++++++ 4 files changed, 61 insertions(+), 6 deletions(-) diff --git a/ulut/ul_hashtab.h b/ulut/ul_hashtab.h index 7121fc6..95ac2b8 100644 --- a/ulut/ul_hashtab.h +++ b/ulut/ul_hashtab.h @@ -70,10 +70,27 @@ typedef struct ul_hashtab_cust_table_field { } treeroots; long count; ul_hashtab_hashval_t hashmask; + unsigned char sizestep; } ul_hashtab_cust_table_field_t; typedef int (ul_hashtab_resize_insert_fnc_t)(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT; +typedef struct ul_hashtab_sizestep { + ul_hashtab_hashval_t toshrink; + ul_hashtab_hashval_t toexpand; + ul_hashtab_hashval_t size; +} ul_hashtab_sizestep_t; + +static inline int ul_hashtab_sizestep_max(const ul_hashtab_sizestep_t *steptab) +{ + return steptab[0].toshrink; +} + +const ul_hashtab_sizestep_t *ul_hashtab_sizestep_global; +const ul_hashtab_sizestep_t * const ul_hashtab_sizestep_default; + +#define ul_hashtab_sizestep_null ((ul_hashtab_sizestep_t *)0) + void ul_hashtab_init_table_field_primitive(ul_hashtab_cust_table_field_t *table_field); int ul_hashtab_delete_all_primitive(ul_hashtab_cust_table_field_t *table_field); int ul_hashtab_resize_primitive(ul_hashtab_cust_table_field_t *table_field, diff --git a/ulut/ul_hashtabchk.c b/ulut/ul_hashtabchk.c index 7d5ab08..3918b3a 100644 --- a/ulut/ul_hashtabchk.c +++ b/ulut/ul_hashtabchk.c @@ -70,7 +70,7 @@ cust_hash_prep_fnc(cust3_item_t *item) UL_HASTAB_CUST_NODE_INT_IMP(cust3, cust3_table_t, cust3_item_t, cust3_key_t, my_table, my_node, my_val, cust3_cmp_fnc, cust3_hash_fnc, - cust3_hash_get_fnc, cust_hash_prep_fnc, 0, 0) + cust3_hash_get_fnc, cust_hash_prep_fnc, ul_hashtab_sizestep_global) cust3_table_t cust3_table; @@ -137,6 +137,7 @@ int main(int argc, char *argv[]) } if(argc>=3) { tablepow=atol(argv[2]); + ul_hashtab_sizestep_global=ul_hashtab_sizestep_null; } cust3_resize_table(table, 1<cust_table_field.treeroots.treetable[cust_hash_fnc(key)&table->cust_table_field.hashmask]);\ } \ \ +static inline \ +void cust_prefix##_privdummy(cust_table_t *table) \ +{/*used to suppress warning about unused static function generated by GAVL*/\ + cust3_privtree_init_root_field(&(table->cust_table_field.treeroots.treesingle));\ +} \ +\ static \ int cust_prefix##_privinternal_insert(cust_table_t *table, cust_item_t *item)\ {\ @@ -75,8 +81,12 @@ int cust_prefix##_resize_table(cust_table_t *table, ul_hashtab_hashval_t newsize int cust_prefix##_insert(cust_table_t *table, cust_item_t *item)\ {\ int res;\ - if(cust_expand_ratio<=0?0:(table->cust_table_field.count/cust_expand_ratio>table->cust_table_field.hashmask)) \ - cust_prefix##_resize_table(table, (table->cust_table_field.hashmask+1)<<1);\ + if((cust_sizestep)!=ul_hashtab_sizestep_null) \ + if((table->cust_table_field.sizestepcust_table_field.count>=(cust_sizestep)[table->cust_table_field.sizestep].toexpand)) {\ + table->cust_table_field.sizestep++; \ + cust_prefix##_resize_table(table, (cust_sizestep)[table->cust_table_field.sizestep].size);\ + } \ cust_hash_prep_fnc(item);\ res=cust_prefix##_privinternal_insert(table, item);\ if(res>0) \ @@ -90,8 +100,13 @@ int cust_prefix##_delete(cust_table_t *table, cust_item_t *item)\ res=cust_prefix##_privtree_delete(cust_prefix##_privtree_tree4item(table, item), item);\ if(res>0) { \ table->cust_table_field.count--; \ - if(cust_shrink_ratio<=0?0:(table->cust_table_field.count/cust_shrink_ratiocust_table_field.hashmask)) \ - cust_prefix##_resize_table(table, (table->cust_table_field.hashmask>>1)+1);\ + if(((cust_sizestep)!=ul_hashtab_sizestep_null)&&table->cust_table_field.sizestep) \ + if(table->cust_table_field.sizestep>ul_hashtab_sizestep_max(cust_sizestep)) \ + table->cust_table_field.sizestep=ul_hashtab_sizestep_max(cust_sizestep); \ + if(table->cust_table_field.count<=(cust_sizestep)[table->cust_table_field.sizestep].toshrink) {\ + table->cust_table_field.sizestep--; \ + cust_prefix##_resize_table(table, (cust_sizestep)[table->cust_table_field.sizestep].size);\ + } \ }\ return res; \ } \ @@ -104,6 +119,7 @@ cust_item_t *cust_prefix##_delete_key(cust_table_t *table, cust_key_t const *key if(cust_prefix##_privtree_search_node(treeroot, key, &node)) \ return NULL; \ cust_prefix##_privtree_delete_node((ul_hashtab_treeroot_t *)treeroot, node); \ + table->cust_table_field.count--; \ return cust_prefix##_privtree_node2item(NULL,node); \ } \ \ diff --git a/ulut/ul_hashtabprim.c b/ulut/ul_hashtabprim.c index 37f6eb4..3ba8452 100644 --- a/ulut/ul_hashtabprim.c +++ b/ulut/ul_hashtabprim.c @@ -36,6 +36,7 @@ int ul_hashtab_delete_all_primitive(ul_hashtab_cust_table_field_t *table_field) { if(table_field->hashmask) free(table_field->treeroots.treetable); + table_field->sizestep=0; table_field->hashmask=0; table_field->count=0; table_field->treeroots.treesingle.treeroot=NULL; @@ -123,3 +124,23 @@ gavl_node_t *ul_hashtab_next_it_primitive(const ul_hashtab_cust_table_field_t *t (*pptreeroot)++; } while (1); } + +#undef TABENT +#define TABENT(pow) ((ul_hashtab_hashval_t)(1l<<(pow))) + +static const ul_hashtab_sizestep_t ul_hashtab_sizestep_default_table[]={ + { ((ul_hashtab_hashval_t)~0l)<(1l<<8)?2: + ((ul_hashtab_hashval_t)~0l)<(1l<<16)?5:8, + TABENT( 1), TABENT( 0)}, + {TABENT( 0), TABENT( 4), TABENT( 4)}, + {TABENT( 3), TABENT( 6), TABENT( 6)}, + {TABENT( 5), TABENT( 8), TABENT( 8)}, + {TABENT( 7), TABENT(11), TABENT(10)}, + {TABENT(10), TABENT(14), TABENT(12)}, + {TABENT(13), TABENT(18), TABENT(14)}, + {TABENT(17), TABENT(21), TABENT(16)}, + {TABENT(16), 0, TABENT(18)}, +}; + +const ul_hashtab_sizestep_t * const ul_hashtab_sizestep_default=ul_hashtab_sizestep_default_table; +const ul_hashtab_sizestep_t *ul_hashtab_sizestep_global=ul_hashtab_sizestep_default_table; -- 2.39.2