/[opencvs]/eyes/uthash.h
ViewVC logotype

Annotation of /eyes/uthash.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.1 - (hide annotations)
Thu Mar 8 15:49:21 2012 UTC (7 years, 11 months ago) by hib
Branch: MAIN
CVS Tags: HEAD
File MIME type: text/plain
more cleanup for girl3 (Jenni) and cyclone is still in process

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

  ViewVC Help
Powered by ViewVC 1.1.26