From b1de47b93bcc706c9846fedda33fc9c8f282dd65 Mon Sep 17 00:00:00 2001
From: Tyge Løvset <tylo@norceresearch.no>
Date: Sun, 17 Jan 2021 23:22:41 +0100
Subject: Templated skew(), split(), and next() because of gcc -O3 bugs.

---
 examples/csmap_ex.c | 27 +++++++++------
 stc/csmap.h         | 98 +++++++++++++++++++++++++----------------------------
 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)
@@ -327,6 +321,44 @@ STC_API void cbst_next(csmap___iter_t *it, size_t offset);
             c_free(tn); \
         } \
     } \
+\
+    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) { \
@@ -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)
-- 
cgit v1.2.3