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