1037b3c26Smrg/* 2037b3c26SmrgCopyright (c) 2003-2016, Troy D. Hanson http://troydhanson.github.com/uthash/ 3037b3c26SmrgAll rights reserved. 4037b3c26Smrg 5037b3c26SmrgRedistribution and use in source and binary forms, with or without 6037b3c26Smrgmodification, are permitted provided that the following conditions are met: 7037b3c26Smrg 8037b3c26Smrg * Redistributions of source code must retain the above copyright 9037b3c26Smrg notice, this list of conditions and the following disclaimer. 10037b3c26Smrg 11037b3c26SmrgTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 12037b3c26SmrgIS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 13037b3c26SmrgTO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 14037b3c26SmrgPARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 15037b3c26SmrgOR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 16037b3c26SmrgEXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 17037b3c26SmrgPROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 18037b3c26SmrgPROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 19037b3c26SmrgLIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 20037b3c26SmrgNEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 21037b3c26SmrgSOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 22037b3c26Smrg*/ 23037b3c26Smrg 24037b3c26Smrg#ifndef UTHASH_H 25037b3c26Smrg#define UTHASH_H 26037b3c26Smrg 27037b3c26Smrg#define UTHASH_VERSION 2.0.1 28037b3c26Smrg 29037b3c26Smrg#include <string.h> /* memcmp,strlen */ 30037b3c26Smrg#include <stddef.h> /* ptrdiff_t */ 31037b3c26Smrg#include <stdlib.h> /* exit() */ 32037b3c26Smrg 33037b3c26Smrg/* These macros use decltype or the earlier __typeof GNU extension. 34037b3c26Smrg As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 35037b3c26Smrg when compiling c++ source) this code uses whatever method is needed 36037b3c26Smrg or, for VS2008 where neither is available, uses casting workarounds. */ 37037b3c26Smrg#if defined(_MSC_VER) /* MS compiler */ 38037b3c26Smrg#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 39037b3c26Smrg#define DECLTYPE(x) (decltype(x)) 40037b3c26Smrg#else /* VS2008 or older (or VS2010 in C mode) */ 41037b3c26Smrg#define NO_DECLTYPE 42037b3c26Smrg#define DECLTYPE(x) 43037b3c26Smrg#endif 44037b3c26Smrg#elif defined(__BORLANDC__) || defined(__LCC__) || defined(__WATCOMC__) 45037b3c26Smrg#define NO_DECLTYPE 46037b3c26Smrg#define DECLTYPE(x) 47037b3c26Smrg#else /* GNU, Sun and other compilers */ 48037b3c26Smrg#define DECLTYPE(x) (__typeof(x)) 49037b3c26Smrg#endif 50037b3c26Smrg 51037b3c26Smrg#ifdef NO_DECLTYPE 52037b3c26Smrg#define DECLTYPE_ASSIGN(dst,src) \ 53037b3c26Smrgdo { \ 54037b3c26Smrg char **_da_dst = (char**)(&(dst)); \ 55037b3c26Smrg *_da_dst = (char*)(src); \ 56037b3c26Smrg} while (0) 57037b3c26Smrg#else 58037b3c26Smrg#define DECLTYPE_ASSIGN(dst,src) \ 59037b3c26Smrgdo { \ 60037b3c26Smrg (dst) = DECLTYPE(dst)(src); \ 61037b3c26Smrg} while (0) 62037b3c26Smrg#endif 63037b3c26Smrg 64037b3c26Smrg/* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */ 65037b3c26Smrg#if defined(_WIN32) 66037b3c26Smrg#if defined(_MSC_VER) && _MSC_VER >= 1600 67037b3c26Smrg#include <stdint.h> 68037b3c26Smrg#elif defined(__WATCOMC__) || defined(__MINGW32__) || defined(__CYGWIN__) 69037b3c26Smrg#include <stdint.h> 70037b3c26Smrg#else 71037b3c26Smrgtypedef unsigned int uint32_t; 72037b3c26Smrgtypedef unsigned char uint8_t; 73037b3c26Smrg#endif 74e5ad8bdfSchristos#elif (defined(__lint__) || defined(__GNUC__)) && !defined(__VXWORKS__) 75037b3c26Smrg#include <stdint.h> 76037b3c26Smrg#else 77037b3c26Smrgtypedef unsigned int uint32_t; 78037b3c26Smrgtypedef unsigned char uint8_t; 79037b3c26Smrg#endif 80037b3c26Smrg 81037b3c26Smrg#ifndef uthash_fatal 82037b3c26Smrg#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ 83037b3c26Smrg#endif 84037b3c26Smrg#ifndef uthash_malloc 85037b3c26Smrg#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ 86037b3c26Smrg#endif 87037b3c26Smrg#ifndef uthash_free 88037b3c26Smrg#define uthash_free(ptr,sz) free(ptr) /* free fcn */ 89037b3c26Smrg#endif 90037b3c26Smrg#ifndef uthash_strlen 91037b3c26Smrg#define uthash_strlen(s) strlen(s) 92037b3c26Smrg#endif 93037b3c26Smrg#ifndef uthash_memcmp 94037b3c26Smrg#define uthash_memcmp(a,b,n) memcmp(a,b,n) 95037b3c26Smrg#endif 96037b3c26Smrg 97037b3c26Smrg#ifndef uthash_noexpand_fyi 98037b3c26Smrg#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ 99037b3c26Smrg#endif 100037b3c26Smrg#ifndef uthash_expand_fyi 101037b3c26Smrg#define uthash_expand_fyi(tbl) /* can be defined to log expands */ 102037b3c26Smrg#endif 103037b3c26Smrg 104037b3c26Smrg/* initial number of buckets */ 105037b3c26Smrg#define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */ 106037b3c26Smrg#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */ 107037b3c26Smrg#define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */ 108037b3c26Smrg 109037b3c26Smrg/* calculate the element whose hash handle address is hhp */ 110037b3c26Smrg#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) 111037b3c26Smrg/* calculate the hash handle from element address elp */ 112037b3c26Smrg#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle *)(((char*)(elp)) + ((tbl)->hho))) 113037b3c26Smrg 114037b3c26Smrg#define HASH_VALUE(keyptr,keylen,hashv) \ 115037b3c26Smrgdo { \ 116037b3c26Smrg HASH_FCN(keyptr, keylen, hashv); \ 117037b3c26Smrg} while (0) 118037b3c26Smrg 119037b3c26Smrg#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ 120037b3c26Smrgdo { \ 121037b3c26Smrg (out) = NULL; \ 122037b3c26Smrg if (head) { \ 123037b3c26Smrg unsigned _hf_bkt; \ 124037b3c26Smrg HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ 125037b3c26Smrg if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \ 126037b3c26Smrg HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ 127037b3c26Smrg } \ 128037b3c26Smrg } \ 129037b3c26Smrg} while (0) 130037b3c26Smrg 131037b3c26Smrg#define HASH_FIND(hh,head,keyptr,keylen,out) \ 132037b3c26Smrgdo { \ 133037b3c26Smrg unsigned _hf_hashv; \ 134037b3c26Smrg HASH_VALUE(keyptr, keylen, _hf_hashv); \ 135037b3c26Smrg HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ 136037b3c26Smrg} while (0) 137037b3c26Smrg 138037b3c26Smrg#ifdef HASH_BLOOM 139037b3c26Smrg#define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM) 140037b3c26Smrg#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL) 141037b3c26Smrg#define HASH_BLOOM_MAKE(tbl) \ 142037b3c26Smrgdo { \ 143037b3c26Smrg (tbl)->bloom_nbits = HASH_BLOOM; \ 144037b3c26Smrg (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ 145037b3c26Smrg if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ 146037b3c26Smrg memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ 147037b3c26Smrg (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ 148037b3c26Smrg} while (0) 149037b3c26Smrg 150037b3c26Smrg#define HASH_BLOOM_FREE(tbl) \ 151037b3c26Smrgdo { \ 152037b3c26Smrg uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ 153037b3c26Smrg} while (0) 154037b3c26Smrg 155037b3c26Smrg#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U))) 156037b3c26Smrg#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U))) 157037b3c26Smrg 158037b3c26Smrg#define HASH_BLOOM_ADD(tbl,hashv) \ 159037b3c26Smrg HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U))) 160037b3c26Smrg 161037b3c26Smrg#define HASH_BLOOM_TEST(tbl,hashv) \ 162037b3c26Smrg HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1U))) 163037b3c26Smrg 164037b3c26Smrg#else 165037b3c26Smrg#define HASH_BLOOM_MAKE(tbl) 166037b3c26Smrg#define HASH_BLOOM_FREE(tbl) 167037b3c26Smrg#define HASH_BLOOM_ADD(tbl,hashv) 168037b3c26Smrg#define HASH_BLOOM_TEST(tbl,hashv) (1) 169037b3c26Smrg#define HASH_BLOOM_BYTELEN 0U 170037b3c26Smrg#endif 171037b3c26Smrg 172037b3c26Smrg#define HASH_MAKE_TABLE(hh,head) \ 173037b3c26Smrgdo { \ 174037b3c26Smrg (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ 175037b3c26Smrg sizeof(UT_hash_table)); \ 176037b3c26Smrg if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ 177037b3c26Smrg memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ 178037b3c26Smrg (head)->hh.tbl->tail = &((head)->hh); \ 179037b3c26Smrg (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ 180037b3c26Smrg (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ 181037b3c26Smrg (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ 182037b3c26Smrg (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ 183037b3c26Smrg HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 184037b3c26Smrg if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ 185037b3c26Smrg memset((head)->hh.tbl->buckets, 0, \ 186037b3c26Smrg HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 187037b3c26Smrg HASH_BLOOM_MAKE((head)->hh.tbl); \ 188037b3c26Smrg (head)->hh.tbl->signature = HASH_SIGNATURE; \ 189037b3c26Smrg} while (0) 190037b3c26Smrg 191037b3c26Smrg#define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \ 192037b3c26Smrgdo { \ 193037b3c26Smrg (replaced) = NULL; \ 194037b3c26Smrg HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ 195037b3c26Smrg if (replaced) { \ 196037b3c26Smrg HASH_DELETE(hh, head, replaced); \ 197037b3c26Smrg } \ 198037b3c26Smrg HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \ 199037b3c26Smrg} while (0) 200037b3c26Smrg 201037b3c26Smrg#define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \ 202037b3c26Smrgdo { \ 203037b3c26Smrg (replaced) = NULL; \ 204037b3c26Smrg HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ 205037b3c26Smrg if (replaced) { \ 206037b3c26Smrg HASH_DELETE(hh, head, replaced); \ 207037b3c26Smrg } \ 208037b3c26Smrg HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \ 209037b3c26Smrg} while (0) 210037b3c26Smrg 211037b3c26Smrg#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \ 212037b3c26Smrgdo { \ 213037b3c26Smrg unsigned _hr_hashv; \ 214037b3c26Smrg HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ 215037b3c26Smrg HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \ 216037b3c26Smrg} while (0) 217037b3c26Smrg 218037b3c26Smrg#define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn) \ 219037b3c26Smrgdo { \ 220037b3c26Smrg unsigned _hr_hashv; \ 221037b3c26Smrg HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ 222037b3c26Smrg HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \ 223037b3c26Smrg} while (0) 224037b3c26Smrg 225037b3c26Smrg#define HASH_APPEND_LIST(hh, head, add) \ 226037b3c26Smrgdo { \ 227037b3c26Smrg (add)->hh.next = NULL; \ 228037b3c26Smrg (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ 229037b3c26Smrg (head)->hh.tbl->tail->next = (add); \ 230037b3c26Smrg (head)->hh.tbl->tail = &((add)->hh); \ 231037b3c26Smrg} while (0) 232037b3c26Smrg 233037b3c26Smrg#define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \ 234037b3c26Smrgdo { \ 235037b3c26Smrg unsigned _ha_bkt; \ 236037b3c26Smrg (add)->hh.hashv = (hashval); \ 237037b3c26Smrg (add)->hh.key = (char*) (keyptr); \ 238037b3c26Smrg (add)->hh.keylen = (unsigned) (keylen_in); \ 239037b3c26Smrg if (!(head)) { \ 240037b3c26Smrg (add)->hh.next = NULL; \ 241037b3c26Smrg (add)->hh.prev = NULL; \ 242037b3c26Smrg (head) = (add); \ 243037b3c26Smrg HASH_MAKE_TABLE(hh, head); \ 244037b3c26Smrg } else { \ 245037b3c26Smrg struct UT_hash_handle *_hs_iter = &(head)->hh; \ 246037b3c26Smrg (add)->hh.tbl = (head)->hh.tbl; \ 247037b3c26Smrg do { \ 248037b3c26Smrg if (cmpfcn(DECLTYPE(head) ELMT_FROM_HH((head)->hh.tbl, _hs_iter), add) > 0) \ 249037b3c26Smrg break; \ 250037b3c26Smrg } while ((_hs_iter = _hs_iter->next)); \ 251037b3c26Smrg if (_hs_iter) { \ 252037b3c26Smrg (add)->hh.next = _hs_iter; \ 253037b3c26Smrg if (((add)->hh.prev = _hs_iter->prev)) { \ 254037b3c26Smrg HH_FROM_ELMT((head)->hh.tbl, _hs_iter->prev)->next = (add); \ 255037b3c26Smrg } else { \ 256037b3c26Smrg (head) = (add); \ 257037b3c26Smrg } \ 258037b3c26Smrg _hs_iter->prev = (add); \ 259037b3c26Smrg } else { \ 260037b3c26Smrg HASH_APPEND_LIST(hh, head, add); \ 261037b3c26Smrg } \ 262037b3c26Smrg } \ 263037b3c26Smrg (head)->hh.tbl->num_items++; \ 264037b3c26Smrg HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ 265037b3c26Smrg HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], &(add)->hh); \ 266037b3c26Smrg HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ 267037b3c26Smrg HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ 268037b3c26Smrg HASH_FSCK(hh, head); \ 269037b3c26Smrg} while (0) 270037b3c26Smrg 271037b3c26Smrg#define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn) \ 272037b3c26Smrgdo { \ 273037b3c26Smrg unsigned _hs_hashv; \ 274037b3c26Smrg HASH_VALUE(keyptr, keylen_in, _hs_hashv); \ 275037b3c26Smrg HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \ 276037b3c26Smrg} while (0) 277037b3c26Smrg 278037b3c26Smrg#define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \ 279037b3c26Smrg HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn) 280037b3c26Smrg 281037b3c26Smrg#define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn) \ 282037b3c26Smrg HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn) 283037b3c26Smrg 284037b3c26Smrg#define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \ 285037b3c26Smrgdo { \ 286037b3c26Smrg unsigned _ha_bkt; \ 287037b3c26Smrg (add)->hh.hashv = (hashval); \ 288037b3c26Smrg (add)->hh.key = (char*) (keyptr); \ 289037b3c26Smrg (add)->hh.keylen = (unsigned) (keylen_in); \ 290037b3c26Smrg if (!(head)) { \ 291037b3c26Smrg (add)->hh.next = NULL; \ 292037b3c26Smrg (add)->hh.prev = NULL; \ 293037b3c26Smrg (head) = (add); \ 294037b3c26Smrg HASH_MAKE_TABLE(hh, head); \ 295037b3c26Smrg } else { \ 296037b3c26Smrg (add)->hh.tbl = (head)->hh.tbl; \ 297037b3c26Smrg HASH_APPEND_LIST(hh, head, add); \ 298037b3c26Smrg } \ 299037b3c26Smrg (head)->hh.tbl->num_items++; \ 300037b3c26Smrg HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ 301037b3c26Smrg HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], &(add)->hh); \ 302037b3c26Smrg HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ 303037b3c26Smrg HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ 304037b3c26Smrg HASH_FSCK(hh, head); \ 305037b3c26Smrg} while (0) 306037b3c26Smrg 307037b3c26Smrg#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ 308037b3c26Smrgdo { \ 309037b3c26Smrg unsigned _ha_hashv; \ 310037b3c26Smrg HASH_VALUE(keyptr, keylen_in, _ha_hashv); \ 311037b3c26Smrg HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \ 312037b3c26Smrg} while (0) 313037b3c26Smrg 314037b3c26Smrg#define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \ 315037b3c26Smrg HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add) 316037b3c26Smrg 317037b3c26Smrg#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ 318037b3c26Smrg HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add) 319037b3c26Smrg 320037b3c26Smrg#define HASH_TO_BKT(hashv,num_bkts,bkt) \ 321037b3c26Smrgdo { \ 322037b3c26Smrg bkt = ((hashv) & ((num_bkts) - 1U)); \ 323037b3c26Smrg} while (0) 324037b3c26Smrg 325037b3c26Smrg/* delete "delptr" from the hash table. 326037b3c26Smrg * "the usual" patch-up process for the app-order doubly-linked-list. 327037b3c26Smrg * The use of _hd_hh_del below deserves special explanation. 328037b3c26Smrg * These used to be expressed using (delptr) but that led to a bug 329037b3c26Smrg * if someone used the same symbol for the head and deletee, like 330037b3c26Smrg * HASH_DELETE(hh,users,users); 331037b3c26Smrg * We want that to work, but by changing the head (users) below 332037b3c26Smrg * we were forfeiting our ability to further refer to the deletee (users) 333037b3c26Smrg * in the patch-up process. Solution: use scratch space to 334037b3c26Smrg * copy the deletee pointer, then the latter references are via that 335037b3c26Smrg * scratch pointer rather than through the repointed (users) symbol. 336037b3c26Smrg */ 337037b3c26Smrg#define HASH_DELETE(hh,head,delptr) \ 338037b3c26Smrgdo { \ 339037b3c26Smrg struct UT_hash_handle *_hd_hh_del; \ 340037b3c26Smrg if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ 341037b3c26Smrg uthash_free((head)->hh.tbl->buckets, \ 342037b3c26Smrg (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 343037b3c26Smrg HASH_BLOOM_FREE((head)->hh.tbl); \ 344037b3c26Smrg uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 345037b3c26Smrg head = NULL; \ 346037b3c26Smrg } else { \ 347037b3c26Smrg unsigned _hd_bkt; \ 348037b3c26Smrg _hd_hh_del = &((delptr)->hh); \ 349037b3c26Smrg if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ 350037b3c26Smrg (head)->hh.tbl->tail = \ 351037b3c26Smrg (UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ 352037b3c26Smrg (head)->hh.tbl->hho); \ 353037b3c26Smrg } \ 354037b3c26Smrg if ((delptr)->hh.prev != NULL) { \ 355037b3c26Smrg ((UT_hash_handle*)((ptrdiff_t)((delptr)->hh.prev) + \ 356037b3c26Smrg (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ 357037b3c26Smrg } else { \ 358037b3c26Smrg DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ 359037b3c26Smrg } \ 360037b3c26Smrg if (_hd_hh_del->next != NULL) { \ 361037b3c26Smrg ((UT_hash_handle*)((ptrdiff_t)_hd_hh_del->next + \ 362037b3c26Smrg (head)->hh.tbl->hho))->prev = \ 363037b3c26Smrg _hd_hh_del->prev; \ 364037b3c26Smrg } \ 365037b3c26Smrg HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ 366037b3c26Smrg HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ 367037b3c26Smrg (head)->hh.tbl->num_items--; \ 368037b3c26Smrg } \ 369037b3c26Smrg HASH_FSCK(hh,head); \ 370037b3c26Smrg} while (0) 371037b3c26Smrg 372037b3c26Smrg 373037b3c26Smrg/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ 374037b3c26Smrg#define HASH_FIND_STR(head,findstr,out) \ 375037b3c26Smrg HASH_FIND(hh,head,findstr,(unsigned)uthash_strlen(findstr),out) 376037b3c26Smrg#define HASH_ADD_STR(head,strfield,add) \ 377037b3c26Smrg HASH_ADD(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add) 378037b3c26Smrg#define HASH_REPLACE_STR(head,strfield,add,replaced) \ 379037b3c26Smrg HASH_REPLACE(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add,replaced) 380037b3c26Smrg#define HASH_FIND_INT(head,findint,out) \ 381037b3c26Smrg HASH_FIND(hh,head,findint,sizeof(int),out) 382037b3c26Smrg#define HASH_ADD_INT(head,intfield,add) \ 383037b3c26Smrg HASH_ADD(hh,head,intfield,sizeof(int),add) 384037b3c26Smrg#define HASH_REPLACE_INT(head,intfield,add,replaced) \ 385037b3c26Smrg HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced) 386037b3c26Smrg#define HASH_FIND_PTR(head,findptr,out) \ 387037b3c26Smrg HASH_FIND(hh,head,findptr,sizeof(void *),out) 388037b3c26Smrg#define HASH_ADD_PTR(head,ptrfield,add) \ 389037b3c26Smrg HASH_ADD(hh,head,ptrfield,sizeof(void *),add) 390037b3c26Smrg#define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \ 391037b3c26Smrg HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced) 392037b3c26Smrg#define HASH_DEL(head,delptr) \ 393037b3c26Smrg HASH_DELETE(hh,head,delptr) 394037b3c26Smrg 395037b3c26Smrg/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. 396037b3c26Smrg * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. 397037b3c26Smrg */ 398037b3c26Smrg#ifdef HASH_DEBUG 399037b3c26Smrg#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) 400037b3c26Smrg#define HASH_FSCK(hh,head) \ 401037b3c26Smrgdo { \ 402037b3c26Smrg struct UT_hash_handle *_thh; \ 403037b3c26Smrg if (head) { \ 404037b3c26Smrg unsigned _bkt_i; \ 405037b3c26Smrg unsigned _count; \ 406037b3c26Smrg char *_prev; \ 407037b3c26Smrg _count = 0; \ 408037b3c26Smrg for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ 409037b3c26Smrg unsigned _bkt_count = 0; \ 410037b3c26Smrg _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ 411037b3c26Smrg _prev = NULL; \ 412037b3c26Smrg while (_thh) { \ 413037b3c26Smrg if (_prev != (char*)(_thh->hh_prev)) { \ 414037b3c26Smrg HASH_OOPS("invalid hh_prev %p, actual %p\n", \ 415037b3c26Smrg _thh->hh_prev, _prev ); \ 416037b3c26Smrg } \ 417037b3c26Smrg _bkt_count++; \ 418037b3c26Smrg _prev = (char*)(_thh); \ 419037b3c26Smrg _thh = _thh->hh_next; \ 420037b3c26Smrg } \ 421037b3c26Smrg _count += _bkt_count; \ 422037b3c26Smrg if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ 423037b3c26Smrg HASH_OOPS("invalid bucket count %u, actual %u\n", \ 424037b3c26Smrg (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ 425037b3c26Smrg } \ 426037b3c26Smrg } \ 427037b3c26Smrg if (_count != (head)->hh.tbl->num_items) { \ 428037b3c26Smrg HASH_OOPS("invalid hh item count %u, actual %u\n", \ 429037b3c26Smrg (head)->hh.tbl->num_items, _count ); \ 430037b3c26Smrg } \ 431037b3c26Smrg /* traverse hh in app order; check next/prev integrity, count */ \ 432037b3c26Smrg _count = 0; \ 433037b3c26Smrg _prev = NULL; \ 434037b3c26Smrg _thh = &(head)->hh; \ 435037b3c26Smrg while (_thh) { \ 436037b3c26Smrg _count++; \ 437037b3c26Smrg if (_prev !=(char*)(_thh->prev)) { \ 438037b3c26Smrg HASH_OOPS("invalid prev %p, actual %p\n", \ 439037b3c26Smrg _thh->prev, _prev ); \ 440037b3c26Smrg } \ 441037b3c26Smrg _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ 442037b3c26Smrg _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ 443037b3c26Smrg (head)->hh.tbl->hho) : NULL ); \ 444037b3c26Smrg } \ 445037b3c26Smrg if (_count != (head)->hh.tbl->num_items) { \ 446037b3c26Smrg HASH_OOPS("invalid app item count %u, actual %u\n", \ 447037b3c26Smrg (head)->hh.tbl->num_items, _count ); \ 448037b3c26Smrg } \ 449037b3c26Smrg } \ 450037b3c26Smrg} while (0) 451037b3c26Smrg#else 452037b3c26Smrg#define HASH_FSCK(hh,head) 453037b3c26Smrg#endif 454037b3c26Smrg 455037b3c26Smrg/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to 456037b3c26Smrg * the descriptor to which this macro is defined for tuning the hash function. 457037b3c26Smrg * The app can #include <unistd.h> to get the prototype for write(2). */ 458037b3c26Smrg#ifdef HASH_EMIT_KEYS 459037b3c26Smrg#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ 460037b3c26Smrgdo { \ 461037b3c26Smrg unsigned _klen = fieldlen; \ 462037b3c26Smrg write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ 463037b3c26Smrg write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \ 464037b3c26Smrg} while (0) 465037b3c26Smrg#else 466037b3c26Smrg#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) 467037b3c26Smrg#endif 468037b3c26Smrg 469037b3c26Smrg/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ 470037b3c26Smrg#ifdef HASH_FUNCTION 471037b3c26Smrg#define HASH_FCN HASH_FUNCTION 472037b3c26Smrg#else 473037b3c26Smrg#define HASH_FCN HASH_JEN 474037b3c26Smrg#endif 475037b3c26Smrg 476037b3c26Smrg/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */ 477037b3c26Smrg#define HASH_BER(key,keylen,hashv) \ 478037b3c26Smrgdo { \ 479037b3c26Smrg unsigned _hb_keylen=(unsigned)keylen; \ 480037b3c26Smrg const unsigned char *_hb_key=(const unsigned char*)(key); \ 481037b3c26Smrg (hashv) = 0; \ 482037b3c26Smrg while (_hb_keylen-- != 0U) { \ 483037b3c26Smrg (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \ 484037b3c26Smrg } \ 485037b3c26Smrg} while (0) 486037b3c26Smrg 487037b3c26Smrg 488037b3c26Smrg/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at 489037b3c26Smrg * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ 490037b3c26Smrg#define HASH_SAX(key,keylen,hashv) \ 491037b3c26Smrgdo { \ 492037b3c26Smrg unsigned _sx_i; \ 493037b3c26Smrg const unsigned char *_hs_key=(const unsigned char*)(key); \ 494037b3c26Smrg hashv = 0; \ 495037b3c26Smrg for(_sx_i=0; _sx_i < keylen; _sx_i++) { \ 496037b3c26Smrg hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ 497037b3c26Smrg } \ 498037b3c26Smrg} while (0) 499037b3c26Smrg/* FNV-1a variation */ 500037b3c26Smrg#define HASH_FNV(key,keylen,hashv) \ 501037b3c26Smrgdo { \ 502037b3c26Smrg unsigned _fn_i; \ 503037b3c26Smrg const unsigned char *_hf_key=(const unsigned char*)(key); \ 504037b3c26Smrg hashv = 2166136261U; \ 505037b3c26Smrg for(_fn_i=0; _fn_i < keylen; _fn_i++) { \ 506037b3c26Smrg hashv = hashv ^ _hf_key[_fn_i]; \ 507037b3c26Smrg hashv = hashv * 16777619U; \ 508037b3c26Smrg } \ 509037b3c26Smrg} while (0) 510037b3c26Smrg 511037b3c26Smrg#define HASH_OAT(key,keylen,hashv) \ 512037b3c26Smrgdo { \ 513037b3c26Smrg unsigned _ho_i; \ 514037b3c26Smrg const unsigned char *_ho_key=(const unsigned char*)(key); \ 515037b3c26Smrg hashv = 0; \ 516037b3c26Smrg for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ 517037b3c26Smrg hashv += _ho_key[_ho_i]; \ 518037b3c26Smrg hashv += (hashv << 10); \ 519037b3c26Smrg hashv ^= (hashv >> 6); \ 520037b3c26Smrg } \ 521037b3c26Smrg hashv += (hashv << 3); \ 522037b3c26Smrg hashv ^= (hashv >> 11); \ 523037b3c26Smrg hashv += (hashv << 15); \ 524037b3c26Smrg} while (0) 525037b3c26Smrg 526037b3c26Smrg#define HASH_JEN_MIX(a,b,c) \ 527037b3c26Smrgdo { \ 528037b3c26Smrg a -= b; a -= c; a ^= ( c >> 13 ); \ 529037b3c26Smrg b -= c; b -= a; b ^= ( a << 8 ); \ 530037b3c26Smrg c -= a; c -= b; c ^= ( b >> 13 ); \ 531037b3c26Smrg a -= b; a -= c; a ^= ( c >> 12 ); \ 532037b3c26Smrg b -= c; b -= a; b ^= ( a << 16 ); \ 533037b3c26Smrg c -= a; c -= b; c ^= ( b >> 5 ); \ 534037b3c26Smrg a -= b; a -= c; a ^= ( c >> 3 ); \ 535037b3c26Smrg b -= c; b -= a; b ^= ( a << 10 ); \ 536037b3c26Smrg c -= a; c -= b; c ^= ( b >> 15 ); \ 537037b3c26Smrg} while (0) 538037b3c26Smrg 539037b3c26Smrg#define HASH_JEN(key,keylen,hashv) \ 540037b3c26Smrgdo { \ 541037b3c26Smrg unsigned _hj_i,_hj_j,_hj_k; \ 542037b3c26Smrg unsigned const char *_hj_key=(unsigned const char*)(key); \ 543037b3c26Smrg hashv = 0xfeedbeefu; \ 544037b3c26Smrg _hj_i = _hj_j = 0x9e3779b9u; \ 545037b3c26Smrg _hj_k = (unsigned)(keylen); \ 546037b3c26Smrg while (_hj_k >= 12U) { \ 547037b3c26Smrg _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ 548037b3c26Smrg + ( (unsigned)_hj_key[2] << 16 ) \ 549037b3c26Smrg + ( (unsigned)_hj_key[3] << 24 ) ); \ 550037b3c26Smrg _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ 551037b3c26Smrg + ( (unsigned)_hj_key[6] << 16 ) \ 552037b3c26Smrg + ( (unsigned)_hj_key[7] << 24 ) ); \ 553037b3c26Smrg hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ 554037b3c26Smrg + ( (unsigned)_hj_key[10] << 16 ) \ 555037b3c26Smrg + ( (unsigned)_hj_key[11] << 24 ) ); \ 556037b3c26Smrg \ 557037b3c26Smrg HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 558037b3c26Smrg \ 559037b3c26Smrg _hj_key += 12; \ 560037b3c26Smrg _hj_k -= 12U; \ 561037b3c26Smrg } \ 562037b3c26Smrg hashv += (unsigned)(keylen); \ 563037b3c26Smrg switch ( _hj_k ) { \ 564037b3c26Smrg case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \ 565037b3c26Smrg case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \ 566037b3c26Smrg case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \ 567037b3c26Smrg case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \ 568037b3c26Smrg case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \ 569037b3c26Smrg case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \ 570037b3c26Smrg case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \ 571037b3c26Smrg case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \ 572037b3c26Smrg case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \ 573037b3c26Smrg case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \ 574037b3c26Smrg case 1: _hj_i += _hj_key[0]; \ 575037b3c26Smrg } \ 576037b3c26Smrg HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 577037b3c26Smrg} while (0) 578037b3c26Smrg 579037b3c26Smrg/* The Paul Hsieh hash function */ 580037b3c26Smrg#undef get16bits 581037b3c26Smrg#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 582037b3c26Smrg || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 583037b3c26Smrg#define get16bits(d) (*((const uint16_t *) (d))) 584037b3c26Smrg#endif 585037b3c26Smrg 586037b3c26Smrg#if !defined (get16bits) 587037b3c26Smrg#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ 588037b3c26Smrg +(uint32_t)(((const uint8_t *)(d))[0]) ) 589037b3c26Smrg#endif 590037b3c26Smrg#define HASH_SFH(key,keylen,hashv) \ 591037b3c26Smrgdo { \ 592037b3c26Smrg unsigned const char *_sfh_key=(unsigned const char*)(key); \ 593037b3c26Smrg uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \ 594037b3c26Smrg \ 595037b3c26Smrg unsigned _sfh_rem = _sfh_len & 3U; \ 596037b3c26Smrg _sfh_len >>= 2; \ 597037b3c26Smrg hashv = 0xcafebabeu; \ 598037b3c26Smrg \ 599037b3c26Smrg /* Main loop */ \ 600037b3c26Smrg for (;_sfh_len > 0U; _sfh_len--) { \ 601037b3c26Smrg hashv += get16bits (_sfh_key); \ 602037b3c26Smrg _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \ 603037b3c26Smrg hashv = (hashv << 16) ^ _sfh_tmp; \ 604037b3c26Smrg _sfh_key += 2U*sizeof (uint16_t); \ 605037b3c26Smrg hashv += hashv >> 11; \ 606037b3c26Smrg } \ 607037b3c26Smrg \ 608037b3c26Smrg /* Handle end cases */ \ 609037b3c26Smrg switch (_sfh_rem) { \ 610037b3c26Smrg case 3: hashv += get16bits (_sfh_key); \ 611037b3c26Smrg hashv ^= hashv << 16; \ 612037b3c26Smrg hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \ 613037b3c26Smrg hashv += hashv >> 11; \ 614037b3c26Smrg break; \ 615037b3c26Smrg case 2: hashv += get16bits (_sfh_key); \ 616037b3c26Smrg hashv ^= hashv << 11; \ 617037b3c26Smrg hashv += hashv >> 17; \ 618037b3c26Smrg break; \ 619037b3c26Smrg case 1: hashv += *_sfh_key; \ 620037b3c26Smrg hashv ^= hashv << 10; \ 621037b3c26Smrg hashv += hashv >> 1; \ 622037b3c26Smrg } \ 623037b3c26Smrg \ 624037b3c26Smrg /* Force "avalanching" of final 127 bits */ \ 625037b3c26Smrg hashv ^= hashv << 3; \ 626037b3c26Smrg hashv += hashv >> 5; \ 627037b3c26Smrg hashv ^= hashv << 4; \ 628037b3c26Smrg hashv += hashv >> 17; \ 629037b3c26Smrg hashv ^= hashv << 25; \ 630037b3c26Smrg hashv += hashv >> 6; \ 631037b3c26Smrg} while (0) 632037b3c26Smrg 633037b3c26Smrg#ifdef HASH_USING_NO_STRICT_ALIASING 634037b3c26Smrg/* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. 635037b3c26Smrg * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. 636037b3c26Smrg * MurmurHash uses the faster approach only on CPU's where we know it's safe. 637037b3c26Smrg * 638037b3c26Smrg * Note the preprocessor built-in defines can be emitted using: 639037b3c26Smrg * 640037b3c26Smrg * gcc -m64 -dM -E - < /dev/null (on gcc) 641037b3c26Smrg * cc -## a.c (where a.c is a simple test file) (Sun Studio) 642037b3c26Smrg */ 643037b3c26Smrg#if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) 644037b3c26Smrg#define MUR_GETBLOCK(p,i) p[i] 645037b3c26Smrg#else /* non intel */ 646037b3c26Smrg#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL) 647037b3c26Smrg#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL) 648037b3c26Smrg#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL) 649037b3c26Smrg#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL) 650037b3c26Smrg#define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) 65148246ce7Smrg#ifdef HAVE_BIG_ENDIAN 652037b3c26Smrg#define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) 653037b3c26Smrg#define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16)) 654037b3c26Smrg#define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8)) 65548246ce7Smrg#else /* little endian non-intel */ 656037b3c26Smrg#define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24)) 657037b3c26Smrg#define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16)) 658037b3c26Smrg#define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8)) 659037b3c26Smrg#endif 660037b3c26Smrg#define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \ 661037b3c26Smrg (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \ 662037b3c26Smrg (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \ 663037b3c26Smrg MUR_ONE_THREE(p)))) 664037b3c26Smrg#endif 665037b3c26Smrg#define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) 666037b3c26Smrg#define MUR_FMIX(_h) \ 667037b3c26Smrgdo { \ 668037b3c26Smrg _h ^= _h >> 16; \ 669037b3c26Smrg _h *= 0x85ebca6bu; \ 670037b3c26Smrg _h ^= _h >> 13; \ 671037b3c26Smrg _h *= 0xc2b2ae35u; \ 672037b3c26Smrg _h ^= _h >> 16; \ 673037b3c26Smrg} while (0) 674037b3c26Smrg 675037b3c26Smrg#define HASH_MUR(key,keylen,hashv) \ 676037b3c26Smrgdo { \ 677037b3c26Smrg const uint8_t *_mur_data = (const uint8_t*)(key); \ 678037b3c26Smrg const int _mur_nblocks = (int)(keylen) / 4; \ 679037b3c26Smrg uint32_t _mur_h1 = 0xf88D5353u; \ 680037b3c26Smrg uint32_t _mur_c1 = 0xcc9e2d51u; \ 681037b3c26Smrg uint32_t _mur_c2 = 0x1b873593u; \ 682037b3c26Smrg uint32_t _mur_k1 = 0; \ 683037b3c26Smrg const uint8_t *_mur_tail; \ 684037b3c26Smrg const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \ 685037b3c26Smrg int _mur_i; \ 686037b3c26Smrg for(_mur_i = -_mur_nblocks; _mur_i!=0; _mur_i++) { \ 687037b3c26Smrg _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ 688037b3c26Smrg _mur_k1 *= _mur_c1; \ 689037b3c26Smrg _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 690037b3c26Smrg _mur_k1 *= _mur_c2; \ 691037b3c26Smrg \ 692037b3c26Smrg _mur_h1 ^= _mur_k1; \ 693037b3c26Smrg _mur_h1 = MUR_ROTL32(_mur_h1,13); \ 694037b3c26Smrg _mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \ 695037b3c26Smrg } \ 696037b3c26Smrg _mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \ 697037b3c26Smrg _mur_k1=0; \ 698037b3c26Smrg switch((keylen) & 3U) { \ 699037b3c26Smrg case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16; /* FALLTHROUGH */ \ 700037b3c26Smrg case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8; /* FALLTHROUGH */ \ 701037b3c26Smrg case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \ 702037b3c26Smrg _mur_k1 *= _mur_c1; \ 703037b3c26Smrg _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 704037b3c26Smrg _mur_k1 *= _mur_c2; \ 705037b3c26Smrg _mur_h1 ^= _mur_k1; \ 706037b3c26Smrg } \ 707037b3c26Smrg _mur_h1 ^= (uint32_t)(keylen); \ 708037b3c26Smrg MUR_FMIX(_mur_h1); \ 709037b3c26Smrg hashv = _mur_h1; \ 710037b3c26Smrg} while (0) 711037b3c26Smrg#endif /* HASH_USING_NO_STRICT_ALIASING */ 712037b3c26Smrg 713037b3c26Smrg/* iterate over items in a known bucket to find desired item */ 714037b3c26Smrg#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \ 715037b3c26Smrgdo { \ 716037b3c26Smrg if ((head).hh_head != NULL) { \ 717037b3c26Smrg DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \ 718037b3c26Smrg } else { \ 719037b3c26Smrg (out) = NULL; \ 720037b3c26Smrg } \ 721037b3c26Smrg while ((out) != NULL) { \ 722037b3c26Smrg if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \ 723037b3c26Smrg if (uthash_memcmp((out)->hh.key, keyptr, keylen_in) == 0) { \ 724037b3c26Smrg break; \ 725037b3c26Smrg } \ 726037b3c26Smrg } \ 727037b3c26Smrg if ((out)->hh.hh_next != NULL) { \ 728037b3c26Smrg DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \ 729037b3c26Smrg } else { \ 730037b3c26Smrg (out) = NULL; \ 731037b3c26Smrg } \ 732037b3c26Smrg } \ 733037b3c26Smrg} while (0) 734037b3c26Smrg 735037b3c26Smrg/* add an item to a bucket */ 736037b3c26Smrg#define HASH_ADD_TO_BKT(head,addhh) \ 737037b3c26Smrgdo { \ 738037b3c26Smrg head.count++; \ 739037b3c26Smrg (addhh)->hh_next = head.hh_head; \ 740037b3c26Smrg (addhh)->hh_prev = NULL; \ 741037b3c26Smrg if (head.hh_head != NULL) { (head).hh_head->hh_prev = (addhh); } \ 742037b3c26Smrg (head).hh_head=addhh; \ 743037b3c26Smrg if ((head.count >= ((head.expand_mult+1U) * HASH_BKT_CAPACITY_THRESH)) \ 744037b3c26Smrg && ((addhh)->tbl->noexpand != 1U)) { \ 745037b3c26Smrg HASH_EXPAND_BUCKETS((addhh)->tbl); \ 746037b3c26Smrg } \ 747037b3c26Smrg} while (0) 748037b3c26Smrg 749037b3c26Smrg/* remove an item from a given bucket */ 750037b3c26Smrg#define HASH_DEL_IN_BKT(hh,head,hh_del) \ 751037b3c26Smrg (head).count--; \ 752037b3c26Smrg if ((head).hh_head == hh_del) { \ 753037b3c26Smrg (head).hh_head = hh_del->hh_next; \ 754037b3c26Smrg } \ 755037b3c26Smrg if (hh_del->hh_prev) { \ 756037b3c26Smrg hh_del->hh_prev->hh_next = hh_del->hh_next; \ 757037b3c26Smrg } \ 758037b3c26Smrg if (hh_del->hh_next) { \ 759037b3c26Smrg hh_del->hh_next->hh_prev = hh_del->hh_prev; \ 760037b3c26Smrg } 761037b3c26Smrg 762037b3c26Smrg/* Bucket expansion has the effect of doubling the number of buckets 763037b3c26Smrg * and redistributing the items into the new buckets. Ideally the 764037b3c26Smrg * items will distribute more or less evenly into the new buckets 765037b3c26Smrg * (the extent to which this is true is a measure of the quality of 766037b3c26Smrg * the hash function as it applies to the key domain). 767037b3c26Smrg * 768037b3c26Smrg * With the items distributed into more buckets, the chain length 769037b3c26Smrg * (item count) in each bucket is reduced. Thus by expanding buckets 770037b3c26Smrg * the hash keeps a bound on the chain length. This bounded chain 771037b3c26Smrg * length is the essence of how a hash provides constant time lookup. 772037b3c26Smrg * 773037b3c26Smrg * The calculation of tbl->ideal_chain_maxlen below deserves some 774037b3c26Smrg * explanation. First, keep in mind that we're calculating the ideal 775037b3c26Smrg * maximum chain length based on the *new* (doubled) bucket count. 776037b3c26Smrg * In fractions this is just n/b (n=number of items,b=new num buckets). 777037b3c26Smrg * Since the ideal chain length is an integer, we want to calculate 778037b3c26Smrg * ceil(n/b). We don't depend on floating point arithmetic in this 779037b3c26Smrg * hash, so to calculate ceil(n/b) with integers we could write 780037b3c26Smrg * 781037b3c26Smrg * ceil(n/b) = (n/b) + ((n%b)?1:0) 782037b3c26Smrg * 783037b3c26Smrg * and in fact a previous version of this hash did just that. 784037b3c26Smrg * But now we have improved things a bit by recognizing that b is 785037b3c26Smrg * always a power of two. We keep its base 2 log handy (call it lb), 786037b3c26Smrg * so now we can write this with a bit shift and logical AND: 787037b3c26Smrg * 788037b3c26Smrg * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) 789037b3c26Smrg * 790037b3c26Smrg */ 791037b3c26Smrg#define HASH_EXPAND_BUCKETS(tbl) \ 792037b3c26Smrgdo { \ 793037b3c26Smrg unsigned _he_bkt; \ 794037b3c26Smrg unsigned _he_bkt_i; \ 795037b3c26Smrg struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ 796037b3c26Smrg UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ 797037b3c26Smrg _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ 798037b3c26Smrg 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 799037b3c26Smrg if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ 800037b3c26Smrg memset(_he_new_buckets, 0, \ 801037b3c26Smrg 2UL * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 802037b3c26Smrg tbl->ideal_chain_maxlen = \ 803037b3c26Smrg (tbl->num_items >> (tbl->log2_num_buckets+1U)) + \ 804037b3c26Smrg (((tbl->num_items & ((tbl->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \ 805037b3c26Smrg tbl->nonideal_items = 0; \ 806037b3c26Smrg for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ 807037b3c26Smrg { \ 808037b3c26Smrg _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ 809037b3c26Smrg while (_he_thh != NULL) { \ 810037b3c26Smrg _he_hh_nxt = _he_thh->hh_next; \ 811037b3c26Smrg HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2U, _he_bkt); \ 812037b3c26Smrg _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ 813037b3c26Smrg if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ 814037b3c26Smrg tbl->nonideal_items++; \ 815037b3c26Smrg _he_newbkt->expand_mult = _he_newbkt->count / \ 816037b3c26Smrg tbl->ideal_chain_maxlen; \ 817037b3c26Smrg } \ 818037b3c26Smrg _he_thh->hh_prev = NULL; \ 819037b3c26Smrg _he_thh->hh_next = _he_newbkt->hh_head; \ 820037b3c26Smrg if (_he_newbkt->hh_head != NULL) { _he_newbkt->hh_head->hh_prev = \ 821037b3c26Smrg _he_thh; } \ 822037b3c26Smrg _he_newbkt->hh_head = _he_thh; \ 823037b3c26Smrg _he_thh = _he_hh_nxt; \ 824037b3c26Smrg } \ 825037b3c26Smrg } \ 826037b3c26Smrg uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 827037b3c26Smrg tbl->num_buckets *= 2U; \ 828037b3c26Smrg tbl->log2_num_buckets++; \ 829037b3c26Smrg tbl->buckets = _he_new_buckets; \ 830037b3c26Smrg tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ 831037b3c26Smrg (tbl->ineff_expands+1U) : 0U; \ 832037b3c26Smrg if (tbl->ineff_expands > 1U) { \ 833037b3c26Smrg tbl->noexpand=1; \ 834037b3c26Smrg uthash_noexpand_fyi(tbl); \ 835037b3c26Smrg } \ 836037b3c26Smrg uthash_expand_fyi(tbl); \ 837037b3c26Smrg} while (0) 838037b3c26Smrg 839037b3c26Smrg 840037b3c26Smrg/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ 841037b3c26Smrg/* Note that HASH_SORT assumes the hash handle name to be hh. 842037b3c26Smrg * HASH_SRT was added to allow the hash handle name to be passed in. */ 843037b3c26Smrg#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) 844037b3c26Smrg#define HASH_SRT(hh,head,cmpfcn) \ 845037b3c26Smrgdo { \ 846037b3c26Smrg unsigned _hs_i; \ 847037b3c26Smrg unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ 848037b3c26Smrg struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ 849037b3c26Smrg if (head != NULL) { \ 850037b3c26Smrg _hs_insize = 1; \ 851037b3c26Smrg _hs_looping = 1; \ 852037b3c26Smrg _hs_list = &((head)->hh); \ 853037b3c26Smrg while (_hs_looping != 0U) { \ 854037b3c26Smrg _hs_p = _hs_list; \ 855037b3c26Smrg _hs_list = NULL; \ 856037b3c26Smrg _hs_tail = NULL; \ 857037b3c26Smrg _hs_nmerges = 0; \ 858037b3c26Smrg while (_hs_p != NULL) { \ 859037b3c26Smrg _hs_nmerges++; \ 860037b3c26Smrg _hs_q = _hs_p; \ 861037b3c26Smrg _hs_psize = 0; \ 862037b3c26Smrg for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ 863037b3c26Smrg _hs_psize++; \ 864037b3c26Smrg _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ 865037b3c26Smrg ((void*)((char*)(_hs_q->next) + \ 866037b3c26Smrg (head)->hh.tbl->hho)) : NULL); \ 867037b3c26Smrg if (! (_hs_q) ) { break; } \ 868037b3c26Smrg } \ 869037b3c26Smrg _hs_qsize = _hs_insize; \ 870037b3c26Smrg while ((_hs_psize > 0U) || ((_hs_qsize > 0U) && (_hs_q != NULL))) {\ 871037b3c26Smrg if (_hs_psize == 0U) { \ 872037b3c26Smrg _hs_e = _hs_q; \ 873037b3c26Smrg _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ 874037b3c26Smrg ((void*)((char*)(_hs_q->next) + \ 875037b3c26Smrg (head)->hh.tbl->hho)) : NULL); \ 876037b3c26Smrg _hs_qsize--; \ 877037b3c26Smrg } else if ( (_hs_qsize == 0U) || (_hs_q == NULL) ) { \ 878037b3c26Smrg _hs_e = _hs_p; \ 879037b3c26Smrg if (_hs_p != NULL){ \ 880037b3c26Smrg _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \ 881037b3c26Smrg ((void*)((char*)(_hs_p->next) + \ 882037b3c26Smrg (head)->hh.tbl->hho)) : NULL); \ 883037b3c26Smrg } \ 884037b3c26Smrg _hs_psize--; \ 885037b3c26Smrg } else if (( \ 886037b3c26Smrg cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ 887037b3c26Smrg DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ 888037b3c26Smrg ) <= 0) { \ 889037b3c26Smrg _hs_e = _hs_p; \ 890037b3c26Smrg if (_hs_p != NULL){ \ 891037b3c26Smrg _hs_p = (UT_hash_handle*)((_hs_p->next != NULL) ? \ 892037b3c26Smrg ((void*)((char*)(_hs_p->next) + \ 893037b3c26Smrg (head)->hh.tbl->hho)) : NULL); \ 894037b3c26Smrg } \ 895037b3c26Smrg _hs_psize--; \ 896037b3c26Smrg } else { \ 897037b3c26Smrg _hs_e = _hs_q; \ 898037b3c26Smrg _hs_q = (UT_hash_handle*)((_hs_q->next != NULL) ? \ 899037b3c26Smrg ((void*)((char*)(_hs_q->next) + \ 900037b3c26Smrg (head)->hh.tbl->hho)) : NULL); \ 901037b3c26Smrg _hs_qsize--; \ 902037b3c26Smrg } \ 903037b3c26Smrg if ( _hs_tail != NULL ) { \ 904037b3c26Smrg _hs_tail->next = ((_hs_e != NULL) ? \ 905037b3c26Smrg ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ 906037b3c26Smrg } else { \ 907037b3c26Smrg _hs_list = _hs_e; \ 908037b3c26Smrg } \ 909037b3c26Smrg if (_hs_e != NULL) { \ 910037b3c26Smrg _hs_e->prev = ((_hs_tail != NULL) ? \ 911037b3c26Smrg ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ 912037b3c26Smrg } \ 913037b3c26Smrg _hs_tail = _hs_e; \ 914037b3c26Smrg } \ 915037b3c26Smrg _hs_p = _hs_q; \ 916037b3c26Smrg } \ 917037b3c26Smrg if (_hs_tail != NULL){ \ 918037b3c26Smrg _hs_tail->next = NULL; \ 919037b3c26Smrg } \ 920037b3c26Smrg if ( _hs_nmerges <= 1U ) { \ 921037b3c26Smrg _hs_looping=0; \ 922037b3c26Smrg (head)->hh.tbl->tail = _hs_tail; \ 923037b3c26Smrg DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ 924037b3c26Smrg } \ 925037b3c26Smrg _hs_insize *= 2U; \ 926037b3c26Smrg } \ 927037b3c26Smrg HASH_FSCK(hh,head); \ 928037b3c26Smrg } \ 929037b3c26Smrg} while (0) 930037b3c26Smrg 931037b3c26Smrg/* This function selects items from one hash into another hash. 932037b3c26Smrg * The end result is that the selected items have dual presence 933037b3c26Smrg * in both hashes. There is no copy of the items made; rather 934037b3c26Smrg * they are added into the new hash through a secondary hash 935037b3c26Smrg * hash handle that must be present in the structure. */ 936037b3c26Smrg#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ 937037b3c26Smrgdo { \ 938037b3c26Smrg unsigned _src_bkt, _dst_bkt; \ 939037b3c26Smrg void *_last_elt=NULL, *_elt; \ 940037b3c26Smrg UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ 941037b3c26Smrg ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ 942037b3c26Smrg if (src != NULL) { \ 943037b3c26Smrg for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ 944037b3c26Smrg for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ 945037b3c26Smrg _src_hh != NULL; \ 946037b3c26Smrg _src_hh = _src_hh->hh_next) { \ 947037b3c26Smrg _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ 948037b3c26Smrg if (cond(_elt)) { \ 949037b3c26Smrg _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ 950037b3c26Smrg _dst_hh->key = _src_hh->key; \ 951037b3c26Smrg _dst_hh->keylen = _src_hh->keylen; \ 952037b3c26Smrg _dst_hh->hashv = _src_hh->hashv; \ 953037b3c26Smrg _dst_hh->prev = _last_elt; \ 954037b3c26Smrg _dst_hh->next = NULL; \ 955037b3c26Smrg if (_last_elt_hh != NULL) { _last_elt_hh->next = _elt; } \ 956037b3c26Smrg if (dst == NULL) { \ 957037b3c26Smrg DECLTYPE_ASSIGN(dst,_elt); \ 958037b3c26Smrg HASH_MAKE_TABLE(hh_dst,dst); \ 959037b3c26Smrg } else { \ 960037b3c26Smrg _dst_hh->tbl = (dst)->hh_dst.tbl; \ 961037b3c26Smrg } \ 962037b3c26Smrg HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ 963037b3c26Smrg HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ 964037b3c26Smrg (dst)->hh_dst.tbl->num_items++; \ 965037b3c26Smrg _last_elt = _elt; \ 966037b3c26Smrg _last_elt_hh = _dst_hh; \ 967037b3c26Smrg } \ 968037b3c26Smrg } \ 969037b3c26Smrg } \ 970037b3c26Smrg } \ 971037b3c26Smrg HASH_FSCK(hh_dst,dst); \ 972037b3c26Smrg} while (0) 973037b3c26Smrg 974037b3c26Smrg#define HASH_CLEAR(hh,head) \ 975037b3c26Smrgdo { \ 976037b3c26Smrg if (head != NULL) { \ 977037b3c26Smrg uthash_free((head)->hh.tbl->buckets, \ 978037b3c26Smrg (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ 979037b3c26Smrg HASH_BLOOM_FREE((head)->hh.tbl); \ 980037b3c26Smrg uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 981037b3c26Smrg (head)=NULL; \ 982037b3c26Smrg } \ 983037b3c26Smrg} while (0) 984037b3c26Smrg 985037b3c26Smrg#define HASH_OVERHEAD(hh,head) \ 986037b3c26Smrg ((head != NULL) ? ( \ 987037b3c26Smrg (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ 988037b3c26Smrg ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ 989037b3c26Smrg sizeof(UT_hash_table) + \ 990037b3c26Smrg (HASH_BLOOM_BYTELEN))) : 0U) 991037b3c26Smrg 992037b3c26Smrg#ifdef NO_DECLTYPE 993037b3c26Smrg#define HASH_ITER(hh,head,el,tmp) \ 994037b3c26Smrgfor(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \ 995037b3c26Smrg (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL))) 996037b3c26Smrg#else 997037b3c26Smrg#define HASH_ITER(hh,head,el,tmp) \ 998037b3c26Smrgfor(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \ 999037b3c26Smrg (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL))) 1000037b3c26Smrg#endif 1001037b3c26Smrg 1002037b3c26Smrg/* obtain a count of items in the hash */ 1003037b3c26Smrg#define HASH_COUNT(head) HASH_CNT(hh,head) 1004037b3c26Smrg#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U) 1005037b3c26Smrg 1006037b3c26Smrgtypedef struct UT_hash_bucket { 1007037b3c26Smrg struct UT_hash_handle *hh_head; 1008037b3c26Smrg unsigned count; 1009037b3c26Smrg 1010037b3c26Smrg /* expand_mult is normally set to 0. In this situation, the max chain length 1011037b3c26Smrg * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If 1012037b3c26Smrg * the bucket's chain exceeds this length, bucket expansion is triggered). 1013037b3c26Smrg * However, setting expand_mult to a non-zero value delays bucket expansion 1014037b3c26Smrg * (that would be triggered by additions to this particular bucket) 1015037b3c26Smrg * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. 1016037b3c26Smrg * (The multiplier is simply expand_mult+1). The whole idea of this 1017037b3c26Smrg * multiplier is to reduce bucket expansions, since they are expensive, in 1018037b3c26Smrg * situations where we know that a particular bucket tends to be overused. 1019037b3c26Smrg * It is better to let its chain length grow to a longer yet-still-bounded 1020037b3c26Smrg * value, than to do an O(n) bucket expansion too often. 1021037b3c26Smrg */ 1022037b3c26Smrg unsigned expand_mult; 1023037b3c26Smrg 1024037b3c26Smrg} UT_hash_bucket; 1025037b3c26Smrg 1026037b3c26Smrg/* random signature used only to find hash tables in external analysis */ 1027037b3c26Smrg#define HASH_SIGNATURE 0xa0111fe1u 1028037b3c26Smrg#define HASH_BLOOM_SIGNATURE 0xb12220f2u 1029037b3c26Smrg 1030037b3c26Smrgtypedef struct UT_hash_table { 1031037b3c26Smrg UT_hash_bucket *buckets; 1032037b3c26Smrg unsigned num_buckets, log2_num_buckets; 1033037b3c26Smrg unsigned num_items; 1034037b3c26Smrg struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ 1035037b3c26Smrg ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ 1036037b3c26Smrg 1037037b3c26Smrg /* in an ideal situation (all buckets used equally), no bucket would have 1038037b3c26Smrg * more than ceil(#items/#buckets) items. that's the ideal chain length. */ 1039037b3c26Smrg unsigned ideal_chain_maxlen; 1040037b3c26Smrg 1041037b3c26Smrg /* nonideal_items is the number of items in the hash whose chain position 1042037b3c26Smrg * exceeds the ideal chain maxlen. these items pay the penalty for an uneven 1043037b3c26Smrg * hash distribution; reaching them in a chain traversal takes >ideal steps */ 1044037b3c26Smrg unsigned nonideal_items; 1045037b3c26Smrg 1046037b3c26Smrg /* ineffective expands occur when a bucket doubling was performed, but 1047037b3c26Smrg * afterward, more than half the items in the hash had nonideal chain 1048037b3c26Smrg * positions. If this happens on two consecutive expansions we inhibit any 1049037b3c26Smrg * further expansion, as it's not helping; this happens when the hash 1050037b3c26Smrg * function isn't a good fit for the key domain. When expansion is inhibited 1051037b3c26Smrg * the hash will still work, albeit no longer in constant time. */ 1052037b3c26Smrg unsigned ineff_expands, noexpand; 1053037b3c26Smrg 1054037b3c26Smrg uint32_t signature; /* used only to find hash tables in external analysis */ 1055037b3c26Smrg#ifdef HASH_BLOOM 1056037b3c26Smrg uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ 1057037b3c26Smrg uint8_t *bloom_bv; 1058037b3c26Smrg uint8_t bloom_nbits; 1059037b3c26Smrg#endif 1060037b3c26Smrg 1061037b3c26Smrg} UT_hash_table; 1062037b3c26Smrg 1063037b3c26Smrgtypedef struct UT_hash_handle { 1064037b3c26Smrg struct UT_hash_table *tbl; 1065037b3c26Smrg void *prev; /* prev element in app order */ 1066037b3c26Smrg void *next; /* next element in app order */ 1067037b3c26Smrg struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ 1068037b3c26Smrg struct UT_hash_handle *hh_next; /* next hh in bucket order */ 1069037b3c26Smrg void *key; /* ptr to enclosing struct's key */ 1070037b3c26Smrg unsigned keylen; /* enclosing struct's key len */ 1071037b3c26Smrg unsigned hashv; /* result of hash-fcn(key) */ 1072037b3c26Smrg} UT_hash_handle; 1073037b3c26Smrg 1074037b3c26Smrg#endif /* UTHASH_H */ 1075