1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 #ifndef UTHASH_H
25 #define UTHASH_H
26
27 #include <string.h>
28 #include <stddef.h>
29 #include <stdlib.h>
30
31
32
33
34
35 #if defined(_MSC_VER)
36 #if _MSC_VER >= 1600 && defined(__cplusplus)
37 #define DECLTYPE(x) (decltype(x))
38 #else
39 #define NO_DECLTYPE
40 #define DECLTYPE(x)
41 #endif
42 #elif defined(__BORLANDC__) || defined(__LCC__) || defined(__WATCOMC__)
43 #define NO_DECLTYPE
44 #define DECLTYPE(x)
45 #else
46 #define DECLTYPE(x) (__typeof(x))
47 #endif
48
49 #ifdef NO_DECLTYPE
50 #define DECLTYPE_ASSIGN(dst,src) \
51 do { \
52 char **_da_dst = (char**)(&(dst)); \
53 *_da_dst = (char*)(src); \
54 } while(0)
55 #else
56 #define DECLTYPE_ASSIGN(dst,src) \
57 do { \
58 (dst) = DECLTYPE(dst)(src); \
59 } while(0)
60 #endif
61
62
63 #if defined(_WIN32)
64 #if defined(_MSC_VER) && _MSC_VER >= 1600
65 #include <stdint.h>
66 #elif defined(__WATCOMC__) || defined(__MINGW32__) || defined(__CYGWIN__)
67 #include <stdint.h>
68 #else
69 typedef unsigned int uint32_t;
70 typedef unsigned char uint8_t;
71 #endif
72 #elif defined(__GNUC__) && !defined(__VXWORKS__)
73 #include <stdint.h>
74 #else
75 typedef unsigned int uint32_t;
76 typedef unsigned char uint8_t;
77 #endif
78
79 #define UTHASH_VERSION 1.9.9
80
81 #ifndef uthash_fatal
82 #define uthash_fatal(msg) exit(-1)
83 #endif
84 #ifndef uthash_malloc
85 #define uthash_malloc(sz) malloc(sz)
86 #endif
87 #ifndef uthash_free
88 #define uthash_free(ptr,sz) free(ptr)
89 #endif
90
91 #ifndef uthash_noexpand_fyi
92 #define uthash_noexpand_fyi(tbl)
93 #endif
94 #ifndef uthash_expand_fyi
95 #define uthash_expand_fyi(tbl)
96 #endif
97
98
99 #define HASH_INITIAL_NUM_BUCKETS 32U
100 #define HASH_INITIAL_NUM_BUCKETS_LOG2 5U
101 #define HASH_BKT_CAPACITY_THRESH 10U
102
103
104 #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
105
106 #define HASH_FIND(hh,head,keyptr,keylen,out) \
107 do { \
108 out=NULL; \
109 if (head != NULL) { \
110 unsigned _hf_bkt,_hf_hashv; \
111 HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \
112 if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv) != 0) { \
113 HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \
114 keyptr,keylen,out); \
115 } \
116 } \
117 } while (0)
118
119 #ifdef HASH_BLOOM
120 #define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM)
121 #define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL)
122 #define HASH_BLOOM_MAKE(tbl) \
123 do { \
124 (tbl)->bloom_nbits = HASH_BLOOM; \
125 (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \
126 if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \
127 memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \
128 (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \
129 } while (0)
130
131 #define HASH_BLOOM_FREE(tbl) \
132 do { \
133 uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \
134 } while (0)
135
136 #define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U)))
137 #define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U)))
138
139 #define HASH_BLOOM_ADD(tbl,hashv) \
140 HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U)))
141
142 #define HASH_BLOOM_TEST(tbl,hashv) \
143 HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U)))
144
145 #else
146 #define HASH_BLOOM_MAKE(tbl)
147 #define HASH_BLOOM_FREE(tbl)
148 #define HASH_BLOOM_ADD(tbl,hashv)
149 #define HASH_BLOOM_TEST(tbl,hashv) (1)
150 #define HASH_BLOOM_BYTELEN 0U
151 #endif
152
153 #define HASH_MAKE_TABLE(hh,head) \
154 do { \
155 (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \
156 sizeof(UT_hash_table)); \
157 if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \
158 memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \
159 (head)->hh.tbl->tail = &((head)->hh); \
160 (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \
161 (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \
162 (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \
163 (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \
164 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
165 if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \
166 memset((head)->hh.tbl->buckets, 0, \
167 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
168 HASH_BLOOM_MAKE((head)->hh.tbl); \
169 (head)->hh.tbl->signature = HASH_SIGNATURE; \
170 } while(0)
171
172 #define HASH_ADD(hh,head,fieldname,keylen_in,add) \
173 HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add)
174
175 #define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \
176 do { \
177 replaced=NULL; \
178 HASH_FIND(hh,head,&((add)->fieldname),keylen_in,replaced); \
179 if (replaced!=NULL) { \
180 HASH_DELETE(hh,head,replaced); \
181 } \
182 HASH_ADD(hh,head,fieldname,keylen_in,add); \
183 } while(0)
184
185 #define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \
186 do { \
187 unsigned _ha_bkt; \
188 (add)->hh.next = NULL; \
189 (add)->hh.key = (char*)(keyptr); \
190 (add)->hh.keylen = (unsigned)(keylen_in); \
191 if (!(head)) { \
192 head = (add); \
193 (head)->hh.prev = NULL; \
194 HASH_MAKE_TABLE(hh,head); \
195 } else { \
196 (head)->hh.tbl->tail->next = (add); \
197 (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \
198 (head)->hh.tbl->tail = &((add)->hh); \
199 } \
200 (head)->hh.tbl->num_items++; \
201 (add)->hh.tbl = (head)->hh.tbl; \
202 HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \
203 (add)->hh.hashv, _ha_bkt); \
204 HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \
205 HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \
206 HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \
207 HASH_FSCK(hh,head); \
208 } while(0)
209
210 #define HASH_TO_BKT( hashv, num_bkts, bkt ) \
211 do { \
212 bkt = ((hashv) & ((num_bkts) - 1U)); \
213 } while(0)
214
215
216
217
218
219
220
221
222
223
224
225
226
227 #define HASH_DELETE(hh,head,delptr) \
228 do { \
229 struct UT_hash_handle *_hd_hh_del; \
230 if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \
231 uthash_free((head)->hh.tbl->buckets, \
232 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \
233 HASH_BLOOM_FREE((head)->hh.tbl); \
234 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
235 head = NULL; \
236 } else { \
237 unsigned _hd_bkt; \
238 _hd_hh_del = &((delptr)->hh); \
239 if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \
240 (head)->hh.tbl->tail = \
241 (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \
242 (head)->hh.tbl->hho); \
243 } \
244 if ((delptr)->hh.prev != NULL) { \
245 ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \
246 (head)->hh.tbl->hho))->next = (delptr)->hh.next; \
247 } else { \
248 DECLTYPE_ASSIGN(head,(delptr)->hh.next); \
249 } \
250 if (_hd_hh_del->next != NULL) { \
251 ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \
252 (head)->hh.tbl->hho))->prev = \
253 _hd_hh_del->prev; \
254 } \
255 HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \
256 HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \
257 (head)->hh.tbl->num_items--; \
258 } \
259 HASH_FSCK(hh,head); \
260 } while (0)
261
262
263
264 #define HASH_FIND_STR(head,findstr,out) \
265 HASH_FIND(hh,head,findstr,(unsigned)strlen(findstr),out)
266 #define HASH_ADD_STR(head,strfield,add) \
267 HASH_ADD(hh,head,strfield[0],(unsigned int)strlen(add->strfield),add)
268 #define HASH_REPLACE_STR(head,strfield,add,replaced) \
269 HASH_REPLACE(hh,head,strfield[0],(unsigned)strlen(add->strfield),add,replaced)
270 #define HASH_FIND_INT(head,findint,out) \
271 HASH_FIND(hh,head,findint,sizeof(int),out)
272 #define HASH_ADD_INT(head,intfield,add) \
273 HASH_ADD(hh,head,intfield,sizeof(int),add)
274 #define HASH_REPLACE_INT(head,intfield,add,replaced) \
275 HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced)
276 #define HASH_FIND_PTR(head,findptr,out) \
277 HASH_FIND(hh,head,findptr,sizeof(void *),out)
278 #define HASH_ADD_PTR(head,ptrfield,add) \
279 HASH_ADD(hh,head,ptrfield,sizeof(void *),add)
280 #define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \
281 HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced)
282 #define HASH_DEL(head,delptr) \
283 HASH_DELETE(hh,head,delptr)
284
285
286
287
288 #ifdef HASH_DEBUG
289 #define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
290 #define HASH_FSCK(hh,head) \
291 do { \
292 struct UT_hash_handle *_thh; \
293 if (head) { \
294 unsigned _bkt_i; \
295 unsigned _count; \
296 char *_prev; \
297 _count = 0; \
298 for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \
299 unsigned _bkt_count = 0; \
300 _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \
301 _prev = NULL; \
302 while (_thh) { \
303 if (_prev != (char*)(_thh->hh_prev)) { \
304 HASH_OOPS("invalid hh_prev %p, actual %p\n", \
305 _thh->hh_prev, _prev ); \
306 } \
307 _bkt_count++; \
308 _prev = (char*)(_thh); \
309 _thh = _thh->hh_next; \
310 } \
311 _count += _bkt_count; \
312 if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \
313 HASH_OOPS("invalid bucket count %u, actual %u\n", \
314 (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \
315 } \
316 } \
317 if (_count != (head)->hh.tbl->num_items) { \
318 HASH_OOPS("invalid hh item count %u, actual %u\n", \
319 (head)->hh.tbl->num_items, _count ); \
320 } \
321 \
322 _count = 0; \
323 _prev = NULL; \
324 _thh = &(head)->hh; \
325 while (_thh) { \
326 _count++; \
327 if (_prev !=(char*)(_thh->prev)) { \
328 HASH_OOPS("invalid prev %p, actual %p\n", \
329 _thh->prev, _prev ); \
330 } \
331 _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \
332 _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \
333 (head)->hh.tbl->hho) : NULL ); \
334 } \
335 if (_count != (head)->hh.tbl->num_items) { \
336 HASH_OOPS("invalid app item count %u, actual %u\n", \
337 (head)->hh.tbl->num_items, _count ); \
338 } \
339 } \
340 } while (0)
341 #else
342 #define HASH_FSCK(hh,head)
343 #endif
344
345
346
347
348 #ifdef HASH_EMIT_KEYS
349 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \
350 do { \
351 unsigned _klen = fieldlen; \
352 write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \
353 write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \
354 } while (0)
355 #else
356 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)
357 #endif
358
359
360 #ifdef HASH_FUNCTION
361 #define HASH_FCN HASH_FUNCTION
362 #else
363 #define HASH_FCN HASH_JEN
364 #endif
365
366
367 #define HASH_BER(key,keylen,num_bkts,hashv,bkt) \
368 do { \
369 unsigned _hb_keylen=(unsigned)keylen; \
370 const unsigned char *_hb_key=(const unsigned char*)(key); \
371 (hashv) = 0; \
372 while (_hb_keylen-- != 0U) { \
373 (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \
374 } \
375 bkt = (hashv) & (num_bkts-1U); \
376 } while (0)
377
378
379
380
381 #define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \
382 do { \
383 unsigned _sx_i; \
384 const unsigned char *_hs_key=(const unsigned char*)(key); \
385 hashv = 0; \
386 for(_sx_i=0; _sx_i < keylen; _sx_i++) { \
387 hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \
388 } \
389 bkt = hashv & (num_bkts-1U); \
390 } while (0)
391
392 #define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \
393 do { \
394 unsigned _fn_i; \
395 const unsigned char *_hf_key=(const unsigned char*)(key); \
396 hashv = 2166136261U; \
397 for(_fn_i=0; _fn_i < keylen; _fn_i++) { \
398 hashv = hashv ^ _hf_key[_fn_i]; \
399 hashv = hashv * 16777619U; \
400 } \
401 bkt = hashv & (num_bkts-1U); \
402 } while(0)
403
404 #define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \
405 do { \
406 unsigned _ho_i; \
407 const unsigned char *_ho_key=(const unsigned char*)(key); \
408 hashv = 0; \
409 for(_ho_i=0; _ho_i < keylen; _ho_i++) { \
410 hashv += _ho_key[_ho_i]; \
411 hashv += (hashv << 10); \
412 hashv ^= (hashv >> 6); \
413 } \
414 hashv += (hashv << 3); \
415 hashv ^= (hashv >> 11); \
416 hashv += (hashv << 15); \
417 bkt = hashv & (num_bkts-1U); \
418 } while(0)
419
420 #define HASH_JEN_MIX(a,b,c) \
421 do { \
422 a -= b; a -= c; a ^= ( c >> 13 ); \
423 b -= c; b -= a; b ^= ( a << 8 ); \
424 c -= a; c -= b; c ^= ( b >> 13 ); \
425 a -= b; a -= c; a ^= ( c >> 12 ); \
426 b -= c; b -= a; b ^= ( a << 16 ); \
427 c -= a; c -= b; c ^= ( b >> 5 ); \
428 a -= b; a -= c; a ^= ( c >> 3 ); \
429 b -= c; b -= a; b ^= ( a << 10 ); \
430 c -= a; c -= b; c ^= ( b >> 15 ); \
431 } while (0)
432
433 #define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \
434 do { \
435 unsigned _hj_i,_hj_j,_hj_k; \
436 unsigned const char *_hj_key=(unsigned const char*)(key); \
437 hashv = 0xfeedbeefu; \
438 _hj_i = _hj_j = 0x9e3779b9u; \
439 _hj_k = (unsigned)(keylen); \
440 while (_hj_k >= 12U) { \
441 _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \
442 + ( (unsigned)_hj_key[2] << 16 ) \
443 + ( (unsigned)_hj_key[3] << 24 ) ); \
444 _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \
445 + ( (unsigned)_hj_key[6] << 16 ) \
446 + ( (unsigned)_hj_key[7] << 24 ) ); \
447 hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \
448 + ( (unsigned)_hj_key[10] << 16 ) \
449 + ( (unsigned)_hj_key[11] << 24 ) ); \
450 \
451 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
452 \
453 _hj_key += 12; \
454 _hj_k -= 12U; \
455 } \
456 hashv += (unsigned)(keylen); \
457 switch ( _hj_k ) { \
458 case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \
459 case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \
460 case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \
461 case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \
462 case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \
463 case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \
464 case 5: _hj_j += _hj_key[4]; \
465 case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \
466 case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \
467 case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \
468 case 1: _hj_i += _hj_key[0]; \
469 } \
470 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
471 bkt = hashv & (num_bkts-1U); \
472 } while(0)
473
474
475 #undef get16bits
476 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
477 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
478 #define get16bits(d) (*((const uint16_t *) (d)))
479 #endif
480
481 #if !defined (get16bits)
482 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
483 +(uint32_t)(((const uint8_t *)(d))[0]) )
484 #endif
485 #define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \
486 do { \
487 unsigned const char *_sfh_key=(unsigned const char*)(key); \
488 uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \
489 \
490 unsigned _sfh_rem = _sfh_len & 3U; \
491 _sfh_len >>= 2; \
492 hashv = 0xcafebabeu; \
493 \
494 \
495 for (;_sfh_len > 0U; _sfh_len--) { \
496 hashv += get16bits (_sfh_key); \
497 _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \
498 hashv = (hashv << 16) ^ _sfh_tmp; \
499 _sfh_key += 2U*sizeof (uint16_t); \
500 hashv += hashv >> 11; \
501 } \
502 \
503 \
504 switch (_sfh_rem) { \
505 case 3: hashv += get16bits (_sfh_key); \
506 hashv ^= hashv << 16; \
507 hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \
508 hashv += hashv >> 11; \
509 break; \
510 case 2: hashv += get16bits (_sfh_key); \
511 hashv ^= hashv << 11; \
512 hashv += hashv >> 17; \
513 break; \
514 case 1: hashv += *_sfh_key; \
515 hashv ^= hashv << 10; \
516 hashv += hashv >> 1; \
517 } \
518 \
519 \
520 hashv ^= hashv << 3; \
521 hashv += hashv >> 5; \
522 hashv ^= hashv << 4; \
523 hashv += hashv >> 17; \
524 hashv ^= hashv << 25; \
525 hashv += hashv >> 6; \
526 bkt = hashv & (num_bkts-1U); \
527 } while(0)
528
529 #ifdef HASH_USING_NO_STRICT_ALIASING
530
531
532
533
534
535
536
537
538
539 #if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86))
540 #define MUR_GETBLOCK(p,i) p[i]
541 #else
542 #define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL)
543 #define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL)
544 #define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL)
545 #define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL)
546 #define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL))
547 #if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__))
548 #define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24))
549 #define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16))
550 #define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8))
551 #else
552 #define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24))
553 #define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16))
554 #define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8))
555 #endif
556 #define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \
557 (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \
558 (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \
559 MUR_ONE_THREE(p))))
560 #endif
561 #define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
562 #define MUR_FMIX(_h) \
563 do { \
564 _h ^= _h >> 16; \
565 _h *= 0x85ebca6bu; \
566 _h ^= _h >> 13; \
567 _h *= 0xc2b2ae35u; \
568 _h ^= _h >> 16; \
569 } while(0)
570
571 #define HASH_MUR(key,keylen,num_bkts,hashv,bkt) \
572 do { \
573 const uint8_t *_mur_data = (const uint8_t*)(key); \
574 const int _mur_nblocks = (int)(keylen) / 4; \
575 uint32_t _mur_h1 = 0xf88D5353u; \
576 uint32_t _mur_c1 = 0xcc9e2d51u; \
577 uint32_t _mur_c2 = 0x1b873593u; \
578 uint32_t _mur_k1 = 0; \
579 const uint8_t *_mur_tail; \
580 const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \
581 int _mur_i; \
582 for(_mur_i = -_mur_nblocks; _mur_i!=0; _mur_i++) { \
583 _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \
584 _mur_k1 *= _mur_c1; \
585 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
586 _mur_k1 *= _mur_c2; \
587 \
588 _mur_h1 ^= _mur_k1; \
589 _mur_h1 = MUR_ROTL32(_mur_h1,13); \
590 _mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \
591 } \
592 _mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \
593 _mur_k1=0; \
594 switch((keylen) & 3U) { \
595 case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16; \
596 case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8; \
597 case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \
598 _mur_k1 *= _mur_c1; \
599 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
600 _mur_k1 *= _mur_c2; \
601 _mur_h1 ^= _mur_k1; \
602 } \
603 _mur_h1 ^= (uint32_t)(keylen); \
604 MUR_FMIX(_mur_h1); \
605 hashv = _mur_h1; \
606 bkt = hashv & (num_bkts-1U); \
607 } while(0)
608 #endif
609
610
611 #define HASH_KEYCMP(a,b,len) memcmp(a,b,(unsigned long)(len))
612
613
614 #define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \
615 do { \
616 if (head.hh_head != NULL) { DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); } \
617 else { out=NULL; } \
618 while (out != NULL) { \
619 if ((out)->hh.keylen == (keylen_in)) { \
620 if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) { break; } \
621 } \
622 if ((out)->hh.hh_next != NULL) { DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); } \
623 else { out = NULL; } \
624 } \
625 } while(0)
626
627
628 #define HASH_ADD_TO_BKT(head,addhh) \
629 do { \
630 head.count++; \
631 (addhh)->hh_next = head.hh_head; \
632 (addhh)->hh_prev = NULL; \
633 if (head.hh_head != NULL) { (head).hh_head->hh_prev = (addhh); } \
634 (head).hh_head=addhh; \
635 if ((head.count >= ((head.expand_mult+1U) * HASH_BKT_CAPACITY_THRESH)) \
636 && ((addhh)->tbl->noexpand != 1U)) { \
637 HASH_EXPAND_BUCKETS((addhh)->tbl); \
638 } \
639 } while(0)
640
641
642 #define HASH_DEL_IN_BKT(hh,head,hh_del) \
643 (head).count--; \
644 if ((head).hh_head == hh_del) { \
645 (head).hh_head = hh_del->hh_next; \
646 } \
647 if (hh_del->hh_prev) { \
648 hh_del->hh_prev->hh_next = hh_del->hh_next; \
649 } \
650 if (hh_del->hh_next) { \
651 hh_del->hh_next->hh_prev = hh_del->hh_prev; \
652 }
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683 #define HASH_EXPAND_BUCKETS(tbl) \
684 do { \
685 unsigned _he_bkt; \
686 unsigned _he_bkt_i; \
687 struct UT_hash_handle *_he_thh, *_he_hh_nxt; \
688 UT_hash_bucket *_he_new_buckets, *_he_newbkt; \
689 _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \
690 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
691 if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \
692 memset(_he_new_buckets, 0, \
693 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
694 tbl->ideal_chain_maxlen = \
695 (tbl->num_items >> (tbl->log2_num_buckets+1U)) + \
696 (((tbl->num_items & ((tbl->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \
697 tbl->nonideal_items = 0; \
698 for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \
699 { \
700 _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \
701 while (_he_thh != NULL) { \
702 _he_hh_nxt = _he_thh->hh_next; \
703 HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2U, _he_bkt); \
704 _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \
705 if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \
706 tbl->nonideal_items++; \
707 _he_newbkt->expand_mult = _he_newbkt->count / \
708 tbl->ideal_chain_maxlen; \
709 } \
710 _he_thh->hh_prev = NULL; \
711 _he_thh->hh_next = _he_newbkt->hh_head; \
712 if (_he_newbkt->hh_head != NULL) { _he_newbkt->hh_head->hh_prev = \
713 _he_thh; } \
714 _he_newbkt->hh_head = _he_thh; \
715 _he_thh = _he_hh_nxt; \
716 } \
717 } \
718 uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \
719 tbl->num_buckets *= 2U; \
720 tbl->log2_num_buckets++; \
721 tbl->buckets = _he_new_buckets; \
722 tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \
723 (tbl->ineff_expands+1U) : 0U; \
724 if (tbl->ineff_expands > 1U) { \
725 tbl->noexpand=1; \
726 uthash_noexpand_fyi(tbl); \
727 } \
728 uthash_expand_fyi(tbl); \
729 } while(0)
730
731
732
733
734
735 #define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn)
736 #define HASH_SRT(hh,head,cmpfcn) \
737 do { \
738 unsigned _hs_i; \
739 unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \
740 struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \
741 if (head != NULL) { \
742 _hs_insize = 1; \
743 _hs_looping = 1; \
744 _hs_list = &((head)->hh); \
745 while (_hs_looping != 0U) { \
746 _hs_p = _hs_list; \
747 _hs_list = NULL; \
748 _hs_tail = NULL; \
749 _hs_nmerges = 0; \
750 while (_hs_p != NULL) { \
751 _hs_nmerges++; \
752 _hs_q = _hs_p; \
753 _hs_psize = 0; \
754 for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \
755 _hs_psize++; \
756 _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \
757 ((void*)((char*)(_hs_q->next) + \
758 (head)->hh.tbl->hho)) : NULL); \
759 if (! (_hs_q) ) { break; } \
760 } \
761 _hs_qsize = _hs_insize; \
762 while ((_hs_psize > 0U) || ((_hs_qsize > 0U) && (_hs_q != NULL))) {\
763 if (_hs_psize == 0U) { \
764 _hs_e = _hs_q; \
765 _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \
766 ((void*)((char*)(_hs_q->next) + \
767 (head)->hh.tbl->hho)) : NULL); \
768 _hs_qsize--; \
769 } else if ( (_hs_qsize == 0U) || (_hs_q == NULL) ) { \
770 _hs_e = _hs_p; \
771 if (_hs_p != NULL){ \
772 _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \
773 ((void*)((char*)(_hs_p->next) + \
774 (head)->hh.tbl->hho)) : NULL); \
775 } \
776 _hs_psize--; \
777 } else if (( \
778 cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \
779 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \
780 ) <= 0) { \
781 _hs_e = _hs_p; \
782 if (_hs_p != NULL){ \
783 _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \
784 ((void*)((char*)(_hs_p->next) + \
785 (head)->hh.tbl->hho)) : NULL); \
786 } \
787 _hs_psize--; \
788 } else { \
789 _hs_e = _hs_q; \
790 _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \
791 ((void*)((char*)(_hs_q->next) + \
792 (head)->hh.tbl->hho)) : NULL); \
793 _hs_qsize--; \
794 } \
795 if ( _hs_tail != NULL ) { \
796 _hs_tail->next = ((_hs_e != NULL) ? \
797 ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \
798 } else { \
799 _hs_list = _hs_e; \
800 } \
801 if (_hs_e != NULL) { \
802 _hs_e->prev = ((_hs_tail != NULL) ? \
803 ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \
804 } \
805 _hs_tail = _hs_e; \
806 } \
807 _hs_p = _hs_q; \
808 } \
809 if (_hs_tail != NULL){ \
810 _hs_tail->next = NULL; \
811 } \
812 if ( _hs_nmerges <= 1U ) { \
813 _hs_looping=0; \
814 (head)->hh.tbl->tail = _hs_tail; \
815 DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \
816 } \
817 _hs_insize *= 2U; \
818 } \
819 HASH_FSCK(hh,head); \
820 } \
821 } while (0)
822
823
824
825
826
827
828 #define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \
829 do { \
830 unsigned _src_bkt, _dst_bkt; \
831 void *_last_elt=NULL, *_elt; \
832 UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \
833 ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \
834 if (src != NULL) { \
835 for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \
836 for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \
837 _src_hh != NULL; \
838 _src_hh = _src_hh->hh_next) { \
839 _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \
840 if (cond(_elt)) { \
841 _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \
842 _dst_hh->key = _src_hh->key; \
843 _dst_hh->keylen = _src_hh->keylen; \
844 _dst_hh->hashv = _src_hh->hashv; \
845 _dst_hh->prev = _last_elt; \
846 _dst_hh->next = NULL; \
847 if (_last_elt_hh != NULL) { _last_elt_hh->next = _elt; } \
848 if (dst == NULL) { \
849 DECLTYPE_ASSIGN(dst,_elt); \
850 HASH_MAKE_TABLE(hh_dst,dst); \
851 } else { \
852 _dst_hh->tbl = (dst)->hh_dst.tbl; \
853 } \
854 HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \
855 HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \
856 (dst)->hh_dst.tbl->num_items++; \
857 _last_elt = _elt; \
858 _last_elt_hh = _dst_hh; \
859 } \
860 } \
861 } \
862 } \
863 HASH_FSCK(hh_dst,dst); \
864 } while (0)
865
866 #define HASH_CLEAR(hh,head) \
867 do { \
868 if (head != NULL) { \
869 uthash_free((head)->hh.tbl->buckets, \
870 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \
871 HASH_BLOOM_FREE((head)->hh.tbl); \
872 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
873 (head)=NULL; \
874 } \
875 } while(0)
876
877 #define HASH_OVERHEAD(hh,head) \
878 ((head != NULL) ? ( \
879 (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \
880 ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \
881 sizeof(UT_hash_table) + \
882 (HASH_BLOOM_BYTELEN))) : 0U)
883
884 #ifdef NO_DECLTYPE
885 #define HASH_ITER(hh,head,el,tmp) \
886 for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \
887 (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL)))
888 #else
889 #define HASH_ITER(hh,head,el,tmp) \
890 for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \
891 (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL)))
892 #endif
893
894
895 #define HASH_COUNT(head) HASH_CNT(hh,head)
896 #define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U)
897
898 typedef struct UT_hash_bucket {
899 struct UT_hash_handle *hh_head;
900 unsigned count;
901
902
903
904
905
906
907
908
909
910
911
912
913
914 unsigned expand_mult;
915
916 } UT_hash_bucket;
917
918
919 #define HASH_SIGNATURE 0xa0111fe1u
920 #define HASH_BLOOM_SIGNATURE 0xb12220f2u
921
922 typedef struct UT_hash_table {
923 UT_hash_bucket *buckets;
924 unsigned num_buckets, log2_num_buckets;
925 unsigned num_items;
926 struct UT_hash_handle *tail;
927 ptrdiff_t hho;
928
929
930
931 unsigned ideal_chain_maxlen;
932
933
934
935
936 unsigned nonideal_items;
937
938
939
940
941
942
943
944 unsigned ineff_expands, noexpand;
945
946 uint32_t signature;
947 #ifdef HASH_BLOOM
948 uint32_t bloom_sig;
949 uint8_t *bloom_bv;
950 uint8_t bloom_nbits;
951 #endif
952
953 } UT_hash_table;
954
955 typedef struct UT_hash_handle {
956 struct UT_hash_table *tbl;
957 void *prev;
958 void *next;
959 struct UT_hash_handle *hh_prev;
960 struct UT_hash_handle *hh_next;
961 void *key;
962 unsigned keylen;
963 unsigned hashv;
964 } UT_hash_handle;
965
966 #endif