Two fixes in csmap. erase: value_del called on wrong node. Forgot calling skew and split 3 and 2 times in erase.

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<int, int>;

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; \

     } \