P4C
The P4 Compiler
Loading...
Searching...
No Matches
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.0.2
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_memcmp
92
#define uthash_memcmp(a,b,n) memcmp(a,b,n)
93
#endif
94
#ifndef uthash_strlen
95
#define uthash_strlen(s) strlen(s)
96
#endif
97
98
#ifndef uthash_noexpand_fyi
99
#define uthash_noexpand_fyi(tbl)
/* can be defined to log noexpand */
100
#endif
101
#ifndef uthash_expand_fyi
102
#define uthash_expand_fyi(tbl)
/* can be defined to log expands */
103
#endif
104
105
#ifndef HASH_NONFATAL_OOM
106
#define HASH_NONFATAL_OOM 0
107
#endif
108
109
#if HASH_NONFATAL_OOM
110
/* malloc failures can be recovered from */
111
112
#ifndef uthash_nonfatal_oom
113
#define uthash_nonfatal_oom(obj) do {} while (0)
/* non-fatal OOM error */
114
#endif
115
116
#define HASH_RECORD_OOM(oomed) do { (oomed) = 1; } while (0)
117
#define IF_HASH_NONFATAL_OOM(x) x
118
119
#else
120
/* malloc failures result in lost memory, hash tables are unusable */
121
122
#ifndef uthash_fatal
123
#define uthash_fatal(msg) exit(-1)
/* fatal OOM error */
124
#endif
125
126
#define HASH_RECORD_OOM(oomed) uthash_fatal("out of memory")
127
#define IF_HASH_NONFATAL_OOM(x)
128
129
#endif
130
131
/* initial number of buckets */
132
#define HASH_INITIAL_NUM_BUCKETS 32U
/* initial number of buckets */
133
#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U
/* lg2 of initial number of buckets */
134
#define HASH_BKT_CAPACITY_THRESH 10U
/* expand when bucket count reaches */
135
136
/* calculate the element whose hash handle address is hhp */
137
#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
138
/* calculate the hash handle from element address elp */
139
#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle *)(((char*)(elp)) + ((tbl)->hho)))
140
141
#define HASH_ROLLBACK_BKT(hh, head, itemptrhh) \
142
do { \
143
struct UT_hash_handle *_hd_hh_item = (itemptrhh); \
144
unsigned _hd_bkt; \
145
HASH_TO_BKT(_hd_hh_item->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \
146
(head)->hh.tbl->buckets[_hd_bkt].count++; \
147
_hd_hh_item->hh_next = NULL; \
148
_hd_hh_item->hh_prev = NULL; \
149
} while (0)
150
151
#define HASH_VALUE(keyptr,keylen,hashv) \
152
do { \
153
HASH_FCN(keyptr, keylen, hashv); \
154
} while (0)
155
156
#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \
157
do { \
158
(out) = NULL; \
159
if (head) { \
160
unsigned _hf_bkt; \
161
HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \
162
if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \
163
HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \
164
} \
165
} \
166
} while (0)
167
168
#define HASH_FIND(hh,head,keyptr,keylen,out) \
169
do { \
170
unsigned _hf_hashv; \
171
HASH_VALUE(keyptr, keylen, _hf_hashv); \
172
HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \
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)))
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 = (char*) (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
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
#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
515
#define HASH_FSCK(hh,head,where) \
516
do { \
517
struct UT_hash_handle *_thh; \
518
if (head) { \
519
unsigned _bkt_i; \
520
unsigned _count = 0; \
521
char *_prev; \
522
for (_bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; ++_bkt_i) { \
523
unsigned _bkt_count = 0; \
524
_thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \
525
_prev = NULL; \
526
while (_thh) { \
527
if (_prev != (char*)(_thh->hh_prev)) { \
528
HASH_OOPS("%s: invalid hh_prev %p, actual %p\n", \
529
(where), (void*)_thh->hh_prev, (void*)_prev); \
530
} \
531
_bkt_count++; \
532
_prev = (char*)(_thh); \
533
_thh = _thh->hh_next; \
534
} \
535
_count += _bkt_count; \
536
if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \
537
HASH_OOPS("%s: invalid bucket count %u, actual %u\n", \
538
(where), (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \
539
} \
540
} \
541
if (_count != (head)->hh.tbl->num_items) { \
542
HASH_OOPS("%s: invalid hh item count %u, actual %u\n", \
543
(where), (head)->hh.tbl->num_items, _count); \
544
} \
545
_count = 0; \
546
_prev = NULL; \
547
_thh = &(head)->hh; \
548
while (_thh) { \
549
_count++; \
550
if (_prev != (char*)_thh->prev) { \
551
HASH_OOPS("%s: invalid prev %p, actual %p\n", \
552
(where), (void*)_thh->prev, (void*)_prev); \
553
} \
554
_prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \
555
_thh = (_thh->next ? HH_FROM_ELMT((head)->hh.tbl, _thh->next) : NULL); \
556
} \
557
if (_count != (head)->hh.tbl->num_items) { \
558
HASH_OOPS("%s: invalid app item count %u, actual %u\n", \
559
(where), (head)->hh.tbl->num_items, _count); \
560
} \
561
} \
562
} while (0)
563
#else
564
#define HASH_FSCK(hh,head,where)
565
#endif
566
567
/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to
568
* the descriptor to which this macro is defined for tuning the hash function.
569
* The app can #include <unistd.h> to get the prototype for write(2). */
570
#ifdef HASH_EMIT_KEYS
571
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \
572
do { \
573
unsigned _klen = fieldlen; \
574
write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \
575
write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \
576
} while (0)
577
#else
578
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)
579
#endif
580
581
/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */
582
#ifdef HASH_FUNCTION
583
#define HASH_FCN HASH_FUNCTION
584
#else
585
#define HASH_FCN HASH_JEN
586
#endif
587
588
/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */
589
#define HASH_BER(key,keylen,hashv) \
590
do { \
591
unsigned _hb_keylen = (unsigned)keylen; \
592
const unsigned char *_hb_key = (const unsigned char*)(key); \
593
(hashv) = 0; \
594
while (_hb_keylen-- != 0U) { \
595
(hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \
596
} \
597
} while (0)
598
599
600
/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at
601
* http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
602
#define HASH_SAX(key,keylen,hashv) \
603
do { \
604
unsigned _sx_i; \
605
const unsigned char *_hs_key = (const unsigned char*)(key); \
606
hashv = 0; \
607
for (_sx_i=0; _sx_i < keylen; _sx_i++) { \
608
hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \
609
} \
610
} while (0)
611
/* FNV-1a variation */
612
#define HASH_FNV(key,keylen,hashv) \
613
do { \
614
unsigned _fn_i; \
615
const unsigned char *_hf_key = (const unsigned char*)(key); \
616
(hashv) = 2166136261U; \
617
for (_fn_i=0; _fn_i < keylen; _fn_i++) { \
618
hashv = hashv ^ _hf_key[_fn_i]; \
619
hashv = hashv * 16777619U; \
620
} \
621
} while (0)
622
623
#define HASH_OAT(key,keylen,hashv) \
624
do { \
625
unsigned _ho_i; \
626
const unsigned char *_ho_key=(const unsigned char*)(key); \
627
hashv = 0; \
628
for(_ho_i=0; _ho_i < keylen; _ho_i++) { \
629
hashv += _ho_key[_ho_i]; \
630
hashv += (hashv << 10); \
631
hashv ^= (hashv >> 6); \
632
} \
633
hashv += (hashv << 3); \
634
hashv ^= (hashv >> 11); \
635
hashv += (hashv << 15); \
636
} while (0)
637
638
#define HASH_JEN_MIX(a,b,c) \
639
do { \
640
a -= b; a -= c; a ^= ( c >> 13 ); \
641
b -= c; b -= a; b ^= ( a << 8 ); \
642
c -= a; c -= b; c ^= ( b >> 13 ); \
643
a -= b; a -= c; a ^= ( c >> 12 ); \
644
b -= c; b -= a; b ^= ( a << 16 ); \
645
c -= a; c -= b; c ^= ( b >> 5 ); \
646
a -= b; a -= c; a ^= ( c >> 3 ); \
647
b -= c; b -= a; b ^= ( a << 10 ); \
648
c -= a; c -= b; c ^= ( b >> 15 ); \
649
} while (0)
650
651
#define HASH_JEN(key,keylen,hashv) \
652
do { \
653
unsigned _hj_i,_hj_j,_hj_k; \
654
unsigned const char *_hj_key=(unsigned const char*)(key); \
655
hashv = 0xfeedbeefu; \
656
_hj_i = _hj_j = 0x9e3779b9u; \
657
_hj_k = (unsigned)(keylen); \
658
while (_hj_k >= 12U) { \
659
_hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \
660
+ ( (unsigned)_hj_key[2] << 16 ) \
661
+ ( (unsigned)_hj_key[3] << 24 ) ); \
662
_hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \
663
+ ( (unsigned)_hj_key[6] << 16 ) \
664
+ ( (unsigned)_hj_key[7] << 24 ) ); \
665
hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \
666
+ ( (unsigned)_hj_key[10] << 16 ) \
667
+ ( (unsigned)_hj_key[11] << 24 ) ); \
668
\
669
HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
670
\
671
_hj_key += 12; \
672
_hj_k -= 12U; \
673
} \
674
hashv += (unsigned)(keylen); \
675
switch ( _hj_k ) { \
676
case 11: hashv += ( (unsigned)_hj_key[10] << 24 );
/* FALLTHROUGH */
\
677
case 10: hashv += ( (unsigned)_hj_key[9] << 16 );
/* FALLTHROUGH */
\
678
case 9: hashv += ( (unsigned)_hj_key[8] << 8 );
/* FALLTHROUGH */
\
679
case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 );
/* FALLTHROUGH */
\
680
case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 );
/* FALLTHROUGH */
\
681
case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 );
/* FALLTHROUGH */
\
682
case 5: _hj_j += _hj_key[4];
/* FALLTHROUGH */
\
683
case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 );
/* FALLTHROUGH */
\
684
case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 );
/* FALLTHROUGH */
\
685
case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 );
/* FALLTHROUGH */
\
686
case 1: _hj_i += _hj_key[0]; \
687
} \
688
HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
689
} while (0)
690
691
/* The Paul Hsieh hash function */
692
#undef get16bits
693
#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
694
|| defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
695
#define get16bits(d) (*((const uint16_t *) (d)))
696
#endif
697
698
#if !defined (get16bits)
699
#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
700
+(uint32_t)(((const uint8_t *)(d))[0]) )
701
#endif
702
#define HASH_SFH(key,keylen,hashv) \
703
do { \
704
unsigned const char *_sfh_key=(unsigned const char*)(key); \
705
uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \
706
\
707
unsigned _sfh_rem = _sfh_len & 3U; \
708
_sfh_len >>= 2; \
709
hashv = 0xcafebabeu; \
710
\
711
/* Main loop */
\
712
for (;_sfh_len > 0U; _sfh_len--) { \
713
hashv += get16bits (_sfh_key); \
714
_sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \
715
hashv = (hashv << 16) ^ _sfh_tmp; \
716
_sfh_key += 2U*sizeof (uint16_t); \
717
hashv += hashv >> 11; \
718
} \
719
\
720
/* Handle end cases */
\
721
switch (_sfh_rem) { \
722
case 3: hashv += get16bits (_sfh_key); \
723
hashv ^= hashv << 16; \
724
hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \
725
hashv += hashv >> 11; \
726
break; \
727
case 2: hashv += get16bits (_sfh_key); \
728
hashv ^= hashv << 11; \
729
hashv += hashv >> 17; \
730
break; \
731
case 1: hashv += *_sfh_key; \
732
hashv ^= hashv << 10; \
733
hashv += hashv >> 1; \
734
} \
735
\
736
/* Force "avalanching" of final 127 bits */
\
737
hashv ^= hashv << 3; \
738
hashv += hashv >> 5; \
739
hashv ^= hashv << 4; \
740
hashv += hashv >> 17; \
741
hashv ^= hashv << 25; \
742
hashv += hashv >> 6; \
743
} while (0)
744
745
#ifdef HASH_USING_NO_STRICT_ALIASING
746
/* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads.
747
* For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error.
748
* MurmurHash uses the faster approach only on CPU's where we know it's safe.
749
*
750
* Note the preprocessor built-in defines can be emitted using:
751
*
752
* gcc -m64 -dM -E - < /dev/null (on GCC)
753
* cc -## a.c (where a.c is a simple test file) (Sun Studio)
754
*/
755
#if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86))
756
#define MUR_GETBLOCK(p,i) p[i]
757
#else
/* non intel */
758
#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL)
759
#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL)
760
#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL)
761
#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL)
762
#define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL))
763
#if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__))
764
#define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24))
765
#define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16))
766
#define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8))
767
#else
/* assume little endian non-intel */
768
#define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24))
769
#define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16))
770
#define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8))
771
#endif
772
#define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \
773
(MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \
774
(MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \
775
MUR_ONE_THREE(p))))
776
#endif
777
#define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
778
#define MUR_FMIX(_h) \
779
do { \
780
_h ^= _h >> 16; \
781
_h *= 0x85ebca6bu; \
782
_h ^= _h >> 13; \
783
_h *= 0xc2b2ae35u; \
784
_h ^= _h >> 16; \
785
} while (0)
786
787
#define HASH_MUR(key,keylen,hashv) \
788
do { \
789
const uint8_t *_mur_data = (const uint8_t*)(key); \
790
const int _mur_nblocks = (int)(keylen) / 4; \
791
uint32_t _mur_h1 = 0xf88D5353u; \
792
uint32_t _mur_c1 = 0xcc9e2d51u; \
793
uint32_t _mur_c2 = 0x1b873593u; \
794
uint32_t _mur_k1 = 0; \
795
const uint8_t *_mur_tail; \
796
const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \
797
int _mur_i; \
798
for (_mur_i = -_mur_nblocks; _mur_i != 0; _mur_i++) { \
799
_mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \
800
_mur_k1 *= _mur_c1; \
801
_mur_k1 = MUR_ROTL32(_mur_k1,15); \
802
_mur_k1 *= _mur_c2; \
803
\
804
_mur_h1 ^= _mur_k1; \
805
_mur_h1 = MUR_ROTL32(_mur_h1,13); \
806
_mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \
807
} \
808
_mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \
809
_mur_k1=0; \
810
switch ((keylen) & 3U) { \
811
case 0: break; \
812
case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16;
/* FALLTHROUGH */
\
813
case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8;
/* FALLTHROUGH */
\
814
case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \
815
_mur_k1 *= _mur_c1; \
816
_mur_k1 = MUR_ROTL32(_mur_k1,15); \
817
_mur_k1 *= _mur_c2; \
818
_mur_h1 ^= _mur_k1; \
819
} \
820
_mur_h1 ^= (uint32_t)(keylen); \
821
MUR_FMIX(_mur_h1); \
822
hashv = _mur_h1; \
823
} while (0)
824
#endif
/* HASH_USING_NO_STRICT_ALIASING */
825
826
/* iterate over items in a known bucket to find desired item */
827
#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \
828
do { \
829
if ((head).hh_head != NULL) { \
830
DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \
831
} else { \
832
(out) = NULL; \
833
} \
834
while ((out) != NULL) { \
835
if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \
836
if (uthash_memcmp((out)->hh.key, keyptr, keylen_in) == 0) { \
837
break; \
838
} \
839
} \
840
if ((out)->hh.hh_next != NULL) { \
841
DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \
842
} else { \
843
(out) = NULL; \
844
} \
845
} \
846
} while (0)
847
848
/* add an item to a bucket */
849
#define HASH_ADD_TO_BKT(head,hh,addhh,oomed) \
850
do { \
851
UT_hash_bucket *_ha_head = &(head); \
852
_ha_head->count++; \
853
(addhh)->hh_next = _ha_head->hh_head; \
854
(addhh)->hh_prev = NULL; \
855
if (_ha_head->hh_head != NULL) { \
856
_ha_head->hh_head->hh_prev = (addhh); \
857
} \
858
_ha_head->hh_head = (addhh); \
859
if ((_ha_head->count >= ((_ha_head->expand_mult + 1U) * HASH_BKT_CAPACITY_THRESH)) \
860
&& !(addhh)->tbl->noexpand) { \
861
HASH_EXPAND_BUCKETS(addhh,(addhh)->tbl, oomed); \
862
IF_HASH_NONFATAL_OOM( \
863
if (oomed) { \
864
HASH_DEL_IN_BKT(head,addhh); \
865
} \
866
) \
867
} \
868
} while (0)
869
870
/* remove an item from a given bucket */
871
#define HASH_DEL_IN_BKT(head,delhh) \
872
do { \
873
UT_hash_bucket *_hd_head = &(head); \
874
_hd_head->count--; \
875
if (_hd_head->hh_head == (delhh)) { \
876
_hd_head->hh_head = (delhh)->hh_next; \
877
} \
878
if ((delhh)->hh_prev) { \
879
(delhh)->hh_prev->hh_next = (delhh)->hh_next; \
880
} \
881
if ((delhh)->hh_next) { \
882
(delhh)->hh_next->hh_prev = (delhh)->hh_prev; \
883
} \
884
} while (0)
885
886
/* Bucket expansion has the effect of doubling the number of buckets
887
* and redistributing the items into the new buckets. Ideally the
888
* items will distribute more or less evenly into the new buckets
889
* (the extent to which this is true is a measure of the quality of
890
* the hash function as it applies to the key domain).
891
*
892
* With the items distributed into more buckets, the chain length
893
* (item count) in each bucket is reduced. Thus by expanding buckets
894
* the hash keeps a bound on the chain length. This bounded chain
895
* length is the essence of how a hash provides constant time lookup.
896
*
897
* The calculation of tbl->ideal_chain_maxlen below deserves some
898
* explanation. First, keep in mind that we're calculating the ideal
899
* maximum chain length based on the *new* (doubled) bucket count.
900
* In fractions this is just n/b (n=number of items,b=new num buckets).
901
* Since the ideal chain length is an integer, we want to calculate
902
* ceil(n/b). We don't depend on floating point arithmetic in this
903
* hash, so to calculate ceil(n/b) with integers we could write
904
*
905
* ceil(n/b) = (n/b) + ((n%b)?1:0)
906
*
907
* and in fact a previous version of this hash did just that.
908
* But now we have improved things a bit by recognizing that b is
909
* always a power of two. We keep its base 2 log handy (call it lb),
910
* so now we can write this with a bit shift and logical AND:
911
*
912
* ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0)
913
*
914
*/
915
#define HASH_EXPAND_BUCKETS(hh,tbl,oomed) \
916
do { \
917
unsigned _he_bkt; \
918
unsigned _he_bkt_i; \
919
struct UT_hash_handle *_he_thh, *_he_hh_nxt; \
920
UT_hash_bucket *_he_new_buckets, *_he_newbkt; \
921
_he_new_buckets = (UT_hash_bucket*)uthash_malloc( \
922
2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \
923
if (!_he_new_buckets) { \
924
HASH_RECORD_OOM(oomed); \
925
} else { \
926
uthash_bzero(_he_new_buckets, \
927
2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \
928
(tbl)->ideal_chain_maxlen = \
929
((tbl)->num_items >> ((tbl)->log2_num_buckets+1U)) + \
930
((((tbl)->num_items & (((tbl)->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \
931
(tbl)->nonideal_items = 0; \
932
for (_he_bkt_i = 0; _he_bkt_i < (tbl)->num_buckets; _he_bkt_i++) { \
933
_he_thh = (tbl)->buckets[ _he_bkt_i ].hh_head; \
934
while (_he_thh != NULL) { \
935
_he_hh_nxt = _he_thh->hh_next; \
936
HASH_TO_BKT(_he_thh->hashv, (tbl)->num_buckets * 2U, _he_bkt); \
937
_he_newbkt = &(_he_new_buckets[_he_bkt]); \
938
if (++(_he_newbkt->count) > (tbl)->ideal_chain_maxlen) { \
939
(tbl)->nonideal_items++; \
940
_he_newbkt->expand_mult = _he_newbkt->count / (tbl)->ideal_chain_maxlen; \
941
} \
942
_he_thh->hh_prev = NULL; \
943
_he_thh->hh_next = _he_newbkt->hh_head; \
944
if (_he_newbkt->hh_head != NULL) { \
945
_he_newbkt->hh_head->hh_prev = _he_thh; \
946
} \
947
_he_newbkt->hh_head = _he_thh; \
948
_he_thh = _he_hh_nxt; \
949
} \
950
} \
951
uthash_free((tbl)->buckets, (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \
952
(tbl)->num_buckets *= 2U; \
953
(tbl)->log2_num_buckets++; \
954
(tbl)->buckets = _he_new_buckets; \
955
(tbl)->ineff_expands = ((tbl)->nonideal_items > ((tbl)->num_items >> 1)) ? \
956
((tbl)->ineff_expands+1U) : 0U; \
957
if ((tbl)->ineff_expands > 1U) { \
958
(tbl)->noexpand = 1; \
959
uthash_noexpand_fyi(tbl); \
960
} \
961
uthash_expand_fyi(tbl); \
962
} \
963
} while (0)
964
965
966
/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
967
/* Note that HASH_SORT assumes the hash handle name to be hh.
968
* HASH_SRT was added to allow the hash handle name to be passed in. */
969
#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn)
970
#define HASH_SRT(hh,head,cmpfcn) \
971
do { \
972
unsigned _hs_i; \
973
unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \
974
struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \
975
if (head != NULL) { \
976
_hs_insize = 1; \
977
_hs_looping = 1; \
978
_hs_list = &((head)->hh); \
979
while (_hs_looping != 0U) { \
980
_hs_p = _hs_list; \
981
_hs_list = NULL; \
982
_hs_tail = NULL; \
983
_hs_nmerges = 0; \
984
while (_hs_p != NULL) { \
985
_hs_nmerges++; \
986
_hs_q = _hs_p; \
987
_hs_psize = 0; \
988
for (_hs_i = 0; _hs_i < _hs_insize; ++_hs_i) { \
989
_hs_psize++; \
990
_hs_q = ((_hs_q->next != NULL) ? \
991
HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \
992
if (_hs_q == NULL) { \
993
break; \
994
} \
995
} \
996
_hs_qsize = _hs_insize; \
997
while ((_hs_psize != 0U) || ((_hs_qsize != 0U) && (_hs_q != NULL))) { \
998
if (_hs_psize == 0U) { \
999
_hs_e = _hs_q; \
1000
_hs_q = ((_hs_q->next != NULL) ? \
1001
HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \
1002
_hs_qsize--; \
1003
} else if ((_hs_qsize == 0U) || (_hs_q == NULL)) { \
1004
_hs_e = _hs_p; \
1005
if (_hs_p != NULL) { \
1006
_hs_p = ((_hs_p->next != NULL) ? \
1007
HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \
1008
} \
1009
_hs_psize--; \
1010
} else if ((cmpfcn( \
1011
DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_p)), \
1012
DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_q)) \
1013
)) <= 0) { \
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 { \
1021
_hs_e = _hs_q; \
1022
_hs_q = ((_hs_q->next != NULL) ? \
1023
HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \
1024
_hs_qsize--; \
1025
} \
1026
if ( _hs_tail != NULL ) { \
1027
_hs_tail->next = ((_hs_e != NULL) ? \
1028
ELMT_FROM_HH((head)->hh.tbl, _hs_e) : NULL); \
1029
} else { \
1030
_hs_list = _hs_e; \
1031
} \
1032
if (_hs_e != NULL) { \
1033
_hs_e->prev = ((_hs_tail != NULL) ? \
1034
ELMT_FROM_HH((head)->hh.tbl, _hs_tail) : NULL); \
1035
} \
1036
_hs_tail = _hs_e; \
1037
} \
1038
_hs_p = _hs_q; \
1039
} \
1040
if (_hs_tail != NULL) { \
1041
_hs_tail->next = NULL; \
1042
} \
1043
if (_hs_nmerges <= 1U) { \
1044
_hs_looping = 0; \
1045
(head)->hh.tbl->tail = _hs_tail; \
1046
DECLTYPE_ASSIGN(head, ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \
1047
} \
1048
_hs_insize *= 2U; \
1049
} \
1050
HASH_FSCK(hh, head, "HASH_SRT"); \
1051
} \
1052
} while (0)
1053
1054
/* This function selects items from one hash into another hash.
1055
* The end result is that the selected items have dual presence
1056
* in both hashes. There is no copy of the items made; rather
1057
* they are added into the new hash through a secondary hash
1058
* hash handle that must be present in the structure. */
1059
#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \
1060
do { \
1061
unsigned _src_bkt, _dst_bkt; \
1062
void *_last_elt = NULL, *_elt; \
1063
UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \
1064
ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \
1065
if ((src) != NULL) { \
1066
for (_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \
1067
for (_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \
1068
_src_hh != NULL; \
1069
_src_hh = _src_hh->hh_next) { \
1070
_elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \
1071
if (cond(_elt)) { \
1072
IF_HASH_NONFATAL_OOM( int _hs_oomed = 0; ) \
1073
_dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \
1074
_dst_hh->key = _src_hh->key; \
1075
_dst_hh->keylen = _src_hh->keylen; \
1076
_dst_hh->hashv = _src_hh->hashv; \
1077
_dst_hh->prev = _last_elt; \
1078
_dst_hh->next = NULL; \
1079
if (_last_elt_hh != NULL) { \
1080
_last_elt_hh->next = _elt; \
1081
} \
1082
if ((dst) == NULL) { \
1083
DECLTYPE_ASSIGN(dst, _elt); \
1084
HASH_MAKE_TABLE(hh_dst, dst, _hs_oomed); \
1085
IF_HASH_NONFATAL_OOM( \
1086
if (_hs_oomed) { \
1087
uthash_nonfatal_oom(_elt); \
1088
(dst) = NULL; \
1089
continue; \
1090
} \
1091
) \
1092
} else { \
1093
_dst_hh->tbl = (dst)->hh_dst.tbl; \
1094
} \
1095
HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \
1096
HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt], hh_dst, _dst_hh, _hs_oomed); \
1097
(dst)->hh_dst.tbl->num_items++; \
1098
IF_HASH_NONFATAL_OOM( \
1099
if (_hs_oomed) { \
1100
HASH_ROLLBACK_BKT(hh_dst, dst, _dst_hh); \
1101
HASH_DELETE_HH(hh_dst, dst, _dst_hh); \
1102
_dst_hh->tbl = NULL; \
1103
uthash_nonfatal_oom(_elt); \
1104
continue; \
1105
} \
1106
) \
1107
HASH_BLOOM_ADD(_dst_hh->tbl, _dst_hh->hashv); \
1108
_last_elt = _elt; \
1109
_last_elt_hh = _dst_hh; \
1110
} \
1111
} \
1112
} \
1113
} \
1114
HASH_FSCK(hh_dst, dst, "HASH_SELECT"); \
1115
} while (0)
1116
1117
#define HASH_CLEAR(hh,head) \
1118
do { \
1119
if ((head) != NULL) { \
1120
HASH_BLOOM_FREE((head)->hh.tbl); \
1121
uthash_free((head)->hh.tbl->buckets, \
1122
(head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \
1123
uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
1124
(head) = NULL; \
1125
} \
1126
} while (0)
1127
1128
#define HASH_OVERHEAD(hh,head) \
1129
(((head) != NULL) ? ( \
1130
(size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \
1131
((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \
1132
sizeof(UT_hash_table) + \
1133
(HASH_BLOOM_BYTELEN))) : 0U)
1134
1135
#ifdef NO_DECLTYPE
1136
#define HASH_ITER(hh,head,el,tmp) \
1137
for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \
1138
(el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL)))
1139
#else
1140
#define HASH_ITER(hh,head,el,tmp) \
1141
for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \
1142
(el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL)))
1143
#endif
1144
1145
/* obtain a count of items in the hash */
1146
#define HASH_COUNT(head) HASH_CNT(hh,head)
1147
#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U)
1148
1149
typedef
struct
UT_hash_bucket
{
1150
struct
UT_hash_handle
*hh_head;
1151
unsigned
count;
1152
1153
/* expand_mult is normally set to 0. In this situation, the max chain length
1154
* threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If
1155
* the bucket's chain exceeds this length, bucket expansion is triggered).
1156
* However, setting expand_mult to a non-zero value delays bucket expansion
1157
* (that would be triggered by additions to this particular bucket)
1158
* until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH.
1159
* (The multiplier is simply expand_mult+1). The whole idea of this
1160
* multiplier is to reduce bucket expansions, since they are expensive, in
1161
* situations where we know that a particular bucket tends to be overused.
1162
* It is better to let its chain length grow to a longer yet-still-bounded
1163
* value, than to do an O(n) bucket expansion too often.
1164
*/
1165
unsigned
expand_mult;
1166
1167
}
UT_hash_bucket
;
1168
1169
/* random signature used only to find hash tables in external analysis */
1170
#define HASH_SIGNATURE 0xa0111fe1u
1171
#define HASH_BLOOM_SIGNATURE 0xb12220f2u
1172
1173
typedef
struct
UT_hash_table
{
1174
UT_hash_bucket
*buckets;
1175
unsigned
num_buckets, log2_num_buckets;
1176
unsigned
num_items;
1177
struct
UT_hash_handle
*tail;
/* tail hh in app order, for fast append */
1178
ptrdiff_t hho;
/* hash handle offset (byte pos of hash handle in element */
1179
1180
/* in an ideal situation (all buckets used equally), no bucket would have
1181
* more than ceil(#items/#buckets) items. that's the ideal chain length. */
1182
unsigned
ideal_chain_maxlen;
1183
1184
/* nonideal_items is the number of items in the hash whose chain position
1185
* exceeds the ideal chain maxlen. these items pay the penalty for an uneven
1186
* hash distribution; reaching them in a chain traversal takes >ideal steps */
1187
unsigned
nonideal_items;
1188
1189
/* ineffective expands occur when a bucket doubling was performed, but
1190
* afterward, more than half the items in the hash had nonideal chain
1191
* positions. If this happens on two consecutive expansions we inhibit any
1192
* further expansion, as it's not helping; this happens when the hash
1193
* function isn't a good fit for the key domain. When expansion is inhibited
1194
* the hash will still work, albeit no longer in constant time. */
1195
unsigned
ineff_expands, noexpand;
1196
1197
uint32_t signature;
/* used only to find hash tables in external analysis */
1198
#ifdef HASH_BLOOM
1199
uint32_t bloom_sig;
/* used only to test bloom exists in external analysis */
1200
uint8_t *bloom_bv;
1201
uint8_t bloom_nbits;
1202
#endif
1203
1204
}
UT_hash_table
;
1205
1206
typedef
struct
UT_hash_handle
{
1207
struct
UT_hash_table
*tbl;
1208
void
*prev;
/* prev element in app order */
1209
void
*next;
/* next element in app order */
1210
struct
UT_hash_handle
*hh_prev;
/* previous hh in bucket order */
1211
struct
UT_hash_handle
*hh_next;
/* next hh in bucket order */
1212
void
*key;
/* ptr to enclosing struct's key */
1213
unsigned
keylen;
/* enclosing struct's key len */
1214
unsigned
hashv;
/* result of hash-fcn(key) */
1215
}
UT_hash_handle
;
1216
1217
#endif
/* UTHASH_H */
UT_hash_bucket
Definition
uthash.h:1149
UT_hash_handle
Definition
uthash.h:1206
UT_hash_table
Definition
uthash.h:1173
backends
ebpf
runtime
contrib
uthash.h
Generated by
1.12.0
1.12.0