ziv@2234
|
1 /*
|
ziv@2234
|
2 Copyright (c) 2003-2014, Troy D. Hanson http://troydhanson.github.com/uthash/
|
ziv@2234
|
3 All rights reserved.
|
ziv@2234
|
4
|
ziv@2234
|
5 Redistribution and use in source and binary forms, with or without
|
ziv@2234
|
6 modification, are permitted provided that the following conditions are met:
|
ziv@2234
|
7
|
ziv@2234
|
8 * Redistributions of source code must retain the above copyright
|
ziv@2234
|
9 notice, this list of conditions and the following disclaimer.
|
ziv@2234
|
10
|
ziv@2234
|
11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
|
ziv@2234
|
12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
|
ziv@2234
|
13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
|
ziv@2234
|
14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
|
ziv@2234
|
15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
ziv@2234
|
16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
ziv@2234
|
17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
ziv@2234
|
18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
|
ziv@2234
|
19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
ziv@2234
|
20 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
ziv@2234
|
21 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
ziv@2234
|
22 */
|
ziv@2234
|
23
|
ziv@2234
|
24 #ifndef UTHASH_H
|
ziv@2234
|
25 #define UTHASH_H
|
ziv@2234
|
26
|
ziv@2234
|
27 #include <string.h> /* memcmp,strlen */
|
ziv@2234
|
28 #include <stddef.h> /* ptrdiff_t */
|
ziv@2234
|
29 #include <stdlib.h> /* exit() */
|
ziv@2234
|
30
|
ziv@2234
|
31 /* These macros use decltype or the earlier __typeof GNU extension.
|
ziv@2234
|
32 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
|
ziv@2234
|
33 when compiling c++ source) this code uses whatever method is needed
|
ziv@2234
|
34 or, for VS2008 where neither is available, uses casting workarounds. */
|
ziv@2234
|
35 #if defined(_MSC_VER) /* MS compiler */
|
ziv@2234
|
36 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
|
ziv@2234
|
37 #define DECLTYPE(x) (decltype(x))
|
ziv@2234
|
38 #else /* VS2008 or older (or VS2010 in C mode) */
|
ziv@2234
|
39 #define NO_DECLTYPE
|
ziv@2234
|
40 #define DECLTYPE(x)
|
ziv@2234
|
41 #endif
|
ziv@2234
|
42 #elif defined(__BORLANDC__) || defined(__LCC__) || defined(__WATCOMC__)
|
ziv@2234
|
43 #define NO_DECLTYPE
|
ziv@2234
|
44 #define DECLTYPE(x)
|
ziv@2234
|
45 #else /* GNU, Sun and other compilers */
|
ziv@2234
|
46 #define DECLTYPE(x) (__typeof(x))
|
ziv@2234
|
47 #endif
|
ziv@2234
|
48
|
ziv@2234
|
49 #ifdef NO_DECLTYPE
|
ziv@2234
|
50 #define DECLTYPE_ASSIGN(dst,src) \
|
ziv@2234
|
51 do { \
|
ziv@2234
|
52 char **_da_dst = (char**)(&(dst)); \
|
ziv@2234
|
53 *_da_dst = (char*)(src); \
|
ziv@2234
|
54 } while(0)
|
ziv@2234
|
55 #else
|
ziv@2234
|
56 #define DECLTYPE_ASSIGN(dst,src) \
|
ziv@2234
|
57 do { \
|
ziv@2234
|
58 (dst) = DECLTYPE(dst)(src); \
|
ziv@2234
|
59 } while(0)
|
ziv@2234
|
60 #endif
|
ziv@2234
|
61
|
ziv@2234
|
62 /* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */
|
ziv@2234
|
63 #if defined (_WIN32)
|
ziv@2234
|
64 #if defined(_MSC_VER) && _MSC_VER >= 1600
|
ziv@2234
|
65 #include <stdint.h>
|
ziv@2234
|
66 #elif defined(__WATCOMC__)
|
ziv@2234
|
67 #include <stdint.h>
|
ziv@2234
|
68 #else
|
ziv@2234
|
69 typedef unsigned int uint32_t;
|
ziv@2234
|
70 typedef unsigned char uint8_t;
|
ziv@2234
|
71 #endif
|
ziv@2234
|
72 #else
|
ziv@2234
|
73 #include <stdint.h>
|
ziv@2234
|
74 #endif
|
ziv@2234
|
75
|
ziv@2234
|
76 #define UTHASH_VERSION 1.9.9
|
ziv@2234
|
77
|
ziv@2234
|
78 #ifndef uthash_fatal
|
ziv@2234
|
79 #define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */
|
ziv@2234
|
80 #endif
|
ziv@2234
|
81 #ifndef uthash_malloc
|
ziv@2234
|
82 #define uthash_malloc(sz) malloc(sz) /* malloc fcn */
|
ziv@2234
|
83 #endif
|
ziv@2234
|
84 #ifndef uthash_free
|
ziv@2234
|
85 #define uthash_free(ptr,sz) free(ptr) /* free fcn */
|
ziv@2234
|
86 #endif
|
ziv@2234
|
87
|
ziv@2234
|
88 #ifndef uthash_noexpand_fyi
|
ziv@2234
|
89 #define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */
|
ziv@2234
|
90 #endif
|
ziv@2234
|
91 #ifndef uthash_expand_fyi
|
ziv@2234
|
92 #define uthash_expand_fyi(tbl) /* can be defined to log expands */
|
ziv@2234
|
93 #endif
|
ziv@2234
|
94
|
ziv@2234
|
95 /* initial number of buckets */
|
ziv@2234
|
96 #define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */
|
ziv@2234
|
97 #define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */
|
ziv@2234
|
98 #define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */
|
ziv@2234
|
99
|
ziv@2234
|
100 /* calculate the element whose hash handle address is hhe */
|
ziv@2234
|
101 #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
|
ziv@2234
|
102
|
ziv@2234
|
103 #define HASH_FIND(hh,head,keyptr,keylen,out) \
|
ziv@2234
|
104 do { \
|
ziv@2234
|
105 out=NULL; \
|
ziv@2234
|
106 if (head != NULL) { \
|
ziv@2234
|
107 unsigned _hf_bkt,_hf_hashv; \
|
ziv@2234
|
108 HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \
|
ziv@2234
|
109 if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv) != 0) { \
|
ziv@2234
|
110 HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \
|
ziv@2234
|
111 keyptr,keylen,out); \
|
ziv@2234
|
112 } \
|
ziv@2234
|
113 } \
|
ziv@2234
|
114 } while (0)
|
ziv@2234
|
115
|
ziv@2234
|
116 #ifdef HASH_BLOOM
|
ziv@2234
|
117 #define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM)
|
ziv@2234
|
118 #define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL)
|
ziv@2234
|
119 #define HASH_BLOOM_MAKE(tbl) \
|
ziv@2234
|
120 do { \
|
ziv@2234
|
121 (tbl)->bloom_nbits = HASH_BLOOM; \
|
ziv@2234
|
122 (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \
|
ziv@2234
|
123 if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \
|
ziv@2234
|
124 memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \
|
ziv@2234
|
125 (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \
|
ziv@2234
|
126 } while (0)
|
ziv@2234
|
127
|
ziv@2234
|
128 #define HASH_BLOOM_FREE(tbl) \
|
ziv@2234
|
129 do { \
|
ziv@2234
|
130 uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \
|
ziv@2234
|
131 } while (0)
|
ziv@2234
|
132
|
ziv@2234
|
133 #define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U)))
|
ziv@2234
|
134 #define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U)))
|
ziv@2234
|
135
|
ziv@2234
|
136 #define HASH_BLOOM_ADD(tbl,hashv) \
|
ziv@2234
|
137 HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U)))
|
ziv@2234
|
138
|
ziv@2234
|
139 #define HASH_BLOOM_TEST(tbl,hashv) \
|
ziv@2234
|
140 HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U)))
|
ziv@2234
|
141
|
ziv@2234
|
142 #else
|
ziv@2234
|
143 #define HASH_BLOOM_MAKE(tbl)
|
ziv@2234
|
144 #define HASH_BLOOM_FREE(tbl)
|
ziv@2234
|
145 #define HASH_BLOOM_ADD(tbl,hashv)
|
ziv@2234
|
146 #define HASH_BLOOM_TEST(tbl,hashv) (1)
|
ziv@2234
|
147 #define HASH_BLOOM_BYTELEN 0U
|
ziv@2234
|
148 #endif
|
ziv@2234
|
149
|
ziv@2234
|
150 #define HASH_MAKE_TABLE(hh,head) \
|
ziv@2234
|
151 do { \
|
ziv@2234
|
152 (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \
|
ziv@2234
|
153 sizeof(UT_hash_table)); \
|
ziv@2234
|
154 if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \
|
ziv@2234
|
155 memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \
|
ziv@2234
|
156 (head)->hh.tbl->tail = &((head)->hh); \
|
ziv@2234
|
157 (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \
|
ziv@2234
|
158 (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \
|
ziv@2234
|
159 (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \
|
ziv@2234
|
160 (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \
|
ziv@2234
|
161 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
|
ziv@2234
|
162 if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \
|
ziv@2234
|
163 memset((head)->hh.tbl->buckets, 0, \
|
ziv@2234
|
164 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
|
ziv@2234
|
165 HASH_BLOOM_MAKE((head)->hh.tbl); \
|
ziv@2234
|
166 (head)->hh.tbl->signature = HASH_SIGNATURE; \
|
ziv@2234
|
167 } while(0)
|
ziv@2234
|
168
|
ziv@2234
|
169 #define HASH_ADD(hh,head,fieldname,keylen_in,add) \
|
ziv@2234
|
170 HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add)
|
ziv@2234
|
171
|
ziv@2234
|
172 #define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \
|
ziv@2234
|
173 do { \
|
ziv@2234
|
174 replaced=NULL; \
|
ziv@2234
|
175 HASH_FIND(hh,head,&((add)->fieldname),keylen_in,replaced); \
|
ziv@2234
|
176 if (replaced!=NULL) { \
|
ziv@2234
|
177 HASH_DELETE(hh,head,replaced); \
|
ziv@2234
|
178 } \
|
ziv@2234
|
179 HASH_ADD(hh,head,fieldname,keylen_in,add); \
|
ziv@2234
|
180 } while(0)
|
ziv@2234
|
181
|
ziv@2234
|
182 #define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \
|
ziv@2234
|
183 do { \
|
ziv@2234
|
184 unsigned _ha_bkt; \
|
ziv@2234
|
185 (add)->hh.next = NULL; \
|
ziv@2234
|
186 (add)->hh.key = (char*)(keyptr); \
|
ziv@2234
|
187 (add)->hh.keylen = (unsigned)(keylen_in); \
|
ziv@2234
|
188 if (!(head)) { \
|
ziv@2234
|
189 head = (add); \
|
ziv@2234
|
190 (head)->hh.prev = NULL; \
|
ziv@2234
|
191 HASH_MAKE_TABLE(hh,head); \
|
ziv@2234
|
192 } else { \
|
ziv@2234
|
193 (head)->hh.tbl->tail->next = (add); \
|
ziv@2234
|
194 (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \
|
ziv@2234
|
195 (head)->hh.tbl->tail = &((add)->hh); \
|
ziv@2234
|
196 } \
|
ziv@2234
|
197 (head)->hh.tbl->num_items++; \
|
ziv@2234
|
198 (add)->hh.tbl = (head)->hh.tbl; \
|
ziv@2234
|
199 HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \
|
ziv@2234
|
200 (add)->hh.hashv, _ha_bkt); \
|
ziv@2234
|
201 HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \
|
ziv@2234
|
202 HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \
|
ziv@2234
|
203 HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \
|
ziv@2234
|
204 HASH_FSCK(hh,head); \
|
ziv@2234
|
205 } while(0)
|
ziv@2234
|
206
|
ziv@2234
|
207 #define HASH_TO_BKT( hashv, num_bkts, bkt ) \
|
ziv@2234
|
208 do { \
|
ziv@2234
|
209 bkt = ((hashv) & ((num_bkts) - 1U)); \
|
ziv@2234
|
210 } while(0)
|
ziv@2234
|
211
|
ziv@2234
|
212 /* delete "delptr" from the hash table.
|
ziv@2234
|
213 * "the usual" patch-up process for the app-order doubly-linked-list.
|
ziv@2234
|
214 * The use of _hd_hh_del below deserves special explanation.
|
ziv@2234
|
215 * These used to be expressed using (delptr) but that led to a bug
|
ziv@2234
|
216 * if someone used the same symbol for the head and deletee, like
|
ziv@2234
|
217 * HASH_DELETE(hh,users,users);
|
ziv@2234
|
218 * We want that to work, but by changing the head (users) below
|
ziv@2234
|
219 * we were forfeiting our ability to further refer to the deletee (users)
|
ziv@2234
|
220 * in the patch-up process. Solution: use scratch space to
|
ziv@2234
|
221 * copy the deletee pointer, then the latter references are via that
|
ziv@2234
|
222 * scratch pointer rather than through the repointed (users) symbol.
|
ziv@2234
|
223 */
|
ziv@2234
|
224 #define HASH_DELETE(hh,head,delptr) \
|
ziv@2234
|
225 do { \
|
ziv@2234
|
226 struct UT_hash_handle *_hd_hh_del; \
|
ziv@2234
|
227 if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \
|
ziv@2234
|
228 uthash_free((head)->hh.tbl->buckets, \
|
ziv@2234
|
229 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \
|
ziv@2234
|
230 HASH_BLOOM_FREE((head)->hh.tbl); \
|
ziv@2234
|
231 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
|
ziv@2234
|
232 head = NULL; \
|
ziv@2234
|
233 } else { \
|
ziv@2234
|
234 unsigned _hd_bkt; \
|
ziv@2234
|
235 _hd_hh_del = &((delptr)->hh); \
|
ziv@2234
|
236 if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \
|
ziv@2234
|
237 (head)->hh.tbl->tail = \
|
ziv@2234
|
238 (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \
|
ziv@2234
|
239 (head)->hh.tbl->hho); \
|
ziv@2234
|
240 } \
|
ziv@2234
|
241 if ((delptr)->hh.prev != NULL) { \
|
ziv@2234
|
242 ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \
|
ziv@2234
|
243 (head)->hh.tbl->hho))->next = (delptr)->hh.next; \
|
ziv@2234
|
244 } else { \
|
ziv@2234
|
245 DECLTYPE_ASSIGN(head,(delptr)->hh.next); \
|
ziv@2234
|
246 } \
|
ziv@2234
|
247 if (_hd_hh_del->next != NULL) { \
|
ziv@2234
|
248 ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \
|
ziv@2234
|
249 (head)->hh.tbl->hho))->prev = \
|
ziv@2234
|
250 _hd_hh_del->prev; \
|
ziv@2234
|
251 } \
|
ziv@2234
|
252 HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \
|
ziv@2234
|
253 HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \
|
ziv@2234
|
254 (head)->hh.tbl->num_items--; \
|
ziv@2234
|
255 } \
|
ziv@2234
|
256 HASH_FSCK(hh,head); \
|
ziv@2234
|
257 } while (0)
|
ziv@2234
|
258
|
ziv@2234
|
259
|
ziv@2234
|
260 /* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */
|
ziv@2234
|
261 #define HASH_FIND_STR(head,findstr,out) \
|
ziv@2234
|
262 HASH_FIND(hh,head,findstr,(unsigned)strlen(findstr),out)
|
ziv@2234
|
263 #define HASH_ADD_STR(head,strfield,add) \
|
ziv@2234
|
264 HASH_ADD(hh,head,strfield[0],(unsigned int)strlen(add->strfield),add)
|
ziv@2234
|
265 #define HASH_REPLACE_STR(head,strfield,add,replaced) \
|
ziv@2234
|
266 HASH_REPLACE(hh,head,strfield[0],(unsigned)strlen(add->strfield),add,replaced)
|
ziv@2234
|
267 #define HASH_FIND_INT(head,findint,out) \
|
ziv@2234
|
268 HASH_FIND(hh,head,findint,sizeof(int),out)
|
ziv@2234
|
269 #define HASH_ADD_INT(head,intfield,add) \
|
ziv@2234
|
270 HASH_ADD(hh,head,intfield,sizeof(int),add)
|
ziv@2234
|
271 #define HASH_REPLACE_INT(head,intfield,add,replaced) \
|
ziv@2234
|
272 HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced)
|
ziv@2234
|
273 #define HASH_FIND_PTR(head,findptr,out) \
|
ziv@2234
|
274 HASH_FIND(hh,head,findptr,sizeof(void *),out)
|
ziv@2234
|
275 #define HASH_ADD_PTR(head,ptrfield,add) \
|
ziv@2234
|
276 HASH_ADD(hh,head,ptrfield,sizeof(void *),add)
|
ziv@2234
|
277 #define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \
|
ziv@2234
|
278 HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced)
|
ziv@2234
|
279 #define HASH_DEL(head,delptr) \
|
ziv@2234
|
280 HASH_DELETE(hh,head,delptr)
|
ziv@2234
|
281
|
ziv@2234
|
282 /* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined.
|
ziv@2234
|
283 * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined.
|
ziv@2234
|
284 */
|
ziv@2234
|
285 #ifdef HASH_DEBUG
|
ziv@2234
|
286 #define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
|
ziv@2234
|
287 #define HASH_FSCK(hh,head) \
|
ziv@2234
|
288 do { \
|
ziv@2234
|
289 struct UT_hash_handle *_thh; \
|
ziv@2234
|
290 if (head) { \
|
ziv@2234
|
291 unsigned _bkt_i; \
|
ziv@2234
|
292 unsigned _count; \
|
ziv@2234
|
293 char *_prev; \
|
ziv@2234
|
294 _count = 0; \
|
ziv@2234
|
295 for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \
|
ziv@2234
|
296 unsigned _bkt_count = 0; \
|
ziv@2234
|
297 _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \
|
ziv@2234
|
298 _prev = NULL; \
|
ziv@2234
|
299 while (_thh) { \
|
ziv@2234
|
300 if (_prev != (char*)(_thh->hh_prev)) { \
|
ziv@2234
|
301 HASH_OOPS("invalid hh_prev %p, actual %p\n", \
|
ziv@2234
|
302 _thh->hh_prev, _prev ); \
|
ziv@2234
|
303 } \
|
ziv@2234
|
304 _bkt_count++; \
|
ziv@2234
|
305 _prev = (char*)(_thh); \
|
ziv@2234
|
306 _thh = _thh->hh_next; \
|
ziv@2234
|
307 } \
|
ziv@2234
|
308 _count += _bkt_count; \
|
ziv@2234
|
309 if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \
|
ziv@2234
|
310 HASH_OOPS("invalid bucket count %u, actual %u\n", \
|
ziv@2234
|
311 (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \
|
ziv@2234
|
312 } \
|
ziv@2234
|
313 } \
|
ziv@2234
|
314 if (_count != (head)->hh.tbl->num_items) { \
|
ziv@2234
|
315 HASH_OOPS("invalid hh item count %u, actual %u\n", \
|
ziv@2234
|
316 (head)->hh.tbl->num_items, _count ); \
|
ziv@2234
|
317 } \
|
ziv@2234
|
318 /* traverse hh in app order; check next/prev integrity, count */ \
|
ziv@2234
|
319 _count = 0; \
|
ziv@2234
|
320 _prev = NULL; \
|
ziv@2234
|
321 _thh = &(head)->hh; \
|
ziv@2234
|
322 while (_thh) { \
|
ziv@2234
|
323 _count++; \
|
ziv@2234
|
324 if (_prev !=(char*)(_thh->prev)) { \
|
ziv@2234
|
325 HASH_OOPS("invalid prev %p, actual %p\n", \
|
ziv@2234
|
326 _thh->prev, _prev ); \
|
ziv@2234
|
327 } \
|
ziv@2234
|
328 _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \
|
ziv@2234
|
329 _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \
|
ziv@2234
|
330 (head)->hh.tbl->hho) : NULL ); \
|
ziv@2234
|
331 } \
|
ziv@2234
|
332 if (_count != (head)->hh.tbl->num_items) { \
|
ziv@2234
|
333 HASH_OOPS("invalid app item count %u, actual %u\n", \
|
ziv@2234
|
334 (head)->hh.tbl->num_items, _count ); \
|
ziv@2234
|
335 } \
|
ziv@2234
|
336 } \
|
ziv@2234
|
337 } while (0)
|
ziv@2234
|
338 #else
|
ziv@2234
|
339 #define HASH_FSCK(hh,head)
|
ziv@2234
|
340 #endif
|
ziv@2234
|
341
|
ziv@2234
|
342 /* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to
|
ziv@2234
|
343 * the descriptor to which this macro is defined for tuning the hash function.
|
ziv@2234
|
344 * The app can #include <unistd.h> to get the prototype for write(2). */
|
ziv@2234
|
345 #ifdef HASH_EMIT_KEYS
|
ziv@2234
|
346 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \
|
ziv@2234
|
347 do { \
|
ziv@2234
|
348 unsigned _klen = fieldlen; \
|
ziv@2234
|
349 write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \
|
ziv@2234
|
350 write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \
|
ziv@2234
|
351 } while (0)
|
ziv@2234
|
352 #else
|
ziv@2234
|
353 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)
|
ziv@2234
|
354 #endif
|
ziv@2234
|
355
|
ziv@2234
|
356 /* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */
|
ziv@2234
|
357 #ifdef HASH_FUNCTION
|
ziv@2234
|
358 #define HASH_FCN HASH_FUNCTION
|
ziv@2234
|
359 #else
|
ziv@2234
|
360 #define HASH_FCN HASH_JEN
|
ziv@2234
|
361 #endif
|
ziv@2234
|
362
|
ziv@2234
|
363 /* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */
|
ziv@2234
|
364 #define HASH_BER(key,keylen,num_bkts,hashv,bkt) \
|
ziv@2234
|
365 do { \
|
ziv@2234
|
366 unsigned _hb_keylen=(unsigned)keylen; \
|
ziv@2234
|
367 const unsigned char *_hb_key=(const unsigned char*)(key); \
|
ziv@2234
|
368 (hashv) = 0; \
|
ziv@2234
|
369 while (_hb_keylen-- != 0U) { \
|
ziv@2234
|
370 (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \
|
ziv@2234
|
371 } \
|
ziv@2234
|
372 bkt = (hashv) & (num_bkts-1U); \
|
ziv@2234
|
373 } while (0)
|
ziv@2234
|
374
|
ziv@2234
|
375
|
ziv@2234
|
376 /* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at
|
ziv@2234
|
377 * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
|
ziv@2234
|
378 #define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \
|
ziv@2234
|
379 do { \
|
ziv@2234
|
380 unsigned _sx_i; \
|
ziv@2234
|
381 const unsigned char *_hs_key=(const unsigned char*)(key); \
|
ziv@2234
|
382 hashv = 0; \
|
ziv@2234
|
383 for(_sx_i=0; _sx_i < keylen; _sx_i++) { \
|
ziv@2234
|
384 hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \
|
ziv@2234
|
385 } \
|
ziv@2234
|
386 bkt = hashv & (num_bkts-1U); \
|
ziv@2234
|
387 } while (0)
|
ziv@2234
|
388 /* FNV-1a variation */
|
ziv@2234
|
389 #define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \
|
ziv@2234
|
390 do { \
|
ziv@2234
|
391 unsigned _fn_i; \
|
ziv@2234
|
392 const unsigned char *_hf_key=(const unsigned char*)(key); \
|
ziv@2234
|
393 hashv = 2166136261U; \
|
ziv@2234
|
394 for(_fn_i=0; _fn_i < keylen; _fn_i++) { \
|
ziv@2234
|
395 hashv = hashv ^ _hf_key[_fn_i]; \
|
ziv@2234
|
396 hashv = hashv * 16777619U; \
|
ziv@2234
|
397 } \
|
ziv@2234
|
398 bkt = hashv & (num_bkts-1U); \
|
ziv@2234
|
399 } while(0)
|
ziv@2234
|
400
|
ziv@2234
|
401 #define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \
|
ziv@2234
|
402 do { \
|
ziv@2234
|
403 unsigned _ho_i; \
|
ziv@2234
|
404 const unsigned char *_ho_key=(const unsigned char*)(key); \
|
ziv@2234
|
405 hashv = 0; \
|
ziv@2234
|
406 for(_ho_i=0; _ho_i < keylen; _ho_i++) { \
|
ziv@2234
|
407 hashv += _ho_key[_ho_i]; \
|
ziv@2234
|
408 hashv += (hashv << 10); \
|
ziv@2234
|
409 hashv ^= (hashv >> 6); \
|
ziv@2234
|
410 } \
|
ziv@2234
|
411 hashv += (hashv << 3); \
|
ziv@2234
|
412 hashv ^= (hashv >> 11); \
|
ziv@2234
|
413 hashv += (hashv << 15); \
|
ziv@2234
|
414 bkt = hashv & (num_bkts-1U); \
|
ziv@2234
|
415 } while(0)
|
ziv@2234
|
416
|
ziv@2234
|
417 #define HASH_JEN_MIX(a,b,c) \
|
ziv@2234
|
418 do { \
|
ziv@2234
|
419 a -= b; a -= c; a ^= ( c >> 13 ); \
|
ziv@2234
|
420 b -= c; b -= a; b ^= ( a << 8 ); \
|
ziv@2234
|
421 c -= a; c -= b; c ^= ( b >> 13 ); \
|
ziv@2234
|
422 a -= b; a -= c; a ^= ( c >> 12 ); \
|
ziv@2234
|
423 b -= c; b -= a; b ^= ( a << 16 ); \
|
ziv@2234
|
424 c -= a; c -= b; c ^= ( b >> 5 ); \
|
ziv@2234
|
425 a -= b; a -= c; a ^= ( c >> 3 ); \
|
ziv@2234
|
426 b -= c; b -= a; b ^= ( a << 10 ); \
|
ziv@2234
|
427 c -= a; c -= b; c ^= ( b >> 15 ); \
|
ziv@2234
|
428 } while (0)
|
ziv@2234
|
429
|
ziv@2234
|
430 #define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \
|
ziv@2234
|
431 do { \
|
ziv@2234
|
432 unsigned _hj_i,_hj_j,_hj_k; \
|
ziv@2234
|
433 unsigned const char *_hj_key=(unsigned const char*)(key); \
|
ziv@2234
|
434 hashv = 0xfeedbeefu; \
|
ziv@2234
|
435 _hj_i = _hj_j = 0x9e3779b9u; \
|
ziv@2234
|
436 _hj_k = (unsigned)(keylen); \
|
ziv@2234
|
437 while (_hj_k >= 12U) { \
|
ziv@2234
|
438 _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \
|
ziv@2234
|
439 + ( (unsigned)_hj_key[2] << 16 ) \
|
ziv@2234
|
440 + ( (unsigned)_hj_key[3] << 24 ) ); \
|
ziv@2234
|
441 _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \
|
ziv@2234
|
442 + ( (unsigned)_hj_key[6] << 16 ) \
|
ziv@2234
|
443 + ( (unsigned)_hj_key[7] << 24 ) ); \
|
ziv@2234
|
444 hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \
|
ziv@2234
|
445 + ( (unsigned)_hj_key[10] << 16 ) \
|
ziv@2234
|
446 + ( (unsigned)_hj_key[11] << 24 ) ); \
|
ziv@2234
|
447 \
|
ziv@2234
|
448 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
|
ziv@2234
|
449 \
|
ziv@2234
|
450 _hj_key += 12; \
|
ziv@2234
|
451 _hj_k -= 12U; \
|
ziv@2234
|
452 } \
|
ziv@2234
|
453 hashv += (unsigned)(keylen); \
|
ziv@2234
|
454 switch ( _hj_k ) { \
|
ziv@2234
|
455 case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \
|
ziv@2234
|
456 case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \
|
ziv@2234
|
457 case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \
|
ziv@2234
|
458 case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \
|
ziv@2234
|
459 case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \
|
ziv@2234
|
460 case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \
|
ziv@2234
|
461 case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \
|
ziv@2234
|
462 case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \
|
ziv@2234
|
463 case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \
|
ziv@2234
|
464 case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \
|
ziv@2234
|
465 case 1: _hj_i += _hj_key[0]; \
|
ziv@2234
|
466 } \
|
ziv@2234
|
467 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
|
ziv@2234
|
468 bkt = hashv & (num_bkts-1U); \
|
ziv@2234
|
469 } while(0)
|
ziv@2234
|
470
|
ziv@2234
|
471 /* The Paul Hsieh hash function */
|
ziv@2234
|
472 #undef get16bits
|
ziv@2234
|
473 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
|
ziv@2234
|
474 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
|
ziv@2234
|
475 #define get16bits(d) (*((const uint16_t *) (d)))
|
ziv@2234
|
476 #endif
|
ziv@2234
|
477
|
ziv@2234
|
478 #if !defined (get16bits)
|
ziv@2234
|
479 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
|
ziv@2234
|
480 +(uint32_t)(((const uint8_t *)(d))[0]) )
|
ziv@2234
|
481 #endif
|
ziv@2234
|
482 #define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \
|
ziv@2234
|
483 do { \
|
ziv@2234
|
484 unsigned const char *_sfh_key=(unsigned const char*)(key); \
|
ziv@2234
|
485 uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \
|
ziv@2234
|
486 \
|
ziv@2234
|
487 unsigned _sfh_rem = _sfh_len & 3U; \
|
ziv@2234
|
488 _sfh_len >>= 2; \
|
ziv@2234
|
489 hashv = 0xcafebabeu; \
|
ziv@2234
|
490 \
|
ziv@2234
|
491 /* Main loop */ \
|
ziv@2234
|
492 for (;_sfh_len > 0U; _sfh_len--) { \
|
ziv@2234
|
493 hashv += get16bits (_sfh_key); \
|
ziv@2234
|
494 _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \
|
ziv@2234
|
495 hashv = (hashv << 16) ^ _sfh_tmp; \
|
ziv@2234
|
496 _sfh_key += 2U*sizeof (uint16_t); \
|
ziv@2234
|
497 hashv += hashv >> 11; \
|
ziv@2234
|
498 } \
|
ziv@2234
|
499 \
|
ziv@2234
|
500 /* Handle end cases */ \
|
ziv@2234
|
501 switch (_sfh_rem) { \
|
ziv@2234
|
502 case 3: hashv += get16bits (_sfh_key); \
|
ziv@2234
|
503 hashv ^= hashv << 16; \
|
ziv@2234
|
504 hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \
|
ziv@2234
|
505 hashv += hashv >> 11; \
|
ziv@2234
|
506 break; \
|
ziv@2234
|
507 case 2: hashv += get16bits (_sfh_key); \
|
ziv@2234
|
508 hashv ^= hashv << 11; \
|
ziv@2234
|
509 hashv += hashv >> 17; \
|
ziv@2234
|
510 break; \
|
ziv@2234
|
511 case 1: hashv += *_sfh_key; \
|
ziv@2234
|
512 hashv ^= hashv << 10; \
|
ziv@2234
|
513 hashv += hashv >> 1; \
|
ziv@2234
|
514 } \
|
ziv@2234
|
515 \
|
ziv@2234
|
516 /* Force "avalanching" of final 127 bits */ \
|
ziv@2234
|
517 hashv ^= hashv << 3; \
|
ziv@2234
|
518 hashv += hashv >> 5; \
|
ziv@2234
|
519 hashv ^= hashv << 4; \
|
ziv@2234
|
520 hashv += hashv >> 17; \
|
ziv@2234
|
521 hashv ^= hashv << 25; \
|
ziv@2234
|
522 hashv += hashv >> 6; \
|
ziv@2234
|
523 bkt = hashv & (num_bkts-1U); \
|
ziv@2234
|
524 } while(0)
|
ziv@2234
|
525
|
ziv@2234
|
526 #ifdef HASH_USING_NO_STRICT_ALIASING
|
ziv@2234
|
527 /* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads.
|
ziv@2234
|
528 * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error.
|
ziv@2234
|
529 * MurmurHash uses the faster approach only on CPU's where we know it's safe.
|
ziv@2234
|
530 *
|
ziv@2234
|
531 * Note the preprocessor built-in defines can be emitted using:
|
ziv@2234
|
532 *
|
ziv@2234
|
533 * gcc -m64 -dM -E - < /dev/null (on gcc)
|
ziv@2234
|
534 * cc -## a.c (where a.c is a simple test file) (Sun Studio)
|
ziv@2234
|
535 */
|
ziv@2234
|
536 #if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86))
|
ziv@2234
|
537 #define MUR_GETBLOCK(p,i) p[i]
|
ziv@2234
|
538 #else /* non intel */
|
ziv@2234
|
539 #define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL)
|
ziv@2234
|
540 #define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL)
|
ziv@2234
|
541 #define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL)
|
ziv@2234
|
542 #define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL)
|
ziv@2234
|
543 #define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL))
|
ziv@2234
|
544 #if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__))
|
ziv@2234
|
545 #define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24))
|
ziv@2234
|
546 #define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16))
|
ziv@2234
|
547 #define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8))
|
ziv@2234
|
548 #else /* assume little endian non-intel */
|
ziv@2234
|
549 #define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24))
|
ziv@2234
|
550 #define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16))
|
ziv@2234
|
551 #define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8))
|
ziv@2234
|
552 #endif
|
ziv@2234
|
553 #define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \
|
ziv@2234
|
554 (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \
|
ziv@2234
|
555 (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \
|
ziv@2234
|
556 MUR_ONE_THREE(p))))
|
ziv@2234
|
557 #endif
|
ziv@2234
|
558 #define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
|
ziv@2234
|
559 #define MUR_FMIX(_h) \
|
ziv@2234
|
560 do { \
|
ziv@2234
|
561 _h ^= _h >> 16; \
|
ziv@2234
|
562 _h *= 0x85ebca6bu; \
|
ziv@2234
|
563 _h ^= _h >> 13; \
|
ziv@2234
|
564 _h *= 0xc2b2ae35u; \
|
ziv@2234
|
565 _h ^= _h >> 16; \
|
ziv@2234
|
566 } while(0)
|
ziv@2234
|
567
|
ziv@2234
|
568 #define HASH_MUR(key,keylen,num_bkts,hashv,bkt) \
|
ziv@2234
|
569 do { \
|
ziv@2234
|
570 const uint8_t *_mur_data = (const uint8_t*)(key); \
|
ziv@2234
|
571 const int _mur_nblocks = (int)(keylen) / 4; \
|
ziv@2234
|
572 uint32_t _mur_h1 = 0xf88D5353u; \
|
ziv@2234
|
573 uint32_t _mur_c1 = 0xcc9e2d51u; \
|
ziv@2234
|
574 uint32_t _mur_c2 = 0x1b873593u; \
|
ziv@2234
|
575 uint32_t _mur_k1 = 0; \
|
ziv@2234
|
576 const uint8_t *_mur_tail; \
|
ziv@2234
|
577 const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \
|
ziv@2234
|
578 int _mur_i; \
|
ziv@2234
|
579 for(_mur_i = -_mur_nblocks; _mur_i!=0; _mur_i++) { \
|
ziv@2234
|
580 _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \
|
ziv@2234
|
581 _mur_k1 *= _mur_c1; \
|
ziv@2234
|
582 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
|
ziv@2234
|
583 _mur_k1 *= _mur_c2; \
|
ziv@2234
|
584 \
|
ziv@2234
|
585 _mur_h1 ^= _mur_k1; \
|
ziv@2234
|
586 _mur_h1 = MUR_ROTL32(_mur_h1,13); \
|
ziv@2234
|
587 _mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \
|
ziv@2234
|
588 } \
|
ziv@2234
|
589 _mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \
|
ziv@2234
|
590 _mur_k1=0; \
|
ziv@2234
|
591 switch((keylen) & 3U) { \
|
ziv@2234
|
592 case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16; /* FALLTHROUGH */ \
|
ziv@2234
|
593 case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8; /* FALLTHROUGH */ \
|
ziv@2234
|
594 case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \
|
ziv@2234
|
595 _mur_k1 *= _mur_c1; \
|
ziv@2234
|
596 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
|
ziv@2234
|
597 _mur_k1 *= _mur_c2; \
|
ziv@2234
|
598 _mur_h1 ^= _mur_k1; \
|
ziv@2234
|
599 } \
|
ziv@2234
|
600 _mur_h1 ^= (uint32_t)(keylen); \
|
ziv@2234
|
601 MUR_FMIX(_mur_h1); \
|
ziv@2234
|
602 hashv = _mur_h1; \
|
ziv@2234
|
603 bkt = hashv & (num_bkts-1U); \
|
ziv@2234
|
604 } while(0)
|
ziv@2234
|
605 #endif /* HASH_USING_NO_STRICT_ALIASING */
|
ziv@2234
|
606
|
ziv@2234
|
607 /* key comparison function; return 0 if keys equal */
|
ziv@2234
|
608 #define HASH_KEYCMP(a,b,len) memcmp(a,b,(unsigned long)(len))
|
ziv@2234
|
609
|
ziv@2234
|
610 /* iterate over items in a known bucket to find desired item */
|
ziv@2234
|
611 #define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \
|
ziv@2234
|
612 do { \
|
ziv@2234
|
613 if (head.hh_head != NULL) { DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); } \
|
ziv@2234
|
614 else { out=NULL; } \
|
ziv@2234
|
615 while (out != NULL) { \
|
ziv@2234
|
616 if ((out)->hh.keylen == (keylen_in)) { \
|
ziv@2234
|
617 if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) { break; } \
|
ziv@2234
|
618 } \
|
ziv@2234
|
619 if ((out)->hh.hh_next != NULL) { DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); } \
|
ziv@2234
|
620 else { out = NULL; } \
|
ziv@2234
|
621 } \
|
ziv@2234
|
622 } while(0)
|
ziv@2234
|
623
|
ziv@2234
|
624 /* add an item to a bucket */
|
ziv@2234
|
625 #define HASH_ADD_TO_BKT(head,addhh) \
|
ziv@2234
|
626 do { \
|
ziv@2234
|
627 head.count++; \
|
ziv@2234
|
628 (addhh)->hh_next = head.hh_head; \
|
ziv@2234
|
629 (addhh)->hh_prev = NULL; \
|
ziv@2234
|
630 if (head.hh_head != NULL) { (head).hh_head->hh_prev = (addhh); } \
|
ziv@2234
|
631 (head).hh_head=addhh; \
|
ziv@2234
|
632 if ((head.count >= ((head.expand_mult+1U) * HASH_BKT_CAPACITY_THRESH)) \
|
ziv@2234
|
633 && ((addhh)->tbl->noexpand != 1U)) { \
|
ziv@2234
|
634 HASH_EXPAND_BUCKETS((addhh)->tbl); \
|
ziv@2234
|
635 } \
|
ziv@2234
|
636 } while(0)
|
ziv@2234
|
637
|
ziv@2234
|
638 /* remove an item from a given bucket */
|
ziv@2234
|
639 #define HASH_DEL_IN_BKT(hh,head,hh_del) \
|
ziv@2234
|
640 (head).count--; \
|
ziv@2234
|
641 if ((head).hh_head == hh_del) { \
|
ziv@2234
|
642 (head).hh_head = hh_del->hh_next; \
|
ziv@2234
|
643 } \
|
ziv@2234
|
644 if (hh_del->hh_prev) { \
|
ziv@2234
|
645 hh_del->hh_prev->hh_next = hh_del->hh_next; \
|
ziv@2234
|
646 } \
|
ziv@2234
|
647 if (hh_del->hh_next) { \
|
ziv@2234
|
648 hh_del->hh_next->hh_prev = hh_del->hh_prev; \
|
ziv@2234
|
649 }
|
ziv@2234
|
650
|
ziv@2234
|
651 /* Bucket expansion has the effect of doubling the number of buckets
|
ziv@2234
|
652 * and redistributing the items into the new buckets. Ideally the
|
ziv@2234
|
653 * items will distribute more or less evenly into the new buckets
|
ziv@2234
|
654 * (the extent to which this is true is a measure of the quality of
|
ziv@2234
|
655 * the hash function as it applies to the key domain).
|
ziv@2234
|
656 *
|
ziv@2234
|
657 * With the items distributed into more buckets, the chain length
|
ziv@2234
|
658 * (item count) in each bucket is reduced. Thus by expanding buckets
|
ziv@2234
|
659 * the hash keeps a bound on the chain length. This bounded chain
|
ziv@2234
|
660 * length is the essence of how a hash provides constant time lookup.
|
ziv@2234
|
661 *
|
ziv@2234
|
662 * The calculation of tbl->ideal_chain_maxlen below deserves some
|
ziv@2234
|
663 * explanation. First, keep in mind that we're calculating the ideal
|
ziv@2234
|
664 * maximum chain length based on the *new* (doubled) bucket count.
|
ziv@2234
|
665 * In fractions this is just n/b (n=number of items,b=new num buckets).
|
ziv@2234
|
666 * Since the ideal chain length is an integer, we want to calculate
|
ziv@2234
|
667 * ceil(n/b). We don't depend on floating point arithmetic in this
|
ziv@2234
|
668 * hash, so to calculate ceil(n/b) with integers we could write
|
ziv@2234
|
669 *
|
ziv@2234
|
670 * ceil(n/b) = (n/b) + ((n%b)?1:0)
|
ziv@2234
|
671 *
|
ziv@2234
|
672 * and in fact a previous version of this hash did just that.
|
ziv@2234
|
673 * But now we have improved things a bit by recognizing that b is
|
ziv@2234
|
674 * always a power of two. We keep its base 2 log handy (call it lb),
|
ziv@2234
|
675 * so now we can write this with a bit shift and logical AND:
|
ziv@2234
|
676 *
|
ziv@2234
|
677 * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0)
|
ziv@2234
|
678 *
|
ziv@2234
|
679 */
|
ziv@2234
|
680 #define HASH_EXPAND_BUCKETS(tbl) \
|
ziv@2234
|
681 do { \
|
ziv@2234
|
682 unsigned _he_bkt; \
|
ziv@2234
|
683 unsigned _he_bkt_i; \
|
ziv@2234
|
684 struct UT_hash_handle *_he_thh, *_he_hh_nxt; \
|
ziv@2234
|
685 UT_hash_bucket *_he_new_buckets, *_he_newbkt; \
|
ziv@2234
|
686 _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \
|
ziv@2234
|
687 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
|
ziv@2234
|
688 if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \
|
ziv@2234
|
689 memset(_he_new_buckets, 0, \
|
ziv@2234
|
690 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
|
ziv@2234
|
691 tbl->ideal_chain_maxlen = \
|
ziv@2234
|
692 (tbl->num_items >> (tbl->log2_num_buckets+1U)) + \
|
ziv@2234
|
693 (((tbl->num_items & ((tbl->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \
|
ziv@2234
|
694 tbl->nonideal_items = 0; \
|
ziv@2234
|
695 for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \
|
ziv@2234
|
696 { \
|
ziv@2234
|
697 _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \
|
ziv@2234
|
698 while (_he_thh != NULL) { \
|
ziv@2234
|
699 _he_hh_nxt = _he_thh->hh_next; \
|
ziv@2234
|
700 HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2U, _he_bkt); \
|
ziv@2234
|
701 _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \
|
ziv@2234
|
702 if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \
|
ziv@2234
|
703 tbl->nonideal_items++; \
|
ziv@2234
|
704 _he_newbkt->expand_mult = _he_newbkt->count / \
|
ziv@2234
|
705 tbl->ideal_chain_maxlen; \
|
ziv@2234
|
706 } \
|
ziv@2234
|
707 _he_thh->hh_prev = NULL; \
|
ziv@2234
|
708 _he_thh->hh_next = _he_newbkt->hh_head; \
|
ziv@2234
|
709 if (_he_newbkt->hh_head != NULL) { _he_newbkt->hh_head->hh_prev = \
|
ziv@2234
|
710 _he_thh; } \
|
ziv@2234
|
711 _he_newbkt->hh_head = _he_thh; \
|
ziv@2234
|
712 _he_thh = _he_hh_nxt; \
|
ziv@2234
|
713 } \
|
ziv@2234
|
714 } \
|
ziv@2234
|
715 uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \
|
ziv@2234
|
716 tbl->num_buckets *= 2U; \
|
ziv@2234
|
717 tbl->log2_num_buckets++; \
|
ziv@2234
|
718 tbl->buckets = _he_new_buckets; \
|
ziv@2234
|
719 tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \
|
ziv@2234
|
720 (tbl->ineff_expands+1U) : 0U; \
|
ziv@2234
|
721 if (tbl->ineff_expands > 1U) { \
|
ziv@2234
|
722 tbl->noexpand=1; \
|
ziv@2234
|
723 uthash_noexpand_fyi(tbl); \
|
ziv@2234
|
724 } \
|
ziv@2234
|
725 uthash_expand_fyi(tbl); \
|
ziv@2234
|
726 } while(0)
|
ziv@2234
|
727
|
ziv@2234
|
728
|
ziv@2234
|
729 /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
|
ziv@2234
|
730 /* Note that HASH_SORT assumes the hash handle name to be hh.
|
ziv@2234
|
731 * HASH_SRT was added to allow the hash handle name to be passed in. */
|
ziv@2234
|
732 #define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn)
|
ziv@2234
|
733 #define HASH_SRT(hh,head,cmpfcn) \
|
ziv@2234
|
734 do { \
|
ziv@2234
|
735 unsigned _hs_i; \
|
ziv@2234
|
736 unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \
|
ziv@2234
|
737 struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \
|
ziv@2234
|
738 if (head != NULL) { \
|
ziv@2234
|
739 _hs_insize = 1; \
|
ziv@2234
|
740 _hs_looping = 1; \
|
ziv@2234
|
741 _hs_list = &((head)->hh); \
|
ziv@2234
|
742 while (_hs_looping != 0U) { \
|
ziv@2234
|
743 _hs_p = _hs_list; \
|
ziv@2234
|
744 _hs_list = NULL; \
|
ziv@2234
|
745 _hs_tail = NULL; \
|
ziv@2234
|
746 _hs_nmerges = 0; \
|
ziv@2234
|
747 while (_hs_p != NULL) { \
|
ziv@2234
|
748 _hs_nmerges++; \
|
ziv@2234
|
749 _hs_q = _hs_p; \
|
ziv@2234
|
750 _hs_psize = 0; \
|
ziv@2234
|
751 for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \
|
ziv@2234
|
752 _hs_psize++; \
|
ziv@2234
|
753 _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \
|
ziv@2234
|
754 ((void*)((char*)(_hs_q->next) + \
|
ziv@2234
|
755 (head)->hh.tbl->hho)) : NULL); \
|
ziv@2234
|
756 if (! (_hs_q) ) { break; } \
|
ziv@2234
|
757 } \
|
ziv@2234
|
758 _hs_qsize = _hs_insize; \
|
ziv@2234
|
759 while ((_hs_psize > 0U) || ((_hs_qsize > 0U) && (_hs_q != NULL))) {\
|
ziv@2234
|
760 if (_hs_psize == 0U) { \
|
ziv@2234
|
761 _hs_e = _hs_q; \
|
ziv@2234
|
762 _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \
|
ziv@2234
|
763 ((void*)((char*)(_hs_q->next) + \
|
ziv@2234
|
764 (head)->hh.tbl->hho)) : NULL); \
|
ziv@2234
|
765 _hs_qsize--; \
|
ziv@2234
|
766 } else if ( (_hs_qsize == 0U) || (_hs_q == NULL) ) { \
|
ziv@2234
|
767 _hs_e = _hs_p; \
|
ziv@2234
|
768 if (_hs_p != NULL){ \
|
ziv@2234
|
769 _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \
|
ziv@2234
|
770 ((void*)((char*)(_hs_p->next) + \
|
ziv@2234
|
771 (head)->hh.tbl->hho)) : NULL); \
|
ziv@2234
|
772 } \
|
ziv@2234
|
773 _hs_psize--; \
|
ziv@2234
|
774 } else if (( \
|
ziv@2234
|
775 cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \
|
ziv@2234
|
776 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \
|
ziv@2234
|
777 ) <= 0) { \
|
ziv@2234
|
778 _hs_e = _hs_p; \
|
ziv@2234
|
779 if (_hs_p != NULL){ \
|
ziv@2234
|
780 _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \
|
ziv@2234
|
781 ((void*)((char*)(_hs_p->next) + \
|
ziv@2234
|
782 (head)->hh.tbl->hho)) : NULL); \
|
ziv@2234
|
783 } \
|
ziv@2234
|
784 _hs_psize--; \
|
ziv@2234
|
785 } else { \
|
ziv@2234
|
786 _hs_e = _hs_q; \
|
ziv@2234
|
787 _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \
|
ziv@2234
|
788 ((void*)((char*)(_hs_q->next) + \
|
ziv@2234
|
789 (head)->hh.tbl->hho)) : NULL); \
|
ziv@2234
|
790 _hs_qsize--; \
|
ziv@2234
|
791 } \
|
ziv@2234
|
792 if ( _hs_tail != NULL ) { \
|
ziv@2234
|
793 _hs_tail->next = ((_hs_e != NULL) ? \
|
ziv@2234
|
794 ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \
|
ziv@2234
|
795 } else { \
|
ziv@2234
|
796 _hs_list = _hs_e; \
|
ziv@2234
|
797 } \
|
ziv@2234
|
798 if (_hs_e != NULL) { \
|
ziv@2234
|
799 _hs_e->prev = ((_hs_tail != NULL) ? \
|
ziv@2234
|
800 ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \
|
ziv@2234
|
801 } \
|
ziv@2234
|
802 _hs_tail = _hs_e; \
|
ziv@2234
|
803 } \
|
ziv@2234
|
804 _hs_p = _hs_q; \
|
ziv@2234
|
805 } \
|
ziv@2234
|
806 if (_hs_tail != NULL){ \
|
ziv@2234
|
807 _hs_tail->next = NULL; \
|
ziv@2234
|
808 } \
|
ziv@2234
|
809 if ( _hs_nmerges <= 1U ) { \
|
ziv@2234
|
810 _hs_looping=0; \
|
ziv@2234
|
811 (head)->hh.tbl->tail = _hs_tail; \
|
ziv@2234
|
812 DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \
|
ziv@2234
|
813 } \
|
ziv@2234
|
814 _hs_insize *= 2U; \
|
ziv@2234
|
815 } \
|
ziv@2234
|
816 HASH_FSCK(hh,head); \
|
ziv@2234
|
817 } \
|
ziv@2234
|
818 } while (0)
|
ziv@2234
|
819
|
ziv@2234
|
820 /* This function selects items from one hash into another hash.
|
ziv@2234
|
821 * The end result is that the selected items have dual presence
|
ziv@2234
|
822 * in both hashes. There is no copy of the items made; rather
|
ziv@2234
|
823 * they are added into the new hash through a secondary hash
|
ziv@2234
|
824 * hash handle that must be present in the structure. */
|
ziv@2234
|
825 #define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \
|
ziv@2234
|
826 do { \
|
ziv@2234
|
827 unsigned _src_bkt, _dst_bkt; \
|
ziv@2234
|
828 void *_last_elt=NULL, *_elt; \
|
ziv@2234
|
829 UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \
|
ziv@2234
|
830 ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \
|
ziv@2234
|
831 if (src != NULL) { \
|
ziv@2234
|
832 for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \
|
ziv@2234
|
833 for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \
|
ziv@2234
|
834 _src_hh != NULL; \
|
ziv@2234
|
835 _src_hh = _src_hh->hh_next) { \
|
ziv@2234
|
836 _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \
|
ziv@2234
|
837 if (cond(_elt)) { \
|
ziv@2234
|
838 _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \
|
ziv@2234
|
839 _dst_hh->key = _src_hh->key; \
|
ziv@2234
|
840 _dst_hh->keylen = _src_hh->keylen; \
|
ziv@2234
|
841 _dst_hh->hashv = _src_hh->hashv; \
|
ziv@2234
|
842 _dst_hh->prev = _last_elt; \
|
ziv@2234
|
843 _dst_hh->next = NULL; \
|
ziv@2234
|
844 if (_last_elt_hh != NULL) { _last_elt_hh->next = _elt; } \
|
ziv@2234
|
845 if (dst == NULL) { \
|
ziv@2234
|
846 DECLTYPE_ASSIGN(dst,_elt); \
|
ziv@2234
|
847 HASH_MAKE_TABLE(hh_dst,dst); \
|
ziv@2234
|
848 } else { \
|
ziv@2234
|
849 _dst_hh->tbl = (dst)->hh_dst.tbl; \
|
ziv@2234
|
850 } \
|
ziv@2234
|
851 HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \
|
ziv@2234
|
852 HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \
|
ziv@2234
|
853 (dst)->hh_dst.tbl->num_items++; \
|
ziv@2234
|
854 _last_elt = _elt; \
|
ziv@2234
|
855 _last_elt_hh = _dst_hh; \
|
ziv@2234
|
856 } \
|
ziv@2234
|
857 } \
|
ziv@2234
|
858 } \
|
ziv@2234
|
859 } \
|
ziv@2234
|
860 HASH_FSCK(hh_dst,dst); \
|
ziv@2234
|
861 } while (0)
|
ziv@2234
|
862
|
ziv@2234
|
863 #define HASH_CLEAR(hh,head) \
|
ziv@2234
|
864 do { \
|
ziv@2234
|
865 if (head != NULL) { \
|
ziv@2234
|
866 uthash_free((head)->hh.tbl->buckets, \
|
ziv@2234
|
867 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \
|
ziv@2234
|
868 HASH_BLOOM_FREE((head)->hh.tbl); \
|
ziv@2234
|
869 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
|
ziv@2234
|
870 (head)=NULL; \
|
ziv@2234
|
871 } \
|
ziv@2234
|
872 } while(0)
|
ziv@2234
|
873
|
ziv@2234
|
874 #define HASH_OVERHEAD(hh,head) \
|
ziv@2234
|
875 ((head != NULL) ? ( \
|
ziv@2234
|
876 (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \
|
ziv@2234
|
877 ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \
|
ziv@2234
|
878 sizeof(UT_hash_table) + \
|
ziv@2234
|
879 (HASH_BLOOM_BYTELEN))) : 0U)
|
ziv@2234
|
880
|
ziv@2234
|
881 #ifdef NO_DECLTYPE
|
ziv@2234
|
882 #define HASH_ITER(hh,head,el,tmp) \
|
ziv@2234
|
883 for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \
|
ziv@2234
|
884 (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL)))
|
ziv@2234
|
885 #else
|
ziv@2234
|
886 #define HASH_ITER(hh,head,el,tmp) \
|
ziv@2234
|
887 for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \
|
ziv@2234
|
888 (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL)))
|
ziv@2234
|
889 #endif
|
ziv@2234
|
890
|
ziv@2234
|
891 /* obtain a count of items in the hash */
|
ziv@2234
|
892 #define HASH_COUNT(head) HASH_CNT(hh,head)
|
ziv@2234
|
893 #define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U)
|
ziv@2234
|
894
|
ziv@2234
|
895 typedef struct UT_hash_bucket {
|
ziv@2234
|
896 struct UT_hash_handle *hh_head;
|
ziv@2234
|
897 unsigned count;
|
ziv@2234
|
898
|
ziv@2234
|
899 /* expand_mult is normally set to 0. In this situation, the max chain length
|
ziv@2234
|
900 * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If
|
ziv@2234
|
901 * the bucket's chain exceeds this length, bucket expansion is triggered).
|
ziv@2234
|
902 * However, setting expand_mult to a non-zero value delays bucket expansion
|
ziv@2234
|
903 * (that would be triggered by additions to this particular bucket)
|
ziv@2234
|
904 * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH.
|
ziv@2234
|
905 * (The multiplier is simply expand_mult+1). The whole idea of this
|
ziv@2234
|
906 * multiplier is to reduce bucket expansions, since they are expensive, in
|
ziv@2234
|
907 * situations where we know that a particular bucket tends to be overused.
|
ziv@2234
|
908 * It is better to let its chain length grow to a longer yet-still-bounded
|
ziv@2234
|
909 * value, than to do an O(n) bucket expansion too often.
|
ziv@2234
|
910 */
|
ziv@2234
|
911 unsigned expand_mult;
|
ziv@2234
|
912
|
ziv@2234
|
913 } UT_hash_bucket;
|
ziv@2234
|
914
|
ziv@2234
|
915 /* random signature used only to find hash tables in external analysis */
|
ziv@2234
|
916 #define HASH_SIGNATURE 0xa0111fe1u
|
ziv@2234
|
917 #define HASH_BLOOM_SIGNATURE 0xb12220f2u
|
ziv@2234
|
918
|
ziv@2234
|
919 typedef struct UT_hash_table {
|
ziv@2234
|
920 UT_hash_bucket *buckets;
|
ziv@2234
|
921 unsigned num_buckets, log2_num_buckets;
|
ziv@2234
|
922 unsigned num_items;
|
ziv@2234
|
923 struct UT_hash_handle *tail; /* tail hh in app order, for fast append */
|
ziv@2234
|
924 ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */
|
ziv@2234
|
925
|
ziv@2234
|
926 /* in an ideal situation (all buckets used equally), no bucket would have
|
ziv@2234
|
927 * more than ceil(#items/#buckets) items. that's the ideal chain length. */
|
ziv@2234
|
928 unsigned ideal_chain_maxlen;
|
ziv@2234
|
929
|
ziv@2234
|
930 /* nonideal_items is the number of items in the hash whose chain position
|
ziv@2234
|
931 * exceeds the ideal chain maxlen. these items pay the penalty for an uneven
|
ziv@2234
|
932 * hash distribution; reaching them in a chain traversal takes >ideal steps */
|
ziv@2234
|
933 unsigned nonideal_items;
|
ziv@2234
|
934
|
ziv@2234
|
935 /* ineffective expands occur when a bucket doubling was performed, but
|
ziv@2234
|
936 * afterward, more than half the items in the hash had nonideal chain
|
ziv@2234
|
937 * positions. If this happens on two consecutive expansions we inhibit any
|
ziv@2234
|
938 * further expansion, as it's not helping; this happens when the hash
|
ziv@2234
|
939 * function isn't a good fit for the key domain. When expansion is inhibited
|
ziv@2234
|
940 * the hash will still work, albeit no longer in constant time. */
|
ziv@2234
|
941 unsigned ineff_expands, noexpand;
|
ziv@2234
|
942
|
ziv@2234
|
943 uint32_t signature; /* used only to find hash tables in external analysis */
|
ziv@2234
|
944 #ifdef HASH_BLOOM
|
ziv@2234
|
945 uint32_t bloom_sig; /* used only to test bloom exists in external analysis */
|
ziv@2234
|
946 uint8_t *bloom_bv;
|
ziv@2234
|
947 uint8_t bloom_nbits;
|
ziv@2234
|
948 #endif
|
ziv@2234
|
949
|
ziv@2234
|
950 } UT_hash_table;
|
ziv@2234
|
951
|
ziv@2234
|
952 typedef struct UT_hash_handle {
|
ziv@2234
|
953 struct UT_hash_table *tbl;
|
ziv@2234
|
954 void *prev; /* prev element in app order */
|
ziv@2234
|
955 void *next; /* next element in app order */
|
ziv@2234
|
956 struct UT_hash_handle *hh_prev; /* previous hh in bucket order */
|
ziv@2234
|
957 struct UT_hash_handle *hh_next; /* next hh in bucket order */
|
ziv@2234
|
958 void *key; /* ptr to enclosing struct's key */
|
ziv@2234
|
959 unsigned keylen; /* enclosing struct's key len */
|
ziv@2234
|
960 unsigned hashv; /* result of hash-fcn(key) */
|
ziv@2234
|
961 } UT_hash_handle;
|
ziv@2234
|
962
|
ziv@2234
|
963 #endif /* UTHASH_H */
|