Chameleon

Chameleon Svn Source Tree

Root/branches/cparm/i386/libsaio/uthash.h

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

Archive Download this file

Revision: HEAD