Context Navigation

source: libabac/uthash.h @ 63dcd99

abac0-leak

Last change on this file since 63dcd99 was 15200be, checked in by Mike Ryan <mikeryan@…>, 14 years ago
move libabac into its own directory
Property mode set to `100644`
File size: 63.0 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: