From d1048f2545ac40b8d9b07fb427d418290b7ae829 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 16 Sep 2020 12:27:12 +0200 Subject: Changed iterator API in cset and clist. From i.get->value to *i.get --- examples/demos.c | 10 ++++----- examples/inits.c | 2 +- examples/list.c | 14 ++++++------ examples/words.c | 2 +- stc/cdefs.h | 2 ++ stc/clist.h | 66 +++++++++++++++++++++++++++++--------------------------- stc/cmap.h | 29 ++++++++++++------------- 7 files changed, 64 insertions(+), 61 deletions(-) diff --git a/examples/demos.c b/examples/demos.c index 634e4dde..f39b439f 100644 --- a/examples/demos.c +++ b/examples/demos.c @@ -84,19 +84,19 @@ void listdemo1() for (int i = 100; i < 110; ++i) clist_ix_push_back(&nums2, i); c_foreach (i, clist_ix, nums) - printf("value: %d\n", i.get->value); + printf("value: %d\n", *i.get); /* merge/append nums2 to nums */ clist_ix_splice_front(&nums, &nums2); c_foreach (i, clist_ix, nums) - printf("spliced: %d\n", i.get->value); + printf("spliced: %d\n", *i.get); - clist_ix_find(&nums, 100).get->value *= 10; + *clist_ix_find(&nums, 100).get *= 10; clist_ix_sort(&nums); // Sort the array clist_ix_remove(&nums, 105); clist_ix_pop_front(&nums); clist_ix_push_front(&nums, -99); c_foreach (i, clist_ix, nums) - printf("sorted: %d\n", i.get->value); + printf("sorted: %d\n", *i.get); clist_ix_destroy(&nums); } @@ -110,7 +110,7 @@ void setdemo1() cset_i_insert(&nums, 11); c_foreach (i, cset_i, nums) - printf("set: %d\n", i.get->value); + printf("set: %d\n", *i.get); cset_i_destroy(&nums); } diff --git a/examples/inits.c b/examples/inits.c index 4d07cb02..7cad8f4e 100644 --- a/examples/inits.c +++ b/examples/inits.c @@ -109,7 +109,7 @@ int main(void) { clist_ip_sort(&pairs2); c_foreach (i, clist_ip, pairs2) - printf("(%d %d) ", i.get->value.x, i.get->value.y); + printf("(%d %d) ", i.get->x, i.get->y); puts(""); clist_ip_destroy(&pairs2); } \ No newline at end of file diff --git a/examples/list.c b/examples/list.c index 55e6c419..4a131fac 100644 --- a/examples/list.c +++ b/examples/list.c @@ -9,24 +9,24 @@ int main() { clist_fx list = clist_ini; crand_rng64_t eng = crand_rng64_init(time(NULL)); crand_uniform_f64_t dist = crand_uniform_f64_init(0.0f, n); - + for (int i = 0; i < 100000; ++i) clist_fx_push_back(&list, crand_uniform_f64(&eng, &dist)); k = 0; c_foreach (i, clist_fx, list) - if (++k <= 10) printf("%8d: %10f\n", k, i.get->value); else break; + if (++k <= 10) printf("%8d: %10f\n", k, *i.get); else break; clist_fx_sort(&list); // mergesort O(n*log n) puts("sorted"); k = 0; c_foreach (i, clist_fx, list) - if (++k <= 10) printf("%8d: %10f\n", k, i.get->value); else break; + if (++k <= 10) printf("%8d: %10f\n", k, *i.get); else break; puts(""); clist_fx_clear(&list); c_push_items(&list, clist_fx, {10, 20, 30, 40, 30, 50}); - c_foreach (i, clist_fx, list) printf(" %g", i.get->value); + c_foreach (i, clist_fx, list) printf(" %g", *i.get); puts(""); - + int removed = clist_fx_remove(&list, 30); clist_fx_insert_after(&list, clist_fx_before_begin(&list), 5); // same as push_front() clist_fx_push_back(&list, 500); @@ -34,11 +34,11 @@ int main() { clist_fx_iter_t it = clist_fx_before_begin(&list); printf("Full: "); c_foreach (i, clist_fx, list) - printf(" %g", i.get->value); + printf(" %g", *i.get); 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.get->value); + printf(" %g", *i.get); puts(""); clist_fx_destroy(&list); } \ No newline at end of file diff --git a/examples/words.c b/examples/words.c index 70a4878f..0f799ea2 100644 --- a/examples/words.c +++ b/examples/words.c @@ -18,7 +18,7 @@ int main1() }); clist_str_push_back(&lwords, cstr_from("%f", 123897.0 / 23.0)); c_foreach (w, clist_str, lwords) - printf("%s\n", w.get->value.str); + printf("%s\n", w.get->str); puts(""); cvec_str words = cvec_ini; diff --git a/stc/cdefs.h b/stc/cdefs.h index ef6fd62f..6ec64bc7 100644 --- a/stc/cdefs.h +++ b/stc/cdefs.h @@ -64,6 +64,8 @@ #define c_new(T) ((T *) malloc(sizeof(T))) #define c_new_n(T, n) ((T *) malloc(sizeof(T) * (n))) #define c_static_assert(cond, msg) typedef char static_assert_##msg[(cond) ? 1 : -1] +#define c_container_of(ptr, type, member) \ + ((type *)((char *)(ptr) - offsetof(type, member))) #define c_max_alloca (512) #define c_swap(T, x, y) do { T __t = x; x = y; y = __t; } while (0) diff --git a/stc/clist.h b/stc/clist.h index 1fd88310..4eac50f1 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -55,7 +55,6 @@ clist_ix_destroy(&list); } */ - #define typedef_clist(...) c_MACRO_OVERLOAD(typedef_clist, __VA_ARGS__) #define typedef_clist_2(X, Value) \ @@ -82,7 +81,7 @@ \ typedef struct { \ clist_##X##_node_t* const* _last; \ - clist_##X##_node_t* get; \ + clist_##X##_value_t* get; \ int _state; \ } clist_##X##_iter_t @@ -97,8 +96,10 @@ __pos = ctype##_emplace_after(__self, __pos, __arr[__i]); \ } while (0) + typedef_clist_types(void, int); STC_API size_t _clist_size(const clist_void* self); +#define _clist_node(X, vp) c_container_of(vp, clist_##X##_node_t, value) #define typedef_clist_7(X, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ \ @@ -139,16 +140,18 @@ STC_API size_t _clist_size(const clist_void* self); \ STC_INLINE clist_##X##_iter_t \ clist_##X##_before_begin(const clist_##X* self) { \ - clist_##X##_iter_t it = {&self->last, self->last, -1}; return it; \ + clist_##X##_value_t *before = self->last ? &self->last->value : NULL; \ + clist_##X##_iter_t it = {&self->last, before, -1}; return it; \ } \ STC_INLINE clist_##X##_iter_t \ clist_##X##_begin(const clist_##X* self) { \ - clist_##X##_node_t* head = self->last ? self->last->next : NULL; \ + clist_##X##_value_t* head = self->last ? &self->last->next->value : NULL; \ clist_##X##_iter_t it = {&self->last, head, 0}; return it; \ } \ STC_INLINE clist_##X##_iter_t \ clist_##X##_last(const clist_##X* self) { \ - clist_##X##_iter_t it = {&self->last, self->last, 0}; return it; \ + clist_##X##_value_t *last = self->last ? &self->last->value : NULL; \ + clist_##X##_iter_t it = {&self->last, last, 0}; return it; \ } \ STC_INLINE clist_##X##_iter_t \ clist_##X##_end(const clist_##X* self) { \ @@ -156,11 +159,12 @@ STC_API size_t _clist_size(const clist_void* self); } \ STC_INLINE void \ clist_##X##_next(clist_##X##_iter_t* it) { \ - it->get = ((it->_state += it->get == *it->_last) == 1) ? NULL : it->get->next; \ + clist_##X##_node_t* node = _clist_node(X, it->get); \ + it->get = ((it->_state += node == *it->_last) == 1) ? NULL : &node->next->value; \ } \ STC_INLINE clist_##X##_value_t* \ - clist_##X##_itval(clist_##X##_iter_t it) {return &it.get->value;} \ -\ + clist_##X##_itval(clist_##X##_iter_t it) {return it.get;} \ + \ STC_API clist_##X##_iter_t \ clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t pos, Value value); \ STC_INLINE clist_##X##_iter_t \ @@ -175,10 +179,8 @@ STC_API size_t _clist_size(const clist_void* self); return pos; \ } \ \ - STC_INLINE void \ - clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other) { \ - _clist_splice_after((clist_void *) self, *(clist_void_iter_t *) &pos, (clist_void *) other); \ - } \ + STC_API void \ + clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other); \ STC_INLINE void \ clist_##X##_splice_front(clist_##X* self, clist_##X* other) { \ clist_##X##_splice_after(self, clist_##X##_before_begin(self), other); \ @@ -237,13 +239,14 @@ STC_API size_t _clist_size(const clist_void* self); \ STC_API clist_##X##_iter_t \ clist_##X##_insert_after(clist_##X* self, clist_##X##_iter_t pos, Value value) { \ - _c_clist_insert_after(self, X, pos.get, value); \ - if (pos.get == self->last && pos._state == 0) self->last = entry; \ - pos.get = entry; return pos; \ + clist_##X##_node_t* node = pos.get ? _clist_node(X, pos.get) : NULL; \ + _c_clist_insert_after(self, X, node, value); \ + if (node == self->last && pos._state == 0) self->last = entry; \ + pos.get = &entry->value; return pos; \ } \ STC_API clist_##X##_iter_t \ clist_##X##_erase_after(clist_##X* self, clist_##X##_iter_t pos) { \ - _c_clist_erase_after(self, X, pos.get, valueDestroy); \ + _c_clist_erase_after(self, X, _clist_node(X, pos.get), valueDestroy); \ clist_##X##_next(&pos); return pos; \ } \ \ @@ -251,7 +254,7 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_find_before(const clist_##X* self, clist_##X##_iter_t first, clist_##X##_iter_t finish, RawValue val) { \ clist_##X##_iter_t i = first; \ for (clist_##X##_next(&i); i.get != finish.get; clist_##X##_next(&i)) { \ - RawValue r = valueToRaw(&i.get->value); \ + RawValue r = valueToRaw(i.get); \ if (valueCompareRaw(&r, &val) == 0) return first; \ first = i; \ } \ @@ -273,6 +276,19 @@ STC_API size_t _clist_size(const clist_void* self); clist_##X##_erase_after(self, it), ++n; \ return n; \ } \ +\ + STC_API void \ + clist_##X##_splice_after(clist_##X* self, clist_##X##_iter_t pos, clist_##X* other) { \ + if (!pos.get) \ + self->last = other->last; \ + else if (other->last) { \ + clist_##X##_node_t *node = _clist_node(X, pos.get), *next = node->next; \ + node->next = other->last->next; \ + other->last->next = next; \ + if (node == self->last && pos._state == 0) self->last = other->last; \ + } \ + other->last = NULL; \ + } \ \ static inline int \ clist_##X##_sort_compare(const void* x, const void* y) { \ @@ -290,7 +306,7 @@ STC_API size_t _clist_size(const clist_void* self); #define _c_clist_insert_after(self, X, node, val) \ clist_##X##_node_t *entry = c_new (clist_##X##_node_t), \ - *next = self->last ? node->next : entry; \ + *next = self->last ? node->next : entry; \ entry->value = val; \ entry->next = next; \ if (node) node->next = entry @@ -304,20 +320,6 @@ STC_API size_t _clist_size(const clist_void* self); valueDestroy(&del->value); \ free(del) - -STC_API void -_clist_splice_after(clist_void* self, clist_void_iter_t pos, clist_void* other) { - if (!pos.get) - self->last = other->last; - else if (other->last) { - clist_void_node_t *next = pos.get->next; - pos.get->next = other->last->next; - other->last->next = next; - if (pos.get == self->last && pos._state == 0) self->last = other->last; - } - other->last = NULL; -} - STC_API size_t _clist_size(const clist_void* self) { const clist_void_node_t *i = self->last; diff --git a/stc/cmap.h b/stc/cmap.h index 3192be93..10848cb6 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -148,8 +148,8 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; #define CSET_ONLY_cmap(...) #define CMAP_ONLY_cset(...) #define CMAP_ONLY_cmap(...) __VA_ARGS__ -#define KEY_NAME_cset value -#define KEY_NAME_cmap first +#define KEY_REF_cset(e) (*(e)) +#define KEY_REF_cmap(e) (e)->first /* CHASH full: use 'void' for Mapped if ctype is cset */ #define _c_typedef_CHASH(X, ctype, Key, Mapped, valueDestroy, keyEqualsRaw, keyHashRaw, \ @@ -159,20 +159,19 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; typedef RawKey ctype##_##X##_rawkey_t; \ typedef RawVal ctype##_##X##_rawval_t; \ \ - typedef struct { \ - ctype##_##X##_key_t KEY_NAME_##ctype; \ - CMAP_ONLY_##ctype(ctype##_##X##_mapped_t second;) \ - } ctype##_##X##_value_t, ctype##_##X##_entry_t; \ + typedef CSET_ONLY_##ctype( ctype##_##X##_key_t ) \ + CMAP_ONLY_##ctype( struct {ctype##_##X##_key_t first; \ + ctype##_##X##_mapped_t second;} ) \ + ctype##_##X##_value_t, ctype##_##X##_entry_t; \ \ STC_INLINE void \ ctype##_##X##_entry_destroy(ctype##_##X##_value_t* e) { \ - keyDestroy(&e->KEY_NAME_##ctype); \ + keyDestroy(&KEY_REF_##ctype(e)); \ CMAP_ONLY_##ctype(valueDestroy(&e->second);) \ } \ - typedef \ - CMAP_ONLY_##ctype( struct {ctype##_##X##_rawkey_t first; \ - ctype##_##X##_rawval_t second;}) \ - CSET_ONLY_##ctype( ctype##_##X##_rawkey_t ) \ + typedef CSET_ONLY_##ctype( ctype##_##X##_rawkey_t ) \ + CMAP_ONLY_##ctype( struct {ctype##_##X##_rawkey_t first; \ + ctype##_##X##_rawval_t second;} ) \ ctype##_##X##_input_t; \ \ typedef struct { \ @@ -346,7 +345,7 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; uint8_t* hashx = self->_hashx; \ while ((sx = hashx[b.idx])) { \ if (sx == b.hx) { \ - ctype##_##X##_rawkey_t r = keyToRaw(&self->table[b.idx].KEY_NAME_##ctype); \ + ctype##_##X##_rawkey_t r = keyToRaw(&KEY_REF_##ctype(self->table + b.idx)); \ if (keyEqualsRaw(&r, rawKeyPtr)) break; \ } \ if (++b.idx == cap) b.idx = 0; \ @@ -376,7 +375,7 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; ctype##_bucket_t b = ctype##_##X##_bucket(self, &rawKey); \ ctype##_##X##_result_t res = {&self->table[b.idx], !self->_hashx[b.idx]}; \ if (res.second) { \ - res.first->KEY_NAME_##ctype = keyFromRaw(rawKey); \ + KEY_REF_##ctype(res.first) = keyFromRaw(rawKey); \ self->_hashx[b.idx] = (uint8_t) b.hx; \ ++self->size; \ } \ @@ -400,7 +399,7 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; uint8_t* hashx = self->_hashx; \ for (size_t i = 0; i < oldcap; ++i, ++e) \ if (tmp._hashx[i]) { \ - RawKey r = keyToRaw(&e->KEY_NAME_##ctype); \ + RawKey r = keyToRaw(&KEY_REF_##ctype(e)); \ ctype##_bucket_t b = ctype##_##X##_bucket(self, &r); \ slot[b.idx] = *e, \ hashx[b.idx] = (uint8_t) b.hx; \ @@ -419,7 +418,7 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; if (++j == cap) j = 0; /* ++j; j %= cap; is slow */ \ if (! hashx[j]) \ break; \ - RawKey r = keyToRaw(&slot[j].KEY_NAME_##ctype); \ + RawKey r = keyToRaw(&KEY_REF_##ctype(slot + j)); \ k = chash_reduce(keyHashRaw(&r, sizeof(RawKey)), cap); \ if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ -- cgit v1.2.3