From df0f4db2bb6ea55c0d45918e799b06a9970cec2b Mon Sep 17 00:00:00 2001
From: Tyge Løvset <tylo@norceresearch.no>
Date: Tue, 2 Feb 2021 18:18:12 +0100
Subject: Rewrote unordered map AA-tree csmap.h. Now uses array as memory pool
 instead of individual allocated nodes. 40% faster. V1 moved to examples.

---
 stc/crandom.h |  21 ++--
 stc/csmap.h   | 332 +++++++++++++++++++++++++++++++++++-----------------------
 2 files changed, 212 insertions(+), 141 deletions(-)

(limited to 'stc')

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 \
@@ -195,13 +203,6 @@ int main(void) {
         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); \
@@ -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
-- 
cgit v1.2.3