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