From d3110bfa37d12771e22c20aa503059476432a59d Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 9 Aug 2020 23:26:24 +0200 Subject: Moved hash functions from cdefs to cmap. --- stc/cdefs.h | 26 -------------------------- stc/cmap.h | 31 +++++++++++++++++++++++++++++++ 2 files changed, 31 insertions(+), 26 deletions(-) diff --git a/stc/cdefs.h b/stc/cdefs.h index 54c8863e..6136a7e1 100644 --- a/stc/cdefs.h +++ b/stc/cdefs.h @@ -86,31 +86,5 @@ prefix##_push_n(container, __arr, sizeof(__arr)/sizeof(prefix##_input_t)); \ } while (0) -/* One-byte-at-a-time hash based on Murmur's mix */ -static inline uint32_t c_default_hash(const void *data, size_t len) { - const volatile uint8_t *key = (const uint8_t *) data; - uint32_t x = UINT32_C(0xc613fc15); - while (len--) { - x ^= *key++; - x *= UINT32_C(0x5bd1e995); - x ^= x >> 15; - } - return x; -} - -/* https://programmingpraxis.com/2018/06/19/fibonacci-hash */ -/* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ -static inline uint32_t c_fibonacci_hash32(const void* data, size_t len) { - const volatile uint32_t *key = (const uint32_t *) data; - uint32_t x = *key++ * 2654435769u; - while (len -= 4) x ^= *key++ * 2654435769u; - return x; -} -static inline uint32_t c_fibonacci_hash64(const void* data, size_t len) { - const volatile uint64_t *key = (const uint64_t *) data; - uint64_t x = *key++ * 11400714819323198485ull; - while (len -= 8) x ^= *key++ * 11400714819323198485ull; - return (uint32_t) x; // (x >> 13); -} #endif diff --git a/stc/cmap.h b/stc/cmap.h index db7cc0a9..08986f29 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -197,6 +197,10 @@ ctype##_##tag##_begin(ctype##_##tag* map); \ STC_API void \ ctype##_##tag##_next(ctype##_##tag##_iter_t* it); \ \ +STC_API uint32_t c_default_hash(const void *data, size_t len); \ +STC_API uint32_t c_fibonacci_hash32(const void* data, size_t len); \ +STC_API uint32_t c_fibonacci_hash64(const void* data, size_t len); \ + \ implement_CHASH(tag, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ keyDestroy, RawKey, keyToRaw, keyFromRaw) \ typedef Key ctype##_##tag##_key_t; \ @@ -375,6 +379,33 @@ ctype##_##tag##_next(ctype##_##tag##_iter_t* it) { \ while (++it->item != it->end && *++it->_hx == 0) ; \ } + +/* One-byte-at-a-time hash based on Murmur's mix */ +STC_API uint32_t c_default_hash(const void *data, size_t len) { + const volatile uint8_t *key = (const uint8_t *) data; + uint32_t x = UINT32_C(0xc613fc15); + while (len--) { + x ^= *key++; + x *= UINT32_C(0x5bd1e995); + x ^= x >> 15; + } + return x; +} +/* https://programmingpraxis.com/2018/06/19/fibonacci-hash */ +/* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */ +STC_API uint32_t c_fibonacci_hash32(const void* data, size_t len) { + const volatile uint32_t *key = (const uint32_t *) data; + uint32_t x = *key++ * 2654435769u; + while (len -= 4) x ^= *key++ * 2654435769u; + return x; +} +STC_API uint32_t c_fibonacci_hash64(const void* data, size_t len) { + const volatile uint64_t *key = (const uint64_t *) data; + uint64_t x = *key++ * 11400714819323198485ull; + while (len -= 8) x ^= *key++ * 11400714819323198485ull; + return (uint32_t) x; // (x >> 13); +} + #else #define implement_CHASH(tag, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ keyDestroy, RawKey, keyToRaw, keyFromRaw) -- cgit v1.2.3