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