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