StarPU Internal Handbook

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