/src/mosquitto/deps/uthash.h
Line | Count | Source |
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 | 0 | #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 | 0 | #define DECLTYPE_ASSIGN(dst,src) \ |
69 | 0 | do { \ |
70 | 0 | (dst) = DECLTYPE(dst)(src); \ |
71 | 0 | } 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 | 0 | #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 | 0 | #define HASH_FUNCTION(keyptr,keylen,hashv) HASH_JEN(keyptr, keylen, hashv) |
89 | | #endif |
90 | | |
91 | | #ifndef HASH_KEYCMP |
92 | 0 | #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 | 0 | #define uthash_fatal(msg) exit(-1) /* fatal OOM error */ |
121 | | #endif |
122 | | |
123 | 0 | #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 | 0 | #define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */ |
130 | 0 | #define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */ |
131 | 0 | #define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */ |
132 | | |
133 | | /* calculate the element whose hash handle address is hhp */ |
134 | 0 | #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) |
135 | | /* calculate the hash handle from element address elp */ |
136 | 0 | #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 | 0 | #define HASH_VALUE(keyptr,keylen,hashv) \ |
149 | 0 | do { \ |
150 | 0 | HASH_FUNCTION(keyptr, keylen, hashv); \ |
151 | 0 | } while (0) |
152 | | |
153 | 0 | #define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ |
154 | 0 | do { \ |
155 | 0 | (out) = NULL; \ |
156 | 0 | if (head) { \ |
157 | 0 | unsigned _hf_bkt; \ |
158 | 0 | HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ |
159 | 0 | if (HASH_BLOOM_TEST((head)->hh.tbl, hashval)) { \ |
160 | 0 | HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ |
161 | 0 | } \ |
162 | 0 | } \ |
163 | 0 | } while (0) |
164 | | |
165 | 0 | #define HASH_FIND(hh,head,keyptr,keylen,out) \ |
166 | 0 | do { \ |
167 | 0 | (out) = NULL; \ |
168 | 0 | if (head) { \ |
169 | 0 | unsigned _hf_hashv; \ |
170 | 0 | HASH_VALUE(keyptr, keylen, _hf_hashv); \ |
171 | 0 | HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ |
172 | 0 | } \ |
173 | 0 | } 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 | 0 | #define HASH_BLOOM_TEST(tbl,hashv) 1 |
209 | | #define HASH_BLOOM_BYTELEN 0U |
210 | | #endif |
211 | | |
212 | 0 | #define HASH_MAKE_TABLE(hh,head,oomed) \ |
213 | 0 | do { \ |
214 | 0 | (head)->hh.tbl = (UT_hash_table*)uthash_malloc(sizeof(UT_hash_table)); \ |
215 | 0 | if (!(head)->hh.tbl) { \ |
216 | 0 | HASH_RECORD_OOM(oomed); \ |
217 | 0 | } else { \ |
218 | 0 | uthash_bzero((head)->hh.tbl, sizeof(UT_hash_table)); \ |
219 | 0 | (head)->hh.tbl->tail = &((head)->hh); \ |
220 | 0 | (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ |
221 | 0 | (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ |
222 | 0 | (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ |
223 | 0 | (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ |
224 | 0 | HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ |
225 | 0 | (head)->hh.tbl->signature = HASH_SIGNATURE; \ |
226 | 0 | if (!(head)->hh.tbl->buckets) { \ |
227 | 0 | HASH_RECORD_OOM(oomed); \ |
228 | 0 | uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ |
229 | 0 | } else { \ |
230 | 0 | uthash_bzero((head)->hh.tbl->buckets, \ |
231 | 0 | HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ |
232 | 0 | HASH_BLOOM_MAKE((head)->hh.tbl, oomed); \ |
233 | 0 | IF_HASH_NONFATAL_OOM( \ |
234 | 0 | if (oomed) { \ |
235 | 0 | uthash_free((head)->hh.tbl->buckets, \ |
236 | 0 | HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ |
237 | 0 | uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ |
238 | 0 | } \ |
239 | 0 | ) \ |
240 | 0 | } \ |
241 | 0 | } \ |
242 | 0 | } 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 | 0 | #define HASH_APPEND_LIST(hh, head, add) \ |
279 | 0 | do { \ |
280 | 0 | (add)->hh.next = NULL; \ |
281 | 0 | (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ |
282 | 0 | (head)->hh.tbl->tail->next = (add); \ |
283 | 0 | (head)->hh.tbl->tail = &((add)->hh); \ |
284 | 0 | } 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 | 0 | #define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \ |
338 | 0 | do { \ |
339 | 0 | unsigned _ha_bkt; \ |
340 | 0 | (head)->hh.tbl->num_items++; \ |
341 | 0 | HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ |
342 | 0 | HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \ |
343 | 0 | HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ |
344 | 0 | HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ |
345 | 0 | } 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 | 0 | #define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \ |
397 | 0 | do { \ |
398 | 0 | IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \ |
399 | 0 | (add)->hh.hashv = (hashval); \ |
400 | 0 | (add)->hh.key = (const void*) (keyptr); \ |
401 | 0 | (add)->hh.keylen = (unsigned) (keylen_in); \ |
402 | 0 | if (!(head)) { \ |
403 | 0 | (add)->hh.next = NULL; \ |
404 | 0 | (add)->hh.prev = NULL; \ |
405 | 0 | HASH_MAKE_TABLE(hh, add, _ha_oomed); \ |
406 | 0 | IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \ |
407 | 0 | (head) = (add); \ |
408 | 0 | IF_HASH_NONFATAL_OOM( } ) \ |
409 | 0 | } else { \ |
410 | 0 | (add)->hh.tbl = (head)->hh.tbl; \ |
411 | 0 | HASH_APPEND_LIST(hh, head, add); \ |
412 | 0 | } \ |
413 | 0 | HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \ |
414 | 0 | HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE"); \ |
415 | 0 | } while (0) |
416 | | |
417 | 0 | #define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ |
418 | 0 | do { \ |
419 | 0 | unsigned _ha_hashv; \ |
420 | 0 | HASH_VALUE(keyptr, keylen_in, _ha_hashv); \ |
421 | 0 | HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \ |
422 | 0 | } while (0) |
423 | | |
424 | | #define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \ |
425 | 0 | HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add) |
426 | | |
427 | | #define HASH_ADD(hh,head,fieldname,keylen_in,add) \ |
428 | 0 | HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add) |
429 | | |
430 | 0 | #define HASH_TO_BKT(hashv,num_bkts,bkt) \ |
431 | 0 | do { \ |
432 | 0 | bkt = ((hashv) & ((num_bkts) - 1U)); \ |
433 | 0 | } 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 | 0 | HASH_DELETE_HH(hh, head, &(delptr)->hh) |
449 | | |
450 | 0 | #define HASH_DELETE_HH(hh,head,delptrhh) \ |
451 | 0 | do { \ |
452 | 0 | const struct UT_hash_handle *_hd_hh_del = (delptrhh); \ |
453 | 0 | if ((_hd_hh_del->prev == NULL) && (_hd_hh_del->next == NULL)) { \ |
454 | 0 | HASH_BLOOM_FREE((head)->hh.tbl); \ |
455 | 0 | uthash_free((head)->hh.tbl->buckets, \ |
456 | 0 | (head)->hh.tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ |
457 | 0 | uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ |
458 | 0 | (head) = NULL; \ |
459 | 0 | } else { \ |
460 | 0 | unsigned _hd_bkt; \ |
461 | 0 | if (_hd_hh_del == (head)->hh.tbl->tail) { \ |
462 | 0 | (head)->hh.tbl->tail = HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev); \ |
463 | 0 | } \ |
464 | 0 | if (_hd_hh_del->prev != NULL) { \ |
465 | 0 | HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev)->next = _hd_hh_del->next; \ |
466 | 0 | } else { \ |
467 | 0 | DECLTYPE_ASSIGN(head, _hd_hh_del->next); \ |
468 | 0 | } \ |
469 | 0 | if (_hd_hh_del->next != NULL) { \ |
470 | 0 | HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->next)->prev = _hd_hh_del->prev; \ |
471 | 0 | } \ |
472 | 0 | HASH_TO_BKT(_hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ |
473 | 0 | HASH_DEL_IN_BKT((head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ |
474 | 0 | (head)->hh.tbl->num_items--; \ |
475 | 0 | } \ |
476 | 0 | HASH_FSCK(hh, head, "HASH_DELETE_HH"); \ |
477 | 0 | } 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 | 0 | 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 | 0 | #define HASH_JEN_MIX(a,b,c) \ |
635 | 0 | do { \ |
636 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
637 | 0 | a -= b; a -= c; a ^= ( c >> 13 ); \ |
638 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
639 | 0 | b -= c; b -= a; b ^= ( a << 8 ); \ |
640 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
641 | 0 | c -= a; c -= b; c ^= ( b >> 13 ); \ |
642 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
643 | 0 | a -= b; a -= c; a ^= ( c >> 12 ); \ |
644 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
645 | 0 | b -= c; b -= a; b ^= ( a << 16 ); \ |
646 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
647 | 0 | c -= a; c -= b; c ^= ( b >> 5 ); \ |
648 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
649 | 0 | a -= b; a -= c; a ^= ( c >> 3 ); \ |
650 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
651 | 0 | b -= c; b -= a; b ^= ( a << 10 ); \ |
652 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
653 | 0 | c -= a; c -= b; c ^= ( b >> 15 ); \ |
654 | 0 | } while (0) |
655 | | |
656 | | #define HASH_JEN(key,keylen,hashv) \ |
657 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
658 | 0 | do { \ |
659 | 0 | unsigned _hj_i,_hj_j,_hj_k; \ |
660 | 0 | unsigned const char *_hj_key=(unsigned const char*)(key); \ |
661 | 0 | hashv = 0xfeedbeefu; \ |
662 | 0 | _hj_i = _hj_j = 0x9e3779b9u; \ |
663 | 0 | _hj_k = (unsigned)(keylen); \ |
664 | 0 | while (_hj_k >= 12U) { \ |
665 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
666 | 0 | _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ |
667 | 0 | + ( (unsigned)_hj_key[2] << 16 ) \ |
668 | 0 | + ( (unsigned)_hj_key[3] << 24 ) ); \ |
669 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
670 | 0 | _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ |
671 | 0 | + ( (unsigned)_hj_key[6] << 16 ) \ |
672 | 0 | + ( (unsigned)_hj_key[7] << 24 ) ); \ |
673 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
674 | 0 | hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ |
675 | 0 | + ( (unsigned)_hj_key[10] << 16 ) \ |
676 | 0 | + ( (unsigned)_hj_key[11] << 24 ) ); \ |
677 | 0 | \ |
678 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
679 | 0 | HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ |
680 | 0 | \ |
681 | 0 | _hj_key += 12; \ |
682 | 0 | _hj_k -= 12U; \ |
683 | 0 | } \ |
684 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
685 | 0 | hashv += (unsigned)(keylen); \ |
686 | 0 | switch ( _hj_k ) { \ |
687 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
688 | 0 | case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \ |
689 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
690 | 0 | case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \ |
691 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
692 | 0 | case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \ |
693 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
694 | 0 | case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \ |
695 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
696 | 0 | case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \ |
697 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
698 | 0 | case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \ |
699 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
700 | 0 | case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \ |
701 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
702 | 0 | case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \ |
703 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
704 | 0 | case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \ |
705 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
706 | 0 | case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \ |
707 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
708 | 0 | case 1: _hj_i += _hj_key[0]; /* FALLTHROUGH */ \ |
709 | 0 | default: ; \ |
710 | 0 | } \ |
711 | 0 | /* coverity[overflow_const] - intentional wrapping in Jenkins hash */ \ |
712 | 0 | HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ |
713 | 0 | } while (0) |
714 | | |
715 | | /* The Paul Hsieh hash function */ |
716 | | #undef get16bits |
717 | | #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ |
718 | | || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) |
719 | | #define get16bits(d) (*((const uint16_t *) (d))) |
720 | | #endif |
721 | | |
722 | | #if !defined (get16bits) |
723 | | #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ |
724 | | +(uint32_t)(((const uint8_t *)(d))[0]) ) |
725 | | #endif |
726 | | #define HASH_SFH(key,keylen,hashv) \ |
727 | | do { \ |
728 | | unsigned const char *_sfh_key=(unsigned const char*)(key); \ |
729 | | uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \ |
730 | | \ |
731 | | unsigned _sfh_rem = _sfh_len & 3U; \ |
732 | | _sfh_len >>= 2; \ |
733 | | hashv = 0xcafebabeu; \ |
734 | | \ |
735 | | /* Main loop */ \ |
736 | | for (;_sfh_len > 0U; _sfh_len--) { \ |
737 | | hashv += get16bits (_sfh_key); \ |
738 | | _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \ |
739 | | hashv = (hashv << 16) ^ _sfh_tmp; \ |
740 | | _sfh_key += 2U*sizeof (uint16_t); \ |
741 | | hashv += hashv >> 11; \ |
742 | | } \ |
743 | | \ |
744 | | /* Handle end cases */ \ |
745 | | switch (_sfh_rem) { \ |
746 | | case 3: hashv += get16bits (_sfh_key); \ |
747 | | hashv ^= hashv << 16; \ |
748 | | hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \ |
749 | | hashv += hashv >> 11; \ |
750 | | break; \ |
751 | | case 2: hashv += get16bits (_sfh_key); \ |
752 | | hashv ^= hashv << 11; \ |
753 | | hashv += hashv >> 17; \ |
754 | | break; \ |
755 | | case 1: hashv += *_sfh_key; \ |
756 | | hashv ^= hashv << 10; \ |
757 | | hashv += hashv >> 1; \ |
758 | | break; \ |
759 | | default: ; \ |
760 | | } \ |
761 | | \ |
762 | | /* Force "avalanching" of final 127 bits */ \ |
763 | | hashv ^= hashv << 3; \ |
764 | | hashv += hashv >> 5; \ |
765 | | hashv ^= hashv << 4; \ |
766 | | hashv += hashv >> 17; \ |
767 | | hashv ^= hashv << 25; \ |
768 | | hashv += hashv >> 6; \ |
769 | | } while (0) |
770 | | |
771 | | /* iterate over items in a known bucket to find desired item */ |
772 | 0 | #define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \ |
773 | 0 | do { \ |
774 | 0 | if ((head).hh_head != NULL) { \ |
775 | 0 | DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \ |
776 | 0 | } else { \ |
777 | 0 | (out) = NULL; \ |
778 | 0 | } \ |
779 | 0 | while ((out) != NULL) { \ |
780 | 0 | if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \ |
781 | 0 | if (HASH_KEYCMP((out)->hh.key, keyptr, keylen_in) == 0) { \ |
782 | 0 | break; \ |
783 | 0 | } \ |
784 | 0 | } \ |
785 | 0 | if ((out)->hh.hh_next != NULL) { \ |
786 | 0 | DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \ |
787 | 0 | } else { \ |
788 | 0 | (out) = NULL; \ |
789 | 0 | } \ |
790 | 0 | } \ |
791 | 0 | } while (0) |
792 | | |
793 | | /* add an item to a bucket */ |
794 | 0 | #define HASH_ADD_TO_BKT(head,hh,addhh,oomed) \ |
795 | 0 | do { \ |
796 | 0 | UT_hash_bucket *_ha_head = &(head); \ |
797 | 0 | _ha_head->count++; \ |
798 | 0 | (addhh)->hh_next = _ha_head->hh_head; \ |
799 | 0 | (addhh)->hh_prev = NULL; \ |
800 | 0 | if (_ha_head->hh_head != NULL) { \ |
801 | 0 | _ha_head->hh_head->hh_prev = (addhh); \ |
802 | 0 | } \ |
803 | 0 | _ha_head->hh_head = (addhh); \ |
804 | 0 | if ((_ha_head->count >= ((_ha_head->expand_mult + 1U) * HASH_BKT_CAPACITY_THRESH)) \ |
805 | 0 | && !(addhh)->tbl->noexpand) { \ |
806 | 0 | HASH_EXPAND_BUCKETS(addhh,(addhh)->tbl, oomed); \ |
807 | 0 | IF_HASH_NONFATAL_OOM( \ |
808 | 0 | if (oomed) { \ |
809 | 0 | HASH_DEL_IN_BKT(head,addhh); \ |
810 | 0 | } \ |
811 | 0 | ) \ |
812 | 0 | } \ |
813 | 0 | } while (0) |
814 | | |
815 | | /* remove an item from a given bucket */ |
816 | 0 | #define HASH_DEL_IN_BKT(head,delhh) \ |
817 | 0 | do { \ |
818 | 0 | UT_hash_bucket *_hd_head = &(head); \ |
819 | 0 | _hd_head->count--; \ |
820 | 0 | if (_hd_head->hh_head == (delhh)) { \ |
821 | 0 | _hd_head->hh_head = (delhh)->hh_next; \ |
822 | 0 | } \ |
823 | 0 | if ((delhh)->hh_prev) { \ |
824 | 0 | (delhh)->hh_prev->hh_next = (delhh)->hh_next; \ |
825 | 0 | } \ |
826 | 0 | if ((delhh)->hh_next) { \ |
827 | 0 | (delhh)->hh_next->hh_prev = (delhh)->hh_prev; \ |
828 | 0 | } \ |
829 | 0 | } while (0) |
830 | | |
831 | | /* Bucket expansion has the effect of doubling the number of buckets |
832 | | * and redistributing the items into the new buckets. Ideally the |
833 | | * items will distribute more or less evenly into the new buckets |
834 | | * (the extent to which this is true is a measure of the quality of |
835 | | * the hash function as it applies to the key domain). |
836 | | * |
837 | | * With the items distributed into more buckets, the chain length |
838 | | * (item count) in each bucket is reduced. Thus by expanding buckets |
839 | | * the hash keeps a bound on the chain length. This bounded chain |
840 | | * length is the essence of how a hash provides constant time lookup. |
841 | | * |
842 | | * The calculation of tbl->ideal_chain_maxlen below deserves some |
843 | | * explanation. First, keep in mind that we're calculating the ideal |
844 | | * maximum chain length based on the *new* (doubled) bucket count. |
845 | | * In fractions this is just n/b (n=number of items,b=new num buckets). |
846 | | * Since the ideal chain length is an integer, we want to calculate |
847 | | * ceil(n/b). We don't depend on floating point arithmetic in this |
848 | | * hash, so to calculate ceil(n/b) with integers we could write |
849 | | * |
850 | | * ceil(n/b) = (n/b) + ((n%b)?1:0) |
851 | | * |
852 | | * and in fact a previous version of this hash did just that. |
853 | | * But now we have improved things a bit by recognizing that b is |
854 | | * always a power of two. We keep its base 2 log handy (call it lb), |
855 | | * so now we can write this with a bit shift and logical AND: |
856 | | * |
857 | | * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) |
858 | | * |
859 | | */ |
860 | 0 | #define HASH_EXPAND_BUCKETS(hh,tbl,oomed) \ |
861 | 0 | do { \ |
862 | 0 | unsigned _he_bkt; \ |
863 | 0 | unsigned _he_bkt_i; \ |
864 | 0 | struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ |
865 | 0 | UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ |
866 | 0 | _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ |
867 | 0 | sizeof(struct UT_hash_bucket) * (tbl)->num_buckets * 2U); \ |
868 | 0 | if (!_he_new_buckets) { \ |
869 | 0 | HASH_RECORD_OOM(oomed); \ |
870 | 0 | } else { \ |
871 | 0 | uthash_bzero(_he_new_buckets, \ |
872 | 0 | sizeof(struct UT_hash_bucket) * (tbl)->num_buckets * 2U); \ |
873 | 0 | (tbl)->ideal_chain_maxlen = \ |
874 | 0 | ((tbl)->num_items >> ((tbl)->log2_num_buckets+1U)) + \ |
875 | 0 | ((((tbl)->num_items & (((tbl)->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \ |
876 | 0 | (tbl)->nonideal_items = 0; \ |
877 | 0 | for (_he_bkt_i = 0; _he_bkt_i < (tbl)->num_buckets; _he_bkt_i++) { \ |
878 | 0 | _he_thh = (tbl)->buckets[ _he_bkt_i ].hh_head; \ |
879 | 0 | while (_he_thh != NULL) { \ |
880 | 0 | _he_hh_nxt = _he_thh->hh_next; \ |
881 | 0 | HASH_TO_BKT(_he_thh->hashv, (tbl)->num_buckets * 2U, _he_bkt); \ |
882 | 0 | _he_newbkt = &(_he_new_buckets[_he_bkt]); \ |
883 | 0 | if (++(_he_newbkt->count) > (tbl)->ideal_chain_maxlen) { \ |
884 | 0 | (tbl)->nonideal_items++; \ |
885 | 0 | if (_he_newbkt->count > _he_newbkt->expand_mult * (tbl)->ideal_chain_maxlen) { \ |
886 | 0 | _he_newbkt->expand_mult++; \ |
887 | 0 | } \ |
888 | 0 | } \ |
889 | 0 | _he_thh->hh_prev = NULL; \ |
890 | 0 | _he_thh->hh_next = _he_newbkt->hh_head; \ |
891 | 0 | if (_he_newbkt->hh_head != NULL) { \ |
892 | 0 | _he_newbkt->hh_head->hh_prev = _he_thh; \ |
893 | 0 | } \ |
894 | 0 | _he_newbkt->hh_head = _he_thh; \ |
895 | 0 | _he_thh = _he_hh_nxt; \ |
896 | 0 | } \ |
897 | 0 | } \ |
898 | 0 | uthash_free((tbl)->buckets, (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ |
899 | 0 | (tbl)->num_buckets *= 2U; \ |
900 | 0 | (tbl)->log2_num_buckets++; \ |
901 | 0 | (tbl)->buckets = _he_new_buckets; \ |
902 | 0 | (tbl)->ineff_expands = ((tbl)->nonideal_items > ((tbl)->num_items >> 1)) ? \ |
903 | 0 | ((tbl)->ineff_expands+1U) : 0U; \ |
904 | 0 | if ((tbl)->ineff_expands > 1U) { \ |
905 | 0 | (tbl)->noexpand = 1; \ |
906 | 0 | uthash_noexpand_fyi(tbl); \ |
907 | 0 | } \ |
908 | 0 | uthash_expand_fyi(tbl); \ |
909 | 0 | } \ |
910 | 0 | } while (0) |
911 | | |
912 | | |
913 | | /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ |
914 | | /* Note that HASH_SORT assumes the hash handle name to be hh. |
915 | | * HASH_SRT was added to allow the hash handle name to be passed in. */ |
916 | | #define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) |
917 | | #define HASH_SRT(hh,head,cmpfcn) \ |
918 | | do { \ |
919 | | unsigned _hs_i; \ |
920 | | unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ |
921 | | struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ |
922 | | if (head != NULL) { \ |
923 | | _hs_insize = 1; \ |
924 | | _hs_looping = 1; \ |
925 | | _hs_list = &((head)->hh); \ |
926 | | while (_hs_looping != 0U) { \ |
927 | | _hs_p = _hs_list; \ |
928 | | _hs_list = NULL; \ |
929 | | _hs_tail = NULL; \ |
930 | | _hs_nmerges = 0; \ |
931 | | while (_hs_p != NULL) { \ |
932 | | _hs_nmerges++; \ |
933 | | _hs_q = _hs_p; \ |
934 | | _hs_psize = 0; \ |
935 | | for (_hs_i = 0; _hs_i < _hs_insize; ++_hs_i) { \ |
936 | | _hs_psize++; \ |
937 | | _hs_q = ((_hs_q->next != NULL) ? \ |
938 | | HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ |
939 | | if (_hs_q == NULL) { \ |
940 | | break; \ |
941 | | } \ |
942 | | } \ |
943 | | _hs_qsize = _hs_insize; \ |
944 | | while ((_hs_psize != 0U) || ((_hs_qsize != 0U) && (_hs_q != NULL))) { \ |
945 | | if (_hs_psize == 0U) { \ |
946 | | _hs_e = _hs_q; \ |
947 | | _hs_q = ((_hs_q->next != NULL) ? \ |
948 | | HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ |
949 | | _hs_qsize--; \ |
950 | | } else if ((_hs_qsize == 0U) || (_hs_q == NULL)) { \ |
951 | | _hs_e = _hs_p; \ |
952 | | if (_hs_p != NULL) { \ |
953 | | _hs_p = ((_hs_p->next != NULL) ? \ |
954 | | HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ |
955 | | } \ |
956 | | _hs_psize--; \ |
957 | | } else if ((cmpfcn( \ |
958 | | DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_p)), \ |
959 | | DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_q)) \ |
960 | | )) <= 0) { \ |
961 | | _hs_e = _hs_p; \ |
962 | | if (_hs_p != NULL) { \ |
963 | | _hs_p = ((_hs_p->next != NULL) ? \ |
964 | | HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ |
965 | | } \ |
966 | | _hs_psize--; \ |
967 | | } else { \ |
968 | | _hs_e = _hs_q; \ |
969 | | _hs_q = ((_hs_q->next != NULL) ? \ |
970 | | HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ |
971 | | _hs_qsize--; \ |
972 | | } \ |
973 | | if ( _hs_tail != NULL ) { \ |
974 | | _hs_tail->next = ((_hs_e != NULL) ? \ |
975 | | ELMT_FROM_HH((head)->hh.tbl, _hs_e) : NULL); \ |
976 | | } else { \ |
977 | | _hs_list = _hs_e; \ |
978 | | } \ |
979 | | if (_hs_e != NULL) { \ |
980 | | _hs_e->prev = ((_hs_tail != NULL) ? \ |
981 | | ELMT_FROM_HH((head)->hh.tbl, _hs_tail) : NULL); \ |
982 | | } \ |
983 | | _hs_tail = _hs_e; \ |
984 | | } \ |
985 | | _hs_p = _hs_q; \ |
986 | | } \ |
987 | | if (_hs_tail != NULL) { \ |
988 | | _hs_tail->next = NULL; \ |
989 | | } \ |
990 | | if (_hs_nmerges <= 1U) { \ |
991 | | _hs_looping = 0; \ |
992 | | (head)->hh.tbl->tail = _hs_tail; \ |
993 | | DECLTYPE_ASSIGN(head, ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ |
994 | | } \ |
995 | | _hs_insize *= 2U; \ |
996 | | } \ |
997 | | HASH_FSCK(hh, head, "HASH_SRT"); \ |
998 | | } \ |
999 | | } while (0) |
1000 | | |
1001 | | /* This function selects items from one hash into another hash. |
1002 | | * The end result is that the selected items have dual presence |
1003 | | * in both hashes. There is no copy of the items made; rather |
1004 | | * they are added into the new hash through a secondary hash |
1005 | | * hash handle that must be present in the structure. */ |
1006 | | #define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ |
1007 | | do { \ |
1008 | | unsigned _src_bkt, _dst_bkt; \ |
1009 | | void *_last_elt = NULL, *_elt; \ |
1010 | | UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ |
1011 | | ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ |
1012 | | if ((src) != NULL) { \ |
1013 | | for (_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ |
1014 | | for (_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ |
1015 | | _src_hh != NULL; \ |
1016 | | _src_hh = _src_hh->hh_next) { \ |
1017 | | _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ |
1018 | | if (cond(_elt)) { \ |
1019 | | IF_HASH_NONFATAL_OOM( int _hs_oomed = 0; ) \ |
1020 | | _dst_hh = (UT_hash_handle*)(void*)(((char*)_elt) + _dst_hho); \ |
1021 | | _dst_hh->key = _src_hh->key; \ |
1022 | | _dst_hh->keylen = _src_hh->keylen; \ |
1023 | | _dst_hh->hashv = _src_hh->hashv; \ |
1024 | | _dst_hh->prev = _last_elt; \ |
1025 | | _dst_hh->next = NULL; \ |
1026 | | if (_last_elt_hh != NULL) { \ |
1027 | | _last_elt_hh->next = _elt; \ |
1028 | | } \ |
1029 | | if ((dst) == NULL) { \ |
1030 | | DECLTYPE_ASSIGN(dst, _elt); \ |
1031 | | HASH_MAKE_TABLE(hh_dst, dst, _hs_oomed); \ |
1032 | | IF_HASH_NONFATAL_OOM( \ |
1033 | | if (_hs_oomed) { \ |
1034 | | uthash_nonfatal_oom(_elt); \ |
1035 | | (dst) = NULL; \ |
1036 | | continue; \ |
1037 | | } \ |
1038 | | ) \ |
1039 | | } else { \ |
1040 | | _dst_hh->tbl = (dst)->hh_dst.tbl; \ |
1041 | | } \ |
1042 | | HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ |
1043 | | HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt], hh_dst, _dst_hh, _hs_oomed); \ |
1044 | | (dst)->hh_dst.tbl->num_items++; \ |
1045 | | IF_HASH_NONFATAL_OOM( \ |
1046 | | if (_hs_oomed) { \ |
1047 | | HASH_ROLLBACK_BKT(hh_dst, dst, _dst_hh); \ |
1048 | | HASH_DELETE_HH(hh_dst, dst, _dst_hh); \ |
1049 | | _dst_hh->tbl = NULL; \ |
1050 | | uthash_nonfatal_oom(_elt); \ |
1051 | | continue; \ |
1052 | | } \ |
1053 | | ) \ |
1054 | | HASH_BLOOM_ADD(_dst_hh->tbl, _dst_hh->hashv); \ |
1055 | | _last_elt = _elt; \ |
1056 | | _last_elt_hh = _dst_hh; \ |
1057 | | } \ |
1058 | | } \ |
1059 | | } \ |
1060 | | } \ |
1061 | | HASH_FSCK(hh_dst, dst, "HASH_SELECT"); \ |
1062 | | } while (0) |
1063 | | |
1064 | | #define HASH_CLEAR(hh,head) \ |
1065 | | do { \ |
1066 | | if ((head) != NULL) { \ |
1067 | | HASH_BLOOM_FREE((head)->hh.tbl); \ |
1068 | | uthash_free((head)->hh.tbl->buckets, \ |
1069 | | (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ |
1070 | | uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ |
1071 | | (head) = NULL; \ |
1072 | | } \ |
1073 | | } while (0) |
1074 | | |
1075 | | #define HASH_OVERHEAD(hh,head) \ |
1076 | | (((head) != NULL) ? ( \ |
1077 | | (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ |
1078 | | ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ |
1079 | | sizeof(UT_hash_table) + \ |
1080 | | (HASH_BLOOM_BYTELEN))) : 0U) |
1081 | | |
1082 | | #ifdef NO_DECLTYPE |
1083 | | #define HASH_ITER(hh,head,el,tmp) \ |
1084 | | for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \ |
1085 | | (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL))) |
1086 | | #else |
1087 | 0 | #define HASH_ITER(hh,head,el,tmp) \ |
1088 | 0 | for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \ |
1089 | 0 | (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL))) |
1090 | | #endif |
1091 | | |
1092 | | /* obtain a count of items in the hash */ |
1093 | | #define HASH_COUNT(head) HASH_CNT(hh,head) |
1094 | 0 | #define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U) |
1095 | | |
1096 | | typedef struct UT_hash_bucket { |
1097 | | struct UT_hash_handle *hh_head; |
1098 | | unsigned count; |
1099 | | |
1100 | | /* expand_mult is normally set to 0. In this situation, the max chain length |
1101 | | * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If |
1102 | | * the bucket's chain exceeds this length, bucket expansion is triggered). |
1103 | | * However, setting expand_mult to a non-zero value delays bucket expansion |
1104 | | * (that would be triggered by additions to this particular bucket) |
1105 | | * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. |
1106 | | * (The multiplier is simply expand_mult+1). The whole idea of this |
1107 | | * multiplier is to reduce bucket expansions, since they are expensive, in |
1108 | | * situations where we know that a particular bucket tends to be overused. |
1109 | | * It is better to let its chain length grow to a longer yet-still-bounded |
1110 | | * value, than to do an O(n) bucket expansion too often. |
1111 | | */ |
1112 | | unsigned expand_mult; |
1113 | | |
1114 | | } UT_hash_bucket; |
1115 | | |
1116 | | /* random signature used only to find hash tables in external analysis */ |
1117 | 0 | #define HASH_SIGNATURE 0xa0111fe1u |
1118 | | #define HASH_BLOOM_SIGNATURE 0xb12220f2u |
1119 | | |
1120 | | typedef struct UT_hash_table { |
1121 | | UT_hash_bucket *buckets; |
1122 | | unsigned num_buckets, log2_num_buckets; |
1123 | | unsigned num_items; |
1124 | | struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ |
1125 | | ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ |
1126 | | |
1127 | | /* in an ideal situation (all buckets used equally), no bucket would have |
1128 | | * more than ceil(#items/#buckets) items. that's the ideal chain length. */ |
1129 | | unsigned ideal_chain_maxlen; |
1130 | | |
1131 | | /* nonideal_items is the number of items in the hash whose chain position |
1132 | | * exceeds the ideal chain maxlen. these items pay the penalty for an uneven |
1133 | | * hash distribution; reaching them in a chain traversal takes >ideal steps */ |
1134 | | unsigned nonideal_items; |
1135 | | |
1136 | | /* ineffective expands occur when a bucket doubling was performed, but |
1137 | | * afterward, more than half the items in the hash had nonideal chain |
1138 | | * positions. If this happens on two consecutive expansions we inhibit any |
1139 | | * further expansion, as it's not helping; this happens when the hash |
1140 | | * function isn't a good fit for the key domain. When expansion is inhibited |
1141 | | * the hash will still work, albeit no longer in constant time. */ |
1142 | | unsigned ineff_expands, noexpand; |
1143 | | |
1144 | | uint32_t signature; /* used only to find hash tables in external analysis */ |
1145 | | #ifdef HASH_BLOOM |
1146 | | uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ |
1147 | | uint8_t *bloom_bv; |
1148 | | uint8_t bloom_nbits; |
1149 | | #endif |
1150 | | |
1151 | | } UT_hash_table; |
1152 | | |
1153 | | typedef struct UT_hash_handle { |
1154 | | struct UT_hash_table *tbl; |
1155 | | void *prev; /* prev element in app order */ |
1156 | | void *next; /* next element in app order */ |
1157 | | struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ |
1158 | | struct UT_hash_handle *hh_next; /* next hh in bucket order */ |
1159 | | const void *key; /* ptr to enclosing struct's key */ |
1160 | | unsigned keylen; /* enclosing struct's key len */ |
1161 | | unsigned hashv; /* result of hash-fcn(key) */ |
1162 | | } UT_hash_handle; |
1163 | | |
1164 | | #endif /* UTHASH_H */ |