Gitiles
Code Review Sign In
192.168.1.100 / T103 / 1f884588077ad3476b9c91cbb0ee9ee0332bbb68 / . / src / multimedia / audio-tuning / audio-xml-parser / mt2635 / include / uthash.h
blob: 39fd891b7be3f2873c7616bd9db740c7889b8d5e [file] [log] [blame]
rjw1f884582022-01-06 17:20:42 +0800[diff] [blame^]1/*
2Copyright (c) 2003-2014, Troy D. Hanson http://troydhanson.github.com/uthash/
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, 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
11THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22*/
23
24#ifndef UTHASH_H
25#define UTHASH_H
26
27#include <string.h> /* memcmp,strlen */
28#include <stddef.h> /* ptrdiff_t */
29#include <stdlib.h> /* exit() */
30
31/* These macros use decltype or the earlier __typeof GNU extension.
32 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
33 when compiling c++ source) this code uses whatever method is needed
34 or, for VS2008 where neither is available, uses casting workarounds. */
35#if defined(_MSC_VER) /* MS compiler */
36#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */
37#define DECLTYPE(x) (decltype(x))
38#else /* VS2008 or older (or VS2010 in C mode) */
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 /* GNU, Sun and other compilers */
46#define DECLTYPE(x) (__typeof(x))
47#endif
48
49#ifdef NO_DECLTYPE
50#define DECLTYPE_ASSIGN(dst,src) \
51do { \
52 char **_da_dst = (char**)(&(dst)); \
53 *_da_dst = (char*)(src); \
54} while(0)
55#else
56#define DECLTYPE_ASSIGN(dst,src) \
57do { \
58 (dst) = DECLTYPE(dst)(src); \
59} while(0)
60#endif
61
62/* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */
63#if defined (_WIN32)
64#if defined(_MSC_VER) && _MSC_VER >= 1600
65#include <stdint.h>
66#elif defined(__WATCOMC__)
67#include <stdint.h>
68#else
69typedef unsigned int uint32_t;
70typedef unsigned char uint8_t;
71#endif
72#else
73#include <stdint.h>
74#endif
75
76#define UTHASH_VERSION 1.9.9
77
78#ifndef uthash_fatal
79#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */
80#endif
81#ifndef uthash_malloc
82#define uthash_malloc(sz) malloc(sz) /* malloc fcn */
83#endif
84#ifndef uthash_free
85#define uthash_free(ptr,sz) free(ptr) /* free fcn */
86#endif
87
88#ifndef uthash_noexpand_fyi
89#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */
90#endif
91#ifndef uthash_expand_fyi
92#define uthash_expand_fyi(tbl) /* can be defined to log expands */
93#endif
94
95/* initial number of buckets */
96#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */
97#define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */
98#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */
99
100/* calculate the element whose hash handle address is hhe */
101#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
102
103#define HASH_FIND(hh,head,keyptr,keylen,out) \
104do { \
105 out=NULL; \
106 if (head) { \
107 unsigned _hf_bkt,_hf_hashv; \
108 HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \
109 if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \
110 HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \
111 keyptr,keylen,out); \
112 } \
113 } \
114} while (0)
115
116#ifdef HASH_BLOOM
117#define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM)
118#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0)
119#define HASH_BLOOM_MAKE(tbl) \
120do { \
121 (tbl)->bloom_nbits = HASH_BLOOM; \
122 (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \
123 if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \
124 memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \
125 (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \
126} while (0)
127
128#define HASH_BLOOM_FREE(tbl) \
129do { \
130 uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \
131} while (0)
132
133#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8)))
134#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8)))
135
136#define HASH_BLOOM_ADD(tbl,hashv) \
137 HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
138
139#define HASH_BLOOM_TEST(tbl,hashv) \
140 HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
141
142#else
143#define HASH_BLOOM_MAKE(tbl)
144#define HASH_BLOOM_FREE(tbl)
145#define HASH_BLOOM_ADD(tbl,hashv)
146#define HASH_BLOOM_TEST(tbl,hashv) (1)
147#define HASH_BLOOM_BYTELEN 0
148#endif
149
150#define HASH_MAKE_TABLE(hh,head) \
151do { \
152 (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \
153 sizeof(UT_hash_table)); \
154 if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \
155 memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \
156 (head)->hh.tbl->tail = &((head)->hh); \
157 (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \
158 (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \
159 (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \
160 (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \
161 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
162 if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \
163 memset((head)->hh.tbl->buckets, 0, \
164 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
165 HASH_BLOOM_MAKE((head)->hh.tbl); \
166 (head)->hh.tbl->signature = HASH_SIGNATURE; \
167} while(0)
168
169#define HASH_ADD(hh,head,fieldname,keylen_in,add) \
170 HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add)
171
172#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \
173do { \
174 replaced=NULL; \
175 HASH_FIND(hh,head,&((add)->fieldname),keylen_in,replaced); \
176 if (replaced!=NULL) { \
177 HASH_DELETE(hh,head,replaced); \
178 } \
179 HASH_ADD(hh,head,fieldname,keylen_in,add); \
180} while(0)
181
182#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \
183do { \
184 unsigned _ha_bkt; \
185 (add)->hh.next = NULL; \
186 (add)->hh.key = (char*)(keyptr); \
187 (add)->hh.keylen = (unsigned)(keylen_in); \
188 if (!(head)) { \
189 head = (add); \
190 (head)->hh.prev = NULL; \
191 HASH_MAKE_TABLE(hh,head); \
192 } else { \
193 (head)->hh.tbl->tail->next = (add); \
194 (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \
195 (head)->hh.tbl->tail = &((add)->hh); \
196 } \
197 (head)->hh.tbl->num_items++; \
198 (add)->hh.tbl = (head)->hh.tbl; \
199 HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \
200 (add)->hh.hashv, _ha_bkt); \
201 HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \
202 HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \
203 HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \
204 HASH_FSCK(hh,head); \
205} while(0)
206
207#define HASH_TO_BKT( hashv, num_bkts, bkt ) \
208do { \
209 bkt = ((hashv) & ((num_bkts) - 1)); \
210} while(0)
211
212/* delete "delptr" from the hash table.
213 * "the usual" patch-up process for the app-order doubly-linked-list.
214 * The use of _hd_hh_del below deserves special explanation.
215 * These used to be expressed using (delptr) but that led to a bug
216 * if someone used the same symbol for the head and deletee, like
217 * HASH_DELETE(hh,users,users);
218 * We want that to work, but by changing the head (users) below
219 * we were forfeiting our ability to further refer to the deletee (users)
220 * in the patch-up process. Solution: use scratch space to
221 * copy the deletee pointer, then the latter references are via that
222 * scratch pointer rather than through the repointed (users) symbol.
223 */
224#define HASH_DELETE(hh,head,delptr) \
225do { \
226 struct UT_hash_handle *_hd_hh_del; \
227 if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \
228 uthash_free((head)->hh.tbl->buckets, \
229 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \
230 HASH_BLOOM_FREE((head)->hh.tbl); \
231 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
232 head = NULL; \
233 } else { \
234 unsigned _hd_bkt; \
235 _hd_hh_del = &((delptr)->hh); \
236 if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \
237 (head)->hh.tbl->tail = \
238 (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \
239 (head)->hh.tbl->hho); \
240 } \
241 if ((delptr)->hh.prev) { \
242 ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \
243 (head)->hh.tbl->hho))->next = (delptr)->hh.next; \
244 } else { \
245 DECLTYPE_ASSIGN(head,(delptr)->hh.next); \
246 } \
247 if (_hd_hh_del->next) { \
248 ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \
249 (head)->hh.tbl->hho))->prev = \
250 _hd_hh_del->prev; \
251 } \
252 HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \
253 HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \
254 (head)->hh.tbl->num_items--; \
255 } \
256 HASH_FSCK(hh,head); \
257} while (0)
258
259
260/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */
261#define HASH_FIND_STR(head,findstr,out) \
262 HASH_FIND(hh,head,findstr,(unsigned)strlen(findstr),out)
263#define HASH_ADD_STR(head,strfield,add) \
264 HASH_ADD(hh,head,strfield[0],strlen(add->strfield),add)
265#define HASH_REPLACE_STR(head,strfield,add,replaced) \
266 HASH_REPLACE(hh,head,strfield[0],(unsigned)strlen(add->strfield),add,replaced)
267#define HASH_FIND_INT(head,findint,out) \
268 HASH_FIND(hh,head,findint,sizeof(int),out)
269#define HASH_ADD_INT(head,intfield,add) \
270 HASH_ADD(hh,head,intfield,sizeof(int),add)
271#define HASH_REPLACE_INT(head,intfield,add,replaced) \
272 HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced)
273#define HASH_FIND_PTR(head,findptr,out) \
274 HASH_FIND(hh,head,findptr,sizeof(void *),out)
275#define HASH_ADD_PTR(head,ptrfield,add) \
276 HASH_ADD(hh,head,ptrfield,sizeof(void *),add)
277#define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \
278 HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced)
279#define HASH_DEL(head,delptr) \
280 HASH_DELETE(hh,head,delptr)
281
282/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined.
283 * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined.
284 */
285#ifdef HASH_DEBUG
286#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
287#define HASH_FSCK(hh,head) \
288do { \
289 struct UT_hash_handle *_thh; \
290 if (head) { \
291 unsigned _bkt_i; \
292 unsigned _count; \
293 char *_prev; \
294 _count = 0; \
295 for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \
296 unsigned _bkt_count = 0; \
297 _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \
298 _prev = NULL; \
299 while (_thh) { \
300 if (_prev != (char*)(_thh->hh_prev)) { \
301 HASH_OOPS("invalid hh_prev %p, actual %p\n", \
302 _thh->hh_prev, _prev ); \
303 } \
304 _bkt_count++; \
305 _prev = (char*)(_thh); \
306 _thh = _thh->hh_next; \
307 } \
308 _count += _bkt_count; \
309 if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \
310 HASH_OOPS("invalid bucket count %u, actual %u\n", \
311 (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \
312 } \
313 } \
314 if (_count != (head)->hh.tbl->num_items) { \
315 HASH_OOPS("invalid hh item count %u, actual %u\n", \
316 (head)->hh.tbl->num_items, _count ); \
317 } \
318 /* traverse hh in app order; check next/prev integrity, count */ \
319 _count = 0; \
320 _prev = NULL; \
321 _thh = &(head)->hh; \
322 while (_thh) { \
323 _count++; \
324 if (_prev !=(char*)(_thh->prev)) { \
325 HASH_OOPS("invalid prev %p, actual %p\n", \
326 _thh->prev, _prev ); \
327 } \
328 _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \
329 _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \
330 (head)->hh.tbl->hho) : NULL ); \
331 } \
332 if (_count != (head)->hh.tbl->num_items) { \
333 HASH_OOPS("invalid app item count %u, actual %u\n", \
334 (head)->hh.tbl->num_items, _count ); \
335 } \
336 } \
337} while (0)
338#else
339#define HASH_FSCK(hh,head)
340#endif
341
342/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to
343 * the descriptor to which this macro is defined for tuning the hash function.
344 * The app can #include <unistd.h> to get the prototype for write(2). */
345#ifdef HASH_EMIT_KEYS
346#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \
347do { \
348 unsigned _klen = fieldlen; \
349 write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \
350 write(HASH_EMIT_KEYS, keyptr, fieldlen); \
351} while (0)
352#else
353#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)
354#endif
355
356/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */
357#ifdef HASH_FUNCTION
358#define HASH_FCN HASH_FUNCTION
359#else
360#define HASH_FCN HASH_JEN
361#endif
362
363/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */
364#define HASH_BER(key,keylen,num_bkts,hashv,bkt) \
365do { \
366 unsigned _hb_keylen=keylen; \
367 const char *_hb_key=(const char*)(key); \
368 (hashv) = 0; \
369 while (_hb_keylen--) { (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; } \
370 bkt = (hashv) & (num_bkts-1); \
371} while (0)
372
373
374/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at
375 * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
376#define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \
377do { \
378 unsigned _sx_i; \
379 const char *_hs_key=(const char*)(key); \
380 hashv = 0; \
381 for(_sx_i=0; _sx_i < keylen; _sx_i++) \
382 hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \
383 bkt = hashv & (num_bkts-1); \
384} while (0)
385/* FNV-1a variation */
386#define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \
387do { \
388 unsigned _fn_i; \
389 const char *_hf_key=(const char*)(key); \
390 hashv = 2166136261UL; \
391 for(_fn_i=0; _fn_i < keylen; _fn_i++) { \
392 hashv = hashv ^ _hf_key[_fn_i]; \
393 hashv = hashv * 16777619; \
394 } \
395 bkt = hashv & (num_bkts-1); \
396} while(0)
397
398#define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \
399do { \
400 unsigned _ho_i; \
401 const char *_ho_key=(const char*)(key); \
402 hashv = 0; \
403 for(_ho_i=0; _ho_i < keylen; _ho_i++) { \
404 hashv += _ho_key[_ho_i]; \
405 hashv += (hashv << 10); \
406 hashv ^= (hashv >> 6); \
407 } \
408 hashv += (hashv << 3); \
409 hashv ^= (hashv >> 11); \
410 hashv += (hashv << 15); \
411 bkt = hashv & (num_bkts-1); \
412} while(0)
413
414#define HASH_JEN_MIX(a,b,c) \
415do { \
416 a -= b; a -= c; a ^= ( c >> 13 ); \
417 b -= c; b -= a; b ^= ( a << 8 ); \
418 c -= a; c -= b; c ^= ( b >> 13 ); \
419 a -= b; a -= c; a ^= ( c >> 12 ); \
420 b -= c; b -= a; b ^= ( a << 16 ); \
421 c -= a; c -= b; c ^= ( b >> 5 ); \
422 a -= b; a -= c; a ^= ( c >> 3 ); \
423 b -= c; b -= a; b ^= ( a << 10 ); \
424 c -= a; c -= b; c ^= ( b >> 15 ); \
425} while (0)
426
427#define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \
428do { \
429 unsigned _hj_i,_hj_j,_hj_k; \
430 unsigned const char *_hj_key=(unsigned const char*)(key); \
431 hashv = 0xfeedbeef; \
432 _hj_i = _hj_j = 0x9e3779b9; \
433 _hj_k = (unsigned)(keylen); \
434 while (_hj_k >= 12) { \
435 _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \
436 + ( (unsigned)_hj_key[2] << 16 ) \
437 + ( (unsigned)_hj_key[3] << 24 ) ); \
438 _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \
439 + ( (unsigned)_hj_key[6] << 16 ) \
440 + ( (unsigned)_hj_key[7] << 24 ) ); \
441 hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \
442 + ( (unsigned)_hj_key[10] << 16 ) \
443 + ( (unsigned)_hj_key[11] << 24 ) ); \
444 \
445 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
446 \
447 _hj_key += 12; \
448 _hj_k -= 12; \
449 } \
450 hashv += keylen; \
451 switch ( _hj_k ) { \
452 case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \
453 case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \
454 case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \
455 case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \
456 case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \
457 case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \
458 case 5: _hj_j += _hj_key[4]; \
459 case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \
460 case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \
461 case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \
462 case 1: _hj_i += _hj_key[0]; \
463 } \
464 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \
465 bkt = hashv & (num_bkts-1); \
466} while(0)
467
468/* The Paul Hsieh hash function */
469#undef get16bits
470#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
471 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
472#define get16bits(d) (*((const uint16_t *) (d)))
473#endif
474
475#if !defined (get16bits)
476#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
477 +(uint32_t)(((const uint8_t *)(d))[0]) )
478#endif
479#define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \
480do { \
481 unsigned const char *_sfh_key=(unsigned const char*)(key); \
482 uint32_t _sfh_tmp, _sfh_len = keylen; \
483 \
484 int _sfh_rem = _sfh_len & 3; \
485 _sfh_len >>= 2; \
486 hashv = 0xcafebabe; \
487 \
488 /* Main loop */ \
489 for (;_sfh_len > 0; _sfh_len--) { \
490 hashv += get16bits (_sfh_key); \
491 _sfh_tmp = (uint32_t)(get16bits (_sfh_key+2)) << 11 ^ hashv; \
492 hashv = (hashv << 16) ^ _sfh_tmp; \
493 _sfh_key += 2*sizeof (uint16_t); \
494 hashv += hashv >> 11; \
495 } \
496 \
497 /* Handle end cases */ \
498 switch (_sfh_rem) { \
499 case 3: hashv += get16bits (_sfh_key); \
500 hashv ^= hashv << 16; \
501 hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)] << 18); \
502 hashv += hashv >> 11; \
503 break; \
504 case 2: hashv += get16bits (_sfh_key); \
505 hashv ^= hashv << 11; \
506 hashv += hashv >> 17; \
507 break; \
508 case 1: hashv += *_sfh_key; \
509 hashv ^= hashv << 10; \
510 hashv += hashv >> 1; \
511 } \
512 \
513 /* Force "avalanching" of final 127 bits */ \
514 hashv ^= hashv << 3; \
515 hashv += hashv >> 5; \
516 hashv ^= hashv << 4; \
517 hashv += hashv >> 17; \
518 hashv ^= hashv << 25; \
519 hashv += hashv >> 6; \
520 bkt = hashv & (num_bkts-1); \
521} while(0)
522
523#ifdef HASH_USING_NO_STRICT_ALIASING
524/* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads.
525 * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error.
526 * MurmurHash uses the faster approach only on CPU's where we know it's safe.
527 *
528 * Note the preprocessor built-in defines can be emitted using:
529 *
530 * gcc -m64 -dM -E - < /dev/null (on gcc)
531 * cc -## a.c (where a.c is a simple test file) (Sun Studio)
532 */
533#if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86))
534#define MUR_GETBLOCK(p,i) p[i]
535#else /* non intel */
536#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 0x3) == 0)
537#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 0x3) == 1)
538#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 0x3) == 2)
539#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 0x3) == 3)
540#define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL))
541#if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__))
542#define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24))
543#define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16))
544#define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8))
545#else /* assume little endian non-intel */
546#define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24))
547#define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16))
548#define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8))
549#endif
550#define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \
551 (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \
552 (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \
553 MUR_ONE_THREE(p))))
554#endif
555#define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
556#define MUR_FMIX(_h) \
557do { \
558 _h ^= _h >> 16; \
559 _h *= 0x85ebca6b; \
560 _h ^= _h >> 13; \
561 _h *= 0xc2b2ae35l; \
562 _h ^= _h >> 16; \
563} while(0)
564
565#define HASH_MUR(key,keylen,num_bkts,hashv,bkt) \
566do { \
567 const uint8_t *_mur_data = (const uint8_t*)(key); \
568 const int _mur_nblocks = (keylen) / 4; \
569 uint32_t _mur_h1 = 0xf88D5353; \
570 uint32_t _mur_c1 = 0xcc9e2d51; \
571 uint32_t _mur_c2 = 0x1b873593; \
572 uint32_t _mur_k1 = 0; \
573 const uint8_t *_mur_tail; \
574 const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+_mur_nblocks*4); \
575 int _mur_i; \
576 for(_mur_i = -_mur_nblocks; _mur_i; _mur_i++) { \
577 _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \
578 _mur_k1 *= _mur_c1; \
579 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
580 _mur_k1 *= _mur_c2; \
581 \
582 _mur_h1 ^= _mur_k1; \
583 _mur_h1 = MUR_ROTL32(_mur_h1,13); \
584 _mur_h1 = _mur_h1*5+0xe6546b64; \
585 } \
586 _mur_tail = (const uint8_t*)(_mur_data + _mur_nblocks*4); \
587 _mur_k1=0; \
588 switch((keylen) & 3) { \
589 case 3: _mur_k1 ^= _mur_tail[2] << 16; \
590 case 2: _mur_k1 ^= _mur_tail[1] << 8; \
591 case 1: _mur_k1 ^= _mur_tail[0]; \
592 _mur_k1 *= _mur_c1; \
593 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
594 _mur_k1 *= _mur_c2; \
595 _mur_h1 ^= _mur_k1; \
596 } \
597 _mur_h1 ^= (keylen); \
598 MUR_FMIX(_mur_h1); \
599 hashv = _mur_h1; \
600 bkt = hashv & (num_bkts-1); \
601} while(0)
602#endif /* HASH_USING_NO_STRICT_ALIASING */
603
604/* key comparison function; return 0 if keys equal */
605#define HASH_KEYCMP(a,b,len) memcmp(a,b,len)
606
607/* iterate over items in a known bucket to find desired item */
608#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \
609do { \
610 if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \
611 else out=NULL; \
612 while (out) { \
613 if ((out)->hh.keylen == keylen_in) { \
614 if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) break; \
615 } \
616 if ((out)->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); \
617 else out = NULL; \
618 } \
619} while(0)
620
621/* add an item to a bucket */
622#define HASH_ADD_TO_BKT(head,addhh) \
623do { \
624 head.count++; \
625 (addhh)->hh_next = head.hh_head; \
626 (addhh)->hh_prev = NULL; \
627 if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \
628 (head).hh_head=addhh; \
629 if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \
630 && (addhh)->tbl->noexpand != 1) { \
631 HASH_EXPAND_BUCKETS((addhh)->tbl); \
632 } \
633} while(0)
634
635/* remove an item from a given bucket */
636#define HASH_DEL_IN_BKT(hh,head,hh_del) \
637 (head).count--; \
638 if ((head).hh_head == hh_del) { \
639 (head).hh_head = hh_del->hh_next; \
640 } \
641 if (hh_del->hh_prev) { \
642 hh_del->hh_prev->hh_next = hh_del->hh_next; \
643 } \
644 if (hh_del->hh_next) { \
645 hh_del->hh_next->hh_prev = hh_del->hh_prev; \
646 }
647
648/* Bucket expansion has the effect of doubling the number of buckets
649 * and redistributing the items into the new buckets. Ideally the
650 * items will distribute more or less evenly into the new buckets
651 * (the extent to which this is true is a measure of the quality of
652 * the hash function as it applies to the key domain).
653 *
654 * With the items distributed into more buckets, the chain length
655 * (item count) in each bucket is reduced. Thus by expanding buckets
656 * the hash keeps a bound on the chain length. This bounded chain
657 * length is the essence of how a hash provides constant time lookup.
658 *
659 * The calculation of tbl->ideal_chain_maxlen below deserves some
660 * explanation. First, keep in mind that we're calculating the ideal
661 * maximum chain length based on the *new* (doubled) bucket count.
662 * In fractions this is just n/b (n=number of items,b=new num buckets).
663 * Since the ideal chain length is an integer, we want to calculate
664 * ceil(n/b). We don't depend on floating point arithmetic in this
665 * hash, so to calculate ceil(n/b) with integers we could write
666 *
667 * ceil(n/b) = (n/b) + ((n%b)?1:0)
668 *
669 * and in fact a previous version of this hash did just that.
670 * But now we have improved things a bit by recognizing that b is
671 * always a power of two. We keep its base 2 log handy (call it lb),
672 * so now we can write this with a bit shift and logical AND:
673 *
674 * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0)
675 *
676 */
677#define HASH_EXPAND_BUCKETS(tbl) \
678do { \
679 unsigned _he_bkt; \
680 unsigned _he_bkt_i; \
681 struct UT_hash_handle *_he_thh, *_he_hh_nxt; \
682 UT_hash_bucket *_he_new_buckets, *_he_newbkt; \
683 _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \
684 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
685 if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \
686 memset(_he_new_buckets, 0, \
687 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
688 tbl->ideal_chain_maxlen = \
689 (tbl->num_items >> (tbl->log2_num_buckets+1)) + \
690 ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \
691 tbl->nonideal_items = 0; \
692 for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \
693 { \
694 _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \
695 while (_he_thh) { \
696 _he_hh_nxt = _he_thh->hh_next; \
697 HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \
698 _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \
699 if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \
700 tbl->nonideal_items++; \
701 _he_newbkt->expand_mult = _he_newbkt->count / \
702 tbl->ideal_chain_maxlen; \
703 } \
704 _he_thh->hh_prev = NULL; \
705 _he_thh->hh_next = _he_newbkt->hh_head; \
706 if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \
707 _he_thh; \
708 _he_newbkt->hh_head = _he_thh; \
709 _he_thh = _he_hh_nxt; \
710 } \
711 } \
712 uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \
713 tbl->num_buckets *= 2; \
714 tbl->log2_num_buckets++; \
715 tbl->buckets = _he_new_buckets; \
716 tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \
717 (tbl->ineff_expands+1) : 0; \
718 if (tbl->ineff_expands > 1) { \
719 tbl->noexpand=1; \
720 uthash_noexpand_fyi(tbl); \
721 } \
722 uthash_expand_fyi(tbl); \
723} while(0)
724
725
726/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
727/* Note that HASH_SORT assumes the hash handle name to be hh.
728 * HASH_SRT was added to allow the hash handle name to be passed in. */
729#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn)
730#define HASH_SRT(hh,head,cmpfcn) \
731do { \
732 unsigned _hs_i; \
733 unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \
734 struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \
735 if (head) { \
736 _hs_insize = 1; \
737 _hs_looping = 1; \
738 _hs_list = &((head)->hh); \
739 while (_hs_looping) { \
740 _hs_p = _hs_list; \
741 _hs_list = NULL; \
742 _hs_tail = NULL; \
743 _hs_nmerges = 0; \
744 while (_hs_p) { \
745 _hs_nmerges++; \
746 _hs_q = _hs_p; \
747 _hs_psize = 0; \
748 for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \
749 _hs_psize++; \
750 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \
751 ((void*)((char*)(_hs_q->next) + \
752 (head)->hh.tbl->hho)) : NULL); \
753 if (! (_hs_q) ) break; \
754 } \
755 _hs_qsize = _hs_insize; \
756 while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \
757 if (_hs_psize == 0) { \
758 _hs_e = _hs_q; \
759 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \
760 ((void*)((char*)(_hs_q->next) + \
761 (head)->hh.tbl->hho)) : NULL); \
762 _hs_qsize--; \
763 } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \
764 _hs_e = _hs_p; \
765 if (_hs_p){ \
766 _hs_p = (UT_hash_handle*)((_hs_p->next) ? \
767 ((void*)((char*)(_hs_p->next) + \
768 (head)->hh.tbl->hho)) : NULL); \
769 } \
770 _hs_psize--; \
771 } else if (( \
772 cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \
773 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \
774 ) <= 0) { \
775 _hs_e = _hs_p; \
776 if (_hs_p){ \
777 _hs_p = (UT_hash_handle*)((_hs_p->next) ? \
778 ((void*)((char*)(_hs_p->next) + \
779 (head)->hh.tbl->hho)) : NULL); \
780 } \
781 _hs_psize--; \
782 } else { \
783 _hs_e = _hs_q; \
784 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \
785 ((void*)((char*)(_hs_q->next) + \
786 (head)->hh.tbl->hho)) : NULL); \
787 _hs_qsize--; \
788 } \
789 if ( _hs_tail ) { \
790 _hs_tail->next = ((_hs_e) ? \
791 ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \
792 } else { \
793 _hs_list = _hs_e; \
794 } \
795 if (_hs_e) { \
796 _hs_e->prev = ((_hs_tail) ? \
797 ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \
798 } \
799 _hs_tail = _hs_e; \
800 } \
801 _hs_p = _hs_q; \
802 } \
803 if (_hs_tail){ \
804 _hs_tail->next = NULL; \
805 } \
806 if ( _hs_nmerges <= 1 ) { \
807 _hs_looping=0; \
808 (head)->hh.tbl->tail = _hs_tail; \
809 DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \
810 } \
811 _hs_insize *= 2; \
812 } \
813 HASH_FSCK(hh,head); \
814 } \
815} while (0)
816
817/* This function selects items from one hash into another hash.
818 * The end result is that the selected items have dual presence
819 * in both hashes. There is no copy of the items made; rather
820 * they are added into the new hash through a secondary hash
821 * hash handle that must be present in the structure. */
822#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \
823do { \
824 unsigned _src_bkt, _dst_bkt; \
825 void *_last_elt=NULL, *_elt; \
826 UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \
827 ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \
828 if (src) { \
829 for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \
830 for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \
831 _src_hh; \
832 _src_hh = _src_hh->hh_next) { \
833 _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \
834 if (cond(_elt)) { \
835 _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \
836 _dst_hh->key = _src_hh->key; \
837 _dst_hh->keylen = _src_hh->keylen; \
838 _dst_hh->hashv = _src_hh->hashv; \
839 _dst_hh->prev = _last_elt; \
840 _dst_hh->next = NULL; \
841 if (_last_elt_hh) { _last_elt_hh->next = _elt; } \
842 if (!dst) { \
843 DECLTYPE_ASSIGN(dst,_elt); \
844 HASH_MAKE_TABLE(hh_dst,dst); \
845 } else { \
846 _dst_hh->tbl = (dst)->hh_dst.tbl; \
847 } \
848 HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \
849 HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \
850 (dst)->hh_dst.tbl->num_items++; \
851 _last_elt = _elt; \
852 _last_elt_hh = _dst_hh; \
853 } \
854 } \
855 } \
856 } \
857 HASH_FSCK(hh_dst,dst); \
858} while (0)
859
860#define HASH_CLEAR(hh,head) \
861do { \
862 if (head) { \
863 uthash_free((head)->hh.tbl->buckets, \
864 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \
865 HASH_BLOOM_FREE((head)->hh.tbl); \
866 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \
867 (head)=NULL; \
868 } \
869} while(0)
870
871#define HASH_OVERHEAD(hh,head) \
872 ((head) ? ( \
873 (size_t)((((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \
874 ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \
875 (sizeof(UT_hash_table)) + \
876 (HASH_BLOOM_BYTELEN)))) : 0)
877
878#ifdef NO_DECLTYPE
879#define HASH_ITER(hh,head,el,tmp) \
880for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \
881 el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL))
882#else
883#define HASH_ITER(hh,head,el,tmp) \
884for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \
885 el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL))
886#endif
887
888/* obtain a count of items in the hash */
889#define HASH_COUNT(head) HASH_CNT(hh,head)
890#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0)
891
892typedef struct UT_hash_bucket {
893 struct UT_hash_handle *hh_head;
894 unsigned count;
895
896 /* expand_mult is normally set to 0. In this situation, the max chain length
897 * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If
898 * the bucket's chain exceeds this length, bucket expansion is triggered).
899 * However, setting expand_mult to a non-zero value delays bucket expansion
900 * (that would be triggered by additions to this particular bucket)
901 * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH.
902 * (The multiplier is simply expand_mult+1). The whole idea of this
903 * multiplier is to reduce bucket expansions, since they are expensive, in
904 * situations where we know that a particular bucket tends to be overused.
905 * It is better to let its chain length grow to a longer yet-still-bounded
906 * value, than to do an O(n) bucket expansion too often.
907 */
908 unsigned expand_mult;
909
910} UT_hash_bucket;
911
912/* random signature used only to find hash tables in external analysis */
913#define HASH_SIGNATURE 0xa0111fe1
914#define HASH_BLOOM_SIGNATURE 0xb12220f2
915
916typedef struct UT_hash_table {
917 UT_hash_bucket *buckets;
918 unsigned num_buckets, log2_num_buckets;
919 unsigned num_items;
920 struct UT_hash_handle *tail; /* tail hh in app order, for fast append */
921 ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */
922
923 /* in an ideal situation (all buckets used equally), no bucket would have
924 * more than ceil(#items/#buckets) items. that's the ideal chain length. */
925 unsigned ideal_chain_maxlen;
926
927 /* nonideal_items is the number of items in the hash whose chain position
928 * exceeds the ideal chain maxlen. these items pay the penalty for an uneven
929 * hash distribution; reaching them in a chain traversal takes >ideal steps */
930 unsigned nonideal_items;
931
932 /* ineffective expands occur when a bucket doubling was performed, but
933 * afterward, more than half the items in the hash had nonideal chain
934 * positions. If this happens on two consecutive expansions we inhibit any
935 * further expansion, as it's not helping; this happens when the hash
936 * function isn't a good fit for the key domain. When expansion is inhibited
937 * the hash will still work, albeit no longer in constant time. */
938 unsigned ineff_expands, noexpand;
939
940 uint32_t signature; /* used only to find hash tables in external analysis */
941#ifdef HASH_BLOOM
942 uint32_t bloom_sig; /* used only to test bloom exists in external analysis */
943 uint8_t *bloom_bv;
944 char bloom_nbits;
945#endif
946
947} UT_hash_table;
948
949typedef struct UT_hash_handle {
950 struct UT_hash_table *tbl;
951 void *prev; /* prev element in app order */
952 void *next; /* next element in app order */
953 struct UT_hash_handle *hh_prev; /* previous hh in bucket order */
954 struct UT_hash_handle *hh_next; /* next hh in bucket order */
955 void *key; /* ptr to enclosing struct's key */
956 unsigned keylen; /* enclosing struct's key len */
957 unsigned hashv; /* result of hash-fcn(key) */
958} UT_hash_handle;
959
960#endif /* UTHASH_H */