Changed internal representation of cdeq. All containers in STC can now be initialized with {NULL}.

1 files changed, 59 insertions, 83 deletions

diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h
index 62ddc3ea..93e806ae 100644
--- a/include/stc/cdeq.h
+++ b/include/stc/cdeq.h
@@ -27,8 +27,6 @@
 #include <stdlib.h>
 #include <string.h>
 
-struct cdeq_rep { size_t size, cap; unsigned base[1]; };
-#define cdeq_rep_(self) c_unchecked_container_of((self)->_base, struct cdeq_rep, base)
 #define _it2_ptr(it1, it2) (it1.ref && !it2.ref ? it2.end : it2.ref)
 #define _it_ptr(it) (it.ref ? it.ref : it.end)
 #endif // CDEQ_H_INCLUDED
@@ -80,32 +78,32 @@ STC_API _cx_iter        _cx_memb(_copy_range)(_cx_self* self, _cx_value* pos,
 STC_INLINE void         _cx_memb(_copy)(_cx_self *self, const _cx_self* other) {
                             if (self->data == other->data) return;
                             _cx_memb(_clear)(self);
-                            _cx_memb(_copy_range)(self, self->data, other->data, 
-                                                    other->data + cdeq_rep_(other)->size);
+                            _cx_memb(_copy_range)(self, self->data,
+                                                  other->data, other->data + other->_len);
                         }
 #endif // !_i_queue
 STC_API _cx_self        _cx_memb(_clone)(_cx_self cx);
 STC_INLINE i_key        _cx_memb(_value_clone)(i_key val)
                             { return i_keyclone(val); }
 #endif // !i_no_clone
-STC_INLINE size_t       _cx_memb(_size)(const _cx_self* cx) { return cdeq_rep_(cx)->size; }
-STC_INLINE size_t       _cx_memb(_capacity)(const _cx_self* cx) { return cdeq_rep_(cx)->cap; }
-STC_INLINE bool         _cx_memb(_empty)(const _cx_self* cx) { return !cdeq_rep_(cx)->size; }
+STC_INLINE size_t       _cx_memb(_size)(const _cx_self* self) { return self->_len; }
+STC_INLINE size_t       _cx_memb(_capacity)(const _cx_self* self) { return self->_cap; }
+STC_INLINE bool         _cx_memb(_empty)(const _cx_self* self) { return !self->_len; }
 STC_INLINE _cx_raw      _cx_memb(_value_toraw)(const _cx_value* pval) { return i_keyto(pval); }
 STC_INLINE void         _cx_memb(_swap)(_cx_self* a, _cx_self* b) { c_swap(_cx_self, *a, *b); }
 STC_INLINE _cx_value*   _cx_memb(_front)(const _cx_self* self) { return self->data; }
 STC_INLINE _cx_value*   _cx_memb(_back)(const _cx_self* self)
-                            { return self->data + cdeq_rep_(self)->size - 1; }
+                            { return self->data + self->_len - 1; }
 STC_INLINE void         _cx_memb(_pop_front)(_cx_self* self) // == _pop() when _i_queue
-                            { assert(!_cx_memb(_empty)(self)); i_keydrop(self->data); ++self->data; --cdeq_rep_(self)->size; }
+                            { i_keydrop(self->data); ++self->data; --self->_len; }
 
 STC_INLINE _cx_iter _cx_memb(_begin)(const _cx_self* self) {
-    size_t n = cdeq_rep_(self)->size;
+    size_t n = self->_len;
     return c_init(_cx_iter){n ? self->data : NULL, self->data + n};
 }
 
 STC_INLINE _cx_iter _cx_memb(_end)(const _cx_self* self)
-    { return c_init(_cx_iter){NULL, self->data + cdeq_rep_(self)->size}; }
+    { return c_init(_cx_iter){NULL, self->data + self->_len}; }
 
 STC_INLINE void _cx_memb(_next)(_cx_iter* it)
     { if (++it->ref == it->end) it->ref = NULL; }
@@ -115,16 +113,16 @@ STC_INLINE _cx_iter _cx_memb(_advance)(_cx_iter it, intptr_t n)
 
 #if !defined _i_queue
 
-STC_INLINE size_t       _cx_memb(_index)(const _cx_self* cx, _cx_iter it)
-                            { return it.ref - cx->data; }
-STC_INLINE void         _cx_memb(_pop_back)(_cx_self* self)
-                            { assert(!_cx_memb(_empty)(self)); _cx_value* p = &self->data[--cdeq_rep_(self)->size]; i_keydrop(p); }
+STC_INLINE size_t _cx_memb(_index)(const _cx_self* self, _cx_iter it)
+    { return it.ref - self->data; }
+STC_INLINE void _cx_memb(_pop_back)(_cx_self* self)
+    { _cx_value* p = &self->data[--self->_len]; i_keydrop(p); }
 
 STC_INLINE const _cx_value* _cx_memb(_at)(const _cx_self* self, const size_t idx) {
-    assert(idx < cdeq_rep_(self)->size);  return self->data + idx;
+    assert(idx < self->_len); return self->data + idx;
 }
 STC_INLINE _cx_value* _cx_memb(_at_mut)(_cx_self* self, const size_t idx) {
-    assert(idx < cdeq_rep_(self)->size);  return self->data + idx;
+    assert(idx < self->_len); return self->data + idx;
 }
 
 STC_INLINE _cx_value* _cx_memb(_push_back)(_cx_self* self, i_key value) {
@@ -207,74 +205,60 @@ _cx_memb(_sort)(_cx_self* self) {
 
 /* -------------------------- IMPLEMENTATION ------------------------- */
 #if defined(i_implement)
-
-#ifndef CDEQ_H_INCLUDED
-static struct cdeq_rep _cdeq_sentinel = {0, 0};
 #define _cdeq_nfront(self) ((self)->data - (self)->_base)
-#endif
 
 STC_DEF _cx_self
 _cx_memb(_init)(void) {
-    _cx_value *b = (_cx_value *) _cdeq_sentinel.base;
-    return c_init(_cx_self){b, b};
+    _cx_self cx = {NULL};
+    return cx;
 }
 
 STC_DEF void
 _cx_memb(_clear)(_cx_self* self) {
-    struct cdeq_rep* rep = cdeq_rep_(self);
-    if (rep->cap) {
-        for (_cx_value *p = self->data, *q = p + rep->size; p != q; ) {
-            --q; i_keydrop(q);
-        }
-        rep->size = 0;
+    if (self->_cap) {
+        for (_cx_value *p = self->data, *q = p + self->_len; p != q; )
+            { --q; i_keydrop(q); }
+        self->_len = 0;
         self->data = self->_base;
     }
 }
 
 STC_DEF void
 _cx_memb(_shrink_to_fit)(_cx_self *self) {
-    if (_cx_memb(_size)(self) != _cx_memb(_capacity)(self)) {
-        struct cdeq_rep* rep = cdeq_rep_(self);
-        const size_t sz = rep->size;
-        memmove(self->_base, self->data, sz*sizeof(i_key));
-        rep = (struct cdeq_rep*) c_realloc(rep, offsetof(struct cdeq_rep, base) +
-                                                sz*sizeof(i_key));
-        if (rep) {
-            self->_base = self->data = (_cx_value*)rep->base;
-            rep->cap = sz;
+    if (self->_len != self->_cap) {
+        memmove(self->_base, self->data, self->_len*sizeof(i_key));
+        _cx_value* d = (_cx_value*)c_realloc(self->_base, self->_len*sizeof(i_key));
+        if (d) {
+            self->_base = self->data = d;
+            self->_cap = self->_len;
         }
     }
 }
 
 STC_DEF void
 _cx_memb(_drop)(_cx_self* self) {
-    struct cdeq_rep* rep = cdeq_rep_(self);
-    // second test to supress gcc -O2 warn: -Wfree-nonheap-object
-    if (rep->cap == 0 || rep == &_cdeq_sentinel)
-        return;
-    _cx_memb(_clear)(self);
-    c_free(rep);
+    if (self->_base) {
+        _cx_memb(_clear)(self);
+        c_free(self->_base);
+    }
 }
 
 static size_t
 _cx_memb(_realloc_)(_cx_self* self, const size_t n) {
-    struct cdeq_rep* rep = cdeq_rep_(self);
-    const size_t sz = rep->size, cap = (size_t) (sz*1.7) + n + 7;
+    const size_t cap = (size_t)(self->_len*1.7) + n + 7;
     const size_t nfront = _cdeq_nfront(self);
-    rep = (struct cdeq_rep*) c_realloc(rep->cap ? rep : NULL,
-                                       offsetof(struct cdeq_rep, base) + cap*sizeof(i_key));
-    if (!rep)
+    _cx_value* d = (_cx_value*)c_realloc(self->_base, cap*sizeof(i_key));
+    if (!d)
         return 0; 
-    rep->size = sz, rep->cap = cap;
-    self->_base = (_cx_value *) rep->base;
-    self->data = self->_base + nfront;
+    self->_cap = cap;
+    self->_base = d;
+    self->data = d + nfront;
     return cap;
 }
 
 static bool
 _cx_memb(_expand_right_half_)(_cx_self* self, const size_t idx, const size_t n) {
-    struct cdeq_rep* rep = cdeq_rep_(self);
-    const size_t sz = rep->size, cap = rep->cap;
+    const size_t sz = self->_len, cap = self->_cap;
     const size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront;
     if (nback >= n || sz*1.3 + n > cap) {
         if (!_cx_memb(_realloc_)(self, n))
@@ -303,31 +287,26 @@ _cx_memb(_with_capacity)(const size_t n) {
 
 STC_DEF bool
 _cx_memb(_reserve)(_cx_self* self, const size_t n) {
-    const size_t sz = cdeq_rep_(self)->size;
+    const size_t sz = self->_len;
     return n <= sz || _cx_memb(_expand_right_half_)(self, sz, n - sz);
 }
 
 STC_DEF _cx_value*
 _cx_memb(_push)(_cx_self* self, i_key value) {
-    struct cdeq_rep* r = cdeq_rep_(self);
-    if (_cdeq_nfront(self) + r->size == r->cap) {
-        _cx_memb(_expand_right_half_)(self, r->size, 1);
-        r = cdeq_rep_(self);
-    }
-    _cx_value *v = self->data + r->size++;
-    *v = value; return v;
+    if (_cdeq_nfront(self) + self->_len == self->_cap)
+        _cx_memb(_expand_right_half_)(self, self->_len, 1);
+    _cx_value *v = self->data + self->_len++;
+    *v = value;
+    return v;
 }
 
 #if !c_option(c_no_clone)
 STC_DEF _cx_self
 _cx_memb(_clone)(_cx_self cx) {
-    const size_t sz = cdeq_rep_(&cx)->size;
-    _cx_self out = _cx_memb(_with_capacity)(sz);
-    struct cdeq_rep* r = cdeq_rep_(&out);
-    if (r->cap) {
-        for (size_t i = 0; i < sz; ++i) out.data[i] = i_keyclone(cx.data[i]);
-        r->size = sz;
-    }
+    _cx_self out = _cx_memb(_with_capacity)(cx._len);
+    if (out._base)
+        for (size_t i = 0; i < cx._len; ++i) 
+            out.data[i] = i_keyclone(cx.data[i]);
     return out;
 }
 #endif
@@ -336,9 +315,8 @@ _cx_memb(_clone)(_cx_self cx) {
 
 static void
 _cx_memb(_expand_left_half_)(_cx_self* self, const size_t idx, const size_t n) {
-    struct cdeq_rep* rep = cdeq_rep_(self);
-    size_t cap = rep->cap;
-    const size_t sz = rep->size;
+    size_t cap = self->_cap;
+    const size_t sz = self->_len;
     const size_t nfront = _cdeq_nfront(self), nback = cap - sz - nfront;
     if (nfront >= n) {
         self->data = (_cx_value *)memmove(self->data - n, self->data, idx*sizeof(i_key));
@@ -354,19 +332,17 @@ _cx_memb(_expand_left_half_)(_cx_self* self, const size_t idx, const size_t n) {
 
 static _cx_iter
 _cx_memb(_insert_uninit)(_cx_self* self, _cx_value* pos, const size_t n) {
-    struct cdeq_rep* r = cdeq_rep_(self);
     if (n) {
-        if (!pos) pos = self->data + r->size;
+        if (!pos) pos = self->data + self->_len;
         const size_t idx = pos - self->data;
-        if (idx*2 < r->size)
+        if (idx*2 < self->_len)
             _cx_memb(_expand_left_half_)(self, idx, n);
         else
             _cx_memb(_expand_right_half_)(self, idx, n);
-        r = cdeq_rep_(self);
-        r->size += n;
+        self->_len += n;
         pos = self->data + idx;
     }
-    return c_init(_cx_iter){pos, self->data + r->size};
+    return c_init(_cx_iter){pos, self->data + self->_len};
 }
 
 STC_DEF _cx_value*
@@ -375,7 +351,7 @@ _cx_memb(_push_front)(_cx_self* self, i_key value) {
         _cx_memb(_expand_left_half_)(self, 0, 1);
     else
         --self->data;
-    ++cdeq_rep_(self)->size;
+    ++self->_len;
     *self->data = value;
     return self->data;
 }
@@ -393,12 +369,11 @@ STC_DEF _cx_iter
 _cx_memb(_erase_range_p)(_cx_self* self, _cx_value* p1, _cx_value* p2) {
     assert(p1 && p2);
     intptr_t len = p2 - p1;
-    struct cdeq_rep* r = cdeq_rep_(self);
-    _cx_value* p = p1, *end = self->data + r->size;
+    _cx_value* p = p1, *end = self->data + self->_len;
     for (; p != p2; ++p)
         { i_keydrop(p); }
     memmove(p1, p2, (end - p2) * sizeof *p1);
-    r->size -= len;
+    self->_len -= len;
     return c_init(_cx_iter){p2 == end ? NULL : p1, end - len};
 }
 
@@ -436,7 +411,8 @@ _cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, _cx_raw raw) {
         if (i_eq((&raw), (&r)))
             return i1;
     }
-    i2.ref = NULL; return i2; // NB!
+    i2.ref = NULL;
+    return i2;
 }
 
 STC_DEF int