Ashley Mills / tinydtls

Version 0.5.0 of tinydtls

Dependents:   tinydtls_test_cellular tinydtls_test_ethernet tiny-dtls

uthash.h@1:598a56fe116e, 2014-02-12 (annotated)

Committer:
ashleymills
Date:
Wed Feb 12 09:30:16 2014 +0000
Revision:
1:598a56fe116e
Parent:
0:ff9ebe0cf0e9 
Explicitly removed something instead of relying on MACRO to disable it. Mbed can't use it.

Who changed what in which revision?

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