uLUt: hash table corrected decision about resize in delete operation.

[ulut.git] / ulut / ul_hashtabcust.h

diff --git a/ulut/ul_hashtabcust.h b/ulut/ul_hashtabcust.h
index e5353ca0934b3a12dd30b6d2f924e57112712921..21125f835464488f68f5c15cfd09b1ad33cd3a5e 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,14 @@ 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 +120,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); \
 } \
 \