diff options
Diffstat (limited to 'vendors/uthash.h')
| -rw-r--r-- | vendors/uthash.h | 213 |
1 files changed, 212 insertions, 1 deletions
diff --git a/vendors/uthash.h b/vendors/uthash.h index 2c00932..e3c235c 100644 --- a/vendors/uthash.h +++ b/vendors/uthash.h @@ -29,6 +29,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #include <string.h> /* memcmp, memset, strlen */ #include <stddef.h> /* ptrdiff_t */ #include <stdlib.h> /* exit */ +#include <stdio.h> #if defined(HASH_DEFINE_OWN_STDINT) && HASH_DEFINE_OWN_STDINT /* This codepath is provided for backward compatibility, but I plan to remove it. */ @@ -87,9 +88,86 @@ do { #define uthash_strlen(s) strlen(s) #endif +#include "xxhash/xxhash.h" + +static uint32_t +murmurhash (const char *key, uint32_t len, uint32_t seed) { + uint32_t c1 = 0xcc9e2d51; + uint32_t c2 = 0x1b873593; + uint32_t r1 = 15; + uint32_t r2 = 13; + uint32_t m = 5; + uint32_t n = 0xe6546b64; + uint32_t h = 0; + uint32_t k = 0; + uint8_t *d = (uint8_t *) key; // 32 bit extract from `key' + const uint32_t *chunks = NULL; + const uint8_t *tail = NULL; // tail - last 8 bytes + int i = 0; + int l = len / 4; // chunk length + + h = seed; + + chunks = (const uint32_t *) (d + l * 4); // body + tail = (const uint8_t *) (d + l * 4); // last 8 byte chunk of `key' + + // for each 4 byte chunk of `key' + for (i = -l; i != 0; ++i) { + // next 4 byte chunk of `key' + k = chunks[i]; + + // encode next 4 byte chunk of `key' + k *= c1; + k = (k << r1) | (k >> (32 - r1)); + k *= c2; + + // append to hash + h ^= k; + h = (h << r2) | (h >> (32 - r2)); + h = h * m + n; + } + + k = 0; + + // remainder + switch (len & 3) { // `len % 4' + case 3: k ^= (tail[2] << 16); + case 2: k ^= (tail[1] << 8); + + case 1: + k ^= tail[0]; + k *= c1; + k = (k << r1) | (k >> (32 - r1)); + k *= c2; + h ^= k; + } + + h ^= len; + + h ^= (h >> 16); + h *= 0x85ebca6b; + h ^= (h >> 13); + h *= 0xc2b2ae35; + h ^= (h >> 16); + + return h; +} + +#define HASH_MUR(keyptr, keylen, hashv) \ + do { \ + hashv = murmurhash(keyptr, keylen, 0); \ + } while (0) + + #define HASH_XXH(keyptr, keylen, hashv) \ + do { \ + hashv = XXH3_64bits(keyptr, keylen); \ + } while (0) + + #ifndef HASH_FUNCTION // #define HASH_FUNCTION(keyptr,keylen,hashv) HASH_JEN(keyptr, keylen, hashv) -#define HASH_FUNCTION(keyptr,keylen,hashv) HASH_SFH(keyptr, keylen, hashv) +// #define HASH_FUNCTION(keyptr,keylen,hashv) HASH_SFH(keyptr, keylen, hashv) +#define HASH_FUNCTION(keyptr,keylen,hashv) HASH_MUR(keyptr, keylen, hashv) // #define HASH_FUNCTION(keyptr,keylen,hashv) HASH_OAT(keyptr, keylen, hashv) // #define HASH_FUNCTION(keyptr,keylen,hashv) HASH_SAX(keyptr, keylen, hashv) // #define HASH_FUNCTION(keyptr,keylen,hashv) HASH_FNV(keyptr, keylen, hashv) @@ -1142,4 +1220,137 @@ typedef struct UT_hash_handle { unsigned hashv; /* result of hash-fcn(key) */ } UT_hash_handle; +static inline unsigned hash_to_bkt_func(unsigned hashv, unsigned num_bkts) { + return hashv & (num_bkts - 1U); +} + +static int my_key_cmp1(const void *a, const void *b, unsigned len) { + for (unsigned i = 0; i < len; i++) { + if (((char *)a)[i] != ((char *)b)[i]) { + return 1; + } + } + return 0; +} + +static void* elmt_from_hh_func(struct UT_hash_table *tbl, struct UT_hash_handle *hhp) { + return (void*)((char*)hhp - tbl->hho); +} + +static struct UT_hash_handle *things_in_while_find_hh( + struct UT_hash_table *tbl, + const void *keyptr, + unsigned keylen_in, + unsigned hashval, + struct UT_hash_handle *hh +) { + while (hh != NULL) { + if (hh->hashv == hashval && hh->keylen == keylen_in && + my_key_cmp1(hh->key, keyptr, keylen_in) == 0) { + // printf("while_cnt: %d before returning the value \n", while_cnt); + return hh; + } + hh = hh->hh_next; + } + return NULL; +} + +/* 替换 HASH_FIND_IN_BKT */ +// static inline void *hash_find_in_bkt_func( +// struct UT_hash_table *tbl, +// unsigned bkt, +// const void *keyptr, +// unsigned keylen_in, +// unsigned hashval +// ) { +// struct UT_hash_bucket *bucket = &(tbl->buckets[bkt]); +// struct UT_hash_handle *hh = bucket->hh_head; +// int while_cnt = 0; +// while (hh != NULL) { +// while_cnt++; +// if (hh->hashv == hashval && hh->keylen == keylen_in && +// // HASH_KEYCMP(hh->key, keyptr, keylen_in) == 0) { +// my_key_cmp1(hh->key, keyptr, keylen_in) == 0) { +// // printf("while_cnt: %d before returning the value \n", while_cnt); +// return elmt_from_hh_func(tbl, hh); +// } +// hh = hh->hh_next; +// } +// return NULL; +// } + +static inline void *hash_find_in_bkt_func( + struct UT_hash_table *tbl, + unsigned bkt, + const void *keyptr, + unsigned keylen_in, + unsigned hashval +) { + struct UT_hash_bucket *bucket = &(tbl->buckets[bkt]); + struct UT_hash_handle *hh = bucket->hh_head; + + hh = things_in_while_find_hh(tbl, keyptr, keylen_in, hashval, hh); + if (hh != NULL) { + return elmt_from_hh_func(tbl, hh); + } + return NULL; +} + +/* 替换 HASH_FIND_BYHASHVALUE */ +static inline void *hash_find_byhashvalue_func( + struct UT_hash_table *tbl, + const void *keyptr, + unsigned keylen, + unsigned hashval +) { + unsigned bkt = hash_to_bkt_func(hashval, tbl->num_buckets); + if (HASH_BLOOM_TEST(tbl, hashval)) { + return hash_find_in_bkt_func(tbl, bkt, keyptr, keylen, hashval); + } + return NULL; +} + +/* 替换 HASH_FIND */ +static inline void *hash_find_func( + struct UT_hash_table *tbl, + const void *keyptr, + unsigned keylen +) { + unsigned hashv; + HASH_VALUE(keyptr, keylen, hashv); + return hash_find_byhashvalue_func(tbl, keyptr, keylen, hashv); +} + +/* 2. 取消定义原有宏 */ +#undef HASH_TO_BKT +#undef HASH_FIND_IN_BKT +#undef HASH_FIND_BYHASHVALUE +#undef HASH_FIND + +/* 3. 重定义宏以调用替代函数 */ +#define HASH_TO_BKT(hashv, num_bkts, bkt) \ + do { \ + (bkt) = hash_to_bkt_func((hashv), (num_bkts)); \ + } while (0) + +#define HASH_FIND_IN_BKT(tbl, hh, head, keyptr, keylen_in, hashval, out) \ + do { \ + (out) = hash_find_in_bkt_func((tbl), (head), (keyptr), (keylen_in), (hashval)); \ + } while (0) + +#define HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, hashval, out) \ + do { \ + (out) = hash_find_byhashvalue_func((head)->hh.tbl, (keyptr), (keylen), (hashval)); \ + } while (0) + +#define HASH_FIND(hh, head, keyptr, keylen, out) \ + do { \ + if (!(head)) { \ + (out) = NULL; \ + } else { \ + (out) = hash_find_func((head)->hh.tbl, (keyptr), (keylen)); \ + } \ + } while (0) + + #endif /* UTHASH_H */ |