"Fossies" - the Fresh Open Source Software Archive

Member "hitch-1.5.2/src/foreign/uthash.h" (27 Aug 2019, 62067 Bytes) of package /linux/www/hitch-1.5.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "uthash.h" see the Fossies "Dox" file reference documentation.

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