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