]> rtime.felk.cvut.cz Git - ulut.git/blob - ulut/ul_hashtab.h
7121fc6dcb605e78af319bad2937657bba37b236
[ulut.git] / 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 } ul_hashtab_cust_table_field_t;
74
75 typedef int (ul_hashtab_resize_insert_fnc_t)(ul_hashtab_cust_table_field_t *table_field, gavl_node_t *treenode) UL_ATTR_REENTRANT;
76
77 void ul_hashtab_init_table_field_primitive(ul_hashtab_cust_table_field_t *table_field);
78 int ul_hashtab_delete_all_primitive(ul_hashtab_cust_table_field_t *table_field);
79 int ul_hashtab_resize_primitive(ul_hashtab_cust_table_field_t *table_field,
80                 ul_hashtab_hashval_t newsize, ul_hashtab_resize_insert_fnc_t *ins_fnc);
81 gavl_node_t *ul_hashtab_next_it_primitive(const ul_hashtab_cust_table_field_t *table_field,
82         ul_hashtab_treeroot_t **pptreeroot, gavl_node_t *treenode);
83
84 /* Declaration of new custom hash table with internal node */
85 #define UL_HASTAB_CUST_NODE_INT_DEC_SCOPE(cust_scope, cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
86                 cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
87 \
88 typedef struct {\
89   cust_table_t *container; \
90   ul_hashtab_treeroot_t *ptreeroot; \
91   cust_item_t *item; \
92 } cust_prefix##_it_t;\
93 \
94 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);\
95 cust_scope cust_item_t *cust_prefix##_find(const cust_table_t *table, cust_key_t const *key);\
96 cust_scope int cust_prefix##_insert(cust_table_t *table, cust_item_t *item);\
97 cust_scope int cust_prefix##_delete_node(cust_table_t *table, gavl_node_t *node);\
98 cust_scope cust_item_t *cust_prefix##_delete_key(cust_table_t *table, cust_key_t const *key);\
99 cust_scope int cust_prefix##_delete(cust_table_t *table, cust_item_t *item);\
100 cust_scope int cust_prefix##_resize_table(cust_table_t *table, ul_hashtab_hashval_t newsize);\
101 cust_scope void cust_prefix##_next_it(cust_prefix##_it_t *it);\
102 cust_scope int cust_prefix##_find_it(cust_table_t *container, cust_key_t const *key, cust_prefix##_it_t *it);\
103 cust_scope void cust_prefix##_delete_it(cust_prefix##_it_t *it);\
104 \
105 static inline \
106 void cust_prefix##_init_table_field(cust_table_t *table)\
107 {\
108   return ul_hashtab_init_table_field_primitive(&table->cust_table_field);\
109 } \
110 \
111 static inline \
112 int cust_prefix##_delete_all(cust_table_t *table)\
113 {\
114   return ul_hashtab_delete_all_primitive(&table->cust_table_field);\
115 } \
116 \
117 static inline \
118 cust_item_t *cust_prefix##_it2item(const cust_prefix##_it_t *it)\
119 {\
120   return it->item;\
121 } \
122 \
123 static inline int \
124 cust_prefix##_is_end_it(cust_prefix##_it_t *it)\
125 {\
126   return !it->item;\
127 } \
128 \
129 static inline void \
130 cust_prefix##_first_it(cust_table_t *container, cust_prefix##_it_t *it)\
131 {\
132   it->container=container;\
133   it->item=NULL;\
134   cust_prefix##_next_it(it);\
135 } \
136 \
137 void cust_prefix##_next_it(cust_prefix##_it_t *it) \
138 { \
139   gavl_node_t *treenode; \
140   treenode=ul_hashtab_next_it_primitive(\
141     &it->container->cust_table_field, &it->ptreeroot, \
142     it->item!=NULL?&it->item->cust_item_node.treenode: NULL); \
143   it->item=treenode!=NULL?UL_CONTAINEROF(treenode, cust_item_t, cust_item_node.treenode):NULL;\
144 }
145
146 #define UL_HASTAB_CUST_NODE_INT_DEC(cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
147                 cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc) \
148         UL_HASTAB_CUST_NODE_INT_DEC_SCOPE(extern, cust_prefix, cust_table_t, cust_item_t, cust_key_t,\
149                 cust_table_field, cust_item_node, cust_item_key, cust_cmp_fnc)
150
151 #ifdef __cplusplus
152 } /* extern "C"*/
153 #endif
154
155 #endif /* _UL_HASHTAB_H */