From 2b74b8a880d48232892ca84ac29efacd66905cd4 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 23 Apr 2022 14:00:47 +0200 Subject: Integrated (and removed) c_hash32 and c_hash64 into c_default_hash, which is improved. Added i_key_ssv and i_val_ssv (cstr with csview as raw-type). --- benchmarks/build_all.sh | 1 - benchmarks/misc/sso_bench.c | 2 +- benchmarks/misc/sso_bench2.cpp | 1 - benchmarks/picobench/picobench_cmap.cpp | 2 -- benchmarks/plotbench/cmap_benchmark.cpp | 1 - benchmarks/shootout_hashmaps.cpp | 1 - docs/clist_api.md | 1 + docs/cmap_api.md | 2 -- examples/make.sh | 2 +- examples/read.c | 2 +- examples/sso_map.c | 1 - examples/sso_substr.c | 1 - include/stc/carc.h | 6 ++---- include/stc/cbox.h | 6 ++---- include/stc/ccommon.h | 18 ++++++++++-------- include/stc/cmap.h | 3 --- include/stc/cstr.h | 7 ++++--- include/stc/csview.h | 15 ++++++++------- include/stc/template.h | 32 ++++++++++++++++++++++++++------ 19 files changed, 56 insertions(+), 48 deletions(-) diff --git a/benchmarks/build_all.sh b/benchmarks/build_all.sh index fda58f69..348a79dd 100644 --- a/benchmarks/build_all.sh +++ b/benchmarks/build_all.sh @@ -1,6 +1,5 @@ #!/bin/bash cc='g++ -std=c++17' -#cc='g++ -std=c++17 -DSTC_USE_SSO' #cc='clang' #cc='clang -c -DSTC_HEADER' #cc='cl -nologo' diff --git a/benchmarks/misc/sso_bench.c b/benchmarks/misc/sso_bench.c index 450884f3..f2714be1 100644 --- a/benchmarks/misc/sso_bench.c +++ b/benchmarks/misc/sso_bench.c @@ -1,5 +1,5 @@ // https://gobyexample.com/maps -#include +#include #define i_type Map #define i_key_str #define i_val int diff --git a/benchmarks/misc/sso_bench2.cpp b/benchmarks/misc/sso_bench2.cpp index 87b701b5..1355a727 100644 --- a/benchmarks/misc/sso_bench2.cpp +++ b/benchmarks/misc/sso_bench2.cpp @@ -2,7 +2,6 @@ #include #include #include -#define STC_USE_SSO 1 #define i_type svec #define i_val_str #include diff --git a/benchmarks/picobench/picobench_cmap.cpp b/benchmarks/picobench/picobench_cmap.cpp index 02daad51..d72ea12f 100644 --- a/benchmarks/picobench/picobench_cmap.cpp +++ b/benchmarks/picobench/picobench_cmap.cpp @@ -37,13 +37,11 @@ DEFMAP(map_s, ); #define i_key int32_t #define i_val int32_t -#define i_hash c_hash32 #define i_tag i #include #define i_key uint64_t #define i_val uint64_t -#define i_hash c_hash64 #define i_tag x #include diff --git a/benchmarks/plotbench/cmap_benchmark.cpp b/benchmarks/plotbench/cmap_benchmark.cpp index 0554ae9c..a22aee86 100644 --- a/benchmarks/plotbench/cmap_benchmark.cpp +++ b/benchmarks/plotbench/cmap_benchmark.cpp @@ -17,7 +17,6 @@ static float secs(Range s) { return (float)(s.t2 - s.t1) / CLOCKS_PER_SEC; } #define i_key uint64_t #define i_val uint64_t -#define i_hash c_hash64 #define i_tag x #include diff --git a/benchmarks/shootout_hashmaps.cpp b/benchmarks/shootout_hashmaps.cpp index 57bd3383..4ed961e7 100644 --- a/benchmarks/shootout_hashmaps.cpp +++ b/benchmarks/shootout_hashmaps.cpp @@ -26,7 +26,6 @@ KHASH_MAP_INIT_INT64(ii, int64_t) // cmap and khash template expansion #define i_key int64_t #define i_val int64_t -#define i_hash c_hash64 #define i_tag ii #include diff --git a/docs/clist_api.md b/docs/clist_api.md index cae3e66b..c785fbe5 100644 --- a/docs/clist_api.md +++ b/docs/clist_api.md @@ -57,6 +57,7 @@ void clist_X_pop_front(clist_X* self); void clist_X_push_back(clist_X* self, i_val value); // note: no pop_back() void clist_X_push(clist_X* self, i_val value); // alias for push_back() void clist_X_emplace_back(clist_X* self, i_valraw raw); +void clist_X_emplace(clist_X* self, i_valraw raw); // alias for emplace_back() clist_X_iter clist_X_insert_at(clist_X* self, clist_X_iter it, i_val value); // return iter to new elem clist_X_iter clist_X_emplace_at(clist_X* self, clist_X_iter it, i_valraw raw); diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 03ee11a9..07f1c140 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -89,8 +89,6 @@ uint64_t c_strhash(const char *str); / // hash template parameter functions: uint64_t c_default_hash(const void *data, size_t len); // key is any integral type -uint64_t c_hash32(const void* data, size_t is4); // key is one 32-bit int -uint64_t c_hash64(const void* data, size_t is8); // key is one 64-bit int // equalto template parameter functions: bool c_default_eq(const i_keyraw* a, const i_keyraw* b); // *a == *b diff --git a/examples/make.sh b/examples/make.sh index ef0468c7..4687ed97 100644 --- a/examples/make.sh +++ b/examples/make.sh @@ -1,7 +1,7 @@ #!/bin/bash cc='gcc -s -O2 -Wall -std=c99 -pedantic' #cc='gcc -x c++ -s -O2 -Wall -std=c++20' -#cc='clang -s -O2 -Wall -std=c99 -pedantic -DSTC_USE_SSO' +#cc='clang -s -O2 -Wall -std=c99 -pedantic -DSTC_OLD_CSTR' #cc='clang' #cc='clang -c -DSTC_HEADER' #cc='cl -O2 -nologo -W2 -MD' diff --git a/examples/read.c b/examples/read.c index 127373b1..5f31e357 100644 --- a/examples/read.c +++ b/examples/read.c @@ -1,4 +1,4 @@ -#include +#include #define i_val_str #include #include diff --git a/examples/sso_map.c b/examples/sso_map.c index a70722f7..d6174da8 100644 --- a/examples/sso_map.c +++ b/examples/sso_map.c @@ -1,4 +1,3 @@ -#define STC_USE_SSO 1 #include #define i_key_str #define i_val_str diff --git a/examples/sso_substr.c b/examples/sso_substr.c index 60fb9997..fdb53d0b 100644 --- a/examples/sso_substr.c +++ b/examples/sso_substr.c @@ -1,4 +1,3 @@ -#define STC_USE_SSO 1 #include #include diff --git a/include/stc/carc.h b/include/stc/carc.h index 54ba3159..1cdca419 100644 --- a/include/stc/carc.h +++ b/include/stc/carc.h @@ -170,10 +170,8 @@ _cx_memb(_take)(_cx_self* self, _cx_self ptr) { STC_INLINE uint64_t _cx_memb(_value_hash)(const _cx_value* x, size_t n) { - #if c_option(c_no_cmp) && UINTPTR_MAX == UINT64_MAX - return c_hash64(&x, 8); - #elif c_option(c_no_cmp) - return c_hash32(&x, 4); + #if c_option(c_no_cmp) + return c_default_hash(&x, sizeof x); #else _cx_raw rx = i_keyto(x); return i_hash((&rx), (sizeof rx)); diff --git a/include/stc/cbox.h b/include/stc/cbox.h index 27536c21..fa6ef2a9 100644 --- a/include/stc/cbox.h +++ b/include/stc/cbox.h @@ -147,10 +147,8 @@ _cx_memb(_take)(_cx_self* self, _cx_self other) { STC_INLINE uint64_t _cx_memb(_value_hash)(const _cx_value* x, size_t n) { - #if c_option(c_no_cmp) && UINTPTR_MAX == UINT64_MAX - return c_hash64(&x, 8); - #elif c_option(c_no_cmp) - return c_hash32(&x, 4); + #if c_option(c_no_cmp) + return c_default_hash(&x, sizeof x); #else _cx_raw rx = i_keyto(x); return i_hash((&rx), (sizeof rx)); diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index d7351611..56dd501e 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -117,19 +117,21 @@ STC_INLINE uint64_t c_strhash(const char *s) { if (h) while ((c = *s++)) h = (h << 10) - h + c; return _c_ROTL(h, 26) ^ h; } + STC_INLINE uint64_t c_default_hash(const void* key, size_t len) { - if (!len) return 1; + uint64_t u8, h = 1; + uint32_t u4; const uint8_t *x = (const uint8_t*) key; - uint64_t h = *x++; + for (size_t n = len >> 3; n--; ) + memcpy(&u8, x, 8), x += 8, h += u8*0xc6a4a7935bd1e99d; + switch (len &= 7) { + case 0: return h; + case 4: memcpy(&u4, x, 4); return h + u4*0xc6a4a7935bd1e99d; + } + h += *x++; while (--len) h = (h << 10) - h + *x++; return _c_ROTL(h, 26) ^ h; } -STC_INLINE uint64_t c_hash32(const void* key, size_t n) { - return *(uint32_t *)key*0xc6a4a7935bd1e99d; -} -STC_INLINE uint64_t c_hash64(const void* key, size_t n) { - return *(uint64_t *)key*0xc6a4a7935bd1e99d; -} STC_INLINE char* c_strnstrn(const char *s, const char *needle, size_t slen, const size_t nlen) { if (!nlen) return (char *)s; diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 6cde2532..978d624a 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -72,9 +72,6 @@ typedef struct { size_t idx; uint8_t hx; } chash_bucket_t; #endif #define _i_ishash #include "template.h" -#ifdef _i_no_hash - #error "i_hash must be defined if i_cmp, i_eq or i_keyfrom is defined for cmap/cset. For basic types c_default_hash may be used." -#endif #if !c_option(c_is_fwd) _cx_deftypes(_c_chash_types, _cx_self, i_key, i_val, i_size, _i_MAP_ONLY, _i_SET_ONLY); #endif diff --git a/include/stc/cstr.h b/include/stc/cstr.h index d5b7e5bd..9c6568f7 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -256,9 +256,10 @@ STC_INLINE bool cstr_getline(cstr *self, FILE *fp) { return cstr_getdelim(self, '\n', fp); } /* container adaptor functions: */ -#define cstr_cmp(xp, yp) strcmp(cstr_str(xp), cstr_str(yp)) -#define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) -#define cstr_hash(xp, dummy) c_strhash(cstr_str(xp)) +#define cstr_cmp(xp, yp) strcmp(cstr_str(xp), cstr_str(yp)) +#define cstr_eq(xp, yp) (!cstr_cmp(xp, yp)) +STC_INLINE uint64_t cstr_hash(const cstr *self, size_t dummylen) + { return c_default_hash(cstr_str(self), cstr_size(*self)); } /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) diff --git a/include/stc/csview.h b/include/stc/csview.h index c4b88f4d..59e853ca 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -127,13 +127,14 @@ STC_INLINE bool cstr_ends_with_sv(cstr s, csview sub) #endif /* ---- Container helper functions ---- */ -STC_INLINE int csview_cmp(const csview* x, const csview* y) { - const size_t m = x->size < y->size ? x->size : y->size; - const int c = memcmp(x->str, y->str, m); - return c ? c : x->size - y->size; - } -#define csview_hash(xp, dummy) c_default_hash((xp)->str, (xp)->size) -#define csview_eq(xp, yp) (!csview_cmp(xp, yp)) +STC_INLINE int csview_cmp(const csview* x, const csview* y) { + const size_t m = x->size < y->size ? x->size : y->size; + const int c = memcmp(x->str, y->str, m); + return c ? c : x->size - y->size; + } +#define csview_eq(xp, yp) (!csview_cmp(xp, yp)) +STC_INLINE uint64_t csview_hash(const csview *self, size_t sz) + { return c_default_hash(self->str, self->size); } /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) diff --git a/include/stc/template.h b/include/stc/template.h index d47b06ec..48881edf 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -50,11 +50,15 @@ #define i_size uint32_t #endif -#if defined i_key_str || defined i_val_str +#if defined i_key_str || defined i_val_str || defined i_key_ssv || defined i_val_ssv #include "cstr.h" + #if defined i_key_ssv || defined i_val_ssv + #include "csview.h" + #endif #endif -#if !(defined i_key || defined i_key_str || defined i_key_bind || defined i_key_arcbox) +#if !(defined i_key || defined i_key_str || defined i_key_ssv || \ + defined i_key_bind || defined i_key_arcbox) #define _i_key_from_val #if defined _i_ismap #error "i_key* must be defined for maps." @@ -63,6 +67,9 @@ #if defined i_val_str #define i_key_str i_val_str #endif + #if defined i_val_ssv + #define i_key_ssv i_val_ssv + #endif #if defined i_val_arcbox #define i_key_arcbox i_val_arcbox #endif @@ -89,12 +96,20 @@ #endif #endif -#ifdef i_key_str +#if defined i_key_str #define i_key_bind cstr #define i_keyraw crawstr #ifndef i_tag #define i_tag str #endif +#elif defined i_key_ssv + #define i_key_bind cstr + #define i_keyraw csview + #define i_keyfrom cstr_from_sv + #define i_keyto cstr_to_sv + #ifndef i_tag + #define i_tag ssv + #endif #elif defined i_key_arcbox #define i_key_bind i_key_arcbox #define i_keyraw c_paste(i_key_arcbox, _value) @@ -144,9 +159,6 @@ #if (!defined i_keyfrom && defined i_keydrop) || c_option(c_no_clone) #define _i_no_clone #endif -#if !defined i_hash && (defined i_keyfrom || defined i_keyclone || defined i_cmp || defined i_eq) - #define _i_no_hash -#endif #ifndef i_keyfrom #define i_keyfrom c_default_from #endif @@ -181,6 +193,12 @@ #ifdef i_val_str #define i_val_bind cstr #define i_valraw crawstr +#elif defined i_val_ssv + #define i_val cstr + #define i_valraw csview + #define i_valfrom cstr_from_sv + #define i_valto cstr_to_sv + #define i_valdrop cstr_drop #elif defined i_val_arcbox #define i_val_bind i_val_arcbox #define i_valraw c_paste(i_val_arcbox, _value) @@ -257,6 +275,7 @@ #undef i_val #undef i_val_str +#undef i_val_ssv #undef i_val_arcbox #undef i_val_bind #undef i_valraw @@ -267,6 +286,7 @@ #undef i_key #undef i_key_str +#undef i_key_ssv #undef i_key_arcbox #undef i_key_bind #undef i_keyraw -- cgit v1.2.3