From 41795cba77b5559e702bc5b749fb2d8dc5c6d8bf Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 3 Nov 2022 17:24:10 +0100 Subject: Changed internal representation of csmap. --- examples/sorted_map.c | 64 ++++++++++++++++++++++++++ examples/unordered_map.c | 64 -------------------------- include/stc/csmap.h | 114 +++++++++++++++++++++-------------------------- include/stc/forward.h | 1 + 4 files changed, 115 insertions(+), 128 deletions(-) create mode 100644 examples/sorted_map.c delete mode 100644 examples/unordered_map.c diff --git a/examples/sorted_map.c b/examples/sorted_map.c new file mode 100644 index 00000000..c4a05c76 --- /dev/null +++ b/examples/sorted_map.c @@ -0,0 +1,64 @@ +// https://iq.opengenus.org/containers-cpp-stl/ + +#define i_key int +#define i_val int +#include +#include + +int main() +{ + + // empty map containers + c_auto (csmap_int, gquiz1, gquiz2) + { + // insert elements in random order + csmap_int_insert(&gquiz1, 2, 30); + csmap_int_insert(&gquiz1, 4, 20); + csmap_int_insert(&gquiz1, 7, 10); + csmap_int_insert(&gquiz1, 5, 50); + csmap_int_insert(&gquiz1, 3, 60); + csmap_int_insert(&gquiz1, 1, 40); + csmap_int_insert(&gquiz1, 6, 50); + + // printing map gquiz1 + printf("\nThe map gquiz1 is :\n\tKEY\tELEMENT\n"); + c_foreach (itr, csmap_int, gquiz1) + printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); + printf("\n"); + + // assigning the elements from gquiz1 to gquiz2 + c_foreach (i, csmap_int, gquiz1) + csmap_int_insert(&gquiz2, i.ref->first, i.ref->second); + + // print all elements of the map gquiz2 + printf("\nThe map gquiz2 is :\n\tKEY\tELEMENT\n"); + c_foreach (itr, csmap_int, gquiz2) + printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); + printf("\n"); + + // remove all elements up to element with key=3 in gquiz2 + printf("\ngquiz2 after removal of elements less than key=3 :\n"); + printf("\tKEY\tELEMENT\n"); + csmap_int_erase_range(&gquiz2, csmap_int_begin(&gquiz2), + csmap_int_find(&gquiz2, 3)); + c_foreach (itr, csmap_int, gquiz2) + printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); + printf("\n"); + + // remove all elements with key = 4 + int num = csmap_int_erase(&gquiz2, 4); + printf("\ngquiz2.erase(4) : %d removed\n", num); + printf("\tKEY\tELEMENT\n"); + c_foreach (itr, csmap_int, gquiz2) + printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); + printf("\n"); + + // lower bound and upper bound for map gquiz1 key = 5 + printf("gquiz1.lower_bound(5) : "); + printf("\tKEY = %d\t", csmap_int_lower_bound(&gquiz1, 5).ref->first); + printf("\tELEMENT = %d\n", csmap_int_lower_bound(&gquiz1, 5).ref->second); + printf("gquiz1.upper_bound(5) : "); + printf("\tKEY = %d\t", csmap_int_lower_bound(&gquiz1, 5+1).ref->first); + printf("\tELEMENT = %d\n", csmap_int_lower_bound(&gquiz1, 5+1).ref->second); + } +} diff --git a/examples/unordered_map.c b/examples/unordered_map.c deleted file mode 100644 index c4a05c76..00000000 --- a/examples/unordered_map.c +++ /dev/null @@ -1,64 +0,0 @@ -// https://iq.opengenus.org/containers-cpp-stl/ - -#define i_key int -#define i_val int -#include -#include - -int main() -{ - - // empty map containers - c_auto (csmap_int, gquiz1, gquiz2) - { - // insert elements in random order - csmap_int_insert(&gquiz1, 2, 30); - csmap_int_insert(&gquiz1, 4, 20); - csmap_int_insert(&gquiz1, 7, 10); - csmap_int_insert(&gquiz1, 5, 50); - csmap_int_insert(&gquiz1, 3, 60); - csmap_int_insert(&gquiz1, 1, 40); - csmap_int_insert(&gquiz1, 6, 50); - - // printing map gquiz1 - printf("\nThe map gquiz1 is :\n\tKEY\tELEMENT\n"); - c_foreach (itr, csmap_int, gquiz1) - printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); - printf("\n"); - - // assigning the elements from gquiz1 to gquiz2 - c_foreach (i, csmap_int, gquiz1) - csmap_int_insert(&gquiz2, i.ref->first, i.ref->second); - - // print all elements of the map gquiz2 - printf("\nThe map gquiz2 is :\n\tKEY\tELEMENT\n"); - c_foreach (itr, csmap_int, gquiz2) - printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); - printf("\n"); - - // remove all elements up to element with key=3 in gquiz2 - printf("\ngquiz2 after removal of elements less than key=3 :\n"); - printf("\tKEY\tELEMENT\n"); - csmap_int_erase_range(&gquiz2, csmap_int_begin(&gquiz2), - csmap_int_find(&gquiz2, 3)); - c_foreach (itr, csmap_int, gquiz2) - printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); - printf("\n"); - - // remove all elements with key = 4 - int num = csmap_int_erase(&gquiz2, 4); - printf("\ngquiz2.erase(4) : %d removed\n", num); - printf("\tKEY\tELEMENT\n"); - c_foreach (itr, csmap_int, gquiz2) - printf("\t%d\t%d\n", itr.ref->first, itr.ref->second); - printf("\n"); - - // lower bound and upper bound for map gquiz1 key = 5 - printf("gquiz1.lower_bound(5) : "); - printf("\tKEY = %d\t", csmap_int_lower_bound(&gquiz1, 5).ref->first); - printf("\tELEMENT = %d\n", csmap_int_lower_bound(&gquiz1, 5).ref->second); - printf("gquiz1.upper_bound(5) : "); - printf("\tKEY = %d\t", csmap_int_lower_bound(&gquiz1, 5+1).ref->first); - printf("\tELEMENT = %d\n", csmap_int_lower_bound(&gquiz1, 5+1).ref->second); - } -} diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 5afa6c1b..35b89eea 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -58,8 +58,6 @@ int main(void) { #include #include -struct csmap_rep { size_t root, disp, head, size, cap; unsigned nodes[1]; }; -#define _csmap_rep(self) c_unchecked_container_of((self)->nodes, struct csmap_rep, nodes) #endif // CSMAP_H_INCLUDED #ifndef _i_prefix @@ -117,9 +115,9 @@ STC_API _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it); STC_API _cx_iter _cx_memb(_erase_range)(_cx_self* self, _cx_iter it1, _cx_iter it2); STC_API void _cx_memb(_next)(_cx_iter* it); -STC_INLINE bool _cx_memb(_empty)(const _cx_self* cx) { return _csmap_rep(cx)->size == 0; } -STC_INLINE size_t _cx_memb(_size)(const _cx_self* cx) { return _csmap_rep(cx)->size; } -STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* cx) { return _csmap_rep(cx)->cap; } +STC_INLINE bool _cx_memb(_empty)(const _cx_self* cx) { return cx->size == 0; } +STC_INLINE size_t _cx_memb(_size)(const _cx_self* cx) { return cx->size; } +STC_INLINE size_t _cx_memb(_capacity)(const _cx_self* cx) { return cx->cap; } STC_INLINE void _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); } STC_INLINE _cx_iter _cx_memb(_find)(const _cx_self* self, _cx_rawkey rkey) { _cx_iter it; _cx_memb(_find_it)(self, rkey, &it); return it; } @@ -203,7 +201,7 @@ _cx_memb(_begin)(const _cx_self* self) { _cx_iter it; it.ref = NULL; it._d = self->nodes, it._top = 0; - it._tn = (i_size) _csmap_rep(self)->root; + it._tn = self->root; if (it._tn) _cx_memb(_next)(&it); return it; @@ -226,38 +224,28 @@ _cx_memb(_advance)(_cx_iter it, size_t n) { /* -------------------------- IMPLEMENTATION ------------------------- */ #if defined(i_implement) -#ifndef CSMAP_H_INCLUDED -static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0}; -#endif - STC_DEF _cx_self _cx_memb(_init)(void) { - _cx_self tree = {(_cx_node *)_csmap_sentinel.nodes}; + _cx_self tree = {0}; return tree; } STC_DEF bool _cx_memb(_reserve)(_cx_self* self, const size_t cap) { - struct csmap_rep* rep = _csmap_rep(self), *oldrep; - if (cap >= rep->size) { - // second test is bogus, but supresses gcc warning: - oldrep = rep->cap && rep != &_csmap_sentinel ? rep : NULL; - rep = (struct csmap_rep*) c_realloc(oldrep, offsetof(struct csmap_rep, nodes) + - (cap + 1)*sizeof(_cx_node)); - if (!rep) - return false; - if (oldrep == NULL) - memset(rep, 0, offsetof(struct csmap_rep, nodes) + sizeof(_cx_node)); - rep->cap = cap; - self->nodes = (_cx_node *) rep->nodes; - } + if (cap <= self->cap) + return false; + _cx_node* nodes = (_cx_node*)c_realloc(self->nodes, (cap + 1)*sizeof(_cx_node)); + if (!nodes) + return false; + self->cap = cap; + self->nodes = nodes; return true; } STC_DEF _cx_value* _cx_memb(_front)(const _cx_self* self) { _cx_node *d = self->nodes; - i_size tn = (i_size) _csmap_rep(self)->root; + i_size tn = self->root; while (d[tn].link[0]) tn = d[tn].link[0]; return &d[tn].value; @@ -266,7 +254,7 @@ _cx_memb(_front)(const _cx_self* self) { STC_DEF _cx_value* _cx_memb(_back)(const _cx_self* self) { _cx_node *d = self->nodes; - i_size tn = (i_size) _csmap_rep(self)->root; + i_size tn = self->root; while (d[tn].link[1]) tn = d[tn].link[1]; return &d[tn].value; @@ -274,15 +262,15 @@ _cx_memb(_back)(const _cx_self* self) { static i_size _cx_memb(_new_node_)(_cx_self* self, int level) { - i_size tn; struct csmap_rep *rep = _csmap_rep(self); - if (rep->disp) { - tn = (i_size)rep->disp; - rep->disp = self->nodes[tn].link[1]; + i_size tn; + if (self->disp) { + tn = self->disp; + self->disp = self->nodes[tn].link[1]; } else { - if (rep->head == rep->cap) - if (!_cx_memb(_reserve)(self, rep->head*3/2 + 4)) + if (self->head == self->cap) + if (!_cx_memb(_reserve)(self, self->head*3/2 + 4)) return 0; - tn = ++_csmap_rep(self)->head; /* start with 1, 0 is nullnode. */ + tn = ++self->head; /* start with 1, 0 is nullnode. */ } _cx_node* dn = &self->nodes[tn]; dn->link[0] = dn->link[1] = 0; dn->level = level; @@ -343,7 +331,7 @@ _cx_memb(_push)(_cx_self* self, _cx_value _val) { STC_DEF _cx_value* _cx_memb(_find_it)(const _cx_self* self, _cx_rawkey rkey, _cx_iter* out) { - i_size tn = _csmap_rep(self)->root; + i_size tn = self->root; _cx_node *d = out->_d = self->nodes; out->_top = 0; while (tn) { @@ -442,20 +430,21 @@ _cx_memb(_insert_entry_i_)(_cx_self* self, i_size tn, const _cx_rawkey* rkey, _c static _cx_result _cx_memb(_insert_entry_)(_cx_self* self, _cx_rawkey rkey) { _cx_result res = {NULL}; - i_size tn = _cx_memb(_insert_entry_i_)(self, (i_size) _csmap_rep(self)->root, &rkey, &res); - _csmap_rep(self)->root = tn; - _csmap_rep(self)->size += res.inserted; + i_size tn = _cx_memb(_insert_entry_i_)(self, self->root, &rkey, &res); + self->root = tn; + self->size += res.inserted; return res; } static i_size -_cx_memb(_erase_r_)(_cx_node *d, i_size tn, const _cx_rawkey* rkey, int *erased) { +_cx_memb(_erase_r_)(_cx_self *self, i_size tn, const _cx_rawkey* rkey, int *erased) { + _cx_node *d = self->nodes; if (tn == 0) return 0; _cx_rawkey raw = i_keyto(_i_keyref(&d[tn].value)); i_size tx; int c = i_cmp((&raw), rkey); if (c != 0) - d[tn].link[c < 0] = _cx_memb(_erase_r_)(d, d[tn].link[c < 0], rkey, erased); + d[tn].link[c < 0] = _cx_memb(_erase_r_)(self, d[tn].link[c < 0], rkey, erased); else { if (!(*erased)++) _cx_memb(_value_drop)(&d[tn].value); @@ -465,14 +454,13 @@ _cx_memb(_erase_r_)(_cx_node *d, i_size tn, const _cx_rawkey* rkey, int *erased) tx = d[tx].link[1]; d[tn].value = d[tx].value; /* move */ raw = i_keyto(_i_keyref(&d[tn].value)); - d[tn].link[0] = _cx_memb(_erase_r_)(d, d[tn].link[0], &raw, erased); + d[tn].link[0] = _cx_memb(_erase_r_)(self, d[tn].link[0], &raw, erased); } else { /* unlink node */ tx = tn; tn = d[tn].link[ d[tn].link[0] == 0 ]; /* move it to disposed nodes list */ - struct csmap_rep *rep = c_unchecked_container_of(d, struct csmap_rep, nodes); - d[tx].link[1] = (i_size) rep->disp; - rep->disp = tx; + d[tx].link[1] = self->disp; + self->disp = tx; } } tx = d[tn].link[1]; @@ -491,24 +479,24 @@ _cx_memb(_erase_r_)(_cx_node *d, i_size tn, const _cx_rawkey* rkey, int *erased) STC_DEF int _cx_memb(_erase)(_cx_self* self, _cx_rawkey rkey) { int erased = 0; - i_size root = _cx_memb(_erase_r_)(self->nodes, (i_size) _csmap_rep(self)->root, &rkey, &erased); - if (erased) { - _csmap_rep(self)->root = root; - --_csmap_rep(self)->size; - return 1; - } - return 0; + i_size root = _cx_memb(_erase_r_)(self, self->root, &rkey, &erased); + if (!erased) + return 0; + self->root = root; + --self->size; + return 1; } STC_DEF _cx_iter _cx_memb(_erase_at)(_cx_self* self, _cx_iter it) { - _cx_rawkey raw = i_keyto(_i_keyref(it.ref)), nxt; + _cx_rawkey raw = i_keyto(_i_keyref(it.ref)); _cx_memb(_next)(&it); - if (it.ref) - nxt = i_keyto(_i_keyref(it.ref)); - _cx_memb(_erase)(self, raw); - if (it.ref) + if (it.ref) { + _cx_rawkey nxt = i_keyto(_i_keyref(it.ref)); + _cx_memb(_erase)(self, raw); _cx_memb(_find_it)(self, nxt, &it); + } else + _cx_memb(_erase)(self, raw); return it; } @@ -546,10 +534,10 @@ _cx_memb(_clone_r_)(_cx_self* self, _cx_node* src, i_size sn) { STC_DEF _cx_self _cx_memb(_clone)(_cx_self tree) { - _cx_self clone = _cx_memb(_with_capacity)(_csmap_rep(&tree)->size); - i_size root = _cx_memb(_clone_r_)(&clone, tree.nodes, (i_size) _csmap_rep(&tree)->root); - _csmap_rep(&clone)->root = root; - _csmap_rep(&clone)->size = _csmap_rep(&tree)->size; + _cx_self clone = _cx_memb(_with_capacity)(tree.size); + i_size root = _cx_memb(_clone_r_)(&clone, tree.nodes, tree.root); + clone.root = root; + clone.size = tree.size; return clone; } #endif // !_i_no_clone @@ -577,11 +565,9 @@ _cx_memb(_drop_r_)(_cx_node* d, i_size tn) { STC_DEF void _cx_memb(_drop)(_cx_self* self) { - struct csmap_rep* rep = _csmap_rep(self); - // second test is bogus, but supresses gcc warning: - if (rep->cap && rep != &_csmap_sentinel) { - _cx_memb(_drop_r_)(self->nodes, (i_size) rep->root); - c_free(rep); // correct, but may give warning + if (self->cap) { + _cx_memb(_drop_r_)(self->nodes, self->root); + c_free(self->nodes); } } diff --git a/include/stc/forward.h b/include/stc/forward.h index e78f1dd7..ef287fe4 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -185,6 +185,7 @@ typedef union { \ typedef struct { \ SELF##_node *nodes; \ + SELF##_size_t root, disp, head, size, cap; \ } SELF #endif #define _c_cstack_types(SELF, VAL) \ -- cgit v1.2.3