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