Mercurial > urweb

comparison include/urweb/uthash.h @ 2234:2f7ed04332a0

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