Templated skew(), split(), and next() because of gcc -O3 bugs.

2 files changed, 62 insertions, 63 deletions

diff --git a/examples/csmap_ex.c b/examples/csmap_ex.c
index dac82339..13fbe977 100644
--- a/examples/csmap_ex.c
+++ b/examples/csmap_ex.c
@@ -11,40 +11,45 @@ using_csset_str();
 int main(int argc, char **argv)

 {

     csmap_i map = csmap_i_init();

-    time_t seed = time(NULL);

+    time_t seed = 123 ; // time(NULL);

 

-    size_t n = 1000000;

+    size_t n = 5000000;

     uint64_t mask = (1ull << 20) - 1;

+    csmap_i_iter_t it;

+

     stc64_srandom(seed);

     for (size_t i = 0; i < n; ++i) {

-        csmap_i_emplace(&map, stc64_random() & mask, i);

+        uint64_t val = stc64_random() & mask;

+        csmap_i_emplace(&map, val, i);

+        if (!csmap_i_find(&map, val, &it)) {

+            printf("Not found: %zu, %zu: ", i, val);

+        }

     }

-    puts("inserted");

     stc64_srandom(seed);

     for (unsigned int i = 0; i < n - 50; ++i) {

         csmap_i_erase(&map, stc64_random() & mask);

     }

-

+    

     csmap_i_emplace(&map, 500000, 5);

 

     c_foreach (i, csmap_i, map)

         printf("-- %d: %d\n", i.ref->first, i.ref->second);

     puts("");

 

-    csmap_i_iter_t it;

-    printf("min/max: %d -- %d: %d: %zu\n\n", csmap_i_front(&map)->first,

-                                             csmap_i_back(&map)->first, 

-                                             csmap_i_find(&map, 500000, &it) != NULL,

-                                             csmap_i_size(map));

+    csmap_i_find(&map, 500000, &it);

 

     c_foreach (i, csmap_i, it, csmap_i_end(&map))

         printf("-- %d: %d\n", i.ref->first, i.ref->second);

     printf("\n%d: %d\n", 500000, *csmap_i_at(&map, 500000));

 

+    printf("min/max: %d -- %d: %d: %zu\n\n", csmap_i_front(&map)->first,

+                                             csmap_i_back(&map)->first, 

+                                             csmap_i_find(&map, 500000, &it) != NULL,

+                                             csmap_i_size(map));

+

     csmap_i_del(&map);

     puts("done\n");

 

-

     c_init (csset_str, names, {

         "Hello", "Try this", "Awesome", "Works well", "Greetings"

     });

diff --git a/stc/csmap.h b/stc/csmap.h
index b4a215c6..49600b96 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -265,15 +265,13 @@ int main(void) {
         return &tn->value; \

     } \

 \

-    STC_INLINE void \

-    C##_##X##_next(C##_##X##_iter_t* it) { \

-        cbst_next((csmap___iter_t*) it, offsetof(C##_##X##_node_t, value)); \

-    } \

+    STC_API void \

+    C##_##X##_next(C##_##X##_iter_t* it); \

+\

     STC_INLINE C##_##X##_iter_t \

     C##_##X##_begin(C##_##X* self) { \

         C##_##X##_iter_t it = {NULL, 0, self->root}; \

-        cbst_next((csmap___iter_t*) &it, offsetof(C##_##X##_node_t, value)); \

-        return it; \

+        C##_##X##_next(&it); return it; \

     } \

     STC_INLINE C##_##X##_iter_t \

     C##_##X##_end(C##_##X* self) {\

@@ -304,10 +302,6 @@ int main(void) {
 _using_CBST_types(_, csmap, int, int);

 static csmap___node_t cbst_nil = {&cbst_nil, &cbst_nil, 0};

 

-STC_API csmap___node_t* cbst_skew(csmap___node_t *tn);

-STC_API csmap___node_t* cbst_split(csmap___node_t *tn);

-STC_API void cbst_next(csmap___iter_t *it, size_t offset);

-

 /* -------------------------- IMPLEMENTATION ------------------------- */

 

 #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION)

@@ -328,6 +322,44 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
         } \

     } \

 \

+    static C##_##X##_node_t * \

+    C##_##X##_skew_(C##_##X##_node_t *tn) { \

+        if (tn->link[0]->level == tn->level && tn->level) { \

+            C##_##X##_node_t *tmp = tn->link[0]; \

+            tn->link[0] = tmp->link[1]; \

+            tmp->link[1] = tn; \

+            tn = tmp; \

+        } \

+        return tn; \

+    } \

+\

+    static C##_##X##_node_t * \

+    C##_##X##_split_(C##_##X##_node_t *tn) { \

+        if (tn->link[1]->link[1]->level == tn->level && tn->level) { \

+            C##_##X##_node_t *tmp = tn->link[1]; \

+            tn->link[1] = tmp->link[0]; \

+            tmp->link[0] = tn; \

+            tn = tmp; \

+            ++tn->level; \

+        } \

+        return tn; \

+    } \

+\

+    STC_DEF void \

+    C##_##X##_next(C##_##X##_iter_t *it) { \

+        C##_##X##_node_t *tn = it->_tn; \

+        if (it->_top || tn->level) { \

+            while (tn->level) { \

+                it->_st[it->_top++] = tn; \

+                tn = tn->link[0]; \

+            } \

+            tn = it->_st[--it->_top]; \

+            it->_tn = tn->link[1]; \

+            it->ref = &tn->value; \

+        } else \

+            it->ref = NULL; \

+    } \

+\

     STC_DEF C##_##X##_node_t* \

     C##_##X##_insert_key_r_(C##_##X##_node_t* tn, const C##_##X##_rawkey_t* rkey, C##_##X##_result_t* res) { \

         if (tn->level == 0) { \

@@ -341,8 +373,8 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
         int c = keyCompareRaw(&r, rkey); \

         if (c == 0) { res->first = &tn->value; return tn; } \

         tn->link[c == -1] = C##_##X##_insert_key_r_(tn->link[c == -1], rkey, res); \

-        tn = (C##_##X##_node_t*) cbst_skew((csmap___node_t*) tn); \

-        tn = (C##_##X##_node_t*) cbst_split((csmap___node_t*) tn); \

+        tn = C##_##X##_skew_(tn); \

+        tn = C##_##X##_split_(tn); \

         return tn; \

     } \

 \

@@ -381,8 +413,8 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
         if (tn->link[0]->level < tn->level - 1 || tn->link[1]->level < tn->level - 1) { \

             if (tn->link[1]->level > --tn->level) \

                 tn->link[1]->level = tn->level; \

-            tn = (C##_##X##_node_t*) cbst_skew((csmap___node_t*) tn); \

-            tn = (C##_##X##_node_t*) cbst_split((csmap___node_t*) tn); \

+            tn = C##_##X##_skew_(tn); \

+            tn = C##_##X##_split_(tn); \

         } \

         return tn; \

     } \

@@ -413,44 +445,6 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
         return cn; \

     }

 

-STC_DEF csmap___node_t *

-cbst_skew(csmap___node_t *tn) {

-    if (tn->link[0]->level == tn->level && tn->level) {

-        csmap___node_t *tmp = tn->link[0];

-        tn->link[0] = tmp->link[1];

-        tmp->link[1] = tn;

-        tn = tmp;

-    }

-    return tn;

-}

-

-STC_DEF csmap___node_t *

-cbst_split(csmap___node_t *tn) {

-    if (tn->link[1]->link[1]->level == tn->level && tn->level) {

-        csmap___node_t *tmp = tn->link[1];

-        tn->link[1] = tmp->link[0];

-        tmp->link[0] = tn;

-        tn = tmp;

-        ++tn->level;

-    }

-    return tn;

-}

-

-STC_DEF void

-cbst_next(csmap___iter_t *it, size_t offset) {

-    csmap___node_t *tn = it->_tn;

-    if (it->_top || tn->level) {

-        while (tn->level) {

-            it->_st[it->_top++] = tn;

-            tn = tn->link[0];

-        }

-        tn = it->_st[--it->_top];

-        it->_tn = tn->link[1];

-        it->ref = (csmap___value_t *) ((uint8_t *)tn + offset);

-    } else

-        it->ref = NULL;

-}

-

 #else

 #define _implement_CBST(X, C, Key, Mapped, mappedDel, keyCompareRaw, keyDel, \

                            keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped)