?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
modified: diffout.py
[GalaxyCodeBases.git] / c_cpp / lib / uthash / src / uthash.h
blob46edea0e64a258296390b6c40d7318f8717f09d7
1 /*
2 Copyright (c) 2003-2017, 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.2
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 void *_hs_iter = (head); \
246 (add)->hh.tbl = (head)->hh.tbl; \
247 do { \
248 if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) \
249 break; \
250 } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \
251 if (_hs_iter) { \
252 (add)->hh.next = _hs_iter; \
253 if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) { \
254 HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add); \
255 } else { \
256 (head) = (add); \
257 } \
258 HH_FROM_ELMT((head)->hh.tbl, _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 */
A place to share codes with mates