ulut/ul_hashtab.h

   1 /*******************************************************************
   2   uLan Utilities Library - C library of basic reusable constructions
   3
   4   ul_hashtab.h  - hash table declarations
   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_HASHTAB_H
  25 #define _UL_HASHTAB_H
  26
  27 #include "ul_utdefs.h"
  28 #include "ul_itbase.h"
  29 #include "ul_gavl.h"
  30
  31 #ifdef __cplusplus
  32 extern "C" {
  33 #endif
  34
  35 typedef unsigned int ul_hashtab_hashval_t;
  36
  37 /**
  38  * struct ul_hastab_node - Structure Representing Node of Generic AVL Tree
  39  * @treenode:   place to store GAVL node information
  40  */
  41 typedef struct ul_hashtab_node {
  42   gavl_node_t treenode;
  43 } ul_hashtab_node_t;
  44
  45 /**
  46  * struct ul_hashtab_node_hashcache - Structure Representing Node of Generic AVL Tree
  47  * @treenode:   place to store GAVL node information
  48  * @hashval:    place to store computed hash value
  49  */
  50 typedef struct ul_hashtab_node_hashval {
  51   gavl_node_t treenode;
  52   ul_hashtab_hashval_t hashval;
  53 } ul_hashtab_node_hashval_t;
  54
  55 typedef struct ul_hashtab_treeroot {
  56   gavl_cust_root_field_t treeroot;
  57 } ul_hashtab_treeroot_t;
  58
  59 /**
  60  * struct ul_hashtab_cust_table_field - Structure Representing Hash Table
  61  * @count:      number of inserted items
  62  * @hashmask:   mask of bits used to index into actual allocated size
  63  * @treeroots:  internal storage for hash resolution
  64  */
  65
  66 typedef struct ul_hashtab_cust_table_field {
  67   union {
  68     ul_hashtab_treeroot_t *treetable;
  69     ul_hashtab_treeroot_t treesingle;
  70   } treeroots;
  71   long count;
  72   ul_hashtab_hashval_t hashmask;
  73   unsigned char sizestep;
  74 } ul_hashtab_cust_table_field_t;
  75
  76 typedef int (ul_hashtab_resize_insert_fnc_t)(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT;
  77
  78 typedef struct ul_hashtab_sizestep {
  79   ul_hashtab_hashval_t toshrink;
  80   ul_hashtab_hashval_t toexpand;
  81   ul_hashtab_hashval_t size;
  82 } ul_hashtab_sizestep_t;
  83
  84 static inline int ul_hashtab_sizestep_max(const ul_hashtab_sizestep_t *steptab)
  85 {
  86   return steptab[0].toshrink;
  87 }
  88
  89 const ul_hashtab_sizestep_t *ul_hashtab_sizestep_global;
  90 const ul_hashtab_sizestep_t * const ul_hashtab_sizestep_default;
  91
  92 #define ul_hashtab_sizestep_null ((ul_hashtab_sizestep_t *)0)
  93
  94 void ul_hashtab_init_table_field_primitive(ul_hashtab_cust_table_field_t *table_field);
  95 int ul_hashtab_delete_all_primitive(ul_hashtab_cust_table_field_t *table_field);
  96 int ul_hashtab_resize_primitive(ul_hashtab_cust_table_field_t *table_field,
  97                 ul_hashtab_hashval_t newsize, ul_hashtab_resize_insert_fnc_t *ins_fnc);
  98 gavl_node_t *ul_hashtab_next_it_primitive(const ul_hashtab_cust_table_field_t *table_field,
  99         ul_hashtab_treeroot_t **pptreeroot, gavl_node_t *treenode);
 100
 101 /* Declaration of new custom hash table with internal node */
 102 #define UL_HASTAB_CUST_NODE_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
 103                 cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
 104 \
 105 typedef struct {\
 106   cust_table_t *container; \
 107   ul_hashtab_treeroot_t *ptreeroot; \
 108   cust_item_t *item; \
 109 } cust_prefix##_it_t;\
 110 \
 111 cust_scope int cust_prefix##_search_node(const cust_table_t *table, cust_key_t const *key, typeof(((cust_item_t*)0)->cust_item_node) **nodep);\
 112 cust_scope cust_item_t *cust_prefix##_find(const cust_table_t *table, cust_key_t const *key);\
 113 cust_scope int cust_prefix##_insert(cust_table_t *table, cust_item_t *item);\
 114 cust_scope int cust_prefix##_delete_node(cust_table_t *table, gavl_node_t *node);\
 115 cust_scope cust_item_t *cust_prefix##_delete_key(cust_table_t *table, cust_key_t const *key);\
 116 cust_scope int cust_prefix##_delete(cust_table_t *table, cust_item_t *item);\
 117 cust_scope int cust_prefix##_resize_table(cust_table_t *table, ul_hashtab_hashval_t newsize);\
 118 cust_scope int cust_prefix##_find_it(cust_table_t *container, cust_key_t const *key, cust_prefix##_it_t *it);\
 119 cust_scope void cust_prefix##_delete_it(cust_prefix##_it_t *it);\
 120 \
 121 static inline \
 122 void cust_prefix##_init_table_field(cust_table_t *table)\
 123 {\
 124   return ul_hashtab_init_table_field_primitive(&table->cust_table_field);\
 125 } \
 126 \
 127 static inline \
 128 int cust_prefix##_delete_all(cust_table_t *table)\
 129 {\
 130   return ul_hashtab_delete_all_primitive(&table->cust_table_field);\
 131 } \
 132 \
 133 static inline \
 134 cust_item_t *cust_prefix##_it2item(const cust_prefix##_it_t *it)\
 135 {\
 136   return it->item;\
 137 } \
 138 \
 139 static inline int \
 140 cust_prefix##_is_end_it(cust_prefix##_it_t *it)\
 141 {\
 142   return !it->item;\
 143 } \
 144 \
 145 static inline void \
 146 cust_prefix##_next_it(cust_prefix##_it_t *it) \
 147 { \
 148   gavl_node_t *treenode; \
 149   treenode=ul_hashtab_next_it_primitive(\
 150     &it->container->cust_table_field, &it->ptreeroot, \
 151     it->item!=NULL?&it->item->cust_item_node.treenode: NULL); \
 152   it->item=treenode!=NULL?UL_CONTAINEROF(treenode, cust_item_t, cust_item_node.treenode):NULL;\
 153 } \
 154 \
 155 static inline void \
 156 cust_prefix##_first_it(cust_table_t *container, cust_prefix##_it_t *it)\
 157 {\
 158   it->container=container;\
 159   it->item=NULL;\
 160   cust_prefix##_next_it(it);\
 161 }
 162
 163 #define UL_HASTAB_CUST_NODE_INT_DEC(cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
 164                 cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
 165         UL_HASTAB_CUST_NODE_INT_DEC_SCOPE(extern, cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
 166                 cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc)
 167
 168 #ifdef __cplusplus
 169 } /* extern "C"*/
 170 #endif
 171
 172 #endif /* _UL_HASHTAB_H */