0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020
0021
0022
0023
0024
0025 #ifndef EXHASH_H
0026 #define EXHASH_H
0027
0028 #include <string.h> /* memcmp,strlen */
0029 #include <stddef.h> /* ptrdiff_t */
0030 #include <stdlib.h> /* exit() */
0031
0032
0033
0034
0035
0036
0037 #ifdef _MSC_VER
0038 #if _MSC_VER >= 1600 && defined(__cplusplus)
0039 #define DECLTYPE(x) (decltype(x))
0040 #else
0041 #define NO_DECLTYPE
0042 #define DECLTYPE(x)
0043 #endif
0044 #else
0045 #define DECLTYPE(x) (__typeof(x))
0046 #endif
0047
0048 #ifdef NO_DECLTYPE
0049 #define DECLTYPE_ASSIGN(dst,src) \
0050 do { \
0051 char **_da_dst = (char**)(&(dst)); \
0052 *_da_dst = (char*)(src); \
0053 } while(0)
0054 #else
0055 #define DECLTYPE_ASSIGN(dst,src) \
0056 do { \
0057 (dst) = DECLTYPE(dst)(src); \
0058 } while(0)
0059 #endif
0060
0061
0062 #ifdef _MSC_VER
0063 typedef unsigned int uint32_t;
0064 typedef unsigned char uint8_t;
0065 #else
0066 #include <inttypes.h> /* uint32_t */
0067 #endif
0068
0069 #define EXHASH_VERSION 1.9.4
0070
0071 #define exhash_fatal(msg) exit(-1)
0072 #define exhash_malloc(sz) NDRX_FPMALLOC(sz, 0)
0073 #define exhash_free(ptr,sz) NDRX_FPFREE(ptr)
0074
0075 #define exhash_noexpand_fyi(tbl)
0076 #define exhash_expand_fyi(tbl)
0077
0078
0079 #define EXHASH_INITIAL_NUM_BUCKETS 32
0080 #define EXHASH_INITIAL_NUM_BUCKETS_LOG2 5
0081 #define EXHASH_BKT_CAPACITY_THRESH 10
0082
0083
0084 #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho)))
0085
0086 #define EXHASH_FIND(hh,head,keyptr,keylen,out) \
0087 do { \
0088 unsigned _hf_bkt,_hf_hashv; \
0089 out=NULL; \
0090 if (head) { \
0091 EXHASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \
0092 if (EXHASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \
0093 EXHASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \
0094 keyptr,keylen,out); \
0095 } \
0096 } \
0097 } while (0)
0098
0099 #ifdef HASH_BLOOM
0100 #define EXHASH_BLOOM_BITLEN (1ULL << HASH_BLOOM)
0101 #define EXHASH_BLOOM_BYTELEN (EXHASH_BLOOM_BITLEN/8) + ((EXHASH_BLOOM_BITLEN%8) ? 1:0)
0102 #define EXHASH_BLOOM_MAKE(tbl) \
0103 do { \
0104 (tbl)->bloom_nbits = HASH_BLOOM; \
0105 (tbl)->bloom_bv = (uint8_t*)exhash_malloc(EXHASH_BLOOM_BYTELEN); \
0106 if (!((tbl)->bloom_bv)) { exhash_fatal( "out of memory"); } \
0107 memset((tbl)->bloom_bv, 0, EXHASH_BLOOM_BYTELEN); \
0108 (tbl)->bloom_sig = EXHASH_BLOOM_SIGNATURE; \
0109 } while (0);
0110
0111 #define EXHASH_BLOOM_FREE(tbl) \
0112 do { \
0113 exhash_free((tbl)->bloom_bv, EXHASH_BLOOM_BYTELEN); \
0114 } while (0);
0115
0116 #define EXHASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8)))
0117 #define EXHASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8)))
0118
0119 #define EXHASH_BLOOM_ADD(tbl,hashv) \
0120 EXHASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
0121
0122 #define EXHASH_BLOOM_TEST(tbl,hashv) \
0123 EXHASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1)))
0124
0125 #else
0126 #define EXHASH_BLOOM_MAKE(tbl)
0127 #define EXHASH_BLOOM_FREE(tbl)
0128 #define EXHASH_BLOOM_ADD(tbl,hashv)
0129 #define EXHASH_BLOOM_TEST(tbl,hashv) (1)
0130 #endif
0131
0132 #define EXHASH_MAKE_TABLE(hh,head) \
0133 do { \
0134 (head)->hh.tbl = (EX_hash_table*)exhash_malloc( \
0135 sizeof(EX_hash_table)); \
0136 if (!((head)->hh.tbl)) { exhash_fatal( "out of memory"); } \
0137 memset((head)->hh.tbl, 0, sizeof(EX_hash_table)); \
0138 (head)->hh.tbl->tail = &((head)->hh); \
0139 (head)->hh.tbl->num_buckets = EXHASH_INITIAL_NUM_BUCKETS; \
0140 (head)->hh.tbl->log2_num_buckets = EXHASH_INITIAL_NUM_BUCKETS_LOG2; \
0141 (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \
0142 (head)->hh.tbl->buckets = (EX_hash_bucket*)exhash_malloc( \
0143 EXHASH_INITIAL_NUM_BUCKETS*sizeof(struct EX_hash_bucket)); \
0144 if (! (head)->hh.tbl->buckets) { exhash_fatal( "out of memory"); } \
0145 memset((head)->hh.tbl->buckets, 0, \
0146 EXHASH_INITIAL_NUM_BUCKETS*sizeof(struct EX_hash_bucket)); \
0147 EXHASH_BLOOM_MAKE((head)->hh.tbl); \
0148 (head)->hh.tbl->signature = EXHASH_SIGNATURE; \
0149 } while(0)
0150
0151 #define EXHASH_ADD(hh,head,fieldname,keylen_in,add) \
0152 EXHASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add)
0153
0154 #define EXHASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \
0155 do { \
0156 unsigned _ha_bkt; \
0157 (add)->hh.next = NULL; \
0158 (add)->hh.key = (char*)keyptr; \
0159 (add)->hh.keylen = keylen_in; \
0160 if (!(head)) { \
0161 head = (add); \
0162 (head)->hh.prev = NULL; \
0163 EXHASH_MAKE_TABLE(hh,head); \
0164 } else { \
0165 (head)->hh.tbl->tail->next = (add); \
0166 (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \
0167 (head)->hh.tbl->tail = &((add)->hh); \
0168 } \
0169 (head)->hh.tbl->num_items++; \
0170 (add)->hh.tbl = (head)->hh.tbl; \
0171 EXHASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \
0172 (add)->hh.hashv, _ha_bkt); \
0173 EXHASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \
0174 EXHASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \
0175 EXHASH_EMIT_KEY(hh,head,keyptr,keylen_in); \
0176 EXHASH_FSCK(hh,head); \
0177 } while(0)
0178
0179 #define EXHASH_TO_BKT( hashv, num_bkts, bkt ) \
0180 do { \
0181 bkt = ((hashv) & ((num_bkts) - 1)); \
0182 } while(0)
0183
0184
0185
0186
0187
0188
0189
0190
0191
0192
0193
0194
0195
0196 #define EXHASH_DELETE(hh,head,delptr) \
0197 do { \
0198 unsigned _hd_bkt; \
0199 struct EX_hash_handle *_hd_hh_del; \
0200 if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \
0201 exhash_free((head)->hh.tbl->buckets, \
0202 (head)->hh.tbl->num_buckets*sizeof(struct EX_hash_bucket) ); \
0203 EXHASH_BLOOM_FREE((head)->hh.tbl); \
0204 exhash_free((head)->hh.tbl, sizeof(EX_hash_table)); \
0205 head = NULL; \
0206 } else { \
0207 _hd_hh_del = &((delptr)->hh); \
0208 if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \
0209 (head)->hh.tbl->tail = \
0210 (EX_hash_handle*)((char*)((delptr)->hh.prev) + \
0211 (head)->hh.tbl->hho); \
0212 } \
0213 if ((delptr)->hh.prev) { \
0214 ((EX_hash_handle*)((char*)((delptr)->hh.prev) + \
0215 (head)->hh.tbl->hho))->next = (delptr)->hh.next; \
0216 } else { \
0217 DECLTYPE_ASSIGN(head,(delptr)->hh.next); \
0218 } \
0219 if (_hd_hh_del->next) { \
0220 ((EX_hash_handle*)((char*)_hd_hh_del->next + \
0221 (head)->hh.tbl->hho))->prev = \
0222 _hd_hh_del->prev; \
0223 } \
0224 EXHASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \
0225 EXHASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \
0226 (head)->hh.tbl->num_items--; \
0227 } \
0228 EXHASH_FSCK(hh,head); \
0229 } while (0)
0230
0231
0232
0233 #define EXHASH_FIND_STR(head,findstr,out) \
0234 EXHASH_FIND(hh,head,findstr,strlen(findstr),out)
0235 #define EXHASH_ADD_STR(head,strfield,add) \
0236 EXHASH_ADD(hh,head,strfield,strlen(add->strfield),add)
0237 #define EXHASH_FIND_INT(head,findint,out) \
0238 EXHASH_FIND(hh,head,findint,sizeof(int),out)
0239 #define EXHASH_ADD_INT(head,intfield,add) \
0240 EXHASH_ADD(hh,head,intfield,sizeof(int),add)
0241 #define EXHASH_FIND_LONG(head,findlong,out) \
0242 EXHASH_FIND(hh,head,findlong,sizeof(long),out)
0243 #define EXHASH_ADD_LONG(head,longfield,add) \
0244 EXHASH_ADD(hh,head,longfield,sizeof(long),add)
0245 #define EXHASH_FIND_PTR(head,findptr,out) \
0246 EXHASH_FIND(hh,head,findptr,sizeof(void *),out)
0247 #define EXHASH_ADD_PTR(head,ptrfield,add) \
0248 EXHASH_ADD(hh,head,ptrfield,sizeof(void *),add)
0249 #define EXHASH_DEL(head,delptr) \
0250 EXHASH_DELETE(hh,head,delptr)
0251
0252
0253
0254
0255 #ifdef HASH_DEBUG
0256 #define EXHASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0)
0257 #define EXHASH_FSCK(hh,head) \
0258 do { \
0259 unsigned _bkt_i; \
0260 unsigned _count, _bkt_count; \
0261 char *_prev; \
0262 struct EX_hash_handle *_thh; \
0263 if (head) { \
0264 _count = 0; \
0265 for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \
0266 _bkt_count = 0; \
0267 _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \
0268 _prev = NULL; \
0269 while (_thh) { \
0270 if (_prev != (char*)(_thh->hh_prev)) { \
0271 EXHASH_OOPS("invalid hh_prev %p, actual %p\n", \
0272 _thh->hh_prev, _prev ); \
0273 } \
0274 _bkt_count++; \
0275 _prev = (char*)(_thh); \
0276 _thh = _thh->hh_next; \
0277 } \
0278 _count += _bkt_count; \
0279 if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \
0280 EXHASH_OOPS("invalid bucket count %d, actual %d\n", \
0281 (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \
0282 } \
0283 } \
0284 if (_count != (head)->hh.tbl->num_items) { \
0285 EXHASH_OOPS("invalid hh item count %d, actual %d\n", \
0286 (head)->hh.tbl->num_items, _count ); \
0287 } \
0288 \
0289 _count = 0; \
0290 _prev = NULL; \
0291 _thh = &(head)->hh; \
0292 while (_thh) { \
0293 _count++; \
0294 if (_prev !=(char*)(_thh->prev)) { \
0295 EXHASH_OOPS("invalid prev %p, actual %p\n", \
0296 _thh->prev, _prev ); \
0297 } \
0298 _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \
0299 _thh = ( _thh->next ? (EX_hash_handle*)((char*)(_thh->next) + \
0300 (head)->hh.tbl->hho) : NULL ); \
0301 } \
0302 if (_count != (head)->hh.tbl->num_items) { \
0303 EXHASH_OOPS("invalid app item count %d, actual %d\n", \
0304 (head)->hh.tbl->num_items, _count ); \
0305 } \
0306 } \
0307 } while (0)
0308 #else
0309 #define EXHASH_FSCK(hh,head)
0310 #endif
0311
0312
0313
0314
0315 #ifdef EXHASH_EMIT_KEYS
0316 #define EXHASH_EMIT_KEY(hh,head,keyptr,fieldlen) \
0317 do { \
0318 unsigned _klen = fieldlen; \
0319 write(EXHASH_EMIT_KEYS, &_klen, sizeof(_klen)); \
0320 write(EXHASH_EMIT_KEYS, keyptr, fieldlen); \
0321 } while (0)
0322 #else
0323 #define EXHASH_EMIT_KEY(hh,head,keyptr,fieldlen)
0324 #endif
0325
0326
0327 #ifdef EXHASH_FUNCTION
0328 #define EXHASH_FCN EXHASH_FUNCTION
0329 #else
0330 #define EXHASH_FCN EXHASH_JEN
0331 #endif
0332
0333
0334 #define EXHASH_BER(key,keylen,num_bkts,hashv,bkt) \
0335 do { \
0336 unsigned _hb_keylen=keylen; \
0337 char *_hb_key=(char*)(key); \
0338 (hashv) = 0; \
0339 while (_hb_keylen--) { (hashv) = ((hashv) * 33) + *_hb_key++; } \
0340 bkt = (hashv) & (num_bkts-1); \
0341 } while (0)
0342
0343
0344
0345
0346 #define EXHASH_SAX(key,keylen,num_bkts,hashv,bkt) \
0347 do { \
0348 unsigned _sx_i; \
0349 char *_hs_key=(char*)(key); \
0350 hashv = 0; \
0351 for(_sx_i=0; _sx_i < keylen; _sx_i++) \
0352 hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \
0353 bkt = hashv & (num_bkts-1); \
0354 } while (0)
0355
0356 #define EXHASH_FNV(key,keylen,num_bkts,hashv,bkt) \
0357 do { \
0358 unsigned _fn_i; \
0359 char *_hf_key=(char*)(key); \
0360 hashv = 2166136261UL; \
0361 for(_fn_i=0; _fn_i < keylen; _fn_i++) \
0362 hashv = (hashv * 16777619) ^ _hf_key[_fn_i]; \
0363 bkt = hashv & (num_bkts-1); \
0364 } while(0);
0365
0366 #define EXHASH_OAT(key,keylen,num_bkts,hashv,bkt) \
0367 do { \
0368 unsigned _ho_i; \
0369 char *_ho_key=(char*)(key); \
0370 hashv = 0; \
0371 for(_ho_i=0; _ho_i < keylen; _ho_i++) { \
0372 hashv += _ho_key[_ho_i]; \
0373 hashv += (hashv << 10); \
0374 hashv ^= (hashv >> 6); \
0375 } \
0376 hashv += (hashv << 3); \
0377 hashv ^= (hashv >> 11); \
0378 hashv += (hashv << 15); \
0379 bkt = hashv & (num_bkts-1); \
0380 } while(0)
0381
0382 #define EXEXHASH_JEN_MIX(a,b,c) \
0383 do { \
0384 a -= b; a -= c; a ^= ( c >> 13 ); \
0385 b -= c; b -= a; b ^= ( a << 8 ); \
0386 c -= a; c -= b; c ^= ( b >> 13 ); \
0387 a -= b; a -= c; a ^= ( c >> 12 ); \
0388 b -= c; b -= a; b ^= ( a << 16 ); \
0389 c -= a; c -= b; c ^= ( b >> 5 ); \
0390 a -= b; a -= c; a ^= ( c >> 3 ); \
0391 b -= c; b -= a; b ^= ( a << 10 ); \
0392 c -= a; c -= b; c ^= ( b >> 15 ); \
0393 } while (0)
0394
0395 #define EXHASH_JEN(key,keylen,num_bkts,hashv,bkt) \
0396 do { \
0397 unsigned _hj_i,_hj_j,_hj_k; \
0398 char *_hj_key=(char*)(key); \
0399 hashv = 0xfeedbeef; \
0400 _hj_i = _hj_j = 0x9e3779b9; \
0401 _hj_k = keylen; \
0402 while (_hj_k >= 12) { \
0403 _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \
0404 + ( (unsigned)_hj_key[2] << 16 ) \
0405 + ( (unsigned)_hj_key[3] << 24 ) ); \
0406 _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \
0407 + ( (unsigned)_hj_key[6] << 16 ) \
0408 + ( (unsigned)_hj_key[7] << 24 ) ); \
0409 hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \
0410 + ( (unsigned)_hj_key[10] << 16 ) \
0411 + ( (unsigned)_hj_key[11] << 24 ) ); \
0412 \
0413 EXEXHASH_JEN_MIX(_hj_i, _hj_j, hashv); \
0414 \
0415 _hj_key += 12; \
0416 _hj_k -= 12; \
0417 } \
0418 hashv += keylen; \
0419 switch ( _hj_k ) { \
0420 case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \
0421 case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \
0422 case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \
0423 case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \
0424 case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \
0425 case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \
0426 case 5: _hj_j += _hj_key[4]; \
0427 case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \
0428 case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \
0429 case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \
0430 case 1: _hj_i += _hj_key[0]; \
0431 } \
0432 EXEXHASH_JEN_MIX(_hj_i, _hj_j, hashv); \
0433 bkt = hashv & (num_bkts-1); \
0434 } while(0)
0435
0436
0437 #undef get16bits
0438 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
0439 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
0440 #define get16bits(d) (*((const uint16_t *) (d)))
0441 #endif
0442
0443 #if !defined (get16bits)
0444 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
0445 +(uint32_t)(((const uint8_t *)(d))[0]) )
0446 #endif
0447 #define EXHASH_SFH(key,keylen,num_bkts,hashv,bkt) \
0448 do { \
0449 char *_sfh_key=(char*)(key); \
0450 uint32_t _sfh_tmp, _sfh_len = keylen; \
0451 \
0452 int _sfh_rem = _sfh_len & 3; \
0453 _sfh_len >>= 2; \
0454 hashv = 0xcafebabe; \
0455 \
0456 \
0457 for (;_sfh_len > 0; _sfh_len--) { \
0458 hashv += get16bits (_sfh_key); \
0459 _sfh_tmp = (get16bits (_sfh_key+2) << 11) ^ hashv; \
0460 hashv = (hashv << 16) ^ _sfh_tmp; \
0461 _sfh_key += 2*sizeof (uint16_t); \
0462 hashv += hashv >> 11; \
0463 } \
0464 \
0465 \
0466 switch (_sfh_rem) { \
0467 case 3: hashv += get16bits (_sfh_key); \
0468 hashv ^= hashv << 16; \
0469 hashv ^= _sfh_key[sizeof (uint16_t)] << 18; \
0470 hashv += hashv >> 11; \
0471 break; \
0472 case 2: hashv += get16bits (_sfh_key); \
0473 hashv ^= hashv << 11; \
0474 hashv += hashv >> 17; \
0475 break; \
0476 case 1: hashv += *_sfh_key; \
0477 hashv ^= hashv << 10; \
0478 hashv += hashv >> 1; \
0479 } \
0480 \
0481 \
0482 hashv ^= hashv << 3; \
0483 hashv += hashv >> 5; \
0484 hashv ^= hashv << 4; \
0485 hashv += hashv >> 17; \
0486 hashv ^= hashv << 25; \
0487 hashv += hashv >> 6; \
0488 bkt = hashv & (num_bkts-1); \
0489 } while(0);
0490
0491 #ifdef HASH_USING_NO_STRICT_ALIASING
0492
0493
0494
0495
0496
0497
0498
0499
0500
0501 #if (defined(__i386__) || defined(__x86_64__))
0502 #define MUR_GETBLOCK(p,i) p[i]
0503 #else
0504 #define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 0x3) == 0)
0505 #define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 0x3) == 1)
0506 #define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 0x3) == 2)
0507 #define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 0x3) == 3)
0508 #define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL))
0509 #if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__))
0510 #define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24))
0511 #define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16))
0512 #define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8))
0513 #else
0514 #define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24))
0515 #define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16))
0516 #define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8))
0517 #endif
0518 #define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \
0519 (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \
0520 (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \
0521 MUR_ONE_THREE(p))))
0522 #endif
0523 #define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
0524 #define MUR_FMIX(_h) \
0525 do { \
0526 _h ^= _h >> 16; \
0527 _h *= 0x85ebca6b; \
0528 _h ^= _h >> 13; \
0529 _h *= 0xc2b2ae35l; \
0530 _h ^= _h >> 16; \
0531 } while(0)
0532
0533 #define EXHASH_MUR(key,keylen,num_bkts,hashv,bkt) \
0534 do { \
0535 const uint8_t *_mur_data = (const uint8_t*)(key); \
0536 const int _mur_nblocks = (keylen) / 4; \
0537 uint32_t _mur_h1 = 0xf88D5353; \
0538 uint32_t _mur_c1 = 0xcc9e2d51; \
0539 uint32_t _mur_c2 = 0x1b873593; \
0540 const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+_mur_nblocks*4); \
0541 int _mur_i; \
0542 for(_mur_i = -_mur_nblocks; _mur_i; _mur_i++) { \
0543 uint32_t _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \
0544 _mur_k1 *= _mur_c1; \
0545 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
0546 _mur_k1 *= _mur_c2; \
0547 \
0548 _mur_h1 ^= _mur_k1; \
0549 _mur_h1 = MUR_ROTL32(_mur_h1,13); \
0550 _mur_h1 = _mur_h1*5+0xe6546b64; \
0551 } \
0552 const uint8_t *_mur_tail = (const uint8_t*)(_mur_data + _mur_nblocks*4); \
0553 uint32_t _mur_k1=0; \
0554 switch((keylen) & 3) { \
0555 case 3: _mur_k1 ^= _mur_tail[2] << 16; \
0556 case 2: _mur_k1 ^= _mur_tail[1] << 8; \
0557 case 1: _mur_k1 ^= _mur_tail[0]; \
0558 _mur_k1 *= _mur_c1; \
0559 _mur_k1 = MUR_ROTL32(_mur_k1,15); \
0560 _mur_k1 *= _mur_c2; \
0561 _mur_h1 ^= _mur_k1; \
0562 } \
0563 _mur_h1 ^= (keylen); \
0564 MUR_FMIX(_mur_h1); \
0565 hashv = _mur_h1; \
0566 bkt = hashv & (num_bkts-1); \
0567 } while(0)
0568 #endif
0569
0570
0571 #define EXHASH_KEYCMP(a,b,len) memcmp(a,b,len)
0572
0573
0574 #define EXHASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \
0575 do { \
0576 if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \
0577 else out=NULL; \
0578 while (out) { \
0579 if (out->hh.keylen == keylen_in) { \
0580 if ((EXHASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \
0581 } \
0582 if (out->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,out->hh.hh_next)); \
0583 else out = NULL; \
0584 } \
0585 } while(0)
0586
0587
0588 #define EXHASH_ADD_TO_BKT(head,addhh) \
0589 do { \
0590 head.count++; \
0591 (addhh)->hh_next = head.hh_head; \
0592 (addhh)->hh_prev = NULL; \
0593 if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \
0594 (head).hh_head=addhh; \
0595 if (head.count >= ((head.expand_mult+1) * EXHASH_BKT_CAPACITY_THRESH) \
0596 && (addhh)->tbl->noexpand != 1) { \
0597 EXHASH_EXPAND_BUCKETS((addhh)->tbl); \
0598 } \
0599 } while(0)
0600
0601
0602 #define EXHASH_DEL_IN_BKT(hh,head,hh_del) \
0603 (head).count--; \
0604 if ((head).hh_head == hh_del) { \
0605 (head).hh_head = hh_del->hh_next; \
0606 } \
0607 if (hh_del->hh_prev) { \
0608 hh_del->hh_prev->hh_next = hh_del->hh_next; \
0609 } \
0610 if (hh_del->hh_next) { \
0611 hh_del->hh_next->hh_prev = hh_del->hh_prev; \
0612 }
0613
0614
0615
0616
0617
0618
0619
0620
0621
0622
0623
0624
0625
0626
0627
0628
0629
0630
0631
0632
0633
0634
0635
0636
0637
0638
0639
0640
0641
0642
0643 #define EXHASH_EXPAND_BUCKETS(tbl) \
0644 do { \
0645 unsigned _he_bkt; \
0646 unsigned _he_bkt_i; \
0647 struct EX_hash_handle *_he_thh, *_he_hh_nxt; \
0648 EX_hash_bucket *_he_new_buckets, *_he_newbkt; \
0649 _he_new_buckets = (EX_hash_bucket*)exhash_malloc( \
0650 2 * tbl->num_buckets * sizeof(struct EX_hash_bucket)); \
0651 if (!_he_new_buckets) { exhash_fatal( "out of memory"); } \
0652 memset(_he_new_buckets, 0, \
0653 2 * tbl->num_buckets * sizeof(struct EX_hash_bucket)); \
0654 tbl->ideal_chain_maxlen = \
0655 (tbl->num_items >> (tbl->log2_num_buckets+1)) + \
0656 ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \
0657 tbl->nonideal_items = 0; \
0658 for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \
0659 { \
0660 _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \
0661 while (_he_thh) { \
0662 _he_hh_nxt = _he_thh->hh_next; \
0663 EXHASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \
0664 _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \
0665 if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \
0666 tbl->nonideal_items++; \
0667 _he_newbkt->expand_mult = _he_newbkt->count / \
0668 tbl->ideal_chain_maxlen; \
0669 } \
0670 _he_thh->hh_prev = NULL; \
0671 _he_thh->hh_next = _he_newbkt->hh_head; \
0672 if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \
0673 _he_thh; \
0674 _he_newbkt->hh_head = _he_thh; \
0675 _he_thh = _he_hh_nxt; \
0676 } \
0677 } \
0678 exhash_free( tbl->buckets, tbl->num_buckets*sizeof(struct EX_hash_bucket) ); \
0679 tbl->num_buckets *= 2; \
0680 tbl->log2_num_buckets++; \
0681 tbl->buckets = _he_new_buckets; \
0682 tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \
0683 (tbl->ineff_expands+1) : 0; \
0684 if (tbl->ineff_expands > 1) { \
0685 tbl->noexpand=1; \
0686 exhash_noexpand_fyi(tbl); \
0687 } \
0688 exhash_expand_fyi(tbl); \
0689 } while(0)
0690
0691
0692
0693
0694
0695 #define EXHASH_SORT(head,cmpfcn) EXHASH_SRT(hh,head,cmpfcn)
0696 #define EXHASH_SRT(hh,head,cmpfcn) \
0697 do { \
0698 unsigned _hs_i; \
0699 unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \
0700 struct EX_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \
0701 if (head) { \
0702 _hs_insize = 1; \
0703 _hs_looping = 1; \
0704 _hs_list = &((head)->hh); \
0705 while (_hs_looping) { \
0706 _hs_p = _hs_list; \
0707 _hs_list = NULL; \
0708 _hs_tail = NULL; \
0709 _hs_nmerges = 0; \
0710 while (_hs_p) { \
0711 _hs_nmerges++; \
0712 _hs_q = _hs_p; \
0713 _hs_psize = 0; \
0714 for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \
0715 _hs_psize++; \
0716 _hs_q = (EX_hash_handle*)((_hs_q->next) ? \
0717 ((void*)((char*)(_hs_q->next) + \
0718 (head)->hh.tbl->hho)) : NULL); \
0719 if (! (_hs_q) ) break; \
0720 } \
0721 _hs_qsize = _hs_insize; \
0722 while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \
0723 if (_hs_psize == 0) { \
0724 _hs_e = _hs_q; \
0725 _hs_q = (EX_hash_handle*)((_hs_q->next) ? \
0726 ((void*)((char*)(_hs_q->next) + \
0727 (head)->hh.tbl->hho)) : NULL); \
0728 _hs_qsize--; \
0729 } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \
0730 _hs_e = _hs_p; \
0731 _hs_p = (EX_hash_handle*)((_hs_p->next) ? \
0732 ((void*)((char*)(_hs_p->next) + \
0733 (head)->hh.tbl->hho)) : NULL); \
0734 _hs_psize--; \
0735 } else if (( \
0736 cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \
0737 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \
0738 ) <= 0) { \
0739 _hs_e = _hs_p; \
0740 _hs_p = (EX_hash_handle*)((_hs_p->next) ? \
0741 ((void*)((char*)(_hs_p->next) + \
0742 (head)->hh.tbl->hho)) : NULL); \
0743 _hs_psize--; \
0744 } else { \
0745 _hs_e = _hs_q; \
0746 _hs_q = (EX_hash_handle*)((_hs_q->next) ? \
0747 ((void*)((char*)(_hs_q->next) + \
0748 (head)->hh.tbl->hho)) : NULL); \
0749 _hs_qsize--; \
0750 } \
0751 if ( _hs_tail ) { \
0752 _hs_tail->next = ((_hs_e) ? \
0753 ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \
0754 } else { \
0755 _hs_list = _hs_e; \
0756 } \
0757 _hs_e->prev = ((_hs_tail) ? \
0758 ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \
0759 _hs_tail = _hs_e; \
0760 } \
0761 _hs_p = _hs_q; \
0762 } \
0763 _hs_tail->next = NULL; \
0764 if ( _hs_nmerges <= 1 ) { \
0765 _hs_looping=0; \
0766 (head)->hh.tbl->tail = _hs_tail; \
0767 DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \
0768 } \
0769 _hs_insize *= 2; \
0770 } \
0771 EXHASH_FSCK(hh,head); \
0772 } \
0773 } while (0)
0774
0775
0776
0777
0778
0779
0780 #define EXHASH_SELECT(hh_dst, dst, hh_src, src, cond) \
0781 do { \
0782 unsigned _src_bkt, _dst_bkt; \
0783 void *_last_elt=NULL, *_elt; \
0784 EX_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \
0785 ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \
0786 if (src) { \
0787 for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \
0788 for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \
0789 _src_hh; \
0790 _src_hh = _src_hh->hh_next) { \
0791 _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \
0792 if (cond(_elt)) { \
0793 _dst_hh = (EX_hash_handle*)(((char*)_elt) + _dst_hho); \
0794 _dst_hh->key = _src_hh->key; \
0795 _dst_hh->keylen = _src_hh->keylen; \
0796 _dst_hh->hashv = _src_hh->hashv; \
0797 _dst_hh->prev = _last_elt; \
0798 _dst_hh->next = NULL; \
0799 if (_last_elt_hh) { _last_elt_hh->next = _elt; } \
0800 if (!dst) { \
0801 DECLTYPE_ASSIGN(dst,_elt); \
0802 EXHASH_MAKE_TABLE(hh_dst,dst); \
0803 } else { \
0804 _dst_hh->tbl = (dst)->hh_dst.tbl; \
0805 } \
0806 EXHASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \
0807 EXHASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \
0808 (dst)->hh_dst.tbl->num_items++; \
0809 _last_elt = _elt; \
0810 _last_elt_hh = _dst_hh; \
0811 } \
0812 } \
0813 } \
0814 } \
0815 EXHASH_FSCK(hh_dst,dst); \
0816 } while (0)
0817
0818 #define EXHASH_CLEAR(hh,head) \
0819 do { \
0820 if (head) { \
0821 exhash_free((head)->hh.tbl->buckets, \
0822 (head)->hh.tbl->num_buckets*sizeof(struct EX_hash_bucket)); \
0823 EXHASH_BLOOM_FREE((head)->hh.tbl); \
0824 exhash_free((head)->hh.tbl, sizeof(EX_hash_table)); \
0825 (head)=NULL; \
0826 } \
0827 } while(0)
0828
0829 #ifdef NO_DECLTYPE
0830 #define EXHASH_ITER(hh,head,el,tmp) \
0831 for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \
0832 el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL))
0833 #else
0834 #define EXHASH_ITER(hh,head,el,tmp) \
0835 for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \
0836 el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL))
0837 #endif
0838
0839
0840 #define EXHASH_COUNT(head) EXHASH_CNT(hh,head)
0841 #define EXHASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0)
0842
0843 typedef struct EX_hash_bucket {
0844 struct EX_hash_handle *hh_head;
0845 unsigned count;
0846
0847
0848
0849
0850
0851
0852
0853
0854
0855
0856
0857
0858
0859 unsigned expand_mult;
0860
0861 } EX_hash_bucket;
0862
0863
0864 #define EXHASH_SIGNATURE 0xa0111fe1
0865 #define EXHASH_BLOOM_SIGNATURE 0xb12220f2
0866
0867 typedef struct EX_hash_table {
0868 EX_hash_bucket *buckets;
0869 unsigned num_buckets, log2_num_buckets;
0870 unsigned num_items;
0871 struct EX_hash_handle *tail;
0872 ptrdiff_t hho;
0873
0874
0875
0876 unsigned ideal_chain_maxlen;
0877
0878
0879
0880
0881 unsigned nonideal_items;
0882
0883
0884
0885
0886
0887
0888
0889 unsigned ineff_expands, noexpand;
0890
0891 uint32_t signature;
0892 #ifdef HASH_BLOOM
0893 uint32_t bloom_sig;
0894 uint8_t *bloom_bv;
0895 char bloom_nbits;
0896 #endif
0897
0898 } EX_hash_table;
0899
0900 typedef struct EX_hash_handle {
0901 struct EX_hash_table *tbl;
0902 void *prev;
0903 void *next;
0904 struct EX_hash_handle *hh_prev;
0905 struct EX_hash_handle *hh_next;
0906 void *key;
0907 unsigned keylen;
0908 unsigned hashv;
0909 } EX_hash_handle;
0910
0911 #endif