Added cdeq.h + test. Unsure if the rest should be kept as oldstyle (using).

5 files changed, 406 insertions, 339 deletions

diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h
index 65e2cd0d..b941d6c5 100644
--- a/include/stc/cdeq.h
+++ b/include/stc/cdeq.h
@@ -20,317 +20,319 @@
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

  * SOFTWARE.

  */

-#ifndef CDEQ_H_INCLUDED

-#define CDEQ_H_INCLUDED

 

+#ifndef CDEQ_H_INCLUDED

 #include "ccommon.h"

+#include "forward.h"

 #include <stdlib.h>

 #include <string.h>

 

-\

-    defTypes( _c_cdeq_types(Self, i_val); ) \

-    typedef i_valraw cx_rawvalue_t; \

-\

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

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

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

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

-    STC_API cx_iter_t      cx_memb(_find_in)(cx_iter_t p1, cx_iter_t p2, i_valraw raw); \

-    STC_API int              cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y); \

-    STC_API void             cx_memb(_push_back)(Self* self, i_val value); \

-    STC_API void             cx_memb(_push_front)(Self* self, i_val value); \

-    STC_API cx_iter_t      cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2); \

-    STC_API cx_iter_t      cx_memb(_insert_range_p)(Self* self, cx_value_t* pos, \

-                                                 const cx_value_t* p1, const cx_value_t* p2, bool clone); \

-    STC_API cx_iter_t      cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos, \

-                                             const cx_rawvalue_t* p1, const cx_rawvalue_t* p2); \

-    STC_API void             cx_memb(_expand_right_)(Self* self, size_t idx, size_t n); \

-\

-    STC_INLINE bool          cx_memb(_empty)(Self cx) { return !_cdeq_rep(&cx)->size; } \

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

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

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

-    STC_INLINE i_val         cx_memb(_value_fromraw)(i_valraw raw) { return i_valfrom(raw); } \

-    STC_INLINE i_valraw      cx_memb(_value_toraw)(cx_value_t* pval) { return i_valto(pval); } \

-    STC_INLINE i_val         cx_memb(_value_clone)(i_val val) \

-                                { return i_valfrom(i_valto(&val)); } \

-    STC_INLINE void          cx_memb(_emplace_back)(Self* self, i_valraw raw) \

-                                { cx_memb(_push_back)(self, i_valfrom(raw)); } \

-    STC_INLINE void          cx_memb(_emplace_front)(Self* self, i_valraw raw) \

-                                { cx_memb(_push_front)(self, i_valfrom(raw)); } \

-    STC_INLINE void          cx_memb(_pop_back)(Self* self) \

-                                {i_valdel(&self->data[--_cdeq_rep(self)->size]); } \

-    STC_INLINE void          cx_memb(_pop_front)(Self* self) \

-                                {i_valdel(self->data++); --_cdeq_rep(self)->size; } \

-    STC_INLINE cx_value_t* cx_memb(_front)(const Self* self) { return self->data; } \

-    STC_INLINE cx_value_t* cx_memb(_back)(const Self* self) \

-                                { return self->data + _cdeq_rep(self)->size - 1; } \

-    STC_INLINE cx_value_t* cx_memb(_at)(const Self* self, size_t idx) \

-                                {assert(idx < _cdeq_rep(self)->size); return self->data + idx; } \

-    STC_INLINE cx_iter_t   cx_memb(_begin)(const Self* self) \

-                                { return c_make(cx_iter_t){self->data}; } \

-    STC_INLINE cx_iter_t   cx_memb(_end)(const Self* self) \

-                                { return c_make(cx_iter_t){self->data + _cdeq_rep(self)->size}; } \

-    STC_INLINE void          cx_memb(_next)(cx_iter_t* it) {++it->ref; } \

-    STC_INLINE cx_iter_t   cx_memb(_adv)(cx_iter_t it, intptr_t offs) {it.ref += offs; return it; } \

-    STC_INLINE size_t        cx_memb(_idx)(Self cx, cx_iter_t it) { return it.ref - cx.data; } \

-\

-    STC_INLINE Self \

-    cx_memb(_with_capacity)(size_t n) { \

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

-        cx_memb(_expand_right_)(&cx, 0, n); \

-        return cx; \

-    } \

-\

-    STC_INLINE void \

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

-        size_t sz = _cdeq_rep(self)->size; \

-        if (n > sz) cx_memb(_expand_right_)(self, sz, n - sz); \

-    } \

-\

-    STC_INLINE void \

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

-        Self cx = cx_memb(_clone)(*self); \

-        cx_memb(_del)(self); *self = cx; \

-    } \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_insert)(Self* self, size_t idx, i_val value) { \

-        return cx_memb(_insert_range_p)(self, self->data + idx, &value, &value + 1, false); \

-    } \

-    STC_INLINE cx_iter_t \

-    cx_memb(_insert_n)(Self* self, size_t idx, const cx_value_t arr[], size_t n) { \

-        return cx_memb(_insert_range_p)(self, self->data + idx, arr, arr + n, false); \

-    } \

-    STC_INLINE cx_iter_t \

-    cx_memb(_insert_at)(Self* self, cx_iter_t it, i_val value) { \

-        return cx_memb(_insert_range_p)(self, it.ref, &value, &value + 1, false); \

-    } \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_emplace)(Self* self, size_t idx, i_valraw raw) { \

-        return cx_memb(_emplace_range_p)(self, self->data + idx, &raw, &raw + 1); \

-    } \

-    STC_INLINE cx_iter_t \

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

-        return cx_memb(_emplace_range_p)(self, self->data + idx, arr, arr + n); \

-    } \

-    STC_INLINE cx_iter_t \

-    cx_memb(_emplace_at)(Self* self, cx_iter_t it, i_valraw raw) { \

-        return cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1); \

-    } \

-    STC_INLINE cx_iter_t \

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

-        return cx_memb(_insert_range_p)(self, it.ref, it1.ref, it2.ref, true); \

-    } \

-    STC_INLINE void \

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

-        cx_memb(_emplace_range_p)(self, self->data + _cdeq_rep(self)->size, arr, arr + n); \

-    } \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_erase)(Self* self, size_t idx) { \

-        return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + 1); \

-    } \

-    STC_INLINE cx_iter_t \

-    cx_memb(_erase_n)(Self* self, size_t idx, size_t n) { \

-        return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + n); \

-    } \

-    STC_INLINE cx_iter_t \

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

-        return cx_memb(_erase_range_p)(self, it.ref, it.ref + 1); \

-    } \

-    STC_INLINE cx_iter_t \

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

-        return cx_memb(_erase_range_p)(self, it1.ref, it2.ref); \

-    } \

-\

-    STC_INLINE cx_iter_t \

-    cx_memb(_find)(const Self* self, i_valraw raw) { \

-        return cx_memb(_find_in)(cx_memb(_begin)(self), cx_memb(_end)(self), raw); \

-    } \

-\

-    STC_INLINE cx_value_t* \

-    cx_memb(_get)(const Self* self, i_valraw raw) { \

-        cx_iter_t end = cx_memb(_end)(self); \

-        cx_value_t* val = cx_memb(_find_in)(cx_memb(_begin)(self), end, raw).ref; \

-        return val == end.ref ? NULL : val; \

-    } \

-\

-    STC_INLINE void \

-    cx_memb(_sort_range)(cx_iter_t i1, cx_iter_t i2, \

-                    int(*_cmp_)(const cx_value_t*, const cx_value_t*)) { \

-        qsort(i1.ref, i2.ref - i1.ref, sizeof *i1.ref, (int(*)(const void*, const void*)) _cmp_); \

-    } \

-\

-    STC_INLINE void \

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

-        cx_memb(_sort_range)(cx_memb(_begin)(self), cx_memb(_end)(self), cx_memb(_value_compare)); \

-    } \

-\

-    _c_implement_cdeq(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw) \

-    struct stc_trailing_semicolon

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

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

+#endif // CDEQ_H_INCLUDED

 

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

+#define i_module cdeq

+#include "template.h"

+

+#if !defined i_fwd

+   cx_deftypes(_c_cdeq_types, Self, i_val);

+#endif

+typedef i_valraw cx_rawvalue_t;

+

+STC_API Self            cx_memb(_init)(void);

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

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

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

+STC_API cx_iter_t       cx_memb(_find_in)(cx_iter_t p1, cx_iter_t p2, i_valraw raw);

+STC_API int             cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y);

+STC_API void            cx_memb(_push_back)(Self* self, i_val value);

+STC_API void            cx_memb(_push_front)(Self* self, i_val value);

+STC_API cx_iter_t       cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2);

+STC_API cx_iter_t       cx_memb(_insert_range_p)(Self* self, cx_value_t* pos,

+                                                const cx_value_t* p1, const cx_value_t* p2, bool clone);

+STC_API cx_iter_t       cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos,

+                                            const cx_rawvalue_t* p1, const cx_rawvalue_t* p2);

+STC_API void            cx_memb(_expand_right_)(Self* self, size_t idx, size_t n);

+

+STC_INLINE bool         cx_memb(_empty)(Self cx) { return !cdeq_rep_(&cx)->size; }

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

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

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

+STC_INLINE i_val        cx_memb(_value_fromraw)(i_valraw raw) { return i_valfrom(raw); }

+STC_INLINE i_valraw     cx_memb(_value_toraw)(cx_value_t* pval) { return i_valto(pval); }

+STC_INLINE i_val        cx_memb(_value_clone)(i_val val)

+                            { return i_valfrom(i_valto(&val)); }

+STC_INLINE void         cx_memb(_emplace_back)(Self* self, i_valraw raw)

+                            { cx_memb(_push_back)(self, i_valfrom(raw)); }

+STC_INLINE void         cx_memb(_emplace_front)(Self* self, i_valraw raw)

+                            { cx_memb(_push_front)(self, i_valfrom(raw)); }

+STC_INLINE void         cx_memb(_pop_back)(Self* self)

+                            { i_valdel(&self->data[--cdeq_rep_(self)->size]); }

+STC_INLINE void         cx_memb(_pop_front)(Self* self)

+                            { i_valdel(self->data++); --cdeq_rep_(self)->size; }

+STC_INLINE cx_value_t*  cx_memb(_front)(const Self* self) { return self->data; }

+STC_INLINE cx_value_t*  cx_memb(_back)(const Self* self)

+                            { return self->data + cdeq_rep_(self)->size - 1; }

+STC_INLINE cx_value_t*  cx_memb(_at)(const Self* self, size_t idx)

+                            { assert(idx < cdeq_rep_(self)->size); return self->data + idx; }

+STC_INLINE cx_iter_t    cx_memb(_begin)(const Self* self)

+                            { return c_make(cx_iter_t){self->data}; }

+STC_INLINE cx_iter_t    cx_memb(_end)(const Self* self)

+                            { return c_make(cx_iter_t){self->data + cdeq_rep_(self)->size}; }

+STC_INLINE void         cx_memb(_next)(cx_iter_t* it) { ++it->ref; }

+STC_INLINE cx_iter_t    cx_memb(_adv)(cx_iter_t it, intptr_t offs) { it.ref += offs; return it; }

+STC_INLINE size_t       cx_memb(_idx)(Self cx, cx_iter_t it) { return it.ref - cx.data; }

+

+STC_INLINE Self

+cx_memb(_with_capacity)(size_t n) {

+    Self cx = cx_memb(_init)();

+    cx_memb(_expand_right_)(&cx, 0, n);

+    return cx;

+}

+

+STC_INLINE void

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

+    size_t sz = cdeq_rep_(self)->size;

+    if (n > sz) cx_memb(_expand_right_)(self, sz, n - sz);

+}

 

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

+STC_INLINE void

+cx_memb(_shrink_to_fit)(Self *self) {

+    Self cx = cx_memb(_clone)(*self);

+    cx_memb(_del)(self); *self = cx;

+}

 

+STC_INLINE cx_iter_t

+cx_memb(_insert)(Self* self, size_t idx, i_val value) {

+    return cx_memb(_insert_range_p)(self, self->data + idx, &value, &value + 1, false);

+}

+STC_INLINE cx_iter_t

+cx_memb(_insert_n)(Self* self, size_t idx, const cx_value_t arr[], size_t n) {

+    return cx_memb(_insert_range_p)(self, self->data + idx, arr, arr + n, false);

+}

+STC_INLINE cx_iter_t

+cx_memb(_insert_at)(Self* self, cx_iter_t it, i_val value) {

+    return cx_memb(_insert_range_p)(self, it.ref, &value, &value + 1, false);

+}

+

+STC_INLINE cx_iter_t

+cx_memb(_emplace)(Self* self, size_t idx, i_valraw raw) {

+    return cx_memb(_emplace_range_p)(self, self->data + idx, &raw, &raw + 1);

+}

+STC_INLINE cx_iter_t

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

+    return cx_memb(_emplace_range_p)(self, self->data + idx, arr, arr + n);

+}

+STC_INLINE cx_iter_t

+cx_memb(_emplace_at)(Self* self, cx_iter_t it, i_valraw raw) {

+    return cx_memb(_emplace_range_p)(self, it.ref, &raw, &raw + 1);

+}

+STC_INLINE cx_iter_t

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

+    return cx_memb(_insert_range_p)(self, it.ref, it1.ref, it2.ref, true);

+}

+STC_INLINE void

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

+    cx_memb(_emplace_range_p)(self, self->data + cdeq_rep_(self)->size, arr, arr + n);

+}

+

+STC_INLINE cx_iter_t

+cx_memb(_erase)(Self* self, size_t idx) {

+    return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + 1);

+}

+STC_INLINE cx_iter_t

+cx_memb(_erase_n)(Self* self, size_t idx, size_t n) {

+    return cx_memb(_erase_range_p)(self, self->data + idx, self->data + idx + n);

+}

+STC_INLINE cx_iter_t

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

+    return cx_memb(_erase_range_p)(self, it.ref, it.ref + 1);

+}

+STC_INLINE cx_iter_t

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

+    return cx_memb(_erase_range_p)(self, it1.ref, it2.ref);

+}

+

+STC_INLINE cx_iter_t

+cx_memb(_find)(const Self* self, i_valraw raw) {

+    return cx_memb(_find_in)(cx_memb(_begin)(self), cx_memb(_end)(self), raw);

+}

+

+STC_INLINE cx_value_t*

+cx_memb(_get)(const Self* self, i_valraw raw) {

+    cx_iter_t end = cx_memb(_end)(self);

+    cx_value_t* val = cx_memb(_find_in)(cx_memb(_begin)(self), end, raw).ref;

+    return val == end.ref ? NULL : val;

+}

+

+STC_INLINE void

+cx_memb(_sort_range)(cx_iter_t i1, cx_iter_t i2,

+                int(*_cmp_)(const cx_value_t*, const cx_value_t*)) {

+    qsort(i1.ref, i2.ref - i1.ref, sizeof *i1.ref, (int(*)(const void*, const void*)) _cmp_);

+}

+

+STC_INLINE void

+cx_memb(_sort)(Self* self) {

+    cx_memb(_sort_range)(cx_memb(_begin)(self), cx_memb(_end)(self), cx_memb(_value_compare));

+}

+

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

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

+

+#ifndef CDEQ_H_INCLUDED

+#define CDEQ_H_INCLUDED

 static struct cdeq_rep _cdeq_sentinel = {0, 0};

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

+#endif

+

+STC_DEF Self

+cx_memb(_init)(void) {

+    cx_value_t *b = (cx_value_t *) _cdeq_sentinel.base;

+    return c_make(Self){b, b};

+}

 

-#define _c_implement_cdeq(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw) \

-\

-    STC_DEF Self \

-    cx_memb(_init)(void) { \

-        cx_value_t *b = (cx_value_t *) _cdeq_sentinel.base; \

-        return c_make(Self){b, b}; \

-    } \

-\

-    STC_DEF void \

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

-        struct cdeq_rep* rep = _cdeq_rep(self); if (rep->cap) { \

-            for (cx_value_t *p = self->data, *q = p + rep->size; p != q; ++p) \

-                i_valdel(p); \

-            rep->size = 0; \

-        } \

-    } \

-\

-    STC_DEF void \

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

-        cx_memb(_clear)(self); \

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

-            c_free(_cdeq_rep(self)); \

-    } \

-\

-    STC_DEF size_t \

-    cx_memb(_realloc_)(Self* self, size_t n) { \

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

-        size_t sz = rep->size, cap = (size_t) (sz*1.7) + n + 7; \

-        size_t nfront = _cdeq_nfront(self); \

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

-                                           offsetof(struct cdeq_rep, base) + cap*sizeof(i_val)); \

-        rep->size = sz, rep->cap = cap; \

-        self->_base = (cx_value_t *) rep->base; \

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

-        return cap; \

-    } \

-\

-    STC_DEF void \

-    cx_memb(_expand_left_)(Self* self, size_t idx, size_t n) { \

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

-        size_t sz = rep->size, cap = rep->cap; \

-        size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; \

-        if (nfront >= n) { \

-            self->data = (cx_value_t *) memmove(self->data - n, self->data, idx*sizeof(i_val)); \

-        } else { \

-            if (sz*1.3 + n > cap) cap = cx_memb(_realloc_)(self, n); \

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

-            size_t pos = (nback*2 < unused) ? unused - nback : unused/2; \

-            memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); \

-            self->data = (cx_value_t *) memmove(self->_base + pos, self->data, idx*sizeof(i_val)); \

-        } \

-    } \

-\

-    STC_DEF void \

-    cx_memb(_expand_right_)(Self* self, size_t idx, size_t n) { \

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

-        size_t sz = rep->size, cap = rep->cap; \

-        size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront; \

-        if (nback >= n || sz*1.3 + n > cap && cx_memb(_realloc_)(self, n)) { \

-            memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); \

-        } else { \

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

-            size_t pos = (nfront*2 < unused) ? nfront : unused/2; \

-            memmove(self->_base + pos, self->data, idx*sizeof(i_val)); \

-            memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val)); \

-            self->data = ((cx_value_t *) self->_base) + pos; \

-        } \

-    } \

-\

-    STC_DEF cx_value_t* \

-    cx_memb(_insert_space_)(Self* self, cx_value_t* pos, size_t n) { \

-        size_t idx = pos - self->data; \

-        if (idx*2 < _cdeq_rep(self)->size) cx_memb(_expand_left_)(self, idx, n); \

-        else                               cx_memb(_expand_right_)(self, idx, n); \

-        if (n) _cdeq_rep(self)->size += n; /* do only if size > 0 */ \

-        return self->data + idx; \

-    } \

-\

-    STC_DEF void \

-    cx_memb(_push_front)(Self* self, i_val value) { \

-        if (self->data == self->_base) \

-            cx_memb(_expand_left_)(self, 0, 1); \

-        else \

-            --self->data; \

-        *self->data = value; \

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

-    } \

-\

-    STC_DEF void \

-    cx_memb(_push_back)(Self* self, i_val value) { \

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

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

-            cx_memb(_expand_right_)(self, rep->size, 1); \

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

-    } \

-\

-    STC_DEF Self \

-    cx_memb(_clone)(Self cx) { \

-        size_t sz = _cdeq_rep(&cx)->size; \

-        Self out = cx_memb(_with_capacity)(sz); \

-        cx_memb(_insert_range_p)(&out, out.data, cx.data, cx.data + sz, true); \

-        return out; \

-    } \

-\

-    STC_DEF cx_iter_t \

-    cx_memb(_insert_range_p)(Self* self, cx_value_t* pos, const cx_value_t* p1, \

-                                                     const cx_value_t* p2, bool clone) { \

-        pos = cx_memb(_insert_space_)(self, pos, p2 - p1); \

-        cx_iter_t it = {pos}; \

-        if (clone) while (p1 != p2) *pos++ = i_valfrom(i_valto(p1++)); \

-        else memcpy(pos, p1, (p2 - p1)*sizeof *p1); \

-        return it; \

-    } \

-\

-    STC_DEF cx_iter_t \

-    cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos, const cx_rawvalue_t* p1, const cx_rawvalue_t* p2) { \

-        pos = cx_memb(_insert_space_)(self, pos, p2 - p1); \

-        cx_iter_t it = {pos}; \

-        while (p1 != p2) *pos++ = i_valfrom(*p1++); \

-        return it; \

-    } \

-\

-    STC_DEF cx_iter_t \

-    cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2) { \

-        size_t n = p2 - p1; \

-        if (n > 0) { \

-            cx_value_t* p = p1, *end = self->data + _cdeq_rep(self)->size; \

-            while (p != p2) i_valdel(p++); \

-            if (p1 == self->data) self->data += n; \

-            else memmove(p1, p2, (end - p2) * sizeof(i_val)); \

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

-        } \

-        return c_make(cx_iter_t){p1}; \

-    } \

-\

-    STC_DEF cx_iter_t \

-    cx_memb(_find_in)(cx_iter_t i1, cx_iter_t i2, i_valraw raw) { \

-        for (; i1.ref != i2.ref; ++i1.ref) { \

-            i_valraw r = i_valto(i1.ref); \

-            if (i_cmp(&raw, &r) == 0) return i1; \

-        } \

-        return i2; \

-    } \

-\

-    STC_DEF int \

-    cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y) { \

-        i_valraw rx = i_valto(x); \

-        i_valraw ry = i_valto(y); \

-        return i_cmp(&rx, &ry); \

+STC_DEF void

+cx_memb(_clear)(Self* self) {

+    struct cdeq_rep* rep = cdeq_rep_(self); if (rep->cap) {

+        for (cx_value_t *p = self->data, *q = p + rep->size; p != q; ++p)

+            i_valdel(p);

+        rep->size = 0;

     }

+}

 

-#else

-#define _c_implement_cdeq(Self, i_val, i_cmp, i_valdel, i_valfrom, i_valto, i_valraw)

-#endif

+STC_DEF void

+cx_memb(_del)(Self* self) {

+    cx_memb(_clear)(self);

+    if (cdeq_rep_(self)->cap)

+        c_free(cdeq_rep_(self));

+}

+

+STC_DEF size_t

+cx_memb(_realloc_)(Self* self, size_t n) {

+    struct cdeq_rep* rep = cdeq_rep_(self);

+    size_t sz = rep->size, cap = (size_t) (sz*1.7) + n + 7;

+    size_t nfront = _cdeq_nfront(self);

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

+                                        offsetof(struct cdeq_rep, base) + cap*sizeof(i_val));

+    rep->size = sz, rep->cap = cap;

+    self->_base = (cx_value_t *) rep->base;

+    self->data = self->_base + nfront;

+    return cap;

+}

+

+STC_DEF void

+cx_memb(_expand_left_)(Self* self, size_t idx, size_t n) {

+    struct cdeq_rep* rep = cdeq_rep_(self);

+    size_t sz = rep->size, cap = rep->cap;

+    size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront;

+    if (nfront >= n) {

+        self->data = (cx_value_t *) memmove(self->data - n, self->data, idx*sizeof(i_val));

+    } else {

+        if (sz*1.3 + n > cap) cap = cx_memb(_realloc_)(self, n);

+        size_t unused = cap - (sz + n);

+        size_t pos = (nback*2 < unused) ? unused - nback : unused/2;

+        memmove(self->_base + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val));

+        self->data = (cx_value_t *) memmove(self->_base + pos, self->data, idx*sizeof(i_val));

+    }

+}

+

+STC_DEF void

+cx_memb(_expand_right_)(Self* self, size_t idx, size_t n) {

+    struct cdeq_rep* rep = cdeq_rep_(self);

+    size_t sz = rep->size, cap = rep->cap;

+    size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront;

+    if (nback >= n || sz*1.3 + n > cap && cx_memb(_realloc_)(self, n)) {

+        memmove(self->data + idx + n, self->data + idx, (sz - idx)*sizeof(i_val));

+    } else {

+        size_t unused = cap - (sz + n);

+        size_t pos = (nfront*2 < unused) ? nfront : unused/2;

+        memmove(self->_base + pos, self->data, idx*sizeof(i_val));

+        memmove(self->data + pos + idx + n, self->data + idx, (sz - idx)*sizeof(i_val));

+        self->data = ((cx_value_t *) self->_base) + pos;

+    }

+}

+

+STC_DEF cx_value_t*

+cx_memb(_insert_space_)(Self* self, cx_value_t* pos, size_t n) {

+    size_t idx = pos - self->data;

+    if (idx*2 < cdeq_rep_(self)->size) cx_memb(_expand_left_)(self, idx, n);

+    else                               cx_memb(_expand_right_)(self, idx, n);

+    if (n) cdeq_rep_(self)->size += n; /* do only if size > 0 */

+    return self->data + idx;

+}

+

+STC_DEF void

+cx_memb(_push_front)(Self* self, i_val value) {

+    if (self->data == self->_base)

+        cx_memb(_expand_left_)(self, 0, 1);

+    else

+        --self->data;

+    *self->data = value;

+    ++cdeq_rep_(self)->size;

+}

+

+STC_DEF void

+cx_memb(_push_back)(Self* self, i_val value) {

+    struct cdeq_rep* rep = cdeq_rep_(self);

+    if (_cdeq_nfront(self) + rep->size == rep->cap)

+        cx_memb(_expand_right_)(self, rep->size, 1);

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

+}

+

+STC_DEF Self

+cx_memb(_clone)(Self cx) {

+    size_t sz = cdeq_rep_(&cx)->size;

+    Self out = cx_memb(_with_capacity)(sz);

+    cx_memb(_insert_range_p)(&out, out.data, cx.data, cx.data + sz, true);

+    return out;

+}

+

+STC_DEF cx_iter_t

+cx_memb(_insert_range_p)(Self* self, cx_value_t* pos, const cx_value_t* p1,

+                                                    const cx_value_t* p2, bool clone) {

+    pos = cx_memb(_insert_space_)(self, pos, p2 - p1);

+    cx_iter_t it = {pos};

+    if (clone) while (p1 != p2) *pos++ = i_valfrom(i_valto(p1++));

+    else memcpy(pos, p1, (p2 - p1)*sizeof *p1);

+    return it;

+}

+

+STC_DEF cx_iter_t

+cx_memb(_emplace_range_p)(Self* self, cx_value_t* pos, const cx_rawvalue_t* p1, const cx_rawvalue_t* p2) {

+    pos = cx_memb(_insert_space_)(self, pos, p2 - p1);

+    cx_iter_t it = {pos};

+    while (p1 != p2) *pos++ = i_valfrom(*p1++);

+    return it;

+}

+

+STC_DEF cx_iter_t

+cx_memb(_erase_range_p)(Self* self, cx_value_t* p1, cx_value_t* p2) {

+    size_t n = p2 - p1;

+    if (n > 0) {

+        cx_value_t* p = p1, *end = self->data + cdeq_rep_(self)->size;

+        while (p != p2) i_valdel(p++);

+        if (p1 == self->data) self->data += n;

+        else memmove(p1, p2, (end - p2) * sizeof(i_val));

+        cdeq_rep_(self)->size -= n;

+    }

+    return c_make(cx_iter_t){p1};

+}

+

+STC_DEF cx_iter_t

+cx_memb(_find_in)(cx_iter_t i1, cx_iter_t i2, i_valraw raw) {

+    for (; i1.ref != i2.ref; ++i1.ref) {

+        i_valraw r = i_valto(i1.ref);

+        if (i_cmp(&raw, &r) == 0) return i1;

+    }

+    return i2;

+}

+

+STC_DEF int

+cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y) {

+    i_valraw rx = i_valto(x);

+    i_valraw ry = i_valto(y);

+    return i_cmp(&rx, &ry);

+}

 

 #endif

+#include "template.h"

diff --git a/include/stc/csmap.h b/include/stc/csmap.h
index 9896340c..dbee8fc9 100644
--- a/include/stc/csmap.h
+++ b/include/stc/csmap.h
@@ -24,23 +24,27 @@
 // Sorted/Ordered set and map - implemented as an AA-tree.

 /*

 #include <stdio.h>

+#include <stc/cstr.h>

+

+#define i_tag sx  // Sorted map<cstr, double>

+#define i_key_str

+#define i_val double

 #include <stc/csmap.h>

-using_csmap(mx, int, char); // Sorted map<int, char>

 

 int main(void) {

-    c_forvar (csmap_mx m = csmap_mx_init(), csmap_mx_del(&m))

+    c_forvar (csmap_sx m = csmap_sx_init(), csmap_sx_del(&m))

     {

-        csmap_mx_insert(&m, 5, 'a');

-        csmap_mx_insert(&m, 8, 'b');

-        csmap_mx_insert(&m, 12, 'c');

+        csmap_sx_emplace(&m, "Testing one", 1.234);

+        csmap_sx_emplace(&m, "Testing two", 12.34);

+        csmap_sx_emplace(&m, "Testing three", 123.4);

 

-        csmap_mx_iter_t it = csmap_mx_find(&m, 10); // none

-        char val = csmap_mx_find(&m, 5).ref->second;

-        csmap_mx_put(&m, 5, 'd'); // update

-        csmap_mx_erase(&m, 8);

+        csmap_sx_value_t *v = csmap_sx_get(&m, "Testing five"); // NULL

+        double num = *csmap_sx_at(&m, "Testing one");

+        csmap_sx_emplace_or_assign(&m, "Testing three", 1000.0); // update

+        csmap_sx_erase(&m, "Testing two");

 

-        c_foreach (i, csmap_mx, m)

-            printf("map %d: %c\n", i.ref->first, i.ref->second);

+        c_foreach (i, csmap_sx, m)

+            printf("map %s: %g\n", i.ref->first.str, i.ref->second);

     }

 }

 */

diff --git a/include/stc/cvec.h b/include/stc/cvec.h
index b79191f9..513870ed 100644
--- a/include/stc/cvec.h
+++ b/include/stc/cvec.h
@@ -63,8 +63,8 @@ int main() {
 #include <stdlib.h>

 #include <string.h>

 

-struct cvec_Rep_ { size_t size, cap; void* data[]; };

-#define cvec_rep_(self) c_container_of((self)->data, struct cvec_Rep_, data)

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

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

 #endif // CVEC_H_INCLUDED

 

 #define i_module cvec

@@ -218,12 +218,11 @@ cx_memb(_sort)(Self* self) {
 }

 

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

-

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

 

 #ifndef CVEC_H_INCLUDED

 #define CVEC_H_INCLUDED

-static struct cvec_Rep_ _cvec_sentinel = {0, 0};

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

 #endif

 

 STC_DEF Self

@@ -234,7 +233,7 @@ cx_memb(_init)(void) {
 

 STC_DEF void

 cx_memb(_clear)(Self* self) {

-    struct cvec_Rep_* rep = cvec_rep_(self); if (rep->cap) {

+    struct cvec_rep* rep = cvec_rep_(self); if (rep->cap) {

         for (cx_value_t *p = self->data, *q = p + rep->size; p != q; ++p)

             i_valdel(p);

         rep->size = 0;

@@ -250,11 +249,11 @@ cx_memb(_del)(Self* self) {
 

 STC_DEF void

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

-    struct cvec_Rep_* rep = cvec_rep_(self);

+    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,

-                                            offsetof(struct cvec_Rep_, data) + cap*sizeof(i_val));

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

+                                            offsetof(struct cvec_rep, data) + cap*sizeof(i_val));

         self->data = (cx_value_t*) rep->data;

         rep->size = len;

         rep->cap = cap;

@@ -264,7 +263,7 @@ cx_memb(_reserve)(Self* self, size_t cap) {
 STC_DEF void

 cx_memb(_resize)(Self* self, size_t len, i_val null_val) {

     cx_memb(_reserve)(self, len);

-    struct cvec_Rep_* rep = cvec_rep_(self);

+    struct cvec_rep* rep = cvec_rep_(self);

     size_t i, n = rep->size;

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

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

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

+#include <stc/forward.h>

+

+forward_cdeq(i32, int);

+forward_cdeq(pnt, struct Point);

+

+struct MyStruct {

+    cdeq_i32 intvec;

+    cdeq_pnt pntvec;

+} typedef MyStruct;

+

+

+#define f_tag i32

+#define i_val int

+#include <stc/cdeq.h>

+

+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

+#define i_val Point

+#define i_cmp point_compare

+#include <stc/cdeq.h>

+

+#define i_val float

+#include <stc/cdeq.h>

+

+#define i_val_str

+#include <stc/cdeq.h>

+

+

+int main()

+{

+    cdeq_i32 vec = cdeq_i32_init();

+    cdeq_i32_push_back(&vec, 123);

+    cdeq_i32_del(&vec);

+

+    cdeq_float fvec = cdeq_float_init();

+    cdeq_float_push_back(&fvec, 123.3);

+    cdeq_float_del(&fvec);

+

+    cdeq_pnt pvec = cdeq_pnt_init();

+    cdeq_pnt_push_back(&pvec, (Point){42, 14});

+    cdeq_pnt_push_back(&pvec, (Point){32, 94});

+    cdeq_pnt_push_front(&pvec, (Point){62, 81});

+    cdeq_pnt_sort(&pvec);

+    c_foreach (i, cdeq_pnt, pvec)

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

+    puts("");

+    cdeq_pnt_del(&pvec);

+

+    cdeq_str svec = cdeq_str_init();

+    cdeq_str_emplace_back(&svec, "Hello, friend");

+    cdeq_str_del(&svec);

+}
\ No newline at end of file
diff --git a/include/stc/test_new_smap.c b/include/stc/test_new_smap.c
index c2e68d0e..bcb83c61 100644
--- a/include/stc/test_new_smap.c
+++ b/include/stc/test_new_smap.c
@@ -37,24 +37,29 @@ int point_compare(const Point* a, const Point* b) {
 

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

+    c_forauto (csmap_int, map)

+        csmap_int_insert(&map, 123, 321);

+

+    c_forauto (csmap_pnt, pmap) {

+        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("");

+    }

+

+    c_forauto (csmap_str, smap) {

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

+        csmap_str_emplace(&smap, "The brown fox", "jumped");

+        csmap_str_emplace(&smap, "This is the time", "for all good things");

+        c_foreach (i, csmap_str, smap)

+            printf(" (%s: %s)\n", i.ref->first.str, i.ref->second.str);

+    }

+

+    c_forauto (csset_str, sset) {

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

+        csset_str_emplace(&sset, "Goodbye, foe");

+        printf("Found? %s\n", csset_str_contains(&sset, "Hello, friend") ? "true" : "false");

+    }

 }
\ No newline at end of file