resource/csdk/connectivity/lib/libcoap-4.1.1/uthash.h

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