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