From 090e3b780b7499b4b5f299ae6c77e6e633d05a17 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 7 Feb 2021 00:23:57 +0100 Subject: Internal rename. --- examples/csmap_ex.c | 18 ++++++++++++------ stc/cmap.h | 4 ++-- stc/csmap.h | 50 +++++++++++++++++++++++--------------------------- 3 files changed, 37 insertions(+), 35 deletions(-) diff --git a/examples/csmap_ex.c b/examples/csmap_ex.c index f26c0fc0..032400f9 100644 --- a/examples/csmap_ex.c +++ b/examples/csmap_ex.c @@ -10,11 +10,12 @@ using_csset_str(); int main(int argc, char **argv) { - csmap_i map = csmap_i_init(); + size_t n = 1000000; + + csmap_i map = csmap_i_with_capacity(n); time_t seed = time(NULL); - size_t n = 1000000; - uint64_t mask = (1ull << 28) - 1; + uint64_t mask = (1ull << 31) - 1; csmap_i_iter_t it; stc64_srandom(seed); @@ -22,17 +23,22 @@ int main(int argc, char **argv) uint64_t val = stc64_random() & mask; csmap_i_emplace(&map, val, i); } - printf("size %zu\n\n", csmap_i_size(map)); + printf("size1: %zu, %zu\n", csmap_i_size(map), csmap_i_capacity(map)); stc64_srandom(seed); c_forrange (n - 20) csmap_i_erase(&map, stc64_random() & mask); size_t val = 500000; - csmap_i_emplace(&map, val, 5); + c_forrange (i, n) { + uint64_t val = stc64_random() & mask; + csmap_i_emplace(&map, val, i); + } + + printf("size2: %zu, %zu\n", csmap_i_size(map), csmap_i_capacity(map)); int k = 0; c_foreach (i, csmap_i, map) - printf("%2d %d: %zu\n", ++k, i.ref->first, i.ref->second); + if (k < 20) printf("%2d %d: %zu\n", ++k, i.ref->first, i.ref->second); csmap_i_find_it(&map, val, &it); printf("\nmin/max: %d -- %d: found: %d. size: %zu\n", csmap_i_front(&map)->first, diff --git a/stc/cmap.h b/stc/cmap.h index 78f9468f..4e582585 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -146,12 +146,12 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t; \ typedef SET_ONLY_##C( C##_##X##_key_t ) \ MAP_ONLY_##C( struct {C##_##X##_key_t first; \ - C##_##X##_mapped_t second;} ) \ + C##_##X##_mapped_t second;} ) \ C##_##X##_value_t; \ \ typedef SET_ONLY_##C( C##_##X##_rawkey_t ) \ MAP_ONLY_##C( struct {C##_##X##_rawkey_t first; \ - C##_##X##_rawmapped_t second;} ) \ + C##_##X##_rawmapped_t second;} ) \ C##_##X##_rawvalue_t; \ \ typedef struct { \ diff --git a/stc/csmap.h b/stc/csmap.h index b765d1c1..c72efede 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -150,15 +150,15 @@ int main(void) { C##_##X##_size_t _tn, _st[48]; \ } C##_##X##_iter_t -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) +struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; +#define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes) #define _using_AATREE(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \ keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \ _using_AATREE_types(X, C, Key, Mapped); \ \ typedef struct { \ - C##_##X##_node_t* data; \ + C##_##X##_node_t* nodes; \ } C##_##X; \ \ typedef RawKey C##_##X##_rawkey_t; \ @@ -278,7 +278,7 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* data[]; }; \ STC_INLINE C##_##X##_iter_t \ C##_##X##_begin(C##_##X* self) { \ - C##_##X##_iter_t it = {NULL, self->data, 0, (C##_##X##_size_t) _csmap_rep(self)->root}; \ + C##_##X##_iter_t it = {NULL, self->nodes, 0, (C##_##X##_size_t) _csmap_rep(self)->root}; \ if (it._tn) C##_##X##_next(&it); \ return it; \ } \ @@ -310,20 +310,20 @@ 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 tree = {(C##_##X##_node_t *) _smap_inits.data}; \ + C##_##X tree = {(C##_##X##_node_t *) _smap_inits.nodes}; \ return tree; \ } \ \ STC_DEF C##_##X##_value_t* \ C##_##X##_front(C##_##X* self) { \ - C##_##X##_node_t *d = self->data; \ + C##_##X##_node_t *d = self->nodes; \ C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \ while (d[tn].link[0]) tn = d[tn].link[0]; \ return &d[tn].value; \ } \ STC_DEF C##_##X##_value_t* \ C##_##X##_back(C##_##X* self) { \ - C##_##X##_node_t *d = self->data; \ + C##_##X##_node_t *d = self->nodes; \ C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \ while (d[tn].link[1]) tn = d[tn].link[1]; \ return &d[tn].value; \ @@ -339,7 +339,7 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; if (oldcap == 0) \ memset(rep, 0, sizeof(struct csmap_rep) + sizeof(C##_##X##_node_t)); \ rep->cap = cap; \ - self->data = (C##_##X##_node_t *) rep->data; \ + self->nodes = (C##_##X##_node_t *) rep->nodes; \ } \ } \ \ @@ -348,27 +348,20 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; size_t tn; struct csmap_rep *rep = _csmap_rep(self); \ if (rep->disp) { \ tn = rep->disp; \ - rep->disp = self->data[tn].link[1]; \ + rep->disp = self->nodes[tn].link[1]; \ } 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]; \ + C##_##X##_node_t* dn = &self->nodes[tn]; \ dn->link[0] = dn->link[1] = 0; dn->level = level; \ return (C##_##X##_size_t) tn; \ } \ -\ - STC_INLINE void \ - C##_##X##_node_unlink_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \ - struct csmap_rep *rep = c_container_of(d, struct csmap_rep, data); \ - d[tn].link[1] = (C##_##X##_size_t) rep->disp; \ - rep->disp = tn; \ - } \ \ STC_DEF C##_##X##_value_t* \ C##_##X##_find_it(const C##_##X* self, C##_##X##_rawkey_t rkey, C##_##X##_iter_t* out) { \ C##_##X##_size_t tn = _csmap_rep(self)->root; \ - C##_##X##_node_t *d = out->_d = self->data; \ + C##_##X##_node_t *d = out->_d = self->nodes; \ out->_top = 0; \ while (tn) { \ C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&d[tn].value)); \ @@ -421,7 +414,7 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; static inline C##_##X##_size_t \ C##_##X##insert_entry_i_(C##_##X* self, C##_##X##_size_t tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \ C##_##X##_size_t up[64], it = tn; \ - C##_##X##_node_t* d = self->data; \ + C##_##X##_node_t* d = self->nodes; \ int c, top = 0, dir = 0; \ while (it) { \ up[top++] = it; \ @@ -430,7 +423,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, 1); d = self->data; \ + it = C##_##X##_node_new_(self, 1); d = self->nodes; \ res->first = &d[it].value, res->second = true; \ if (top == 0) return it; \ d[up[top - 1]].link[dir] = it; \ @@ -471,7 +464,10 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; } else { /* unlink node */ \ tx = tn; \ tn = d[tn].link[ d[tn].link[0] == 0 ]; \ - C##_##X##_node_unlink_(d, tx); \ + /* move it to disposed nodes list */ \ + struct csmap_rep *rep = c_container_of(d, struct csmap_rep, nodes); \ + d[tx].link[1] = (C##_##X##_size_t) rep->disp; \ + rep->disp = tx; \ } \ } \ tx = d[tn].link[1]; \ @@ -490,7 +486,7 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; STC_DEF int \ C##_##X##_erase(C##_##X* self, RawKey rkey) { \ int erased = 0; \ - C##_##X##_size_t root = C##_##X##_erase_r_(self->data, (C##_##X##_size_t) _csmap_rep(self)->root, &rkey, &erased); \ + C##_##X##_size_t root = C##_##X##_erase_r_(self->nodes, (C##_##X##_size_t) _csmap_rep(self)->root, &rkey, &erased); \ if (erased) {_csmap_rep(self)->root = root; --_csmap_rep(self)->size;} \ return erased; \ } \ @@ -499,15 +495,15 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; 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; \ + self->nodes[tn].value = C##_##X##_value_clone(src[sn].value); \ + tx = C##_##X##_clone_r_(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx; \ + tx = C##_##X##_clone_r_(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx; \ return tn; \ } \ STC_DEF C##_##X \ 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); \ + C##_##X##_size_t root = C##_##X##_clone_r_(&clone, tree.nodes, (C##_##X##_size_t) _csmap_rep(&tree)->root); \ _csmap_rep(&clone)->root = root; \ _csmap_rep(&clone)->size = _csmap_rep(&tree)->size; \ return clone; \ @@ -524,7 +520,7 @@ static struct csmap_rep _smap_inits = {0, 0, 0, 0}; STC_DEF void \ C##_##X##_del(C##_##X* self) { \ if (_csmap_rep(self)->root) { \ - C##_##X##_del_r_(self->data, (C##_##X##_size_t) _csmap_rep(self)->root); \ + C##_##X##_del_r_(self->nodes, (C##_##X##_size_t) _csmap_rep(self)->root); \ c_free(_csmap_rep(self)); \ } \ } -- cgit v1.2.3