From 8f57f3d331de4cb4aa7d06862c2de3424eb1ba5b Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 22 Apr 2022 12:20:31 +0200 Subject: Readded push()/emplace() to all containers missing them. Made _hash function required for i_key_bind, _eq is derived from _cmp. --- docs/cdeq_api.md | 2 ++ docs/cmap_api.md | 18 ++++++++++-------- docs/cset_api.md | 1 + docs/csmap_api.md | 3 +-- docs/csset_api.md | 1 + 5 files changed, 15 insertions(+), 10 deletions(-) (limited to 'docs') diff --git a/docs/cdeq_api.md b/docs/cdeq_api.md index 3cd4fece..aa528aa2 100644 --- a/docs/cdeq_api.md +++ b/docs/cdeq_api.md @@ -51,7 +51,9 @@ cdeq_X_value* cdeq_X_emplace_front(cdeq_X* self, i_valraw raw); void cdeq_X_pop_front(cdeq_X* self); cdeq_X_value* cdeq_X_push_back(cdeq_X* self, i_val value); +cdeq_X_value* cdeq_X_push(cdeq_X* self, i_val value); // alias for push_back() cdeq_X_value* cdeq_X_emplace_back(cdeq_X* self, i_valraw raw); +cdeq_X_value* cdeq_X_emplace(cdeq_X* self, i_valraw raw); // alias for emplace_back() void cdeq_X_pop_back(cdeq_X* self); cdeq_X_iter cdeq_X_insert(cdeq_X* self, size_t idx, i_val value); // move value diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 69257779..645b0bd0 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -67,11 +67,10 @@ cmap_X_iter cmap_X_find(const cmap_X* self, i_keyraw rkey); cmap_X_result cmap_X_insert(cmap_X* self, i_key key, i_val mapped); // no change if key in map cmap_X_result cmap_X_insert_or_assign(cmap_X* self, i_key key, i_val mapped); // always update mapped -cmap_X_result cmap_X_put(cmap_X* self, i_key key, i_val mapped); // alias for insert_or_assign +cmap_X_result cmap_X_push(cmap_X* self, i_key key, i_val mapped); // alias for insert cmap_X_result cmap_X_emplace(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map cmap_X_result cmap_X_emplace_or_assign(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped -cmap_X_result cmap_X_put_raw(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // alias for emplace_or_assign size_t cmap_X_erase(cmap_X* self, i_keyraw rkey); // return 0 or 1 cmap_X_iter cmap_X_erase_at(cmap_X* self, cmap_X_iter it); // return iter after it @@ -276,8 +275,9 @@ typedef struct { #define Viking_init() ((Viking){cstr_null, cstr_null}) -static inline bool Viking_eq(const Viking* a, const Viking* b) { - return cstr_equals_s(a->name, b->name) && cstr_equals_s(a->country, b->country); +static inline int Viking_cmp(const Viking* a, const Viking* b) { + int c = cstr_cmp(&a->name, &b->name); + return c ? c : cstr_cmp(&a->country, &b->country); } static inline uint32_t Viking_hash(const Viking* a, int ignored) { @@ -298,7 +298,7 @@ static inline void Viking_drop(Viking* vk) { #define i_key_bind Viking #define i_val int // i_key_bind auto-binds: -// #define i_eq Viking_eq +// #define i_cmp Viking_cmp // #define i_hash Viking_hash // #define i_keyfrom Viking_clone // #define i_keydrop Viking_drop @@ -361,8 +361,10 @@ static inline uint64_t RViking_hash(const RViking* raw, size_t ignore) { uint64_t hash = c_strhash(raw->name) ^ (c_strhash(raw->country) >> 15); return hash; } -static inline bool RViking_eq(const RViking* rx, const RViking* ry) { - return strcmp(rx->name, ry->name) == 0 && strcmp(rx->country, ry->country) == 0; + +static inline int RViking_cmp(const RViking* rx, const RViking* ry) { + int c = strcmp(rx->name, ry->name); + return c ? c : strcmp(rx->country, ry->country); } static inline Viking Viking_from(RViking raw) { @@ -379,7 +381,7 @@ static inline RViking Viking_toraw(const Viking* vk) { #define i_keyraw RViking // i_key_bind macro will make these functions auto-bind: // #define i_hash RViking_hash -// #define i_eq RViking_eq +// #define i_cmp RViking_cmp // #define i_keyfrom Viking_from // uses _from because i_keyraw is defined // #define i_keyto Viking_toraw // #define i_keydrop Viking_drop diff --git a/docs/cset_api.md b/docs/cset_api.md index e429c5ae..d9b412da 100644 --- a/docs/cset_api.md +++ b/docs/cset_api.md @@ -46,6 +46,7 @@ cset_X_value* cset_X_get_mut(cset_X* self, i_keyraw rkey); cset_X_iter cset_X_find(const cset_X* self, i_keyraw rkey); cset_X_result cset_X_insert(cset_X* self, i_key key); +cset_X_result cset_X_push(cset_X* self, i_key key); // alias for insert. cset_X_result cset_X_emplace(cset_X* self, i_keyraw rkey); size_t cset_X_erase(cset_X* self, i_keyraw rkey); // return 0 or 1 diff --git a/docs/csmap_api.md b/docs/csmap_api.md index 012a7d58..e73e6562 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -63,11 +63,10 @@ csmap_X_value* csmap_X_back(const csmap_X* self); csmap_X_result csmap_X_insert(csmap_X* self, i_key key, i_val mapped); // no change if key in map csmap_X_result csmap_X_insert_or_assign(csmap_X* self, i_key key, i_val mapped); // always update mapped -csmap_X_result csmap_X_put(csmap_X* self, i_key key, i_val mapped); // alias for insert_or_assign() +csmap_X_result csmap_X_push(csmap_X* self, i_key key, i_val mapped); // alias for insert() csmap_X_result csmap_X_emplace(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map csmap_X_result csmap_X_emplace_or_assign(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped -csmap_X_result csmap_X_put_raw(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // alias for emplace_or_assign size_t csmap_X_erase(csmap_X* self, i_keyraw rkey); csmap_X_iter csmap_X_erase_at(csmap_X* self, csmap_X_iter it); // returns iter after it diff --git a/docs/csset_api.md b/docs/csset_api.md index 0ce8e811..57d23ee6 100644 --- a/docs/csset_api.md +++ b/docs/csset_api.md @@ -42,6 +42,7 @@ csset_X_value* csset_X_find_it(const csset_X* self, i_keyraw rkey, csset_X csset_X_iter csset_X_lower_bound(const csset_X* self, i_keyraw rkey); // find closest entry >= rkey csset_X_result csset_X_insert(csset_X* self, i_key key); +csset_X_result csset_X_push(csset_X* self, i_key key); // alias for insert() csset_X_result csset_X_emplace(csset_X* self, i_keyraw rkey); size_t csset_X_erase(csset_X* self, i_keyraw rkey); -- cgit v1.2.3 From dd5551dec268da39ad1c5c66de014e4621d24748 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 22 Apr 2022 12:44:57 +0200 Subject: Changed API for c*map_X_push() to take a entry pair (c*map_X_value) argument instead of key + val. --- docs/cmap_api.md | 2 +- docs/csmap_api.md | 2 +- include/stc/cmap.h | 6 ++++-- include/stc/csmap.h | 13 ++++++++----- 4 files changed, 14 insertions(+), 9 deletions(-) (limited to 'docs') diff --git a/docs/cmap_api.md b/docs/cmap_api.md index 645b0bd0..03ee11a9 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -67,7 +67,7 @@ cmap_X_iter cmap_X_find(const cmap_X* self, i_keyraw rkey); cmap_X_result cmap_X_insert(cmap_X* self, i_key key, i_val mapped); // no change if key in map cmap_X_result cmap_X_insert_or_assign(cmap_X* self, i_key key, i_val mapped); // always update mapped -cmap_X_result cmap_X_push(cmap_X* self, i_key key, i_val mapped); // alias for insert +cmap_X_result cmap_X_push(cmap_X* self, cmap_X_value entry); // similar to insert cmap_X_result cmap_X_emplace(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map cmap_X_result cmap_X_emplace_or_assign(cmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped diff --git a/docs/csmap_api.md b/docs/csmap_api.md index e73e6562..ab9eb2ee 100644 --- a/docs/csmap_api.md +++ b/docs/csmap_api.md @@ -63,7 +63,7 @@ csmap_X_value* csmap_X_back(const csmap_X* self); csmap_X_result csmap_X_insert(csmap_X* self, i_key key, i_val mapped); // no change if key in map csmap_X_result csmap_X_insert_or_assign(csmap_X* self, i_key key, i_val mapped); // always update mapped -csmap_X_result csmap_X_push(csmap_X* self, i_key key, i_val mapped); // alias for insert() +csmap_X_result csmap_X_push(csmap_X* self, csmap_X_value entry); // similar to insert() csmap_X_result csmap_X_emplace(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // no change if rkey in map csmap_X_result csmap_X_emplace_or_assign(csmap_X* self, i_keyraw rkey, i_valraw rmapped); // always update rmapped diff --git a/include/stc/cmap.h b/include/stc/cmap.h index 16041094..6cde2532 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -178,8 +178,10 @@ _cx_memb(_insert)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { } STC_INLINE _cx_result -_cx_memb(_push)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { - return _cx_memb(_insert)(self, _key _i_MAP_ONLY(, _mapped)); +_cx_memb(_push)(_cx_self* self, _cx_value _val) { + _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val))); + if (_res.inserted) *_res.ref = _val; else _cx_memb(_value_drop)(&_val); + return _res; } STC_INLINE _cx_iter diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 700aa4c2..25f66d79 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -104,6 +104,7 @@ STC_API _cx_result _cx_memb(_emplace)(_cx_self* self, i_keyraw rkey _i_MAP_ #endif // !_i_no_clone STC_API _cx_self _cx_memb(_init)(void); STC_API _cx_result _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)); +STC_API _cx_result _cx_memb(_push)(_cx_self* self, _cx_value _val); STC_API void _cx_memb(_drop)(_cx_self* self); STC_API bool _cx_memb(_reserve)(_cx_self* self, size_t cap); STC_API _cx_value* _cx_memb(_find_it)(const _cx_self* self, i_keyraw rkey, _cx_iter* out); @@ -170,11 +171,6 @@ _cx_memb(_value_drop)(_cx_value* val) { { _cx_iter it; return &_cx_memb(_find_it)(self, rkey, &it)->second; } #endif // !_i_isset -STC_INLINE _cx_result -_cx_memb(_push)(_cx_self* self, i_key _key _i_MAP_ONLY(, i_val _mapped)) { - return _cx_memb(_insert)(self, _key _i_MAP_ONLY(, _mapped)); -} - STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, i_keyraw rkey) { _cx_iter it; @@ -273,6 +269,13 @@ _cx_memb(_insert)(_cx_self* self, i_key key _i_MAP_ONLY(, i_val mapped)) { return res; } +STC_DEF _cx_result +_cx_memb(_push)(_cx_self* self, _cx_value _val) { + _cx_result _res = _cx_memb(_insert_entry_)(self, i_keyto(_i_keyref(&_val))); + if (_res.inserted) *_res.ref = _val; else _cx_memb(_value_drop)(&_val); + return _res; +} + #ifndef _i_isset STC_DEF _cx_result _cx_memb(_insert_or_assign)(_cx_self* self, i_key key, i_val mapped) { -- cgit v1.2.3 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(-) (limited to 'docs') 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 From 6d8406e66c029d4c672bb7531aabec7eb1d079d8 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 24 Apr 2022 13:31:11 +0200 Subject: Created VERSION 3.5. See News section in docs for changes. --- README.md | 13 +- benchmarks/misc/sso_bench.c | 52 ----- benchmarks/misc/sso_bench.cpp | 115 +++++++++++ benchmarks/misc/sso_bench2.cpp | 114 ----------- benchmarks/misc/string_bench.c | 153 --------------- benchmarks/misc/string_bench.cpp | 199 ------------------- benchmarks/misc/string_bench_STC.cpp | 298 ++++++++++++++++++++++++++++ benchmarks/misc/string_bench_STD.cpp | 370 +++++++++++++++++++++++++++++++++++ docs/cstr_api.md | 1 + docs/csview_api.md | 2 +- include/stc/ccommon.h | 19 +- include/stc/cstr.h | 74 ++++--- include/stc/csview.h | 17 +- include/stc/template.h | 5 +- 14 files changed, 852 insertions(+), 580 deletions(-) delete mode 100644 benchmarks/misc/sso_bench.c create mode 100644 benchmarks/misc/sso_bench.cpp delete mode 100644 benchmarks/misc/sso_bench2.cpp delete mode 100644 benchmarks/misc/string_bench.c delete mode 100644 benchmarks/misc/string_bench.cpp create mode 100644 benchmarks/misc/string_bench_STC.cpp create mode 100644 benchmarks/misc/string_bench_STD.cpp (limited to 'docs') diff --git a/README.md b/README.md index 754f58f4..8bc3e7fa 100644 --- a/README.md +++ b/README.md @@ -3,12 +3,13 @@ STC - Smart Template Containers for C ===================================== -News: Version 3 released (Jan 2022) ------------------------------------ -This version introduces lots of enhancements, bugfixes and additions. There are also -a number of [breaking changes](#brief-summary-of-changes) and [a migration guide from version 2 to 3](#migration-guide-from-version-2-to-3). -With version 3, the API is freezed as far as possible. Any changes will be handled with long -lasting deprecations, so you may develop production code using it. +News: Version 3.5 released (Mar 2022) +------------------------------------- +- Swapped to new **cstr** (*short string optimized*, aka SSO). Note that `cstr_str(&s)` must be used, `s.str` is no longer usable. +- Added general `i_clone` template parameter: containers with smart pointers (**carc**, **cbox**) can now be correctly cloned. +- Optimized *c_default_hash()*. Therefore *c_hash32()* and *c_hash64()* are removed (same speed). +- Added *.._push()* and *.._emplace()* function to all containers to allow for more generic coding. +- Added some examples and benchmarks for SSO and heterogenous lookup comparison with c++20 (string_bench_*.cpp). Introduction ------------ diff --git a/benchmarks/misc/sso_bench.c b/benchmarks/misc/sso_bench.c deleted file mode 100644 index f2714be1..00000000 --- a/benchmarks/misc/sso_bench.c +++ /dev/null @@ -1,52 +0,0 @@ -// https://gobyexample.com/maps -#include -#define i_type Map -#define i_key_str -#define i_val int -#include -#define i_type Vec -#define i_val_str -#include - -#include -#include - -void rndstr(char buf[64], int max) { - unsigned n = crandom() % max; - static char chr[64] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_"; - c_forrange (i, n) - buf[i] = chr[crandom() & 63]; - buf[n] = '\0'; -} - -enum {N = 10000000}; - -int main(void) { - - c_auto (Vec, vec) - c_auto (Map, map) { - char buf[128]; - - csrandom(time(NULL)); - printf("map\n"); - clock_t t0 = clock(), t1, t2; - c_forrange (i, int, N) { - rndstr(buf, 64); - Map_emplace(&map, buf, i); - } - t1 = clock(); - printf("vec\n"); - c_apply_cnt(v, Vec_push(&vec, cstr_clone(v->first)), Map, map); - t2 = clock(); - puts("map items:"); - int k = 0; - c_forpair (k, v, Map, map) - if (k++ == 5) break; else printf(" %s: %d\n", cstr_str(&_.k), _.v); - puts("vec items:"); - k = 0; - c_foreach (i, Vec, vec) - if (k++ == 5) break; else printf(" %s\n", cstr_str(i.ref)); - - printf("\nmap insert: %d ms\nvec pushes: %d ms\n", (int)((t1 - t0)*10000/CLOCKS_PER_SEC), (int)((t2 - t1)*10000/CLOCKS_PER_SEC)); - } -} diff --git a/benchmarks/misc/sso_bench.cpp b/benchmarks/misc/sso_bench.cpp new file mode 100644 index 00000000..08444320 --- /dev/null +++ b/benchmarks/misc/sso_bench.cpp @@ -0,0 +1,115 @@ +#include +#include +#include +#include +#define i_type svec +#define i_val_str +#include + +#define ROTL_(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) + +static uint64_t g_romutrio[3] = { + 0x26aa069ea2fb1a4dULL, 0x70c72c95cd592d04ULL, + 0x504f333d3aa0b359ULL, +}; + +static inline uint64_t romutrio(void) { + uint64_t *s = g_romutrio, xp = s[0], yp = s[1], zp = s[2]; + s[0] = 15241094284759029579u * zp; + s[1] = yp - xp; s[1] = ROTL_(s[1], 12); + s[2] = zp - yp; s[2] = ROTL_(s[2], 44); + return xp; +} + +static void sromutrio(uint64_t seed) { + uint64_t *s = g_romutrio; + s[0] = 0x26aa069ea2fb1a4dULL + seed; + s[1] = 0x70c72c95cd592d04ULL + seed; + s[2] = 0x504f333d3aa0b359ULL + seed; +} + + +static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-"; + +static const int BENCHMARK_SIZE = 5000000; +static const int MAX_STRING_LENGTH = 25; + +using time_point = std::chrono::high_resolution_clock::time_point; + +void addRandomString_STD(std::vector& vec, const int length) { + std::string s(length, 0); + char* p = &s[0]; + for (int i = 0; i < length; ++i) { + p[i] = CHARS[romutrio() & 63]; + } + s.append(s); + vec.push_back(s); +} + +void addRandomString_STC(svec& vec, const int length) { + cstr s = cstr_with_size(length, 0); + char* p = cstr_data(&s); + for (int i = 0; i < length; ++i) { + p[i] = CHARS[romutrio() & 63]; + } + cstr_append_s(&s, s); + svec_push_back(&vec, s); +} + +template +void benchmark(L& vec, const int length, R addRandomString) { + time_point t1 = std::chrono::high_resolution_clock::now(); + + if (length == 0) + for (int i = 0; i < BENCHMARK_SIZE; i++) + addRandomString(vec, (i*13 & 31) + 1); + else + for (int i = 0; i < BENCHMARK_SIZE; i++) + addRandomString(vec, length); + + time_point t2 = std::chrono::high_resolution_clock::now(); + const auto duration = std::chrono::duration_cast(t2 - t1).count(); + std::cerr << length*2 << "\t" << duration; +} + + +int main() { + uint64_t seed = 4321; + sromutrio(seed); + std::cerr << "length\ttime\tstd::string\n"; + for (int k = 0; k < 4; k++) { + std::vector vec; vec.reserve(BENCHMARK_SIZE); + benchmark(vec, 0, addRandomString_STD); + std::cout << '\t' << vec[0] << '\n'; + } + + sromutrio(seed); + std::cerr << "\nlength\ttime\tSTC string\n"; + for (int k = 0; k < 4; k++) { + svec vec = svec_with_capacity(BENCHMARK_SIZE); + benchmark(vec, 0, addRandomString_STC); + std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; + svec_drop(&vec); + } + + sromutrio(seed); + std::cerr << "length\ttime\tstd::string\n"; + for (int length = 1; length <= MAX_STRING_LENGTH; length++) { + std::vector vec; vec.reserve(BENCHMARK_SIZE); + benchmark(vec, length, addRandomString_STD); + std::cout << '\t' << vec[0] << '\n'; + } + + sromutrio(seed); + std::cerr << "\nlength\ttime\tSTC string\n"; + for (int length = 1; length <= MAX_STRING_LENGTH; length++) { + svec vec = svec_with_capacity(BENCHMARK_SIZE); + benchmark(vec, length, addRandomString_STC); + std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; + svec_drop(&vec); + } + + std::cerr << "sizeof std::string : " << sizeof(std::string) << std::endl + << "sizeof STC string : " << sizeof(cstr) << std::endl; + return 0; +} diff --git a/benchmarks/misc/sso_bench2.cpp b/benchmarks/misc/sso_bench2.cpp deleted file mode 100644 index 1355a727..00000000 --- a/benchmarks/misc/sso_bench2.cpp +++ /dev/null @@ -1,114 +0,0 @@ -#include -#include -#include -#include -#define i_type svec -#define i_val_str -#include - -#define ROTL_(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) - -static uint64_t g_romutrio[3] = { - 0x26aa069ea2fb1a4dULL, 0x70c72c95cd592d04ULL, - 0x504f333d3aa0b359ULL, -}; - -static inline uint64_t romutrio(void) { - uint64_t *s = g_romutrio, xp = s[0], yp = s[1], zp = s[2]; - s[0] = 15241094284759029579u * zp; - s[1] = yp - xp; s[1] = ROTL_(s[1], 12); - s[2] = zp - yp; s[2] = ROTL_(s[2], 44); - return xp; -} - -static void sromutrio(uint64_t seed) { - uint64_t *s = g_romutrio; - s[0] = 0x26aa069ea2fb1a4dULL + seed; - s[1] = 0x70c72c95cd592d04ULL + seed; - s[2] = 0x504f333d3aa0b359ULL + seed; -} - - -static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-"; - -static const int BENCHMARK_SIZE = 5000000; -static const int MAX_STRING_LENGTH = 20; - -using time_point = std::chrono::high_resolution_clock::time_point; - -void addRandomString_STD(std::vector& vec, const int length) { - std::string s(length, 0); - char* p = &s[0]; - for (int i = 0; i < length; ++i) { - p[i] = CHARS[romutrio() & 63]; - } - s.append(s); - vec.push_back(s); -} - -void addRandomString_STC(svec& vec, const int length) { - cstr s = cstr_with_size(length, 0); - char* p = cstr_data(&s); - for (int i = 0; i < length; ++i) { - p[i] = CHARS[romutrio() & 63]; - } - cstr_append_s(&s, s); - svec_push(&vec, s); -} - -template -void benchmark(L& vec, const int length, R addRandomString) { - time_point t1 = std::chrono::high_resolution_clock::now(); - - if (length == 0) - for (int i = 0; i < BENCHMARK_SIZE; i++) - addRandomString(vec, (i*13 & 31) + 1); - else - for (int i = 0; i < BENCHMARK_SIZE; i++) - addRandomString(vec, length); - - time_point t2 = std::chrono::high_resolution_clock::now(); - const auto duration = std::chrono::duration_cast(t2 - t1).count(); - std::cerr << length*2 << "\t" << duration; -} - - -int main() { - sromutrio(1234); - std::cerr << "length\ttime\tstd::string\n"; - for (int k = 0; k < 4; k++) { - std::vector vec; vec.reserve(BENCHMARK_SIZE); - benchmark(vec, 0, addRandomString_STD); - std::cout << '\t' << vec[0] << '\n'; - } - - sromutrio(1234); - std::cerr << "\nlength\ttime\tSTC string\n"; - for (int k = 0; k < 4; k++) { - svec vec = svec_with_capacity(BENCHMARK_SIZE); - benchmark(vec, 0, addRandomString_STC); - std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; - svec_drop(&vec); - } - - sromutrio(1234); - std::cerr << "length\ttime\tstd::string\n"; - for (int length = 1; length <= MAX_STRING_LENGTH; length++) { - std::vector vec; vec.reserve(BENCHMARK_SIZE); - benchmark(vec, length, addRandomString_STD); - std::cout << '\t' << vec[0] << '\n'; - } - - sromutrio(1234); - std::cerr << "\nlength\ttime\tSTC string\n"; - for (int length = 1; length <= MAX_STRING_LENGTH; length++) { - svec vec = svec_with_capacity(BENCHMARK_SIZE); - benchmark(vec, length, addRandomString_STC); - std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; - svec_drop(&vec); - } - - std::cerr << "size std::string : " << sizeof(std::string) << std::endl - << "size STC string : " << sizeof(cstr) << std::endl; - return 0; -} diff --git a/benchmarks/misc/string_bench.c b/benchmarks/misc/string_bench.c deleted file mode 100644 index fb2a70b2..00000000 --- a/benchmarks/misc/string_bench.c +++ /dev/null @@ -1,153 +0,0 @@ -// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark -// https://github.com/shaovoon/cpp_hetero_lookup_bench - -#include - -#define i_val_str -#include - -#define i_key_str -#define i_val size_t -#include - -#define i_key_str -#define i_val size_t -#include - - -cvec_str read_file(const char* name) -{ - cvec_str data = cvec_str_init(); - c_auto (cstr, line) - c_autovar (FILE* f = fopen(name, "r"), fclose(f)) - while (cstr_getline(&line, f)) - cvec_str_emplace_back(&data, cstr_str(&line)); - return data; -} - -void initShortStringVec(cvec_str* vs) -{ - cvec_str_clear(vs); - - *vs = read_file("names.txt"); - size_t lengths = 0; - c_foreach (i, cvec_str, *vs) - { - cstr_append_s(i.ref, *i.ref); - cstr_append_s(i.ref, *i.ref); - lengths += cstr_size(*i.ref); - } - printf("avg len: %f\n", (float)lengths / cvec_str_size(*vs)); -} - -void initLongStringVec(cvec_str* vs) -{ - cvec_str_clear(vs); - *vs = read_file("names.txt"); - cstr* s = vs->data; - size_t lengths = 0; - cstr_append_s(s, s[1]); - cstr_append_s(s, s[2]); - cstr_append_s(s, s[3]); - for (int i=1; i < cvec_str_size(*vs); ++i) - { - cstr* t = vs->data + i; - cstr_append_s(t, *t); - cstr_append_s(t, *t); - cstr_append_s(t, *s); - cstr_append_s(t, *t); - cstr_append_s(t, *t); - lengths += cstr_size(*t); - } - printf("avg len: %f\n", (float)lengths / cvec_str_size(*vs)); -} - -struct Maps { - csmap_str* snormal; - cmap_str* unormal; -}; - -void initMaps(cvec_str vs, struct Maps maps) -{ - csmap_str_clear(maps.snormal); - cmap_str_clear(maps.unormal); - - for (size_t i = 0; i < cvec_str_size(vs); ++i) - { - cstr str = *cvec_str_at(&vs, i); - csmap_str_insert(maps.snormal, cstr_clone(str), i); - cmap_str_insert(maps.unormal, cstr_clone(str), i); - } -} - -void benchmark(cvec_str vec_string, struct Maps maps); - -static const size_t MAX_LOOP = 2000; - -int main() -{ - c_auto (cvec_str, vec_string) - c_auto (csmap_str, snormal) - c_auto (cmap_str, unormal) - { - struct Maps maps = { &snormal, &unormal }; - - initShortStringVec(&vec_string); - initMaps(vec_string, maps); - - puts("Short String Benchmark"); - puts("======================"); - - benchmark(vec_string, maps); - - puts("\nLong String Benchmark"); - puts("======================"); - - initLongStringVec(&vec_string); - initMaps(vec_string, maps); - - benchmark(vec_string, maps); - } -} - -void benchmark(cvec_str vec_string, struct Maps maps) -{ - size_t grandtotal = 0; - size_t total; - clock_t stopwatch; - - total = 0; - printf("%32s", "Trans Map with char*"); - stopwatch = clock(); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - csmap_str_iter it, end = csmap_str_end(maps.snormal); - for (size_t j = 0; j < cvec_str_size(vec_string); ++j) - { - csmap_str_find_it(maps.snormal, cstr_str(&vec_string.data[j]), &it); - if (it.ref != end.ref) - total += it.ref->second; - } - } - grandtotal += total; - printf(" timing:%5.0fms\n", (clock() - stopwatch) / (float)CLOCKS_PER_SEC * 1000.0f); - - - total = 0; - printf("%32s", "Trans Unord Map with char*"); - stopwatch = clock(); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - cmap_str_iter it, end = cmap_str_end(maps.unormal); - for (size_t j = 0; j < cvec_str_size(vec_string); ++j) - { - it = cmap_str_find(maps.unormal, cstr_str(&vec_string.data[j])); - if (it.ref != end.ref) - total += it.ref->second; - } - } - grandtotal += total; - printf(" timing:%5.0fms\n", (clock() - stopwatch) / (float)CLOCKS_PER_SEC * 1000.0f); - - printf("C grandtotal: %" PRIuMAX " <--- Ignore this\n", grandtotal); -} diff --git a/benchmarks/misc/string_bench.cpp b/benchmarks/misc/string_bench.cpp deleted file mode 100644 index 65bf7a0e..00000000 --- a/benchmarks/misc/string_bench.cpp +++ /dev/null @@ -1,199 +0,0 @@ -// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark -// https://github.com/shaovoon/cpp_hetero_lookup_bench - -#include -#include -#include -#include -#include -#include -#include - -#define i_val_str -#include - - -std::vector read_file(const char* name) -{ - std::vector data; - c_auto (cstr, line) - c_autovar (FILE* f = fopen(name, "r"), fclose(f)) - while (cstr_getline(&line, f)) - data.emplace_back(cstr_str(&line)); - return data; -} - -class timer -{ -public: - timer() = default; - void start(const std::string& text_) - { - text = text_; - begin = std::chrono::high_resolution_clock::now(); - } - void stop() - { - auto end = std::chrono::high_resolution_clock::now(); - auto dur = end - begin; - auto ms = std::chrono::duration_cast(dur).count(); - std::cout << std::setw(32) << text << " timing:" << std::setw(5) << ms << "ms" << std::endl; - } - -private: - std::string text; - std::chrono::high_resolution_clock::time_point begin; -}; - -void initShortStringVec(std::vector& vs) -{ - vs.clear(); - vs = read_file("names.txt"); - size_t num = 0; - - for (size_t i = 0; i < vs.size(); ++i) - { - num += vs[i].size(); - } - printf("avg len: %f\n", (float)num / vs.size()); -} - -void initLongStringVec(std::vector& vs) -{ - vs.clear(); - vs = read_file("names.txt"); - size_t num = 0; - vs[0] += vs[1]; - vs[0] += vs[2]; - vs[0] += vs[3]; - for (size_t i = 1; i < vs.size(); ++i) - { - vs[i] += vs[i]; - vs[i] += vs[i]; - vs[i] += vs[0]; - vs[i] += vs[i]; - vs[i] += vs[i]; - num += vs[i].size(); - } - printf("avg len: %f\n", (float)num / vs.size()); -} - -void initMapNormal(const std::vector& vs, - std::map& mapNormal, - std::unordered_map& unordmapNormal) -{ - mapNormal.clear(); - unordmapNormal.clear(); - for (size_t i = 0; i < vs.size(); ++i) - { - mapNormal.insert(std::make_pair(vs.at(i), i)); - unordmapNormal.insert(std::make_pair(vs.at(i), i)); - } -} -/* -struct string_hash { - using is_transparent = void; - using hash_type = std::hash; // just a helper local type - size_t operator()(const std::string& txt) const { return hash_type{}(txt); } - size_t operator()(const char* txt) const { return hash_type{}(txt); } -};*/ - -void benchmark( - const std::vector& vec_string, - const std::map& mapNormal, - const std::unordered_map& unordmapNormal); - -const size_t MAX_LOOP = 2000; - -int main() -{ - std::vector vec_string; - - std::map mapNormal; - std::unordered_map unordmapNormal; - - initShortStringVec(vec_string); - initMapNormal(vec_string, mapNormal, unordmapNormal); - - std::cout << "Short String Benchmark" << std::endl; - std::cout << "======================" << std::endl; - - benchmark(vec_string, mapNormal, unordmapNormal); - - std::cout << "Long String Benchmark" << std::endl; - std::cout << "=====================" << std::endl; - - initLongStringVec(vec_string); - initMapNormal(vec_string, mapNormal, unordmapNormal); - - benchmark(vec_string, mapNormal, unordmapNormal); - return 0; -} - -void benchmark( - const std::vector& vec_string, - const std::map& mapNormal, - const std::unordered_map& unordmapNormal) -{ - size_t grandtotal = 0; - size_t total = 0; - timer stopwatch; - - total = 0; - stopwatch.start("Normal Map with string"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = mapNormal.find(vec_string[j]); - if(it!=mapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - total = 0; - stopwatch.start("Normal Map with char*"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = mapNormal.find(vec_string[j].c_str()); - if (it != mapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - total = 0; - stopwatch.start("Normal Unord Map with string"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = unordmapNormal.find(vec_string[j]); - if (it != unordmapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - total = 0; - stopwatch.start("Normal Unord Map with char*"); - for (size_t i = 0; i < MAX_LOOP; ++i) - { - for (size_t j = 0; j < vec_string.size(); ++j) - { - const auto& it = unordmapNormal.find(vec_string[j].c_str()); - if (it != unordmapNormal.cend()) - total += it->second; - } - } - grandtotal += total; - stopwatch.stop(); - - std::cout << "C++ grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl; -} \ No newline at end of file diff --git a/benchmarks/misc/string_bench_STC.cpp b/benchmarks/misc/string_bench_STC.cpp new file mode 100644 index 00000000..ed0e3243 --- /dev/null +++ b/benchmarks/misc/string_bench_STC.cpp @@ -0,0 +1,298 @@ +// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark +// https://github.com/shaovoon/cpp_hetero_lookup_bench + +#include +#include +#include +#include // string +#include // string_view + +#define i_key_str +#include // vec of cstr with const char* lookup + +#define i_type cvec_sv // override default type name (cvec_csview) +#define i_key csview +#define i_cmp csview_cmp +#include // cvec_vs: vec of csview + +#define i_key_str +#define i_val size_t +#include // sorted map of cstr, const char* lookup + +#define i_key_ssv +#define i_val size_t +#include // sorted map of cstr, csview lookup + +#define i_key_str +#define i_val size_t +#include // unordered map of cstr, const char* lookup + +#define i_key_ssv +#define i_val size_t +#include // unordered map of cstr, csview lookup + + +cvec_str read_file(const char* name) +{ + cvec_str data = cvec_str_init(); + c_auto (cstr, line) + c_autovar (FILE* f = fopen(name, "r"), fclose(f)) + while (cstr_getline(&line, f)) + cvec_str_emplace_back(&data, cstr_str(&line)); + return data; +} + +class timer +{ +public: + timer() = default; + void start(const std::string& text_) + { + text = text_; + begin = std::chrono::high_resolution_clock::now(); + } + void stop() + { + auto end = std::chrono::high_resolution_clock::now(); + auto dur = end - begin; + auto ms = std::chrono::duration_cast(dur).count(); + std::cout << std::setw(32) << text << " timing:" << std::setw(5) << ms << "ms" << std::endl; + } + +private: + std::string text; + std::chrono::high_resolution_clock::time_point begin; +}; + +void initShortStringVec(cvec_str* vs, cvec_sv* vsv) +{ + cvec_str_clear(vs); + cvec_sv_clear(vsv); + + *vs = read_file("names.txt"); +/* + cvec_str_emplace_back(vs, "Susan"); + cvec_str_emplace_back(vs, "Jason"); + cvec_str_emplace_back(vs, "Lily"); + cvec_str_emplace_back(vs, "Michael"); + cvec_str_emplace_back(vs, "Mary"); + + cvec_str_emplace_back(vs, "Jerry"); + cvec_str_emplace_back(vs, "Jenny"); + cvec_str_emplace_back(vs, "Klaus"); + cvec_str_emplace_back(vs, "Celine"); + cvec_str_emplace_back(vs, "Kenny"); + + cvec_str_emplace_back(vs, "Kelly"); + cvec_str_emplace_back(vs, "Jackson"); + cvec_str_emplace_back(vs, "Mandy"); + cvec_str_emplace_back(vs, "Terry"); + cvec_str_emplace_back(vs, "Sandy"); + + cvec_str_emplace_back(vs, "Billy"); + cvec_str_emplace_back(vs, "Cindy"); + cvec_str_emplace_back(vs, "Phil"); + cvec_str_emplace_back(vs, "Lindy"); + cvec_str_emplace_back(vs, "David"); +*/ + size_t num = 0; + c_foreach (i, cvec_str, *vs) + { + cvec_sv_push_back(vsv, csview_from_s(i.ref)); + num += cstr_size(*i.ref); + } + std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl; + std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl; +} + +void initLongStringVec(cvec_str* vs, cvec_sv* vsv) +{ + cvec_str_clear(vs); + cvec_sv_clear(vsv); + + *vs = read_file("names.txt"); + c_foreach (i, cvec_str, *vs) { + cstr_append_s(i.ref, *i.ref); + cstr_append_s(i.ref, *i.ref); + cstr_append_s(i.ref, *i.ref); + } +/* + cvec_str_emplace_back(vs, "Susan Susan Susan Susan Susan Susan"); + cvec_str_emplace_back(vs, "Jason Jason Jason Jason Jason Jason"); + cvec_str_emplace_back(vs, "Lily Lily Lily Lily Lily Lily"); + cvec_str_emplace_back(vs, "Michael Michael Michael Michael Michael Michael"); + cvec_str_emplace_back(vs, "Mary Mary Mary Mary Mary Mary"); + + cvec_str_emplace_back(vs, "Jerry Jerry Jerry Jerry Jerry Jerry"); + cvec_str_emplace_back(vs, "Jenny Jenny Jenny Jenny Jenny Jenny"); + cvec_str_emplace_back(vs, "Klaus Klaus Klaus Klaus Klaus Klaus"); + cvec_str_emplace_back(vs, "Celine Celine Celine Celine Celine Celine"); + cvec_str_emplace_back(vs, "Kenny Kenny Kenny Kenny Kenny Kenny"); + + cvec_str_emplace_back(vs, "Kelly Kelly Kelly Kelly Kelly Kelly"); + cvec_str_emplace_back(vs, "Jackson Jackson Jackson Jackson Jackson Jackson"); + cvec_str_emplace_back(vs, "Mandy Mandy Mandy Mandy Mandy Mandy"); + cvec_str_emplace_back(vs, "Terry Terry Terry Terry Terry Terry"); + cvec_str_emplace_back(vs, "Sandy Sandy Sandy Sandy Sandy Sandy"); + + cvec_str_emplace_back(vs, "Billy Billy Billy Billy Billy Billy"); + cvec_str_emplace_back(vs, "Cindy Cindy Cindy Cindy Cindy Cindy"); + cvec_str_emplace_back(vs, "Phil Phil Phil Phil Phil Phil"); + cvec_str_emplace_back(vs, "Lindy Lindy Lindy Lindy Lindy Lindy"); + cvec_str_emplace_back(vs, "David David David David David David"); +*/ + size_t num = 0; + c_foreach (i, cvec_str, *vs) + { + cvec_sv_push_back(vsv, csview_from_s(i.ref)); + num += cstr_size(*i.ref); + } + std::cout << "num strings: " << cvec_sv_size(*vsv) << std::endl; + std::cout << "avg str len: " << num / (float)cvec_sv_size(*vsv) << std::endl; +} + +void initMaps(const cvec_str* vs, csmap_str* mapTrans, csmap_ssv* mapSview, + cmap_str* unordmapTrans, cmap_ssv* unordmapSview) +{ + csmap_str_clear(mapTrans); + csmap_ssv_clear(mapSview); + cmap_str_clear(unordmapTrans); + cmap_ssv_clear(unordmapSview); + + size_t n = 0; + c_foreach (i, cvec_str, *vs) + { + csmap_str_insert(mapTrans, cstr_clone(*i.ref), n); + csmap_ssv_insert(mapSview, cstr_clone(*i.ref), n); + cmap_str_insert(unordmapTrans, cstr_clone(*i.ref), n); + cmap_ssv_insert(unordmapSview, cstr_clone(*i.ref), n); + ++n; + } +} + +void benchmark( + const cvec_str* vec_string, + const cvec_sv* vec_stringview, + const csmap_str* mapTrans, + const csmap_ssv* mapSview, + const cmap_str* unordmapTrans, + const cmap_ssv* unordmapSview); + +//const size_t MAX_LOOP = 1000000; +const size_t MAX_LOOP = 2000; + +int main() +{ + c_auto (cvec_str, vec_string) + c_auto (cvec_sv, vec_stringview) + c_auto (csmap_str, mapTrans) + c_auto (csmap_ssv, mapSview) + c_auto (cmap_str, unordmapTrans) + c_auto (cmap_ssv, unordmapSview) + { + std::cout << "Short String Benchmark" << std::endl; + std::cout << "======================" << std::endl; + + initShortStringVec(&vec_string, &vec_stringview); + initMaps(&vec_string, &mapTrans, &mapSview, + &unordmapTrans, &unordmapSview); + + for (int i=0; i<3; ++i) + benchmark( + &vec_string, + &vec_stringview, + &mapTrans, + &mapSview, + &unordmapTrans, + &unordmapSview); + + std::cout << "Long String Benchmark" << std::endl; + std::cout << "=====================" << std::endl; + + initLongStringVec(&vec_string, &vec_stringview); + initMaps(&vec_string, &mapTrans, &mapSview, + &unordmapTrans, &unordmapSview); + for (int i=0; i<3; ++i) + benchmark( + &vec_string, + &vec_stringview, + &mapTrans, + &mapSview, + &unordmapTrans, + &unordmapSview); + } + return 0; +} + +void benchmark( + const cvec_str* vec_string, + const cvec_sv* vec_stringview, + const csmap_str* mapTrans, + const csmap_ssv* mapSview, + const cmap_str* unordmapTrans, + const cmap_ssv* unordmapSview) +{ + size_t grandtotal = 0; + + size_t total = 0; + + timer stopwatch; + total = 0; + stopwatch.start("Trans Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_str, *vec_string) + { + const csmap_str_value* v = csmap_str_get(mapTrans, cstr_str(j.ref)); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_sv, *vec_stringview) + { + const csmap_ssv_value* v = csmap_ssv_get(mapSview, *j.ref); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Unord Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_str, *vec_string) + { + const cmap_str_value* v = cmap_str_get(unordmapTrans, cstr_str(j.ref)); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Unord Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + c_foreach (j, cvec_sv, *vec_stringview) + { + const cmap_ssv_value* v = cmap_ssv_get(unordmapSview, *j.ref); + if (v) + total += v->second; + } + } + grandtotal += total; + stopwatch.stop(); + + std::cout << "grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl; + +} diff --git a/benchmarks/misc/string_bench_STD.cpp b/benchmarks/misc/string_bench_STD.cpp new file mode 100644 index 00000000..595ab632 --- /dev/null +++ b/benchmarks/misc/string_bench_STD.cpp @@ -0,0 +1,370 @@ +// https://www.codeproject.com/Tips/5255442/Cplusplus14-20-Heterogeneous-Lookup-Benchmark +// https://github.com/shaovoon/cpp_hetero_lookup_bench +// Requires c++20, e.g. g++ -std=c++20 + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +std::vector read_file(const char* name) +{ + std::vector data; + c_auto (cstr, line) + c_autovar (FILE* f = fopen(name, "r"), fclose(f)) + while (cstr_getline(&line, f)) + data.emplace_back(cstr_str(&line)); + return data; +} + +class timer +{ +public: + timer() = default; + void start(const std::string& text_) + { + text = text_; + begin = std::chrono::high_resolution_clock::now(); + } + void stop() + { + auto end = std::chrono::high_resolution_clock::now(); + auto dur = end - begin; + auto ms = std::chrono::duration_cast(dur).count(); + std::cout << std::setw(32) << text << " timing:" << std::setw(5) << ms << "ms" << std::endl; + } + +private: + std::string text; + std::chrono::high_resolution_clock::time_point begin; +}; + +void initShortStringVec(std::vector& vs, std::vector& vsv) +{ + vs.clear(); + vsv.clear(); + + vs = read_file("names.txt"); +/* + vs.push_back("Susan"); + vs.push_back("Jason"); + vs.push_back("Lily"); + vs.push_back("Michael"); + vs.push_back("Mary"); + + vs.push_back("Jerry"); + vs.push_back("Jenny"); + vs.push_back("Klaus"); + vs.push_back("Celine"); + vs.push_back("Kenny"); + + vs.push_back("Kelly"); + vs.push_back("Jackson"); + vs.push_back("Mandy"); + vs.push_back("Terry"); + vs.push_back("Sandy"); + + vs.push_back("Billy"); + vs.push_back("Cindy"); + vs.push_back("Phil"); + vs.push_back("Lindy"); + vs.push_back("David"); +*/ + size_t num = 0; + for (size_t i = 0; i < vs.size(); ++i) + { + vsv.push_back(vs.at(i)); + num += vs.at(i).size(); + } + std::cout << "num strings: " << vsv.size() << std::endl; + std::cout << "avg str len: " << num / (float)vsv.size() << std::endl; +} + +void initLongStringVec(std::vector& vs, std::vector& vsv) +{ + vs.clear(); + vsv.clear(); + + vs = read_file("names.txt"); + for (size_t i = 1; i < vs.size(); ++i) { + vs[i] += vs[i]; + vs[i] += vs[i]; + vs[i] += vs[i]; + } +/* + vs.push_back("Susan Susan Susan Susan Susan Susan"); + vs.push_back("Jason Jason Jason Jason Jason Jason"); + vs.push_back("Lily Lily Lily Lily Lily Lily"); + vs.push_back("Michael Michael Michael Michael Michael Michael"); + vs.push_back("Mary Mary Mary Mary Mary Mary"); + + vs.push_back("Jerry Jerry Jerry Jerry Jerry Jerry"); + vs.push_back("Jenny Jenny Jenny Jenny Jenny Jenny"); + vs.push_back("Klaus Klaus Klaus Klaus Klaus Klaus"); + vs.push_back("Celine Celine Celine Celine Celine Celine"); + vs.push_back("Kenny Kenny Kenny Kenny Kenny Kenny"); + + vs.push_back("Kelly Kelly Kelly Kelly Kelly Kelly"); + vs.push_back("Jackson Jackson Jackson Jackson Jackson Jackson"); + vs.push_back("Mandy Mandy Mandy Mandy Mandy Mandy"); + vs.push_back("Terry Terry Terry Terry Terry Terry"); + vs.push_back("Sandy Sandy Sandy Sandy Sandy Sandy"); + + vs.push_back("Billy Billy Billy Billy Billy Billy"); + vs.push_back("Cindy Cindy Cindy Cindy Cindy Cindy"); + vs.push_back("Phil Phil Phil Phil Phil Phil"); + vs.push_back("Lindy Lindy Lindy Lindy Lindy Lindy"); + vs.push_back("David David David David David David"); +*/ + size_t num = 0; + for (size_t i = 0; i < vs.size(); ++i) + { + vsv.push_back(vs.at(i)); + num += vs.at(i).size(); + } + std::cout << "num strings: " << vsv.size() << std::endl; + std::cout << "avg str len: " << num / (float)vsv.size() << std::endl; +} + +void initMapNormal(const std::vector& vs, std::map& mapNormal) +{ + mapNormal.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + mapNormal.insert(std::make_pair(vs.at(i), i)); + } +} + +void initMapTrans(const std::vector& vs, std::map >& mapTrans) +{ + mapTrans.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + mapTrans.insert(std::make_pair(vs.at(i), i)); + } +} + +struct MyEqual : public std::equal_to<> +{ + using is_transparent = void; +}; + +struct string_hash { + using is_transparent = void; + using key_equal = std::equal_to<>; // Pred to use + using hash_type = std::hash; // just a helper local type + size_t operator()(std::string_view txt) const { return hash_type{}(txt); } + size_t operator()(const std::string& txt) const { return hash_type{}(txt); } + size_t operator()(const char* txt) const { return hash_type{}(txt); } +}; + +void initUnorderedMapNormal(const std::vector& vs, std::unordered_map& unordmapNormal) +{ + unordmapNormal.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + unordmapNormal.insert(std::make_pair(vs.at(i), i)); + } +} + +void initUnorderedMapTrans(const std::vector& vs, std::unordered_map& unordmapTrans) +{ + unordmapTrans.clear(); + for (size_t i = 0; i < vs.size(); ++i) + { + unordmapTrans.insert(std::make_pair(vs.at(i), i)); + } +} + +void benchmark( + const std::vector& vec_shortstr, + const std::vector& vec_shortstrview, + const std::map& mapNormal, + const std::map >& mapTrans, + const std::unordered_map& unordmapNormal, + const std::unordered_map& unordmapTrans); + +//const size_t MAX_LOOP = 1000000; +const size_t MAX_LOOP = 2000; + +int main() +{ + std::vector vec_shortstr; + std::vector vec_shortstrview; + + std::map mapNormal; + std::map > mapTrans; + initShortStringVec(vec_shortstr, vec_shortstrview); + initMapNormal(vec_shortstr, mapNormal); + initMapTrans(vec_shortstr, mapTrans); + + std::unordered_map unordmapNormal; + std::unordered_map unordmapTrans; + initUnorderedMapNormal(vec_shortstr, unordmapNormal); + initUnorderedMapTrans(vec_shortstr, unordmapTrans); + + std::cout << "Short String Benchmark" << std::endl; + std::cout << "======================" << std::endl; + + for (int i=0; i<3; ++i) benchmark( + vec_shortstr, + vec_shortstrview, + mapNormal, + mapTrans, + unordmapNormal, + unordmapTrans); + + std::cout << "Long String Benchmark" << std::endl; + std::cout << "=====================" << std::endl; + + initLongStringVec(vec_shortstr, vec_shortstrview); + initMapNormal(vec_shortstr, mapNormal); + initMapTrans(vec_shortstr, mapTrans); + + initUnorderedMapNormal(vec_shortstr, unordmapNormal); + initUnorderedMapTrans(vec_shortstr, unordmapTrans); + + for (int i=0; i<3; ++i) benchmark( + vec_shortstr, + vec_shortstrview, + mapNormal, + mapTrans, + unordmapNormal, + unordmapTrans); + + return 0; +} + +void benchmark( + const std::vector& vec_shortstr, + const std::vector& vec_shortstrview, + const std::map& mapNormal, + const std::map >& mapTrans, + const std::unordered_map& unordmapNormal, + const std::unordered_map& unordmapTrans) +{ + size_t grandtotal = 0; + size_t total = 0; + timer stopwatch; +/* + total = 0; + stopwatch.start("Normal Map with string"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = mapNormal.find(vec_shortstr[j]); + if(it!=mapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Normal Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = mapNormal.find(vec_shortstr[j].c_str()); + if (it != mapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); +*/ + total = 0; + stopwatch.start("Trans Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = mapTrans.find(vec_shortstr[j].c_str()); + if (it != mapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstrview.size(); ++j) + { + const auto& it = mapTrans.find(vec_shortstrview[j]); + if (it != mapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); +/* + total = 0; + stopwatch.start("Normal Unord Map with string"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = unordmapNormal.find(vec_shortstr[j]); + if (it != unordmapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Normal Unord Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = unordmapNormal.find(vec_shortstr[j].c_str()); + if (it != unordmapNormal.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); +*/ + total = 0; + stopwatch.start("Trans Unord Map with char*"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstr.size(); ++j) + { + const auto& it = unordmapTrans.find(vec_shortstr[j].c_str()); + if (it != unordmapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + stopwatch.stop(); + + total = 0; + stopwatch.start("Trans Unord Map with string_view"); + for (size_t i = 0; i < MAX_LOOP; ++i) + { + for (size_t j = 0; j < vec_shortstrview.size(); ++j) + { + const auto& it = unordmapTrans.find(vec_shortstrview[j]); + if (it != unordmapTrans.cend()) + total += it->second; + } + } + grandtotal += total; + + stopwatch.stop(); + + std::cout << "grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl; + +} diff --git a/docs/cstr_api.md b/docs/cstr_api.md index 4f7c689e..85a872fe 100644 --- a/docs/cstr_api.md +++ b/docs/cstr_api.md @@ -22,6 +22,7 @@ cstr cstr_from_n(const char* str, size_t n); // constru cstr cstr_with_capacity(size_t cap); cstr cstr_with_size(size_t len, char fill); // repeat fill len times cstr cstr_from_fmt(const char* fmt, ...); // printf() formatting +cstr cstr_from_replace_all_sv(csview sv, csview find, csview repl); cstr cstr_clone(cstr s); cstr* cstr_take(cstr* self, cstr s); // take the constructed or moved string diff --git a/docs/csview_api.md b/docs/csview_api.md index a472194f..5211e2f6 100644 --- a/docs/csview_api.md +++ b/docs/csview_api.md @@ -76,7 +76,7 @@ uint32_t utf8_decode(uint32_t *state, uint32_t *codep, const uint32_t byt #### Extended cstr methods ```c cstr cstr_from_sv(csview sv); // construct cstr from csview -csview cstr_to_sv(const cstr* self); // convert to csview from const cstr* +csview cstr_sv(const cstr* self); // convert to csview from const cstr* cstr cstr_from_replace_all_sv(csview sv, csview find, csview replace); csview cstr_substr(const cstr* s, intptr_t pos, size_t n); // negative pos count from end diff --git a/include/stc/ccommon.h b/include/stc/ccommon.h index 56dd501e..1c19bde7 100644 --- a/include/stc/ccommon.h +++ b/include/stc/ccommon.h @@ -112,27 +112,24 @@ typedef const char* crawstr; #define _c_ROTL(x, k) (x << (k) | x >> (8*sizeof(x) - (k))) -STC_INLINE uint64_t c_strhash(const char *s) { - int c; uint64_t h = *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) { - uint64_t u8, h = 1; + uint64_t u8, h = 1; size_t n = len >> 3; uint32_t u4; const uint8_t *x = (const uint8_t*) key; - for (size_t n = len >> 3; n--; ) - memcpy(&u8, x, 8), x += 8, h += u8*0xc6a4a7935bd1e99d; + while (n--) + memcpy(&u8, x, 8), x += 8, h += (h << 10) ^ (u8*0xc6a4a7935bd1e99d); switch (len &= 7) { - case 0: return h; - case 4: memcpy(&u4, x, 4); return h + u4*0xc6a4a7935bd1e99d; + 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_strhash(const char *s) + { return c_default_hash(s, strlen(s)); } + STC_INLINE char* c_strnstrn(const char *s, const char *needle, size_t slen, const size_t nlen) { if (!nlen) return (char *)s; if (nlen > slen) return NULL; diff --git a/include/stc/cstr.h b/include/stc/cstr.h index 9c6568f7..b669b6d5 100644 --- a/include/stc/cstr.h +++ b/include/stc/cstr.h @@ -87,12 +87,17 @@ STC_API void cstr_erase_n(cstr* self, size_t pos, size_t n); STC_API cstr cstr_from_fmt(const char* fmt, ...); STC_API int cstr_printf(cstr* self, const char* fmt, ...); STC_API void cstr_replace_all(cstr* self, const char* find, const char* repl); +STC_API cstr cstr_from_replace_all_sv(csview sv, csview find, csview repl); STC_INLINE cstr_rep_t cstr_rep(cstr* s) { return cstr_is_long(s) ? c_make(cstr_rep_t){s->lon.data, cstr_l_size(s), cstr_l_cap(s)} : c_make(cstr_rep_t){s->sml.data, cstr_s_size(s), cstr_s_cap}; } +STC_INLINE csview cstr_sv(const cstr* s) { + return cstr_is_long(s) ? c_make(csview){s->lon.data, cstr_l_size(s)} + : c_make(csview){s->sml.data, cstr_s_size(s)}; +} STC_INLINE cstr cstr_init(void) { return cstr_null; } @@ -132,8 +137,8 @@ STC_INLINE cstr cstr_move(cstr* self) { } STC_INLINE cstr cstr_clone(cstr s) { - cstr_rep_t r = cstr_rep(&s); - return cstr_from_n(r.data, r.size); + csview sv = cstr_sv(&s); + return cstr_from_n(sv.str, sv.size); } STC_INLINE void cstr_drop(cstr* self) { @@ -169,17 +174,19 @@ STC_INLINE size_t cstr_length(cstr s) STC_INLINE size_t cstr_capacity(cstr s) { return cstr_is_long(&s) ? cstr_l_cap(&s) : cstr_s_cap; } +STC_INLINE int cstr_cmp(const cstr* s1, const cstr* s2) + { return strcmp(cstr_str(s1), cstr_str(s2)); } + +STC_INLINE bool cstr_eq(const cstr* s1, const cstr* s2) { + csview x = cstr_sv(s1), y = cstr_sv(s2); + return x.size == y.size && !memcmp(x.str, y.str, x.size); +} + STC_INLINE bool cstr_equals(cstr s1, const char* str) { return strcmp(cstr_str(&s1), str) == 0; } STC_INLINE bool cstr_equals_s(cstr s1, cstr s2) - { return strcmp(cstr_str(&s1), cstr_str(&s2)) == 0; } - -STC_INLINE bool cstr_eq(const cstr* s1, const cstr* s2) - { return strcmp(cstr_str(s1), cstr_str(s2)) == 0; } - -STC_INLINE int cstr_cmp(const cstr* s1, const cstr* s2) - { return strcmp(cstr_str(s1), cstr_str(s2)); } + { return cstr_cmp(&s1, &s2) == 0; } STC_INLINE size_t cstr_find(cstr s, const char* needle) { const char *str = cstr_str(&s), *res = strstr(str, needle); @@ -205,8 +212,8 @@ STC_INLINE bool cstr_starts_with_s(cstr s, cstr sub) { return cstr_starts_with(s, cstr_str(&sub)); } STC_INLINE bool cstr_ends_with(cstr s, const char* sub) { - cstr_rep_t r = cstr_rep(&s); size_t n = strlen(sub); - return n <= r.size && memcmp(r.data + r.size - n, sub, n) == 0; + csview sv = cstr_sv(&s); size_t n = strlen(sub); + return n <= sv.size && memcmp(sv.str + sv.size - n, sub, n) == 0; } STC_INLINE bool cstr_ends_with_s(cstr s, cstr sub) @@ -216,16 +223,16 @@ STC_INLINE void cstr_assign(cstr* self, const char* str) { cstr_assign_n(self, str, strlen(str)); } STC_INLINE void cstr_copy(cstr* self, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_assign_n(self, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_assign_n(self, sv.str, sv.size); } STC_INLINE void cstr_append(cstr* self, const char* str) { cstr_append_n(self, str, strlen(str)); } STC_INLINE void cstr_append_s(cstr* self, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_append_n(self, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_append_n(self, sv.str, sv.size); } STC_INLINE void cstr_replace_n(cstr* self, size_t pos, size_t len, const char* str, size_t n) { @@ -237,8 +244,8 @@ STC_INLINE void cstr_replace(cstr* self, size_t pos, size_t len, const char* str { cstr_replace_n(self, pos, len, str, strlen(str)); } STC_INLINE void cstr_replace_s(cstr* self, size_t pos, size_t len, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_replace_n(self, pos, len, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_replace_n(self, pos, len, sv.str, sv.size); } STC_INLINE void cstr_insert_n(cstr* self, size_t pos, const char* str, size_t n) @@ -248,18 +255,17 @@ STC_INLINE void cstr_insert(cstr* self, size_t pos, const char* str) { cstr_replace_n(self, pos, 0, str, strlen(str)); } STC_INLINE void cstr_insert_s(cstr* self, size_t pos, cstr s) { - cstr_rep_t r = cstr_rep(&s); - cstr_replace_n(self, pos, 0, r.data, r.size); + csview sv = cstr_sv(&s); + cstr_replace_n(self, pos, 0, sv.str, sv.size); } 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)) -STC_INLINE uint64_t cstr_hash(const cstr *self, size_t dummylen) - { return c_default_hash(cstr_str(self), cstr_size(*self)); } +STC_INLINE uint64_t cstr_hash(const cstr *self, size_t dummylen) { + csview sv = cstr_sv(self); + return c_default_hash(sv.str, sv.size); +} /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(_i_implement) @@ -332,11 +338,11 @@ STC_DEF void cstr_resize(cstr* self, const size_t size, const char value) { } STC_DEF size_t cstr_find_n(cstr s, const char* needle, const size_t pos, const size_t nmax) { - cstr_rep_t r = cstr_rep(&s); + csview sv = cstr_sv(&s); const size_t nlen = (size_t) strlen(needle); - if (pos > r.size) return cstr_npos; - char* res = c_strnstrn(r.data + pos, needle, r.size, nmax < nlen ? nmax : nlen); - return res ? res - r.data : cstr_npos; + if (pos > sv.size) return cstr_npos; + char* res = c_strnstrn(sv.str + pos, needle, sv.size, nmax < nlen ? nmax : nlen); + return res ? res - sv.str : cstr_npos; } STC_DEF cstr* cstr_assign_n(cstr* self, const char* str, const size_t n) { @@ -401,9 +407,15 @@ cstr_from_replace_all(const char* str, const size_t str_len, STC_DEF void cstr_replace_all(cstr* self, const char* find, const char* repl) { - cstr_rep_t r = cstr_rep(self); - cstr_take(self, cstr_from_replace_all(r.data, r.size, find, strlen(find), - repl, strlen(repl))); + csview sv = cstr_sv(self); + cstr_take(self, cstr_from_replace_all(sv.str, sv.size, find, strlen(find), + repl, strlen(repl))); +} + +STC_DEF cstr +cstr_from_replace_all_sv(csview sv, csview find, csview repl) { + return cstr_from_replace_all(sv.str, sv.size, find.str, find.size, + repl.str, repl.size); } STC_DEF void cstr_erase_n(cstr* self, const size_t pos, size_t n) { diff --git a/include/stc/csview.h b/include/stc/csview.h index 59e853ca..be430a79 100644 --- a/include/stc/csview.h +++ b/include/stc/csview.h @@ -94,11 +94,6 @@ STC_INLINE csview csview_from_s(const cstr* self) STC_INLINE cstr cstr_from_sv(csview sv) { return cstr_from_n(sv.str, sv.size); } -/*STC_INLINE cstr cstr_from_replace_all_sv(csview sv, csview find, csview repl) - { return cstr_from_replace_all(sv.str, sv.size, find.str, find.size, - repl.str, repl.size); }*/ -STC_INLINE csview cstr_to_sv(const cstr* self) - { return c_make(csview){cstr_str(self), cstr_size(*self)}; } STC_INLINE csview cstr_substr(const cstr* self, intptr_t pos, size_t n) { return csview_substr(csview_from_s(self), pos, n); } STC_INLINE csview cstr_slice(const cstr* self, intptr_t p1, intptr_t p2) @@ -127,12 +122,12 @@ 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_eq(xp, yp) (!csview_cmp(xp, yp)) +STC_INLINE int csview_cmp(const csview* x, const csview* y) + { return strcmp(x->str, y->str); } + +STC_INLINE bool csview_eq(const csview* x, const csview* y) + { return x->size == y->size && !memcmp(x->str, y->str, x->size); } + STC_INLINE uint64_t csview_hash(const csview *self, size_t sz) { return c_default_hash(self->str, self->size); } diff --git a/include/stc/template.h b/include/stc/template.h index 48881edf..659f6a72 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -106,7 +106,8 @@ #define i_key_bind cstr #define i_keyraw csview #define i_keyfrom cstr_from_sv - #define i_keyto cstr_to_sv + #define i_keyto cstr_sv + #define i_eq csview_eq #ifndef i_tag #define i_tag ssv #endif @@ -197,7 +198,7 @@ #define i_val cstr #define i_valraw csview #define i_valfrom cstr_from_sv - #define i_valto cstr_to_sv + #define i_valto cstr_sv #define i_valdrop cstr_drop #elif defined i_val_arcbox #define i_val_bind i_val_arcbox -- cgit v1.2.3