Ashley Mills
mbed port of tinydtls
Embed:
(wiki syntax)
Show/hide line numbers
uthash.h
00001 /* 00002 Copyright (c) 2003-2010, Troy D. Hanson http://uthash.sourceforge.net 00003 All rights reserved. 00004 00005 Redistribution and use in source and binary forms, with or without 00006 modification, are permitted provided that the following conditions are met: 00007 00008 * Redistributions of source code must retain the above copyright 00009 notice, this list of conditions and the following disclaimer. 00010 00011 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 00012 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 00013 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 00014 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 00015 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 00016 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 00017 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 00018 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00019 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00020 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00021 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00022 */ 00023 00024 #ifndef UTHASH_H 00025 #define UTHASH_H 00026 00027 #include <string.h> /* memcmp,strlen */ 00028 #include <stddef.h> /* ptrdiff_t */ 00029 00030 /* These macros use decltype or the earlier __typeof GNU extension. 00031 As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 00032 when compiling c++ source) this code uses whatever method is needed 00033 or, for VS2008 where neither is available, uses casting workarounds. */ 00034 #ifdef _MSC_VER /* MS compiler */ 00035 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 00036 #define DECLTYPE(x) (decltype(x)) 00037 #else /* VS2008 or older (or VS2010 in C mode) */ 00038 #define NO_DECLTYPE 00039 #define DECLTYPE(x) 00040 #endif 00041 #else /* GNU, Sun and other compilers */ 00042 #define DECLTYPE(x) (__typeof(x)) 00043 #endif 00044 00045 #ifdef NO_DECLTYPE 00046 #define DECLTYPE_ASSIGN(dst,src) \ 00047 do { \ 00048 char **_da_dst = (char**)(&(dst)); \ 00049 *_da_dst = (char*)(src); \ 00050 } while(0) 00051 #else 00052 #define DECLTYPE_ASSIGN(dst,src) \ 00053 do { \ 00054 (dst) = DECLTYPE(dst)(src); \ 00055 } while(0) 00056 #endif 00057 00058 /* a number of the hash function use uint32_t which isn't defined on win32 */ 00059 #ifdef _MSC_VER 00060 typedef unsigned int uint32_t; 00061 #else 00062 #include <inttypes.h> /* uint32_t */ 00063 #endif 00064 00065 #define UTHASH_VERSION 1.9.3 00066 00067 #define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ 00068 #define uthash_malloc(sz) malloc(sz) /* malloc fcn */ 00069 #define uthash_free(ptr,sz) free(ptr) /* free fcn */ 00070 00071 #define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ 00072 #define uthash_expand_fyi(tbl) /* can be defined to log expands */ 00073 00074 /* initial number of buckets */ 00075 #define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ 00076 #define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */ 00077 #define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ 00078 00079 /* calculate the element whose hash handle address is hhe */ 00080 #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) 00081 00082 #define HASH_FIND(hh,head,keyptr,keylen,out) \ 00083 do { \ 00084 unsigned _hf_bkt,_hf_hashv; \ 00085 out=NULL; \ 00086 if (head) { \ 00087 HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \ 00088 if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \ 00089 HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \ 00090 keyptr,keylen,out); \ 00091 } \ 00092 } \ 00093 } while (0) 00094 00095 #ifdef HASH_BLOOM 00096 #define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM) 00097 #define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0) 00098 #define HASH_BLOOM_MAKE(tbl) \ 00099 do { \ 00100 (tbl)->bloom_nbits = HASH_BLOOM; \ 00101 (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ 00102 if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ 00103 memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ 00104 (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ 00105 } while (0); 00106 00107 #define HASH_BLOOM_FREE(tbl) \ 00108 do { \ 00109 uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ 00110 } while (0); 00111 00112 #define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8))) 00113 #define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8))) 00114 00115 #define HASH_BLOOM_ADD(tbl,hashv) \ 00116 HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) 00117 00118 #define HASH_BLOOM_TEST(tbl,hashv) \ 00119 HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) 00120 00121 #else 00122 #define HASH_BLOOM_MAKE(tbl) 00123 #define HASH_BLOOM_FREE(tbl) 00124 #define HASH_BLOOM_ADD(tbl,hashv) 00125 #define HASH_BLOOM_TEST(tbl,hashv) (1) 00126 #endif 00127 00128 #define HASH_MAKE_TABLE(hh,head) \ 00129 do { \ 00130 (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ 00131 sizeof(UT_hash_table)); \ 00132 if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ 00133 memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ 00134 (head)->hh.tbl->tail = &((head)->hh); \ 00135 (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ 00136 (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ 00137 (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ 00138 (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ 00139 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 00140 if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ 00141 memset((head)->hh.tbl->buckets, 0, \ 00142 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 00143 HASH_BLOOM_MAKE((head)->hh.tbl); \ 00144 (head)->hh.tbl->signature = HASH_SIGNATURE; \ 00145 } while(0) 00146 00147 #define HASH_ADD(hh,head,fieldname,keylen_in,add) \ 00148 HASH_ADD_KEYPTR(hh,head,&add->fieldname,keylen_in,add) 00149 00150 #define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ 00151 do { \ 00152 unsigned _ha_bkt; \ 00153 (add)->hh.next = NULL; \ 00154 (add)->hh.key = (char*)keyptr; \ 00155 (add)->hh.keylen = keylen_in; \ 00156 if (!(head)) { \ 00157 head = (add); \ 00158 (head)->hh.prev = NULL; \ 00159 HASH_MAKE_TABLE(hh,head); \ 00160 } else { \ 00161 (head)->hh.tbl->tail->next = (add); \ 00162 (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ 00163 (head)->hh.tbl->tail = &((add)->hh); \ 00164 } \ 00165 (head)->hh.tbl->num_items++; \ 00166 (add)->hh.tbl = (head)->hh.tbl; \ 00167 HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \ 00168 (add)->hh.hashv, _ha_bkt); \ 00169 HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \ 00170 HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \ 00171 HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ 00172 HASH_FSCK(hh,head); \ 00173 } while(0) 00174 00175 #define HASH_TO_BKT( hashv, num_bkts, bkt ) \ 00176 do { \ 00177 bkt = ((hashv) & ((num_bkts) - 1)); \ 00178 } while(0) 00179 00180 /* delete "delptr" from the hash table. 00181 * "the usual" patch-up process for the app-order doubly-linked-list. 00182 * The use of _hd_hh_del below deserves special explanation. 00183 * These used to be expressed using (delptr) but that led to a bug 00184 * if someone used the same symbol for the head and deletee, like 00185 * HASH_DELETE(hh,users,users); 00186 * We want that to work, but by changing the head (users) below 00187 * we were forfeiting our ability to further refer to the deletee (users) 00188 * in the patch-up process. Solution: use scratch space to 00189 * copy the deletee pointer, then the latter references are via that 00190 * scratch pointer rather than through the repointed (users) symbol. 00191 */ 00192 #define HASH_DELETE(hh,head,delptr) \ 00193 do { \ 00194 unsigned _hd_bkt; \ 00195 struct UT_hash_handle *_hd_hh_del; \ 00196 if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ 00197 uthash_free((head)->hh.tbl->buckets, \ 00198 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 00199 HASH_BLOOM_FREE((head)->hh.tbl); \ 00200 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 00201 head = NULL; \ 00202 } else { \ 00203 _hd_hh_del = &((delptr)->hh); \ 00204 if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ 00205 (head)->hh.tbl->tail = \ 00206 (UT_hash_handle*)((char*)((delptr)->hh.prev) + \ 00207 (head)->hh.tbl->hho); \ 00208 } \ 00209 if ((delptr)->hh.prev) { \ 00210 ((UT_hash_handle*)((char*)((delptr)->hh.prev) + \ 00211 (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ 00212 } else { \ 00213 DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ 00214 } \ 00215 if (_hd_hh_del->next) { \ 00216 ((UT_hash_handle*)((char*)_hd_hh_del->next + \ 00217 (head)->hh.tbl->hho))->prev = \ 00218 _hd_hh_del->prev; \ 00219 } \ 00220 HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ 00221 HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ 00222 (head)->hh.tbl->num_items--; \ 00223 } \ 00224 HASH_FSCK(hh,head); \ 00225 } while (0) 00226 00227 00228 /* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ 00229 #define HASH_FIND_STR(head,findstr,out) \ 00230 HASH_FIND(hh,head,findstr,strlen(findstr),out) 00231 #define HASH_ADD_STR(head,strfield,add) \ 00232 HASH_ADD(hh,head,strfield,strlen(add->strfield),add) 00233 #define HASH_FIND_INT(head,findint,out) \ 00234 HASH_FIND(hh,head,findint,sizeof(int),out) 00235 #define HASH_ADD_INT(head,intfield,add) \ 00236 HASH_ADD(hh,head,intfield,sizeof(int),add) 00237 #define HASH_FIND_PTR(head,findptr,out) \ 00238 HASH_FIND(hh,head,findptr,sizeof(void *),out) 00239 #define HASH_ADD_PTR(head,ptrfield,add) \ 00240 HASH_ADD(hh,head,ptrfield,sizeof(void *),add) 00241 #define HASH_DEL(head,delptr) \ 00242 HASH_DELETE(hh,head,delptr) 00243 00244 /* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. 00245 * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. 00246 */ 00247 #ifdef HASH_DEBUG 00248 #define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) 00249 #define HASH_FSCK(hh,head) \ 00250 do { \ 00251 unsigned _bkt_i; \ 00252 unsigned _count, _bkt_count; \ 00253 char *_prev; \ 00254 struct UT_hash_handle *_thh; \ 00255 if (head) { \ 00256 _count = 0; \ 00257 for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ 00258 _bkt_count = 0; \ 00259 _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ 00260 _prev = NULL; \ 00261 while (_thh) { \ 00262 if (_prev != (char*)(_thh->hh_prev)) { \ 00263 HASH_OOPS("invalid hh_prev %p, actual %p\n", \ 00264 _thh->hh_prev, _prev ); \ 00265 } \ 00266 _bkt_count++; \ 00267 _prev = (char*)(_thh); \ 00268 _thh = _thh->hh_next; \ 00269 } \ 00270 _count += _bkt_count; \ 00271 if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ 00272 HASH_OOPS("invalid bucket count %d, actual %d\n", \ 00273 (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ 00274 } \ 00275 } \ 00276 if (_count != (head)->hh.tbl->num_items) { \ 00277 HASH_OOPS("invalid hh item count %d, actual %d\n", \ 00278 (head)->hh.tbl->num_items, _count ); \ 00279 } \ 00280 /* traverse hh in app order; check next/prev integrity, count */ \ 00281 _count = 0; \ 00282 _prev = NULL; \ 00283 _thh = &(head)->hh; \ 00284 while (_thh) { \ 00285 _count++; \ 00286 if (_prev !=(char*)(_thh->prev)) { \ 00287 HASH_OOPS("invalid prev %p, actual %p\n", \ 00288 _thh->prev, _prev ); \ 00289 } \ 00290 _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ 00291 _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ 00292 (head)->hh.tbl->hho) : NULL ); \ 00293 } \ 00294 if (_count != (head)->hh.tbl->num_items) { \ 00295 HASH_OOPS("invalid app item count %d, actual %d\n", \ 00296 (head)->hh.tbl->num_items, _count ); \ 00297 } \ 00298 } \ 00299 } while (0) 00300 #else 00301 #define HASH_FSCK(hh,head) 00302 #endif 00303 00304 /* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to 00305 * the descriptor to which this macro is defined for tuning the hash function. 00306 * The app can #include <unistd.h> to get the prototype for write(2). */ 00307 #ifdef HASH_EMIT_KEYS 00308 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ 00309 do { \ 00310 unsigned _klen = fieldlen; \ 00311 write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ 00312 write(HASH_EMIT_KEYS, keyptr, fieldlen); \ 00313 } while (0) 00314 #else 00315 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) 00316 #endif 00317 00318 /* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ 00319 #ifdef HASH_FUNCTION 00320 #define HASH_FCN HASH_FUNCTION 00321 #else 00322 #define HASH_FCN HASH_JEN 00323 #endif 00324 00325 /* The Bernstein hash function, used in Perl prior to v5.6 */ 00326 #define HASH_BER(key,keylen,num_bkts,hashv,bkt) \ 00327 do { \ 00328 unsigned _hb_keylen=keylen; \ 00329 char *_hb_key=(char*)(key); \ 00330 (hashv) = 0; \ 00331 while (_hb_keylen--) { (hashv) = ((hashv) * 33) + *_hb_key++; } \ 00332 bkt = (hashv) & (num_bkts-1); \ 00333 } while (0) 00334 00335 00336 /* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at 00337 * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ 00338 #define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \ 00339 do { \ 00340 unsigned _sx_i; \ 00341 char *_hs_key=(char*)(key); \ 00342 hashv = 0; \ 00343 for(_sx_i=0; _sx_i < keylen; _sx_i++) \ 00344 hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ 00345 bkt = hashv & (num_bkts-1); \ 00346 } while (0) 00347 00348 #define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \ 00349 do { \ 00350 unsigned _fn_i; \ 00351 char *_hf_key=(char*)(key); \ 00352 hashv = 2166136261UL; \ 00353 for(_fn_i=0; _fn_i < keylen; _fn_i++) \ 00354 hashv = (hashv * 16777619) ^ _hf_key[_fn_i]; \ 00355 bkt = hashv & (num_bkts-1); \ 00356 } while(0); 00357 00358 #define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \ 00359 do { \ 00360 unsigned _ho_i; \ 00361 char *_ho_key=(char*)(key); \ 00362 hashv = 0; \ 00363 for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ 00364 hashv += _ho_key[_ho_i]; \ 00365 hashv += (hashv << 10); \ 00366 hashv ^= (hashv >> 6); \ 00367 } \ 00368 hashv += (hashv << 3); \ 00369 hashv ^= (hashv >> 11); \ 00370 hashv += (hashv << 15); \ 00371 bkt = hashv & (num_bkts-1); \ 00372 } while(0) 00373 00374 #define HASH_JEN_MIX(a,b,c) \ 00375 do { \ 00376 a -= b; a -= c; a ^= ( c >> 13 ); \ 00377 b -= c; b -= a; b ^= ( a << 8 ); \ 00378 c -= a; c -= b; c ^= ( b >> 13 ); \ 00379 a -= b; a -= c; a ^= ( c >> 12 ); \ 00380 b -= c; b -= a; b ^= ( a << 16 ); \ 00381 c -= a; c -= b; c ^= ( b >> 5 ); \ 00382 a -= b; a -= c; a ^= ( c >> 3 ); \ 00383 b -= c; b -= a; b ^= ( a << 10 ); \ 00384 c -= a; c -= b; c ^= ( b >> 15 ); \ 00385 } while (0) 00386 00387 #define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \ 00388 do { \ 00389 unsigned _hj_i,_hj_j,_hj_k; \ 00390 char *_hj_key=(char*)(key); \ 00391 hashv = 0xfeedbeef; \ 00392 _hj_i = _hj_j = 0x9e3779b9; \ 00393 _hj_k = keylen; \ 00394 while (_hj_k >= 12) { \ 00395 _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ 00396 + ( (unsigned)_hj_key[2] << 16 ) \ 00397 + ( (unsigned)_hj_key[3] << 24 ) ); \ 00398 _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ 00399 + ( (unsigned)_hj_key[6] << 16 ) \ 00400 + ( (unsigned)_hj_key[7] << 24 ) ); \ 00401 hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ 00402 + ( (unsigned)_hj_key[10] << 16 ) \ 00403 + ( (unsigned)_hj_key[11] << 24 ) ); \ 00404 \ 00405 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 00406 \ 00407 _hj_key += 12; \ 00408 _hj_k -= 12; \ 00409 } \ 00410 hashv += keylen; \ 00411 switch ( _hj_k ) { \ 00412 case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \ 00413 case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \ 00414 case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \ 00415 case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \ 00416 case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \ 00417 case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \ 00418 case 5: _hj_j += _hj_key[4]; \ 00419 case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \ 00420 case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \ 00421 case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \ 00422 case 1: _hj_i += _hj_key[0]; \ 00423 } \ 00424 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 00425 bkt = hashv & (num_bkts-1); \ 00426 } while(0) 00427 00428 /* The Paul Hsieh hash function */ 00429 #undef get16bits 00430 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 00431 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 00432 #define get16bits(d) (*((const uint16_t *) (d))) 00433 #endif 00434 00435 #if !defined (get16bits) 00436 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ 00437 +(uint32_t)(((const uint8_t *)(d))[0]) ) 00438 #endif 00439 #define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \ 00440 do { \ 00441 char *_sfh_key=(char*)(key); \ 00442 uint32_t _sfh_tmp, _sfh_len = keylen; \ 00443 \ 00444 int _sfh_rem = _sfh_len & 3; \ 00445 _sfh_len >>= 2; \ 00446 hashv = 0xcafebabe; \ 00447 \ 00448 /* Main loop */ \ 00449 for (;_sfh_len > 0; _sfh_len--) { \ 00450 hashv += get16bits (_sfh_key); \ 00451 _sfh_tmp = (get16bits (_sfh_key+2) << 11) ^ hashv; \ 00452 hashv = (hashv << 16) ^ _sfh_tmp; \ 00453 _sfh_key += 2*sizeof (uint16_t); \ 00454 hashv += hashv >> 11; \ 00455 } \ 00456 \ 00457 /* Handle end cases */ \ 00458 switch (_sfh_rem) { \ 00459 case 3: hashv += get16bits (_sfh_key); \ 00460 hashv ^= hashv << 16; \ 00461 hashv ^= _sfh_key[sizeof (uint16_t)] << 18; \ 00462 hashv += hashv >> 11; \ 00463 break; \ 00464 case 2: hashv += get16bits (_sfh_key); \ 00465 hashv ^= hashv << 11; \ 00466 hashv += hashv >> 17; \ 00467 break; \ 00468 case 1: hashv += *_sfh_key; \ 00469 hashv ^= hashv << 10; \ 00470 hashv += hashv >> 1; \ 00471 } \ 00472 \ 00473 /* Force "avalanching" of final 127 bits */ \ 00474 hashv ^= hashv << 3; \ 00475 hashv += hashv >> 5; \ 00476 hashv ^= hashv << 4; \ 00477 hashv += hashv >> 17; \ 00478 hashv ^= hashv << 25; \ 00479 hashv += hashv >> 6; \ 00480 bkt = hashv & (num_bkts-1); \ 00481 } while(0); 00482 00483 #ifdef HASH_USING_NO_STRICT_ALIASING 00484 /* The MurmurHash exploits some CPU's (e.g. x86) tolerance for unaligned reads. 00485 * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. 00486 * So MurmurHash comes in two versions, the faster unaligned one and the slower 00487 * aligned one. We only use the faster one on CPU's where we know it's safe. 00488 * 00489 * Note the preprocessor built-in defines can be emitted using: 00490 * 00491 * gcc -m64 -dM -E - < /dev/null (on gcc) 00492 * cc -## a.c (where a.c is a simple test file) (Sun Studio) 00493 */ 00494 #if (defined(__i386__) || defined(__x86_64__)) 00495 #define HASH_MUR HASH_MUR_UNALIGNED 00496 #else 00497 #define HASH_MUR HASH_MUR_ALIGNED 00498 #endif 00499 00500 /* Appleby's MurmurHash fast version for unaligned-tolerant archs like i386 */ 00501 #define HASH_MUR_UNALIGNED(key,keylen,num_bkts,hashv,bkt) \ 00502 do { \ 00503 const unsigned int _mur_m = 0x5bd1e995; \ 00504 const int _mur_r = 24; \ 00505 hashv = 0xcafebabe ^ keylen; \ 00506 char *_mur_key = (char *)(key); \ 00507 uint32_t _mur_tmp, _mur_len = keylen; \ 00508 \ 00509 for (;_mur_len >= 4; _mur_len-=4) { \ 00510 _mur_tmp = *(uint32_t *)_mur_key; \ 00511 _mur_tmp *= _mur_m; \ 00512 _mur_tmp ^= _mur_tmp >> _mur_r; \ 00513 _mur_tmp *= _mur_m; \ 00514 hashv *= _mur_m; \ 00515 hashv ^= _mur_tmp; \ 00516 _mur_key += 4; \ 00517 } \ 00518 \ 00519 switch(_mur_len) \ 00520 { \ 00521 case 3: hashv ^= _mur_key[2] << 16; \ 00522 case 2: hashv ^= _mur_key[1] << 8; \ 00523 case 1: hashv ^= _mur_key[0]; \ 00524 hashv *= _mur_m; \ 00525 }; \ 00526 \ 00527 hashv ^= hashv >> 13; \ 00528 hashv *= _mur_m; \ 00529 hashv ^= hashv >> 15; \ 00530 \ 00531 bkt = hashv & (num_bkts-1); \ 00532 } while(0) 00533 00534 /* Appleby's MurmurHash version for alignment-sensitive archs like Sparc */ 00535 #define HASH_MUR_ALIGNED(key,keylen,num_bkts,hashv,bkt) \ 00536 do { \ 00537 const unsigned int _mur_m = 0x5bd1e995; \ 00538 const int _mur_r = 24; \ 00539 hashv = 0xcafebabe ^ (keylen); \ 00540 char *_mur_key = (char *)(key); \ 00541 uint32_t _mur_len = keylen; \ 00542 int _mur_align = (int)_mur_key & 3; \ 00543 \ 00544 if (_mur_align && (_mur_len >= 4)) { \ 00545 unsigned _mur_t = 0, _mur_d = 0; \ 00546 switch(_mur_align) { \ 00547 case 1: _mur_t |= _mur_key[2] << 16; \ 00548 case 2: _mur_t |= _mur_key[1] << 8; \ 00549 case 3: _mur_t |= _mur_key[0]; \ 00550 } \ 00551 _mur_t <<= (8 * _mur_align); \ 00552 _mur_key += 4-_mur_align; \ 00553 _mur_len -= 4-_mur_align; \ 00554 int _mur_sl = 8 * (4-_mur_align); \ 00555 int _mur_sr = 8 * _mur_align; \ 00556 \ 00557 for (;_mur_len >= 4; _mur_len-=4) { \ 00558 _mur_d = *(unsigned *)_mur_key; \ 00559 _mur_t = (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ 00560 unsigned _mur_k = _mur_t; \ 00561 _mur_k *= _mur_m; \ 00562 _mur_k ^= _mur_k >> _mur_r; \ 00563 _mur_k *= _mur_m; \ 00564 hashv *= _mur_m; \ 00565 hashv ^= _mur_k; \ 00566 _mur_t = _mur_d; \ 00567 _mur_key += 4; \ 00568 } \ 00569 _mur_d = 0; \ 00570 if(_mur_len >= _mur_align) { \ 00571 switch(_mur_align) { \ 00572 case 3: _mur_d |= _mur_key[2] << 16; \ 00573 case 2: _mur_d |= _mur_key[1] << 8; \ 00574 case 1: _mur_d |= _mur_key[0]; \ 00575 } \ 00576 unsigned _mur_k = (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ 00577 _mur_k *= _mur_m; \ 00578 _mur_k ^= _mur_k >> _mur_r; \ 00579 _mur_k *= _mur_m; \ 00580 hashv *= _mur_m; \ 00581 hashv ^= _mur_k; \ 00582 _mur_k += _mur_align; \ 00583 _mur_len -= _mur_align; \ 00584 \ 00585 switch(_mur_len) \ 00586 { \ 00587 case 3: hashv ^= _mur_key[2] << 16; \ 00588 case 2: hashv ^= _mur_key[1] << 8; \ 00589 case 1: hashv ^= _mur_key[0]; \ 00590 hashv *= _mur_m; \ 00591 } \ 00592 } else { \ 00593 switch(_mur_len) \ 00594 { \ 00595 case 3: _mur_d ^= _mur_key[2] << 16; \ 00596 case 2: _mur_d ^= _mur_key[1] << 8; \ 00597 case 1: _mur_d ^= _mur_key[0]; \ 00598 case 0: hashv ^= (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ 00599 hashv *= _mur_m; \ 00600 } \ 00601 } \ 00602 \ 00603 hashv ^= hashv >> 13; \ 00604 hashv *= _mur_m; \ 00605 hashv ^= hashv >> 15; \ 00606 } else { \ 00607 for (;_mur_len >= 4; _mur_len-=4) { \ 00608 unsigned _mur_k = *(unsigned*)_mur_key; \ 00609 _mur_k *= _mur_m; \ 00610 _mur_k ^= _mur_k >> _mur_r; \ 00611 _mur_k *= _mur_m; \ 00612 hashv *= _mur_m; \ 00613 hashv ^= _mur_k; \ 00614 _mur_key += 4; \ 00615 } \ 00616 switch(_mur_len) \ 00617 { \ 00618 case 3: hashv ^= _mur_key[2] << 16; \ 00619 case 2: hashv ^= _mur_key[1] << 8; \ 00620 case 1: hashv ^= _mur_key[0]; \ 00621 hashv *= _mur_m; \ 00622 } \ 00623 \ 00624 hashv ^= hashv >> 13; \ 00625 hashv *= _mur_m; \ 00626 hashv ^= hashv >> 15; \ 00627 } \ 00628 bkt = hashv & (num_bkts-1); \ 00629 } while(0) 00630 #endif /* HASH_USING_NO_STRICT_ALIASING */ 00631 00632 /* key comparison function; return 0 if keys equal */ 00633 #define HASH_KEYCMP(a,b,len) memcmp(a,b,len) 00634 00635 /* iterate over items in a known bucket to find desired item */ 00636 #define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ 00637 do { \ 00638 if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ 00639 else out=NULL; \ 00640 while (out) { \ 00641 if (out->hh.keylen == keylen_in) { \ 00642 if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \ 00643 } \ 00644 if (out->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,out->hh.hh_next)); \ 00645 else out = NULL; \ 00646 } \ 00647 } while(0) 00648 00649 /* add an item to a bucket */ 00650 #define HASH_ADD_TO_BKT(head,addhh) \ 00651 do { \ 00652 head.count++; \ 00653 (addhh)->hh_next = head.hh_head; \ 00654 (addhh)->hh_prev = NULL; \ 00655 if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ 00656 (head).hh_head=addhh; \ 00657 if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ 00658 && (addhh)->tbl->noexpand != 1) { \ 00659 HASH_EXPAND_BUCKETS((addhh)->tbl); \ 00660 } \ 00661 } while(0) 00662 00663 /* remove an item from a given bucket */ 00664 #define HASH_DEL_IN_BKT(hh,head,hh_del) \ 00665 (head).count--; \ 00666 if ((head).hh_head == hh_del) { \ 00667 (head).hh_head = hh_del->hh_next; \ 00668 } \ 00669 if (hh_del->hh_prev) { \ 00670 hh_del->hh_prev->hh_next = hh_del->hh_next; \ 00671 } \ 00672 if (hh_del->hh_next) { \ 00673 hh_del->hh_next->hh_prev = hh_del->hh_prev; \ 00674 } 00675 00676 /* Bucket expansion has the effect of doubling the number of buckets 00677 * and redistributing the items into the new buckets. Ideally the 00678 * items will distribute more or less evenly into the new buckets 00679 * (the extent to which this is true is a measure of the quality of 00680 * the hash function as it applies to the key domain). 00681 * 00682 * With the items distributed into more buckets, the chain length 00683 * (item count) in each bucket is reduced. Thus by expanding buckets 00684 * the hash keeps a bound on the chain length. This bounded chain 00685 * length is the essence of how a hash provides constant time lookup. 00686 * 00687 * The calculation of tbl->ideal_chain_maxlen below deserves some 00688 * explanation. First, keep in mind that we're calculating the ideal 00689 * maximum chain length based on the *new* (doubled) bucket count. 00690 * In fractions this is just n/b (n=number of items,b=new num buckets). 00691 * Since the ideal chain length is an integer, we want to calculate 00692 * ceil(n/b). We don't depend on floating point arithmetic in this 00693 * hash, so to calculate ceil(n/b) with integers we could write 00694 * 00695 * ceil(n/b) = (n/b) + ((n%b)?1:0) 00696 * 00697 * and in fact a previous version of this hash did just that. 00698 * But now we have improved things a bit by recognizing that b is 00699 * always a power of two. We keep its base 2 log handy (call it lb), 00700 * so now we can write this with a bit shift and logical AND: 00701 * 00702 * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) 00703 * 00704 */ 00705 #define HASH_EXPAND_BUCKETS(tbl) \ 00706 do { \ 00707 unsigned _he_bkt; \ 00708 unsigned _he_bkt_i; \ 00709 struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ 00710 UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ 00711 _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ 00712 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 00713 if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ 00714 memset(_he_new_buckets, 0, \ 00715 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 00716 tbl->ideal_chain_maxlen = \ 00717 (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ 00718 ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ 00719 tbl->nonideal_items = 0; \ 00720 for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ 00721 { \ 00722 _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ 00723 while (_he_thh) { \ 00724 _he_hh_nxt = _he_thh->hh_next; \ 00725 HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ 00726 _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ 00727 if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ 00728 tbl->nonideal_items++; \ 00729 _he_newbkt->expand_mult = _he_newbkt->count / \ 00730 tbl->ideal_chain_maxlen; \ 00731 } \ 00732 _he_thh->hh_prev = NULL; \ 00733 _he_thh->hh_next = _he_newbkt->hh_head; \ 00734 if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ 00735 _he_thh; \ 00736 _he_newbkt->hh_head = _he_thh; \ 00737 _he_thh = _he_hh_nxt; \ 00738 } \ 00739 } \ 00740 uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ 00741 tbl->num_buckets *= 2; \ 00742 tbl->log2_num_buckets++; \ 00743 tbl->buckets = _he_new_buckets; \ 00744 tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ 00745 (tbl->ineff_expands+1) : 0; \ 00746 if (tbl->ineff_expands > 1) { \ 00747 tbl->noexpand=1; \ 00748 uthash_noexpand_fyi(tbl); \ 00749 } \ 00750 uthash_expand_fyi(tbl); \ 00751 } while(0) 00752 00753 00754 /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ 00755 /* Note that HASH_SORT assumes the hash handle name to be hh. 00756 * HASH_SRT was added to allow the hash handle name to be passed in. */ 00757 #define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) 00758 #define HASH_SRT(hh,head,cmpfcn) \ 00759 do { \ 00760 unsigned _hs_i; \ 00761 unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ 00762 struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ 00763 if (head) { \ 00764 _hs_insize = 1; \ 00765 _hs_looping = 1; \ 00766 _hs_list = &((head)->hh); \ 00767 while (_hs_looping) { \ 00768 _hs_p = _hs_list; \ 00769 _hs_list = NULL; \ 00770 _hs_tail = NULL; \ 00771 _hs_nmerges = 0; \ 00772 while (_hs_p) { \ 00773 _hs_nmerges++; \ 00774 _hs_q = _hs_p; \ 00775 _hs_psize = 0; \ 00776 for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ 00777 _hs_psize++; \ 00778 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 00779 ((void*)((char*)(_hs_q->next) + \ 00780 (head)->hh.tbl->hho)) : NULL); \ 00781 if (! (_hs_q) ) break; \ 00782 } \ 00783 _hs_qsize = _hs_insize; \ 00784 while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ 00785 if (_hs_psize == 0) { \ 00786 _hs_e = _hs_q; \ 00787 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 00788 ((void*)((char*)(_hs_q->next) + \ 00789 (head)->hh.tbl->hho)) : NULL); \ 00790 _hs_qsize--; \ 00791 } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ 00792 _hs_e = _hs_p; \ 00793 _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 00794 ((void*)((char*)(_hs_p->next) + \ 00795 (head)->hh.tbl->hho)) : NULL); \ 00796 _hs_psize--; \ 00797 } else if (( \ 00798 cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ 00799 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ 00800 ) <= 0) { \ 00801 _hs_e = _hs_p; \ 00802 _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ 00803 ((void*)((char*)(_hs_p->next) + \ 00804 (head)->hh.tbl->hho)) : NULL); \ 00805 _hs_psize--; \ 00806 } else { \ 00807 _hs_e = _hs_q; \ 00808 _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ 00809 ((void*)((char*)(_hs_q->next) + \ 00810 (head)->hh.tbl->hho)) : NULL); \ 00811 _hs_qsize--; \ 00812 } \ 00813 if ( _hs_tail ) { \ 00814 _hs_tail->next = ((_hs_e) ? \ 00815 ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ 00816 } else { \ 00817 _hs_list = _hs_e; \ 00818 } \ 00819 _hs_e->prev = ((_hs_tail) ? \ 00820 ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ 00821 _hs_tail = _hs_e; \ 00822 } \ 00823 _hs_p = _hs_q; \ 00824 } \ 00825 _hs_tail->next = NULL; \ 00826 if ( _hs_nmerges <= 1 ) { \ 00827 _hs_looping=0; \ 00828 (head)->hh.tbl->tail = _hs_tail; \ 00829 DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ 00830 } \ 00831 _hs_insize *= 2; \ 00832 } \ 00833 HASH_FSCK(hh,head); \ 00834 } \ 00835 } while (0) 00836 00837 /* This function selects items from one hash into another hash. 00838 * The end result is that the selected items have dual presence 00839 * in both hashes. There is no copy of the items made; rather 00840 * they are added into the new hash through a secondary hash 00841 * hash handle that must be present in the structure. */ 00842 #define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ 00843 do { \ 00844 unsigned _src_bkt, _dst_bkt; \ 00845 void *_last_elt=NULL, *_elt; \ 00846 UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ 00847 ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ 00848 if (src) { \ 00849 for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ 00850 for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ 00851 _src_hh; \ 00852 _src_hh = _src_hh->hh_next) { \ 00853 _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ 00854 if (cond(_elt)) { \ 00855 _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ 00856 _dst_hh->key = _src_hh->key; \ 00857 _dst_hh->keylen = _src_hh->keylen; \ 00858 _dst_hh->hashv = _src_hh->hashv; \ 00859 _dst_hh->prev = _last_elt; \ 00860 _dst_hh->next = NULL; \ 00861 if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ 00862 if (!dst) { \ 00863 DECLTYPE_ASSIGN(dst,_elt); \ 00864 HASH_MAKE_TABLE(hh_dst,dst); \ 00865 } else { \ 00866 _dst_hh->tbl = (dst)->hh_dst.tbl; \ 00867 } \ 00868 HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ 00869 HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ 00870 (dst)->hh_dst.tbl->num_items++; \ 00871 _last_elt = _elt; \ 00872 _last_elt_hh = _dst_hh; \ 00873 } \ 00874 } \ 00875 } \ 00876 } \ 00877 HASH_FSCK(hh_dst,dst); \ 00878 } while (0) 00879 00880 #define HASH_CLEAR(hh,head) \ 00881 do { \ 00882 if (head) { \ 00883 uthash_free((head)->hh.tbl->buckets, \ 00884 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ 00885 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 00886 (head)=NULL; \ 00887 } \ 00888 } while(0) 00889 00890 #ifdef NO_DECLTYPE 00891 #define HASH_ITER(hh,head,el,tmp) \ 00892 for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ 00893 el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) 00894 #else 00895 #define HASH_ITER(hh,head,el,tmp) \ 00896 for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ 00897 el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) 00898 #endif 00899 00900 /* obtain a count of items in the hash */ 00901 #define HASH_COUNT(head) HASH_CNT(hh,head) 00902 #define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) 00903 00904 typedef struct UT_hash_bucket { 00905 struct UT_hash_handle *hh_head; 00906 unsigned count; 00907 00908 /* expand_mult is normally set to 0. In this situation, the max chain length 00909 * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If 00910 * the bucket's chain exceeds this length, bucket expansion is triggered). 00911 * However, setting expand_mult to a non-zero value delays bucket expansion 00912 * (that would be triggered by additions to this particular bucket) 00913 * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. 00914 * (The multiplier is simply expand_mult+1). The whole idea of this 00915 * multiplier is to reduce bucket expansions, since they are expensive, in 00916 * situations where we know that a particular bucket tends to be overused. 00917 * It is better to let its chain length grow to a longer yet-still-bounded 00918 * value, than to do an O(n) bucket expansion too often. 00919 */ 00920 unsigned expand_mult; 00921 00922 } UT_hash_bucket; 00923 00924 /* random signature used only to find hash tables in external analysis */ 00925 #define HASH_SIGNATURE 0xa0111fe1 00926 #define HASH_BLOOM_SIGNATURE 0xb12220f2 00927 00928 typedef struct UT_hash_table { 00929 UT_hash_bucket *buckets; 00930 unsigned num_buckets, log2_num_buckets; 00931 unsigned num_items; 00932 struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ 00933 ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ 00934 00935 /* in an ideal situation (all buckets used equally), no bucket would have 00936 * more than ceil(#items/#buckets) items. that's the ideal chain length. */ 00937 unsigned ideal_chain_maxlen; 00938 00939 /* nonideal_items is the number of items in the hash whose chain position 00940 * exceeds the ideal chain maxlen. these items pay the penalty for an uneven 00941 * hash distribution; reaching them in a chain traversal takes >ideal steps */ 00942 unsigned nonideal_items; 00943 00944 /* ineffective expands occur when a bucket doubling was performed, but 00945 * afterward, more than half the items in the hash had nonideal chain 00946 * positions. If this happens on two consecutive expansions we inhibit any 00947 * further expansion, as it's not helping; this happens when the hash 00948 * function isn't a good fit for the key domain. When expansion is inhibited 00949 * the hash will still work, albeit no longer in constant time. */ 00950 unsigned ineff_expands, noexpand; 00951 00952 uint32_t signature; /* used only to find hash tables in external analysis */ 00953 #ifdef HASH_BLOOM 00954 uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ 00955 uint8_t *bloom_bv; 00956 char bloom_nbits; 00957 #endif 00958 00959 } UT_hash_table; 00960 00961 typedef struct UT_hash_handle { 00962 struct UT_hash_table *tbl; 00963 void *prev; /* prev element in app order */ 00964 void *next; /* next element in app order */ 00965 struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ 00966 struct UT_hash_handle *hh_next; /* next hh in bucket order */ 00967 void *key; /* ptr to enclosing struct's key */ 00968 unsigned keylen; /* enclosing struct's key len */ 00969 unsigned hashv; /* result of hash-fcn(key) */ 00970 } UT_hash_handle; 00971 00972 #endif /* UTHASH_H */
Generated on Thu Jul 14 2022 20:00:56 by
1.7.2