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