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