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