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