Back to home page

Enduro/X
 
 

     

0001 /*
0002 Copyright (c) 2003-2011, Troy D. Hanson     http://uthash.sourceforge.net
0003 All rights reserved.
0004 
0005 Redistribution and use in source and binary forms, with or without
0006 modification, are permitted provided that the following conditions are met:
0007 
0008     * Redistributions of source code must retain the above copyright
0009       notice, this list of conditions and the following disclaimer.
0010 
0011 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
0012 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
0013 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
0014 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
0015 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
0016 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
0017 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
0018 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
0019 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
0020 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0021 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0022 */
0023 
0024 /* Modified for Enduro/X (renamed from UT->EX) */
0025 #ifndef EXHASH_H
0026 #define EXHASH_H 
0027 
0028 #include <string.h>   /* memcmp,strlen */
0029 #include <stddef.h>   /* ptrdiff_t */
0030 #include <stdlib.h>   /* exit() */
0031 /* #include <ndebug.h> */
0032 
0033 /* These macros use decltype or the earlier __typeof GNU extension.
0034    As decltype is only available in newer compilers (VS2010 or gcc 4.3+
0035    when compiling c++ source) this code uses whatever method is needed
0036    or, for VS2008 where neither is available, uses casting workarounds. */
0037 #ifdef _MSC_VER         /* MS compiler */
0038 #if _MSC_VER >= 1600 && defined(__cplusplus)  /* VS2010 or newer in C++ mode */
0039 #define DECLTYPE(x) (decltype(x))
0040 #else                   /* VS2008 or older (or VS2010 in C mode) */
0041 #define NO_DECLTYPE
0042 #define DECLTYPE(x)
0043 #endif
0044 #else                   /* GNU, Sun and other compilers */
0045 #define DECLTYPE(x) (__typeof(x))
0046 #endif
0047 
0048 #ifdef NO_DECLTYPE
0049 #define DECLTYPE_ASSIGN(dst,src)                                                 \
0050 do {                                                                             \
0051   char **_da_dst = (char**)(&(dst));                                             \
0052   *_da_dst = (char*)(src);                                                       \
0053 } while(0)
0054 #else 
0055 #define DECLTYPE_ASSIGN(dst,src)                                                 \
0056 do {                                                                             \
0057   (dst) = DECLTYPE(dst)(src);                                                    \
0058 } while(0)
0059 #endif
0060 
0061 /* a number of the hash function use uint32_t which isn't defined on win32 */
0062 #ifdef _MSC_VER
0063 typedef unsigned int uint32_t;
0064 typedef unsigned char uint8_t;
0065 #else
0066 #include <inttypes.h>   /* uint32_t */
0067 #endif
0068 
0069 #define EXHASH_VERSION 1.9.4
0070 
0071 #define exhash_fatal(msg) exit(-1)        /* fatal error (out of memory,etc) */
0072 #define exhash_malloc(sz) NDRX_FPMALLOC(sz, 0)      /* malloc fcn                 */
0073 #define exhash_free(ptr,sz) NDRX_FPFREE(ptr)     /* free fcn                   */
0074 
0075 #define exhash_noexpand_fyi(tbl)          /* can be defined to log noexpand  */
0076 #define exhash_expand_fyi(tbl)            /* can be defined to log expands   */
0077 
0078 /* initial number of buckets */
0079 #define EXHASH_INITIAL_NUM_BUCKETS 32      /* initial number of buckets        */
0080 #define EXHASH_INITIAL_NUM_BUCKETS_LOG2 5  /* lg2 of initial number of buckets */
0081 #define EXHASH_BKT_CAPACITY_THRESH 10      /* expand when bucket count reaches */
0082 
0083 /* calculate the element whose hash handle address is hhe */
0084 #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
0085 
0086 #define EXHASH_FIND(hh,head,keyptr,keylen,out)                                     \
0087 do {                                                                             \
0088   unsigned _hf_bkt,_hf_hashv;                                                    \
0089   out=NULL;                                                                      \
0090   if (head) {                                                                    \
0091      EXHASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt);   \
0092      if (EXHASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) {                           \
0093        EXHASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ],  \
0094                         keyptr,keylen,out);                                      \
0095      }                                                                           \
0096   }                                                                              \
0097 } while (0)
0098 
0099 #ifdef HASH_BLOOM
0100 #define EXHASH_BLOOM_BITLEN (1ULL << HASH_BLOOM)
0101 #define EXHASH_BLOOM_BYTELEN (EXHASH_BLOOM_BITLEN/8) + ((EXHASH_BLOOM_BITLEN%8) ? 1:0)
0102 #define EXHASH_BLOOM_MAKE(tbl)                                                     \
0103 do {                                                                             \
0104   (tbl)->bloom_nbits = HASH_BLOOM;                                               \
0105   (tbl)->bloom_bv = (uint8_t*)exhash_malloc(EXHASH_BLOOM_BYTELEN);                 \
0106   if (!((tbl)->bloom_bv))  { exhash_fatal( "out of memory"); }                   \
0107   memset((tbl)->bloom_bv, 0, EXHASH_BLOOM_BYTELEN);                                \
0108   (tbl)->bloom_sig = EXHASH_BLOOM_SIGNATURE;                                       \
0109 } while (0);
0110 
0111 #define EXHASH_BLOOM_FREE(tbl)                                                     \
0112 do {                                                                             \
0113   exhash_free((tbl)->bloom_bv, EXHASH_BLOOM_BYTELEN);                              \
0114 } while (0);
0115 
0116 #define EXHASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8)))
0117 #define EXHASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8)))
0118 
0119 #define EXHASH_BLOOM_ADD(tbl,hashv)                                                \
0120   EXHASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
0121 
0122 #define EXHASH_BLOOM_TEST(tbl,hashv)                                               \
0123   EXHASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
0124 
0125 #else
0126 #define EXHASH_BLOOM_MAKE(tbl) 
0127 #define EXHASH_BLOOM_FREE(tbl) 
0128 #define EXHASH_BLOOM_ADD(tbl,hashv) 
0129 #define EXHASH_BLOOM_TEST(tbl,hashv) (1)
0130 #endif
0131 
0132 #define EXHASH_MAKE_TABLE(hh,head)                                                 \
0133 do {                                                                             \
0134   (head)->hh.tbl = (EX_hash_table*)exhash_malloc(                                \
0135                   sizeof(EX_hash_table));                                        \
0136   if (!((head)->hh.tbl))  { exhash_fatal( "out of memory"); }                    \
0137   memset((head)->hh.tbl, 0, sizeof(EX_hash_table));                              \
0138   (head)->hh.tbl->tail = &((head)->hh);                                          \
0139   (head)->hh.tbl->num_buckets = EXHASH_INITIAL_NUM_BUCKETS;                        \
0140   (head)->hh.tbl->log2_num_buckets = EXHASH_INITIAL_NUM_BUCKETS_LOG2;              \
0141   (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head);                    \
0142   (head)->hh.tbl->buckets = (EX_hash_bucket*)exhash_malloc(                      \
0143           EXHASH_INITIAL_NUM_BUCKETS*sizeof(struct EX_hash_bucket));               \
0144   if (! (head)->hh.tbl->buckets) { exhash_fatal( "out of memory"); }             \
0145   memset((head)->hh.tbl->buckets, 0,                                             \
0146           EXHASH_INITIAL_NUM_BUCKETS*sizeof(struct EX_hash_bucket));               \
0147   EXHASH_BLOOM_MAKE((head)->hh.tbl);                                               \
0148   (head)->hh.tbl->signature = EXHASH_SIGNATURE;                                    \
0149 } while(0)
0150 
0151 #define EXHASH_ADD(hh,head,fieldname,keylen_in,add)                                \
0152         EXHASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add)
0153  
0154 #define EXHASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add)                            \
0155 do {                                                                             \
0156  unsigned _ha_bkt;                                                               \
0157  (add)->hh.next = NULL;                                                          \
0158  (add)->hh.key = (char*)keyptr;                                                  \
0159  (add)->hh.keylen = keylen_in;                                                   \
0160  if (!(head)) {                                                                  \
0161     head = (add);                                                                \
0162     (head)->hh.prev = NULL;                                                      \
0163     EXHASH_MAKE_TABLE(hh,head);                                                    \
0164  } else {                                                                        \
0165     (head)->hh.tbl->tail->next = (add);                                          \
0166     (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail);         \
0167     (head)->hh.tbl->tail = &((add)->hh);                                         \
0168  }                                                                               \
0169  (head)->hh.tbl->num_items++;                                                    \
0170  (add)->hh.tbl = (head)->hh.tbl;                                                 \
0171  EXHASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets,                         \
0172          (add)->hh.hashv, _ha_bkt);                                              \
0173  EXHASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh);                   \
0174  EXHASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv);                                 \
0175  EXHASH_EMIT_KEY(hh,head,keyptr,keylen_in);                                        \
0176  EXHASH_FSCK(hh,head);                                                             \
0177 } while(0)
0178 
0179 #define EXHASH_TO_BKT( hashv, num_bkts, bkt )                                      \
0180 do {                                                                             \
0181   bkt = ((hashv) & ((num_bkts) - 1));                                            \
0182 } while(0)
0183 
0184 /* delete "delptr" from the hash table.
0185  * "the usual" patch-up process for the app-order doubly-linked-list.
0186  * The use of _hd_hh_del below deserves special explanation.
0187  * These used to be expressed using (delptr) but that led to a bug
0188  * if someone used the same symbol for the head and deletee, like
0189  *  EXHASH_DELETE(hh,users,users);
0190  * We want that to work, but by changing the head (users) below
0191  * we were forfeiting our ability to further refer to the deletee (users)
0192  * in the patch-up process. Solution: use scratch space to
0193  * copy the deletee pointer, then the latter references are via that
0194  * scratch pointer rather than through the repointed (users) symbol.
0195  */
0196 #define EXHASH_DELETE(hh,head,delptr)                                              \
0197 do {                                                                             \
0198     unsigned _hd_bkt;                                                            \
0199     struct EX_hash_handle *_hd_hh_del;                                           \
0200     if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) )  {         \
0201         exhash_free((head)->hh.tbl->buckets,                                     \
0202                     (head)->hh.tbl->num_buckets*sizeof(struct EX_hash_bucket) ); \
0203         EXHASH_BLOOM_FREE((head)->hh.tbl);                                         \
0204         exhash_free((head)->hh.tbl, sizeof(EX_hash_table));                      \
0205         head = NULL;                                                             \
0206     } else {                                                                     \
0207         _hd_hh_del = &((delptr)->hh);                                            \
0208         if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) {     \
0209             (head)->hh.tbl->tail =                                               \
0210                 (EX_hash_handle*)((char*)((delptr)->hh.prev) +                   \
0211                 (head)->hh.tbl->hho);                                            \
0212         }                                                                        \
0213         if ((delptr)->hh.prev) {                                                 \
0214             ((EX_hash_handle*)((char*)((delptr)->hh.prev) +                      \
0215                     (head)->hh.tbl->hho))->next = (delptr)->hh.next;             \
0216         } else {                                                                 \
0217             DECLTYPE_ASSIGN(head,(delptr)->hh.next);                             \
0218         }                                                                        \
0219         if (_hd_hh_del->next) {                                                  \
0220             ((EX_hash_handle*)((char*)_hd_hh_del->next +                         \
0221                     (head)->hh.tbl->hho))->prev =                                \
0222                     _hd_hh_del->prev;                                            \
0223         }                                                                        \
0224         EXHASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt);   \
0225         EXHASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del);        \
0226         (head)->hh.tbl->num_items--;                                             \
0227     }                                                                            \
0228     EXHASH_FSCK(hh,head);                                                          \
0229 } while (0)
0230 
0231 
0232 /* convenience forms of EXHASH_FIND/EXHASH_ADD/EXHASH_DEL */
0233 #define EXHASH_FIND_STR(head,findstr,out)                                          \
0234     EXHASH_FIND(hh,head,findstr,strlen(findstr),out)
0235 #define EXHASH_ADD_STR(head,strfield,add)                                          \
0236     EXHASH_ADD(hh,head,strfield,strlen(add->strfield),add)
0237 #define EXHASH_FIND_INT(head,findint,out)                                          \
0238     EXHASH_FIND(hh,head,findint,sizeof(int),out)
0239 #define EXHASH_ADD_INT(head,intfield,add)                                          \
0240     EXHASH_ADD(hh,head,intfield,sizeof(int),add)
0241 #define EXHASH_FIND_LONG(head,findlong,out)                                          \
0242     EXHASH_FIND(hh,head,findlong,sizeof(long),out)
0243 #define EXHASH_ADD_LONG(head,longfield,add)                                          \
0244     EXHASH_ADD(hh,head,longfield,sizeof(long),add)
0245 #define EXHASH_FIND_PTR(head,findptr,out)                                          \
0246     EXHASH_FIND(hh,head,findptr,sizeof(void *),out)
0247 #define EXHASH_ADD_PTR(head,ptrfield,add)                                          \
0248     EXHASH_ADD(hh,head,ptrfield,sizeof(void *),add)
0249 #define EXHASH_DEL(head,delptr)                                                    \
0250     EXHASH_DELETE(hh,head,delptr)
0251 
0252 /* EXHASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined.
0253  * This is for exhash developer only; it compiles away if HASH_DEBUG isn't defined.
0254  */
0255 #ifdef HASH_DEBUG
0256 #define EXHASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
0257 #define EXHASH_FSCK(hh,head)                                                       \
0258 do {                                                                             \
0259     unsigned _bkt_i;                                                             \
0260     unsigned _count, _bkt_count;                                                 \
0261     char *_prev;                                                                 \
0262     struct EX_hash_handle *_thh;                                                 \
0263     if (head) {                                                                  \
0264         _count = 0;                                                              \
0265         for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) {       \
0266             _bkt_count = 0;                                                      \
0267             _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head;                      \
0268             _prev = NULL;                                                        \
0269             while (_thh) {                                                       \
0270                if (_prev != (char*)(_thh->hh_prev)) {                            \
0271                    EXHASH_OOPS("invalid hh_prev %p, actual %p\n",                  \
0272                     _thh->hh_prev, _prev );                                      \
0273                }                                                                 \
0274                _bkt_count++;                                                     \
0275                _prev = (char*)(_thh);                                            \
0276                _thh = _thh->hh_next;                                             \
0277             }                                                                    \
0278             _count += _bkt_count;                                                \
0279             if ((head)->hh.tbl->buckets[_bkt_i].count !=  _bkt_count) {          \
0280                EXHASH_OOPS("invalid bucket count %d, actual %d\n",                 \
0281                 (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count);              \
0282             }                                                                    \
0283         }                                                                        \
0284         if (_count != (head)->hh.tbl->num_items) {                               \
0285             EXHASH_OOPS("invalid hh item count %d, actual %d\n",                   \
0286                 (head)->hh.tbl->num_items, _count );                             \
0287         }                                                                        \
0288         /* traverse hh in app order; check next/prev integrity, count */         \
0289         _count = 0;                                                              \
0290         _prev = NULL;                                                            \
0291         _thh =  &(head)->hh;                                                     \
0292         while (_thh) {                                                           \
0293            _count++;                                                             \
0294            if (_prev !=(char*)(_thh->prev)) {                                    \
0295               EXHASH_OOPS("invalid prev %p, actual %p\n",                          \
0296                     _thh->prev, _prev );                                         \
0297            }                                                                     \
0298            _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh);                    \
0299            _thh = ( _thh->next ?  (EX_hash_handle*)((char*)(_thh->next) +        \
0300                                   (head)->hh.tbl->hho) : NULL );                 \
0301         }                                                                        \
0302         if (_count != (head)->hh.tbl->num_items) {                               \
0303             EXHASH_OOPS("invalid app item count %d, actual %d\n",                  \
0304                 (head)->hh.tbl->num_items, _count );                             \
0305         }                                                                        \
0306     }                                                                            \
0307 } while (0)
0308 #else
0309 #define EXHASH_FSCK(hh,head) 
0310 #endif
0311 
0312 /* When compiled with -DEXHASH_EMIT_KEYS, length-prefixed keys are emitted to 
0313  * the descriptor to which this macro is defined for tuning the hash function.
0314  * The app can #include <unistd.h> to get the prototype for write(2). */
0315 #ifdef EXHASH_EMIT_KEYS
0316 #define EXHASH_EMIT_KEY(hh,head,keyptr,fieldlen)                                   \
0317 do {                                                                             \
0318     unsigned _klen = fieldlen;                                                   \
0319     write(EXHASH_EMIT_KEYS, &_klen, sizeof(_klen));                                \
0320     write(EXHASH_EMIT_KEYS, keyptr, fieldlen);                                     \
0321 } while (0)
0322 #else 
0323 #define EXHASH_EMIT_KEY(hh,head,keyptr,fieldlen)                    
0324 #endif
0325 
0326 /* default to Jenkin's hash unless overridden e.g. DEXHASH_FUNCTION=EXHASH_SAX */
0327 #ifdef EXHASH_FUNCTION 
0328 #define EXHASH_FCN EXHASH_FUNCTION
0329 #else
0330 #define EXHASH_FCN EXHASH_JEN
0331 #endif
0332 
0333 /* The Bernstein hash function, used in Perl prior to v5.6 */
0334 #define EXHASH_BER(key,keylen,num_bkts,hashv,bkt)                                  \
0335 do {                                                                             \
0336   unsigned _hb_keylen=keylen;                                                    \
0337   char *_hb_key=(char*)(key);                                                    \
0338   (hashv) = 0;                                                                   \
0339   while (_hb_keylen--)  { (hashv) = ((hashv) * 33) + *_hb_key++; }               \
0340   bkt = (hashv) & (num_bkts-1);                                                  \
0341 } while (0)
0342 
0343 
0344 /* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at 
0345  * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */
0346 #define EXHASH_SAX(key,keylen,num_bkts,hashv,bkt)                                  \
0347 do {                                                                             \
0348   unsigned _sx_i;                                                                \
0349   char *_hs_key=(char*)(key);                                                    \
0350   hashv = 0;                                                                     \
0351   for(_sx_i=0; _sx_i < keylen; _sx_i++)                                          \
0352       hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i];                     \
0353   bkt = hashv & (num_bkts-1);                                                    \
0354 } while (0)
0355 
0356 #define EXHASH_FNV(key,keylen,num_bkts,hashv,bkt)                                  \
0357 do {                                                                             \
0358   unsigned _fn_i;                                                                \
0359   char *_hf_key=(char*)(key);                                                    \
0360   hashv = 2166136261UL;                                                          \
0361   for(_fn_i=0; _fn_i < keylen; _fn_i++)                                          \
0362       hashv = (hashv * 16777619) ^ _hf_key[_fn_i];                               \
0363   bkt = hashv & (num_bkts-1);                                                    \
0364 } while(0);
0365  
0366 #define EXHASH_OAT(key,keylen,num_bkts,hashv,bkt)                                  \
0367 do {                                                                             \
0368   unsigned _ho_i;                                                                \
0369   char *_ho_key=(char*)(key);                                                    \
0370   hashv = 0;                                                                     \
0371   for(_ho_i=0; _ho_i < keylen; _ho_i++) {                                        \
0372       hashv += _ho_key[_ho_i];                                                   \
0373       hashv += (hashv << 10);                                                    \
0374       hashv ^= (hashv >> 6);                                                     \
0375   }                                                                              \
0376   hashv += (hashv << 3);                                                         \
0377   hashv ^= (hashv >> 11);                                                        \
0378   hashv += (hashv << 15);                                                        \
0379   bkt = hashv & (num_bkts-1);                                                    \
0380 } while(0)
0381 
0382 #define EXEXHASH_JEN_MIX(a,b,c)                                                      \
0383 do {                                                                             \
0384   a -= b; a -= c; a ^= ( c >> 13 );                                              \
0385   b -= c; b -= a; b ^= ( a << 8 );                                               \
0386   c -= a; c -= b; c ^= ( b >> 13 );                                              \
0387   a -= b; a -= c; a ^= ( c >> 12 );                                              \
0388   b -= c; b -= a; b ^= ( a << 16 );                                              \
0389   c -= a; c -= b; c ^= ( b >> 5 );                                               \
0390   a -= b; a -= c; a ^= ( c >> 3 );                                               \
0391   b -= c; b -= a; b ^= ( a << 10 );                                              \
0392   c -= a; c -= b; c ^= ( b >> 15 );                                              \
0393 } while (0)
0394 
0395 #define EXHASH_JEN(key,keylen,num_bkts,hashv,bkt)                                  \
0396 do {                                                                             \
0397   unsigned _hj_i,_hj_j,_hj_k;                                                    \
0398   char *_hj_key=(char*)(key);                                                    \
0399   hashv = 0xfeedbeef;                                                            \
0400   _hj_i = _hj_j = 0x9e3779b9;                                                    \
0401   _hj_k = keylen;                                                                \
0402   while (_hj_k >= 12) {                                                          \
0403     _hj_i +=    (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 )                      \
0404         + ( (unsigned)_hj_key[2] << 16 )                                         \
0405         + ( (unsigned)_hj_key[3] << 24 ) );                                      \
0406     _hj_j +=    (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 )                      \
0407         + ( (unsigned)_hj_key[6] << 16 )                                         \
0408         + ( (unsigned)_hj_key[7] << 24 ) );                                      \
0409     hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 )                         \
0410         + ( (unsigned)_hj_key[10] << 16 )                                        \
0411         + ( (unsigned)_hj_key[11] << 24 ) );                                     \
0412                                                                                  \
0413      EXEXHASH_JEN_MIX(_hj_i, _hj_j, hashv);                                          \
0414                                                                                  \
0415      _hj_key += 12;                                                              \
0416      _hj_k -= 12;                                                                \
0417   }                                                                              \
0418   hashv += keylen;                                                               \
0419   switch ( _hj_k ) {                                                             \
0420      case 11: hashv += ( (unsigned)_hj_key[10] << 24 );                          \
0421      case 10: hashv += ( (unsigned)_hj_key[9] << 16 );                           \
0422      case 9:  hashv += ( (unsigned)_hj_key[8] << 8 );                            \
0423      case 8:  _hj_j += ( (unsigned)_hj_key[7] << 24 );                           \
0424      case 7:  _hj_j += ( (unsigned)_hj_key[6] << 16 );                           \
0425      case 6:  _hj_j += ( (unsigned)_hj_key[5] << 8 );                            \
0426      case 5:  _hj_j += _hj_key[4];                                               \
0427      case 4:  _hj_i += ( (unsigned)_hj_key[3] << 24 );                           \
0428      case 3:  _hj_i += ( (unsigned)_hj_key[2] << 16 );                           \
0429      case 2:  _hj_i += ( (unsigned)_hj_key[1] << 8 );                            \
0430      case 1:  _hj_i += _hj_key[0];                                               \
0431   }                                                                              \
0432   EXEXHASH_JEN_MIX(_hj_i, _hj_j, hashv);                                             \
0433   bkt = hashv & (num_bkts-1);                                                    \
0434 } while(0)
0435 
0436 /* The Paul Hsieh hash function */
0437 #undef get16bits
0438 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__)             \
0439   || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
0440 #define get16bits(d) (*((const uint16_t *) (d)))
0441 #endif
0442 
0443 #if !defined (get16bits)
0444 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)             \
0445                        +(uint32_t)(((const uint8_t *)(d))[0]) )
0446 #endif
0447 #define EXHASH_SFH(key,keylen,num_bkts,hashv,bkt)                                  \
0448 do {                                                                             \
0449   char *_sfh_key=(char*)(key);                                                   \
0450   uint32_t _sfh_tmp, _sfh_len = keylen;                                          \
0451                                                                                  \
0452   int _sfh_rem = _sfh_len & 3;                                                   \
0453   _sfh_len >>= 2;                                                                \
0454   hashv = 0xcafebabe;                                                            \
0455                                                                                  \
0456   /* Main loop */                                                                \
0457   for (;_sfh_len > 0; _sfh_len--) {                                              \
0458     hashv    += get16bits (_sfh_key);                                            \
0459     _sfh_tmp       = (get16bits (_sfh_key+2) << 11) ^ hashv;                     \
0460     hashv     = (hashv << 16) ^ _sfh_tmp;                                        \
0461     _sfh_key += 2*sizeof (uint16_t);                                             \
0462     hashv    += hashv >> 11;                                                     \
0463   }                                                                              \
0464                                                                                  \
0465   /* Handle end cases */                                                         \
0466   switch (_sfh_rem) {                                                            \
0467     case 3: hashv += get16bits (_sfh_key);                                       \
0468             hashv ^= hashv << 16;                                                \
0469             hashv ^= _sfh_key[sizeof (uint16_t)] << 18;                          \
0470             hashv += hashv >> 11;                                                \
0471             break;                                                               \
0472     case 2: hashv += get16bits (_sfh_key);                                       \
0473             hashv ^= hashv << 11;                                                \
0474             hashv += hashv >> 17;                                                \
0475             break;                                                               \
0476     case 1: hashv += *_sfh_key;                                                  \
0477             hashv ^= hashv << 10;                                                \
0478             hashv += hashv >> 1;                                                 \
0479   }                                                                              \
0480                                                                                  \
0481     /* Force "avalanching" of final 127 bits */                                  \
0482     hashv ^= hashv << 3;                                                         \
0483     hashv += hashv >> 5;                                                         \
0484     hashv ^= hashv << 4;                                                         \
0485     hashv += hashv >> 17;                                                        \
0486     hashv ^= hashv << 25;                                                        \
0487     hashv += hashv >> 6;                                                         \
0488     bkt = hashv & (num_bkts-1);                                                  \
0489 } while(0);
0490 
0491 #ifdef HASH_USING_NO_STRICT_ALIASING
0492 /* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads.
0493  * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error.
0494  * MurmurHash uses the faster approach only on CPU's where we know it's safe. 
0495  *
0496  * Note the preprocessor built-in defines can be emitted using:
0497  *
0498  *   gcc -m64 -dM -E - < /dev/null                  (on gcc)
0499  *   cc -## a.c (where a.c is a simple test file)   (Sun Studio)
0500  */
0501 #if (defined(__i386__) || defined(__x86_64__)) 
0502 #define MUR_GETBLOCK(p,i) p[i]
0503 #else /* non intel */
0504 #define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 0x3) == 0)
0505 #define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 0x3) == 1)
0506 #define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 0x3) == 2)
0507 #define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 0x3) == 3)
0508 #define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL))
0509 #if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__))
0510 #define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24))
0511 #define MUR_TWO_TWO(p)   ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16))
0512 #define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >>  8))
0513 #else /* assume little endian non-intel */
0514 #define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24))
0515 #define MUR_TWO_TWO(p)   ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16))
0516 #define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) <<  8))
0517 #endif
0518 #define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) :           \
0519                             (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \
0520                              (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) :  \
0521                                                       MUR_ONE_THREE(p))))
0522 #endif
0523 #define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
0524 #define MUR_FMIX(_h) \
0525 do {                 \
0526   _h ^= _h >> 16;    \
0527   _h *= 0x85ebca6b;  \
0528   _h ^= _h >> 13;    \
0529   _h *= 0xc2b2ae35l; \
0530   _h ^= _h >> 16;    \
0531 } while(0)
0532 
0533 #define EXHASH_MUR(key,keylen,num_bkts,hashv,bkt)                        \
0534 do {                                                                   \
0535   const uint8_t *_mur_data = (const uint8_t*)(key);                    \
0536   const int _mur_nblocks = (keylen) / 4;                               \
0537   uint32_t _mur_h1 = 0xf88D5353;                                       \
0538   uint32_t _mur_c1 = 0xcc9e2d51;                                       \
0539   uint32_t _mur_c2 = 0x1b873593;                                       \
0540   const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+_mur_nblocks*4); \
0541   int _mur_i;                                                          \
0542   for(_mur_i = -_mur_nblocks; _mur_i; _mur_i++) {                      \
0543     uint32_t _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i);               \
0544     _mur_k1 *= _mur_c1;                                                \
0545     _mur_k1 = MUR_ROTL32(_mur_k1,15);                                  \
0546     _mur_k1 *= _mur_c2;                                                \
0547                                                                        \
0548     _mur_h1 ^= _mur_k1;                                                \
0549     _mur_h1 = MUR_ROTL32(_mur_h1,13);                                  \
0550     _mur_h1 = _mur_h1*5+0xe6546b64;                                    \
0551   }                                                                    \
0552   const uint8_t *_mur_tail = (const uint8_t*)(_mur_data + _mur_nblocks*4); \
0553   uint32_t _mur_k1=0;                                                  \
0554   switch((keylen) & 3) {                                               \
0555     case 3: _mur_k1 ^= _mur_tail[2] << 16;                             \
0556     case 2: _mur_k1 ^= _mur_tail[1] << 8;                              \
0557     case 1: _mur_k1 ^= _mur_tail[0];                                   \
0558     _mur_k1 *= _mur_c1;                                                \
0559     _mur_k1 = MUR_ROTL32(_mur_k1,15);                                  \
0560     _mur_k1 *= _mur_c2;                                                \
0561     _mur_h1 ^= _mur_k1;                                                \
0562   }                                                                    \
0563   _mur_h1 ^= (keylen);                                                 \
0564   MUR_FMIX(_mur_h1);                                                   \
0565   hashv = _mur_h1;                                                     \
0566   bkt = hashv & (num_bkts-1);                                          \
0567 } while(0)
0568 #endif  /* HASH_USING_NO_STRICT_ALIASING */
0569 
0570 /* key comparison function; return 0 if keys equal */
0571 #define EXHASH_KEYCMP(a,b,len) memcmp(a,b,len) 
0572 
0573 /* iterate over items in a known bucket to find desired item */
0574 #define EXHASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out)                       \
0575 do {                                                                             \
0576  if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head));          \
0577  else out=NULL;                                                                  \
0578  while (out) {                                                                   \
0579     if (out->hh.keylen == keylen_in) {                                           \
0580         if ((EXHASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break;             \
0581     }                                                                            \
0582     if (out->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,out->hh.hh_next)); \
0583     else out = NULL;                                                             \
0584  }                                                                               \
0585 } while(0)
0586 
0587 /* add an item to a bucket  */
0588 #define EXHASH_ADD_TO_BKT(head,addhh)                                              \
0589 do {                                                                             \
0590  head.count++;                                                                   \
0591  (addhh)->hh_next = head.hh_head;                                                \
0592  (addhh)->hh_prev = NULL;                                                        \
0593  if (head.hh_head) { (head).hh_head->hh_prev = (addhh); }                        \
0594  (head).hh_head=addhh;                                                           \
0595  if (head.count >= ((head.expand_mult+1) * EXHASH_BKT_CAPACITY_THRESH)             \
0596      && (addhh)->tbl->noexpand != 1) {                                           \
0597        EXHASH_EXPAND_BUCKETS((addhh)->tbl);                                        \
0598  }                                                                               \
0599 } while(0)
0600 
0601 /* remove an item from a given bucket */
0602 #define EXHASH_DEL_IN_BKT(hh,head,hh_del)                                          \
0603     (head).count--;                                                              \
0604     if ((head).hh_head == hh_del) {                                              \
0605       (head).hh_head = hh_del->hh_next;                                          \
0606     }                                                                            \
0607     if (hh_del->hh_prev) {                                                       \
0608         hh_del->hh_prev->hh_next = hh_del->hh_next;                              \
0609     }                                                                            \
0610     if (hh_del->hh_next) {                                                       \
0611         hh_del->hh_next->hh_prev = hh_del->hh_prev;                              \
0612     }                                                                
0613 
0614 /* Bucket expansion has the effect of doubling the number of buckets
0615  * and redistributing the items into the new buckets. Ideally the
0616  * items will distribute more or less evenly into the new buckets
0617  * (the extent to which this is true is a measure of the quality of
0618  * the hash function as it applies to the key domain). 
0619  * 
0620  * With the items distributed into more buckets, the chain length
0621  * (item count) in each bucket is reduced. Thus by expanding buckets
0622  * the hash keeps a bound on the chain length. This bounded chain 
0623  * length is the essence of how a hash provides constant time lookup.
0624  * 
0625  * The calculation of tbl->ideal_chain_maxlen below deserves some
0626  * explanation. First, keep in mind that we're calculating the ideal
0627  * maximum chain length based on the *new* (doubled) bucket count.
0628  * In fractions this is just n/b (n=number of items,b=new num buckets).
0629  * Since the ideal chain length is an integer, we want to calculate 
0630  * ceil(n/b). We don't depend on floating point arithmetic in this
0631  * hash, so to calculate ceil(n/b) with integers we could write
0632  * 
0633  *      ceil(n/b) = (n/b) + ((n%b)?1:0)
0634  * 
0635  * and in fact a previous version of this hash did just that.
0636  * But now we have improved things a bit by recognizing that b is
0637  * always a power of two. We keep its base 2 log handy (call it lb),
0638  * so now we can write this with a bit shift and logical AND:
0639  * 
0640  *      ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0)
0641  * 
0642  */
0643 #define EXHASH_EXPAND_BUCKETS(tbl)                                                 \
0644 do {                                                                             \
0645     unsigned _he_bkt;                                                            \
0646     unsigned _he_bkt_i;                                                          \
0647     struct EX_hash_handle *_he_thh, *_he_hh_nxt;                                 \
0648     EX_hash_bucket *_he_new_buckets, *_he_newbkt;                                \
0649     _he_new_buckets = (EX_hash_bucket*)exhash_malloc(                            \
0650              2 * tbl->num_buckets * sizeof(struct EX_hash_bucket));              \
0651     if (!_he_new_buckets) { exhash_fatal( "out of memory"); }                    \
0652     memset(_he_new_buckets, 0,                                                   \
0653             2 * tbl->num_buckets * sizeof(struct EX_hash_bucket));               \
0654     tbl->ideal_chain_maxlen =                                                    \
0655        (tbl->num_items >> (tbl->log2_num_buckets+1)) +                           \
0656        ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0);                    \
0657     tbl->nonideal_items = 0;                                                     \
0658     for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++)                \
0659     {                                                                            \
0660         _he_thh = tbl->buckets[ _he_bkt_i ].hh_head;                             \
0661         while (_he_thh) {                                                        \
0662            _he_hh_nxt = _he_thh->hh_next;                                        \
0663            EXHASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt);            \
0664            _he_newbkt = &(_he_new_buckets[ _he_bkt ]);                           \
0665            if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) {                \
0666              tbl->nonideal_items++;                                              \
0667              _he_newbkt->expand_mult = _he_newbkt->count /                       \
0668                                         tbl->ideal_chain_maxlen;                 \
0669            }                                                                     \
0670            _he_thh->hh_prev = NULL;                                              \
0671            _he_thh->hh_next = _he_newbkt->hh_head;                               \
0672            if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev =               \
0673                 _he_thh;                                                         \
0674            _he_newbkt->hh_head = _he_thh;                                        \
0675            _he_thh = _he_hh_nxt;                                                 \
0676         }                                                                        \
0677     }                                                                            \
0678     exhash_free( tbl->buckets, tbl->num_buckets*sizeof(struct EX_hash_bucket) ); \
0679     tbl->num_buckets *= 2;                                                       \
0680     tbl->log2_num_buckets++;                                                     \
0681     tbl->buckets = _he_new_buckets;                                              \
0682     tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ?         \
0683         (tbl->ineff_expands+1) : 0;                                              \
0684     if (tbl->ineff_expands > 1) {                                                \
0685         tbl->noexpand=1;                                                         \
0686         exhash_noexpand_fyi(tbl);                                                \
0687     }                                                                            \
0688     exhash_expand_fyi(tbl);                                                      \
0689 } while(0)
0690 
0691 
0692 /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */
0693 /* Note that EXHASH_SORT assumes the hash handle name to be hh. 
0694  * EXHASH_SRT was added to allow the hash handle name to be passed in. */
0695 #define EXHASH_SORT(head,cmpfcn) EXHASH_SRT(hh,head,cmpfcn)
0696 #define EXHASH_SRT(hh,head,cmpfcn)                                                 \
0697 do {                                                                             \
0698   unsigned _hs_i;                                                                \
0699   unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize;               \
0700   struct EX_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail;            \
0701   if (head) {                                                                    \
0702       _hs_insize = 1;                                                            \
0703       _hs_looping = 1;                                                           \
0704       _hs_list = &((head)->hh);                                                  \
0705       while (_hs_looping) {                                                      \
0706           _hs_p = _hs_list;                                                      \
0707           _hs_list = NULL;                                                       \
0708           _hs_tail = NULL;                                                       \
0709           _hs_nmerges = 0;                                                       \
0710           while (_hs_p) {                                                        \
0711               _hs_nmerges++;                                                     \
0712               _hs_q = _hs_p;                                                     \
0713               _hs_psize = 0;                                                     \
0714               for ( _hs_i = 0; _hs_i  < _hs_insize; _hs_i++ ) {                  \
0715                   _hs_psize++;                                                   \
0716                   _hs_q = (EX_hash_handle*)((_hs_q->next) ?                      \
0717                           ((void*)((char*)(_hs_q->next) +                        \
0718                           (head)->hh.tbl->hho)) : NULL);                         \
0719                   if (! (_hs_q) ) break;                                         \
0720               }                                                                  \
0721               _hs_qsize = _hs_insize;                                            \
0722               while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) {           \
0723                   if (_hs_psize == 0) {                                          \
0724                       _hs_e = _hs_q;                                             \
0725                       _hs_q = (EX_hash_handle*)((_hs_q->next) ?                  \
0726                               ((void*)((char*)(_hs_q->next) +                    \
0727                               (head)->hh.tbl->hho)) : NULL);                     \
0728                       _hs_qsize--;                                               \
0729                   } else if ( (_hs_qsize == 0) || !(_hs_q) ) {                   \
0730                       _hs_e = _hs_p;                                             \
0731                       _hs_p = (EX_hash_handle*)((_hs_p->next) ?                  \
0732                               ((void*)((char*)(_hs_p->next) +                    \
0733                               (head)->hh.tbl->hho)) : NULL);                     \
0734                       _hs_psize--;                                               \
0735                   } else if ((                                                   \
0736                       cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \
0737                              DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \
0738                              ) <= 0) {                                           \
0739                       _hs_e = _hs_p;                                             \
0740                       _hs_p = (EX_hash_handle*)((_hs_p->next) ?                  \
0741                               ((void*)((char*)(_hs_p->next) +                    \
0742                               (head)->hh.tbl->hho)) : NULL);                     \
0743                       _hs_psize--;                                               \
0744                   } else {                                                       \
0745                       _hs_e = _hs_q;                                             \
0746                       _hs_q = (EX_hash_handle*)((_hs_q->next) ?                  \
0747                               ((void*)((char*)(_hs_q->next) +                    \
0748                               (head)->hh.tbl->hho)) : NULL);                     \
0749                       _hs_qsize--;                                               \
0750                   }                                                              \
0751                   if ( _hs_tail ) {                                              \
0752                       _hs_tail->next = ((_hs_e) ?                                \
0753                             ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL);          \
0754                   } else {                                                       \
0755                       _hs_list = _hs_e;                                          \
0756                   }                                                              \
0757                   _hs_e->prev = ((_hs_tail) ?                                    \
0758                      ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL);              \
0759                   _hs_tail = _hs_e;                                              \
0760               }                                                                  \
0761               _hs_p = _hs_q;                                                     \
0762           }                                                                      \
0763           _hs_tail->next = NULL;                                                 \
0764           if ( _hs_nmerges <= 1 ) {                                              \
0765               _hs_looping=0;                                                     \
0766               (head)->hh.tbl->tail = _hs_tail;                                   \
0767               DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list));      \
0768           }                                                                      \
0769           _hs_insize *= 2;                                                       \
0770       }                                                                          \
0771       EXHASH_FSCK(hh,head);                                                        \
0772  }                                                                               \
0773 } while (0)
0774 
0775 /* This function selects items from one hash into another hash. 
0776  * The end result is that the selected items have dual presence 
0777  * in both hashes. There is no copy of the items made; rather 
0778  * they are added into the new hash through a secondary hash 
0779  * hash handle that must be present in the structure. */
0780 #define EXHASH_SELECT(hh_dst, dst, hh_src, src, cond)                              \
0781 do {                                                                             \
0782   unsigned _src_bkt, _dst_bkt;                                                   \
0783   void *_last_elt=NULL, *_elt;                                                   \
0784   EX_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL;                         \
0785   ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst));                 \
0786   if (src) {                                                                     \
0787     for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) {     \
0788       for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head;                \
0789           _src_hh;                                                               \
0790           _src_hh = _src_hh->hh_next) {                                          \
0791           _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh);                       \
0792           if (cond(_elt)) {                                                      \
0793             _dst_hh = (EX_hash_handle*)(((char*)_elt) + _dst_hho);               \
0794             _dst_hh->key = _src_hh->key;                                         \
0795             _dst_hh->keylen = _src_hh->keylen;                                   \
0796             _dst_hh->hashv = _src_hh->hashv;                                     \
0797             _dst_hh->prev = _last_elt;                                           \
0798             _dst_hh->next = NULL;                                                \
0799             if (_last_elt_hh) { _last_elt_hh->next = _elt; }                     \
0800             if (!dst) {                                                          \
0801               DECLTYPE_ASSIGN(dst,_elt);                                         \
0802               EXHASH_MAKE_TABLE(hh_dst,dst);                                       \
0803             } else {                                                             \
0804               _dst_hh->tbl = (dst)->hh_dst.tbl;                                  \
0805             }                                                                    \
0806             EXHASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt);    \
0807             EXHASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh);            \
0808             (dst)->hh_dst.tbl->num_items++;                                      \
0809             _last_elt = _elt;                                                    \
0810             _last_elt_hh = _dst_hh;                                              \
0811           }                                                                      \
0812       }                                                                          \
0813     }                                                                            \
0814   }                                                                              \
0815   EXHASH_FSCK(hh_dst,dst);                                                         \
0816 } while (0)
0817 
0818 #define EXHASH_CLEAR(hh,head)                                                      \
0819 do {                                                                             \
0820   if (head) {                                                                    \
0821     exhash_free((head)->hh.tbl->buckets,                                         \
0822                 (head)->hh.tbl->num_buckets*sizeof(struct EX_hash_bucket));      \
0823     EXHASH_BLOOM_FREE((head)->hh.tbl);                                             \
0824     exhash_free((head)->hh.tbl, sizeof(EX_hash_table));                          \
0825     (head)=NULL;                                                                 \
0826   }                                                                              \
0827 } while(0)
0828 
0829 #ifdef NO_DECLTYPE
0830 #define EXHASH_ITER(hh,head,el,tmp)                                                \
0831 for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL);       \
0832   el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) 
0833 #else
0834 #define EXHASH_ITER(hh,head,el,tmp)                                                \
0835 for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL);                 \
0836   el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL))
0837 #endif
0838 
0839 /* obtain a count of items in the hash */
0840 #define EXHASH_COUNT(head) EXHASH_CNT(hh,head) 
0841 #define EXHASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0)
0842 
0843 typedef struct EX_hash_bucket {
0844    struct EX_hash_handle *hh_head;
0845    unsigned count;
0846 
0847    /* expand_mult is normally set to 0. In this situation, the max chain length
0848     * threshold is enforced at its default value, EXHASH_BKT_CAPACITY_THRESH. (If
0849     * the bucket's chain exceeds this length, bucket expansion is triggered). 
0850     * However, setting expand_mult to a non-zero value delays bucket expansion
0851     * (that would be triggered by additions to this particular bucket)
0852     * until its chain length reaches a *multiple* of EXHASH_BKT_CAPACITY_THRESH.
0853     * (The multiplier is simply expand_mult+1). The whole idea of this
0854     * multiplier is to reduce bucket expansions, since they are expensive, in
0855     * situations where we know that a particular bucket tends to be overused.
0856     * It is better to let its chain length grow to a longer yet-still-bounded
0857     * value, than to do an O(n) bucket expansion too often. 
0858     */
0859    unsigned expand_mult;
0860 
0861 } EX_hash_bucket;
0862 
0863 /* random signature used only to find hash tables in external analysis */
0864 #define EXHASH_SIGNATURE 0xa0111fe1
0865 #define EXHASH_BLOOM_SIGNATURE 0xb12220f2
0866 
0867 typedef struct EX_hash_table {
0868    EX_hash_bucket *buckets;
0869    unsigned num_buckets, log2_num_buckets;
0870    unsigned num_items;
0871    struct EX_hash_handle *tail; /* tail hh in app order, for fast append    */
0872    ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */
0873 
0874    /* in an ideal situation (all buckets used equally), no bucket would have
0875     * more than ceil(#items/#buckets) items. that's the ideal chain length. */
0876    unsigned ideal_chain_maxlen;
0877 
0878    /* nonideal_items is the number of items in the hash whose chain position
0879     * exceeds the ideal chain maxlen. these items pay the penalty for an uneven
0880     * hash distribution; reaching them in a chain traversal takes >ideal steps */
0881    unsigned nonideal_items;
0882 
0883    /* ineffective expands occur when a bucket doubling was performed, but 
0884     * afterward, more than half the items in the hash had nonideal chain
0885     * positions. If this happens on two consecutive expansions we inhibit any
0886     * further expansion, as it's not helping; this happens when the hash
0887     * function isn't a good fit for the key domain. When expansion is inhibited
0888     * the hash will still work, albeit no longer in constant time. */
0889    unsigned ineff_expands, noexpand;
0890 
0891    uint32_t signature; /* used only to find hash tables in external analysis */
0892 #ifdef HASH_BLOOM
0893    uint32_t bloom_sig; /* used only to test bloom exists in external analysis */
0894    uint8_t *bloom_bv;
0895    char bloom_nbits;
0896 #endif
0897 
0898 } EX_hash_table;
0899 
0900 typedef struct EX_hash_handle {
0901    struct EX_hash_table *tbl;
0902    void *prev;                       /* prev element in app order      */
0903    void *next;                       /* next element in app order      */
0904    struct EX_hash_handle *hh_prev;   /* previous hh in bucket order    */
0905    struct EX_hash_handle *hh_next;   /* next hh in bucket order        */
0906    void *key;                        /* ptr to enclosing struct's key  */
0907    unsigned keylen;                  /* enclosing struct's key len     */
0908    unsigned hashv;                   /* result of hash-fcn(key)        */
0909 } EX_hash_handle;
0910 
0911 #endif /* EXHASH_H */
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!