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 out=NULL; \ 106 if (head) { \ 107 unsigned _hf_bkt,_hf_hashv; \ 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 struct UT_hash_handle *_hd_hh_del; \ 227 if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ 228 uthash_free((head)->hh.tbl->buckets, \ 229 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 230 HASH_BLOOM_FREE((head)->hh.tbl); \ 231 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 232 head = NULL; \ 233 } else { \ 234 unsigned _hd_bkt; \ 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,(unsigned)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],(unsigned)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 struct UT_hash_handle *_thh; \ 290 if (head) { \ 291 unsigned _bkt_i; \ 292 unsigned _count; \ 293 char *_prev; \ 294 _count = 0; \ 295 for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ 296 unsigned _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 %u, actual %u\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 %u, actual %u\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 %u, actual %u\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 } \ 395 bkt = hashv & (num_bkts-1); \ 396 } while(0) 397 398 #define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \ 399 do { \ 400 unsigned _ho_i; \ 401 char *_ho_key=(char*)(key); \ 402 hashv = 0; \ 403 for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ 404 hashv += _ho_key[_ho_i]; \ 405 hashv += (hashv << 10); \ 406 hashv ^= (hashv >> 6); \ 407 } \ 408 hashv += (hashv << 3); \ 409 hashv ^= (hashv >> 11); \ 410 hashv += (hashv << 15); \ 411 bkt = hashv & (num_bkts-1); \ 412 } while(0) 413 414 #define HASH_JEN_MIX(a,b,c) \ 415 do { \ 416 a -= b; a -= c; a ^= ( c >> 13 ); \ 417 b -= c; b -= a; b ^= ( a << 8 ); \ 418 c -= a; c -= b; c ^= ( b >> 13 ); \ 419 a -= b; a -= c; a ^= ( c >> 12 ); \ 420 b -= c; b -= a; b ^= ( a << 16 ); \ 421 c -= a; c -= b; c ^= ( b >> 5 ); \ 422 a -= b; a -= c; a ^= ( c >> 3 ); \ 423 b -= c; b -= a; b ^= ( a << 10 ); \ 424 c -= a; c -= b; c ^= ( b >> 15 ); \ 425 } while (0) 426 427 #define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \ 428 do { \ 429 unsigned _hj_i,_hj_j,_hj_k; \ 430 unsigned char *_hj_key=(unsigned char*)(key); \ 431 hashv = 0xfeedbeef; \ 432 _hj_i = _hj_j = 0x9e3779b9; \ 433 _hj_k = (unsigned)(keylen); \ 434 while (_hj_k >= 12) { \ 435 _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ 436 + ( (unsigned)_hj_key[2] << 16 ) \ 437 + ( (unsigned)_hj_key[3] << 24 ) ); \ 438 _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ 439 + ( (unsigned)_hj_key[6] << 16 ) \ 440 + ( (unsigned)_hj_key[7] << 24 ) ); \ 441 hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ 442 + ( (unsigned)_hj_key[10] << 16 ) \ 443 + ( (unsigned)_hj_key[11] << 24 ) ); \ 444 \ 445 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 446 \ 447 _hj_key += 12; \ 448 _hj_k -= 12; \ 449 } \ 450 hashv += keylen; \ 451 switch ( _hj_k ) { \ 452 case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \ 453 case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \ 454 case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \ 455 case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \ 456 case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \ 457 case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \ 458 case 5: _hj_j += _hj_key[4]; \ 459 case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \ 460 case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \ 461 case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \ 462 case 1: _hj_i += _hj_key[0]; \ 463 } \ 464 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 465 bkt = hashv & (num_bkts-1); \ 466 } while(0) 467 468 /* The Paul Hsieh hash function */ 469 #undef get16bits 470 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 471 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 472 #define get16bits(d) (*((const uint16_t *) (d))) 473 #endif 474 475 #if !defined (get16bits) 476 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ 477 +(uint32_t)(((const uint8_t *)(d))[0]) ) 478 #endif 479 #define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \ 480 do { \ 481 unsigned char *_sfh_key=(unsigned char*)(key); \ 482 uint32_t _sfh_tmp, _sfh_len = keylen; \ 483 \ 484 int _sfh_rem = _sfh_len & 3; \ 485 _sfh_len >>= 2; \ 486 hashv = 0xcafebabe; \ 487 \ 488 /* Main loop */ \ 489 for (;_sfh_len > 0; _sfh_len--) { \ 490 hashv += get16bits (_sfh_key); \ 491 _sfh_tmp = (uint32_t)(get16bits (_sfh_key+2)) << 11 ^ hashv; \ 492 hashv = (hashv << 16) ^ _sfh_tmp; \ 493 _sfh_key += 2*sizeof (uint16_t); \ 494 hashv += hashv >> 11; \ 495 } \ 496 \ 497 /* Handle end cases */ \ 498 switch (_sfh_rem) { \ 499 case 3: hashv += get16bits (_sfh_key); \ 500 hashv ^= hashv << 16; \ 501 hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)] << 18); \ 502 hashv += hashv >> 11; \ 503 break; \ 504 case 2: hashv += get16bits (_sfh_key); \ 505 hashv ^= hashv << 11; \ 506 hashv += hashv >> 17; \ 507 break; \ 508 case 1: hashv += *_sfh_key; \ 509 hashv ^= hashv << 10; \ 510 hashv += hashv >> 1; \ 511 } \ 512 \ 513 /* Force "avalanching" of final 127 bits */ \ 514 hashv ^= hashv << 3; \ 515 hashv += hashv >> 5; \ 516 hashv ^= hashv << 4; \ 517 hashv += hashv >> 17; \ 518 hashv ^= hashv << 25; \ 519 hashv += hashv >> 6; \ 520 bkt = hashv & (num_bkts-1); \ 521 } while(0) 522 523 #ifdef HASH_USING_NO_STRICT_ALIASING 524 /* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. 525 * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. 526 * MurmurHash uses the faster approach only on CPU's where we know it's safe. 527 * 528 * Note the preprocessor built-in defines can be emitted using: 529 * 530 * gcc -m64 -dM -E - < /dev/null (on gcc) 531 * cc -## a.c (where a.c is a simple test file) (Sun Studio) 532 */ 533 #if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) 534 #define MUR_GETBLOCK(p,i) p[i] 535 #else /* non intel */ 536 #define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 0x3) == 0) 537 #define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 0x3) == 1) 538 #define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 0x3) == 2) 539 #define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 0x3) == 3) 540 #define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) 541 #if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__)) 542 #define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) 543 #define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16)) 544 #define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8)) 545 #else /* assume little endian non-intel */ 546 #define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24)) 547 #define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16)) 548 #define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8)) 549 #endif 550 #define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \ 551 (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \ 552 (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \ 553 MUR_ONE_THREE(p)))) 554 #endif 555 #define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) 556 #define MUR_FMIX(_h) \ 557 do { \ 558 _h ^= _h >> 16; \ 559 _h *= 0x85ebca6b; \ 560 _h ^= _h >> 13; \ 561 _h *= 0xc2b2ae35l; \ 562 _h ^= _h >> 16; \ 563 } while(0) 564 565 #define HASH_MUR(key,keylen,num_bkts,hashv,bkt) \ 566 do { \ 567 const uint8_t *_mur_data = (const uint8_t*)(key); \ 568 const int _mur_nblocks = (keylen) / 4; \ 569 uint32_t _mur_h1 = 0xf88D5353; \ 570 uint32_t _mur_c1 = 0xcc9e2d51; \ 571 uint32_t _mur_c2 = 0x1b873593; \ 572 uint32_t _mur_k1 = 0; \ 573 const uint8_t *_mur_tail; \ 574 const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+_mur_nblocks*4); \ 575 int _mur_i; \ 576 for(_mur_i = -_mur_nblocks; _mur_i; _mur_i++) { \ 577 _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ 578 _mur_k1 *= _mur_c1; \ 579 _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 580 _mur_k1 *= _mur_c2; \ 581 \ 582 _mur_h1 ^= _mur_k1; \ 583 _mur_h1 = MUR_ROTL32(_mur_h1,13); \ 584 _mur_h1 = _mur_h1*5+0xe6546b64; \ 585 } \ 586 _mur_tail = (const uint8_t*)(_mur_data + _mur_nblocks*4); \ 587 _mur_k1=0; \ 588 switch((keylen) & 3) { \ 589 case 3: _mur_k1 ^= _mur_tail[2] << 16; \ 590 case 2: _mur_k1 ^= _mur_tail[1] << 8; \ 591 case 1: _mur_k1 ^= _mur_tail[0]; \ 592 _mur_k1 *= _mur_c1; \ 593 _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 594 _mur_k1 *= _mur_c2; \ 595 _mur_h1 ^= _mur_k1; \ 596 } \ 597 _mur_h1 ^= (keylen); \ 598 MUR_FMIX(_mur_h1); \ 599 hashv = _mur_h1; \ 600 bkt = hashv & (num_bkts-1); \ 601 } while(0) 602 #endif /* HASH_USING_NO_STRICT_ALIASING */ 603 604 /* key comparison function; return 0 if keys equal */ 605 #define HASH_KEYCMP(a,b,len) memcmp(a,b,len) 606 607 /* iterate over items in a known bucket to find desired item */ 608 #define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ 609 do { \ 610 if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ 611 else out=NULL; \ 612 while (out) { \ 613 if ((out)->hh.keylen == keylen_in) { \ 614 if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) break; \ 615 } \ 616 if ((out)->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); \ 617 else out = NULL; \ 618 } \ 619 } while(0) 620 621 /* add an item to a bucket */ 622 #define HASH_ADD_TO_BKT(head,addhh) \ 623 do { \ 624 head.count++; \ 625 (addhh)->hh_next = head.hh_head; \ 626 (addhh)->hh_prev = NULL; \ 627 if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ 628 (head).hh_head=addhh; \ 629 if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ 630 && (addhh)->tbl->noexpand != 1) { \ 631 HASH_EXPAND_BUCKETS((addhh)->tbl); \ 632 } \ 633 } while(0) 634 635 /* remove an item from a given bucket */ 636 #define HASH_DEL_IN_BKT(hh,head,hh_del) \ 637 (head).count--; \ 638 if ((head).hh_head == hh_del) { \ 639 (head).hh_head = hh_del->hh_next; \ 640 } \ 641 if (hh_del->hh_prev) { \ 642 hh_del->hh_prev->hh_next = hh_del->hh_next; \ 643 } \ 644 if (hh_del->hh_next) { \ 645 hh_del->hh_next->hh_prev = hh_del->hh_prev; \ 646 } 647 648 /* Bucket expansion has the effect of doubling the number of buckets 649 * and redistributing the items into the new buckets. Ideally the 650 * items will distribute more or less evenly into the new buckets 651 * (the extent to which this is true is a measure of the quality of 652 * the hash function as it applies to the key domain). 653 * 654 * With the items distributed into more buckets, the chain length 655 * (item count) in each bucket is reduced. Thus by expanding buckets 656 * the hash keeps a bound on the chain length. This bounded chain 657 * length is the essence of how a hash provides constant time lookup. 658 * 659 * The calculation of tbl->ideal_chain_maxlen below deserves some 660 * explanation. First, keep in mind that we're calculating the ideal 661 * maximum chain length based on the *new* (doubled) bucket count. 662 * In fractions this is just n/b (n=number of items,b=new num buckets). 663 * Since the ideal chain length is an integer, we want to calculate 664 * ceil(n/b). We don't depend on floating point arithmetic in this 665 * hash, so to calculate ceil(n/b) with integers we could write 666 * 667 * ceil(n/b) = (n/b) + ((n%b)?1:0) 668 * 669 * and in fact a previous version of this hash did just that. 670 * But now we have improved things a bit by recognizing that b is 671 * always a power of two. We keep its base 2 log handy (call it lb), 672 * so now we can write this with a bit shift and logical AND: 673 * 674 * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) 675 * 676 */ 677 #define HASH_EXPAND_BUCKETS(tbl) \ 678 do { \ 679 unsigned _he_bkt; \ 680 unsigned _he_bkt_i; \ 681 struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ 682 UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ 683 _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ 684 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 685 if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ 686 memset(_he_new_buckets, 0, \ 687 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 688 tbl->ideal_chain_maxlen = \ 689 (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ 690 ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ 691 tbl->nonideal_items = 0; \ 692 for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ 693 { \ 694 _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ 695 while (_he_thh) { \ 696 _he_hh_nxt = _he_thh->hh_next; \ 697 HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ 698 _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ 699 if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ 700 tbl->nonideal_items++; \ 701 _he_newbkt->expand_mult = _he_newbkt->count / \ 702 tbl->ideal_chain_maxlen; \ 703 } \ 704 _he_thh->hh_prev = NULL; \ 705 _he_thh->hh_next = _he_newbkt->hh_head; \ 706 if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ 707 _he_thh; \ 708 _he_newbkt->hh_head = _he_thh; \ 709 _he_thh = _he_hh_nxt; \ 710 } \ 711 } \ 712 uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 713 tbl->num_buckets *= 2; \ 714 tbl->log2_num_buckets++; \ 715 tbl->buckets = _he_new_buckets; \ 716 tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ 717 (tbl->ineff_expands+1) : 0; \ 718 if (tbl->ineff_expands > 1) { \ 719 tbl->noexpand=1; \ 720 uthash_noexpand_fyi(tbl); \ 721 } \ 722 uthash_expand_fyi(tbl); \ 723 } while(0) 724 725 726 /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ 727 /* Note that HASH_SORT assumes the hash handle name to be hh. 728 * HASH_SRT was added to allow the hash handle name to be passed in. */ 729 #define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) 730 #define HASH_SRT(hh,head,cmpfcn) \ 731 do { \ 732 unsigned _hs_i; \ 733 unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ 734 struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ 735 if (head) { \ 736 _hs_insize = 1; \ 737 _hs_looping = 1; \ 738 _hs_list = &((head)->hh); \ 739 while (_hs_looping) { \ 740 _hs_p = _hs_list; \ 741 _hs_list = NULL; \ 742 _hs_tail = NULL; \ 743 _hs_nmerges = 0; \ 744 while (_hs_p) { \ 745 _hs_nmerges++; \ 746 _hs_q = _hs_p; \ 747 _hs_psize = 0; \ 748 for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ 749 _hs_psize++; \ 750 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 751 ((void*)((char*)(_hs_q->next) + \ 752 (head)->hh.tbl->hho)) : NULL); \ 753 if (! (_hs_q) ) break; \ 754 } \ 755 _hs_qsize = _hs_insize; \ 756 while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ 757 if (_hs_psize == 0) { \ 758 _hs_e = _hs_q; \ 759 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 760 ((void*)((char*)(_hs_q->next) + \ 761 (head)->hh.tbl->hho)) : NULL); \ 762 _hs_qsize--; \ 763 } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ 764 _hs_e = _hs_p; \ 765 if (_hs_p){ \ 766 _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 767 ((void*)((char*)(_hs_p->next) + \ 768 (head)->hh.tbl->hho)) : NULL); \ 769 } \ 770 _hs_psize--; \ 771 } else if (( \ 772 cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ 773 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ 774 ) <= 0) { \ 775 _hs_e = _hs_p; \ 776 if (_hs_p){ \ 777 _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 778 ((void*)((char*)(_hs_p->next) + \ 779 (head)->hh.tbl->hho)) : NULL); \ 780 } \ 781 _hs_psize--; \ 782 } else { \ 783 _hs_e = _hs_q; \ 784 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 785 ((void*)((char*)(_hs_q->next) + \ 786 (head)->hh.tbl->hho)) : NULL); \ 787 _hs_qsize--; \ 788 } \ 789 if ( _hs_tail ) { \ 790 _hs_tail->next = ((_hs_e) ? \ 791 ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ 792 } else { \ 793 _hs_list = _hs_e; \ 794 } \ 795 if (_hs_e) { \ 796 _hs_e->prev = ((_hs_tail) ? \ 797 ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ 798 } \ 799 _hs_tail = _hs_e; \ 800 } \ 801 _hs_p = _hs_q; \ 802 } \ 803 if (_hs_tail){ \ 804 _hs_tail->next = NULL; \ 805 } \ 806 if ( _hs_nmerges <= 1 ) { \ 807 _hs_looping=0; \ 808 (head)->hh.tbl->tail = _hs_tail; \ 809 DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ 810 } \ 811 _hs_insize *= 2; \ 812 } \ 813 HASH_FSCK(hh,head); \ 814 } \ 815 } while (0) 816 817 /* This function selects items from one hash into another hash. 818 * The end result is that the selected items have dual presence 819 * in both hashes. There is no copy of the items made; rather 820 * they are added into the new hash through a secondary hash 821 * hash handle that must be present in the structure. */ 822 #define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ 823 do { \ 824 unsigned _src_bkt, _dst_bkt; \ 825 void *_last_elt=NULL, *_elt; \ 826 UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ 827 ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ 828 if (src) { \ 829 for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ 830 for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ 831 _src_hh; \ 832 _src_hh = _src_hh->hh_next) { \ 833 _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ 834 if (cond(_elt)) { \ 835 _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ 836 _dst_hh->key = _src_hh->key; \ 837 _dst_hh->keylen = _src_hh->keylen; \ 838 _dst_hh->hashv = _src_hh->hashv; \ 839 _dst_hh->prev = _last_elt; \ 840 _dst_hh->next = NULL; \ 841 if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ 842 if (!dst) { \ 843 DECLTYPE_ASSIGN(dst,_elt); \ 844 HASH_MAKE_TABLE(hh_dst,dst); \ 845 } else { \ 846 _dst_hh->tbl = (dst)->hh_dst.tbl; \ 847 } \ 848 HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ 849 HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ 850 (dst)->hh_dst.tbl->num_items++; \ 851 _last_elt = _elt; \ 852 _last_elt_hh = _dst_hh; \ 853 } \ 854 } \ 855 } \ 856 } \ 857 HASH_FSCK(hh_dst,dst); \ 858 } while (0) 859 860 #define HASH_CLEAR(hh,head) \ 861 do { \ 862 if (head) { \ 863 uthash_free((head)->hh.tbl->buckets, \ 864 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ 865 HASH_BLOOM_FREE((head)->hh.tbl); \ 866 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 867 (head)=NULL; \ 868 } \ 869 } while(0) 870 871 #define HASH_OVERHEAD(hh,head) \ 872 ((head) ? ( \ 873 (size_t)((((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ 874 ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ 875 (sizeof(UT_hash_table)) + \ 876 (HASH_BLOOM_BYTELEN)))) : 0) 877 878 #ifdef NO_DECLTYPE 879 #define HASH_ITER(hh,head,el,tmp) \ 880 for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ 881 el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) 882 #else 883 #define HASH_ITER(hh,head,el,tmp) \ 884 for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ 885 el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) 886 #endif 887 888 /* obtain a count of items in the hash */ 889 #define HASH_COUNT(head) HASH_CNT(hh,head) 890 #define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) 891 892 typedef struct UT_hash_bucket { 893 struct UT_hash_handle *hh_head; 894 unsigned count; 895 896 /* expand_mult is normally set to 0. In this situation, the max chain length 897 * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If 898 * the bucket's chain exceeds this length, bucket expansion is triggered). 899 * However, setting expand_mult to a non-zero value delays bucket expansion 900 * (that would be triggered by additions to this particular bucket) 901 * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. 902 * (The multiplier is simply expand_mult+1). The whole idea of this 903 * multiplier is to reduce bucket expansions, since they are expensive, in 904 * situations where we know that a particular bucket tends to be overused. 905 * It is better to let its chain length grow to a longer yet-still-bounded 906 * value, than to do an O(n) bucket expansion too often. 907 */ 908 unsigned expand_mult; 909 910 } UT_hash_bucket; 911 912 /* random signature used only to find hash tables in external analysis */ 913 #define HASH_SIGNATURE 0xa0111fe1 914 #define HASH_BLOOM_SIGNATURE 0xb12220f2 915 916 typedef struct UT_hash_table { 917 UT_hash_bucket *buckets; 918 unsigned num_buckets, log2_num_buckets; 919 unsigned num_items; 920 struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ 921 ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ 922 923 /* in an ideal situation (all buckets used equally), no bucket would have 924 * more than ceil(#items/#buckets) items. that's the ideal chain length. */ 925 unsigned ideal_chain_maxlen; 926 927 /* nonideal_items is the number of items in the hash whose chain position 928 * exceeds the ideal chain maxlen. these items pay the penalty for an uneven 929 * hash distribution; reaching them in a chain traversal takes >ideal steps */ 930 unsigned nonideal_items; 931 932 /* ineffective expands occur when a bucket doubling was performed, but 933 * afterward, more than half the items in the hash had nonideal chain 934 * positions. If this happens on two consecutive expansions we inhibit any 935 * further expansion, as it's not helping; this happens when the hash 936 * function isn't a good fit for the key domain. When expansion is inhibited 937 * the hash will still work, albeit no longer in constant time. */ 938 unsigned ineff_expands, noexpand; 939 940 uint32_t signature; /* used only to find hash tables in external analysis */ 941 #ifdef HASH_BLOOM 942 uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ 943 uint8_t *bloom_bv; 944 char bloom_nbits; 945 #endif 946 947 } UT_hash_table; 948 949 typedef struct UT_hash_handle { 950 struct UT_hash_table *tbl; 951 void *prev; /* prev element in app order */ 952 void *next; /* next element in app order */ 953 struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ 954 struct UT_hash_handle *hh_next; /* next hh in bucket order */ 955 void *key; /* ptr to enclosing struct's key */ 956 unsigned keylen; /* enclosing struct's key len */ 957 unsigned hashv; /* result of hash-fcn(key) */ 958 } UT_hash_handle; 959 960 #endif /* UTHASH_H */ 961