From 8b3ee061718a11827466c9e376bf91a06ad23689 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 6 Feb 2021 12:52:10 +0100 Subject: Fixed bug in node_new() and clone() csmap. --- stc/cmap.h | 10 +++++----- stc/csmap.h | 47 ++++++++++++++++++++++++----------------------- 2 files changed, 29 insertions(+), 28 deletions(-) diff --git a/stc/cmap.h b/stc/cmap.h index 5123dd2b..6c8ee8ad 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -195,11 +195,11 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; MAP_ONLY_##C( mappedDel(&val->second); ) \ } \ STC_INLINE size_t \ - C##_##X##_bucket_count(C##_##X m) {return (size_t) m.bucket_count;} \ + C##_##X##_bucket_count(C##_##X map) {return (size_t) map.bucket_count;} \ STC_INLINE size_t \ - C##_##X##_capacity(C##_##X m) {return (size_t) (m.bucket_count * m.max_load_factor);} \ + C##_##X##_capacity(C##_##X map) {return (size_t) (map.bucket_count * map.max_load_factor);} \ STC_INLINE void \ - C##_##X##_swap(C##_##X* a, C##_##X* b) {c_swap(C##_##X, *a, *b);} \ + C##_##X##_swap(C##_##X *map1, C##_##X *map2) {c_swap(C##_##X, *map1, *map2);} \ STC_INLINE void \ C##_##X##_set_load_factors(C##_##X* self, float min_load, float max_load) { \ self->min_load_factor = min_load; \ @@ -208,9 +208,9 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; STC_API C##_##X \ C##_##X##_with_capacity(size_t cap); \ STC_API C##_##X \ - C##_##X##_clone(C##_##X m); \ + C##_##X##_clone(C##_##X map); \ STC_API void \ - C##_##X##_reserve(C##_##X* self, size_t size); \ + C##_##X##_reserve(C##_##X* self, size_t capacity); \ STC_API void \ C##_##X##_del(C##_##X* self); \ STC_API void \ diff --git a/stc/csmap.h b/stc/csmap.h index 4d897722..881d9070 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -150,7 +150,7 @@ int main(void) { C##_##X##_size_t _tn, _st[48]; \ } C##_##X##_iter_t -struct csmap_rep { size_t root, disp, size, cap; void* data[]; }; +struct csmap_rep { size_t root, disp, head, size, cap; void* data[]; }; #define _csmap_rep(self) c_container_of((self)->data, struct csmap_rep, data) #define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ @@ -174,7 +174,7 @@ struct csmap_rep { size_t root, disp, size, cap; void* data[]; }; } C##_##X##_result_t; \ \ STC_API C##_##X C##_##X##_init(void); \ - STC_API C##_##X C##_##X##_clone(C##_##X bst); \ + STC_API C##_##X C##_##X##_clone(C##_##X tree); \ \ STC_API void \ C##_##X##_reserve(C##_##X* self, size_t cap); \ @@ -185,9 +185,9 @@ struct csmap_rep { size_t root, disp, size, cap; void* data[]; }; return x; \ } \ STC_INLINE bool \ - C##_##X##_empty(C##_##X m) {return _csmap_rep(&m)->size == 0;} \ + C##_##X##_empty(C##_##X tree) {return _csmap_rep(&tree)->size == 0;} \ STC_INLINE size_t \ - C##_##X##_size(C##_##X m) {return _csmap_rep(&m)->size;} \ + C##_##X##_size(C##_##X tree) {return _csmap_rep(&tree)->size;} \ STC_API void \ C##_##X##_del(C##_##X* self); \ STC_INLINE void \ @@ -302,8 +302,8 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ STC_DEF C##_##X \ C##_##X##_init(void) { \ - C##_##X m = {(C##_##X##_node_t *) _smap_inits.data}; \ - return m; \ + C##_##X tree = {(C##_##X##_node_t *) _smap_inits.data}; \ + return tree; \ } \ \ STC_DEF C##_##X##_value_t* \ @@ -336,15 +336,17 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; } \ \ STC_DEF C##_##X##_size_t \ - C##_##X##_node_new_(C##_##X* self) { \ + C##_##X##_node_new_(C##_##X* self, int level) { \ size_t tn; struct csmap_rep *rep = _csmap_rep(self); \ if (rep->disp) { \ tn = rep->disp; \ rep->disp = self->data[tn].link[1]; \ - } else if ((tn = rep->size + 1) > rep->cap) \ - C##_##X##_reserve(self, 4 + tn*3/2); \ + } else { \ + if ((tn = rep->head + 1) > rep->cap) C##_##X##_reserve(self, 4 + tn*3/2); \ + ++_csmap_rep(self)->head; /* do after reserve */ \ + } \ C##_##X##_node_t* dn = &self->data[tn]; \ - dn->link[0] = dn->link[1] = 0; dn->level = 1; \ + dn->link[0] = dn->link[1] = 0; dn->level = level; \ return (C##_##X##_size_t) tn; \ } \ \ @@ -420,7 +422,7 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; dir = (c == -1); \ it = d[it].link[dir]; \ } \ - it = C##_##X##_node_new_(self); d = self->data; \ + it = C##_##X##_node_new_(self, 1); d = self->data; \ *KEY_REF_##C(&d[it].value) = keyFromRaw(*rkey); \ res->first = &d[it].value, res->second = true; \ if (top == 0) return it; \ @@ -487,21 +489,20 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; } \ \ static C##_##X##_size_t \ - C##_##X##_clone_r_(C##_##X* self, const C##_##X##_node_t* src, C##_##X##_size_t tn) { \ - if (tn == 0) return 0; \ - C##_##X##_size_t cn = C##_##X##_node_new_(self); \ - C##_##X##_node_t* d = self->data; \ - d[cn].link[0] = C##_##X##_clone_r_(self, src, src[tn].link[0]); \ - d[cn].link[1] = C##_##X##_clone_r_(self, src, src[tn].link[1]); \ - d[cn].level = src[tn].level; \ - d[cn].value = C##_##X##_value_clone(src[tn].value); \ - return cn; \ + C##_##X##_clone_r_(C##_##X* self, const C##_##X##_node_t* src, C##_##X##_size_t sn) { \ + if (sn == 0) return 0; \ + C##_##X##_size_t tx, tn = C##_##X##_node_new_(self, src[sn].level); \ + self->data[tn].value = C##_##X##_value_clone(src[sn].value); \ + tx = C##_##X##_clone_r_(self, src, src[sn].link[0]); self->data[tn].link[0] = tx; \ + tx = C##_##X##_clone_r_(self, src, src[sn].link[1]); self->data[tn].link[1] = tx; \ + return tn; \ } \ STC_DEF C##_##X \ - C##_##X##_clone(C##_##X bst) { \ - C##_##X clone = C##_##X##_with_capacity(_csmap_rep(&bst)->size); \ - C##_##X##_size_t root = C##_##X##_clone_r_(&clone, bst.data, (C##_##X##_size_t) _csmap_rep(&bst)->root); \ + C##_##X##_clone(C##_##X tree) { \ + C##_##X clone = C##_##X##_with_capacity(_csmap_rep(&tree)->size); \ + C##_##X##_size_t root = C##_##X##_clone_r_(&clone, tree.data, (C##_##X##_size_t) _csmap_rep(&tree)->root); \ _csmap_rep(&clone)->root = root; \ + _csmap_rep(&clone)->size = _csmap_rep(&tree)->size; \ return clone; \ } \ \ -- cgit v1.2.3