1262395Sbapt/* 2262395SbaptCopyright (c) 2003-2013, Troy D. Hanson http://troydhanson.github.com/uthash/ 3262395SbaptAll rights reserved. 4262395Sbapt 5262395SbaptRedistribution and use in source and binary forms, with or without 6262395Sbaptmodification, are permitted provided that the following conditions are met: 7262395Sbapt 8262395Sbapt * Redistributions of source code must retain the above copyright 9262395Sbapt notice, this list of conditions and the following disclaimer. 10262395Sbapt 11262395SbaptTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 12262395SbaptIS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 13262395SbaptTO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 14262395SbaptPARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 15262395SbaptOR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 16262395SbaptEXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 17262395SbaptPROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 18262395SbaptPROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 19262395SbaptLIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 20262395SbaptNEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 21262395SbaptSOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 22262395Sbapt*/ 23262395Sbapt 24262395Sbapt#ifndef UTHASH_H 25301339Sbapt#define UTHASH_H 26262395Sbapt 27262395Sbapt#include <string.h> /* memcmp,strlen */ 28262395Sbapt#include <stddef.h> /* ptrdiff_t */ 29262395Sbapt#include <stdlib.h> /* exit() */ 30301339Sbapt#include "mum.h" 31262395Sbapt 32262395Sbapt/* These macros use decltype or the earlier __typeof GNU extension. 33262395Sbapt As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 34262395Sbapt when compiling c++ source) this code uses whatever method is needed 35262395Sbapt or, for VS2008 where neither is available, uses casting workarounds. */ 36262395Sbapt#ifdef _MSC_VER /* MS compiler */ 37262395Sbapt#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 38262395Sbapt#define DECLTYPE(x) (decltype(x)) 39262395Sbapt#else /* VS2008 or older (or VS2010 in C mode) */ 40262395Sbapt#define NO_DECLTYPE 41262395Sbapt#define DECLTYPE(x) 42262395Sbapt#endif 43262395Sbapt#else /* GNU, Sun and other compilers */ 44262395Sbapt#define DECLTYPE(x) (__typeof(x)) 45262395Sbapt#endif 46262395Sbapt 47262395Sbapt#ifdef NO_DECLTYPE 48262395Sbapt#define DECLTYPE_ASSIGN(dst,src) \ 49262395Sbaptdo { \ 50262395Sbapt char **_da_dst = (char**)(&(dst)); \ 51262395Sbapt *_da_dst = (char*)(src); \ 52262395Sbapt} while(0) 53301339Sbapt#else 54262395Sbapt#define DECLTYPE_ASSIGN(dst,src) \ 55262395Sbaptdo { \ 56262395Sbapt (dst) = DECLTYPE(dst)(src); \ 57262395Sbapt} while(0) 58262395Sbapt#endif 59262395Sbapt 60262395Sbapt/* a number of the hash function use uint32_t which isn't defined on win32 */ 61262395Sbapt#ifdef _MSC_VER 62262395Sbapttypedef unsigned int uint32_t; 63262395Sbapttypedef unsigned char uint8_t; 64262395Sbapt#else 65262395Sbapt#include <inttypes.h> /* uint32_t */ 66262395Sbapt#endif 67262395Sbapt 68262395Sbapt#define UTHASH_VERSION 1.9.8 69262395Sbapt 70262395Sbapt#ifndef uthash_fatal 71262395Sbapt#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ 72262395Sbapt#endif 73262395Sbapt#ifndef uthash_malloc 74262395Sbapt#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ 75262395Sbapt#endif 76262395Sbapt#ifndef uthash_free 77262395Sbapt#define uthash_free(ptr,sz) free(ptr) /* free fcn */ 78262395Sbapt#endif 79262395Sbapt 80262395Sbapt#ifndef uthash_noexpand_fyi 81262395Sbapt#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ 82262395Sbapt#endif 83262395Sbapt#ifndef uthash_expand_fyi 84262395Sbapt#define uthash_expand_fyi(tbl) /* can be defined to log expands */ 85262395Sbapt#endif 86262395Sbapt 87262395Sbapt/* initial number of buckets */ 88262395Sbapt#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ 89262395Sbapt#define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */ 90262395Sbapt#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ 91262395Sbapt 92262395Sbapt/* calculate the element whose hash handle address is hhe */ 93262395Sbapt#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) 94262395Sbapt 95262395Sbapt#define HASH_FIND(hh,head,keyptr,keylen,out) \ 96262395Sbaptdo { \ 97262395Sbapt unsigned _hf_bkt,_hf_hashv; \ 98262395Sbapt out=NULL; \ 99262395Sbapt if (head) { \ 100262395Sbapt HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \ 101262395Sbapt if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \ 102262395Sbapt HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \ 103262395Sbapt keyptr,keylen,out); \ 104262395Sbapt } \ 105262395Sbapt } \ 106262395Sbapt} while (0) 107262395Sbapt 108262395Sbapt#ifdef HASH_BLOOM 109262395Sbapt#define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM) 110262395Sbapt#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0) 111262395Sbapt#define HASH_BLOOM_MAKE(tbl) \ 112262395Sbaptdo { \ 113262395Sbapt (tbl)->bloom_nbits = HASH_BLOOM; \ 114262395Sbapt (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ 115262395Sbapt if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ 116262395Sbapt memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ 117262395Sbapt (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ 118301339Sbapt} while (0) 119262395Sbapt 120262395Sbapt#define HASH_BLOOM_FREE(tbl) \ 121262395Sbaptdo { \ 122262395Sbapt uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ 123301339Sbapt} while (0) 124262395Sbapt 125262395Sbapt#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8))) 126262395Sbapt#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8))) 127262395Sbapt 128262395Sbapt#define HASH_BLOOM_ADD(tbl,hashv) \ 129262395Sbapt HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) 130262395Sbapt 131262395Sbapt#define HASH_BLOOM_TEST(tbl,hashv) \ 132262395Sbapt HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) 133262395Sbapt 134262395Sbapt#else 135301339Sbapt#define HASH_BLOOM_MAKE(tbl) 136301339Sbapt#define HASH_BLOOM_FREE(tbl) 137301339Sbapt#define HASH_BLOOM_ADD(tbl,hashv) 138262395Sbapt#define HASH_BLOOM_TEST(tbl,hashv) (1) 139262395Sbapt#define HASH_BLOOM_BYTELEN 0 140262395Sbapt#endif 141262395Sbapt 142262395Sbapt#define HASH_MAKE_TABLE(hh,head) \ 143262395Sbaptdo { \ 144262395Sbapt (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ 145262395Sbapt sizeof(UT_hash_table)); \ 146262395Sbapt if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ 147262395Sbapt memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ 148262395Sbapt (head)->hh.tbl->tail = &((head)->hh); \ 149262395Sbapt (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ 150262395Sbapt (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ 151262395Sbapt (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ 152262395Sbapt (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ 153262395Sbapt HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 154262395Sbapt if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ 155262395Sbapt memset((head)->hh.tbl->buckets, 0, \ 156262395Sbapt HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 157262395Sbapt HASH_BLOOM_MAKE((head)->hh.tbl); \ 158262395Sbapt (head)->hh.tbl->signature = HASH_SIGNATURE; \ 159262395Sbapt} while(0) 160262395Sbapt 161262395Sbapt#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ 162262395Sbapt HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add) 163262395Sbapt 164262395Sbapt#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \ 165262395Sbaptdo { \ 166262395Sbapt replaced=NULL; \ 167262395Sbapt HASH_FIND(hh,head,&((add)->fieldname),keylen_in,replaced); \ 168262395Sbapt if (replaced!=NULL) { \ 169262395Sbapt HASH_DELETE(hh,head,replaced); \ 170262395Sbapt }; \ 171262395Sbapt HASH_ADD(hh,head,fieldname,keylen_in,add); \ 172262395Sbapt} while(0) 173301339Sbapt 174262395Sbapt#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ 175262395Sbaptdo { \ 176262395Sbapt unsigned _ha_bkt; \ 177262395Sbapt (add)->hh.next = NULL; \ 178262395Sbapt (add)->hh.key = (const char*)keyptr; \ 179262395Sbapt (add)->hh.keylen = (unsigned)keylen_in; \ 180262395Sbapt if (!(head)) { \ 181262395Sbapt head = (add); \ 182262395Sbapt (head)->hh.prev = NULL; \ 183262395Sbapt HASH_MAKE_TABLE(hh,head); \ 184262395Sbapt } else { \ 185262395Sbapt (head)->hh.tbl->tail->next = (add); \ 186262395Sbapt (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ 187262395Sbapt (head)->hh.tbl->tail = &((add)->hh); \ 188262395Sbapt } \ 189262395Sbapt (head)->hh.tbl->num_items++; \ 190262395Sbapt (add)->hh.tbl = (head)->hh.tbl; \ 191262395Sbapt HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \ 192262395Sbapt (add)->hh.hashv, _ha_bkt); \ 193262395Sbapt HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \ 194262395Sbapt HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \ 195262395Sbapt HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ 196262395Sbapt HASH_FSCK(hh,head); \ 197262395Sbapt} while(0) 198262395Sbapt 199262395Sbapt#define HASH_TO_BKT( hashv, num_bkts, bkt ) \ 200262395Sbaptdo { \ 201262395Sbapt bkt = ((hashv) & ((num_bkts) - 1)); \ 202262395Sbapt} while(0) 203262395Sbapt 204262395Sbapt/* delete "delptr" from the hash table. 205262395Sbapt * "the usual" patch-up process for the app-order doubly-linked-list. 206262395Sbapt * The use of _hd_hh_del below deserves special explanation. 207262395Sbapt * These used to be expressed using (delptr) but that led to a bug 208262395Sbapt * if someone used the same symbol for the head and deletee, like 209262395Sbapt * HASH_DELETE(hh,users,users); 210262395Sbapt * We want that to work, but by changing the head (users) below 211262395Sbapt * we were forfeiting our ability to further refer to the deletee (users) 212262395Sbapt * in the patch-up process. Solution: use scratch space to 213262395Sbapt * copy the deletee pointer, then the latter references are via that 214262395Sbapt * scratch pointer rather than through the repointed (users) symbol. 215262395Sbapt */ 216262395Sbapt#define HASH_DELETE(hh,head,delptr) \ 217262395Sbaptdo { \ 218262395Sbapt unsigned _hd_bkt; \ 219262395Sbapt struct UT_hash_handle *_hd_hh_del; \ 220262395Sbapt if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ 221262395Sbapt uthash_free((head)->hh.tbl->buckets, \ 222262395Sbapt (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 223262395Sbapt HASH_BLOOM_FREE((head)->hh.tbl); \ 224262395Sbapt uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 225262395Sbapt head = NULL; \ 226262395Sbapt } else { \ 227262395Sbapt _hd_hh_del = &((delptr)->hh); \ 228262395Sbapt if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ 229262395Sbapt (head)->hh.tbl->tail = \ 230262395Sbapt (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ 231262395Sbapt (head)->hh.tbl->hho); \ 232262395Sbapt } \ 233262395Sbapt if ((delptr)->hh.prev) { \ 234262395Sbapt ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ 235262395Sbapt (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ 236262395Sbapt } else { \ 237262395Sbapt DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ 238262395Sbapt } \ 239262395Sbapt if (_hd_hh_del->next) { \ 240262395Sbapt ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \ 241262395Sbapt (head)->hh.tbl->hho))->prev = \ 242262395Sbapt _hd_hh_del->prev; \ 243262395Sbapt } \ 244262395Sbapt HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ 245262395Sbapt HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ 246262395Sbapt (head)->hh.tbl->num_items--; \ 247262395Sbapt } \ 248262395Sbapt HASH_FSCK(hh,head); \ 249262395Sbapt} while (0) 250262395Sbapt 251262395Sbapt 252262395Sbapt/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ 253262395Sbapt#define HASH_FIND_STR(head,findstr,out) \ 254262395Sbapt HASH_FIND(hh,head,findstr,strlen(findstr),out) 255262395Sbapt#define HASH_ADD_STR(head,strfield,add) \ 256262395Sbapt HASH_ADD(hh,head,strfield,strlen(add->strfield),add) 257262395Sbapt#define HASH_REPLACE_STR(head,strfield,add,replaced) \ 258262395Sbapt HASH_REPLACE(hh,head,strfield,strlen(add->strfield),add,replaced) 259262395Sbapt#define HASH_FIND_INT(head,findint,out) \ 260262395Sbapt HASH_FIND(hh,head,findint,sizeof(int),out) 261262395Sbapt#define HASH_ADD_INT(head,intfield,add) \ 262262395Sbapt HASH_ADD(hh,head,intfield,sizeof(int),add) 263262395Sbapt#define HASH_REPLACE_INT(head,intfield,add,replaced) \ 264262395Sbapt HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced) 265262395Sbapt#define HASH_FIND_PTR(head,findptr,out) \ 266262395Sbapt HASH_FIND(hh,head,findptr,sizeof(void *),out) 267262395Sbapt#define HASH_ADD_PTR(head,ptrfield,add) \ 268262395Sbapt HASH_ADD(hh,head,ptrfield,sizeof(void *),add) 269262395Sbapt#define HASH_REPLACE_PTR(head,ptrfield,add) \ 270262395Sbapt HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced) 271262395Sbapt#define HASH_DEL(head,delptr) \ 272262395Sbapt HASH_DELETE(hh,head,delptr) 273262395Sbapt 274262395Sbapt/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. 275262395Sbapt * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. 276262395Sbapt */ 277262395Sbapt#ifdef HASH_DEBUG 278262395Sbapt#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) 279262395Sbapt#define HASH_FSCK(hh,head) \ 280262395Sbaptdo { \ 281262395Sbapt unsigned _bkt_i; \ 282262395Sbapt unsigned _count, _bkt_count; \ 283262395Sbapt char *_prev; \ 284262395Sbapt struct UT_hash_handle *_thh; \ 285262395Sbapt if (head) { \ 286262395Sbapt _count = 0; \ 287262395Sbapt for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ 288262395Sbapt _bkt_count = 0; \ 289262395Sbapt _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ 290262395Sbapt _prev = NULL; \ 291262395Sbapt while (_thh) { \ 292262395Sbapt if (_prev != (char*)(_thh->hh_prev)) { \ 293262395Sbapt HASH_OOPS("invalid hh_prev %p, actual %p\n", \ 294262395Sbapt _thh->hh_prev, _prev ); \ 295262395Sbapt } \ 296262395Sbapt _bkt_count++; \ 297262395Sbapt _prev = (char*)(_thh); \ 298262395Sbapt _thh = _thh->hh_next; \ 299262395Sbapt } \ 300262395Sbapt _count += _bkt_count; \ 301262395Sbapt if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ 302262395Sbapt HASH_OOPS("invalid bucket count %d, actual %d\n", \ 303262395Sbapt (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ 304262395Sbapt } \ 305262395Sbapt } \ 306262395Sbapt if (_count != (head)->hh.tbl->num_items) { \ 307262395Sbapt HASH_OOPS("invalid hh item count %d, actual %d\n", \ 308262395Sbapt (head)->hh.tbl->num_items, _count ); \ 309262395Sbapt } \ 310262395Sbapt /* traverse hh in app order; check next/prev integrity, count */ \ 311262395Sbapt _count = 0; \ 312262395Sbapt _prev = NULL; \ 313262395Sbapt _thh = &(head)->hh; \ 314262395Sbapt while (_thh) { \ 315262395Sbapt _count++; \ 316262395Sbapt if (_prev !=(char*)(_thh->prev)) { \ 317262395Sbapt HASH_OOPS("invalid prev %p, actual %p\n", \ 318262395Sbapt _thh->prev, _prev ); \ 319262395Sbapt } \ 320262395Sbapt _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ 321262395Sbapt _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ 322262395Sbapt (head)->hh.tbl->hho) : NULL ); \ 323262395Sbapt } \ 324262395Sbapt if (_count != (head)->hh.tbl->num_items) { \ 325262395Sbapt HASH_OOPS("invalid app item count %d, actual %d\n", \ 326262395Sbapt (head)->hh.tbl->num_items, _count ); \ 327262395Sbapt } \ 328262395Sbapt } \ 329262395Sbapt} while (0) 330262395Sbapt#else 331301339Sbapt#define HASH_FSCK(hh,head) 332262395Sbapt#endif 333262395Sbapt 334301339Sbapt/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to 335262395Sbapt * the descriptor to which this macro is defined for tuning the hash function. 336262395Sbapt * The app can #include <unistd.h> to get the prototype for write(2). */ 337262395Sbapt#ifdef HASH_EMIT_KEYS 338262395Sbapt#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ 339262395Sbaptdo { \ 340262395Sbapt unsigned _klen = fieldlen; \ 341262395Sbapt write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ 342262395Sbapt write(HASH_EMIT_KEYS, keyptr, fieldlen); \ 343262395Sbapt} while (0) 344301339Sbapt#else 345301339Sbapt#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) 346262395Sbapt#endif 347262395Sbapt 348262395Sbapt/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ 349301339Sbapt#ifdef HASH_FUNCTION 350262395Sbapt#define HASH_FCN HASH_FUNCTION 351262395Sbapt#else 352262395Sbapt#define HASH_FCN HASH_XX 353262395Sbapt#endif 354262395Sbapt 355262395Sbapt#define XX_HASH_PRIME 2654435761U 356262395Sbapt 357262395Sbapt#define HASH_XX(key,keylen,num_bkts,hashv,bkt) \ 358262395Sbaptdo { \ 359301339Sbapt hashv = mum_hash (key, keylen, XX_HASH_PRIME); \ 360262395Sbapt bkt = (hashv) & (num_bkts-1); \ 361262395Sbapt} while (0) 362262395Sbapt 363262395Sbapt 364262395Sbapt 365262395Sbapt/* key comparison function; return 0 if keys equal */ 366301339Sbapt#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) 367262395Sbapt 368262395Sbapt/* iterate over items in a known bucket to find desired item */ 369262395Sbapt#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ 370262395Sbaptdo { \ 371262395Sbapt if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ 372262395Sbapt else out=NULL; \ 373262395Sbapt while (out) { \ 374262395Sbapt if ((out)->hh.keylen == keylen_in) { \ 375262395Sbapt if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) break; \ 376262395Sbapt } \ 377262395Sbapt if ((out)->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); \ 378262395Sbapt else out = NULL; \ 379262395Sbapt } \ 380262395Sbapt} while(0) 381262395Sbapt 382262395Sbapt/* add an item to a bucket */ 383262395Sbapt#define HASH_ADD_TO_BKT(head,addhh) \ 384262395Sbaptdo { \ 385262395Sbapt head.count++; \ 386262395Sbapt (addhh)->hh_next = head.hh_head; \ 387262395Sbapt (addhh)->hh_prev = NULL; \ 388262395Sbapt if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ 389262395Sbapt (head).hh_head=addhh; \ 390262395Sbapt if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ 391262395Sbapt && (addhh)->tbl->noexpand != 1) { \ 392262395Sbapt HASH_EXPAND_BUCKETS((addhh)->tbl); \ 393262395Sbapt } \ 394262395Sbapt} while(0) 395262395Sbapt 396262395Sbapt/* remove an item from a given bucket */ 397262395Sbapt#define HASH_DEL_IN_BKT(hh,head,hh_del) \ 398262395Sbapt (head).count--; \ 399262395Sbapt if ((head).hh_head == hh_del) { \ 400262395Sbapt (head).hh_head = hh_del->hh_next; \ 401262395Sbapt } \ 402262395Sbapt if (hh_del->hh_prev) { \ 403262395Sbapt hh_del->hh_prev->hh_next = hh_del->hh_next; \ 404262395Sbapt } \ 405262395Sbapt if (hh_del->hh_next) { \ 406262395Sbapt hh_del->hh_next->hh_prev = hh_del->hh_prev; \ 407301339Sbapt } 408262395Sbapt 409262395Sbapt/* Bucket expansion has the effect of doubling the number of buckets 410262395Sbapt * and redistributing the items into the new buckets. Ideally the 411262395Sbapt * items will distribute more or less evenly into the new buckets 412262395Sbapt * (the extent to which this is true is a measure of the quality of 413301339Sbapt * the hash function as it applies to the key domain). 414301339Sbapt * 415262395Sbapt * With the items distributed into more buckets, the chain length 416262395Sbapt * (item count) in each bucket is reduced. Thus by expanding buckets 417301339Sbapt * the hash keeps a bound on the chain length. This bounded chain 418262395Sbapt * length is the essence of how a hash provides constant time lookup. 419301339Sbapt * 420262395Sbapt * The calculation of tbl->ideal_chain_maxlen below deserves some 421262395Sbapt * explanation. First, keep in mind that we're calculating the ideal 422262395Sbapt * maximum chain length based on the *new* (doubled) bucket count. 423262395Sbapt * In fractions this is just n/b (n=number of items,b=new num buckets). 424301339Sbapt * Since the ideal chain length is an integer, we want to calculate 425262395Sbapt * ceil(n/b). We don't depend on floating point arithmetic in this 426262395Sbapt * hash, so to calculate ceil(n/b) with integers we could write 427301339Sbapt * 428262395Sbapt * ceil(n/b) = (n/b) + ((n%b)?1:0) 429301339Sbapt * 430262395Sbapt * and in fact a previous version of this hash did just that. 431262395Sbapt * But now we have improved things a bit by recognizing that b is 432262395Sbapt * always a power of two. We keep its base 2 log handy (call it lb), 433262395Sbapt * so now we can write this with a bit shift and logical AND: 434301339Sbapt * 435262395Sbapt * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) 436301339Sbapt * 437262395Sbapt */ 438262395Sbapt#define HASH_EXPAND_BUCKETS(tbl) \ 439262395Sbaptdo { \ 440262395Sbapt unsigned _he_bkt; \ 441262395Sbapt unsigned _he_bkt_i; \ 442262395Sbapt struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ 443262395Sbapt UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ 444262395Sbapt _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ 445262395Sbapt 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 446262395Sbapt if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ 447262395Sbapt memset(_he_new_buckets, 0, \ 448262395Sbapt 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 449262395Sbapt tbl->ideal_chain_maxlen = \ 450262395Sbapt (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ 451262395Sbapt ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ 452262395Sbapt tbl->nonideal_items = 0; \ 453262395Sbapt for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ 454262395Sbapt { \ 455262395Sbapt _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ 456262395Sbapt while (_he_thh) { \ 457262395Sbapt _he_hh_nxt = _he_thh->hh_next; \ 458262395Sbapt HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ 459262395Sbapt _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ 460262395Sbapt if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ 461262395Sbapt tbl->nonideal_items++; \ 462262395Sbapt _he_newbkt->expand_mult = _he_newbkt->count / \ 463262395Sbapt tbl->ideal_chain_maxlen; \ 464262395Sbapt } \ 465262395Sbapt _he_thh->hh_prev = NULL; \ 466262395Sbapt _he_thh->hh_next = _he_newbkt->hh_head; \ 467262395Sbapt if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ 468262395Sbapt _he_thh; \ 469262395Sbapt _he_newbkt->hh_head = _he_thh; \ 470262395Sbapt _he_thh = _he_hh_nxt; \ 471262395Sbapt } \ 472262395Sbapt } \ 473262395Sbapt uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 474262395Sbapt tbl->num_buckets *= 2; \ 475262395Sbapt tbl->log2_num_buckets++; \ 476262395Sbapt tbl->buckets = _he_new_buckets; \ 477262395Sbapt tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ 478262395Sbapt (tbl->ineff_expands+1) : 0; \ 479262395Sbapt if (tbl->ineff_expands > 1) { \ 480262395Sbapt tbl->noexpand=1; \ 481262395Sbapt uthash_noexpand_fyi(tbl); \ 482262395Sbapt } \ 483262395Sbapt uthash_expand_fyi(tbl); \ 484262395Sbapt} while(0) 485262395Sbapt 486262395Sbapt 487262395Sbapt/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ 488301339Sbapt/* Note that HASH_SORT assumes the hash handle name to be hh. 489262395Sbapt * HASH_SRT was added to allow the hash handle name to be passed in. */ 490262395Sbapt#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) 491262395Sbapt#define HASH_SRT(hh,head,cmpfcn) \ 492262395Sbaptdo { \ 493262395Sbapt unsigned _hs_i; \ 494262395Sbapt unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ 495262395Sbapt struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ 496262395Sbapt if (head) { \ 497262395Sbapt _hs_insize = 1; \ 498262395Sbapt _hs_looping = 1; \ 499262395Sbapt _hs_list = &((head)->hh); \ 500262395Sbapt while (_hs_looping) { \ 501262395Sbapt _hs_p = _hs_list; \ 502262395Sbapt _hs_list = NULL; \ 503262395Sbapt _hs_tail = NULL; \ 504262395Sbapt _hs_nmerges = 0; \ 505262395Sbapt while (_hs_p) { \ 506262395Sbapt _hs_nmerges++; \ 507262395Sbapt _hs_q = _hs_p; \ 508262395Sbapt _hs_psize = 0; \ 509262395Sbapt for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ 510262395Sbapt _hs_psize++; \ 511262395Sbapt _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 512262395Sbapt ((void*)((char*)(_hs_q->next) + \ 513262395Sbapt (head)->hh.tbl->hho)) : NULL); \ 514262395Sbapt if (! (_hs_q) ) break; \ 515262395Sbapt } \ 516262395Sbapt _hs_qsize = _hs_insize; \ 517262395Sbapt while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ 518262395Sbapt if (_hs_psize == 0) { \ 519262395Sbapt _hs_e = _hs_q; \ 520262395Sbapt _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 521262395Sbapt ((void*)((char*)(_hs_q->next) + \ 522262395Sbapt (head)->hh.tbl->hho)) : NULL); \ 523262395Sbapt _hs_qsize--; \ 524262395Sbapt } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ 525262395Sbapt _hs_e = _hs_p; \ 526262395Sbapt if (_hs_p){ \ 527262395Sbapt _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 528262395Sbapt ((void*)((char*)(_hs_p->next) + \ 529262395Sbapt (head)->hh.tbl->hho)) : NULL); \ 530262395Sbapt } \ 531262395Sbapt _hs_psize--; \ 532262395Sbapt } else if (( \ 533262395Sbapt cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ 534262395Sbapt DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ 535262395Sbapt ) <= 0) { \ 536262395Sbapt _hs_e = _hs_p; \ 537262395Sbapt if (_hs_p){ \ 538262395Sbapt _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 539262395Sbapt ((void*)((char*)(_hs_p->next) + \ 540262395Sbapt (head)->hh.tbl->hho)) : NULL); \ 541262395Sbapt } \ 542262395Sbapt _hs_psize--; \ 543262395Sbapt } else { \ 544262395Sbapt _hs_e = _hs_q; \ 545262395Sbapt _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 546262395Sbapt ((void*)((char*)(_hs_q->next) + \ 547262395Sbapt (head)->hh.tbl->hho)) : NULL); \ 548262395Sbapt _hs_qsize--; \ 549262395Sbapt } \ 550262395Sbapt if ( _hs_tail ) { \ 551262395Sbapt _hs_tail->next = ((_hs_e) ? \ 552262395Sbapt ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ 553262395Sbapt } else { \ 554262395Sbapt _hs_list = _hs_e; \ 555262395Sbapt } \ 556262395Sbapt if (_hs_e) { \ 557262395Sbapt _hs_e->prev = ((_hs_tail) ? \ 558262395Sbapt ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ 559262395Sbapt } \ 560262395Sbapt _hs_tail = _hs_e; \ 561262395Sbapt } \ 562262395Sbapt _hs_p = _hs_q; \ 563262395Sbapt } \ 564262395Sbapt if (_hs_tail){ \ 565262395Sbapt _hs_tail->next = NULL; \ 566262395Sbapt } \ 567262395Sbapt if ( _hs_nmerges <= 1 ) { \ 568262395Sbapt _hs_looping=0; \ 569262395Sbapt (head)->hh.tbl->tail = _hs_tail; \ 570262395Sbapt DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ 571262395Sbapt } \ 572262395Sbapt _hs_insize *= 2; \ 573262395Sbapt } \ 574262395Sbapt HASH_FSCK(hh,head); \ 575262395Sbapt } \ 576262395Sbapt} while (0) 577262395Sbapt 578301339Sbapt/* This function selects items from one hash into another hash. 579301339Sbapt * The end result is that the selected items have dual presence 580301339Sbapt * in both hashes. There is no copy of the items made; rather 581301339Sbapt * they are added into the new hash through a secondary hash 582262395Sbapt * hash handle that must be present in the structure. */ 583262395Sbapt#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ 584262395Sbaptdo { \ 585262395Sbapt unsigned _src_bkt, _dst_bkt; \ 586262395Sbapt void *_last_elt=NULL, *_elt; \ 587262395Sbapt UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ 588262395Sbapt ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ 589262395Sbapt if (src) { \ 590262395Sbapt for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ 591262395Sbapt for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ 592262395Sbapt _src_hh; \ 593262395Sbapt _src_hh = _src_hh->hh_next) { \ 594262395Sbapt _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ 595262395Sbapt if (cond(_elt)) { \ 596262395Sbapt _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ 597262395Sbapt _dst_hh->key = _src_hh->key; \ 598262395Sbapt _dst_hh->keylen = _src_hh->keylen; \ 599262395Sbapt _dst_hh->hashv = _src_hh->hashv; \ 600262395Sbapt _dst_hh->prev = _last_elt; \ 601262395Sbapt _dst_hh->next = NULL; \ 602262395Sbapt if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ 603262395Sbapt if (!dst) { \ 604262395Sbapt DECLTYPE_ASSIGN(dst,_elt); \ 605262395Sbapt HASH_MAKE_TABLE(hh_dst,dst); \ 606262395Sbapt } else { \ 607262395Sbapt _dst_hh->tbl = (dst)->hh_dst.tbl; \ 608262395Sbapt } \ 609262395Sbapt HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ 610262395Sbapt HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ 611262395Sbapt (dst)->hh_dst.tbl->num_items++; \ 612262395Sbapt _last_elt = _elt; \ 613262395Sbapt _last_elt_hh = _dst_hh; \ 614262395Sbapt } \ 615262395Sbapt } \ 616262395Sbapt } \ 617262395Sbapt } \ 618262395Sbapt HASH_FSCK(hh_dst,dst); \ 619262395Sbapt} while (0) 620262395Sbapt 621262395Sbapt#define HASH_CLEAR(hh,head) \ 622262395Sbaptdo { \ 623262395Sbapt if (head) { \ 624262395Sbapt uthash_free((head)->hh.tbl->buckets, \ 625262395Sbapt (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ 626262395Sbapt HASH_BLOOM_FREE((head)->hh.tbl); \ 627262395Sbapt uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 628262395Sbapt (head)=NULL; \ 629262395Sbapt } \ 630262395Sbapt} while(0) 631262395Sbapt 632262395Sbapt#define HASH_OVERHEAD(hh,head) \ 633262395Sbapt (size_t)((((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ 634262395Sbapt ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ 635262395Sbapt (sizeof(UT_hash_table)) + \ 636262395Sbapt (HASH_BLOOM_BYTELEN))) 637262395Sbapt 638262395Sbapt#ifdef NO_DECLTYPE 639262395Sbapt#define HASH_ITER(hh,head,el,tmp) \ 640262395Sbaptfor((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ 641301339Sbapt el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) 642262395Sbapt#else 643262395Sbapt#define HASH_ITER(hh,head,el,tmp) \ 644262395Sbaptfor((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ 645262395Sbapt el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) 646262395Sbapt#endif 647262395Sbapt 648262395Sbapt/* obtain a count of items in the hash */ 649301339Sbapt#define HASH_COUNT(head) HASH_CNT(hh,head) 650262395Sbapt#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) 651262395Sbapt 652262395Sbapttypedef struct UT_hash_bucket { 653262395Sbapt struct UT_hash_handle *hh_head; 654262395Sbapt unsigned count; 655262395Sbapt 656262395Sbapt /* expand_mult is normally set to 0. In this situation, the max chain length 657262395Sbapt * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If 658301339Sbapt * the bucket's chain exceeds this length, bucket expansion is triggered). 659262395Sbapt * However, setting expand_mult to a non-zero value delays bucket expansion 660262395Sbapt * (that would be triggered by additions to this particular bucket) 661262395Sbapt * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. 662262395Sbapt * (The multiplier is simply expand_mult+1). The whole idea of this 663262395Sbapt * multiplier is to reduce bucket expansions, since they are expensive, in 664262395Sbapt * situations where we know that a particular bucket tends to be overused. 665262395Sbapt * It is better to let its chain length grow to a longer yet-still-bounded 666301339Sbapt * value, than to do an O(n) bucket expansion too often. 667262395Sbapt */ 668262395Sbapt unsigned expand_mult; 669262395Sbapt 670262395Sbapt} UT_hash_bucket; 671262395Sbapt 672262395Sbapt/* random signature used only to find hash tables in external analysis */ 673262395Sbapt#define HASH_SIGNATURE 0xa0111fe1 674262395Sbapt#define HASH_BLOOM_SIGNATURE 0xb12220f2 675262395Sbapt 676262395Sbapttypedef struct UT_hash_table { 677262395Sbapt UT_hash_bucket *buckets; 678262395Sbapt unsigned num_buckets, log2_num_buckets; 679262395Sbapt unsigned num_items; 680262395Sbapt struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ 681262395Sbapt ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ 682262395Sbapt 683262395Sbapt /* in an ideal situation (all buckets used equally), no bucket would have 684262395Sbapt * more than ceil(#items/#buckets) items. that's the ideal chain length. */ 685262395Sbapt unsigned ideal_chain_maxlen; 686262395Sbapt 687262395Sbapt /* nonideal_items is the number of items in the hash whose chain position 688262395Sbapt * exceeds the ideal chain maxlen. these items pay the penalty for an uneven 689262395Sbapt * hash distribution; reaching them in a chain traversal takes >ideal steps */ 690262395Sbapt unsigned nonideal_items; 691262395Sbapt 692301339Sbapt /* ineffective expands occur when a bucket doubling was performed, but 693262395Sbapt * afterward, more than half the items in the hash had nonideal chain 694262395Sbapt * positions. If this happens on two consecutive expansions we inhibit any 695262395Sbapt * further expansion, as it's not helping; this happens when the hash 696262395Sbapt * function isn't a good fit for the key domain. When expansion is inhibited 697262395Sbapt * the hash will still work, albeit no longer in constant time. */ 698262395Sbapt unsigned ineff_expands, noexpand; 699262395Sbapt 700262395Sbapt uint32_t signature; /* used only to find hash tables in external analysis */ 701262395Sbapt#ifdef HASH_BLOOM 702262395Sbapt uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ 703262395Sbapt uint8_t *bloom_bv; 704262395Sbapt char bloom_nbits; 705262395Sbapt#endif 706262395Sbapt 707262395Sbapt} UT_hash_table; 708262395Sbapt 709262395Sbapttypedef struct UT_hash_handle { 710262395Sbapt struct UT_hash_table *tbl; 711262395Sbapt void *prev; /* prev element in app order */ 712262395Sbapt void *next; /* next element in app order */ 713262395Sbapt struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ 714262395Sbapt struct UT_hash_handle *hh_next; /* next hh in bucket order */ 715262395Sbapt const void *key; /* ptr to enclosing struct's key */ 716262395Sbapt unsigned keylen; /* enclosing struct's key len */ 717262395Sbapt unsigned hashv; /* result of hash-fcn(key) */ 718262395Sbapt} UT_hash_handle; 719262395Sbapt 720262395Sbapt#endif /* UTHASH_H */ 721