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