From 62a4ffee9682a79123ac8fdfaa331f324140aaf6 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 3 Feb 2021 19:55:22 +0100 Subject: Two fixes in csmap. erase: value_del called on wrong node. Forgot calling skew and split 3 and 2 times in erase. --- benchmarks/csmap_benchmark2.cpp | 2 +- examples/csmap_ex2.c | 33 +++++++++++++++++++------ stc/csmap.h | 55 ++++++++++++++++++++++------------------- 3 files changed, 55 insertions(+), 35 deletions(-) diff --git a/benchmarks/csmap_benchmark2.cpp b/benchmarks/csmap_benchmark2.cpp index 770bdde5..5bb17bda 100644 --- a/benchmarks/csmap_benchmark2.cpp +++ b/benchmarks/csmap_benchmark2.cpp @@ -9,7 +9,7 @@ #define PICOBENCH_IMPLEMENT_WITH_MAIN #include "picobench.hpp" -enum {N1 = 3000000, S1 = 1}; +enum {N1 = 2000000, S1 = 1}; uint64_t seed = time(NULL); // 18237129837891; using omap_i = std::map; diff --git a/examples/csmap_ex2.c b/examples/csmap_ex2.c index ebb0f6cf..b316d292 100644 --- a/examples/csmap_ex2.c +++ b/examples/csmap_ex2.c @@ -7,26 +7,43 @@ #endif using_csmap(i, int, int); -enum {N=10000000}; +enum {N=2000}; int main() { clock_t t1, t2, t3, t4, t5; { t1 = clock(); csmap_i map = csmap_i_init(); - stc64_srandom(1); - c_forrange (i, N) - csmap_i_emplace(&map, stc64_random() & 0xffffff, i); - c_forrange (i, N/2) - csmap_i_erase(&map, stc64_random() & 0xffffff); + stc64_srandom(123); + c_forrange (i, 12) { + int x = stc64_random() & 0xff; + csmap_i_emplace(&map, x, i); + printf(" %d", x); + } + puts(""); + c_foreach (i, csmap_i, map) printf(" %d", i.ref->first); + puts("\n"); + //c_foreach (i, csmap_i, map) + //printf("%d: %d\n", i.ref->first, i.ref->second); + printf("size %zu\n", csmap_i_size(map)); + + stc64_srandom(123); + c_forrange (i, 6) { + int x = stc64_random() & 0xff; + printf("Try erase: %d\n", x); + csmap_i_erase(&map, x); + c_foreach (i, csmap_i, map) printf(" %d", i.ref->first); + puts(""); + } t2 = clock(); size_t n = 0, sum = 0; c_foreach (i, csmap_i, map) sum += i.ref->first; t3 = clock(); - c_foreach (i, csmap_i, map) - if (n++ < 20) printf("%d: %d\n", i.ref->first, i.ref->second); else break; + //c_foreach (i, csmap_i, map) + //if (n++ < 20) printf("%d: %d\n", i.ref->first, i.ref->second); else break; printf("size %zu: %zu\n", csmap_i_size(map), sum); + t4 = clock(); csmap_i_del(&map); } diff --git a/stc/csmap.h b/stc/csmap.h index 9d020398..d726a836 100644 --- a/stc/csmap.h +++ b/stc/csmap.h @@ -367,8 +367,8 @@ int main(void) { STC_DEF void \ C##_##X##_next(C##_##X##_iter_t *it) { \ C##_##X##_size_t tn = it->_tn; \ - if (it->_top || it->_d[tn].level) { \ - while (it->_d[tn].level) { \ + if (it->_top || tn) { \ + while (tn) { \ it->_st[it->_top++] = tn; \ tn = it->_d[tn].link[0]; \ } \ @@ -381,7 +381,7 @@ int main(void) { \ static C##_##X##_size_t \ C##_##X##_skew_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \ - if (d[d[tn].link[0]].level == d[tn].level) { \ + if (tn && d[d[tn].link[0]].level == d[tn].level) { \ C##_##X##_size_t tmp = d[tn].link[0]; \ d[tn].link[0] = d[tmp].link[1]; \ d[tmp].link[1] = tn; \ @@ -389,10 +389,9 @@ int main(void) { } \ return tn; \ } \ -\ static C##_##X##_size_t \ C##_##X##_split_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \ - if (d[d[d[tn].link[1]].link[1]].level == d[tn].level) { \ + if (tn && d[d[d[tn].link[1]].link[1]].level == d[tn].level) { \ C##_##X##_size_t tmp = d[tn].link[1]; \ d[tn].link[1] = d[tmp].link[0]; \ d[tmp].link[0] = tn; \ @@ -409,8 +408,8 @@ int main(void) { int c, top = 0, dir = 0; \ while (it) { \ up[top++] = it; \ - C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&d[it].value)); \ - if ((c = keyCompareRaw(&r, rkey)) == 0) {res->first = &d[it].value; return tn;} \ + C##_##X##_rawkey_t raw = keyToRaw(KEY_REF_##C(&d[it].value)); \ + if ((c = keyCompareRaw(&raw, rkey)) == 0) {res->first = &d[it].value; return tn;} \ dir = (c == -1); \ it = d[it].link[dir]; \ } \ @@ -440,32 +439,36 @@ int main(void) { static C##_##X##_size_t \ C##_##X##_erase_r_(C##_##X##_node_t *d, C##_##X##_size_t tn, const C##_##X##_rawkey_t* rkey, int *erased) { \ if (tn == 0) return 0; \ - C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&d[tn].value)); \ - int c = keyCompareRaw(&r, rkey); \ + C##_##X##_rawkey_t raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \ + C##_##X##_size_t tx; int c = keyCompareRaw(&raw, rkey); \ if (c != 0) \ d[tn].link[c == -1] = C##_##X##_erase_r_(d, d[tn].link[c == -1], rkey, erased); \ else { \ - if (d[d[tn].link[0]].level && d[d[tn].link[1]].level) { \ - C##_##X##_size_t h = d[tn].link[0]; \ - while (d[d[h].link[1]].level) \ - h = d[h].link[1]; \ - d[tn].value = d[h].value; \ - r = keyToRaw(KEY_REF_##C(&d[tn].value)); \ - d[tn].link[0] = C##_##X##_erase_r_(d, d[tn].link[0], &r, erased); \ + if (d[tn].link[0] && d[tn].link[1]) { \ + tx = d[tn].link[0]; \ + while (d[tx].link[1]) \ + tx = d[tx].link[1]; \ + C##_##X##_value_del(&d[tn].value); \ + d[tn].value = d[tx].value; /* move */ \ + raw = keyToRaw(KEY_REF_##C(&d[tn].value)); \ + d[tn].link[0] = C##_##X##_erase_r_(d, d[tn].link[0], &raw, erased); \ } else { \ - C##_##X##_size_t tmp = tn; \ - tn = d[tn].link[ d[d[tn].link[0]].level == 0 ]; \ - C##_##X##_value_del(&d[tmp].value); \ - C##_##X##_node_del_(d, tmp); \ + tx = tn; \ + tn = d[tn].link[ d[tn].link[0] == 0 ]; \ + C##_##X##_node_del_(d, tx); \ *erased = 1; \ } \ } \ - C##_##X##_size_t t1 = d[tn].link[1]; \ - if (d[d[tn].link[0]].level < d[tn].level - 1 || d[t1].level < d[tn].level - 1) { \ - if (d[t1].level > --d[tn].level) \ - d[t1].level = d[tn].level; \ - tn = C##_##X##_skew_(d, tn); \ - tn = C##_##X##_split_(d, tn); \ + tx = d[tn].link[1]; \ + if (d[d[tn].link[0]].level < d[tn].level - 1 || d[tx].level < d[tn].level - 1) { \ + if (d[tx].level > --d[tn].level) \ + d[tx].level = d[tn].level; \ + if ((tn = C##_##X##_skew_(d, tn))) { \ + tx = d[tn].link[1] = C##_##X##_skew_(d, d[tn].link[1]); \ + d[tx].link[1] = C##_##X##_skew_(d, d[tx].link[1]); \ + tn = C##_##X##_split_(d, tn); \ + d[tn].link[1] = C##_##X##_split_(d, d[tn].link[1]); \ + } \ } \ return tn; \ } \ -- cgit v1.2.3