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_expand_ratio, cust_shrink_ratio) \
  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 \
  58 int cust_prefix##_privinternal_insert(cust_table_t *table, cust_item_t *item)\
  59 {\
  60   return cust_prefix##_privtree_insert(cust_prefix##_privtree_tree4item(table, item), item);\
  61 } \
  62 \
  63 static \
  64 int cust_prefix##_privresize_insert(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT\
  65 {\
  66   return cust_prefix##_privinternal_insert(UL_CONTAINEROF(table_field, cust_table_t, cust_table_field),\
  67                                            cust_prefix##_privtree_node2item(NULL,treenode));\
  68 } \
  69 \
  70 int cust_prefix##_resize_table(cust_table_t *table, ul_hashtab_hashval_t newsize)\
  71 {\
  72   return ul_hashtab_resize_primitive(&table->cust_table_field, newsize, cust_prefix##_privresize_insert);\
  73 } \
  74 \
  75 int cust_prefix##_insert(cust_table_t *table, cust_item_t *item)\
  76 {\
  77   int res;\
  78   if(cust_expand_ratio<=0?0:(table->cust_table_field.count/cust_expand_ratio>table->cust_table_field.hashmask)) \
  79       cust_prefix##_resize_table(table, (table->cust_table_field.hashmask+1)<<1);\
  80   cust_hash_prep_fnc(item);\
  81   res=cust_prefix##_privinternal_insert(table, item);\
  82   if(res>0) \
  83     table->cust_table_field.count++; \
  84   return res; \
  85 } \
  86 \
  87 int cust_prefix##_delete(cust_table_t *table, cust_item_t *item)\
  88 {\
  89   int res;\
  90   res=cust_prefix##_privtree_delete(cust_prefix##_privtree_tree4item(table, item), item);\
  91   if(res>0) { \
  92     table->cust_table_field.count--; \
  93     if(cust_shrink_ratio<=0?0:(table->cust_table_field.count/cust_shrink_ratio<table->cust_table_field.hashmask)) \
  94       cust_prefix##_resize_table(table, (table->cust_table_field.hashmask>>1)+1);\
  95   }\
  96   return res; \
  97 } \
  98 \
  99 cust_item_t *cust_prefix##_delete_key(cust_table_t *table, cust_key_t const *key) \
 100 {\
 101   gavl_node_t *node; \
 102   const ul_hashtab_treeroot_t *treeroot; \
 103   treeroot=cust_prefix##_privtree_tree4key(table, key); \
 104   if(cust_prefix##_privtree_search_node(treeroot, key, &node)) \
 105     return NULL; \
 106   cust_prefix##_privtree_delete_node((ul_hashtab_treeroot_t *)treeroot, node); \
 107   return cust_prefix##_privtree_node2item(NULL,node); \
 108 } \
 109 \
 110 int cust_prefix##_search_node(const cust_table_t *table, cust_key_t const *key, typeof(((cust_item_t*)0)->cust_item_node) **nodep) \
 111 {\
 112   gavl_node_t *node;\
 113   if(cust_prefix##_privtree_search_node(cust_prefix##_privtree_tree4key(table, key), key, &node)) { \
 114     *nodep=NULL; \
 115     return -1; \
 116   } \
 117   *nodep=&(UL_CONTAINEROF(node, cust_item_t, cust_item_node.treenode)->cust_item_node); \
 118   return 0; \
 119 } \
 120 \
 121 cust_item_t *cust_prefix##_find(const cust_table_t *table, cust_key_t const *key) \
 122 {\
 123   return cust_prefix##_privtree_find(cust_prefix##_privtree_tree4key(table, key), key); \
 124 } \
 125 \
 126 int cust_prefix##_find_it(cust_table_t *container, cust_key_t const *key, cust_prefix##_it_t *it) \
 127 {\
 128   it->container=container; \
 129   it->ptreeroot=(ul_hashtab_treeroot_t*)cust_prefix##_privtree_tree4key(it->container, key); \
 130   it->item=cust_prefix##_privtree_find(it->ptreeroot, key); \
 131   return it->item!=NULL?1:0; \
 132 }\
 133 \
 134 void cust_prefix##_delete_it(cust_prefix##_it_t *it)\
 135 {\
 136   cust_item_t *item;\
 137   ul_hashtab_treeroot_t *treeroot; \
 138   if(!(item=it->item)) return;\
 139   treeroot=it->ptreeroot; \
 140   cust_prefix##_next_it(it);\
 141   if(cust_prefix##_privtree_delete(treeroot,item)>=0)\
 142     it->container->cust_table_field.count--; \
 143 }
 144
 145 #ifdef __cplusplus
 146 } /* extern "C"*/
 147 #endif
 148
 149 #endif /* _UL_HASHTABCUST_H */