From 8178a02c4048cef03952a075f87da91b6ec2ee96 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 27 Apr 2022 13:23:10 +0200 Subject: Finally FIXED cloning/to/from scheme to work properly. When using i_key_bind/i_val_bind, a .._clone() function *must* always be defined. Functions .._from and .._toraw is only required when i_keyraw/i_valraw type is defined. --- benchmarks/misc/sso_bench.cpp | 4 ++-- docs/cmap_api.md | 47 +++++++++++++++++++++++++------------------ docs/cstack_api.md | 4 +++- docs/cvec_api.md | 3 ++- examples/complex.c | 1 - examples/lower_bound.c | 39 ++++++++++++++++++++++++++--------- examples/vikings.c | 32 +++++++++++++++-------------- include/stc/cstack.h | 8 ++++++++ include/stc/template.h | 20 +++++++++--------- 9 files changed, 98 insertions(+), 60 deletions(-) diff --git a/benchmarks/misc/sso_bench.cpp b/benchmarks/misc/sso_bench.cpp index c123fff6..e8ecd9ba 100644 --- a/benchmarks/misc/sso_bench.cpp +++ b/benchmarks/misc/sso_bench.cpp @@ -45,14 +45,14 @@ int benchmark(L& con, const int length, R addRandomString) { if (length == 0) for (int i = 0; i < BENCHMARK_SIZE; i++) - addRandomString(con, (crandom() & 31) + 1); + addRandomString(con, (crandom() & 63) + 1); else for (int i = 0; i < BENCHMARK_SIZE; i++) addRandomString(con, length); time_point t2 = std::chrono::high_resolution_clock::now(); const auto duration = std::chrono::duration_cast(t2 - t1).count(); - std::cerr << (length ? length : 16) << "\t" << duration; + std::cerr << (length ? length : 32) << "\t" << duration; return (int)duration; } diff --git a/docs/cmap_api.md b/docs/cmap_api.md index a730bee0..51607be2 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -278,12 +278,13 @@ static inline int Viking_cmp(const Viking* a, const Viking* b) { } static inline uint32_t Viking_hash(const Viking* a) { - return c_strhash(cstr_str(&a->name)) ^ (c_strhash(cstr_str(&a->country)) >> 15); + return cstr_hash(&a->name) ^ cstr_hash(&a->country); } static inline Viking Viking_clone(Viking v) { v.name = cstr_clone(v.name); v.country = cstr_clone(v.country); + return v; } static inline void Viking_drop(Viking* vk) { @@ -294,11 +295,13 @@ static inline void Viking_drop(Viking* vk) { #define i_type Vikings #define i_key_bind Viking #define i_val int -// i_key_bind auto-binds: -// #define i_cmp Viking_cmp -// #define i_hash Viking_hash -// #define i_keyfrom Viking_clone -// #define i_keydrop Viking_drop +/* + i_key_bind auto-binds: + #define i_cmp Viking_cmp + #define i_hash Viking_hash + #define i_keyfrom Viking_clone + #define i_keydrop Viking_drop +*/ #include int main() @@ -354,34 +357,38 @@ typedef struct RViking { const char* country; } RViking; -static inline uint64_t RViking_hash(const RViking* raw) { - uint64_t hash = c_strhash(raw->name) ^ (c_strhash(raw->country) >> 15); - return hash; -} - 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_clone(RViking v) { + v.name = cstr_clone(v.name), v.country = cstr_clone(v.country); + return vk; +} + static inline Viking Viking_from(RViking raw) { return (Viking){cstr_from(raw.name), cstr_from(raw.country)}; } -static inline RViking Viking_toraw(const Viking* vk) { - return (RViking){cstr_str(&vk->name), cstr_str(&vk->country)}; +static inline RViking Viking_toraw(const Viking* vp) { + return (RViking){cstr_str(&vp->name), cstr_str(&vp->country)}; } // With this in place, we define the Viking => int hash map type: #define i_type Vikings +#define i_keyraw RViking +#define i_hash(rp) (c_strhash(rp->name) ^ c_strhash(rp->country)) #define i_key_bind Viking #define i_val int -#define i_keyraw RViking -// i_key_bind macro will make these functions auto-bind: -// #define i_hash RViking_hash -// #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 +/* + i_key_bind macro auto-binds these functions: + #define i_hash RViking_hash + #define i_cmp RViking_cmp + #define i_keyclone Viking_clone + #define i_keyfrom Viking_from // because i_keyraw type is defined + #define i_keyto Viking_toraw // because i_keyraw type is defined + #define i_keydrop Viking_drop +*/ #include int main() diff --git a/docs/cstack_api.md b/docs/cstack_api.md index 8fc5fe8b..f5962344 100644 --- a/docs/cstack_api.md +++ b/docs/cstack_api.md @@ -30,6 +30,7 @@ cstack_X cstack_X_clone(cstack_X st); void cstack_X_clear(cstack_X* self); bool cstack_X_reserve(cstack_X* self, size_t n); void cstack_X_shrink_to_fit(cstack_X* self); +i_val* cstack_X_expand_uninitialized(cstack_X* self, size_t n); void cstack_X_copy(cstack_X* self, cstack_X other); void cstack_X_drop(cstack_X* self); // destructor @@ -39,6 +40,7 @@ bool cstack_X_empty(cstack_X st); i_val* cstack_X_top(const cstack_X* self); const i_val* cstack_X_at(const cstack_X* self, size_t idx); +i_val* cstack_X_at_mut(cstack_X* self, size_t idx); i_val* cstack_X_push(cstack_X* self, i_val value); i_val* cstack_X_emplace(cstack_X* self, i_valraw raw); @@ -90,4 +92,4 @@ int main() { Output: ``` top: 81 -``` \ No newline at end of file +``` diff --git a/docs/cvec_api.md b/docs/cvec_api.md index 1b06275e..d5d87b7b 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -37,7 +37,7 @@ void cvec_X_clear(cvec_X* self); void cvec_X_copy(cvec_X* self, cvec_X other); bool cvec_X_reserve(cvec_X* self, size_t cap); bool cvec_X_resize(cvec_X* self, size_t size, i_val null); -cvec_X_value* cvec_X_expand_uninitialized(cvec_X* self, size_t n); // return uninited data ptr +cvec_X_value* cvec_X_expand_uninitialized(cvec_X* self, size_t n); // return start of uninit void cvec_X_shrink_to_fit(cvec_X* self); void cvec_X_swap(cvec_X* a, cvec_X* b); void cvec_X_drop(cvec_X* self); // destructor @@ -48,6 +48,7 @@ size_t cvec_X_capacity(cvec_X vec); const cvec_X_value* cvec_X_at(const cvec_X* self, size_t idx); const cvec_X_value* cvec_X_get(const cvec_X* self, i_valraw raw); // return NULL if not found +cvec_X_value* cvec_X_at_mut(cvec_X* self, size_t idx); cvec_X_value* cvec_X_get_mut(cvec_X* self, i_valraw raw); // get mutable value cvec_X_iter cvec_X_find(const cvec_X* self, i_valraw raw); cvec_X_iter cvec_X_find_in(cvec_X_iter i1, cvec_X_iter i2, i_valraw raw); diff --git a/examples/complex.c b/examples/complex.c index ef7f711f..12b665c8 100644 --- a/examples/complex.c +++ b/examples/complex.c @@ -5,7 +5,6 @@ void check_drop(float* v) {printf("destroy %g\n", *v);} #define i_type FloatStack #define i_val float #define i_valdrop check_drop -#define i_valfrom c_default_from #include #define i_type StackList diff --git a/examples/lower_bound.c b/examples/lower_bound.c index 578209f8..1d9f5843 100644 --- a/examples/lower_bound.c +++ b/examples/lower_bound.c @@ -6,42 +6,63 @@ #define i_val int #include + +#define i_val char +#include int main() { - c_auto (csset_int, set) + // TEST SORTED VECTOR c_auto (cvec_int, vec) { int key, *res; - // TEST SORTED VECTOR c_apply(t, cvec_int_push(&vec, t), int, { 40, 600, 1, 7000, 2, 500, 30, }); cvec_int_sort(&vec); + key = 500; + res = cvec_int_lower_bound(&vec, key).ref; + if (res != cvec_int_end(&vec).ref) + printf("Sorted Vec %d: lower bound: %d\n", key, *res); // 600 + key = 550; res = cvec_int_lower_bound(&vec, key).ref; + if (res != cvec_int_end(&vec).ref) + printf("Sorted Vec %d: lower_bound: %d\n", key, *res); // 500 + key = 500; + res = cvec_int_binary_search(&vec, key).ref; if (res != cvec_int_end(&vec).ref) - printf("Vec key %d: lower bound: %d\n", key, *res); // 600 - else - printf("Vec element not found\n"); + printf("Sorted Vec %d: bin. search: %d\n", key, *res); // 500 + puts(""); + } + // TEST SORTED SET + c_auto (csset_int, set) + { + int key, *res; - // TEST SORTED SET c_apply(t, csset_int_push(&set, t), int, { 40, 600, 1, 7000, 2, 500, 30, }); + key = 500; + res = csset_int_lower_bound(&set, key).ref; + if (res != csset_int_end(&set).ref) + printf("Sorted Set %d: lower bound: %d\n", key, *res); // 600 + key = 550; res = csset_int_lower_bound(&set, key).ref; + if (res != csset_int_end(&set).ref) + printf("Sorted Set %d: lower bound: %d\n", key, *res); // 600 + key = 500; + res = csset_int_find(&set, key).ref; if (res != csset_int_end(&set).ref) - printf("Set key %d: lower bound: %d\n", key, *res); // 600 - else - printf("Set element not found\n"); + printf("Sorted Set %d: find : %d\n", key, *res); // 600 } return 0; } diff --git a/examples/vikings.c b/examples/vikings.c index 51ab92f8..bd4d379f 100644 --- a/examples/vikings.c +++ b/examples/vikings.c @@ -11,17 +11,13 @@ void Viking_drop(Viking* vk) { cstr_drop(&vk->country); } -// Define Viking raw struct with hash, equals, and convertion functions between Viking and RViking structs: +// Define Viking lookup struct with hash, cmp, and convertion functions between Viking and RViking structs: typedef struct RViking { const char* name; const char* country; } RViking; -uint64_t RViking_hash(const RViking* raw) { - uint64_t hash = c_strhash(raw->name) ^ (c_strhash(raw->country) >> 15); - return hash; -} 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); @@ -30,20 +26,26 @@ static inline int RViking_cmp(const RViking* rx, const RViking* ry) { static inline Viking Viking_from(RViking raw) { // note: parameter is by value return c_make(Viking){cstr_from(raw.name), cstr_from(raw.country)}; } -static inline RViking Viking_toraw(const Viking* vk) { - return c_make(RViking){cstr_str(&vk->name), cstr_str(&vk->country)}; +static inline Viking Viking_clone(Viking vk) { // note: parameter is by value + vk.name = cstr_clone(vk.name), vk.country = cstr_clone(vk.country); + return vk; +} +static inline RViking Viking_toraw(const Viking* vp) { + return c_make(RViking){cstr_str(&vp->name), cstr_str(&vp->country)}; } // With this in place, we define the Viking => int hash map type: #define i_type Vikings -#define i_key_bind Viking -#define i_keyraw RViking -#define i_val int -// i_key_bind auto-binds these functions: -// i_hash => Viking_hash -// i_cmp => Viking_cmp -// i_keyfrom => Viking_from // not _clone because i_keyraw is defined -// i_keyto => Viking_toraw +#define i_key_bind Viking // key type +#define i_val int // mapped type +#define i_keyraw RViking // lookup type +#define i_hash(rp) c_strhash(rp->name) ^ c_strhash(rp->country) +// i_key_bind auto-binds these functions (unless they are defined by i_...): +// i_cmp => RViking_cmp +// i_hash => RViking_hash +// i_keyclone => Viking_clone +// i_keyfrom => Viking_from // because i_keyraw is defined +// i_keyto => Viking_toraw // because i_keyraw is defined // i_keydrop => Viking_drop #include diff --git a/include/stc/cstack.h b/include/stc/cstack.h index f2412184..ee283cec 100644 --- a/include/stc/cstack.h +++ b/include/stc/cstack.h @@ -76,6 +76,14 @@ STC_INLINE bool _cx_memb(_reserve)(_cx_self* self, size_t n) { return t ? (self->data = t, self->capacity = n) : 0; } +STC_INLINE _cx_value* +_cx_memb(_expand_uninitialized)(_cx_self *self, size_t n) { + size_t len = self->size; + if (!_cx_memb(_reserve)(self, len + n)) return NULL; + self->size += n; + return self->data + len; +} + STC_INLINE void _cx_memb(_shrink_to_fit)(_cx_self* self) { _cx_memb(_reserve)(self, self->size); } diff --git a/include/stc/template.h b/include/stc/template.h index a523d07c..31360946 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -122,11 +122,10 @@ #ifdef i_key_bind #define i_key i_key_bind - #ifndef i_keyraw - #ifndef i_keyfrom - #define i_keyfrom c_paste(i_key, _clone) - #endif - #else + #ifndef i_keyclone + #define i_keyclone c_paste(i_key, _clone) + #endif + #ifdef i_keyraw #ifndef i_keyfrom #define i_keyfrom c_paste(i_key, _from) #endif @@ -156,7 +155,7 @@ #ifndef i_tag #define i_tag i_key #endif -#if (!defined i_keyfrom && defined i_keydrop) || c_option(c_no_clone) +#if c_option(c_no_clone) #define _i_no_clone #endif #ifndef i_keyfrom @@ -210,11 +209,10 @@ #ifdef i_val_bind #define i_val i_val_bind - #ifndef i_valraw - #ifndef i_valfrom - #define i_valfrom c_paste(i_val, _clone) - #endif - #else + #ifndef i_valclone + #define i_valclone c_paste(i_val, _clone) + #endif + #ifdef i_valraw #ifndef i_valfrom #define i_valfrom c_paste(i_val, _from) #endif -- cgit v1.2.3