Rewrote unordered map AA-tree csmap.h. Now uses array as memory pool instead of individual allocated nodes. 40% faster. V1 moved to examples.

6 files changed, 846 insertions, 179 deletions

diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp
index 8624b741..65543712 100644
--- a/benchmarks/cmap_benchmark2.cpp
+++ b/benchmarks/cmap_benchmark2.cpp
@@ -16,10 +16,11 @@ enum {N1 = 4000000, S1 = 1, MaxLoadFactor100 = 80};
 uint64_t seed = time(NULL);

 

 static inline uint32_t hash32(const void* data, size_t len) {

-    return (uint32_t) ((*(const uint32_t *) data) * 2654435769u);

+    return *(const uint32_t *)data * 2654435769u;

 }

 static inline uint32_t hash64(const void* data, size_t len) {

-    return (uint32_t) (((*(const uint64_t *) data) * 11400714819323198485ull) >> 24);

+    uint64_t x = *(const uint64_t *)data * 11400714819323198485ull;

+    return x ^ (x >> 24);

 }

 template <class K, class V> using umap = std::unordered_map<K, V>;

 template <class K, class V> using bmap = ska::bytell_hash_map<K, V>;

@@ -127,14 +128,34 @@ static void ins_and_erase_cmap_i(picobench::state& s)
     cmap_i_del(&map);

 }

 

+static void ins_and_erase_cmap_x(picobench::state& s)

+{

+    cmap_x map = cmap_x_init();

+    cmap_x_set_load_factors(&map, 0.0, MaxLoadFactor100 / 100.0);

+    stc64_srandom(seed);

+

+    picobench::scope scope(s);

+    c_forrange (s.iterations())

+        cmap_x_emplace(&map, stc64_random(), 0);

+    cmap_x_clear(&map);

+    stc64_srandom(seed);

+    c_forrange (s.iterations())

+        cmap_x_emplace(&map, stc64_random(), 0);

+    stc64_srandom(seed);

+    c_forrange (s.iterations())

+        cmap_x_erase(&map, stc64_random());

+    s.set_result(cmap_x_size(map));

+    cmap_x_del(&map);

+}

+

 #define P samples(S1).iterations({N1/4})

-PICOBENCH(ins_and_erase_i<umap_i>).P;

-PICOBENCH(ins_and_erase_i<bmap_i>).P;

-PICOBENCH(ins_and_erase_i<fmap_i>).P;

-PICOBENCH(ins_and_erase_i<hmap_i>).P;

-PICOBENCH(ins_and_erase_i<smap_i>).P;

-PICOBENCH(ins_and_erase_i<rmap_i>).P;

-PICOBENCH(ins_and_erase_cmap_i).P;

+PICOBENCH(ins_and_erase_i<umap_x>).P;

+PICOBENCH(ins_and_erase_i<bmap_x>).P;

+PICOBENCH(ins_and_erase_i<fmap_x>).P;

+PICOBENCH(ins_and_erase_i<hmap_x>).P;

+PICOBENCH(ins_and_erase_i<smap_x>).P;

+PICOBENCH(ins_and_erase_i<rmap_x>).P;

+PICOBENCH(ins_and_erase_cmap_x).P;

 #undef P

 

 PICOBENCH_SUITE("Map3");

diff --git a/benchmarks/csmap_benchmark2.cpp b/benchmarks/csmap_benchmark2.cpp
index 8ef45d9a..770bdde5 100644
--- a/benchmarks/csmap_benchmark2.cpp
+++ b/benchmarks/csmap_benchmark2.cpp
@@ -1,3 +1,4 @@
+#include <iostream>

 #include <stc/crandom.h>

 #include <stc/cstr.h>

 #include <stc/csmap.h>

@@ -8,8 +9,8 @@
 #define PICOBENCH_IMPLEMENT_WITH_MAIN

 #include "picobench.hpp"

 

-enum {N1 = 2000000, S1 = 1};

-uint64_t seed = time(NULL);

+enum {N1 = 3000000, S1 = 1};

+uint64_t seed = time(NULL); // 18237129837891;

 

 using omap_i = std::map<int, int>;

 using omap_x = std::map<uint64_t, uint64_t>;

@@ -25,7 +26,6 @@ template <class MapInt>
 static void ctor_and_ins_one_i(picobench::state& s)

 {

     size_t result = 0;

-

     picobench::scope scope(s);

     c_forrange (n, s.iterations()) {

         MapInt map;

@@ -38,7 +38,6 @@ static void ctor_and_ins_one_i(picobench::state& s)
 static void ctor_and_ins_one_csmap_i(picobench::state& s)

 {

     size_t result = 0;

-

     picobench::scope scope(s);

     c_forrange (n, s.iterations()) {

         csmap_i map = csmap_i_init();

@@ -50,54 +49,96 @@ static void ctor_and_ins_one_csmap_i(picobench::state& s)
 }

 

 #define P samples(S1).iterations({N1})

-PICOBENCH(ctor_and_ins_one_i<omap_i>).P;

-PICOBENCH(ctor_and_ins_one_csmap_i).P;

+//PICOBENCH(ctor_and_ins_one_i<omap_i>).P;

+//PICOBENCH(ctor_and_ins_one_csmap_i).P;

+#undef P

+

+

+PICOBENCH_SUITE("Map_insert_only");

+

+template <class MapInt>

+static void insert_i(picobench::state& s)

+{

+    size_t result = 0;

+    MapInt map;

+    stc64_srandom(seed);

+    s.start_timer();

+    c_forrange (n, s.iterations())

+        map.emplace(stc64_random() & 0xfffffff, n);

+    s.set_result(map.size());

+    s.stop_timer();

+}

+

+static void insert_csmap_i(picobench::state& s)

+{

+    size_t result = 0;

+    csmap_i map = csmap_i_init();

+    stc64_srandom(seed);

+    s.start_timer();

+    c_forrange (n, s.iterations())

+        csmap_i_emplace(&map, stc64_random() & 0xfffffff, n);

+    s.set_result(csmap_i_size(map));

+    s.stop_timer();

+    csmap_i_del(&map);

+}

+

+#define P samples(S1).iterations({N1})

+//PICOBENCH(insert_i<omap_i>).P;

+//PICOBENCH(insert_csmap_i).P;

 #undef P

 

+

 PICOBENCH_SUITE("Map2");

 

 template <class MapInt>

 static void ins_and_erase_i(picobench::state& s)

 {

     size_t result = 0;

+    uint64_t mask = (1ull << s.arg()) - 1;

     MapInt map;

     stc64_srandom(seed);

 

     picobench::scope scope(s);

-    c_forrange (s.iterations())

-        map.emplace(stc64_random(), 0);

+    c_forrange (i, s.iterations())

+        map.emplace(stc64_random() & mask, i);

+    result = map.size();

+

     map.clear();

     stc64_srandom(seed);

-    c_forrange (s.iterations())

-        map.emplace(stc64_random(), 0);

+    c_forrange (i, s.iterations())

+        map[stc64_random() & mask] = i;

+

     stc64_srandom(seed);

     c_forrange (s.iterations())

-        map.erase(stc64_random());

-    s.set_result(map.size());

+        map.erase(stc64_random() & mask);

+    s.set_result(result);

 }

 

 static void ins_and_erase_csmap_i(picobench::state& s)

 {

+    size_t result = 0;

+    uint64_t mask = (1ull << s.arg()) - 1;

     csmap_i map = csmap_i_init();

     stc64_srandom(seed);

 

     picobench::scope scope(s);

-    c_forrange (s.iterations())

-        csmap_i_emplace(&map, stc64_random(), 0);

+    c_forrange (i, s.iterations())

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

+    result = csmap_i_size(map);

 

     csmap_i_clear(&map);

     stc64_srandom(seed);

-    c_forrange (s.iterations())

-        csmap_i_emplace(&map, stc64_random(), 0);

+    c_forrange (i, s.iterations())

+        csmap_i_put(&map, stc64_random() & mask, i);

 

     stc64_srandom(seed);

     c_forrange (s.iterations())

-        csmap_i_erase(&map, stc64_random());

-    s.set_result(csmap_i_size(map));

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

+    s.set_result(result);

     csmap_i_del(&map);

 }

 

-#define P samples(S1).iterations({N1/4})

+#define P samples(S1).iterations({N1/2, N1/2, N1/2, N1/2}).args({18, 23, 25, 31})

 PICOBENCH(ins_and_erase_i<omap_i>).P;

 PICOBENCH(ins_and_erase_csmap_i).P;

 #undef P

@@ -113,9 +154,12 @@ static void ins_and_access_i(picobench::state& s)
     stc64_srandom(seed);

 

     picobench::scope scope(s);

-    c_forrange (N1)

+    c_forrange (N1) {

         result += ++map[stc64_random() & mask];

-    s.set_result(result);

+        auto it = map.find(stc64_random() & mask);

+        if (it != map.end()) map.erase(it->first);

+    }

+    s.set_result(result + map.size());

 }

 

 static void ins_and_access_csmap_i(picobench::state& s)

@@ -126,9 +170,12 @@ static void ins_and_access_csmap_i(picobench::state& s)
     stc64_srandom(seed);

 

     picobench::scope scope(s);

-    c_forrange (N1)

+    c_forrange (N1) {

         result += ++csmap_i_emplace(&map, stc64_random() & mask, 0).first->second;

-    s.set_result(result);

+        csmap_i_value_t* val = csmap_i_find(&map, stc64_random() & mask);

+        if (val) csmap_i_erase(&map, val->first);

+    }

+    s.set_result(result + csmap_i_size(map));

     csmap_i_del(&map);

 }

 

@@ -164,7 +211,7 @@ static void ins_and_access_s(picobench::state& s)
             map.erase(it);

         }

     }

-    s.set_result(result);

+    s.set_result(result + map.size());

 }

 

 static void ins_and_access_csmap_s(picobench::state& s)

@@ -185,14 +232,14 @@ static void ins_and_access_csmap_s(picobench::state& s)
             csmap_s_erase(&map, val->first.str);

         }

     }

-    s.set_result(result);

+    s.set_result(result + csmap_s_size(map));

     cstr_del(&str);

     csmap_s_del(&map);

 }

 

 #define P samples(S1).iterations({N1/5, N1/5, N1/5, N1/10, N1/40}).args({13, 7, 8, 100, 1000})

-PICOBENCH(ins_and_access_s<omap_s>).P;

-PICOBENCH(ins_and_access_csmap_s).P;

+//PICOBENCH(ins_and_access_s<omap_s>).P;

+//PICOBENCH(ins_and_access_csmap_s).P;

 #undef P

 

 PICOBENCH_SUITE("Map5");

@@ -257,6 +304,6 @@ static void iterate_csmap_x(picobench::state& s)
 

 

 #define P samples(S1).iterations({N1/20}).args({12})

-PICOBENCH(iterate_x<omap_x>).P;

-PICOBENCH(iterate_csmap_x).P;

+//PICOBENCH(iterate_x<omap_x>).P;

+//PICOBENCH(iterate_csmap_x).P;

 #undef P

diff --git a/examples/csmap_ex2.c b/examples/csmap_ex2.c
new file mode 100644
index 00000000..3c2d6cc7
--- /dev/null
+++ b/examples/csmap_ex2.c
@@ -0,0 +1,21 @@
+#include <stc/csmap.h>

+#include <stc/crandom.h>

+#include <stdio.h>

+

+using_csmap(i, int, int);

+

+int main()

+{

+    csmap_i map = csmap_i_init();

+    stc64_srandom(1);

+    c_forrange (i, 1000000) csmap_i_emplace(&map, stc64_random() & 0xffffff, i);

+

+    size_t n = 0, sum = 0;

+    c_foreach (i, csmap_i, map) {

+        sum += i.ref->first;

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

+    }

+    printf("size %zu: %zu\n", csmap_i_size(map), sum);

+    csmap_i_del(&map);

+    puts("done");

+}
\ No newline at end of file
diff --git a/examples/csmap_v1.h b/examples/csmap_v1.h
new file mode 100644
index 00000000..806d6247
--- /dev/null
+++ b/examples/csmap_v1.h
@@ -0,0 +1,507 @@
+/* MIT License

+ *

+ * Copyright (c) 2021 Tyge Løvset, NORCE, www.norceresearch.no

+ *

+ * Permission is hereby granted, free of charge, to any person obtaining a copy

+ * of this software and associated documentation files (the "Software"), to deal

+ * in the Software without restriction, including without limitation the rights

+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

+ * copies of the Software, and to permit persons to whom the Software is

+ * furnished to do so, subject to the following conditions:

+ *

+ * The above copyright notice and this permission notice shall be included in all

+ * copies or substantial portions of the Software.

+ *

+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

+ * SOFTWARE.

+ */

+#ifndef CSMAP__H__

+#define CSMAP__H__

+

+// Sorted/Ordered set and map - implemented as an AA-tree.

+/*

+#include <stdio.h>

+#include <stc/csmap.h>

+using_csset(i, int);        // Set of int

+using_csmap(ic, int, char); // Map of int -> char

+

+int main(void) {

+    csset_sx s = csset_sx_init();

+    csset_sx_insert(&s, 5);

+    csset_sx_insert(&s, 8);

+    c_foreach (i, csset_sx, s)

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

+    csset_sx_del(&s);

+}

+*/

+#include "ccommon.h"

+#include <stdlib.h>

+#include <string.h>

+

+#define using_csmap(...) \

+    c_MACRO_OVERLOAD(using_csmap, __VA_ARGS__)

+

+#define using_csmap_3(X, Key, Mapped) \

+    using_csmap_4(X, Key, Mapped, c_default_compare)

+

+#define using_csmap_4(X, Key, Mapped, keyCompare) \

+    using_csmap_6(X, Key, Mapped, keyCompare, c_default_del, c_default_clone)

+

+#define using_csmap_6(X, Key, Mapped, keyCompare, mappedDel, mappedClone) \

+    using_csmap_8(X, Key, Mapped, keyCompare, mappedDel, mappedClone, c_default_del, c_default_clone)

+

+#define using_csmap_8(X, Key, Mapped, keyCompare, mappedDel, mappedClone, keyDel, keyClone) \

+    using_csmap_10(X, Key, Mapped, keyCompare, mappedDel, mappedClone, \

+                      keyDel, keyClone, c_default_to_raw, Key)

+

+#define using_csmap_10(X, Key, Mapped, keyCompareRaw, mappedDel, mappedClone, \

+                          keyDel, keyFromRaw, keyToRaw, RawKey) \

+    _using_CBST(X, csmap, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

+                   keyFromRaw, keyToRaw, RawKey, mappedClone, c_default_to_raw, Mapped)

+

+/* csset: */

+#define using_csset(...) \

+    c_MACRO_OVERLOAD(using_csset, __VA_ARGS__)

+

+#define using_csset_2(X, Key) \

+    using_csset_3(X, Key, c_default_compare)

+

+#define using_csset_3(X, Key, keyCompare) \

+    using_csset_5(X, Key, keyCompare, c_default_del, c_default_clone)

+

+#define using_csset_5(X, Key, keyCompare, keyDel, keyClone) \

+    using_csset_7(X, Key, keyCompare, keyDel, keyClone, c_default_to_raw, Key)

+

+#define using_csset_7(X, Key, keyCompareRaw, keyDel, keyFromRaw, keyToRaw, RawKey) \

+    _using_CBST(X, csset, Key, Key, keyCompareRaw, _UNUSED_, keyDel, \

+                   keyFromRaw, keyToRaw, RawKey, _UNUSED_, _UNUSED_, void)

+

+/* csset_str, csmap_str, csmap_strkey, csmap_strval: */

+#define using_csset_str() \

+    _using_CBST_strkey(str, csset, cstr_t, _UNUSED_, _UNUSED_)

+#define using_csmap_str() \

+    _using_CBST(str, csmap, cstr_t, cstr_t, cstr_compare_raw, cstr_del, cstr_del, \

+                     cstr_from, cstr_to_raw, const char*, cstr_from, cstr_to_raw, const char*)

+

+#define using_csmap_strkey(...) \

+    c_MACRO_OVERLOAD(using_csmap_strkey, __VA_ARGS__)

+

+#define using_csmap_strkey_2(X, Mapped) \

+    _using_CBST_strkey(X, csmap, Mapped, c_default_del, c_default_clone)

+

+#define using_csmap_strkey_4(X, Mapped, mappedDel, mappedClone) \

+    _using_CBST_strkey(X, csmap, Mapped, mappedDel, mappedClone)

+

+#define _using_CBST_strkey(X, C, Mapped, mappedDel, mappedClone) \

+    _using_CBST(X, C, cstr_t, Mapped, cstr_compare_raw, mappedDel, cstr_del, \

+                   cstr_from, cstr_to_raw, const char*, mappedClone, c_default_to_raw, Mapped)

+

+#define using_csmap_strval(...) \

+    c_MACRO_OVERLOAD(using_csmap_strval, __VA_ARGS__)

+

+#define using_csmap_strval_2(X, Key) \

+    using_csmap_strval_3(X, Key, c_default_compare)

+

+#define using_csmap_strval_3(X, Key, keyCompare) \

+    using_csmap_strval_5(X, Key, keyCompare, c_default_del, c_default_clone)

+

+#define using_csmap_strval_5(X, Key, keyCompare, keyDel, keyClone) \

+    using_csmap_strval_7(X, Key, keyCompare, keyDel, keyClone, c_default_to_raw, Key)

+

+#define using_csmap_strval_7(X, Key, keyCompare, keyDel, keyFromRaw, keyToRaw, RawKey) \

+    _using_CBST(X, csmap, Key, cstr_t, keyCompare, cstr_del, keyDel, \

+                   keyFromRaw, keyToRaw, RawKey, cstr_from, cstr_to_raw, const char*)

+

+#define SET_ONLY_csset(...) __VA_ARGS__

+#define SET_ONLY_csmap(...)

+#define MAP_ONLY_csset(...)

+#define MAP_ONLY_csmap(...) __VA_ARGS__

+#define KEY_REF_csset(vp)   (vp)

+#define KEY_REF_csmap(vp)   (&(vp)->first)

+

+#define _using_CBST_types(X, C, Key, Mapped) \

+    typedef Key C##_##X##_key_t; \

+    typedef Mapped C##_##X##_mapped_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##_value_t; \

+\

+    typedef struct C##_##X##_node { \

+        struct C##_##X##_node *link[2]; \

+        uint8_t level; \

+        C##_##X##_value_t value; \

+    } C##_##X##_node_t; \

+\

+    typedef struct { \

+        C##_##X##_value_t *ref; \

+        int _top; \

+        C##_##X##_node_t *_tn, *_st[50]; \

+    } C##_##X##_iter_t

+

+

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

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

+    _using_CBST_types(X, C, Key, Mapped); \

+\

+    typedef struct { \

+        C##_##X##_node_t* root; \

+        size_t size; \

+    } C##_##X; \

+\

+    typedef RawKey C##_##X##_rawkey_t; \

+    typedef RawMapped C##_##X##_rawmapped_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##_rawvalue_t; \

+\

+    typedef struct { \

+        C##_##X##_value_t *first; \

+        bool second; \

+    } C##_##X##_result_t; \

+\

+    STC_API C##_##X \

+    C##_##X##_init(void); \

+    STC_INLINE bool \

+    C##_##X##_empty(C##_##X m) {return m.size == 0;} \

+    STC_INLINE size_t \

+    C##_##X##_size(C##_##X m) {return m.size;} \

+\

+    STC_API void \

+    C##_##X##_del_r_(C##_##X##_node_t* tn); \

+\

+    STC_INLINE void \

+    C##_##X##_del(C##_##X* self) {C##_##X##_del_r_(self->root);} \

+    STC_INLINE void \

+    C##_##X##_clear(C##_##X* self) {C##_##X##_del(self); *self = C##_##X##_init();} \

+    STC_INLINE void \

+    C##_##X##_swap(C##_##X* a, C##_##X* b) {c_swap(C##_##X, *a, *b);} \

+\

+    STC_INLINE void \

+    C##_##X##_value_del(C##_##X##_value_t* val) { \

+        keyDel(KEY_REF_##C(val)); \

+        MAP_ONLY_##C( mappedDel(&val->second); ) \

+    } \

+    STC_INLINE C##_##X##_value_t \

+    C##_##X##_value_clone(C##_##X##_value_t val) { \

+        *KEY_REF_##C(&val) = keyFromRaw(keyToRaw(KEY_REF_##C(&val))); \

+        MAP_ONLY_##C( val.second = mappedFromRaw(mappedToRaw(&val.second)); ) \

+        return val; \

+    } \

+\

+    STC_API C##_##X##_node_t* C##_##X##_clone_r_(C##_##X##_node_t *tn); \

+    STC_INLINE C##_##X \

+    C##_##X##_clone(C##_##X bst) { \

+        C##_##X clone = {C##_##X##_clone_r_(bst.root), bst.size}; \

+        return clone; \

+    } \

+\

+    STC_API C##_##X##_value_t* \

+    C##_##X##_find_it(const C##_##X* self, RawKey rkey, C##_##X##_iter_t* out); \

+\

+    STC_INLINE C##_##X##_value_t* \

+    C##_##X##_find(const C##_##X* self, RawKey rkey) { \

+        C##_##X##_iter_t it; \

+        return C##_##X##_find_it(self, rkey, &it); \

+    } \

+    STC_INLINE bool \

+    C##_##X##_contains(const C##_##X* self, RawKey rkey) { \

+        return C##_##X##_find(self, rkey) != NULL; \

+    } \

+\

+    STC_API C##_##X##_result_t \

+    C##_##X##_insert_key(C##_##X* self, RawKey rkey); \

+\

+    STC_INLINE C##_##X##_result_t \

+    C##_##X##_emplace(C##_##X* self, RawKey rkey MAP_ONLY_##C(, RawMapped rmapped) ) { \

+        C##_##X##_result_t res = C##_##X##_insert_key(self, rkey); \

+        MAP_ONLY_##C( if (res.second) res.first->second = mappedFromRaw(rmapped); ) \

+        return res; \

+    } \

+    STC_INLINE C##_##X##_result_t \

+    C##_##X##_insert(C##_##X* self, C##_##X##_rawvalue_t raw) { \

+        return SET_ONLY_##C( C##_##X##_insert_key(self, raw) ) \

+               MAP_ONLY_##C( C##_##X##_emplace(self, raw.first, raw.second) ); \

+    } \

+    STC_INLINE void \

+    C##_##X##_push_n(C##_##X* self, const C##_##X##_rawvalue_t arr[], size_t n) { \

+        for (size_t i=0; i<n; ++i) C##_##X##_insert(self, arr[i]); \

+    } \

+\

+    MAP_ONLY_##C( \

+    STC_INLINE C##_##X##_result_t \

+    C##_##X##_put(C##_##X* self, RawKey rkey, RawMapped rmapped) { \

+        C##_##X##_result_t res = C##_##X##_insert_key(self, rkey); \

+        if (!res.second) mappedDel(&res.first->second); \

+        res.first->second = mappedFromRaw(rmapped); return res; \

+    } \

+    STC_INLINE C##_##X##_result_t \

+    C##_##X##_insert_or_assign(C##_##X* self, RawKey rkey, RawMapped rmapped) { \

+        return C##_##X##_put(self, rkey, rmapped); \

+    } \

+    STC_INLINE C##_##X##_result_t \

+    C##_##X##_put_mapped(C##_##X* self, RawKey rkey, Mapped mapped) { \

+        C##_##X##_result_t res = C##_##X##_insert_key(self, rkey); \

+        if (!res.second) mappedDel(&res.first->second); \

+        res.first->second = mapped; return res; \

+    } \

+    STC_INLINE C##_##X##_mapped_t* \

+    C##_##X##_at(const C##_##X* self, RawKey rkey) { \

+        C##_##X##_iter_t it; \

+        return &C##_##X##_find_it(self, rkey, &it)->second; \

+    }) \

+\

+    STC_INLINE C##_##X##_value_t* \

+    C##_##X##_front(C##_##X* self) { \

+        C##_##X##_node_t *tn = self->root; \

+        while (tn->link[0]->level) tn = tn->link[0]; \

+        return &tn->value; \

+    } \

+    STC_INLINE C##_##X##_value_t* \

+    C##_##X##_back(C##_##X* self) { \

+        C##_##X##_node_t *tn = self->root; \

+        while (tn->link[1]->level) tn = tn->link[1]; \

+        return &tn->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}; \

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

+    } \

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

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

+        C##_##X##_iter_t it = {NULL}; return it; \

+    } \

+    STC_INLINE C##_##X##_mapped_t* \

+    C##_##X##_itval(C##_##X##_iter_t it) {return SET_ONLY_##C( it.ref ) \

+                                                 MAP_ONLY_##C( &it.ref->second );} \

+\

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

+    C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased); \

+\

+    STC_INLINE size_t \

+    C##_##X##_erase(C##_##X* self, RawKey rkey) { \

+        int erased = 0; \

+        self->root = C##_##X##_erase_r_(self->root, &rkey, &erased); \

+        self->size -= erased; return erased; \

+    } \

+    STC_INLINE size_t \

+    C##_##X##_erase_at(C##_##X* self, C##_##X##_iter_t pos) { \

+        return C##_##X##_erase(self, keyToRaw(KEY_REF_##C(pos.ref))); \

+    } \

+\

+    _implement_CBST(X, C, Key, Mapped, keyCompareRaw, mappedDel, keyDel, \

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

+    typedef C##_##X C##_##X##_t

+

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

+

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

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

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

+    STC_DEF C##_##X \

+    C##_##X##_init(void) { \

+        C##_##X m = {(C##_##X##_node_t *) &cbst_nil, 0}; \

+        return m; \

+    } \

+\

+    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##_node_t *tn = self->root; \

+        out->_top = 0; \

+        while (tn->level) { \

+            C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&tn->value)); \

+            switch (keyCompareRaw(&rx, &rkey)) { \

+                case -1: tn = tn->link[1]; break; \

+                case 1: out->_st[out->_top++] = tn; tn = tn->link[0]; break; \

+                case 0: out->_tn = tn->link[1]; return (out->ref = &tn->value); \

+            } \

+        } \

+        return (out->ref = NULL); \

+    } \

+\

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

+    } \

+\

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

+    } \

+\

+/*\

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

+    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) { \

+            tn = c_new_1(C##_##X##_node_t); \

+            res->first = &tn->value, res->second = true; \

+            tn->link[0] = tn->link[1] = (C##_##X##_node_t*) &cbst_nil, tn->level = 1; \

+            *KEY_REF_##C(&tn->value) = keyFromRaw(*rkey); \

+            return tn; \

+        } \

+        C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \

+        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##_skew_(tn); \

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

+        return tn; \

+    } \

+\

+    static C##_##X##_size_t ** recursive version, array based ** \

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

+        if (tn == 0) { \

+            tn = C##_##X##_node_new_(self); \

+            *KEY_REF_##C(&self->data[tn].value) = keyFromRaw(*rkey); \

+            res->first = &self->data[tn].value, res->second = true; \

+            return tn; \

+        } \

+        C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&self->data[tn].value)); \

+        int c = keyCompareRaw(&r, rkey), dir; \

+        if (c == 0) { res->first = &self->data[tn].value; return tn; } \

+        dir = (c == -1); \

+        C##_##X##_size_t node = C##_##X##_insert_key_r_(self, self->data[tn].link[dir], rkey, res); \

+        C##_##X##_node_t *d = self->data; \

+        d[tn].link[dir] = node; \

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

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

+        return tn; \

+    } \

+*/\

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

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

+        C##_##X##_node_t *up[64], *it = tn; \

+        int c, top = 0, dir = 0; \

+        while (it->level) { \

+            up[top++] = it; \

+            C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&it->value)); \

+            if ((c = keyCompareRaw(&r, rkey)) == 0) {res->first = &it->value; return tn;} \

+            it = it->link[(dir = (c == -1))]; \

+        } \

+        tn = c_new_1(C##_##X##_node_t); \

+        *KEY_REF_##C(&tn->value) = keyFromRaw(*rkey); \

+        res->first = &tn->value, res->second = true; \

+        tn->link[0] = tn->link[1] = (C##_##X##_node_t*) &cbst_nil, tn->level = 1; \

+        if (top == 0) return tn; \

+        up[top - 1]->link[dir] = tn; \

+        while (top--) { \

+            if (top) dir = (up[top - 1]->link[1] == up[top]); \

+            up[top] = C##_##X##_skew_(up[top]); \

+            up[top] = C##_##X##_split_(up[top]); \

+            if (top) up[top - 1]->link[dir] = up[top]; \

+        } \

+        return up[0]; \

+    } \

+\

+    STC_DEF C##_##X##_result_t \

+    C##_##X##_insert_key(C##_##X* self, RawKey rkey) { \

+        C##_##X##_result_t res = {NULL, false}; \

+        self->root = C##_##X##_insert_key_i_(self->root, &rkey, &res); \

+        self->size += res.second; \

+        return res; \

+    } \

+\

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

+    C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased) { \

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

+            return tn; \

+        C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \

+        int c = keyCompareRaw(&r, rkey); \

+        if (c != 0) \

+            tn->link[c == -1] = C##_##X##_erase_r_(tn->link[c == -1], rkey, erased); \

+        else { \

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

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

+                while (h->link[1]->level) \

+                    h = h->link[1]; \

+                tn->value = h->value; \

+                r = keyToRaw(KEY_REF_##C(&tn->value)); \

+                tn->link[0] = C##_##X##_erase_r_(tn->link[0], &r, erased); \

+            } else { \

+                C##_##X##_node_t *tmp = tn; \

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

+                C##_##X##_value_del(&tmp->value); \

+                free(tmp); \

+                *erased = 1; \

+            } \

+        } \

+        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##_skew_(tn); \

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

+        } \

+        return tn; \

+    } \

+\

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

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

+        if (! tn->level) return tn; \

+        C##_##X##_node_t *cn = c_new_1(C##_##X##_node_t); \

+        cn->link[0] = C##_##X##_clone_r_(tn->link[0]); \

+        cn->link[1] = C##_##X##_clone_r_(tn->link[1]); \

+        cn->level = tn->level; \

+        cn->value = C##_##X##_value_clone(tn->value); \

+        return cn; \

+    } \

+\

+    STC_DEF void \

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

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

+            C##_##X##_del_r_(tn->link[0]); \

+            C##_##X##_del_r_(tn->link[1]); \

+            C##_##X##_value_del(&tn->value); \

+            c_free(tn); \

+        } \

+    }

+

+

+_using_CBST_types(_, csmap, int, int);

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

+

+#else

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

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

+#endif

+

+#endif

diff --git a/stc/crandom.h b/stc/crandom.h
index b43fdd46..689bf620 100644
--- a/stc/crandom.h
+++ b/stc/crandom.h
@@ -84,14 +84,14 @@ STC_INLINE double stc64_uniformf(stc64_t* rng, stc64_uniformf_t* dist) {
 }

 

 #if defined(__SIZEOF_INT128__)

-    #define cumul128(a, b, lo, hi) \

+    #define cmul128(a, b, lo, hi) \

         do { __uint128_t _z = (__uint128_t)(a) * (b); \

              *(lo) = (uint64_t)_z, *(hi) = _z >> 64; } while(0)

 #elif defined(_MSC_VER) && defined(_WIN64)

     #include <intrin.h>

-    #define cumul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0)

+    #define cmul128(a, b, lo, hi) (*(lo) = _umul128(a, b, hi), (void)0)

 #elif defined(__x86_64__)

-    #define cumul128(a, b, lo, hi) \

+    #define cmul128(a, b, lo, hi) \

         asm("mulq %[rhs]" : "=a" (*(lo)), "=d" (*(hi)) \

                           : [lhs] "0" (a), [rhs] "rm" (b))

 #endif

@@ -99,8 +99,8 @@ STC_INLINE double stc64_uniformf(stc64_t* rng, stc64_uniformf_t* dist) {
 /* Unbiased bounded uniform distribution. */

 STC_INLINE int64_t stc64_uniform(stc64_t* rng, stc64_uniform_t* d) {

     uint64_t lo, hi;

-#ifdef cumul128

-    do { cumul128(stc64_rand(rng), d->range, &lo, &hi); } while (lo < d->threshold);

+#ifdef cmul128

+    do { cmul128(stc64_rand(rng), d->range, &lo, &hi); } while (lo < d->threshold);

 #else

     hi = stc64_rand(rng) % d->range;

 #endif

@@ -118,10 +118,11 @@ STC_API double stc64_normalf(stc64_t* rng, stc64_normalf_t* dist);
 

 /* PRNG crandom: by Tyge Løvset, NORCE Research, 2020.

  * Extremely fast PRNG suited for parallel usage with Weyl-sequence parameter.

- * Faster than sfc64, wyhash64, and xoshiro256** on most platforms.

- * 256bit state, updates only 192bit per rng.

- * 2^63 unique threads with a minimum 2^64 period lengths each.

- * 2^127 minimum period length for single thread (double loop).

+ * 256bit state, updates 192bit per rng.

+  * Faster than pcg, sfc64, xoshiro256** on most platforms.

+ * wyrand64 is slightly faster, but has only 64-bit state,

+ * unfit when longer periods or multiple threads are required.

+ * stc64 supports 2^63 unique threads with a minimum 2^64 period lengths each.

  * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test,

  * and simple correlation tests, i.e. interleaved streams with one-bit diff state.

  */

@@ -131,7 +132,7 @@ STC_DEF stc64_t stc64_init(uint64_t seed) {
 }

 STC_DEF stc64_t stc64_with_seq(uint64_t seed, uint64_t seq) {

     stc64_t rng = {{seed, seed, seed, (seq << 1u) | 1u}};

-    for (int i = 0; i < 8; ++i) stc64_rand(&rng);

+    for (int i = 0; i < 12; ++i) stc64_rand(&rng);

     return rng;

 }

 

diff --git a/stc/csmap.h b/stc/csmap.h
index 2e45f1a4..120b79f2 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -123,10 +123,14 @@ int main(void) {
 #define MAP_ONLY_csmap(...) __VA_ARGS__

 #define KEY_REF_csset(vp)   (vp)

 #define KEY_REF_csmap(vp)   (&(vp)->first)

+#ifndef CSMAP_SIZE_T

+#define CSMAP_SIZE_T uint32_t

+#endif

 

 #define _using_CBST_types(X, C, Key, Mapped) \

     typedef Key C##_##X##_key_t; \

     typedef Mapped C##_##X##_mapped_t; \

+    typedef CSMAP_SIZE_T C##_##X##_size_t; \

 \

     typedef SET_ONLY_##C( C##_##X##_key_t ) \

             MAP_ONLY_##C( struct {C##_##X##_key_t first; \

@@ -134,25 +138,24 @@ int main(void) {
     C##_##X##_value_t; \

 \

     typedef struct C##_##X##_node { \

-        struct C##_##X##_node *link[2]; \

-        uint8_t level; \

+        C##_##X##_size_t link[2]; \

+        int8_t level; \

         C##_##X##_value_t value; \

     } C##_##X##_node_t; \

 \

     typedef struct { \

         C##_##X##_value_t *ref; \

+        C##_##X##_node_t *_d; \

         int _top; \

-        C##_##X##_node_t *_tn, *_st[34]; \

+        C##_##X##_size_t _tn, _st[64]; \

     } C##_##X##_iter_t

 

-

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

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

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

     _using_CBST_types(X, C, Key, Mapped); \

 \

     typedef struct { \

-        C##_##X##_node_t* root; \

-        size_t size; \

+        C##_##X##_node_t* data; \

     } C##_##X; \

 \

     typedef RawKey C##_##X##_rawkey_t; \

@@ -167,18 +170,23 @@ int main(void) {
         bool second; \

     } C##_##X##_result_t; \

 \

-    STC_API C##_##X \

-    C##_##X##_init(void); \

+    STC_API C##_##X C##_##X##_init(void); \

+    STC_API C##_##X C##_##X##_clone(C##_##X bst); \

+\

+    STC_API void \

+    C##_##X##_reserve(C##_##X* self, size_t cap); \

+    STC_INLINE C##_##X \

+    C##_##X##_with_capacity(size_t size) { \

+        C##_##X x = C##_##X##_init(); \

+        C##_##X##_reserve(&x, size); \

+        return x; \

+    } \

     STC_INLINE bool \

-    C##_##X##_empty(C##_##X m) {return m.size == 0;} \

+    C##_##X##_empty(C##_##X m) {return _smap_size(&m) == 0;} \

     STC_INLINE size_t \

-    C##_##X##_size(C##_##X m) {return m.size;} \

-\

+    C##_##X##_size(C##_##X m) {return _smap_size(&m);} \

     STC_API void \

-    C##_##X##_del_r_(C##_##X##_node_t* tn); \

-\

-    STC_INLINE void \

-    C##_##X##_del(C##_##X* self) {C##_##X##_del_r_(self->root);} \

+    C##_##X##_del(C##_##X* self); \

     STC_INLINE void \

     C##_##X##_clear(C##_##X* self) {C##_##X##_del(self); *self = C##_##X##_init();} \

     STC_INLINE void \

@@ -196,13 +204,6 @@ int main(void) {
         return val; \

     } \

 \

-    STC_API C##_##X##_node_t* C##_##X##_clone_r_(C##_##X##_node_t *tn); \

-    STC_INLINE C##_##X \

-    C##_##X##_clone(C##_##X bst) { \

-        C##_##X clone = {C##_##X##_clone_r_(bst.root), bst.size}; \

-        return clone; \

-    } \

-\

     STC_API C##_##X##_value_t* \

     C##_##X##_find_it(const C##_##X* self, RawKey rkey, C##_##X##_iter_t* out); \

 \

@@ -258,26 +259,15 @@ int main(void) {
         return &C##_##X##_find_it(self, rkey, &it)->second; \

     }) \

 \

-    STC_INLINE C##_##X##_value_t* \

-    C##_##X##_front(C##_##X* self) { \

-        C##_##X##_node_t *tn = self->root; \

-        while (tn->link[0]->level) tn = tn->link[0]; \

-        return &tn->value; \

-    } \

-    STC_INLINE C##_##X##_value_t* \

-    C##_##X##_back(C##_##X* self) { \

-        C##_##X##_node_t *tn = self->root; \

-        while (tn->link[1]->level) tn = tn->link[1]; \

-        return &tn->value; \

-    } \

-\

-    STC_API void \

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

+    STC_API C##_##X##_value_t* C##_##X##_front(C##_##X* self); \

+    STC_API C##_##X##_value_t* C##_##X##_back(C##_##X* self); \

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

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

+        C##_##X##_iter_t it = {NULL, self->data, 0, (C##_##X##_size_t) _smap_root(self)}; \

+        if (it._tn) C##_##X##_next(&it); \

+        return it; \

     } \

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

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

@@ -286,17 +276,10 @@ int main(void) {
     STC_INLINE C##_##X##_mapped_t* \

     C##_##X##_itval(C##_##X##_iter_t it) {return SET_ONLY_##C( it.ref ) \

                                                  MAP_ONLY_##C( &it.ref->second );} \

+    STC_API int \

+    C##_##X##_erase(C##_##X* self, RawKey rkey); \

 \

-    STC_API C##_##X##_node_t* \

-    C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased); \

-\

-    STC_INLINE size_t \

-    C##_##X##_erase(C##_##X* self, RawKey rkey) { \

-        int erased = 0; \

-        self->root = C##_##X##_erase_r_(self->root, &rkey, &erased); \

-        self->size -= erased; return erased; \

-    } \

-    STC_INLINE size_t \

+    STC_INLINE int \

     C##_##X##_erase_at(C##_##X* self, C##_##X##_iter_t pos) { \

         return C##_##X##_erase(self, keyToRaw(KEY_REF_##C(pos.ref))); \

     } \

@@ -312,20 +295,70 @@ int main(void) {
                            keyFromRaw, keyToRaw, RawKey, mappedFromRaw, mappedToRaw, RawMapped) \

     STC_DEF C##_##X \

     C##_##X##_init(void) { \

-        C##_##X m = {(C##_##X##_node_t *) &cbst_nil, 0}; \

+        C##_##X m = {(C##_##X##_node_t *) (_smap_inits + 4)}; \

         return m; \

     } \

 \

     STC_DEF C##_##X##_value_t* \

+    C##_##X##_front(C##_##X* self) { \

+        C##_##X##_node_t *d = self->data; \

+        C##_##X##_size_t tn = (C##_##X##_size_t) _smap_root(self); \

+        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##_size_t tn = (C##_##X##_size_t) _smap_root(self); \

+        while (d[tn].link[1]) tn = d[tn].link[1]; \

+        return &d[tn].value; \

+    } \

+\

+    STC_DEF void \

+    C##_##X##_reserve(C##_##X* self, size_t cap) { \

+        C##_##X##_size_t oldcap = _smap_cap(self); \

+        if (cap > oldcap) { \

+            size_t* rep = (size_t *) c_realloc(oldcap ? _smap_rep(self) : NULL, \

+                                               4*sizeof(size_t) + (cap + 1)*sizeof(C##_##X##_node_t)); \

+            if (oldcap == 0) \

+                memset(rep, 0, sizeof(size_t)*4 + sizeof(C##_##X##_node_t)); \

+            rep[_smap_CAP] = cap; \

+            self->data = (C##_##X##_node_t *) (rep + 4); \

+        } \

+    } \

+\

+    STC_DEF C##_##X##_size_t \

+    C##_##X##_node_new_(C##_##X* self) { \

+        size_t tn, *rep = _smap_rep(self); \

+        if (rep[_smap_DISP]) { \

+            tn = rep[_smap_DISP]; \

+            rep[_smap_DISP] = self->data[tn].link[1]; \

+        } else if ((tn = rep[_smap_SIZE] + 1) > rep[_smap_CAP]) \

+            C##_##X##_reserve(self, 4 + tn*3/2); \

+        C##_##X##_node_t* dn = &self->data[tn]; \

+        dn->link[0] = dn->link[1] = 0; dn->level = 1; \

+        return (C##_##X##_size_t) tn; \

+    } \

+\

+    STC_DEF void \

+    C##_##X##_node_del_(C##_##X##_node_t *d, C##_##X##_size_t tn) { \

+        size_t *rep = ((size_t *) d) - 4; \

+        keyDel(KEY_REF_##C(&d[tn].value)); \

+        d[tn].link[1] = (C##_##X##_size_t) rep[_smap_DISP]; d[tn].level = 0; \

+        rep[_smap_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##_node_t *tn = self->root; \

+        C##_##X##_size_t tn = _smap_root(self); \

+        C##_##X##_node_t *d = out->_d = self->data; \

         out->_top = 0; \

-        while (tn->level) { \

-            C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&tn->value)); \

+        if (tn) while (d[tn].level) { \

+            C##_##X##_rawkey_t rx = keyToRaw(KEY_REF_##C(&d[tn].value)); \

             switch (keyCompareRaw(&rx, &rkey)) { \

-                case -1: tn = tn->link[1]; break; \

-                case 1: out->_st[out->_top++] = tn; tn = tn->link[0]; break; \

-                case 0: out->ref = &tn->value; out->_tn = tn->link[1]; return out->ref; \

+                case -1: tn = d[tn].link[1]; break; \

+                case 1: out->_st[out->_top++] = tn; tn = d[tn].link[0]; break; \

+                case 0: out->_tn = d[tn].link[1]; return (out->ref = &d[tn].value); \

             } \

         } \

         return (out->ref = NULL); \

@@ -333,129 +366,166 @@ int main(void) {
 \

     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) { \

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

+        if (it->_top || it->_d[tn].level) { \

+            while (it->_d[tn].level) { \

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

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

+                tn = it->_d[tn].link[0]; \

             } \

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

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

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

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

+            it->ref = &it->_d[tn].value; \

         } else \

             it->ref = NULL; \

     } \

 \

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

+    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) { \

+            C##_##X##_size_t tmp = d[tn].link[0]; \

+            d[tn].link[0] = d[tmp].link[1]; \

+            d[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; \

+    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) { \

+            C##_##X##_size_t tmp = d[tn].link[1]; \

+            d[tn].link[1] = d[tmp].link[0]; \

+            d[tmp].link[0] = tn; \

             tn = tmp; \

-            ++tn->level; \

+            ++d[tn].level; \

         } \

         return tn; \

     } \

 \

-    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) { \

-            tn = c_new_1(C##_##X##_node_t); \

-            res->first = &tn->value, res->second = true; \

-            tn->link[0] = tn->link[1] = (C##_##X##_node_t*) &cbst_nil, tn->level = 1; \

-            *KEY_REF_##C(&tn->value) = keyFromRaw(*rkey); \

-            return tn; \

+    static inline C##_##X##_size_t \

+    C##_##X##_insert_key_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; \

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

+            dir = (c == -1); \

+            it = d[it].link[dir]; \

         } \

-        C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \

-        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##_skew_(tn); \

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

-        return tn; \

+        it = C##_##X##_node_new_(self); d = self->data; \

+        *KEY_REF_##C(&d[it].value) = keyFromRaw(*rkey); \

+        res->first = &d[it].value, res->second = true; \

+        if (top == 0) return it; \

+        d[up[top - 1]].link[dir] = it; \

+        while (top--) { \

+            if (top) dir = (d[up[top - 1]].link[1] == up[top]); \

+            up[top] = C##_##X##_skew_(d, up[top]); \

+            up[top] = C##_##X##_split_(d, up[top]); \

+            if (top) d[up[top - 1]].link[dir] = up[top]; \

+        } \

+        return up[0]; \

     } \

 \

     STC_DEF C##_##X##_result_t \

     C##_##X##_insert_key(C##_##X* self, RawKey rkey) { \

         C##_##X##_result_t res = {NULL, false}; \

-        self->root = C##_##X##_insert_key_r_(self->root, &rkey, &res); \

-        self->size += res.second; \

+        C##_##X##_size_t tn = C##_##X##_insert_key_i_(self, (C##_##X##_size_t) _smap_root(self), &rkey, &res); \

+        _smap_root(self) = tn; \

+        _smap_size(self) += res.second; \

         return res; \

     } \

 \

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

-    C##_##X##_erase_r_(C##_##X##_node_t *tn, const C##_##X##_rawkey_t* rkey, int *erased) { \

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

-            return tn; \

-        C##_##X##_rawkey_t r = keyToRaw(KEY_REF_##C(&tn->value)); \

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

         if (c != 0) \

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

+            d[tn].link[c == -1] = C##_##X##_erase_r_(d, d[tn].link[c == -1], rkey, erased); \

         else { \

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

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

-                while (h->link[1]->level) \

-                    h = h->link[1]; \

-                tn->value = h->value; \

-                r = keyToRaw(KEY_REF_##C(&tn->value)); \

-                tn->link[0] = C##_##X##_erase_r_(tn->link[0], &r, erased); \

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

             } else { \

-                C##_##X##_node_t *tmp = tn; \

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

-                C##_##X##_value_del(&tmp->value); \

-                free(tmp); \

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

                 *erased = 1; \

             } \

         } \

-        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##_skew_(tn); \

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

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

         } \

         return tn; \

     } \

 \

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

-    C##_##X##_clone_r_(C##_##X##_node_t *tn) { \

-        if (! tn->level) return tn; \

-        C##_##X##_node_t *cn = c_new_1(C##_##X##_node_t); \

-        cn->link[0] = C##_##X##_clone_r_(tn->link[0]); \

-        cn->link[1] = C##_##X##_clone_r_(tn->link[1]); \

-        cn->level = tn->level; \

-        cn->value = C##_##X##_value_clone(tn->value); \

+    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) _smap_root(self), &rkey, &erased); \

+        if (erased) {_smap_root(self) = root; --_smap_size(self);} \

+        return erased; \

+    } \

+\

+    static C##_##X##_size_t \

+    C##_##X##_clone_r_(C##_##X* self, const C##_##X##_node_t* src, C##_##X##_size_t tn) { \

+        if (tn == 0) return 0; \

+        C##_##X##_size_t cn = C##_##X##_node_new_(self); \

+        C##_##X##_node_t* d = self->data; \

+        d[cn].link[0] = C##_##X##_clone_r_(self, src, src[tn].link[0]); \

+        d[cn].link[1] = C##_##X##_clone_r_(self, src, src[tn].link[1]); \

+        d[cn].level = src[tn].level; \

+        d[cn].value = C##_##X##_value_clone(src[tn].value); \

         return cn; \

     } \

+    STC_DEF C##_##X \

+    C##_##X##_clone(C##_##X bst) { \

+        C##_##X clone = C##_##X##_with_capacity(_smap_size(&bst)); \

+        C##_##X##_size_t root = C##_##X##_clone_r_(&clone, bst.data, (C##_##X##_size_t) _smap_root(&bst)); \

+        _smap_root(&clone) = root; \

+        return clone; \

+    } \

 \

+    static void \

+    C##_##X##_del_r_(C##_##X##_node_t* d, C##_##X##_size_t tn) { \

+        if (tn) { \

+            C##_##X##_del_r_(d, d[tn].link[0]); \

+            C##_##X##_del_r_(d, d[tn].link[1]); \

+            C##_##X##_value_del(&d[tn].value); \

+        } \

+    } \

     STC_DEF void \

-    C##_##X##_del_r_(C##_##X##_node_t* tn) { \

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

-            C##_##X##_del_r_(tn->link[0]); \

-            C##_##X##_del_r_(tn->link[1]); \

-            C##_##X##_value_del(&tn->value); \

-            c_free(tn); \

+    C##_##X##_del(C##_##X* self) { \

+        if (_smap_root(self)) { \

+            C##_##X##_del_r_(self->data, (C##_##X##_size_t) _smap_root(self)); \

+            c_free(_smap_rep(self)); \

         } \

     }

 

-

 _using_CBST_types(_, csmap, int, int);

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

+static size_t _smap_inits[4] = {0, 0, 0, 0};

 

 #else

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

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

 #endif

 

+enum {_smap_ROOT=0, _smap_DISP=1, _smap_SIZE=2, _smap_CAP=3};

+#define _smap_rep(self) (((size_t *)(self)->data) - 4)

+#define _smap_root(self) _smap_rep(self)[_smap_ROOT]

+#define _smap_disp(self) _smap_rep(self)[_smap_DISP]

+#define _smap_size(self) _smap_rep(self)[_smap_SIZE]

+#define _smap_cap(self) _smap_rep(self)[_smap_CAP]

+

 #endif