From 28574b3bd60c5ef07f3c245095b56c8278a98459 Mon Sep 17 00:00:00 2001 From: tylo Date: Tue, 11 Aug 2020 11:29:23 +0200 Subject: Fixed two bugs: 1) hash16 not to be used for string. 2) cstr_from(): va_copy missed --- examples/README.md | 3 +-- examples/advanced.c | 10 +++++----- examples/benchmark.c | 6 +++--- examples/demos.c | 1 + stc/cmap.h | 15 +++++++-------- stc/cstr.h | 18 ++++++++++++------ 6 files changed, 29 insertions(+), 24 deletions(-) diff --git a/examples/README.md b/examples/README.md index 27307372..661f7555 100644 --- a/examples/README.md +++ b/examples/README.md @@ -24,8 +24,7 @@ typedef struct VikingVw { uint32_t vikingvw_hash(const VikingVw* vw, size_t ignore) { - uint32_t hash = c_default_hash(vw->name, strlen(vw->name)) - ^ c_default_hash(vw->country, strlen(vw->country)); + uint32_t hash = c_string_hash(vw->name) ^ c_string_hash(w->country); return hash; } static inline int vikingvw_equals(const VikingVw* x, const VikingVw* y) { diff --git a/examples/advanced.c b/examples/advanced.c index 7162bdc9..03baf5fc 100644 --- a/examples/advanced.c +++ b/examples/advanced.c @@ -22,8 +22,7 @@ typedef struct VikingVw { } VikingVw; uint32_t vikingvw_hash(const VikingVw* vw, size_t ignore) { - uint32_t hash = c_default_hash(vw->name, strlen(vw->name)) - ^ c_default_hash(vw->country, strlen(vw->country)); + uint32_t hash = c_string_hash(vw->name) ^ c_string_hash(vw->country); return hash; } int vikingvw_equals(const VikingVw* x, const VikingVw* y) { @@ -69,10 +68,11 @@ int main() {{"Olaf", "Denmark"}, 24}, {{"Harald", "Iceland"}, 12}, )); - VikingVw look = {"Einar", "Norway"}; - cmap_vk_entry_t *e = cmap_vk_find(&vikings, look); + + VikingVw einar = {"Einar", "Norway"}; + cmap_vk_entry_t *e = cmap_vk_find(&vikings, einar); e->value += 5; // update - cmap_vk_insert(&vikings, look, 0)->value += 5; // again + cmap_vk_insert(&vikings, einar, 0)->value += 5; // again c_foreach (k, cmap_vk, vikings) { printf("%s of %s has %d hp\n", k.item->key.name.str, k.item->key.country.str, k.item->value); diff --git a/examples/benchmark.c b/examples/benchmark.c index 30fb48af..af696692 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -142,7 +142,7 @@ int main(int argc, char* argv[]) printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); printf("\nUnordered maps: %zu repeats of Insert random key + try to remove a random key:\n", N1); MAP_TEST1(CMAP, ii) - //MAP_TEST1(KMAP, ii) + MAP_TEST1(KMAP, ii) #ifdef __cplusplus MAP_TEST1(UMAP, ii) MAP_TEST1(BMAP, ii) @@ -152,7 +152,7 @@ int main(int argc, char* argv[]) printf("\nUnordered maps: Insert %zu index keys, then remove them in same order:\n", N2); MAP_TEST2(CMAP, ii) - //MAP_TEST2(KMAP, ii) + MAP_TEST2(KMAP, ii) #ifdef __cplusplus MAP_TEST2(UMAP, ii) MAP_TEST2(BMAP, ii) @@ -162,7 +162,7 @@ int main(int argc, char* argv[]) printf("\nUnordered maps: Insert %zu random keys, then remove them in same order:\n", N3); MAP_TEST3(CMAP, ii) - //MAP_TEST3(KMAP, ii) + MAP_TEST3(KMAP, ii) #ifdef __cplusplus MAP_TEST3(UMAP, ii) MAP_TEST3(BMAP, ii) diff --git a/examples/demos.c b/examples/demos.c index 47ba52aa..f8feb346 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -19,6 +19,7 @@ void stringdemo1() cstr_replace(&cs, cstr_find(cs, "seven", 0), 5, "four"); printf("%s.\n", cs.str); + cstr_take(&cs, cstr_from("%s *** %s", cs.str, cs.str)); printf("%s.\n", cs.str); diff --git a/stc/cmap.h b/stc/cmap.h index a984c711..15906880 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -75,7 +75,7 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; declare_cmap_4(tag, Key, Value, c_default_destroy) #define declare_cmap_4(tag, Key, Value, valueDestroy) \ - declare_cmap_6(tag, Key, Value, valueDestroy, c_default_equals, c_default_hash) + declare_cmap_6(tag, Key, Value, valueDestroy, c_default_equals, c_default_hash16) #define declare_cmap_6(tag, Key, Value, valueDestroy, keyEquals, keyHash) \ declare_cmap_10(tag, Key, Value, valueDestroy, keyEquals, keyHash, \ @@ -91,7 +91,7 @@ enum {chash_HASH = 0x7f, chash_USED = 0x80}; c_MACRO_OVERLOAD(declare_cset, __VA_ARGS__) #define declare_cset_2(tag, Key) \ - declare_cset_4(tag, Key, c_default_equals, c_default_hash) + declare_cset_4(tag, Key, c_default_equals, c_default_hash16) #define declare_cset_4(tag, Key, keyEquals, keyHash) \ declare_cset_5(tag, Key, keyEquals, keyHash, c_default_destroy) @@ -197,9 +197,8 @@ 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); \ +STC_API uint32_t c_default_hash16(const void *data, size_t len); \ +STC_API uint32_t c_default_hash32(const void* data, size_t len); \ \ implement_CHASH(tag, ctype, Key, Value, valueDestroy, keyEqualsRaw, keyHashRaw, \ keyDestroy, RawKey, keyToRaw, keyFromRaw) \ @@ -379,14 +378,14 @@ ctype##_##tag##_next(ctype##_##tag##_iter_t* it) { \ while (++it->item != it->end && *++it->_hx == 0) ; \ } -STC_API uint32_t c_default_hash(const void *data, size_t len) { +/* 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_default_hash16(const void *data, size_t len) { const volatile uint16_t *key = (const uint16_t *) data; uint64_t x = 0xc613fc15u; while (len -= 2) x = ((*key++ + x) * 2654435769u) >> 13; 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_default_hash32(const void* data, size_t len) { const volatile uint32_t *key = (const uint32_t *) data; uint64_t x = *key++ * 2654435769u; diff --git a/stc/cstr.h b/stc/cstr.h index 38b1bd72..34b0f742 100644 --- a/stc/cstr.h +++ b/stc/cstr.h @@ -196,13 +196,17 @@ cstr_find(cstr_t s, const char* needle, size_t pos) { #define cstr_to_raw(x) ((x)->str) #define cstr_compare_raw(x, y) strcmp(*(x), *(y)) #define cstr_equals_raw(x, y) (strcmp(*(x), *(y)) == 0) -STC_INLINE uint32_t cstr_hash_raw(const char* const* sPtr, size_t ignored) { + +STC_INLINE uint32_t c_string_hash(const char* str) { uint32_t hash = 5381, c; /* djb2 */ - const char* tmp = *sPtr; - while ((c = *tmp++)) hash = ((hash << 5) + hash) ^ c; + while ((c = *str++)) hash = ((hash << 5) + hash) ^ c; return hash; } +STC_INLINE uint32_t cstr_hash_raw(const char* const* chr_pp, size_t ignored) { + return c_string_hash(*chr_pp); +} + /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) @@ -239,15 +243,17 @@ cstr_make_n(const char* str, size_t len) { STC_API cstr_t cstr_from(const char* fmt, ...) { cstr_t tmp = cstr_init; - va_list args; + va_list args, args2; va_start(args, fmt); + va_copy(args2, args); int len = vsnprintf(NULL, (size_t)0, fmt, args); + va_end(args); if (len > 0) { tmp = cstr_with_capacity(len); - vsprintf(tmp.str, fmt, args); + vsprintf(tmp.str, fmt, args2); _cstr_size(tmp) = len; } - va_end(args); + va_end(args2); return tmp; } -- cgit v1.2.3