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