Added csmap.h and csset.h + test.

4 files changed, 491 insertions, 419 deletions

diff --git a/include/stc/csmap.h b/include/stc/csmap.h
index 3ea30083..5fa2063d 100644
--- a/include/stc/csmap.h
+++ b/include/stc/csmap.h
@@ -20,8 +20,6 @@
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

  * SOFTWARE.

  */

-#ifndef CSMAP_H_INCLUDED

-#define CSMAP_H_INCLUDED

 

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

 /*

@@ -46,429 +44,442 @@ int main(void) {
     }

 }

 */

+

+#ifndef CSMAP_H_INCLUDED

 #include "ccommon.h"

-#include "template.h"

+#include "forward.h"

 #include <stdlib.h>

 #include <string.h>

 

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

 struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; };

 #define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes)

+#endif // CSMAP_H_INCLUDED

 

-#if !defined cx_forwarded

-    _c_aatree_types(Self, C, i_key, i_val);

+#ifndef i_module

+#define i_module csmap

+#define cx_MAP_ONLY c_true

+#define cx_SET_ONLY c_false

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

 #endif

+#include "template.h"

 

-\

-    cx_MAP_ONLY( struct cx_value_t { \

-        cx_key_t first; \

-        cx_mapped_t second; \

-    }; ) \

-\

-    struct cx_node_t { \

-        cx_memb(_size_t) link[2]; \

-        int8_t level; \

-        cx_value_t value; \

-    }; \

-\

-    typedef i_keyraw cx_rawkey_t; \

-    typedef i_valraw cx_memb(_rawmapped_t); \

-    typedef cx_SET_ONLY( i_keyraw ) \

-            cx_MAP_ONLY( struct { i_keyraw first; \

-                                   i_valraw second; } ) \

-    cx_rawvalue_t; \

-\

-    STC_API Self               cx_memb(_init)(void); \

-    STC_API Self               cx_memb(_clone)(Self tree); \

-    STC_API void             cx_memb(_del)(Self* self); \

-    STC_API void             cx_memb(_reserve)(Self* self, size_t cap); \

-    STC_API cx_value_t*    cx_memb(_find_it)(const Self* self, i_keyraw rkey, cx_iter_t* out); \

-    STC_API cx_iter_t      cx_memb(_lower_bound)(const Self* self, i_keyraw rkey); \

-    STC_API cx_value_t*    cx_memb(_front)(const Self* self); \

-    STC_API cx_value_t*    cx_memb(_back)(const Self* self); \

-    STC_API int              cx_memb(_erase)(Self* self, i_keyraw rkey); \

-    STC_API cx_iter_t      cx_memb(_erase_at)(Self* self, cx_iter_t it); \

-    STC_API cx_iter_t      cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2); \

-    STC_API cx_result_t    cx_memb(_insert_entry_)(Self* self, i_keyraw rkey); \

-    STC_API void             cx_memb(_next)(cx_iter_t* it); \

-\

-    STC_INLINE bool          cx_memb(_empty)(Self tree) { return _csmap_rep(&tree)->size == 0; } \

-    STC_INLINE size_t        cx_memb(_size)(Self tree) { return _csmap_rep(&tree)->size; } \

-    STC_INLINE size_t        cx_memb(_capacity)(Self tree) { return _csmap_rep(&tree)->cap; } \

-    STC_INLINE void          cx_memb(_clear)(Self* self) { cx_memb(_del)(self); *self = cx_memb(_init)(); } \

-    STC_INLINE void          cx_memb(_swap)(Self* a, Self* b) {c_swap(Self, *a, *b); } \

-    STC_INLINE bool          cx_memb(_contains)(const Self* self, i_keyraw rkey) \

-                                {cx_iter_t it; return cx_memb(_find_it)(self, rkey, &it) != NULL; } \

-    STC_INLINE cx_value_t* cx_memb(_get)(const Self* self, i_keyraw rkey) \

-                                {cx_iter_t it; return cx_memb(_find_it)(self, rkey, &it); } \

-\

-    STC_INLINE Self \

-    cx_memb(_with_capacity)(size_t size) { \

-        Self tree = cx_memb(_init)(); \

-        cx_memb(_reserve)(&tree, size); \

-        return tree; \

-    } \

-\

-    STC_INLINE cx_rawvalue_t \

-    cx_memb(_value_toraw)(cx_value_t* val) { \

-        return cx_SET_ONLY( i_keyto(val) ) \

-               cx_MAP_ONLY( c_make(cx_rawvalue_t){i_keyto(&val->first), i_valto(&val->second)} ); \

-    } \

-    STC_INLINE void \

-    cx_memb(_value_del)(cx_value_t* val) { \

-        i_keydel(cx_keyref(val)); \

-        cx_MAP_ONLY( i_valdel(&val->second); ) \

-    } \

-    STC_INLINE void \

-    cx_memb(_value_clone)(cx_value_t* dst, cx_value_t* val) { \

-        *cx_keyref(dst) = i_keyfrom(i_keyto(cx_keyref(val))); \

-        cx_MAP_ONLY( dst->second = i_valfrom(i_valto(&val->second)); ) \

-    } \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_find)(const Self* self, i_keyraw rkey) { \

-        cx_iter_t it; \

-        cx_memb(_find_it)(self, rkey, &it); \

-        return it; \

-    } \

-\

-    STC_INLINE cx_result_t \

-    cx_memb(_emplace)(Self* self, i_keyraw rkey cx_MAP_ONLY(, i_valraw rmapped)) { \

-        cx_result_t res = cx_memb(_insert_entry_)(self, rkey); \

-        if (res.inserted) { \

-            *cx_keyref(res.ref) = i_keyfrom(rkey); \

-            cx_MAP_ONLY(res.ref->second = i_valfrom(rmapped);) \

-        } \

-        return res; \

-    } \

-\

-    STC_INLINE void \

-    cx_memb(_emplace_items)(Self* self, const cx_rawvalue_t arr[], size_t n) { \

-        for (size_t i=0; i<n; ++i) cx_SET_ONLY( cx_memb(_emplace)(self, arr[i]); ) \

-                                   cx_MAP_ONLY( cx_memb(_emplace)(self, arr[i].first, arr[i].second); ) \

-    } \

-\

-    STC_INLINE cx_result_t \

-    cx_memb(_insert)(Self* self, i_key key cx_MAP_ONLY(, i_val mapped)) { \

-        cx_result_t res = cx_memb(_insert_entry_)(self, i_keyto(&key)); \

-        if (res.inserted) {*cx_keyref(res.ref) = key; cx_MAP_ONLY( res.ref->second = mapped; )} \

-        else              {i_keydel(&key); cx_MAP_ONLY( i_valdel(&mapped); )} \

-        return res; \

-    } \

-\

-    cx_MAP_ONLY( \

-        STC_INLINE cx_result_t \

-        cx_memb(_insert_or_assign)(Self* self, i_key key, i_val mapped) { \

-            cx_result_t res = cx_memb(_insert_entry_)(self, i_keyto(&key)); \

-            if (res.inserted) res.ref->first = key; \

-            else {i_keydel(&key); i_valdel(&res.ref->second); } \

-            res.ref->second = mapped; return res; \

-        } \

-    \

-        STC_INLINE cx_result_t \

-        cx_memb(_put)(Self* self, i_key key, i_val mapped) { \

-            return cx_memb(_insert_or_assign)(self, key, mapped); \

-        } \

-    \

-        STC_INLINE cx_result_t \

-        cx_memb(_emplace_or_assign)(Self* self, i_keyraw rkey, i_valraw rmapped) { \

-            cx_result_t res = cx_memb(_insert_entry_)(self, rkey); \

-            if (res.inserted) res.ref->first = i_keyfrom(rkey); \

-            else i_valdel(&res.ref->second); \

-            res.ref->second = i_valfrom(rmapped); return res; \

-        } \

-    \

-        STC_INLINE cx_mapped_t* \

-        cx_memb(_at)(const Self* self, i_keyraw rkey) { \

-            cx_iter_t it; \

-            return &cx_memb(_find_it)(self, rkey, &it)->second; \

-        }) \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_begin)(const Self* self) { \

-        cx_iter_t it; it._d = self->nodes, it._top = 0; \

-        it._tn = (cx_memb(_size_t)) _csmap_rep(self)->root; \

-        if (it._tn) cx_memb(_next)(&it); \

-        return it; \

-    } \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_end)(const Self* self) {\

-        return c_make(cx_iter_t){.ref = NULL}; \

-    } \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_fwd)(cx_iter_t it, size_t n) { \

-        while (n-- && it.ref) cx_memb(_next)(&it); \

-        return it; \

-    } \

-\

-    _c_implement_aatree(Self, C, i_key, i_val, i_cmp, \

-                        i_valdel, i_valfrom, i_valto, i_valraw, \

-                        i_keydel, i_keyfrom, i_keyto, i_keyraw) \

-    struct stc_trailing_semicolon

+#ifndef i_fwd

+cx_deftypes(_c_aatree_types, Self, i_key, i_val, cx_MAP_ONLY, cx_SET_ONLY);

+#endif

+

+cx_MAP_ONLY( struct cx_value_t {

+    cx_key_t first;

+    cx_mapped_t second;

+}; )

+struct cx_node_t {

+    cx_memb(_size_t) link[2];

+    int8_t level;

+    cx_value_t value;

+};

+

+typedef i_keyraw cx_rawkey_t;

+typedef i_valraw cx_memb(_rawmapped_t);

+typedef cx_SET_ONLY( i_keyraw )

+        cx_MAP_ONLY( struct { i_keyraw first; i_valraw second; } )

+        cx_rawvalue_t;

+

+STC_API Self            cx_memb(_init)(void);

+STC_API Self            cx_memb(_clone)(Self tree);

+STC_API void            cx_memb(_del)(Self* self);

+STC_API void            cx_memb(_reserve)(Self* self, size_t cap);

+STC_API cx_value_t*     cx_memb(_find_it)(const Self* self, i_keyraw rkey, cx_iter_t* out);

+STC_API cx_iter_t       cx_memb(_lower_bound)(const Self* self, i_keyraw rkey);

+STC_API cx_value_t*     cx_memb(_front)(const Self* self);

+STC_API cx_value_t*     cx_memb(_back)(const Self* self);

+STC_API int             cx_memb(_erase)(Self* self, i_keyraw rkey);

+STC_API cx_iter_t       cx_memb(_erase_at)(Self* self, cx_iter_t it);

+STC_API cx_iter_t       cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2);

+STC_API cx_result_t     cx_memb(_insert_entry_)(Self* self, i_keyraw rkey);

+STC_API void            cx_memb(_next)(cx_iter_t* it);

+

+STC_INLINE bool         cx_memb(_empty)(Self tree) { return _csmap_rep(&tree)->size == 0; }

+STC_INLINE size_t       cx_memb(_size)(Self tree) { return _csmap_rep(&tree)->size; }

+STC_INLINE size_t       cx_memb(_capacity)(Self tree) { return _csmap_rep(&tree)->cap; }

+STC_INLINE void         cx_memb(_clear)(Self* self) { cx_memb(_del)(self); *self = cx_memb(_init)(); }

+STC_INLINE void         cx_memb(_swap)(Self* a, Self* b) { c_swap(Self, *a, *b); }

+STC_INLINE bool         cx_memb(_contains)(const Self* self, i_keyraw rkey)

+                            { cx_iter_t it; return cx_memb(_find_it)(self, rkey, &it) != NULL; }

+STC_INLINE cx_value_t*  cx_memb(_get)(const Self* self, i_keyraw rkey)

+                            { cx_iter_t it; return cx_memb(_find_it)(self, rkey, &it); }

+

+STC_INLINE Self

+cx_memb(_with_capacity)(size_t size) {

+    Self tree = cx_memb(_init)();

+    cx_memb(_reserve)(&tree, size);

+    return tree;

+}

+

+STC_INLINE cx_rawvalue_t

+cx_memb(_value_toraw)(cx_value_t* val) {

+    return cx_SET_ONLY( i_keyto(val) )

+           cx_MAP_ONLY( c_make(cx_rawvalue_t){i_keyto(&val->first), i_valto(&val->second)} );

+}

+

+STC_INLINE void

+cx_memb(_value_del)(cx_value_t* val) {

+    i_keydel(cx_keyref(val));

+    cx_MAP_ONLY( i_valdel(&val->second); )

+}

+

+STC_INLINE void

+cx_memb(_value_clone)(cx_value_t* dst, cx_value_t* val) {

+    *cx_keyref(dst) = i_keyfrom(i_keyto(cx_keyref(val)));

+    cx_MAP_ONLY( dst->second = i_valfrom(i_valto(&val->second)); )

+}

+

+cx_MAP_ONLY(

+    STC_API cx_result_t cx_memb(_insert_or_assign)(Self* self, i_key key, i_val mapped);

+    STC_API cx_result_t cx_memb(_emplace_or_assign)(Self* self, i_keyraw rkey, i_valraw rmapped);

+

+    STC_INLINE cx_result_t

+    cx_memb(_put)(Self* self, i_key key, i_val mapped)

+        { return cx_memb(_insert_or_assign)(self, key, mapped); }

+

+    STC_INLINE cx_mapped_t*

+    cx_memb(_at)(const Self* self, i_keyraw rkey)

+        { cx_iter_t it; return &cx_memb(_find_it)(self, rkey, &it)->second; }

+)

+

+STC_INLINE cx_iter_t

+cx_memb(_find)(const Self* self, i_keyraw rkey) {

+    cx_iter_t it;

+    cx_memb(_find_it)(self, rkey, &it);

+    return it;

+}

+

+STC_INLINE cx_result_t

+cx_memb(_emplace)(Self* self, i_keyraw rkey cx_MAP_ONLY(, i_valraw rmapped)) {

+    cx_result_t res = cx_memb(_insert_entry_)(self, rkey);

+    if (res.inserted) {

+        *cx_keyref(res.ref) = i_keyfrom(rkey);

+        cx_MAP_ONLY(res.ref->second = i_valfrom(rmapped);)

+    }

+    return res;

+}

+

+STC_INLINE void

+cx_memb(_emplace_items)(Self* self, const cx_rawvalue_t arr[], size_t n) {

+    for (size_t i=0; i<n; ++i) cx_SET_ONLY( cx_memb(_emplace)(self, arr[i]); )

+                               cx_MAP_ONLY( cx_memb(_emplace)(self, arr[i].first, arr[i].second); )

+}

+

+STC_INLINE cx_result_t

+cx_memb(_insert)(Self* self, i_key key cx_MAP_ONLY(, i_val mapped)) {

+    cx_result_t res = cx_memb(_insert_entry_)(self, i_keyto(&key));

+    if (res.inserted) { *cx_keyref(res.ref) = key; cx_MAP_ONLY( res.ref->second = mapped; )}

+    else              { i_keydel(&key); cx_MAP_ONLY( i_valdel(&mapped); )}

+    return res;

+}

+

+STC_INLINE cx_iter_t

+cx_memb(_begin)(const Self* self) {

+    cx_iter_t it; it._d = self->nodes, it._top = 0;

+    it._tn = (cx_memb(_size_t)) _csmap_rep(self)->root;

+    if (it._tn) cx_memb(_next)(&it);

+    return it;

+}

+

+STC_INLINE cx_iter_t

+cx_memb(_end)(const Self* self) {

+    return c_make(cx_iter_t){.ref = NULL};

+}

+

+STC_INLINE cx_iter_t

+cx_memb(_fwd)(cx_iter_t it, size_t n) {

+    while (n-- && it.ref) cx_memb(_next)(&it);

+    return it;

+}

 

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

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

 

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

+#ifndef CSMAP_H_INCLUDED

+#define CSMAP_H_INCLUDED

 static struct csmap_rep _csmap_sentinel = {0, 0, 0, 0, 0};

+#endif

+

+STC_DEF Self

+cx_memb(_init)(void) {

+    Self tree = {(cx_node_t *) _csmap_sentinel.nodes};

+    return tree;

+}

+

+STC_DEF cx_value_t*

+cx_memb(_front)(const Self* self) {

+    cx_node_t *d = self->nodes;

+    cx_memb(_size_t) tn = (cx_memb(_size_t)) _csmap_rep(self)->root;

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

+    return &d[tn].value;

+}

+

+STC_DEF cx_value_t*

+cx_memb(_back)(const Self* self) {

+    cx_node_t *d = self->nodes;

+    cx_memb(_size_t) tn = (cx_memb(_size_t)) _csmap_rep(self)->root;

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

+    return &d[tn].value;

+}

 

-#define _c_implement_aatree(Self, C, i_key, i_val, i_cmp, \

-                            i_valdel, i_valfrom, i_valto, i_valraw, \

-                            i_keydel, i_keyfrom, i_keyto, i_keyraw) \

-    STC_DEF Self \

-    cx_memb(_init)(void) { \

-        Self tree = {(cx_node_t *) _csmap_sentinel.nodes}; \

-        return tree; \

-    } \

-\

-    STC_DEF cx_value_t* \

-    cx_memb(_front)(const Self* self) { \

-        cx_node_t *d = self->nodes; \

-        cx_memb(_size_t) tn = (cx_memb(_size_t)) _csmap_rep(self)->root; \

-        while (d[tn].link[0]) tn = d[tn].link[0]; \

-        return &d[tn].value; \

-    } \

-\

-    STC_DEF cx_value_t* \

-    cx_memb(_back)(const Self* self) { \

-        cx_node_t *d = self->nodes; \

-        cx_memb(_size_t) tn = (cx_memb(_size_t)) _csmap_rep(self)->root; \

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

-        return &d[tn].value; \

-    } \

-\

-    STC_DEF void \

-    cx_memb(_reserve)(Self* self, size_t cap) { \

-        struct csmap_rep* rep = _csmap_rep(self); \

-        cx_memb(_size_t) oldcap = rep->cap; \

-        if (cap > oldcap) { \

-            rep = (struct csmap_rep*) c_realloc(oldcap ? rep : NULL, \

-                                                sizeof(struct csmap_rep) + (cap + 1)*sizeof(cx_node_t)); \

-            if (oldcap == 0) \

-                memset(rep, 0, sizeof(struct csmap_rep) + sizeof(cx_node_t)); \

-            rep->cap = cap; \

-            self->nodes = (cx_node_t *) rep->nodes; \

-        } \

-    } \

-\

-    STC_DEF cx_memb(_size_t) \

-    cx_memb(_node_new_)(Self* self, int level) { \

-        size_t tn; struct csmap_rep *rep = _csmap_rep(self); \

-        if (rep->disp) { \

-            tn = rep->disp; \

-            rep->disp = self->nodes[tn].link[1]; \

-        } else { \

-            if ((tn = rep->head + 1) > rep->cap) cx_memb(_reserve)(self, 4 + (tn*13 >> 3)); \

-            ++_csmap_rep(self)->head; /* do after reserve */ \

-        } \

-        cx_node_t* dn = &self->nodes[tn]; \

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

-        return (cx_memb(_size_t)) tn; \

-    } \

-\

-    STC_DEF cx_value_t* \

-    cx_memb(_find_it)(const Self* self, i_keyraw rkey, cx_iter_t* out) { \

-        cx_memb(_size_t) tn = _csmap_rep(self)->root; \

-        cx_node_t *d = out->_d = self->nodes; \

-        out->_top = 0; \

-        while (tn) { \

-            int c; cx_rawkey_t raw = i_keyto(cx_keyref(&d[tn].value)); \

-            if ((c = i_cmp(&raw, &rkey)) < 0) \

-                tn = d[tn].link[1]; \

-            else if (c > 0) \

-                { out->_st[out->_top++] = tn; tn = d[tn].link[0]; } \

-            else \

-                { out->_tn = d[tn].link[1]; return (out->ref = &d[tn].value); } \

-        } \

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

-    } \

-\

-    STC_DEF cx_iter_t \

-    cx_memb(_lower_bound)(const Self* self, i_keyraw rkey) { \

-        cx_iter_t it; \

-        cx_memb(_find_it)(self, rkey, &it); \

-        if (!it.ref && it._top) { \

-            cx_memb(_size_t) tn = it._st[--it._top]; \

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

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

-        } \

-        return it; \

-    } \

-\

-    STC_DEF void \

-    cx_memb(_next)(cx_iter_t *it) { \

-        cx_memb(_size_t) tn = it->_tn; \

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

-            while (tn) { \

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

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

-            } \

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

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

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

-        } else \

-            it->ref = NULL; \

-    } \

-\

-    static cx_memb(_size_t) \

-    cx_memb(_skew_)(cx_node_t *d, cx_memb(_size_t) tn) { \

-        if (tn && d[d[tn].link[0]].level == d[tn].level) { \

-            cx_memb(_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 cx_memb(_size_t) \

-    cx_memb(_split_)(cx_node_t *d, cx_memb(_size_t) tn) { \

-        if (d[d[d[tn].link[1]].link[1]].level == d[tn].level) { \

-            cx_memb(_size_t) tmp = d[tn].link[1]; \

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

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

-            tn = tmp; \

-            ++d[tn].level; \

-        } \

-        return tn; \

-    } \

-\

-    STC_DEF cx_memb(_size_t) \

-    cx_memb(_insert_entry_i_)(Self* self, cx_memb(_size_t) tn, const cx_rawkey_t* rkey, cx_result_t* res) { \

-        cx_memb(_size_t) up[64], tx = tn; \

-        cx_node_t* d = self->nodes; \

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

-        while (tx) { \

-            up[top++] = tx; \

-            i_keyraw raw = i_keyto(cx_keyref(&d[tx].value)); \

-            if ((c = i_cmp(&raw, rkey)) == 0) {res->ref = &d[tx].value; return tn; } \

-            dir = (c < 0); \

-            tx = d[tx].link[dir]; \

-        } \

-        tx = cx_memb(_node_new_)(self, 1); d = self->nodes; \

-        res->ref = &d[tx].value, res->inserted = true; \

-        if (top == 0) return tx; \

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

-        while (top--) { \

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

-            up[top] = cx_memb(_skew_)(d, up[top]); \

-            up[top] = cx_memb(_split_)(d, up[top]); \

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

-        } \

-        return up[0]; \

-    } \

-\

-    STC_DEF cx_result_t \

-    cx_memb(_insert_entry_)(Self* self, i_keyraw rkey) { \

-        cx_result_t res = {NULL, false}; \

-        cx_memb(_size_t) tn = cx_memb(_insert_entry_i_)(self, (cx_memb(_size_t)) _csmap_rep(self)->root, &rkey, &res); \

-        _csmap_rep(self)->root = tn; \

-        _csmap_rep(self)->size += res.inserted; \

-        return res; \

-    } \

-\

-    STC_DEF cx_memb(_size_t) \

-    cx_memb(_erase_r_)(cx_node_t *d, cx_memb(_size_t) tn, const cx_rawkey_t* rkey, int *erased) { \

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

-        i_keyraw raw = i_keyto(cx_keyref(&d[tn].value)); \

-        cx_memb(_size_t) tx; int c = i_cmp(&raw, rkey); \

-        if (c != 0) \

-            d[tn].link[c < 0] = cx_memb(_erase_r_)(d, d[tn].link[c < 0], rkey, erased); \

-        else { \

-            if (!(*erased)++) cx_memb(_value_del)(&d[tn].value); \

-            if (d[tn].link[0] && d[tn].link[1]) { \

-                tx = d[tn].link[0]; \

-                while (d[tx].link[1]) \

-                    tx = d[tx].link[1]; \

-                d[tn].value = d[tx].value; /* move */ \

-                raw = i_keyto(cx_keyref(&d[tn].value)); \

-                d[tn].link[0] = cx_memb(_erase_r_)(d, d[tn].link[0], &raw, erased); \

-            } else { /* unlink node */ \

-                tx = tn; \

-                tn = d[tn].link[ d[tn].link[0] == 0 ]; \

-                /* move it to disposed nodes list */ \

-                struct csmap_rep *rep = c_container_of(d, struct csmap_rep, nodes); \

-                d[tx].link[1] = (cx_memb(_size_t)) rep->disp; \

-                rep->disp = tx; \

-            } \

-        } \

-        tx = d[tn].link[1]; \

-        if (d[d[tn].link[0]].level < d[tn].level - 1 || d[tx].level < d[tn].level - 1) { \

-            if (d[tx].level > --d[tn].level) \

-                d[tx].level = d[tn].level; \

-                            tn = cx_memb(_skew_)(d, tn); \

-            tx = d[tn].link[1] = cx_memb(_skew_)(d, d[tn].link[1]); \

-                 d[tx].link[1] = cx_memb(_skew_)(d, d[tx].link[1]); \

-                            tn = cx_memb(_split_)(d, tn); \

-                 d[tn].link[1] = cx_memb(_split_)(d, d[tn].link[1]); \

-        } \

-        return tn; \

-    } \

-\

-    STC_DEF int \

-    cx_memb(_erase)(Self* self, i_keyraw rkey) { \

-        int erased = 0; \

-        cx_memb(_size_t) root = cx_memb(_erase_r_)(self->nodes, (cx_memb(_size_t)) _csmap_rep(self)->root, &rkey, &erased); \

-        return erased ? (_csmap_rep(self)->root = root, --_csmap_rep(self)->size, 1) : 0; \

-    } \

-\

-    STC_DEF cx_iter_t \

-    cx_memb(_erase_at)(Self* self, cx_iter_t it) { \

-        cx_rawkey_t raw = i_keyto(cx_keyref(it.ref)), nxt; \

-        cx_memb(_next)(&it); \

-        if (it.ref) nxt = i_keyto(cx_keyref(it.ref)); \

-        cx_memb(_erase)(self, raw); \

-        if (it.ref) cx_memb(_find_it)(self, nxt, &it); \

-        return it; \

-    } \

-\

-    STC_DEF cx_iter_t \

-    cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2) { \

-        if (!it2.ref) { while (it1.ref) it1 = cx_memb(_erase_at)(self, it1); \

-                        return it1; } \

-        cx_key_t k1 = *cx_keyref(it1.ref), k2 = *cx_keyref(it2.ref); \

-        cx_rawkey_t r1 = i_keyto(&k1); \

-        for (;;) { \

-            if (memcmp(&k1, &k2, sizeof k1) == 0) return it1; \

-            cx_memb(_next)(&it1); k1 = *cx_keyref(it1.ref); \

-            cx_memb(_erase)(self, r1); \

-            cx_memb(_find_it)(self, (r1 = i_keyto(&k1)), &it1); \

-        } \

-    } \

-\

-    static cx_memb(_size_t) \

-    cx_memb(_clone_r_)(Self* self, cx_node_t* src, cx_memb(_size_t) sn) { \

-        if (sn == 0) return 0; \

-        cx_memb(_size_t) tx, tn = cx_memb(_node_new_)(self, src[sn].level); \

-        cx_memb(_value_clone)(&self->nodes[tn].value, &src[sn].value); \

-        tx = cx_memb(_clone_r_)(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx; \

-        tx = cx_memb(_clone_r_)(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx; \

-        return tn; \

-    } \

-    STC_DEF Self \

-    cx_memb(_clone)(Self tree) { \

-        Self clone = cx_memb(_with_capacity)(_csmap_rep(&tree)->size); \

-        cx_memb(_size_t) root = cx_memb(_clone_r_)(&clone, tree.nodes, (cx_memb(_size_t)) _csmap_rep(&tree)->root); \

-        _csmap_rep(&clone)->root = root; \

-        _csmap_rep(&clone)->size = _csmap_rep(&tree)->size; \

-        return clone; \

-    } \

-\

-    STC_DEF void \

-    cx_memb(_del_r_)(cx_node_t* d, cx_memb(_size_t) tn) { \

-        if (tn) { \

-            cx_memb(_del_r_)(d, d[tn].link[0]); \

-            cx_memb(_del_r_)(d, d[tn].link[1]); \

-            cx_memb(_value_del)(&d[tn].value); \

-        } \

-    } \

-    STC_DEF void \

-    cx_memb(_del)(Self* self) { \

-        if (_csmap_rep(self)->root) { \

-            cx_memb(_del_r_)(self->nodes, (cx_memb(_size_t)) _csmap_rep(self)->root); \

-            c_free(_csmap_rep(self)); \

-        } \

+STC_DEF void

+cx_memb(_reserve)(Self* self, size_t cap) {

+    struct csmap_rep* rep = _csmap_rep(self);

+    cx_memb(_size_t) oldcap = rep->cap;

+    if (cap > oldcap) {

+        rep = (struct csmap_rep*) c_realloc(oldcap ? rep : NULL,

+                                            sizeof(struct csmap_rep) + (cap + 1)*sizeof(cx_node_t));

+        if (oldcap == 0)

+            memset(rep, 0, sizeof(struct csmap_rep) + sizeof(cx_node_t));

+        rep->cap = cap;

+        self->nodes = (cx_node_t *) rep->nodes;

     }

+}

 

-#endif

-#endif

+STC_DEF cx_memb(_size_t)

+cx_memb(_node_new_)(Self* self, int level) {

+    size_t tn; struct csmap_rep *rep = _csmap_rep(self);

+    if (rep->disp) {

+        tn = rep->disp;

+        rep->disp = self->nodes[tn].link[1];

+    } else {

+        if ((tn = rep->head + 1) > rep->cap) cx_memb(_reserve)(self, 4 + (tn*13 >> 3));

+        ++_csmap_rep(self)->head; /* do after reserve */

+    }

+    cx_node_t* dn = &self->nodes[tn];

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

+    return (cx_memb(_size_t)) tn;

+}

+

+cx_MAP_ONLY(

+    STC_DEF cx_result_t

+    cx_memb(_insert_or_assign)(Self* self, i_key key, i_val mapped) {

+        cx_result_t res = cx_memb(_insert_entry_)(self, i_keyto(&key));

+        if (res.inserted) res.ref->first = key;

+        else {i_keydel(&key); i_valdel(&res.ref->second); }

+        res.ref->second = mapped; return res;

+    }

+

+    STC_DEF cx_result_t

+    cx_memb(_emplace_or_assign)(Self* self, i_keyraw rkey, i_valraw rmapped) {

+        cx_result_t res = cx_memb(_insert_entry_)(self, rkey);

+        if (res.inserted) res.ref->first = i_keyfrom(rkey);

+        else i_valdel(&res.ref->second);

+        res.ref->second = i_valfrom(rmapped); return res;

+    }

+)

+

+STC_DEF cx_value_t*

+cx_memb(_find_it)(const Self* self, i_keyraw rkey, cx_iter_t* out) {

+    cx_memb(_size_t) tn = _csmap_rep(self)->root;

+    cx_node_t *d = out->_d = self->nodes;

+    out->_top = 0;

+    while (tn) {

+        int c; cx_rawkey_t raw = i_keyto(cx_keyref(&d[tn].value));

+        if ((c = i_cmp(&raw, &rkey)) < 0)

+            tn = d[tn].link[1];

+        else if (c > 0)

+            { out->_st[out->_top++] = tn; tn = d[tn].link[0]; }

+        else

+            { out->_tn = d[tn].link[1]; return (out->ref = &d[tn].value); }

+    }

+    return (out->ref = NULL);

+}

+

+STC_DEF cx_iter_t

+cx_memb(_lower_bound)(const Self* self, i_keyraw rkey) {

+    cx_iter_t it;

+    cx_memb(_find_it)(self, rkey, &it);

+    if (!it.ref && it._top) {

+        cx_memb(_size_t) tn = it._st[--it._top];

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

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

+    }

+    return it;

+}

+

+STC_DEF void

+cx_memb(_next)(cx_iter_t *it) {

+    cx_memb(_size_t) tn = it->_tn;

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

+        while (tn) {

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

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

+        }

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

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

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

+    } else

+        it->ref = NULL;

+}

+

+static cx_memb(_size_t)

+cx_memb(_skew_)(cx_node_t *d, cx_memb(_size_t) tn) {

+    if (tn && d[d[tn].link[0]].level == d[tn].level) {

+        cx_memb(_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 cx_memb(_size_t)

+cx_memb(_split_)(cx_node_t *d, cx_memb(_size_t) tn) {

+    if (d[d[d[tn].link[1]].link[1]].level == d[tn].level) {

+        cx_memb(_size_t) tmp = d[tn].link[1];

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

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

+        tn = tmp;

+        ++d[tn].level;

+    }

+    return tn;

+}

+

+STC_DEF cx_memb(_size_t)

+cx_memb(_insert_entry_i_)(Self* self, cx_memb(_size_t) tn, const cx_rawkey_t* rkey, cx_result_t* res) {

+    cx_memb(_size_t) up[64], tx = tn;

+    cx_node_t* d = self->nodes;

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

+    while (tx) {

+        up[top++] = tx;

+        i_keyraw raw = i_keyto(cx_keyref(&d[tx].value));

+        if ((c = i_cmp(&raw, rkey)) == 0) {res->ref = &d[tx].value; return tn; }

+        dir = (c < 0);

+        tx = d[tx].link[dir];

+    }

+    tx = cx_memb(_node_new_)(self, 1); d = self->nodes;

+    res->ref = &d[tx].value, res->inserted = true;

+    if (top == 0) return tx;

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

+    while (top--) {

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

+        up[top] = cx_memb(_skew_)(d, up[top]);

+        up[top] = cx_memb(_split_)(d, up[top]);

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

+    }

+    return up[0];

+}

+

+STC_DEF cx_result_t

+cx_memb(_insert_entry_)(Self* self, i_keyraw rkey) {

+    cx_result_t res = {NULL, false};

+    cx_memb(_size_t) tn = cx_memb(_insert_entry_i_)(self, (cx_memb(_size_t)) _csmap_rep(self)->root, &rkey, &res);

+    _csmap_rep(self)->root = tn;

+    _csmap_rep(self)->size += res.inserted;

+    return res;

+}

+

+STC_DEF cx_memb(_size_t)

+cx_memb(_erase_r_)(cx_node_t *d, cx_memb(_size_t) tn, const cx_rawkey_t* rkey, int *erased) {

+    if (tn == 0) return 0;

+    i_keyraw raw = i_keyto(cx_keyref(&d[tn].value));

+    cx_memb(_size_t) tx; int c = i_cmp(&raw, rkey);

+    if (c != 0)

+        d[tn].link[c < 0] = cx_memb(_erase_r_)(d, d[tn].link[c < 0], rkey, erased);

+    else {

+        if (!(*erased)++) cx_memb(_value_del)(&d[tn].value);

+        if (d[tn].link[0] && d[tn].link[1]) {

+            tx = d[tn].link[0];

+            while (d[tx].link[1])

+                tx = d[tx].link[1];

+            d[tn].value = d[tx].value; /* move */

+            raw = i_keyto(cx_keyref(&d[tn].value));

+            d[tn].link[0] = cx_memb(_erase_r_)(d, d[tn].link[0], &raw, erased);

+        } else { /* unlink node */

+            tx = tn;

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

+            /* move it to disposed nodes list */

+            struct csmap_rep *rep = c_container_of(d, struct csmap_rep, nodes);

+            d[tx].link[1] = (cx_memb(_size_t)) rep->disp;

+            rep->disp = tx;

+        }

+    }

+    tx = d[tn].link[1];

+    if (d[d[tn].link[0]].level < d[tn].level - 1 || d[tx].level < d[tn].level - 1) {

+        if (d[tx].level > --d[tn].level)

+            d[tx].level = d[tn].level;

+                        tn = cx_memb(_skew_)(d, tn);

+        tx = d[tn].link[1] = cx_memb(_skew_)(d, d[tn].link[1]);

+                d[tx].link[1] = cx_memb(_skew_)(d, d[tx].link[1]);

+                        tn = cx_memb(_split_)(d, tn);

+                d[tn].link[1] = cx_memb(_split_)(d, d[tn].link[1]);

+    }

+    return tn;

+}

+

+STC_DEF int

+cx_memb(_erase)(Self* self, i_keyraw rkey) {

+    int erased = 0;

+    cx_memb(_size_t) root = cx_memb(_erase_r_)(self->nodes, (cx_memb(_size_t)) _csmap_rep(self)->root, &rkey, &erased);

+    return erased ? (_csmap_rep(self)->root = root, --_csmap_rep(self)->size, 1) : 0;

+}

+

+STC_DEF cx_iter_t

+cx_memb(_erase_at)(Self* self, cx_iter_t it) {

+    cx_rawkey_t raw = i_keyto(cx_keyref(it.ref)), nxt;

+    cx_memb(_next)(&it);

+    if (it.ref) nxt = i_keyto(cx_keyref(it.ref));

+    cx_memb(_erase)(self, raw);

+    if (it.ref) cx_memb(_find_it)(self, nxt, &it);

+    return it;

+}

+

+STC_DEF cx_iter_t

+cx_memb(_erase_range)(Self* self, cx_iter_t it1, cx_iter_t it2) {

+    if (!it2.ref) { while (it1.ref) it1 = cx_memb(_erase_at)(self, it1);

+                    return it1; }

+    cx_key_t k1 = *cx_keyref(it1.ref), k2 = *cx_keyref(it2.ref);

+    cx_rawkey_t r1 = i_keyto(&k1);

+    for (;;) {

+        if (memcmp(&k1, &k2, sizeof k1) == 0) return it1;

+        cx_memb(_next)(&it1); k1 = *cx_keyref(it1.ref);

+        cx_memb(_erase)(self, r1);

+        cx_memb(_find_it)(self, (r1 = i_keyto(&k1)), &it1);

+    }

+}

+

+static cx_memb(_size_t)

+cx_memb(_clone_r_)(Self* self, cx_node_t* src, cx_memb(_size_t) sn) {

+    if (sn == 0) return 0;

+    cx_memb(_size_t) tx, tn = cx_memb(_node_new_)(self, src[sn].level);

+    cx_memb(_value_clone)(&self->nodes[tn].value, &src[sn].value);

+    tx = cx_memb(_clone_r_)(self, src, src[sn].link[0]); self->nodes[tn].link[0] = tx;

+    tx = cx_memb(_clone_r_)(self, src, src[sn].link[1]); self->nodes[tn].link[1] = tx;

+    return tn;

+}

+

+STC_DEF Self

+cx_memb(_clone)(Self tree) {

+    Self clone = cx_memb(_with_capacity)(_csmap_rep(&tree)->size);

+    cx_memb(_size_t) root = cx_memb(_clone_r_)(&clone, tree.nodes, (cx_memb(_size_t)) _csmap_rep(&tree)->root);

+    _csmap_rep(&clone)->root = root;

+    _csmap_rep(&clone)->size = _csmap_rep(&tree)->size;

+    return clone;

+}

+

+STC_DEF void

+cx_memb(_del_r_)(cx_node_t* d, cx_memb(_size_t) tn) {

+    if (tn) {

+        cx_memb(_del_r_)(d, d[tn].link[0]);

+        cx_memb(_del_r_)(d, d[tn].link[1]);

+        cx_memb(_value_del)(&d[tn].value);

+    }

+}

+

+STC_DEF void

+cx_memb(_del)(Self* self) {

+    if (_csmap_rep(self)->root) {

+        cx_memb(_del_r_)(self->nodes, (cx_memb(_size_t)) _csmap_rep(self)->root);

+        c_free(_csmap_rep(self));

+    }

+}

+

+#endif // IMPLEMENTATION

+#undef cx_keyref

+#undef cx_MAP_ONLY

+#undef cx_SET_ONLY

+#include "template.h"

diff --git a/include/stc/csset.h b/include/stc/csset.h
index f275cbfd..f2378095 100644
--- a/include/stc/csset.h
+++ b/include/stc/csset.h
@@ -20,8 +20,6 @@
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

  * SOFTWARE.

  */

-#ifndef CSSET_H_INCLUDED

-#define CSSET_H_INCLUDED

 

 // Sorted set - implemented as an AA-tree (balanced binary tree).

 /*

@@ -43,8 +41,8 @@ int main(void) {
 }

 */

 

-#define i_cnt csset

-#define KEY_REF_csset(vp)   (vp)

+#define i_module csset

+#define cx_MAP_ONLY c_false

+#define cx_SET_ONLY c_true

+#define cx_keyref(vp) (vp)

 #include "csmap.h"

-

-#endif

diff --git a/include/stc/test_new_map.c b/include/stc/test_new_map.c
index 3a40a501..25240ee3 100644
--- a/include/stc/test_new_map.c
+++ b/include/stc/test_new_map.c
@@ -8,11 +8,12 @@ struct MyStruct {
     cstr name;

 } typedef MyStruct;

 

-

+// int => int map

 #define i_key int

 #define i_val int

 #include <stc/cmap.h>

 

+// Point => int map

 struct Point { int x, y; } typedef Point;

 int point_compare(const Point* a, const Point* b) {

     int c = c_default_compare(&a->x, &b->x);

@@ -24,10 +25,12 @@ int point_compare(const Point* a, const Point* b) {
 #define i_cmp point_compare

 #include <stc/cmap.h>

 

+// int => int map

 #define i_key_str

 #define i_val_str

 #include <stc/cmap.h>

 

+// string set

 #define i_key_str

 #include <stc/cset.h>

 

diff --git a/include/stc/test_new_smap.c b/include/stc/test_new_smap.c
new file mode 100644
index 00000000..c2e68d0e
--- /dev/null
+++ b/include/stc/test_new_smap.c
@@ -0,0 +1,60 @@
+#include <stc/cstr.h>

+#include <stc/forward.h>

+

+forward_csmap(pnt, struct Point, int);

+

+struct MyStruct {

+    csmap_pnt pntmap;

+    cstr name;

+} typedef MyStruct;

+

+// int => int map

+#define i_key int

+#define i_val int

+#include <stc/csmap.h>

+

+// Point => int map

+struct Point { int x, y; } typedef Point;

+int point_compare(const Point* a, const Point* b) {

+    int c = c_default_compare(&a->x, &b->x);

+    return c ? c : c_default_compare(&a->y, &b->y);

+}

+#define f_tag pnt  // f=forward declared

+#define i_key Point

+#define i_val int

+#define i_cmp point_compare

+#include <stc/csmap.h>

+

+// int => int map

+#define i_key_str

+#define i_val_str

+#include <stc/csmap.h>

+

+// string set

+#define i_key_str

+#include <stc/csset.h>

+

+

+int main()

+{

+    csmap_int map = csmap_int_init();

+    csmap_int_insert(&map, 123, 321);

+    csmap_int_del(&map);

+

+    csmap_pnt pmap = csmap_pnt_init();

+    csmap_pnt_insert(&pmap, (Point){42, 14}, 1);

+    csmap_pnt_insert(&pmap, (Point){32, 94}, 2);

+    csmap_pnt_insert(&pmap, (Point){62, 81}, 3);

+    c_foreach (i, csmap_pnt, pmap)

+        printf(" (%d,%d: %d)", i.ref->first.x, i.ref->first.y, i.ref->second);

+    puts("");

+    csmap_pnt_del(&pmap);

+

+    csmap_str smap = csmap_str_init();

+    csmap_str_emplace(&smap, "Hello, friend", "this is the mapped value");

+    csmap_str_del(&smap);

+

+    csset_str sset = csset_str_init();

+    csset_str_emplace(&sset, "Hello, friend");

+    csset_str_del(&sset);

+}
\ No newline at end of file