ulut/ul_hashtabcust.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_hastabcust.h       - custom hash table implementation
   5
   6   (C) Copyright 2009 by Pavel Pisa - Originator
   7
   8   The uLan utilities library can be used, copied and modified under
   9   next licenses
  10     - GPL - GNU General Public License
  11     - LGPL - GNU Lesser General Public License
  12     - MPL - Mozilla Public License
  13     - and other licenses added by project originators
  14   Code can be modified and re-distributed under any combination
  15   of the above listed licenses. If contributor does not agree with
  16   some of the licenses, he/she can delete appropriate line.
  17   Warning, if you delete all lines, you are not allowed to
  18   distribute source code and/or binaries utilizing code.
  19
  20   See files COPYING and README for details.
  21
  22  *******************************************************************/
  23
  24 #ifndef _UL_HASHTABCUST_H
  25 #define _UL_HASHTABCUST_H
  26
  27 #include "ul_utdefs.h"
  28 #include "ul_hashtab.h"
  29 #include "ul_gavlcust.h"
  30
  31 #ifdef __cplusplus
  32 extern "C" {
  33 #endif
  34
  35 #define UL_HASTAB_CUST_NODE_INT_IMP(cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
  36                 cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc, cust_hash_fnc, \
  37                 cust_hash_get_fnc, cust_hash_prep_fnc, cust_sizestep) \
  38 GAVL_CUST_NODE_INT_DEC_SCOPE(static, cust_prefix##_privtree, ul_hashtab_treeroot_t, cust_item_t, cust_key_t,\
  39         treeroot, cust_item_node.treenode, cust_item_key, cust_cmp_fnc) \
  40 GAVL_CUST_NODE_INT_IMP(cust_prefix##_privtree, ul_hashtab_treeroot_t, cust_item_t, cust_key_t,\
  41         treeroot, cust_item_node.treenode, cust_item_key, cust_cmp_fnc) \
  42 \
  43 static inline \
  44 ul_hashtab_treeroot_t *cust_prefix##_privtree_tree4item(cust_table_t *table, const cust_item_t *item)\
  45 {\
  46   return !table->cust_table_field.hashmask? &(table->cust_table_field.treeroots.treesingle):\
  47     &(table->cust_table_field.treeroots.treetable[cust_hash_get_fnc(item)&table->cust_table_field.hashmask]);\
  48 } \
  49 \
  50 static inline \
  51 const ul_hashtab_treeroot_t *cust_prefix##_privtree_tree4key(const cust_table_t *table, cust_key_t const *key)\
  52 {\
  53   return !table->cust_table_field.hashmask? &(table->cust_table_field.treeroots.treesingle):\
  54     &(table->cust_table_field.treeroots.treetable[cust_hash_fnc(key)&table->cust_table_field.hashmask]);\
  55 } \
  56 \
  57 static inline \
  58 void cust_prefix##_privdummy(cust_table_t *table) \
  59 {/*used to suppress warning about unused static function generated by GAVL*/\
  60   cust3_privtree_init_root_field(&(table->cust_table_field.treeroots.treesingle));\
  61 } \
  62 \
  63 static \
  64 int cust_prefix##_privinternal_insert(cust_table_t *table, cust_item_t *item)\
  65 {\
  66   return cust_prefix##_privtree_insert(cust_prefix##_privtree_tree4item(table, item), item);\
  67 } \
  68 \
  69 static \
  70 int cust_prefix##_privresize_insert(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT\
  71 {\
  72   return cust_prefix##_privinternal_insert(UL_CONTAINEROF(table_field, cust_table_t, cust_table_field),\
  73                                            cust_prefix##_privtree_node2item(NULL,treenode));\
  74 } \
  75 \
  76 int cust_prefix##_resize_table(cust_table_t *table, ul_hashtab_hashval_t newsize)\
  77 {\
  78   return ul_hashtab_resize_primitive(&table->cust_table_field, newsize, cust_prefix##_privresize_insert);\
  79 } \
  80 \
  81 int cust_prefix##_insert(cust_table_t *table, cust_item_t *item)\
  82 {\
  83   int res;\
  84   if((cust_sizestep)!=ul_hashtab_sizestep_null) \
  85     if((table->cust_table_field.sizestep<ul_hashtab_sizestep_max(cust_sizestep))&& \
  86        (table->cust_table_field.count>=(cust_sizestep)[table->cust_table_field.sizestep].toexpand)) {\
  87       table->cust_table_field.sizestep++; \
  88       cust_prefix##_resize_table(table, (cust_sizestep)[table->cust_table_field.sizestep].size);\
  89   } \
  90   cust_hash_prep_fnc(item);\
  91   res=cust_prefix##_privinternal_insert(table, item);\
  92   if(res>0) \
  93     table->cust_table_field.count++; \
  94   return res; \
  95 } \
  96 \
  97 int cust_prefix##_delete(cust_table_t *table, cust_item_t *item)\
  98 {\
  99   int res;\
 100   res=cust_prefix##_privtree_delete(cust_prefix##_privtree_tree4item(table, item), item);\
 101   if(res>0) { \
 102     table->cust_table_field.count--; \
 103     if(((cust_sizestep)!=ul_hashtab_sizestep_null)&&table->cust_table_field.sizestep) {\
 104       if(table->cust_table_field.sizestep>ul_hashtab_sizestep_max(cust_sizestep)) \
 105         table->cust_table_field.sizestep=ul_hashtab_sizestep_max(cust_sizestep); \
 106       if(table->cust_table_field.count<=(cust_sizestep)[table->cust_table_field.sizestep].toshrink) {\
 107         table->cust_table_field.sizestep--; \
 108         cust_prefix##_resize_table(table, (cust_sizestep)[table->cust_table_field.sizestep].size);\
 109       } \
 110     } \
 111   }\
 112   return res; \
 113 } \
 114 \
 115 cust_item_t *cust_prefix##_delete_key(cust_table_t *table, cust_key_t const *key) \
 116 {\
 117   gavl_node_t *node; \
 118   const ul_hashtab_treeroot_t *treeroot; \
 119   treeroot=cust_prefix##_privtree_tree4key(table, key); \
 120   if(cust_prefix##_privtree_search_node(treeroot, key, &node)) \
 121     return NULL; \
 122   cust_prefix##_privtree_delete_node((ul_hashtab_treeroot_t *)treeroot, node); \
 123   table->cust_table_field.count--; \
 124   return cust_prefix##_privtree_node2item(NULL,node); \
 125 } \
 126 \
 127 int cust_prefix##_search_node(const cust_table_t *table, cust_key_t const *key, typeof(((cust_item_t*)0)->cust_item_node) **nodep) \
 128 {\
 129   gavl_node_t *node;\
 130   if(cust_prefix##_privtree_search_node(cust_prefix##_privtree_tree4key(table, key), key, &node)) { \
 131     *nodep=NULL; \
 132     return -1; \
 133   } \
 134   *nodep=&(UL_CONTAINEROF(node, cust_item_t, cust_item_node.treenode)->cust_item_node); \
 135   return 0; \
 136 } \
 137 \
 138 cust_item_t *cust_prefix##_find(const cust_table_t *table, cust_key_t const *key) \
 139 {\
 140   return cust_prefix##_privtree_find(cust_prefix##_privtree_tree4key(table, key), key); \
 141 } \
 142 \
 143 int cust_prefix##_find_it(cust_table_t *container, cust_key_t const *key, cust_prefix##_it_t *it) \
 144 {\
 145   it->container=container; \
 146   it->ptreeroot=(ul_hashtab_treeroot_t*)cust_prefix##_privtree_tree4key(it->container, key); \
 147   it->item=cust_prefix##_privtree_find(it->ptreeroot, key); \
 148   return it->item!=NULL?1:0; \
 149 }\
 150 \
 151 void cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 152 {\
 153   cust_item_t *item;\
 154   ul_hashtab_treeroot_t *treeroot; \
 155   if(!(item=it->item)) return;\
 156   treeroot=it->ptreeroot; \
 157   cust_prefix##_next_it(it);\
 158   if(cust_prefix##_privtree_delete(treeroot,item)>=0)\
 159     it->container->cust_table_field.count--; \
 160 }
 161
 162 #ifdef __cplusplus
 163 } /* extern "C"*/
 164 #endif
 165
 166 #endif /* _UL_HASHTABCUST_H */