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