2
Copyright (c) 2003-2006, Troy Hanson http://uthash.sourceforge.net
5
Redistribution and use in source and binary forms, with or without
6
modification, are permitted provided that the following conditions are met:
8
* Redistributions of source code must retain the above copyright
9
notice, this list of conditions and the following disclaimer.
10
* Redistributions in binary form must reproduce the above copyright
11
notice, this list of conditions and the following disclaimer in
12
the documentation and/or other materials provided with the
14
* Neither the name of the copyright holder nor the names of its
15
contributors may be used to endorse or promote products derived
16
from this software without specific prior written permission.
18
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
19
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
20
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
21
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
22
OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
25
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
27
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31
#include <string.h> /* memcmp,strlen */
36
#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */
37
#define uthash_bkt_malloc(sz) malloc(sz) /* malloc fcn for UT_hash_bucket's */
38
#define uthash_bkt_free(ptr) free(ptr) /* free fcn for UT_hash_bucket's */
39
#define uthash_tbl_malloc(sz) malloc(sz) /* malloc fcn for UT_hash_table */
40
#define uthash_tbl_free(ptr) free(ptr) /* free fcn for UT_hash_table */
42
#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */
43
#define uthash_expand_fyi(tbl) /* can be defined to log expands */
45
/* initial number of buckets */
46
#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */
47
#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */
49
#define HASH_FIND(hh,head,keyptr,keylen_in,out) \
53
(head)->hh.tbl->key = (char*)(keyptr); \
54
(head)->hh.tbl->keylen = keylen_in; \
55
HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen, \
56
(head)->hh.tbl->num_buckets,(head)->hh.tbl->bkt, \
57
(head)->hh.tbl->i, (head)->hh.tbl->j,(head)->hh.tbl->k); \
58
HASH_FIND_IN_BKT(hh, (head)->hh.tbl->buckets[ (head)->hh.tbl->bkt], \
59
keyptr,keylen_in,out); \
63
#define HASH_ADD(hh,head,fieldname,keylen_in,add) \
64
HASH_ADD_KEYPTR(hh,head,&add->fieldname,keylen_in,add)
66
#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \
68
add->hh.next = NULL; \
69
add->hh.key = (char*)keyptr; \
70
add->hh.keylen = keylen_in; \
74
(head)->hh.prev = NULL; \
75
(head)->hh.tbl = (UT_hash_table*)uthash_tbl_malloc( \
76
sizeof(UT_hash_table)); \
77
if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \
78
(head)->hh.tbl->name = #head; \
79
(head)->hh.tbl->tail = &(add->hh); \
80
(head)->hh.tbl->noexpand = 0; \
81
(head)->hh.tbl->hash_q = 1<<16; \
82
(head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \
83
(head)->hh.tbl->num_items = 0; \
84
(head)->hh.tbl->hho = ((long)(&add->hh) - (long)(add)); \
85
(head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_bkt_malloc( \
86
HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
87
if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \
88
memset((head)->hh.tbl->buckets, 0, \
89
HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \
91
(head)->hh.tbl->tail->next = add; \
92
add->hh.prev = (head)->hh.tbl->tail->elmt; \
93
(head)->hh.tbl->tail = &(add->hh); \
95
(head)->hh.tbl->num_items++; \
96
add->hh.tbl = (head)->hh.tbl; \
97
(head)->hh.tbl->key = (char*)keyptr; \
98
(head)->hh.tbl->keylen = keylen_in; \
99
HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen, \
100
(head)->hh.tbl->num_buckets, \
101
(head)->hh.tbl->bkt, \
102
(head)->hh.tbl->i, (head)->hh.tbl->j, (head)->hh.tbl->k ); \
103
HASH_ADD_TO_BKT(hh,(head)->hh.tbl->buckets[(head)->hh.tbl->bkt],add); \
104
HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \
108
#define HASH_DELETE(hh,head,delptr) \
110
if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \
111
uthash_bkt_free((head)->hh.tbl->buckets ); \
112
uthash_tbl_free((head)->hh.tbl); \
115
if ((delptr) == (head)->hh.tbl->tail->elmt) { \
116
(head)->hh.tbl->tail = (void*)(((long)((delptr)->hh.prev)) + \
117
(head)->hh.tbl->hho); \
119
if ((delptr)->hh.prev) { \
120
((UT_hash_handle*)(((long)((delptr)->hh.prev)) + \
121
(head)->hh.tbl->hho))->next = (delptr)->hh.next; \
123
head = (delptr)->hh.next; \
125
if ((delptr)->hh.next) { \
126
((UT_hash_handle*)(((long)((delptr)->hh.next)) + \
127
(head)->hh.tbl->hho))->prev = (delptr)->hh.prev; \
129
(head)->hh.tbl->key = (char*)((delptr)->hh.key); \
130
(head)->hh.tbl->keylen = (delptr)->hh.keylen; \
131
HASH_FCN((head)->hh.tbl->key,(head)->hh.tbl->keylen, \
132
(head)->hh.tbl->num_buckets,(head)->hh.tbl->bkt, \
133
(head)->hh.tbl->i,(head)->hh.tbl->j,(head)->hh.tbl->k ); \
134
HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[(head)->hh.tbl->bkt], \
136
(head)->hh.tbl->num_items--; \
142
/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */
143
#define HASH_FIND_STR(head,findstr,out) \
144
HASH_FIND(hh,head,findstr,strlen(findstr),out)
145
#define HASH_ADD_STR(head,strfield,add) \
146
HASH_ADD(hh,head,strfield,strlen(add->strfield),add)
147
#define HASH_FIND_INT(head,findint,out) \
148
HASH_FIND(hh,head,findint,sizeof(int),out)
149
#define HASH_ADD_INT(head,intfield,add) \
150
HASH_ADD(hh,head,intfield,sizeof(int),add)
151
#define HASH_DEL(head,delptr) \
152
HASH_DELETE(hh,head,delptr)
154
/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined.
155
* This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined.
156
* This function misuses fields in UT_hash_table for its bookkeeping variables.
159
#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
160
#define HASH_FSCK(head) \
163
(head)->hh.tbl->keylen = 0; /* item counter */ \
164
for( (head)->hh.tbl->bkt_i = 0; \
165
(head)->hh.tbl->bkt_i < (head)->hh.tbl->num_buckets; \
166
(head)->hh.tbl->bkt_i++) \
168
(head)->hh.tbl->bkt_ideal = 0; /* bkt item counter */ \
169
(head)->hh.tbl->hh = \
170
(head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].hh_head; \
171
(head)->hh.tbl->key = NULL; /* hh_prev */ \
172
while ((head)->hh.tbl->hh) { \
173
if ((head)->hh.tbl->key != \
174
(char*)((head)->hh.tbl->hh->hh_prev)) { \
175
HASH_OOPS("invalid hh_prev %x, actual %x\n", \
176
(head)->hh.tbl->hh->hh_prev, \
177
(head)->hh.tbl->key ); \
179
(head)->hh.tbl->bkt_ideal++; \
180
(head)->hh.tbl->key = (char*)((head)->hh.tbl->hh); \
181
(head)->hh.tbl->hh = (head)->hh.tbl->hh->hh_next; \
183
(head)->hh.tbl->keylen += (head)->hh.tbl->bkt_ideal; \
184
if ((head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count \
185
!= (head)->hh.tbl->bkt_ideal) { \
186
HASH_OOPS("invalid bucket count %d, actual %d\n", \
187
(head)->hh.tbl->buckets[(head)->hh.tbl->bkt_i].count, \
188
(head)->hh.tbl->bkt_ideal); \
191
if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) { \
192
HASH_OOPS("invalid hh item count %d, actual %d\n", \
193
(head)->hh.tbl->num_items, (head)->hh.tbl->keylen ); \
195
/* traverse hh in app order; check next/prev integrity, count */ \
196
(head)->hh.tbl->keylen = 0; /* item counter */ \
197
(head)->hh.tbl->key = NULL; /* app prev */ \
198
(head)->hh.tbl->hh = &(head)->hh; \
199
while ((head)->hh.tbl->hh) { \
200
(head)->hh.tbl->keylen++; \
201
if ((head)->hh.tbl->key !=(char*)((head)->hh.tbl->hh->prev)) {\
202
HASH_OOPS("invalid prev %x, actual %x\n", \
203
(head)->hh.tbl->hh->prev, \
204
(head)->hh.tbl->key ); \
206
(head)->hh.tbl->key = (head)->hh.tbl->hh->elmt; \
207
(head)->hh.tbl->hh = ( (head)->hh.tbl->hh->next ? \
208
(UT_hash_handle*)((long)((head)->hh.tbl->hh->next) + \
209
(head)->hh.tbl->hho) \
212
if ((head)->hh.tbl->keylen != (head)->hh.tbl->num_items) { \
213
HASH_OOPS("invalid app item count %d, actual %d\n", \
214
(head)->hh.tbl->num_items, (head)->hh.tbl->keylen ); \
219
#define HASH_FSCK(head)
222
/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to
223
* the descriptor to which this macro is defined for tuning the hash function.
224
* The app can #include <unistd.h> to get the prototype for write(2). */
225
#ifdef HASH_EMIT_KEYS
226
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \
227
(head)->hh.tbl->keylen = fieldlen; \
228
write(HASH_EMIT_KEYS, &((head)->hh.tbl->keylen), sizeof(int)); \
229
write(HASH_EMIT_KEYS, keyptr, fieldlen);
231
#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen)
234
/* default to Jenkins unless specified e.g. DHASH_FUNCTION=HASH_SAX */
236
#define HASH_FCN HASH_FUNCTION
238
#define HASH_FCN HASH_JEN
241
/* The Bernstein hash function, used in Perl prior to v5.6 */
242
#define HASH_BER(key,keylen,num_bkts,bkt,i,j,k) \
244
while (keylen--) bkt = (bkt * 33) + *key++; \
248
/* SAX/FNV/OAT/JEN/JSW hash functions are macro variants of those listed at
249
* http://eternallyconfuzzled.com/tuts/hashing.html (thanks Julienne Walker) */
250
#define HASH_SAX(key,keylen,num_bkts,bkt,i,j,k) \
252
for(i=0; i < keylen; i++) \
253
bkt ^= (bkt << 5) + (bkt >> 2) + key[i]; \
256
#define HASH_FNV(key,keylen,num_bkts,bkt,i,j,k) \
257
bkt = 2166136261UL; \
258
for(i=0; i < keylen; i++) \
259
bkt = (bkt * 16777619) ^ key[i]; \
262
#define HASH_OAT(key,keylen,num_bkts,bkt,i,j,k) \
264
for(i=0; i < keylen; i++) { \
266
bkt += (bkt << 10); \
270
bkt ^= (bkt >> 11); \
271
bkt += (bkt << 15); \
274
#define HASH_JEN_MIX(a,b,c) \
276
a -= b; a -= c; a ^= ( c >> 13 ); \
277
b -= c; b -= a; b ^= ( a << 8 ); \
278
c -= a; c -= b; c ^= ( b >> 13 ); \
279
a -= b; a -= c; a ^= ( c >> 12 ); \
280
b -= c; b -= a; b ^= ( a << 16 ); \
281
c -= a; c -= b; c ^= ( b >> 5 ); \
282
a -= b; a -= c; a ^= ( c >> 3 ); \
283
b -= c; b -= a; b ^= ( a << 10 ); \
284
c -= a; c -= b; c ^= ( b >> 15 ); \
287
#define HASH_JEN(key,keylen,num_bkts,bkt,i,j,k) \
289
i = j = 0x9e3779b9; \
292
i += (key[0] + ( (unsigned)key[1] << 8 ) \
293
+ ( (unsigned)key[2] << 16 ) \
294
+ ( (unsigned)key[3] << 24 ) ); \
295
j += (key[4] + ( (unsigned)key[5] << 8 ) \
296
+ ( (unsigned)key[6] << 16 ) \
297
+ ( (unsigned)key[7] << 24 ) ); \
298
bkt += (key[8] + ( (unsigned)key[9] << 8 ) \
299
+ ( (unsigned)key[10] << 16 ) \
300
+ ( (unsigned)key[11] << 24 ) ); \
302
HASH_JEN_MIX(i, j, bkt); \
309
case 11: bkt += ( (unsigned)key[10] << 24 ); \
310
case 10: bkt += ( (unsigned)key[9] << 16 ); \
311
case 9: bkt += ( (unsigned)key[8] << 8 ); \
312
case 8: j += ( (unsigned)key[7] << 24 ); \
313
case 7: j += ( (unsigned)key[6] << 16 ); \
314
case 6: j += ( (unsigned)key[5] << 8 ); \
315
case 5: j += key[4]; \
316
case 4: i += ( (unsigned)key[3] << 24 ); \
317
case 3: i += ( (unsigned)key[2] << 16 ); \
318
case 2: i += ( (unsigned)key[1] << 8 ); \
319
case 1: i += key[0]; \
321
HASH_JEN_MIX(i, j, bkt); \
324
#define HASH_JSW(key,keylen,num_bkts,bkt,i,j,k) \
326
for(i=0; i < keylen; i++) { \
327
bkt = (bkt << 1 | bkt >> 31) ^ \
329
"\xe9\x81\x51\xe4\x84\x9d\x32\xd9\x2d\xda\xca\x94\xa7\x85\x1e" \
330
"\x28\xfe\xa3\x18\x60\x28\x45\xa6\x48\x67\xdb\xd5\xa2\x91\x4d" \
331
"\x1a\x2f\x97\x37\x82\xd8\xe9\x1c\xb7\x7b\x3c\xa5\x4c\x23\x2" \
332
"\x42\x85\x20\x78\x6c\x6\x67\x6f\xa5\xcb\x53\x8c\xe1\x1f\x12" \
333
"\x66\xcb\xa0\xbe\x47\x59\x8\x20\xd5\x31\xd9\xdc\xcc\x27\xc3" \
334
"\x4d\x8\x9f\xb3\x50\x8\x90\x4f\x1f\x20\x60\xb8\xe2\x7b\x63" \
335
"\x49\xc0\x64\xc7\xaf\xc9\x81\x9c\x5f\x7d\x45\xc5\xe4\xe4\x86" \
336
"\xaf\x1a\x15\x6c\x9b\xc3\x7c\xc5\x88\x2b\xf3\xd9\x72\x76\x47" \
337
"\x56\xe6\x8c\xd1\x6c\x94\x41\x59\x4d\xe2\xd7\x44\x9a\x55\x5e" \
338
"\xee\x9d\x7c\x8f\x21\x57\x10\x77\xf7\x4b\xd8\x7e\xc0\x4d\xba" \
339
"\x1f\x96\x2a\x60\x13\xae\xab\x58\x70\xe5\x23\x62\x2b\x63\xb6" \
340
"\x42\x8e\x8f\x57\xf2\xfa\x47\x37\x91\xac\x11\x3d\x9a\x85\x73" \
341
"\x9e\x39\x65\xc8\xd4\x5b\xaa\x35\x72\x5f\x40\x31\x9a\xb0\xdd" \
342
"\xa9\x2c\x16\xa3\x32\xef\xcb\x8c\x80\x33\x60\xd\x85\xce\x22" \
343
"\x8c\x28\x6\x7f\xff\xf6\x8a\x5f\x21\x8e\xf2\xd0\xd9\x63\x66" \
344
"\x22\xe8\xe6\x3\x39\xfd\x10\x69\xce\x6c\xc4\xde\xf3\x87\x56" \
345
"\xc8\x4a\x31\x51\x58\xc5\x62\x30\x8e\xd\xd5\x2f\x7c\x24\xca" \
346
"\xd1\x12\x1b\x3a\x3e\x95\x99\xa\x7\xc1\x83\xd0\x4f\x97\x8c" \
347
"\xf1\xb0\x9c\xd8\xb9\x72\xd7\x3e\x6b\x66\x83\x8e\xe9\x86\xad" \
348
"\xfa\xc2\xe\x4\xb5\x7b\x5d\x0\xbc\x47\xbe\x4\x69\xfa\xd1" \
349
"\x29\x5c\x77\x38\xfc\x88\xeb\xd5\xe1\x17\x54\xf6\xe5\xb3\xae" \
350
"\xc7\x14\xb6\x4b\xa6\x42\x4b\xa3\xdf\xa5\xcf\xdb\xad\xcd\x2c" \
351
"\xa3\x3\x13\xc0\x42\x5d\x6e\x3c\xfe\xd8\xeb\xa7\x96\x47\x2b" \
352
"\x61\xb3\x70\xc9\x6d\xff\x1a\x82\x65\xdc\x92\x4b\x1a\x52\x75" \
353
"\xa5\x61\x55\x2b\xe\x7\xde\x1e\x71\xc5\x12\x34\x59\x4f\x19" \
354
"\x2\x9\xb6\x5\xe6\x7b\xad\xb6\x92\xfb\x84\x32\xf1\x45\x6c" \
355
"\xec\x1a\xcb\x39\x32\x2\x47\x51\xd6\xc8\x9d\xd0\xb1\xdb\xa8" \
356
"\x90\x4c\x65\x5a\x77\x1f\xca\x74\x8e\x3b\xce\x76\x55\x8b\x78" \
357
"\x3c\xf3\x19\x8f\xe1\xc3\xa9\x8a\xc8\xf3\x14\x30\x4e\x77\xe9" \
358
"\xd5\x6a\xcb\x96\x2f\x31\x35\xff\x6b\x10\x92\xf7\xc4\x33\xb8" \
359
"\x76\x35\x6\xf\x82\x1c\xfa\x1f\x92\x47\xa1\xf9\x7e\xe5\x51" \
360
"\xee\x63\xaa\x9a\x38\xa3\xa1\x86\xbf\xf0\xe8\x29\xe1\x19\x83" \
361
"\xff\x36\x3c\x26\x15\x89\x36\x22\x93\x41\x3e\x63\x36\x34\x4c" \
362
"\xda\x18\xd4\x18\xd8\xc8\x8a\x10\x1f\x14\x4c\x7f\x79\xfc\x46" \
363
"\xbb\xc8\x24\x51\xc7\xe4\xfb\xc0\x78\xb1\xe9\xac\xf1\x3d\x55" \
364
"\x51\x9c\x8\xf0\xa6\x3\xcb\x91\xc6\xf4\xe2\xd4\xe5\x18\x61" \
365
"\xfc\x8f\x8a\xce\x89\x33\xcd\xf\x7d\x50\xa0\x7d\x3f\xac\x49" \
366
"\xe1\x71\x92\xc7\x8d\xc0\xd0\x6e\xe4\xf7\xcd\xc1\x47\x9f\x99" \
367
"\xd5\x7\x20\xad\x64\xdb\xab\x44\xd4\x8\xc6\x9a\xa4\xa7\x7c" \
368
"\x9b\x13\xe4\x9c\x88\xec\xc4\xcb\xe1\x3f\x5\x5\xf\xd\x3a" \
369
"\x75\xed\xfa\xc0\x23\x34\x74\xfd\xca\x1c\x74\x77\x29\xc8\xb6" \
370
"\xe2\xbb\xa1\xa\x2e\xae\x65\x3e\xcb\xf5\x5e\xe0\x29\x4c\xfa" \
371
"\xab\x35\xea\x7\x9f\xb3\x3b\x9c\x4e\x86\xe8\x5b\x76\x11\xf1" \
372
"\xbf\x7f\x73\x34\x71\x9\x2d\x2a\x60\x8f\x14\x12\xba\x26\x84" \
373
"\xb9\x94\xa9\x59\x38\x25\xfd\x77\xc3\xe5\x86\xc4\x3\xda\x32" \
374
"\x30\xd8\x84\x81\x83\x14\x8c\x24\xee\x51\xa9\x92\x61\xb2\xeb" \
375
"\xce\xac\x34\xc1\xad\x24\x74\xce\xf9\xce\x5c\xfd\x45\x69\x1d" \
376
"\xc6\xc2\xaf\x7c\x8d\x5\x52\xb5\x88\x2f\x9f\xee\x6b\x5f\xbd" \
377
"\xfe\x22\x6\x47\xa2\xc8\x25\x37\x67\x44\x4c\xe\xfe\x7e\x5a" \
378
"\x36\x7f\x18\x83\x8f\x82\x87\x3b\xbf\xb8\xd2\x37\xff\x52\x60" \
379
"\xb5\xf3\xd\x20\x80\xcc\xb2\x7a\xdd\xc2\x94\xbc\xe3\xb1\x87" \
380
"\x3e\x49\x57\xcc\xe9\x5a\xea\xb4\xe\xdf\xa6\x8f\x70\x60\x32" \
381
"\xb\x7d\x74\xf5\x46\xb6\x93\xc2\x5\x92\x72\xfc\xd9\xd2\xe5" \
382
"\x90\x36\x2a\xd4\xf9\x50\x33\x52\xa5\xcc\xcf\x14\x9e\xdc\x4f" \
383
"\xb7\x7d\xcf\x25\xdb\xc0\x46\xdb\xea\xe\x27\xc8\x18\x40\x39" \
384
"\xbd\xec\x48\xa3\xfa\x87\xa3\x18\x68\xfc\x7a\x44\xa8\xc5\x8c" \
385
"\x45\x81\x70\x72\x14\x70\xf9\x40\xc8\xe7\x41\xcb\xde\xd\x4e" \
386
"\x35\x4d\xcd\xe2\x40\xa3\x2e\xbb\xb7\x50\x6c\x26\xb8\xbe\x2a" \
387
"\x36\x8e\x23\xb\xa\xfe\xed\xa\xe7\xa0\x16\x73\xad\x24\x51" \
388
"\x7f\xda\x9d\xd7\x9f\x18\xe6\xa8\xe4\x98\xbc\x62\x77\x55\x60" \
389
"\x88\x16\x25\xbf\x95\xad\xea\xe1\x87\x18\x35\x9e\x7c\x51\xee" \
390
"\xc0\x80\x8b\xb8\x37\xfd\x95\xfe\x87\x15\xf4\x97\xd5\x61\x4f" \
391
"\x97\xfa\xaf\x48\xd\x5b\x84\x2d\xdb\x15\xf2\xb4\x17\x4f\x41" \
392
"\x31\x58\x32\x93\xc1\x52\x34\xa6\x17\xd\x56\x5\xee\xfb\xfb" \
393
"\x2d\x69\x14\xbe\x24\x94\x8\xb0\xfc\x9f\x2\x95\x88\x7d\xd6" \
394
"\xe7\xa4\x5b\xbb\xf2\x7d\xd8\xa5\xd2\x7c\x9\x62\x22\x5\x53" \
395
"\xd0\x67\xeb\x68\xfc\x82\x80\xf\xc9\x73\x76\x36\xb8\x13\x9f" \
396
"\xb1\xf1\xee\x61\x12\xe7\x5d\x75\x65\xb8\x84\x17\xb\x7b\x28" \
397
"\x4c\xb7\xda\xbb" ) \
398
+ ( (unsigned char)key[i] * sizeof(int) )); \
402
/* key comparison function; return 0 if keys equal */
403
#define HASH_KEYCMP(a,b,len) memcmp(a,b,len)
405
/* iterate over items in a known bucket to find desired item */
406
#define HASH_FIND_IN_BKT(hh,head,keyptr,keylen_in,out) \
407
out = (head.hh_head) ? (head.hh_head->elmt) : NULL; \
409
if (out->hh.keylen == keylen_in) { \
410
if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \
412
out= (out->hh.hh_next) ? (out->hh.hh_next->elmt) : NULL; \
415
/* add an item to a bucket */
416
#define HASH_ADD_TO_BKT(hh,head,add) \
418
add->hh.hh_next = head.hh_head; \
419
add->hh.hh_prev = NULL; \
420
if (head.hh_head) head.hh_head->hh_prev = &add->hh; \
421
head.hh_head=&add->hh; \
422
if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \
423
&& add->hh.tbl->noexpand != 1) { \
424
HASH_EXPAND_BUCKETS(add->hh.tbl) \
427
/* remove an item from a given bucket */
428
#define HASH_DEL_IN_BKT(hh,head,delptr) \
430
if ((head).hh_head->elmt == delptr) { \
431
(head).hh_head = delptr->hh.hh_next; \
433
if (delptr->hh.hh_prev) { \
434
delptr->hh.hh_prev->hh_next = delptr->hh.hh_next; \
436
if (delptr->hh.hh_next) { \
437
delptr->hh.hh_next->hh_prev = delptr->hh.hh_prev; \
440
#define HASH_EXPAND_BUCKETS(tbl) \
441
tbl->new_buckets = (UT_hash_bucket*)uthash_bkt_malloc( \
442
2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
443
if (!tbl->new_buckets) { uthash_fatal( "out of memory"); } \
444
memset(tbl->new_buckets, 0, \
445
2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \
446
tbl->bkt_ideal= (tbl->num_items / tbl->num_buckets*2) + \
447
((tbl->num_items % (tbl->num_buckets*2)) ? 1 : 0);\
448
tbl->sum_of_deltas = 0; \
449
for(tbl->bkt_i = 0; tbl->bkt_i < tbl->num_buckets; tbl->bkt_i++) \
451
tbl->hh = tbl->buckets[ tbl->bkt_i ].hh_head; \
453
tbl->hh_nxt = tbl->hh->hh_next; \
454
tbl->key = tbl->hh->key; \
455
tbl->keylen = tbl->hh->keylen; \
456
HASH_FCN(tbl->key,tbl->keylen,tbl->num_buckets*2,tbl->bkt,\
457
tbl->i,tbl->j,tbl->k); \
458
tbl->newbkt = &(tbl->new_buckets[ tbl->bkt ]); \
459
if (++(tbl->newbkt->count) > tbl->bkt_ideal) { \
460
tbl->sum_of_deltas++; \
461
tbl->newbkt->expand_mult = tbl->newbkt->count / \
464
tbl->hh->hh_prev = NULL; \
465
tbl->hh->hh_next = tbl->newbkt->hh_head; \
466
if (tbl->newbkt->hh_head) tbl->newbkt->hh_head->hh_prev = \
468
tbl->newbkt->hh_head = tbl->hh; \
469
tbl->hh = tbl->hh_nxt; \
472
tbl->num_buckets *= 2; \
473
uthash_bkt_free( tbl->buckets ); \
474
tbl->buckets = tbl->new_buckets; \
475
tbl->new_hash_q = (1<<16) - ((tbl->sum_of_deltas << 16) / tbl->num_items); \
476
if (tbl->hash_q < (1<<15) && tbl->new_hash_q < (1<<15)) { \
478
uthash_noexpand_fyi(tbl); \
480
tbl->hash_q = tbl->new_hash_q; \
481
uthash_expand_fyi(tbl);
484
/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
485
#define HASH_SORT(head,cmpfcn) \
487
(head)->hh.tbl->insize = 1; \
488
(head)->hh.tbl->looping = 1; \
489
(head)->hh.tbl->list = &((head)->hh); \
490
while ((head)->hh.tbl->looping) { \
491
(head)->hh.tbl->p = (head)->hh.tbl->list; \
492
(head)->hh.tbl->list = NULL; \
493
(head)->hh.tbl->tale = NULL; \
494
(head)->hh.tbl->nmerges = 0; \
495
while ((head)->hh.tbl->p) { \
496
(head)->hh.tbl->nmerges++; \
497
(head)->hh.tbl->q = (head)->hh.tbl->p; \
498
(head)->hh.tbl->psize = 0; \
499
for ( (head)->hh.tbl->i = 0; \
500
(head)->hh.tbl->i < (head)->hh.tbl->insize; \
501
(head)->hh.tbl->i++ ) { \
502
(head)->hh.tbl->psize++; \
503
(head)->hh.tbl->q = (((head)->hh.tbl->q->next) ? \
504
((void*)(((long)((head)->hh.tbl->q->next)) + \
505
(head)->hh.tbl->hho)) : NULL); \
506
if (! ((head)->hh.tbl->q) ) break; \
508
(head)->hh.tbl->qsize = (head)->hh.tbl->insize; \
509
while (((head)->hh.tbl->psize > 0) || \
510
(((head)->hh.tbl->qsize > 0) && (head)->hh.tbl->q )) { \
511
if ((head)->hh.tbl->psize == 0) { \
512
(head)->hh.tbl->e = (head)->hh.tbl->q; \
513
(head)->hh.tbl->q = (((head)->hh.tbl->q->next) ? \
514
((void*)(((long)((head)->hh.tbl->q->next)) + \
515
(head)->hh.tbl->hho)) : NULL); \
516
(head)->hh.tbl->qsize--; \
517
} else if ( ((head)->hh.tbl->qsize == 0) || \
518
!((head)->hh.tbl->q) ) { \
519
(head)->hh.tbl->e = (head)->hh.tbl->p; \
520
(head)->hh.tbl->p = (((head)->hh.tbl->p->next) ? \
521
((void*)(((long)((head)->hh.tbl->p->next)) + \
522
(head)->hh.tbl->hho)) : NULL); \
523
(head)->hh.tbl->psize--; \
525
cmpfcn((head)->hh.tbl->p->elmt,(head)->hh.tbl->q->elmt)) \
527
(head)->hh.tbl->e = (head)->hh.tbl->p; \
528
(head)->hh.tbl->p = (((head)->hh.tbl->p->next) ? \
529
((void*)(((long)((head)->hh.tbl->p->next)) + \
530
(head)->hh.tbl->hho)) : NULL); \
531
(head)->hh.tbl->psize--; \
533
(head)->hh.tbl->e = (head)->hh.tbl->q; \
534
(head)->hh.tbl->q = (((head)->hh.tbl->q->next) ? \
535
((void*)(((long)((head)->hh.tbl->q->next)) + \
536
(head)->hh.tbl->hho)) : NULL); \
537
(head)->hh.tbl->qsize--; \
539
if ( (head)->hh.tbl->tale ) { \
540
(head)->hh.tbl->tale->next = (((head)->hh.tbl->e) ? \
541
((head)->hh.tbl->e->elmt) : NULL); \
543
(head)->hh.tbl->list = (head)->hh.tbl->e; \
545
(head)->hh.tbl->e->prev = (((head)->hh.tbl->tale) ? \
546
((head)->hh.tbl->tale->elmt) : NULL); \
547
(head)->hh.tbl->tale = (head)->hh.tbl->e; \
549
(head)->hh.tbl->p = (head)->hh.tbl->q; \
551
(head)->hh.tbl->tale->next = NULL; \
552
if ( (head)->hh.tbl->nmerges <= 1 ) { \
553
(head)->hh.tbl->looping=0; \
554
(head)->hh.tbl->tail = (head)->hh.tbl->tale; \
555
(head) = (head)->hh.tbl->list->elmt; \
557
(head)->hh.tbl->insize *= 2; \
562
typedef struct UT_hash_bucket {
563
struct UT_hash_handle *hh_head;
565
unsigned expand_mult;
568
typedef struct UT_hash_table {
569
UT_hash_bucket *buckets;
570
unsigned num_buckets;
572
int noexpand; /* when set, inhibits expansion of buckets for this hash */
573
int hash_q; /* measures the evenness of the items among buckets (0-1) */
574
struct UT_hash_handle *tail; /* tail hh in app order, for fast append */
575
char *name; /* macro-stringified name of list head, used by libut */
582
/* scratch for bucket expansion */
583
UT_hash_bucket *new_buckets, *newbkt;
584
struct UT_hash_handle *hh, *hh_nxt;
585
unsigned bkt_i, bkt_ideal, sum_of_deltas;
587
/* scratch for sort */
588
int looping,nmerges,insize,psize,qsize;
589
struct UT_hash_handle *p, *q, *e, *list, *tale;
594
typedef struct UT_hash_handle {
595
struct UT_hash_table *tbl;
596
void *elmt; /* ptr to enclosing element */
597
void *prev; /* prev element in app order */
598
void *next; /* next element in app order */
599
struct UT_hash_handle *hh_prev; /* previous hh in bucket order */
600
struct UT_hash_handle *hh_next; /* next hh in bucket order */
601
void *key; /* ptr to enclosing struct's key */
602
size_t keylen; /* enclosing struct's key len */
605
#endif /* UTHASH_H */
added
removed
libhal/uthash.h
