"Fossies" - the Fresh Open Source Software Archive

Member "hydra-3.3.2/mpl/include/uthash.h" (12 Nov 2019, 69266 Bytes) of package /linux/misc/hydra-3.3.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 and the latest Fossies "Diffs" side-by-side code changes report: 3.3.1_vs_3.3.2.

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