From eee239dadee4d599c279a7e24972d72c1edcce4d Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 9 Sep 2020 10:09:18 +0200 Subject: More compliance with std:: containers. --- examples/advanced.c | 31 +++++++++++++++---------------- examples/benchmark.c | 10 +++++----- examples/demos.c | 2 +- examples/list.c | 6 ++++++ stc/cdefs.h | 2 +- stc/clist.h | 42 +++++++++++++++++++++--------------------- stc/cmap.h | 10 +++++----- stc/cvec.h | 28 ++++++++++++++++------------ 8 files changed, 70 insertions(+), 61 deletions(-) diff --git a/examples/advanced.c b/examples/advanced.c index 29ba55aa..aa82e38e 100644 --- a/examples/advanced.c +++ b/examples/advanced.c @@ -8,12 +8,25 @@ * calculate hash values for the individual members, and then somehow combine them into one * hash value for the entire object. * In order to use Viking as a map key, it is smart to define a plain-old-data "view" - * of the Viking struct first. + * of the Viking struct, to simplfy insert and lookup in the map. */ #include #include #include +// Viking data struct ----------------------- + +typedef struct Viking { + cstr_t name; + cstr_t country; +} Viking; + + +void viking_destroy(Viking* vk) { + cstr_destroy(&vk->name); + cstr_destroy(&vk->country); +} + // Viking view struct ----------------------- typedef struct VikingVw { @@ -30,19 +43,6 @@ int vikingvw_equals(const VikingVw* x, const VikingVw* y) { return strcmp(x->country, y->country) == 0; } -// Viking data struct ----------------------- - -typedef struct Viking { - cstr_t name; - cstr_t country; -} Viking; - - -void viking_destroy(Viking* vk) { - cstr_destroy(&vk->name); - cstr_destroy(&vk->country); -} - VikingVw viking_toVw(Viking* vk) { VikingVw vw = {vk->name.str, vk->country.str}; return vw; } @@ -50,7 +50,6 @@ Viking viking_fromVw(VikingVw vw) { Viking vk = {cstr_make(vw.name), cstr_make(vw.country)}; return vk; } - // Using the full declare_cmap() macro to define [Viking -> int] hash map type: declare_cmap(vk, Viking, int, c_default_destroy, vikingvw_equals, vikingvw_hash, viking_destroy, VikingVw, viking_toVw, viking_fromVw); @@ -72,7 +71,7 @@ int main() VikingVw einar = {"Einar", "Norway"}; cmap_vk_entry_t *e = cmap_vk_find(&vikings, einar); e->value += 5; // update - cmap_vk_emplace(&vikings, einar, 0).item->value += 5; // again + cmap_vk_insert(&vikings, einar, 0).item->value += 5; // again c_foreach (k, cmap_vk, vikings) { printf("%s of %s has %d hp\n", k.item->key.name.str, k.item->key.country.str, k.item->value); diff --git a/examples/benchmark.c b/examples/benchmark.c index 15d659ff..99e06fee 100644 --- a/examples/benchmark.c +++ b/examples/benchmark.c @@ -36,7 +36,7 @@ crand_rng64_t rng; #define CMAP_SETUP(tt, Key, Value) cmap_##tt map = cmap_ini \ ; cmap_##tt##_set_load_factors(&map, max_load_factor, 0.0) -#define CMAP_PUT(tt, key, val) cmap_##tt##_put(&map, key, val)->value +#define CMAP_PUT(tt, key, val) cmap_##tt##_put(&map, key, val).item->value #define CMAP_EMPLACE(tt, key, val) cmap_##tt##_emplace(&map, key, val) #define CMAP_ERASE(tt, key) cmap_##tt##_erase(&map, key) #define CMAP_FIND(tt, key) (cmap_##tt##_find(map, key) != NULL) @@ -130,7 +130,7 @@ crand_rng64_t rng; #define SMAP_DTOR(tt) UMAP_DTOR(tt) enum { - FAC = 5, + FAC = 3, N1 = 10000000 * FAC, N2 = 10000000 * FAC, N3 = 10000000 * FAC, @@ -218,13 +218,13 @@ int main(int argc, char* argv[]) seed = time(NULL); printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed); printf("\nUnordered maps: %d repeats of Insert random key + try to remove a random key:\n", N1); - //RUN_TEST(1) + RUN_TEST(1) printf("\nUnordered maps: Insert %d index keys, then remove them in same order:\n", N2); - //RUN_TEST(2) + RUN_TEST(2) printf("\nUnordered maps: Insert %d random keys, then remove them in same order:\n", N3); - //RUN_TEST(3) + RUN_TEST(3) printf("\nUnordered maps: Iterate %d random keys:\n", N4); RUN_TEST(4) diff --git a/examples/demos.c b/examples/demos.c index 21d9efaa..8ff72840 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -90,7 +90,7 @@ void listdemo1() c_foreach (i, clist_ix, nums) printf("spliced: %d\n", i.item->value); - *clist_ix_find(&nums, 100) *= 10; + clist_ix_find(&nums, 100).item->value *= 10; clist_ix_sort(&nums); // Sort the array clist_ix_remove(&nums, 105); clist_ix_pop_front(&nums); diff --git a/examples/list.c b/examples/list.c index 4eea5620..24dfc82f 100644 --- a/examples/list.c +++ b/examples/list.c @@ -31,8 +31,14 @@ int main() { clist_fx_insert_after(&list, clist_fx_before_begin(&list), 5); // same as push_front() clist_fx_push_back(&list, 500); clist_fx_push_front(&list, 1964); + clist_fx_iter_t it = clist_fx_before_begin(&list); + printf("Full: "); c_foreach (i, clist_fx, list) printf(" %g", i.item->value); + for (int i=0; i<4; ++i) clist_fx_next(&it); + printf("\nSubs: "); + c_foreach (i, clist_fx, it, clist_fx_end(&list)) + printf(" %g", i.item->value); puts(""); clist_fx_destroy(&list); } \ No newline at end of file diff --git a/stc/cdefs.h b/stc/cdefs.h index 0c8b5672..b5ae4a45 100644 --- a/stc/cdefs.h +++ b/stc/cdefs.h @@ -53,7 +53,7 @@ #define _c_OVERLOAD_SELECT(NAME, NUM) _c_CAT( NAME ## _, NUM) #define c_MACRO_OVERLOAD(NAME, ...) _c_OVERLOAD_SELECT(NAME, _c_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__) -/*#define FOO(...) c_MACRO_OVERLOAD(FOO, __VA_ARGS__) #define FOO_0() "0" #define FOO_1(x) "1" #define FOO_2(x,y) "2"*/ +/*#define FOO(...) c_MACRO_OVERLOAD(FOO, __VA_ARGS__) #define FOO_1(x) "1" #define FOO_2(x,y) "2"*/ #define c_new(T) ((T *) malloc(sizeof(T))) #define c_new_n(T, n) ((T *) malloc(sizeof(T) * (n))) diff --git a/stc/clist.h b/stc/clist.h index 9c5777f5..388c7e8e 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -70,16 +70,17 @@ #define declare_clist_types(X, Value) \ typedef struct clist_##X##_node { \ - struct clist_##X##_node *next; \ + struct clist_##X##_node* next; \ Value value; \ } clist_##X##_node_t; \ \ typedef struct clist_##X { \ - clist_##X##_node_t *last; \ + clist_##X##_node_t* last; \ } clist_##X; \ \ typedef struct { \ - clist_##X##_node_t **_last, *item; \ + clist_##X##_node_t* const* _last; \ + clist_##X##_node_t* item; \ int state; \ } clist_##X##_iter_t @@ -129,16 +130,16 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_pop_front(clist_##X* self); \ \ STC_INLINE clist_##X##_iter_t \ - clist_##X##_before_begin(clist_##X* self) { \ + clist_##X##_before_begin(const clist_##X* self) { \ clist_##X##_iter_t it = {&self->last, self->last, -1}; return it; \ } \ STC_INLINE clist_##X##_iter_t \ - clist_##X##_begin(clist_##X* self) { \ + clist_##X##_begin(const clist_##X* self) { \ clist_##X##_node_t* head = self->last ? self->last->next : NULL; \ clist_##X##_iter_t it = {&self->last, head}; return it; \ } \ STC_INLINE clist_##X##_iter_t \ - clist_##X##_end(clist_##X* self) { \ + clist_##X##_end(const clist_##X* self) { \ clist_##X##_iter_t it = {NULL}; return it; \ } \ STC_INLINE void \ @@ -172,9 +173,9 @@ STC_API size_t _clist_size(const clist_void* self); } \ \ STC_API clist_##X##_iter_t \ - clist_##X##_find_before(clist_##X* self, clist_##X##_iter_t prev, RawValue val); \ + clist_##X##_find_before(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t last, RawValue val); \ STC_API clist_##X##_iter_t \ - clist_##X##_find(clist_##X* self, RawValue val); \ + clist_##X##_find(const clist_##X* self, RawValue val); \ STC_API size_t \ clist_##X##_remove(clist_##X* self, RawValue val); \ STC_API void \ @@ -231,30 +232,29 @@ STC_API size_t _clist_size(const clist_void* self); } \ \ STC_API clist_##X##_iter_t \ - clist_##X##_find_before(clist_##X* self, clist_##X##_iter_t prev, RawValue val) { \ - clist_##X##_iter_t i = prev; \ - for (clist_##X##_next(&i); i.item; clist_##X##_next(&i)) { \ + clist_##X##_find_before(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t last, RawValue val) { \ + clist_##X##_iter_t i = first; \ + for (clist_##X##_next(&i); i.item != last.item; clist_##X##_next(&i)) { \ RawValue r = valueToRaw(&i.item->value); \ - if (valueCompareRaw(&r, &val) == 0) \ - return prev; \ - prev = i; \ + if (valueCompareRaw(&r, &val) == 0) return first; \ + first = i; \ } \ - prev.item = NULL; \ - return prev; \ + return clist_##X##_end(self); \ } \ \ STC_API clist_##X##_iter_t \ - clist_##X##_find(clist_##X* self, RawValue val) { \ - clist_##X##_iter_t it = clist_##X##_find_before(self, clist_##X##_before_begin(self), val); \ + clist_##X##_find(const clist_##X* self, RawValue val) { \ + clist_##X##_iter_t it = clist_##X##_find_before(self, clist_##X##_before_begin(self), clist_##X##_end(self), val); \ if (it.item) it.item = it.item->next; \ return it; \ } \ \ STC_API size_t \ clist_##X##_remove(clist_##X* self, RawValue val) { \ - clist_##X##_iter_t it; size_t n = 0; \ - while ((it = clist_##X##_find_before(self, clist_##X##_before_begin(self), val)).item) \ - it = clist_##X##_erase_after(self, it), ++n; \ + size_t n = 0; \ + clist_##X##_iter_t it = clist_##X##_before_begin(self), end = clist_##X##_end(self); \ + while ((it = clist_##X##_find_before(self, it, end, val)).item != end.item) \ + clist_##X##_erase_after(self, it), ++n; \ return n; \ } \ \ diff --git a/stc/cmap.h b/stc/cmap.h index 910a091b..21d5a394 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -235,17 +235,17 @@ ctype##_##X##_insert_or_assign(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, if (!res.inserted) valueDestroy(&res.item->value); \ res.item->value = valueFromRaw(rawValue); return res; \ } \ -STC_INLINE ctype##_##X##_entry_t* \ +STC_INLINE ctype##_##X##_result_t \ ctype##_##X##_putv(ctype##_##X* self, ctype##_##X##_rawkey_t rawKey, Value value) { \ ctype##_##X##_result_t res = ctype##_##X##_insert_key_(self, rawKey); \ if (!res.inserted) valueDestroy(&res.item->value); \ - res.item->value = value; return res.item; \ + res.item->value = value; return res; \ }) \ \ -STC_INLINE ctype##_##X##_entry_t* \ +STC_INLINE ctype##_##X##_result_t \ ctype##_##X##_put(ctype##_##X* self, CMAP_ARGS_##ctype(ctype##_##X##_rawkey_t rawKey, RawValue rawValue)) { \ - CMAP_ONLY_##ctype( return ctype##_##X##_insert_or_assign(self, rawKey, rawValue).item; ) \ - CSET_ONLY_##ctype( return ctype##_##X##_insert_key_(self, rawKey).item; ) \ + CMAP_ONLY_##ctype( return ctype##_##X##_insert_or_assign(self, rawKey, rawValue); ) \ + CSET_ONLY_##ctype( return ctype##_##X##_insert_key_(self, rawKey); ) \ } \ \ STC_API size_t \ diff --git a/stc/cvec.h b/stc/cvec.h index 3d35af04..f43857cf 100644 --- a/stc/cvec.h +++ b/stc/cvec.h @@ -51,6 +51,7 @@ typedef struct cvec_##X { \ typedef Value cvec_##X##_value_t; \ typedef RawValue cvec_##X##_rawvalue_t; \ typedef cvec_##X##_rawvalue_t cvec_##X##_input_t; \ +typedef struct { Value *item; } cvec_##X##_iter_t; \ \ STC_INLINE cvec_##X \ cvec_##X##_init(void) {cvec_##X v = cvec_ini; return v;} \ @@ -90,8 +91,10 @@ STC_API void \ cvec_##X##_sort(cvec_##X* self); \ STC_API void \ cvec_##X##_sort_with(cvec_##X* self, int(*cmp)(const Value*, const Value*)); \ -STC_API size_t \ +STC_API cvec_##X##_iter_t \ cvec_##X##_find(const cvec_##X* self, RawValue rawValue); \ +STC_API cvec_##X##_iter_t \ +cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last, RawValue rawValue); \ STC_API int \ cvec_##X##_value_compare(const Value* x, const Value* y); \ \ @@ -130,14 +133,12 @@ cvec_##X##_sort_with(cvec_##X* self, int(*cmp)(const Value*, const Value*)) { \ qsort(self->data, cvec_size(*self), sizeof(Value), (_cvec_cmp) cmp); \ } \ \ -typedef struct { Value *item; } cvec_##X##_iter_t; \ - \ STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_begin(cvec_##X* self) { \ +cvec_##X##_begin(const cvec_##X* self) { \ cvec_##X##_iter_t it = {self->data}; return it; \ } \ STC_INLINE cvec_##X##_iter_t \ -cvec_##X##_end(cvec_##X* self) { \ +cvec_##X##_end(const cvec_##X* self) { \ cvec_##X##_iter_t it = {self->data + cvec_size(*self)}; return it; \ } \ STC_INLINE void \ @@ -218,14 +219,17 @@ cvec_##X##_erase(cvec_##X* self, size_t pos, size_t size) { \ } \ } \ \ -STC_API size_t \ -cvec_##X##_find(const cvec_##X* self, RawValue rawValue) { \ - const Value *p = self->data, *end = p + cvec_size(*self); \ - for (; p != end; ++p) { \ - RawValue r = valueToRaw(p); \ - if (valueCompareRaw(&r, &rawValue) == 0) return p - self->data; \ +STC_API cvec_##X##_iter_t \ +cvec_##X##_find_in_range(const cvec_##X* self, cvec_##X##_iter_t first, cvec_##X##_iter_t last, RawValue rawValue) { \ + for (; first.item != last.item; cvec_##X##_next(&first)) { \ + RawValue r = valueToRaw(first.item); \ + if (valueCompareRaw(&r, &rawValue) == 0) return first; \ } \ - return SIZE_MAX; /*(size_t) (-1)*/ \ + return cvec_##X##_end(self); \ +} \ +STC_API cvec_##X##_iter_t \ +cvec_##X##_find(const cvec_##X* self, RawValue rawValue) { \ + return cvec_##X##_find_in_range(self, cvec_##X##_begin(self), cvec_##X##_end(self), rawValue); \ } \ \ STC_API int \ -- cgit v1.2.3