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