From e78dd0918583a831e90f4c008c369ca143840124 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 16 Oct 2021 14:59:12 +0200 Subject: More update on hash. Added string_bench.c+cpp. --- include/stc/ccommon.h | 9 +++++++-- include/stc/cmap.h | 6 ++---- include/stc/cstr.h | 3 +-- include/stc/csview.h | 2 +- 4 files changed, 11 insertions(+), 9 deletions(-) (limited to 'include') diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 5480d9f2..b61c7daf 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -102,8 +102,7 @@ #define c_rawstr_compare(x, y) strcmp(*(x), *(y)) #define c_rawstr_equals(x, y) (strcmp(*(x), *(y)) == 0) -#define c_rawstr_hash(p, dummy) c_default_hash(*(p), strlen(*(p))) -#define c_strhash(s) c_default_hash(s, strlen(s)) +#define c_rawstr_hash(p, dummy) c_strhash(*(p)) #define c_no_clone(x) (assert(!"c_no_clone() called"), x) #define c_default_fromraw(x) (x) @@ -111,6 +110,12 @@ #define c_default_del(ptr) ((void) (ptr)) +#define _c_rotl(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) +STC_INLINE uint64_t c_strhash(const char *str) { + int c; uint64_t h = 0xb5ad4eceda1ce2a9; + while ((c = *str++)) h = (_c_rotl(h, 4) ^ (h << 13)) + c; + return h; +} STC_INLINE uint64_t c_default_hash(const void *key, size_t len); #define c_default_hash32(data, len_is_4) \ ((*(const uint32_t*)data * 0xc6a4a7935bd1e99d) >> 15) diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 1dc1fd90..b764a717 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -216,12 +216,10 @@ cx_memb(_erase_at)(Self* self, cx_iter_t it) { #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_imp) #ifndef CMAP_H_INCLUDED -#define _c_rotl(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) STC_INLINE uint64_t c_default_hash(const void *key, size_t len) { - const char* str = (const char*)key; + const char* str = (const char*)key, *e = str + len; uint64_t h = 0xb5ad4eceda1ce2a9; - for (size_t i = 0; i < len; ++i) - h ^= (_c_rotl(h, 4) ^ (h << 13)) + str[i]; + while (str != e) h = (_c_rotl(h, 4) ^ (h << 13)) + *str++; return h; } diff --git a/include/stc/cstr.h b/include/stc/cstr.h index 98b95e3d..41af7925 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -167,10 +167,9 @@ cstr_ends_with(cstr s, const char* sub) { } /* container adaptor functions: */ -#define cstr_toraw(xp) ((xp)->str) // deprecated #define cstr_compare(xp, yp) strcmp((xp)->str, (yp)->str) #define cstr_equals(xp, yp) (strcmp((xp)->str, (yp)->str) == 0) -#define cstr_hash(xp, ...) c_default_hash((xp)->str, cstr_size(*(xp))) +#define cstr_hash(xp, dummy) c_strhash((xp)->str) /* -------------------------- IMPLEMENTATION ------------------------- */ diff --git a/include/stc/csview.h b/include/stc/csview.h index 6733912d..d4ef0bd1 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -115,7 +115,7 @@ STC_INLINE bool cstr_ends_with_v(cstr s, csview sub) /* ---- Container helper functions ---- */ #define csview_compare(xp, yp) strcmp((xp)->str, (yp)->str) -#define csview_hash(xp, ...) c_default_hash((xp)->str, (xp)->size) +#define csview_hash(xp, dummy) c_strhash((xp)->str) #define csview_equals(xp, yp) (strcmp((xp)->str, (yp)->str) == 0) /* -------------------------- IMPLEMENTATION ------------------------- */ -- cgit v1.2.3