1 /*******************************************************************
2 uLan Utilities Library - C library of basic reusable constructions
4 ul_hashtab.h - hash table declarations
6 (C) Copyright 2009 by Pavel Pisa - Originator
8 The uLan utilities library can be used, copied and modified under
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.
20 See files COPYING and README for details.
22 *******************************************************************/
27 #include "ul_utdefs.h"
28 #include "ul_itbase.h"
35 typedef unsigned int ul_hashtab_hashval_t;
38 * struct ul_hastab_node - Structure Representing Node of Generic AVL Tree
39 * @treenode: place to store GAVL node information
41 typedef struct ul_hashtab_node {
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
50 typedef struct ul_hashtab_node_hashval {
52 ul_hashtab_hashval_t hashval;
53 } ul_hashtab_node_hashval_t;
55 typedef struct ul_hashtab_treeroot {
56 gavl_cust_root_field_t treeroot;
57 } ul_hashtab_treeroot_t;
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
66 typedef struct ul_hashtab_cust_table_field {
68 ul_hashtab_treeroot_t *treetable;
69 ul_hashtab_treeroot_t treesingle;
72 ul_hashtab_hashval_t hashmask;
73 unsigned char sizestep;
74 } ul_hashtab_cust_table_field_t;
76 typedef int (ul_hashtab_resize_insert_fnc_t)(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT;
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;
84 static inline int ul_hashtab_sizestep_max(const ul_hashtab_sizestep_t *steptab)
86 return steptab[0].toshrink;
89 const ul_hashtab_sizestep_t *ul_hashtab_sizestep_global;
90 const ul_hashtab_sizestep_t * const ul_hashtab_sizestep_default;
92 #define ul_hashtab_sizestep_null ((ul_hashtab_sizestep_t *)0)
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);
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) \
106 cust_table_t *container; \
107 ul_hashtab_treeroot_t *ptreeroot; \
109 } cust_prefix##_it_t;\
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 void cust_prefix##_next_it(cust_prefix##_it_t *it);\
119 cust_scope int cust_prefix##_find_it(cust_table_t *container, cust_key_t const *key, cust_prefix##_it_t *it);\
120 cust_scope void cust_prefix##_delete_it(cust_prefix##_it_t *it);\
123 void cust_prefix##_init_table_field(cust_table_t *table)\
125 return ul_hashtab_init_table_field_primitive(&table->cust_table_field);\
129 int cust_prefix##_delete_all(cust_table_t *table)\
131 return ul_hashtab_delete_all_primitive(&table->cust_table_field);\
135 cust_item_t *cust_prefix##_it2item(const cust_prefix##_it_t *it)\
141 cust_prefix##_is_end_it(cust_prefix##_it_t *it)\
147 cust_prefix##_first_it(cust_table_t *container, cust_prefix##_it_t *it)\
149 it->container=container;\
151 cust_prefix##_next_it(it);\
154 void cust_prefix##_next_it(cust_prefix##_it_t *it) \
156 gavl_node_t *treenode; \
157 treenode=ul_hashtab_next_it_primitive(\
158 &it->container->cust_table_field, &it->ptreeroot, \
159 it->item!=NULL?&it->item->cust_item_node.treenode: NULL); \
160 it->item=treenode!=NULL?UL_CONTAINEROF(treenode, cust_item_t, cust_item_node.treenode):NULL;\
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)
172 #endif /* _UL_HASHTAB_H */