uLUt: more elaborated hash table sizing implemented.

Signed-off-by: Pavel Pisa <pisa@cmp.felk.cvut.cz>

diff --git a/ulut/ul_hashtab.h b/ulut/ul_hashtab.h
index 7121fc6dcb605e78af319bad2937657bba37b236..95ac2b8d5930a7bcf05829e70187579989ab7d4b 100644 (file)
--- 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 7d5ab08c9d7240b27796b81a42d1c28ace11044f..3918b3ab6e2ac3bb774b94c248c999229e730b81 100644 (file)
--- 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<<tablepow);

diff --git a/ulut/ul_hashtabcust.h b/ulut/ul_hashtabcust.h
index e5353ca0934b3a12dd30b6d2f924e57112712921..c0085210e4a856efc6cd2a8eb89683e48f7b07f1 100644 (file)
--- a/ulut/ul_hashtabcust.h
+++ b/ulut/ul_hashtabcust.h
@@ -34,7 +34,7 @@ extern "C" {
 
 #define UL_HASTAB_CUST_NODE_INT_IMP(cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
                cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc, cust_hash_fnc, \
-               cust_hash_get_fnc, cust_hash_prep_fnc, cust_expand_ratio, cust_shrink_ratio) \
+               cust_hash_get_fnc, cust_hash_prep_fnc, cust_sizestep) \
 GAVL_CUST_NODE_INT_DEC_SCOPE(static, cust_prefix##_privtree, ul_hashtab_treeroot_t, cust_item_t, cust_key_t,\
        treeroot, cust_item_node.treenode, cust_item_key, cust_cmp_fnc) \
 GAVL_CUST_NODE_INT_IMP(cust_prefix##_privtree, ul_hashtab_treeroot_t, cust_item_t, cust_key_t,\
@@ -54,6 +54,12 @@ const ul_hashtab_treeroot_t *cust_prefix##_privtree_tree4key(const cust_table_t
     &(table->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.sizestep<ul_hashtab_sizestep_max(cust_sizestep))&& \
+       (table->cust_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_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)&&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 37f6eb47e9213ced4080db0f110cda4db0fad0d6..3ba8452b3ba5d7b47e14239dbd4abba6784cd666 100644 (file)
--- 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;