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