1260684Skaiw/* 2260684SkaiwCopyright (c) 2003-2013, Troy D. Hanson http://uthash.sourceforge.net 3260684SkaiwAll rights reserved. 4260684Skaiw 5260684SkaiwRedistribution and use in source and binary forms, with or without 6260684Skaiwmodification, are permitted provided that the following conditions are met: 7260684Skaiw 8260684Skaiw * Redistributions of source code must retain the above copyright 9260684Skaiw notice, this list of conditions and the following disclaimer. 10260684Skaiw 11260684SkaiwTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 12260684SkaiwIS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 13260684SkaiwTO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 14260684SkaiwPARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 15260684SkaiwOR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 16260684SkaiwEXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 17260684SkaiwPROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 18260684SkaiwPROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 19260684SkaiwLIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 20260684SkaiwNEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 21260684SkaiwSOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 22260684Skaiw*/ 23260684Skaiw 24260684Skaiw/* $Id: uthash.h 2682 2012-11-23 22:04:22Z kaiwang27 $ */ 25260684Skaiw 26260684Skaiw#ifndef UTHASH_H 27260684Skaiw#define UTHASH_H 28260684Skaiw 29260684Skaiw#include <string.h> /* memcmp,strlen */ 30260684Skaiw#include <stddef.h> /* ptrdiff_t */ 31260684Skaiw#include <stdlib.h> /* exit() */ 32260684Skaiw 33260684Skaiw/* These macros use decltype or the earlier __typeof GNU extension. 34260684Skaiw As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 35260684Skaiw when compiling c++ source) this code uses whatever method is needed 36260684Skaiw or, for VS2008 where neither is available, uses casting workarounds. */ 37260684Skaiw#ifdef _MSC_VER /* MS compiler */ 38260684Skaiw#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 39260684Skaiw#define DECLTYPE(x) (decltype(x)) 40260684Skaiw#else /* VS2008 or older (or VS2010 in C mode) */ 41260684Skaiw#define NO_DECLTYPE 42260684Skaiw#define DECLTYPE(x) 43260684Skaiw#endif 44260684Skaiw#else /* GNU, Sun and other compilers */ 45260684Skaiw#define DECLTYPE(x) (__typeof(x)) 46260684Skaiw#endif 47260684Skaiw 48260684Skaiw#ifdef NO_DECLTYPE 49260684Skaiw#define DECLTYPE_ASSIGN(dst,src) \ 50260684Skaiwdo { \ 51260684Skaiw char **_da_dst = (char**)(&(dst)); \ 52260684Skaiw *_da_dst = (char*)(src); \ 53260684Skaiw} while(0) 54260684Skaiw#else 55260684Skaiw#define DECLTYPE_ASSIGN(dst,src) \ 56260684Skaiwdo { \ 57260684Skaiw (dst) = DECLTYPE(dst)(src); \ 58260684Skaiw} while(0) 59260684Skaiw#endif 60260684Skaiw 61260684Skaiw/* a number of the hash function use uint32_t which isn't defined on win32 */ 62260684Skaiw#ifdef _MSC_VER 63260684Skaiwtypedef unsigned int uint32_t; 64260684Skaiwtypedef unsigned char uint8_t; 65260684Skaiw#else 66260684Skaiw#include <inttypes.h> /* uint32_t */ 67260684Skaiw#endif 68260684Skaiw 69260684Skaiw#define UTHASH_VERSION 1.9.7 70260684Skaiw 71260684Skaiw#ifndef uthash_fatal 72260684Skaiw#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ 73260684Skaiw#endif 74260684Skaiw#ifndef uthash_malloc 75260684Skaiw#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ 76260684Skaiw#endif 77260684Skaiw#ifndef uthash_free 78260684Skaiw#define uthash_free(ptr,sz) free(ptr) /* free fcn */ 79260684Skaiw#endif 80260684Skaiw 81260684Skaiw#ifndef uthash_noexpand_fyi 82260684Skaiw#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ 83260684Skaiw#endif 84260684Skaiw#ifndef uthash_expand_fyi 85260684Skaiw#define uthash_expand_fyi(tbl) /* can be defined to log expands */ 86260684Skaiw#endif 87260684Skaiw 88260684Skaiw/* initial number of buckets */ 89260684Skaiw#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ 90260684Skaiw#define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */ 91260684Skaiw#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ 92260684Skaiw 93260684Skaiw/* calculate the element whose hash handle address is hhe */ 94260684Skaiw#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) 95260684Skaiw 96260684Skaiw#define HASH_FIND(hh,head,keyptr,keylen,out) \ 97260684Skaiwdo { \ 98260684Skaiw unsigned _hf_bkt,_hf_hashv; \ 99260684Skaiw out=NULL; \ 100260684Skaiw if (head) { \ 101260684Skaiw HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \ 102260684Skaiw if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \ 103260684Skaiw HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \ 104260684Skaiw keyptr,keylen,out); \ 105260684Skaiw } \ 106260684Skaiw } \ 107260684Skaiw} while (0) 108260684Skaiw 109260684Skaiw#ifdef HASH_BLOOM 110260684Skaiw#define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM) 111260684Skaiw#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0) 112260684Skaiw#define HASH_BLOOM_MAKE(tbl) \ 113260684Skaiwdo { \ 114260684Skaiw (tbl)->bloom_nbits = HASH_BLOOM; \ 115260684Skaiw (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ 116260684Skaiw if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ 117260684Skaiw memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ 118260684Skaiw (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ 119260684Skaiw} while (0) 120260684Skaiw 121260684Skaiw#define HASH_BLOOM_FREE(tbl) \ 122260684Skaiwdo { \ 123260684Skaiw uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ 124260684Skaiw} while (0) 125260684Skaiw 126260684Skaiw#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8))) 127260684Skaiw#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8))) 128260684Skaiw 129260684Skaiw#define HASH_BLOOM_ADD(tbl,hashv) \ 130260684Skaiw HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) 131260684Skaiw 132260684Skaiw#define HASH_BLOOM_TEST(tbl,hashv) \ 133260684Skaiw HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) 134260684Skaiw 135260684Skaiw#else 136260684Skaiw#define HASH_BLOOM_MAKE(tbl) 137260684Skaiw#define HASH_BLOOM_FREE(tbl) 138260684Skaiw#define HASH_BLOOM_ADD(tbl,hashv) 139260684Skaiw#define HASH_BLOOM_TEST(tbl,hashv) (1) 140260684Skaiw#endif 141260684Skaiw 142260684Skaiw#define HASH_MAKE_TABLE(hh,head) \ 143260684Skaiwdo { \ 144260684Skaiw (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ 145260684Skaiw sizeof(UT_hash_table)); \ 146260684Skaiw if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ 147260684Skaiw memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ 148260684Skaiw (head)->hh.tbl->tail = &((head)->hh); \ 149260684Skaiw (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ 150260684Skaiw (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ 151260684Skaiw (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ 152260684Skaiw (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ 153260684Skaiw HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 154260684Skaiw if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ 155260684Skaiw memset((head)->hh.tbl->buckets, 0, \ 156260684Skaiw HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 157260684Skaiw HASH_BLOOM_MAKE((head)->hh.tbl); \ 158260684Skaiw (head)->hh.tbl->signature = HASH_SIGNATURE; \ 159260684Skaiw} while(0) 160260684Skaiw 161260684Skaiw#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ 162260684Skaiw HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add) 163260684Skaiw 164260684Skaiw#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ 165260684Skaiwdo { \ 166260684Skaiw unsigned _ha_bkt; \ 167260684Skaiw (add)->hh.next = NULL; \ 168260684Skaiw (add)->hh.key = (char*)keyptr; \ 169260684Skaiw (add)->hh.keylen = (unsigned)keylen_in; \ 170260684Skaiw if (!(head)) { \ 171260684Skaiw head = (add); \ 172260684Skaiw (head)->hh.prev = NULL; \ 173260684Skaiw HASH_MAKE_TABLE(hh,head); \ 174260684Skaiw } else { \ 175260684Skaiw (head)->hh.tbl->tail->next = (add); \ 176260684Skaiw (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ 177260684Skaiw (head)->hh.tbl->tail = &((add)->hh); \ 178260684Skaiw } \ 179260684Skaiw (head)->hh.tbl->num_items++; \ 180260684Skaiw (add)->hh.tbl = (head)->hh.tbl; \ 181260684Skaiw HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \ 182260684Skaiw (add)->hh.hashv, _ha_bkt); \ 183260684Skaiw HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \ 184260684Skaiw HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \ 185260684Skaiw HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ 186260684Skaiw HASH_FSCK(hh,head); \ 187260684Skaiw} while(0) 188260684Skaiw 189260684Skaiw#define HASH_TO_BKT( hashv, num_bkts, bkt ) \ 190260684Skaiwdo { \ 191260684Skaiw bkt = ((hashv) & ((num_bkts) - 1)); \ 192260684Skaiw} while(0) 193260684Skaiw 194260684Skaiw/* delete "delptr" from the hash table. 195260684Skaiw * "the usual" patch-up process for the app-order doubly-linked-list. 196260684Skaiw * The use of _hd_hh_del below deserves special explanation. 197260684Skaiw * These used to be expressed using (delptr) but that led to a bug 198260684Skaiw * if someone used the same symbol for the head and deletee, like 199260684Skaiw * HASH_DELETE(hh,users,users); 200260684Skaiw * We want that to work, but by changing the head (users) below 201260684Skaiw * we were forfeiting our ability to further refer to the deletee (users) 202260684Skaiw * in the patch-up process. Solution: use scratch space to 203260684Skaiw * copy the deletee pointer, then the latter references are via that 204260684Skaiw * scratch pointer rather than through the repointed (users) symbol. 205260684Skaiw */ 206260684Skaiw#define HASH_DELETE(hh,head,delptr) \ 207260684Skaiwdo { \ 208260684Skaiw unsigned _hd_bkt; \ 209260684Skaiw struct UT_hash_handle *_hd_hh_del; \ 210260684Skaiw if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ 211260684Skaiw uthash_free((head)->hh.tbl->buckets, \ 212260684Skaiw (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 213260684Skaiw HASH_BLOOM_FREE((head)->hh.tbl); \ 214260684Skaiw uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 215260684Skaiw head = NULL; \ 216260684Skaiw } else { \ 217260684Skaiw _hd_hh_del = &((delptr)->hh); \ 218260684Skaiw if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ 219260684Skaiw (head)->hh.tbl->tail = \ 220260684Skaiw (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ 221260684Skaiw (head)->hh.tbl->hho); \ 222260684Skaiw } \ 223260684Skaiw if ((delptr)->hh.prev) { \ 224260684Skaiw ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ 225260684Skaiw (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ 226260684Skaiw } else { \ 227260684Skaiw DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ 228260684Skaiw } \ 229260684Skaiw if (_hd_hh_del->next) { \ 230260684Skaiw ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \ 231260684Skaiw (head)->hh.tbl->hho))->prev = \ 232260684Skaiw _hd_hh_del->prev; \ 233260684Skaiw } \ 234260684Skaiw HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ 235260684Skaiw HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ 236260684Skaiw (head)->hh.tbl->num_items--; \ 237260684Skaiw } \ 238260684Skaiw HASH_FSCK(hh,head); \ 239260684Skaiw} while (0) 240260684Skaiw 241260684Skaiw 242260684Skaiw/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ 243260684Skaiw#define HASH_FIND_STR(head,findstr,out) \ 244260684Skaiw HASH_FIND(hh,head,findstr,strlen(findstr),out) 245260684Skaiw#define HASH_ADD_STR(head,strfield,add) \ 246260684Skaiw HASH_ADD(hh,head,strfield,strlen(add->strfield),add) 247260684Skaiw#define HASH_FIND_INT(head,findint,out) \ 248260684Skaiw HASH_FIND(hh,head,findint,sizeof(int),out) 249260684Skaiw#define HASH_ADD_INT(head,intfield,add) \ 250260684Skaiw HASH_ADD(hh,head,intfield,sizeof(int),add) 251260684Skaiw#define HASH_FIND_PTR(head,findptr,out) \ 252260684Skaiw HASH_FIND(hh,head,findptr,sizeof(void *),out) 253260684Skaiw#define HASH_ADD_PTR(head,ptrfield,add) \ 254260684Skaiw HASH_ADD(hh,head,ptrfield,sizeof(void *),add) 255260684Skaiw#define HASH_DEL(head,delptr) \ 256260684Skaiw HASH_DELETE(hh,head,delptr) 257260684Skaiw 258260684Skaiw/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. 259260684Skaiw * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. 260260684Skaiw */ 261260684Skaiw#ifdef HASH_DEBUG 262260684Skaiw#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) 263260684Skaiw#define HASH_FSCK(hh,head) \ 264260684Skaiwdo { \ 265260684Skaiw unsigned _bkt_i; \ 266260684Skaiw unsigned _count, _bkt_count; \ 267260684Skaiw char *_prev; \ 268260684Skaiw struct UT_hash_handle *_thh; \ 269260684Skaiw if (head) { \ 270260684Skaiw _count = 0; \ 271260684Skaiw for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ 272260684Skaiw _bkt_count = 0; \ 273260684Skaiw _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ 274260684Skaiw _prev = NULL; \ 275260684Skaiw while (_thh) { \ 276260684Skaiw if (_prev != (char*)(_thh->hh_prev)) { \ 277260684Skaiw HASH_OOPS("invalid hh_prev %p, actual %p\n", \ 278260684Skaiw _thh->hh_prev, _prev ); \ 279260684Skaiw } \ 280260684Skaiw _bkt_count++; \ 281260684Skaiw _prev = (char*)(_thh); \ 282260684Skaiw _thh = _thh->hh_next; \ 283260684Skaiw } \ 284260684Skaiw _count += _bkt_count; \ 285260684Skaiw if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ 286260684Skaiw HASH_OOPS("invalid bucket count %d, actual %d\n", \ 287260684Skaiw (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ 288260684Skaiw } \ 289260684Skaiw } \ 290260684Skaiw if (_count != (head)->hh.tbl->num_items) { \ 291260684Skaiw HASH_OOPS("invalid hh item count %d, actual %d\n", \ 292260684Skaiw (head)->hh.tbl->num_items, _count ); \ 293260684Skaiw } \ 294260684Skaiw /* traverse hh in app order; check next/prev integrity, count */ \ 295260684Skaiw _count = 0; \ 296260684Skaiw _prev = NULL; \ 297260684Skaiw _thh = &(head)->hh; \ 298260684Skaiw while (_thh) { \ 299260684Skaiw _count++; \ 300260684Skaiw if (_prev !=(char*)(_thh->prev)) { \ 301260684Skaiw HASH_OOPS("invalid prev %p, actual %p\n", \ 302260684Skaiw _thh->prev, _prev ); \ 303260684Skaiw } \ 304260684Skaiw _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ 305260684Skaiw _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ 306260684Skaiw (head)->hh.tbl->hho) : NULL ); \ 307260684Skaiw } \ 308260684Skaiw if (_count != (head)->hh.tbl->num_items) { \ 309260684Skaiw HASH_OOPS("invalid app item count %d, actual %d\n", \ 310260684Skaiw (head)->hh.tbl->num_items, _count ); \ 311260684Skaiw } \ 312260684Skaiw } \ 313260684Skaiw} while (0) 314260684Skaiw#else 315260684Skaiw#define HASH_FSCK(hh,head) 316260684Skaiw#endif 317260684Skaiw 318260684Skaiw/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to 319260684Skaiw * the descriptor to which this macro is defined for tuning the hash function. 320260684Skaiw * The app can #include <unistd.h> to get the prototype for write(2). */ 321260684Skaiw#ifdef HASH_EMIT_KEYS 322260684Skaiw#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ 323260684Skaiwdo { \ 324260684Skaiw unsigned _klen = fieldlen; \ 325260684Skaiw write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ 326260684Skaiw write(HASH_EMIT_KEYS, keyptr, fieldlen); \ 327260684Skaiw} while (0) 328260684Skaiw#else 329260684Skaiw#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) 330260684Skaiw#endif 331260684Skaiw 332260684Skaiw/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ 333260684Skaiw#ifdef HASH_FUNCTION 334260684Skaiw#define HASH_FCN HASH_FUNCTION 335260684Skaiw#else 336260684Skaiw#define HASH_FCN HASH_JEN 337260684Skaiw#endif 338260684Skaiw 339260684Skaiw/* The Bernstein hash function, used in Perl prior to v5.6 */ 340260684Skaiw#define HASH_BER(key,keylen,num_bkts,hashv,bkt) \ 341260684Skaiwdo { \ 342260684Skaiw unsigned _hb_keylen=keylen; \ 343260684Skaiw char *_hb_key=(char*)(key); \ 344260684Skaiw (hashv) = 0; \ 345260684Skaiw while (_hb_keylen--) { (hashv) = ((hashv) * 33) + *_hb_key++; } \ 346260684Skaiw bkt = (hashv) & (num_bkts-1); \ 347260684Skaiw} while (0) 348260684Skaiw 349260684Skaiw 350260684Skaiw/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at 351260684Skaiw * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ 352260684Skaiw#define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \ 353260684Skaiwdo { \ 354260684Skaiw unsigned _sx_i; \ 355260684Skaiw char *_hs_key=(char*)(key); \ 356260684Skaiw hashv = 0; \ 357260684Skaiw for(_sx_i=0; _sx_i < keylen; _sx_i++) \ 358260684Skaiw hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ 359260684Skaiw bkt = hashv & (num_bkts-1); \ 360260684Skaiw} while (0) 361260684Skaiw 362260684Skaiw#define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \ 363260684Skaiwdo { \ 364260684Skaiw unsigned _fn_i; \ 365260684Skaiw char *_hf_key=(char*)(key); \ 366260684Skaiw hashv = 2166136261UL; \ 367260684Skaiw for(_fn_i=0; _fn_i < keylen; _fn_i++) \ 368260684Skaiw hashv = (hashv * 16777619) ^ _hf_key[_fn_i]; \ 369260684Skaiw bkt = hashv & (num_bkts-1); \ 370260684Skaiw} while(0) 371260684Skaiw 372260684Skaiw#define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \ 373260684Skaiwdo { \ 374260684Skaiw unsigned _ho_i; \ 375260684Skaiw char *_ho_key=(char*)(key); \ 376260684Skaiw hashv = 0; \ 377260684Skaiw for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ 378260684Skaiw hashv += _ho_key[_ho_i]; \ 379260684Skaiw hashv += (hashv << 10); \ 380260684Skaiw hashv ^= (hashv >> 6); \ 381260684Skaiw } \ 382260684Skaiw hashv += (hashv << 3); \ 383260684Skaiw hashv ^= (hashv >> 11); \ 384260684Skaiw hashv += (hashv << 15); \ 385260684Skaiw bkt = hashv & (num_bkts-1); \ 386260684Skaiw} while(0) 387260684Skaiw 388260684Skaiw#define HASH_JEN_MIX(a,b,c) \ 389260684Skaiwdo { \ 390260684Skaiw a -= b; a -= c; a ^= ( c >> 13 ); \ 391260684Skaiw b -= c; b -= a; b ^= ( a << 8 ); \ 392260684Skaiw c -= a; c -= b; c ^= ( b >> 13 ); \ 393260684Skaiw a -= b; a -= c; a ^= ( c >> 12 ); \ 394260684Skaiw b -= c; b -= a; b ^= ( a << 16 ); \ 395260684Skaiw c -= a; c -= b; c ^= ( b >> 5 ); \ 396260684Skaiw a -= b; a -= c; a ^= ( c >> 3 ); \ 397260684Skaiw b -= c; b -= a; b ^= ( a << 10 ); \ 398260684Skaiw c -= a; c -= b; c ^= ( b >> 15 ); \ 399260684Skaiw} while (0) 400260684Skaiw 401260684Skaiw#define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \ 402260684Skaiwdo { \ 403260684Skaiw unsigned _hj_i,_hj_j,_hj_k; \ 404260684Skaiw char *_hj_key=(char*)(key); \ 405260684Skaiw hashv = 0xfeedbeef; \ 406260684Skaiw _hj_i = _hj_j = 0x9e3779b9; \ 407260684Skaiw _hj_k = (unsigned)keylen; \ 408260684Skaiw while (_hj_k >= 12) { \ 409260684Skaiw _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ 410260684Skaiw + ( (unsigned)_hj_key[2] << 16 ) \ 411260684Skaiw + ( (unsigned)_hj_key[3] << 24 ) ); \ 412260684Skaiw _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ 413260684Skaiw + ( (unsigned)_hj_key[6] << 16 ) \ 414260684Skaiw + ( (unsigned)_hj_key[7] << 24 ) ); \ 415260684Skaiw hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ 416260684Skaiw + ( (unsigned)_hj_key[10] << 16 ) \ 417260684Skaiw + ( (unsigned)_hj_key[11] << 24 ) ); \ 418260684Skaiw \ 419260684Skaiw HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 420260684Skaiw \ 421260684Skaiw _hj_key += 12; \ 422260684Skaiw _hj_k -= 12; \ 423260684Skaiw } \ 424260684Skaiw hashv += keylen; \ 425260684Skaiw switch ( _hj_k ) { \ 426260684Skaiw case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \ 427260684Skaiw case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \ 428260684Skaiw case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \ 429260684Skaiw case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \ 430260684Skaiw case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \ 431260684Skaiw case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \ 432260684Skaiw case 5: _hj_j += _hj_key[4]; \ 433260684Skaiw case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \ 434260684Skaiw case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \ 435260684Skaiw case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \ 436260684Skaiw case 1: _hj_i += _hj_key[0]; \ 437260684Skaiw } \ 438260684Skaiw HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 439260684Skaiw bkt = hashv & (num_bkts-1); \ 440260684Skaiw} while(0) 441260684Skaiw 442260684Skaiw/* The Paul Hsieh hash function */ 443260684Skaiw#undef get16bits 444260684Skaiw#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 445260684Skaiw || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 446260684Skaiw#define get16bits(d) (*((const uint16_t *) (d))) 447260684Skaiw#endif 448260684Skaiw 449260684Skaiw#if !defined (get16bits) 450260684Skaiw#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ 451260684Skaiw +(uint32_t)(((const uint8_t *)(d))[0]) ) 452260684Skaiw#endif 453260684Skaiw#define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \ 454260684Skaiwdo { \ 455260684Skaiw char *_sfh_key=(char*)(key); \ 456260684Skaiw uint32_t _sfh_tmp, _sfh_len = keylen; \ 457260684Skaiw \ 458260684Skaiw int _sfh_rem = _sfh_len & 3; \ 459260684Skaiw _sfh_len >>= 2; \ 460260684Skaiw hashv = 0xcafebabe; \ 461260684Skaiw \ 462260684Skaiw /* Main loop */ \ 463260684Skaiw for (;_sfh_len > 0; _sfh_len--) { \ 464260684Skaiw hashv += get16bits (_sfh_key); \ 465260684Skaiw _sfh_tmp = (get16bits (_sfh_key+2) << 11) ^ hashv; \ 466260684Skaiw hashv = (hashv << 16) ^ _sfh_tmp; \ 467260684Skaiw _sfh_key += 2*sizeof (uint16_t); \ 468260684Skaiw hashv += hashv >> 11; \ 469260684Skaiw } \ 470260684Skaiw \ 471260684Skaiw /* Handle end cases */ \ 472260684Skaiw switch (_sfh_rem) { \ 473260684Skaiw case 3: hashv += get16bits (_sfh_key); \ 474260684Skaiw hashv ^= hashv << 16; \ 475260684Skaiw hashv ^= _sfh_key[sizeof (uint16_t)] << 18; \ 476260684Skaiw hashv += hashv >> 11; \ 477260684Skaiw break; \ 478260684Skaiw case 2: hashv += get16bits (_sfh_key); \ 479260684Skaiw hashv ^= hashv << 11; \ 480260684Skaiw hashv += hashv >> 17; \ 481260684Skaiw break; \ 482260684Skaiw case 1: hashv += *_sfh_key; \ 483260684Skaiw hashv ^= hashv << 10; \ 484260684Skaiw hashv += hashv >> 1; \ 485260684Skaiw } \ 486260684Skaiw \ 487260684Skaiw /* Force "avalanching" of final 127 bits */ \ 488260684Skaiw hashv ^= hashv << 3; \ 489260684Skaiw hashv += hashv >> 5; \ 490260684Skaiw hashv ^= hashv << 4; \ 491260684Skaiw hashv += hashv >> 17; \ 492260684Skaiw hashv ^= hashv << 25; \ 493260684Skaiw hashv += hashv >> 6; \ 494260684Skaiw bkt = hashv & (num_bkts-1); \ 495260684Skaiw} while(0) 496260684Skaiw 497260684Skaiw#ifdef HASH_USING_NO_STRICT_ALIASING 498260684Skaiw/* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. 499260684Skaiw * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. 500260684Skaiw * MurmurHash uses the faster approach only on CPU's where we know it's safe. 501260684Skaiw * 502260684Skaiw * Note the preprocessor built-in defines can be emitted using: 503260684Skaiw * 504260684Skaiw * gcc -m64 -dM -E - < /dev/null (on gcc) 505260684Skaiw * cc -## a.c (where a.c is a simple test file) (Sun Studio) 506260684Skaiw */ 507260684Skaiw#if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) 508260684Skaiw#define MUR_GETBLOCK(p,i) p[i] 509260684Skaiw#else /* non intel */ 510260684Skaiw#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 0x3) == 0) 511260684Skaiw#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 0x3) == 1) 512260684Skaiw#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 0x3) == 2) 513260684Skaiw#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 0x3) == 3) 514260684Skaiw#define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) 515260684Skaiw#if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__)) 516260684Skaiw#define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) 517260684Skaiw#define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16)) 518260684Skaiw#define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8)) 519260684Skaiw#else /* assume little endian non-intel */ 520260684Skaiw#define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24)) 521260684Skaiw#define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16)) 522260684Skaiw#define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8)) 523260684Skaiw#endif 524260684Skaiw#define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \ 525260684Skaiw (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \ 526260684Skaiw (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \ 527260684Skaiw MUR_ONE_THREE(p)))) 528260684Skaiw#endif 529260684Skaiw#define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) 530260684Skaiw#define MUR_FMIX(_h) \ 531260684Skaiwdo { \ 532260684Skaiw _h ^= _h >> 16; \ 533260684Skaiw _h *= 0x85ebca6b; \ 534260684Skaiw _h ^= _h >> 13; \ 535260684Skaiw _h *= 0xc2b2ae35l; \ 536260684Skaiw _h ^= _h >> 16; \ 537260684Skaiw} while(0) 538260684Skaiw 539260684Skaiw#define HASH_MUR(key,keylen,num_bkts,hashv,bkt) \ 540260684Skaiwdo { \ 541260684Skaiw const uint8_t *_mur_data = (const uint8_t*)(key); \ 542260684Skaiw const int _mur_nblocks = (keylen) / 4; \ 543260684Skaiw uint32_t _mur_h1 = 0xf88D5353; \ 544260684Skaiw uint32_t _mur_c1 = 0xcc9e2d51; \ 545260684Skaiw uint32_t _mur_c2 = 0x1b873593; \ 546260684Skaiw uint32_t _mur_k1 = 0; \ 547260684Skaiw const uint8_t *_mur_tail; \ 548260684Skaiw const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+_mur_nblocks*4); \ 549260684Skaiw int _mur_i; \ 550260684Skaiw for(_mur_i = -_mur_nblocks; _mur_i; _mur_i++) { \ 551260684Skaiw _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ 552260684Skaiw _mur_k1 *= _mur_c1; \ 553260684Skaiw _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 554260684Skaiw _mur_k1 *= _mur_c2; \ 555260684Skaiw \ 556260684Skaiw _mur_h1 ^= _mur_k1; \ 557260684Skaiw _mur_h1 = MUR_ROTL32(_mur_h1,13); \ 558260684Skaiw _mur_h1 = _mur_h1*5+0xe6546b64; \ 559260684Skaiw } \ 560260684Skaiw _mur_tail = (const uint8_t*)(_mur_data + _mur_nblocks*4); \ 561260684Skaiw _mur_k1=0; \ 562260684Skaiw switch((keylen) & 3) { \ 563260684Skaiw case 3: _mur_k1 ^= _mur_tail[2] << 16; \ 564260684Skaiw case 2: _mur_k1 ^= _mur_tail[1] << 8; \ 565260684Skaiw case 1: _mur_k1 ^= _mur_tail[0]; \ 566260684Skaiw _mur_k1 *= _mur_c1; \ 567260684Skaiw _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 568260684Skaiw _mur_k1 *= _mur_c2; \ 569260684Skaiw _mur_h1 ^= _mur_k1; \ 570260684Skaiw } \ 571260684Skaiw _mur_h1 ^= (keylen); \ 572260684Skaiw MUR_FMIX(_mur_h1); \ 573260684Skaiw hashv = _mur_h1; \ 574260684Skaiw bkt = hashv & (num_bkts-1); \ 575260684Skaiw} while(0) 576260684Skaiw#endif /* HASH_USING_NO_STRICT_ALIASING */ 577260684Skaiw 578260684Skaiw/* key comparison function; return 0 if keys equal */ 579260684Skaiw#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) 580260684Skaiw 581260684Skaiw/* iterate over items in a known bucket to find desired item */ 582260684Skaiw#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ 583260684Skaiwdo { \ 584260684Skaiw if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ 585260684Skaiw else out=NULL; \ 586260684Skaiw while (out) { \ 587260684Skaiw if ((out)->hh.keylen == keylen_in) { \ 588260684Skaiw if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) break; \ 589260684Skaiw } \ 590260684Skaiw if ((out)->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); \ 591260684Skaiw else out = NULL; \ 592260684Skaiw } \ 593260684Skaiw} while(0) 594260684Skaiw 595260684Skaiw/* add an item to a bucket */ 596260684Skaiw#define HASH_ADD_TO_BKT(head,addhh) \ 597260684Skaiwdo { \ 598260684Skaiw head.count++; \ 599260684Skaiw (addhh)->hh_next = head.hh_head; \ 600260684Skaiw (addhh)->hh_prev = NULL; \ 601260684Skaiw if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ 602260684Skaiw (head).hh_head=addhh; \ 603260684Skaiw if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ 604260684Skaiw && (addhh)->tbl->noexpand != 1) { \ 605260684Skaiw HASH_EXPAND_BUCKETS((addhh)->tbl); \ 606260684Skaiw } \ 607260684Skaiw} while(0) 608260684Skaiw 609260684Skaiw/* remove an item from a given bucket */ 610260684Skaiw#define HASH_DEL_IN_BKT(hh,head,hh_del) \ 611260684Skaiw (head).count--; \ 612260684Skaiw if ((head).hh_head == hh_del) { \ 613260684Skaiw (head).hh_head = hh_del->hh_next; \ 614260684Skaiw } \ 615260684Skaiw if (hh_del->hh_prev) { \ 616260684Skaiw hh_del->hh_prev->hh_next = hh_del->hh_next; \ 617260684Skaiw } \ 618260684Skaiw if (hh_del->hh_next) { \ 619260684Skaiw hh_del->hh_next->hh_prev = hh_del->hh_prev; \ 620260684Skaiw } 621260684Skaiw 622260684Skaiw/* Bucket expansion has the effect of doubling the number of buckets 623260684Skaiw * and redistributing the items into the new buckets. Ideally the 624260684Skaiw * items will distribute more or less evenly into the new buckets 625260684Skaiw * (the extent to which this is true is a measure of the quality of 626260684Skaiw * the hash function as it applies to the key domain). 627260684Skaiw * 628260684Skaiw * With the items distributed into more buckets, the chain length 629260684Skaiw * (item count) in each bucket is reduced. Thus by expanding buckets 630260684Skaiw * the hash keeps a bound on the chain length. This bounded chain 631260684Skaiw * length is the essence of how a hash provides constant time lookup. 632260684Skaiw * 633260684Skaiw * The calculation of tbl->ideal_chain_maxlen below deserves some 634260684Skaiw * explanation. First, keep in mind that we're calculating the ideal 635260684Skaiw * maximum chain length based on the *new* (doubled) bucket count. 636260684Skaiw * In fractions this is just n/b (n=number of items,b=new num buckets). 637260684Skaiw * Since the ideal chain length is an integer, we want to calculate 638260684Skaiw * ceil(n/b). We don't depend on floating point arithmetic in this 639260684Skaiw * hash, so to calculate ceil(n/b) with integers we could write 640260684Skaiw * 641260684Skaiw * ceil(n/b) = (n/b) + ((n%b)?1:0) 642260684Skaiw * 643260684Skaiw * and in fact a previous version of this hash did just that. 644260684Skaiw * But now we have improved things a bit by recognizing that b is 645260684Skaiw * always a power of two. We keep its base 2 log handy (call it lb), 646260684Skaiw * so now we can write this with a bit shift and logical AND: 647260684Skaiw * 648260684Skaiw * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) 649260684Skaiw * 650260684Skaiw */ 651260684Skaiw#define HASH_EXPAND_BUCKETS(tbl) \ 652260684Skaiwdo { \ 653260684Skaiw unsigned _he_bkt; \ 654260684Skaiw unsigned _he_bkt_i; \ 655260684Skaiw struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ 656260684Skaiw UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ 657260684Skaiw _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ 658260684Skaiw 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 659260684Skaiw if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ 660260684Skaiw memset(_he_new_buckets, 0, \ 661260684Skaiw 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 662260684Skaiw tbl->ideal_chain_maxlen = \ 663260684Skaiw (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ 664260684Skaiw ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ 665260684Skaiw tbl->nonideal_items = 0; \ 666260684Skaiw for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ 667260684Skaiw { \ 668260684Skaiw _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ 669260684Skaiw while (_he_thh) { \ 670260684Skaiw _he_hh_nxt = _he_thh->hh_next; \ 671260684Skaiw HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ 672260684Skaiw _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ 673260684Skaiw if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ 674260684Skaiw tbl->nonideal_items++; \ 675260684Skaiw _he_newbkt->expand_mult = _he_newbkt->count / \ 676260684Skaiw tbl->ideal_chain_maxlen; \ 677260684Skaiw } \ 678260684Skaiw _he_thh->hh_prev = NULL; \ 679260684Skaiw _he_thh->hh_next = _he_newbkt->hh_head; \ 680260684Skaiw if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ 681260684Skaiw _he_thh; \ 682260684Skaiw _he_newbkt->hh_head = _he_thh; \ 683260684Skaiw _he_thh = _he_hh_nxt; \ 684260684Skaiw } \ 685260684Skaiw } \ 686260684Skaiw uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 687260684Skaiw tbl->num_buckets *= 2; \ 688260684Skaiw tbl->log2_num_buckets++; \ 689260684Skaiw tbl->buckets = _he_new_buckets; \ 690260684Skaiw tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ 691260684Skaiw (tbl->ineff_expands+1) : 0; \ 692260684Skaiw if (tbl->ineff_expands > 1) { \ 693260684Skaiw tbl->noexpand=1; \ 694260684Skaiw uthash_noexpand_fyi(tbl); \ 695260684Skaiw } \ 696260684Skaiw uthash_expand_fyi(tbl); \ 697260684Skaiw} while(0) 698260684Skaiw 699260684Skaiw 700260684Skaiw/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ 701260684Skaiw/* Note that HASH_SORT assumes the hash handle name to be hh. 702260684Skaiw * HASH_SRT was added to allow the hash handle name to be passed in. */ 703260684Skaiw#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) 704260684Skaiw#define HASH_SRT(hh,head,cmpfcn) \ 705260684Skaiwdo { \ 706260684Skaiw unsigned _hs_i; \ 707260684Skaiw unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ 708260684Skaiw struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ 709260684Skaiw if (head) { \ 710260684Skaiw _hs_insize = 1; \ 711260684Skaiw _hs_looping = 1; \ 712260684Skaiw _hs_list = &((head)->hh); \ 713260684Skaiw while (_hs_looping) { \ 714260684Skaiw _hs_p = _hs_list; \ 715260684Skaiw _hs_list = NULL; \ 716260684Skaiw _hs_tail = NULL; \ 717260684Skaiw _hs_nmerges = 0; \ 718260684Skaiw while (_hs_p) { \ 719260684Skaiw _hs_nmerges++; \ 720260684Skaiw _hs_q = _hs_p; \ 721260684Skaiw _hs_psize = 0; \ 722260684Skaiw for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ 723260684Skaiw _hs_psize++; \ 724260684Skaiw _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 725260684Skaiw ((void*)((char*)(_hs_q->next) + \ 726260684Skaiw (head)->hh.tbl->hho)) : NULL); \ 727260684Skaiw if (! (_hs_q) ) break; \ 728260684Skaiw } \ 729260684Skaiw _hs_qsize = _hs_insize; \ 730260684Skaiw while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ 731260684Skaiw if (_hs_psize == 0) { \ 732260684Skaiw _hs_e = _hs_q; \ 733260684Skaiw _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 734260684Skaiw ((void*)((char*)(_hs_q->next) + \ 735260684Skaiw (head)->hh.tbl->hho)) : NULL); \ 736260684Skaiw _hs_qsize--; \ 737260684Skaiw } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ 738260684Skaiw _hs_e = _hs_p; \ 739260684Skaiw _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 740260684Skaiw ((void*)((char*)(_hs_p->next) + \ 741260684Skaiw (head)->hh.tbl->hho)) : NULL); \ 742260684Skaiw _hs_psize--; \ 743260684Skaiw } else if (( \ 744260684Skaiw cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ 745260684Skaiw DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ 746260684Skaiw ) <= 0) { \ 747260684Skaiw _hs_e = _hs_p; \ 748260684Skaiw _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 749260684Skaiw ((void*)((char*)(_hs_p->next) + \ 750260684Skaiw (head)->hh.tbl->hho)) : NULL); \ 751260684Skaiw _hs_psize--; \ 752260684Skaiw } else { \ 753260684Skaiw _hs_e = _hs_q; \ 754260684Skaiw _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 755260684Skaiw ((void*)((char*)(_hs_q->next) + \ 756260684Skaiw (head)->hh.tbl->hho)) : NULL); \ 757260684Skaiw _hs_qsize--; \ 758260684Skaiw } \ 759260684Skaiw if ( _hs_tail ) { \ 760260684Skaiw _hs_tail->next = ((_hs_e) ? \ 761260684Skaiw ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ 762260684Skaiw } else { \ 763260684Skaiw _hs_list = _hs_e; \ 764260684Skaiw } \ 765260684Skaiw _hs_e->prev = ((_hs_tail) ? \ 766260684Skaiw ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ 767260684Skaiw _hs_tail = _hs_e; \ 768260684Skaiw } \ 769260684Skaiw _hs_p = _hs_q; \ 770260684Skaiw } \ 771260684Skaiw _hs_tail->next = NULL; \ 772260684Skaiw if ( _hs_nmerges <= 1 ) { \ 773260684Skaiw _hs_looping=0; \ 774260684Skaiw (head)->hh.tbl->tail = _hs_tail; \ 775260684Skaiw DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ 776260684Skaiw } \ 777260684Skaiw _hs_insize *= 2; \ 778260684Skaiw } \ 779260684Skaiw HASH_FSCK(hh,head); \ 780260684Skaiw } \ 781260684Skaiw} while (0) 782260684Skaiw 783260684Skaiw/* This function selects items from one hash into another hash. 784260684Skaiw * The end result is that the selected items have dual presence 785260684Skaiw * in both hashes. There is no copy of the items made; rather 786260684Skaiw * they are added into the new hash through a secondary hash 787260684Skaiw * hash handle that must be present in the structure. */ 788260684Skaiw#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ 789260684Skaiwdo { \ 790260684Skaiw unsigned _src_bkt, _dst_bkt; \ 791260684Skaiw void *_last_elt=NULL, *_elt; \ 792260684Skaiw UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ 793260684Skaiw ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ 794260684Skaiw if (src) { \ 795260684Skaiw for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ 796260684Skaiw for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ 797260684Skaiw _src_hh; \ 798260684Skaiw _src_hh = _src_hh->hh_next) { \ 799260684Skaiw _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ 800260684Skaiw if (cond(_elt)) { \ 801260684Skaiw _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ 802260684Skaiw _dst_hh->key = _src_hh->key; \ 803260684Skaiw _dst_hh->keylen = _src_hh->keylen; \ 804260684Skaiw _dst_hh->hashv = _src_hh->hashv; \ 805260684Skaiw _dst_hh->prev = _last_elt; \ 806260684Skaiw _dst_hh->next = NULL; \ 807260684Skaiw if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ 808260684Skaiw if (!dst) { \ 809260684Skaiw DECLTYPE_ASSIGN(dst,_elt); \ 810260684Skaiw HASH_MAKE_TABLE(hh_dst,dst); \ 811260684Skaiw } else { \ 812260684Skaiw _dst_hh->tbl = (dst)->hh_dst.tbl; \ 813260684Skaiw } \ 814260684Skaiw HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ 815260684Skaiw HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ 816260684Skaiw (dst)->hh_dst.tbl->num_items++; \ 817260684Skaiw _last_elt = _elt; \ 818260684Skaiw _last_elt_hh = _dst_hh; \ 819260684Skaiw } \ 820260684Skaiw } \ 821260684Skaiw } \ 822260684Skaiw } \ 823260684Skaiw HASH_FSCK(hh_dst,dst); \ 824260684Skaiw} while (0) 825260684Skaiw 826260684Skaiw#define HASH_CLEAR(hh,head) \ 827260684Skaiwdo { \ 828260684Skaiw if (head) { \ 829260684Skaiw uthash_free((head)->hh.tbl->buckets, \ 830260684Skaiw (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ 831260684Skaiw HASH_BLOOM_FREE((head)->hh.tbl); \ 832260684Skaiw uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 833260684Skaiw (head)=NULL; \ 834260684Skaiw } \ 835260684Skaiw} while(0) 836260684Skaiw 837260684Skaiw#ifdef NO_DECLTYPE 838260684Skaiw#define HASH_ITER(hh,head,el,tmp) \ 839260684Skaiwfor((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ 840260684Skaiw el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) 841260684Skaiw#else 842260684Skaiw#define HASH_ITER(hh,head,el,tmp) \ 843260684Skaiwfor((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ 844260684Skaiw el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) 845260684Skaiw#endif 846260684Skaiw 847260684Skaiw/* obtain a count of items in the hash */ 848260684Skaiw#define HASH_COUNT(head) HASH_CNT(hh,head) 849260684Skaiw#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) 850260684Skaiw 851260684Skaiwtypedef struct UT_hash_bucket { 852260684Skaiw struct UT_hash_handle *hh_head; 853260684Skaiw unsigned count; 854260684Skaiw 855260684Skaiw /* expand_mult is normally set to 0. In this situation, the max chain length 856260684Skaiw * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If 857260684Skaiw * the bucket's chain exceeds this length, bucket expansion is triggered). 858260684Skaiw * However, setting expand_mult to a non-zero value delays bucket expansion 859260684Skaiw * (that would be triggered by additions to this particular bucket) 860260684Skaiw * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. 861260684Skaiw * (The multiplier is simply expand_mult+1). The whole idea of this 862260684Skaiw * multiplier is to reduce bucket expansions, since they are expensive, in 863260684Skaiw * situations where we know that a particular bucket tends to be overused. 864260684Skaiw * It is better to let its chain length grow to a longer yet-still-bounded 865260684Skaiw * value, than to do an O(n) bucket expansion too often. 866260684Skaiw */ 867260684Skaiw unsigned expand_mult; 868260684Skaiw 869260684Skaiw} UT_hash_bucket; 870260684Skaiw 871260684Skaiw/* random signature used only to find hash tables in external analysis */ 872260684Skaiw#define HASH_SIGNATURE 0xa0111fe1 873260684Skaiw#define HASH_BLOOM_SIGNATURE 0xb12220f2 874260684Skaiw 875260684Skaiwtypedef struct UT_hash_table { 876260684Skaiw UT_hash_bucket *buckets; 877260684Skaiw unsigned num_buckets, log2_num_buckets; 878260684Skaiw unsigned num_items; 879260684Skaiw struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ 880260684Skaiw ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ 881260684Skaiw 882260684Skaiw /* in an ideal situation (all buckets used equally), no bucket would have 883260684Skaiw * more than ceil(#items/#buckets) items. that's the ideal chain length. */ 884260684Skaiw unsigned ideal_chain_maxlen; 885260684Skaiw 886260684Skaiw /* nonideal_items is the number of items in the hash whose chain position 887260684Skaiw * exceeds the ideal chain maxlen. these items pay the penalty for an uneven 888260684Skaiw * hash distribution; reaching them in a chain traversal takes >ideal steps */ 889260684Skaiw unsigned nonideal_items; 890260684Skaiw 891260684Skaiw /* ineffective expands occur when a bucket doubling was performed, but 892260684Skaiw * afterward, more than half the items in the hash had nonideal chain 893260684Skaiw * positions. If this happens on two consecutive expansions we inhibit any 894260684Skaiw * further expansion, as it's not helping; this happens when the hash 895260684Skaiw * function isn't a good fit for the key domain. When expansion is inhibited 896260684Skaiw * the hash will still work, albeit no longer in constant time. */ 897260684Skaiw unsigned ineff_expands, noexpand; 898260684Skaiw 899260684Skaiw uint32_t signature; /* used only to find hash tables in external analysis */ 900260684Skaiw#ifdef HASH_BLOOM 901260684Skaiw uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ 902260684Skaiw uint8_t *bloom_bv; 903260684Skaiw char bloom_nbits; 904260684Skaiw#endif 905260684Skaiw 906260684Skaiw} UT_hash_table; 907260684Skaiw 908260684Skaiwtypedef struct UT_hash_handle { 909260684Skaiw struct UT_hash_table *tbl; 910260684Skaiw void *prev; /* prev element in app order */ 911260684Skaiw void *next; /* next element in app order */ 912260684Skaiw struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ 913260684Skaiw struct UT_hash_handle *hh_next; /* next hh in bucket order */ 914260684Skaiw void *key; /* ptr to enclosing struct's key */ 915260684Skaiw unsigned keylen; /* enclosing struct's key len */ 916260684Skaiw unsigned hashv; /* result of hash-fcn(key) */ 917260684Skaiw} UT_hash_handle; 918260684Skaiw 919260684Skaiw#endif /* UTHASH_H */ 920