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