XBPS Library API
20250624
The X Binary Package System
Main Page
Topics
Data Structures
include
uthash.h
1
/*
2
Copyright (c) 2003-2025, Troy D. Hanson https://troydhanson.github.io/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.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) \
63
do { \
64
char **_da_dst = (char**)(&(dst)); \
65
*_da_dst = (char*)(src); \
66
} while (0)
67
#else
68
#define DECLTYPE_ASSIGN(dst,src) \
69
do { \
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) \
139
do { \
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) \
149
do { \
150
HASH_FUNCTION(keyptr, keylen, hashv); \
151
} while (0)
152
153
#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \
154
do { \
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) \
166
do { \
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) \
179
do { \
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) \
191
do { \
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) \
213
do { \
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) \
245
do { \
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) \
255
do { \
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) \
265
do { \
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) \
272
do { \
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) \
279
do { \
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) \
287
do { \
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) \
298
do { \
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) \
314
do { \
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) \
338
do { \
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) \
351
do { \
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) \
384
do { \
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) \
397
do { \
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) \
418
do { \
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) \
431
do { \
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) \
451
do { \
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) \
481
do { \
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) \
486
do { \
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) \
491
do { \
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) \
517
do { \
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) \
573
do { \
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) \
584
do { \
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) \
599
do { \
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) \
609
do { \
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) \
620
do { \
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) \
635
do { \
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) \
648
do { \
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) \
700
do { \
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) \
746
do { \
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) \
768
do { \
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) \
790
do { \
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) \
834
do { \
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) \
891
do { \
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) \
980
do { \
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) \
1038
do { \
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) \
1057
for(((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) \
1061
for(((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
1069
typedef
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
1093
typedef
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
1126
typedef
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_handle
Definition
uthash.h:1126
UT_hash_table
Definition
uthash.h:1093
Generated on
for XBPS Library API by
1.14.0
1.14.0