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

2 files changed, 212 insertions, 141 deletions

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