src/uthash.h

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