Rewrote to use c_container_of() instead of size_t offset.

7 files changed, 159 insertions, 181 deletions

diff --git a/benchmarks/cmap_benchmark2.cpp b/benchmarks/cmap_benchmark2.cpp
index be8a47a6..4d6db980 100644
--- a/benchmarks/cmap_benchmark2.cpp
+++ b/benchmarks/cmap_benchmark2.cpp
@@ -228,7 +228,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_cmap_s(picobench::state& s)

diff --git a/stc/ccommon.h b/stc/ccommon.h
index bea528bc..acf6e1e6 100644
--- a/stc/ccommon.h
+++ b/stc/ccommon.h
@@ -61,9 +61,9 @@
 #define _c_OVERLOAD_SELECT(NAME, NUM) _c_CAT( NAME ## _, NUM)

 

 #define c_MACRO_OVERLOAD(NAME, ...) _c_OVERLOAD_SELECT(NAME, _c_VA_ARG_SIZE(__VA_ARGS__))(__VA_ARGS__)

-#define c_static_assert(cond, msg) typedef char static_assert_##msg[(cond) ? 1 : -1]

+#define c_static_assert(cond) typedef char _static_assert_[(cond) ? 1 : -1]

 #define c_container_of(ptr, type, member) \

-                                ((type *)((char *)(ptr) - offsetof(type, member)))

+        ((type *)((char *)(ptr) - offsetof(type, member)))

 

 #define c_new(...)              c_MACRO_OVERLOAD(c_new, __VA_ARGS__)

 #define c_new_1(T)              ((T *) c_malloc(sizeof(T)))

diff --git a/stc/cdeq.h b/stc/cdeq.h
index 2ce7d398..8cce8188 100644
--- a/stc/cdeq.h
+++ b/stc/cdeq.h
@@ -45,17 +45,20 @@
         cdeq_##X##_value_t *base, *data; \

     } cdeq_##X

 

+struct cdeq_rep { size_t size, cap; void* base[]; };

+#define _cdeq_rep(self) c_container_of((self)->base, struct cdeq_rep, base)

+

 #define using_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

     typedefs_cdeq(X, Value, RawValue); \

 \

     STC_API cdeq_##X \

     cdeq_##X##_init(void); \

     STC_INLINE bool \

-    cdeq_##X##_empty(cdeq_##X deq) {return !_cdeq_size(&deq);} \

+    cdeq_##X##_empty(cdeq_##X deq) {return !_cdeq_rep(&deq)->size;} \

     STC_INLINE size_t \

-    cdeq_##X##_size(cdeq_##X deq) {return _cdeq_size(&deq);} \

+    cdeq_##X##_size(cdeq_##X deq) {return _cdeq_rep(&deq)->size;} \

     STC_INLINE size_t \

-    cdeq_##X##_capacity(cdeq_##X deq) {return _cdeq_cap(&deq);} \

+    cdeq_##X##_capacity(cdeq_##X deq) {return _cdeq_rep(&deq)->cap;} \

     STC_INLINE Value \

     cdeq_##X##_value_from_raw(RawValue raw) {return valueFromRaw(raw);} \

     STC_INLINE cdeq_##X##_value_t \

@@ -102,7 +105,7 @@
     } \

     STC_INLINE void \

     cdeq_##X##_pop_back(cdeq_##X* self) { \

-        valueDestroy(&self->data[--_cdeq_size(self)]); \

+        valueDestroy(&self->data[--_cdeq_rep(self)->size]); \

     } \

 \

     STC_API void \

@@ -114,7 +117,7 @@
     STC_INLINE void \

     cdeq_##X##_pop_front(cdeq_##X* self) { \

         valueDestroy(self->data++); \

-        --_cdeq_size(self); \

+        --_cdeq_rep(self)->size; \

     } \

 \

     STC_API cdeq_##X##_iter_t \

@@ -165,10 +168,10 @@
     STC_INLINE cdeq_##X##_value_t* \

     cdeq_##X##_front(cdeq_##X* self) {return self->data;} \

     STC_INLINE cdeq_##X##_value_t* \

-    cdeq_##X##_back(cdeq_##X* self) {return self->data + _cdeq_size(self) - 1;} \

+    cdeq_##X##_back(cdeq_##X* self) {return self->data + _cdeq_rep(self)->size - 1;} \

     STC_INLINE cdeq_##X##_value_t* \

     cdeq_##X##_at(cdeq_##X* self, size_t i) { \

-        assert(i < _cdeq_size(self)); \

+        assert(i < _cdeq_rep(self)->size); \

         return self->data + i; \

     } \

 \

@@ -180,7 +183,7 @@
     } \

     STC_INLINE void \

     cdeq_##X##_sort(cdeq_##X* self) { \

-        cdeq_##X##_sort_with(self, 0, _cdeq_size(self), cdeq_##X##_value_compare); \

+        cdeq_##X##_sort_with(self, 0, _cdeq_rep(self)->size, cdeq_##X##_value_compare); \

     } \

 \

     STC_INLINE cdeq_##X##_iter_t \

@@ -189,7 +192,7 @@
     } \

     STC_INLINE cdeq_##X##_iter_t \

     cdeq_##X##_end(const cdeq_##X* self) { \

-        cdeq_##X##_iter_t it = {self->data + _cdeq_size(self)}; return it; \

+        cdeq_##X##_iter_t it = {self->data + _cdeq_rep(self)->size}; return it; \

     } \

     STC_INLINE void \

     cdeq_##X##_next(cdeq_##X##_iter_t* it) {++it->ref;} \

@@ -204,66 +207,73 @@
 /* -------------------------- IMPLEMENTATION ------------------------- */

 

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

+

+static struct cdeq_rep _cdeq_inits = {0, 0};

+#define              _cdeq_nfront(self) ((self)->data - (self)->base)

+static inline double _minf(double x, double y) {return x < y ? x : y;}

+static inline double _maxf(double x, double y) {return x > y ? x : y;}

+

 #define _c_implement_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

 \

     STC_DEF cdeq_##X \

     cdeq_##X##_init(void) { \

-        cdeq_##X##_value_t *t = (cdeq_##X##_value_t *) (_cdeq_inits + 2); \

-        cdeq_##X deq = {t, t}; return deq; \

+        cdeq_##X##_value_t *b = (cdeq_##X##_value_t *) _cdeq_inits.base; \

+        cdeq_##X deq = {b, b}; return deq; \

     } \

 \

     STC_DEF void \

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

         _cdeq_##X##_expand(self, n, false); \

-        cdeq_##X##_value_t* p = self->data + _cdeq_size(self); \

+        cdeq_##X##_value_t* p = self->data + _cdeq_rep(self)->size; \

         for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \

-        _cdeq_size(self) += n; \

+        _cdeq_rep(self)->size += n; \

     } \

 \

     STC_DEF void \

     cdeq_##X##_clear(cdeq_##X* self) { \

         cdeq_##X##_value_t* p = self->data; if (p) { \

-            for (cdeq_##X##_value_t* q = p + _cdeq_size(self); p != q; ++p) \

+            for (cdeq_##X##_value_t* q = p + _cdeq_rep(self)->size; p != q; ++p) \

                 valueDestroy(p); \

-            _cdeq_size(self) = 0; \

+            _cdeq_rep(self)->size = 0; \

         } \

     } \

     STC_DEF void \

     cdeq_##X##_del(cdeq_##X* self) { \

         cdeq_##X##_clear(self); \

-        if (_cdeq_alloced(self) != _cdeq_inits) \

-            c_free(_cdeq_alloced(self)); \

+        if (_cdeq_rep(self)->cap) \

+            c_free(_cdeq_rep(self)); \

     } \

 \

     STC_DEF void \

     _cdeq_##X##_expand(cdeq_##X* self, size_t n, bool at_front) { \

-        size_t len = _cdeq_size(self), cap = _cdeq_cap(self); \

+        struct cdeq_rep* rep = _cdeq_rep(self); \

+        size_t len = rep->size, cap = rep->cap; \

         size_t nfront = self->data - self->base, nback = cap - (nfront + len); \

         if (at_front && nfront >= n || !at_front && nback >= n) \

             return; \

         if ((len + n)*1.3 > cap) { \

             cap = (len + n + 6)*1.8; \

-            size_t* rep = (size_t *) c_realloc(_cdeq_alloced(self) != _cdeq_inits ? _cdeq_alloced(self) : NULL, \

-                                               2*sizeof(size_t) + cap*sizeof(Value)); \

-            rep[0] = len, rep[1] = cap; \

-            self->base = (cdeq_##X##_value_t *) (rep + 2); \

+            rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL, \

+                                               sizeof(struct cdeq_rep) + cap*sizeof(Value)); \

+            rep->size = len, rep->cap = cap; \

+            self->base = (cdeq_##X##_value_t *) rep->base; \

             self->data = self->base + nfront; \

             _cdeq_##X##_expand(self, n, at_front); \

             return; \

         } \

         size_t unused = cap - (len + n); \

-        size_t pos = at_front ? c_maxf(unused*0.5, (float) unused - nback) + n \

-                              : c_minf(unused*0.5, nfront); \

+        size_t pos = at_front ? _maxf(unused*0.5, (float) unused - nback) + n \

+                              : _minf(unused*0.5, nfront); \

         self->data = (cdeq_##X##_value_t *) memmove(self->base + pos, self->data, len*sizeof(Value)); \

     } \

 \

     STC_DEF void \

     cdeq_##X##_resize(cdeq_##X* self, size_t size, Value null_val) { \

         _cdeq_##X##_expand(self, size, false); \

-        size_t i, n = _cdeq_size(self); \

+        size_t i, n = _cdeq_rep(self)->size; \

         for (i=size; i<n; ++i) valueDestroy(self->data + i); \

         for (i=n; i<size; ++i) self->data[i] = null_val; \

-        if (self->data) _cdeq_size(self) = size; \

+        if (self->data) _cdeq_rep(self)->size = size; \

     } \

 \

     STC_DEF void \

@@ -271,18 +281,18 @@
         if (self->data == self->base) \

             _cdeq_##X##_expand(self, 1, true); \

         *--self->data = value; \

-        ++_cdeq_size(self); \

+        ++_cdeq_rep(self)->size; \

     } \

     STC_DEF void \

     cdeq_##X##_push_back(cdeq_##X* self, Value value) { \

-        if (_cdeq_nfront(self) + _cdeq_size(self) == _cdeq_cap(self)) \

+        if (_cdeq_nfront(self) + _cdeq_rep(self)->size == _cdeq_rep(self)->cap) \

             _cdeq_##X##_expand(self, 1, false); \

-        self->data[_cdeq_size(self)++] = value; \

+        self->data[_cdeq_rep(self)->size++] = value; \

     } \

 \

     STC_DEF cdeq_##X \

     cdeq_##X##_clone(cdeq_##X vec) { \

-        size_t len = _cdeq_size(&vec); \

+        size_t len = _cdeq_rep(&vec)->size; \

         cdeq_##X out = cdeq_##X##_with_capacity(len); \

         cdeq_##X##_insert_range_p(&out, out.data, vec.data, vec.data + len); \

         return out; \

@@ -291,7 +301,7 @@
     STC_DEF cdeq_##X##_iter_t \

     cdeq_##X##_insert_range_p(cdeq_##X* self, cdeq_##X##_value_t* pos, \

                               const cdeq_##X##_value_t* first, const cdeq_##X##_value_t* finish) { \

-        size_t n = finish - first, idx = pos - self->data, size = _cdeq_size(self); \

+        size_t n = finish - first, idx = pos - self->data, size = _cdeq_rep(self)->size; \

         bool at_front = (idx < size/2); \

         _cdeq_##X##_expand(self, n, at_front); \

         if (at_front) { \

@@ -302,7 +312,7 @@
             memmove(pos + n, pos, (size - idx)*sizeof(Value)); \

         } \

         cdeq_##X##_iter_t it = {pos}; \

-        if (n) _cdeq_size(self) += n; \

+        if (n) _cdeq_rep(self)->size += n; \

         while (first != finish) \

             *pos++ = valueFromRaw(valueToRaw(first++)); \

         return it; \

@@ -312,11 +322,11 @@
     cdeq_##X##_erase_range_p(cdeq_##X* self, cdeq_##X##_value_t* first, cdeq_##X##_value_t* finish) { \

         intptr_t len = finish - first; \

         if (len > 0) { \

-            cdeq_##X##_value_t* p = first, *end = self->data + _cdeq_size(self); \

+            cdeq_##X##_value_t* p = first, *end = self->data + _cdeq_rep(self)->size; \

             while (p != finish) valueDestroy(p++); \

             if (first == self->data) self->data += len; \

             else memmove(first, finish, (end - finish) * sizeof(Value)); \

-            _cdeq_size(self) -= len; \

+            _cdeq_rep(self)->size -= len; \

         } \

         cdeq_##X##_iter_t it = {first}; return it; \

     } \

@@ -341,9 +351,6 @@
         return valueCompareRaw(&rx, &ry); \

     }

 

-static size_t _cdeq_inits[2] = {0, 0};

-#define _cdeq_alloced(self) (((size_t *) (self)->base) - 2)

-

 #else

 #define _c_implement_cdeq_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue)

 #endif

@@ -357,11 +364,4 @@ static size_t _cdeq_inits[2] = {0, 0};
 typedef int(*_cdeq_cmp)(const void*, const void*);

 STC_EXTERN_IMPORT void qsort(void *start, size_t nitems, size_t size, _cdeq_cmp cmp);

 

-#define _cdeq_size(self)      ((size_t *) (self)->base)[-2]

-#define _cdeq_cap(self)       ((size_t *) (self)->base)[-1]

-#define _cdeq_nfront(self)    ((self)->data - (self)->base)

-

-static inline double c_minf(double x, double y) { return x < y ? x : y; }

-static inline double c_maxf(double x, double y) { return x > y ? x : y; }

-

 #endif

diff --git a/stc/cmap.h b/stc/cmap.h
index 888718d4..5123dd2b 100644
--- a/stc/cmap.h
+++ b/stc/cmap.h
@@ -56,12 +56,6 @@ int main(void) {
 #include <string.h>

 

 #define _cmap_inits   {NULL, NULL, 0, 0, 0.15f, 0.85f}

-

-/* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */

-#define chash_reduce(x, N)            ((uint32_t) (((uint64_t) (x) * (N)) >> 32))

-#define chash_entry_index(h, entryPtr) ((entryPtr) - (h).table)

-

-enum {chash_HASH = 0x7f, chash_USED = 0x80};

 typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t;

 

 #define using_cmap(...) \

@@ -313,6 +307,11 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t;
 /* -------------------------- IMPLEMENTATION ------------------------- */

 

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

+

+#define chash_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32))

+#define chash_entry_index(h, entryPtr) ((entryPtr) - (h).table)

+enum {chash_HASH = 0x7f, chash_USED = 0x80};

+

 #define _implement_CHASH(X, C, Key, Mapped, keyEqualsRaw, keyHashRaw, mappedDel, keyDel, \

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

     STC_DEF C##_##X \

@@ -447,8 +446,6 @@ typedef struct {size_t idx; uint32_t hx;} cmap_bucket_t, cset_bucket_t;
             C##_##X##_reserve(self, k*1.2); \

     }

 

-/* https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ */

-

 STC_DEF uint32_t c_default_hash(const void *data, size_t len) {

     const volatile uint16_t *key = (const uint16_t *) data;

     uint64_t x = *key++ * 11400714819323198485llu;

diff --git a/stc/csmap.h b/stc/csmap.h
index 3755e2ca..ac51589c 100644
--- a/stc/csmap.h
+++ b/stc/csmap.h
@@ -150,6 +150,9 @@ int main(void) {
         C##_##X##_size_t _tn, _st[48]; \

     } C##_##X##_iter_t

 

+struct csmap_rep { size_t root, disp, size, cap; void* data[]; };

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

+

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

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

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

@@ -182,9 +185,9 @@ int main(void) {
         return x; \

     } \

     STC_INLINE bool \

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

+    C##_##X##_empty(C##_##X m) {return _csmap_rep(&m)->size == 0;} \

     STC_INLINE size_t \

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

+    C##_##X##_size(C##_##X m) {return _csmap_rep(&m)->size;} \

     STC_API void \

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

     STC_INLINE void \

@@ -267,7 +270,7 @@ int main(void) {
 \

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

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

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

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

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

         return it; \

     } \

@@ -293,49 +296,52 @@ int main(void) {
 /* -------------------------- IMPLEMENTATION ------------------------- */

 

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

+static struct csmap_rep _smap_inits = {0, 0, 0, 0};

+

 #define _implement_AATREE(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 *) (_smap_inits + 4)}; \

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

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

+        C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \

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

+        C##_##X##_size_t tn = (C##_##X##_size_t) _csmap_rep(self)->root; \

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

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

+        C##_##X##_size_t oldcap = rep->cap; \

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

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

+                                                sizeof(struct csmap_rep) + (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); \

+                memset(rep, 0, sizeof(struct csmap_rep) + sizeof(C##_##X##_node_t)); \

+            rep->cap = cap; \

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

         } \

     } \

 \

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

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

+        if (rep->disp) { \

+            tn = rep->disp; \

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

+        } else if ((tn = rep->size + 1) > rep->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; \

@@ -344,15 +350,15 @@ int main(void) {
 \

     STC_DEF void \

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

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

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

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

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

-        rep[_smap_DISP] = tn; \

+        d[tn].link[1] = (C##_##X##_size_t) rep->disp; \

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

+        C##_##X##_size_t tn = _csmap_rep(self)->root; \

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

         out->_top = 0; \

         while (tn) { \

@@ -432,9 +438,9 @@ int main(void) {
     STC_DEF C##_##X##_result_t \

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

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

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

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

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

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

         return res; \

     } \

 \

@@ -476,8 +482,8 @@ int main(void) {
     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);} \

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

+        if (erased) {_csmap_rep(self)->root = root; --_csmap_rep(self)->size;} \

         return erased; \

     } \

 \

@@ -494,9 +500,9 @@ int main(void) {
     } \

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

+        C##_##X clone = C##_##X##_with_capacity(_csmap_rep(&bst)->size); \

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

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

         return clone; \

     } \

 \

@@ -510,25 +516,15 @@ int main(void) {
     } \

     STC_DEF void \

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

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

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

+            c_free(_csmap_rep(self)); \

         } \

     }

 

-_using_AATREE_types(_, csmap, int, int);

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

-

 #else

 #define _implement_AATREE(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

diff --git a/stc/cstr.h b/stc/cstr.h
index 2a49bbda..369d6034 100644
--- a/stc/cstr.h
+++ b/stc/cstr.h
@@ -35,43 +35,26 @@ typedef struct { char *ref; } cstr_iter_t;
 typedef char cstr_value_t;

 #define cstr_npos ((size_t) (-1))

 

+STC_API cstr_t  cstr_from_n(const char* str, size_t len);

+STC_API cstr_t  cstr_from_fmt(const char* fmt, ...);

+STC_API void    cstr_fmt(cstr_t* self, const char* fmt, ...);

+STC_API size_t  cstr_reserve(cstr_t* self, size_t cap);

+STC_API void    cstr_resize(cstr_t* self, size_t len, char fill);

+STC_API cstr_t* cstr_assign_n(cstr_t* self, const char* str, size_t len);

+STC_API cstr_t* cstr_append_n(cstr_t* self, const char* str, size_t len);

+STC_API void    cstr_replace_n(cstr_t* self, size_t pos, size_t len, const char* str, size_t n);

+STC_API void    cstr_erase_n(cstr_t* self, size_t pos, size_t n);

+STC_API bool    cstr_getdelim(cstr_t *self, int delim, FILE *stream);

+STC_API size_t  cstr_find(cstr_t s, const char* needle);

+STC_API size_t  cstr_find_n(cstr_t s, const char* needle, size_t pos, size_t nlen);

+STC_API size_t  cstr_ifind_n(cstr_t s, const char* needle, size_t pos, size_t nlen);

+

+STC_API int     c_strncasecmp(const char* s1, const char* s2, size_t n);

+STC_API char*   c_strnfind(const char* s, const char* needle, size_t nmax);

+STC_DEF char*   c_istrnfind(const char* s, const char* needle, size_t nmax);

+

 struct cstr_rep { size_t size, cap; char str[sizeof(size_t)]; };

 #define _cstr_rep(self) c_container_of((self)->str, struct cstr_rep, str)

-

-STC_API cstr_t

-cstr_from_n(const char* str, size_t len);

-STC_API cstr_t

-cstr_from_fmt(const char* fmt, ...);

-STC_API void

-cstr_fmt(cstr_t* self, const char* fmt, ...);

-STC_API size_t

-cstr_reserve(cstr_t* self, size_t cap);

-STC_API void

-cstr_resize(cstr_t* self, size_t len, char fill);

-STC_API cstr_t*

-cstr_assign_n(cstr_t* self, const char* str, size_t len);

-STC_API cstr_t*

-cstr_append_n(cstr_t* self, const char* str, size_t len);

-STC_API void

-cstr_replace_n(cstr_t* self, size_t pos, size_t len, const char* str, size_t n);

-STC_API void

-cstr_erase_n(cstr_t* self, size_t pos, size_t n);

-STC_API bool

-cstr_getdelim(cstr_t *self, int delim, FILE *stream);

-STC_API size_t

-cstr_find(cstr_t s, const char* needle);

-STC_API size_t

-cstr_find_n(cstr_t s, const char* needle, size_t pos, size_t nlen);

-STC_API size_t

-cstr_ifind_n(cstr_t s, const char* needle, size_t pos, size_t nlen);

-

-STC_API int

-c_strncasecmp(const char* s1, const char* s2, size_t n);

-STC_API char*

-c_strnfind(const char* s, const char* needle, size_t nmax);

-STC_DEF char*

-c_istrnfind(const char* s, const char* needle, size_t nmax);

-

 /* optimal memory: based on malloc_usable_size() sequence: 24, 40, 56, ... */

 #define _cstr_opt_mem(cap)  ((((offsetof(struct cstr_rep, str) + (cap) + 8)>>4)<<4) + 8)

 /* optimal string capacity: 7, 23, 39, ... */

@@ -106,12 +89,10 @@ STC_INLINE cstr_t
 cstr_from(const char* str) {

     return cstr_from_n(str, strlen(str));

 }

-

 STC_INLINE cstr_t

 cstr_clone(cstr_t s) {

     return cstr_from_n(s.str, _cstr_rep(&s)->size);

 }

-

 STC_INLINE void

 cstr_clear(cstr_t* self) {

     self->str[_cstr_rep(self)->size = 0] = '\0';

@@ -158,7 +139,6 @@ STC_INLINE void
 cstr_push_back(cstr_t* self, char value) {

     cstr_append_n(self, &value, 1);

 }

-

 STC_INLINE void

 cstr_pop_back(cstr_t* self) {

     self->str[ --_cstr_rep(self)->size ] = '\0';

@@ -186,10 +166,14 @@ cstr_getline(cstr_t *self, FILE *stream) {
 

 /* readonly */

 

-STC_INLINE size_t cstr_size(cstr_t s) {return _cstr_rep(&s)->size;}

-STC_INLINE size_t cstr_capacity(cstr_t s) {return _cstr_rep(&s)->cap;}

-STC_INLINE size_t cstr_empty(cstr_t s) {return _cstr_rep(&s)->size == 0;}

-STC_INLINE size_t cstr_length(cstr_t s) { return _cstr_rep(&s)->size; }

+STC_INLINE size_t 

+cstr_size(cstr_t s) {return _cstr_rep(&s)->size;}

+STC_INLINE size_t

+cstr_capacity(cstr_t s) {return _cstr_rep(&s)->cap;}

+STC_INLINE size_t

+cstr_empty(cstr_t s) {return _cstr_rep(&s)->size == 0;}

+STC_INLINE size_t

+cstr_length(cstr_t s) { return _cstr_rep(&s)->size; }

 

 STC_INLINE bool

 cstr_equals(cstr_t s1, const char* str) {

@@ -258,7 +242,7 @@ uint32_t cstr_hash_raw(const char* const* p, size_t none) {
 

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

 

-STC_LIBRARY_ONLY( struct cstr_rep _cstr_nullrep = {0, 0, {0}};

+STC_LIBRARY_ONLY( static struct cstr_rep _cstr_nullrep = {0, 0, {0}};

                   const cstr_t cstr_inits = {_cstr_nullrep.str}; )

 

 STC_DEF size_t

diff --git a/stc/cvec.h b/stc/cvec.h
index edfd77e9..77ed6c09 100644
--- a/stc/cvec.h
+++ b/stc/cvec.h
@@ -44,6 +44,9 @@
     typedef struct { \

         cvec_##X##_value_t* data; \

     } cvec_##X

+    

+struct cvec_rep { size_t size, cap; void* data[]; };

+#define _cvec_rep(self) c_container_of((self)->data, struct cvec_rep, data)

 

 #define using_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

     typedefs_cvec(X, Value, RawValue); \

@@ -51,11 +54,11 @@
     STC_API cvec_##X \

     cvec_##X##_init(void); \

     STC_INLINE size_t \

-    cvec_##X##_size(cvec_##X vec) { return _cvec_size(&vec); } \

+    cvec_##X##_size(cvec_##X vec) { return _cvec_rep(&vec)->size; } \

     STC_INLINE size_t \

-    cvec_##X##_capacity(cvec_##X vec) { return _cvec_cap(&vec); } \

+    cvec_##X##_capacity(cvec_##X vec) { return _cvec_rep(&vec)->cap; } \

     STC_INLINE bool \

-    cvec_##X##_empty(cvec_##X vec) {return !_cvec_size(&vec);} \

+    cvec_##X##_empty(cvec_##X vec) {return !_cvec_rep(&vec)->size;} \

     STC_INLINE Value \

     cvec_##X##_value_from_raw(RawValue raw) {return valueFromRaw(raw);} \

     STC_INLINE cvec_##X##_value_t \

@@ -101,7 +104,7 @@
     } \

     STC_INLINE void \

     cvec_##X##_pop_back(cvec_##X* self) { \

-        valueDestroy(&self->data[--_cvec_size(self)]); \

+        valueDestroy(&self->data[--_cvec_rep(self)->size]); \

     } \

 \

     STC_API cvec_##X##_iter_t \

@@ -152,10 +155,10 @@
     STC_INLINE cvec_##X##_value_t* \

     cvec_##X##_front(cvec_##X* self) {return self->data;} \

     STC_INLINE cvec_##X##_value_t* \

-    cvec_##X##_back(cvec_##X* self) {return self->data + _cvec_size(self) - 1;} \

+    cvec_##X##_back(cvec_##X* self) {return self->data + _cvec_rep(self)->size - 1;} \

     STC_INLINE cvec_##X##_value_t* \

      cvec_##X##_at(cvec_##X* self, size_t i) { \

-        assert(i < _cvec_size(self)); \

+        assert(i < _cvec_rep(self)->size); \

         return self->data + i; \

     } \

 \

@@ -167,7 +170,7 @@
     } \

     STC_INLINE void \

     cvec_##X##_sort(cvec_##X* self) { \

-        cvec_##X##_sort_with(self, 0, _cvec_size(self), cvec_##X##_value_compare); \

+        cvec_##X##_sort_with(self, 0, _cvec_rep(self)->size, cvec_##X##_value_compare); \

     } \

 \

     STC_INLINE cvec_##X##_iter_t \

@@ -176,7 +179,7 @@
     } \

     STC_INLINE cvec_##X##_iter_t \

     cvec_##X##_end(const cvec_##X* self) { \

-        cvec_##X##_iter_t it = {self->data + _cvec_size(self)}; return it; \

+        cvec_##X##_iter_t it = {self->data + _cvec_rep(self)->size}; return it; \

     } \

     STC_INLINE void \

     cvec_##X##_next(cvec_##X##_iter_t* it) {++it->ref;} \

@@ -191,66 +194,70 @@
 /* -------------------------- IMPLEMENTATION ------------------------- */

 

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

+static struct cvec_rep _cvec_inits = {0, 0};

+

 #define _c_implement_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue) \

 \

     STC_DEF cvec_##X \

     cvec_##X##_init(void) { \

-        cvec_##X vec = {(cvec_##X##_value_t *) (_cvec_inits + 2)}; return vec; \

+        cvec_##X vec = {(cvec_##X##_value_t *) _cvec_inits.data}; return vec; \

     } \

 \

     STC_DEF void \

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

-        cvec_##X##_reserve(self, _cvec_size(self) + n); \

-        cvec_##X##_value_t* p = self->data + _cvec_size(self); \

+        cvec_##X##_reserve(self, _cvec_rep(self)->size + n); \

+        cvec_##X##_value_t* p = self->data + _cvec_rep(self)->size; \

         for (size_t i=0; i < n; ++i) *p++ = valueFromRaw(arr[i]); \

-        _cvec_size(self) += n; \

+        _cvec_rep(self)->size += n; \

     } \

 \

     STC_DEF void \

     cvec_##X##_clear(cvec_##X* self) { \

         cvec_##X##_value_t* p = self->data; if (p) { \

-            for (cvec_##X##_value_t* q = p + _cvec_size(self); p != q; ++p) valueDestroy(p); \

-            _cvec_size(self) = 0; \

+            for (cvec_##X##_value_t* q = p + _cvec_rep(self)->size; p != q; ++p) valueDestroy(p); \

+            _cvec_rep(self)->size = 0; \

         } \

     } \

     STC_DEF void \

     cvec_##X##_del(cvec_##X* self) { \

         cvec_##X##_clear(self); \

-        if (_cvec_rep(self) != _cvec_inits) \

+        if (_cvec_rep(self)->cap) \

             c_free(_cvec_rep(self)); \

     } \

 \

     STC_DEF void \

     cvec_##X##_reserve(cvec_##X* self, size_t cap) { \

-        size_t len = _cvec_size(self); \

-        if (cap > _cvec_cap(self)) { \

-            size_t* rep = (size_t *) c_realloc(_cvec_rep(self) != _cvec_inits ? _cvec_rep(self) : NULL, \

-                                               2*sizeof(size_t) + cap*sizeof(Value)); \

-            self->data = (cvec_##X##_value_t*) (rep + 2); \

-            rep[0] = len; \

-            rep[1] = cap; \

+        struct cvec_rep* rep = _cvec_rep(self); \

+        size_t len = rep->size, oldcap = rep->cap; \

+        if (cap > oldcap) { \

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

+                                               sizeof(struct cvec_rep) + cap*sizeof(Value)); \

+            self->data = (cvec_##X##_value_t*) rep->data; \

+            rep->size = len; \

+            rep->cap = cap; \

         } \

     } \

     STC_DEF void \

-    cvec_##X##_resize(cvec_##X* self, size_t size, Value null_val) { \

-        cvec_##X##_reserve(self, size); \

-        size_t i, n = _cvec_size(self); \

-        for (i=size; i<n; ++i) valueDestroy(self->data + i); \

-        for (i=n; i<size; ++i) self->data[i] = null_val; \

-        if (self->data) _cvec_size(self) = size; \

+    cvec_##X##_resize(cvec_##X* self, size_t len, Value null_val) { \

+        cvec_##X##_reserve(self, len); \

+        struct cvec_rep* rep = _cvec_rep(self); \

+        size_t i, n = rep->size; \

+        for (i = len; i < n; ++i) valueDestroy(self->data + i); \

+        for (i = n; i < len; ++i) self->data[i] = null_val; \

+        if (rep->cap) rep->size = len; \

     } \

 \

     STC_DEF void \

     cvec_##X##_push_back(cvec_##X* self, Value value) { \

-        size_t len = _cvec_size(self); \

+        size_t len = _cvec_rep(self)->size; \

         if (len == cvec_##X##_capacity(*self)) \

             cvec_##X##_reserve(self, 4 + len*3/2); \

-        self->data[_cvec_size(self)++] = value; \

+        self->data[_cvec_rep(self)->size++] = value; \

     } \

 \

     STC_DEF cvec_##X \

     cvec_##X##_clone(cvec_##X vec) { \

-        size_t len = _cvec_size(&vec); \

+        size_t len = _cvec_rep(&vec)->size; \

         cvec_##X out = cvec_##X##_with_capacity(len); \

         cvec_##X##_insert_range_p(&out, out.data, vec.data, vec.data + len); \

         return out; \

@@ -258,13 +265,13 @@
 \

     STC_DEF cvec_##X##_iter_t \

     cvec_##X##_insert_range_p(cvec_##X* self, cvec_##X##_value_t* pos, const cvec_##X##_value_t* first, const cvec_##X##_value_t* finish) { \

-        size_t len = finish - first, idx = pos - self->data, size = _cvec_size(self); \

+        size_t len = finish - first, idx = pos - self->data, size = _cvec_rep(self)->size; \

         cvec_##X##_iter_t it = {pos}; \

         if (len == 0) return it; \

         if (size + len > cvec_##X##_capacity(*self)) \

             cvec_##X##_reserve(self, 4 + (size + len)*3/2), \

             it.ref = pos = self->data + idx; \

-        _cvec_size(self) += len; \

+        _cvec_rep(self)->size += len; \

         memmove(pos + len, pos, (size - idx) * sizeof(Value)); \

         while (first != finish) \

             *pos++ = valueFromRaw(valueToRaw(first++)); \

@@ -275,10 +282,10 @@
     cvec_##X##_erase_range_p(cvec_##X* self, cvec_##X##_value_t* first, cvec_##X##_value_t* finish) { \

         intptr_t len = finish - first; \

         if (len > 0) { \

-            cvec_##X##_value_t* p = first, *end = self->data + _cvec_size(self); \

+            cvec_##X##_value_t* p = first, *end = self->data + _cvec_rep(self)->size; \

             while (p != finish) valueDestroy(p++); \

             memmove(first, finish, (end - finish) * sizeof(Value)); \

-            _cvec_size(self) -= len; \

+            _cvec_rep(self)->size -= len; \

         } \

         cvec_##X##_iter_t it = {first}; return it; \

     } \

@@ -303,9 +310,6 @@
         return valueCompareRaw(&rx, &ry); \

     }

 

-static size_t _cvec_inits[2] = {0, 0};

-#define _cvec_rep(self) (((size_t *) (self)->data) - 2)

-

 #else

 #define _c_implement_cvec_7(X, Value, valueCompareRaw, valueDestroy, valueFromRaw, valueToRaw, RawValue)

 #endif

@@ -315,10 +319,7 @@ static size_t _cvec_inits[2] = {0, 0};
 #else

 #define STC_EXTERN_IMPORT extern

 #endif

-

 typedef int(*_cvec_cmp)(const void*, const void*);

 STC_EXTERN_IMPORT void qsort(void *base, size_t nitems, size_t size, _cvec_cmp cmp);

-#define _cvec_size(self) ((size_t *) (self)->data)[-2]

-#define _cvec_cap(self) ((size_t *) (self)->data)[-1]

 

 #endif