source: libabac/uthash.h @ 15200be

abac0-leakabac0-meicompt_changesgec13mei-idmei-rt0-nmei_rt0mei_rt2mei_rt2_fix_1meiyap-rt1meiyap1rt2tvf-new-xml
Last change on this file since 15200be was 15200be, checked in by Mike Ryan <mikeryan@…>, 10 years ago

move libabac into its own directory

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