Added support for cqueue.h Added test.

5 files changed, 142 insertions, 116 deletions

diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h
index f384644e..d128597e 100644
--- a/include/stc/cdeq.h
+++ b/include/stc/cdeq.h
@@ -31,11 +31,13 @@ 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

 

+#ifndef i_module

 #define i_module cdeq

+#endif

 #include "template.h"

 

 #if !defined i_fwd

-   cx_deftypes(_c_cdeq_types, Self, i_val);

+cx_deftypes(_c_cdeq_types, Self, i_val);

 #endif

 typedef i_valraw cx_rawvalue_t;

 

@@ -43,16 +45,19 @@ 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 void            cx_memb(_push_back)(Self* self, i_val value);

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

+

+#ifndef i_queue

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

+#endif // i_queue

 

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

@@ -64,25 +69,18 @@ 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_value_t*  cx_memb(_front)(const Self* self) { return self->data; }

 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(_advance)(cx_iter_t it, intptr_t offs) 

+STC_INLINE cx_iter_t    cx_memb(_advance)(cx_iter_t it, intptr_t offs)

                             { it.ref += offs; return it; }

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

 

 STC_INLINE Self

 cx_memb(_with_capacity)(size_t n) {

@@ -92,17 +90,41 @@ cx_memb(_with_capacity)(size_t n) {
 }

 

 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 void

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

+    for (size_t i = 0; i < n; ++i)

+        cx_memb(_push_back)(self, i_valfrom(arr[i]));

+}

+

+#ifndef i_queue

+

+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 cx_value_t* cx_memb(_at)(const Self* self, size_t idx) {

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

+}

+

+STC_INLINE size_t cx_memb(_index)(Self cx, cx_iter_t it) {

+    return it.ref - cx.data;

+}

+

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

@@ -132,10 +154,6 @@ 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) {

@@ -176,6 +194,7 @@ STC_INLINE void
 cx_memb(_sort)(Self* self) {

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

 }

+#endif // i_queue

 

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

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

@@ -194,7 +213,8 @@ cx_memb(_init)(void) {
 

 STC_DEF void

 cx_memb(_clear)(Self* self) {

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

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

@@ -222,34 +242,53 @@ cx_memb(_realloc_)(Self* self, size_t n) {
 }

 

 STC_DEF void

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

+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 (nfront >= n) {

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

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

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

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

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

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

+    cdeq_rep_(&out)->size = sz;

+    for (size_t i = 0; i < sz; ++i) out.data[i] = i_valfrom(i_valto(&cx.data[i]));

+    return out;

+}

+

+#ifndef i_queue

+

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

+    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 = (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;

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

     }

 }

 

@@ -272,22 +311,6 @@ cx_memb(_push_front)(Self* self, i_val 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) {

@@ -335,5 +358,6 @@ cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y) {
     return i_cmp(&rx, &ry);

 }

 

-#endif

+#endif // i_queue

+#endif // IMPLEMENTATION

 #include "template.h"

diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h
index 596f50a9..454913c1 100644
--- a/include/stc/cqueue.h
+++ b/include/stc/cqueue.h
@@ -20,74 +20,46 @@
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

  * SOFTWARE.

  */

-#ifndef CQUEUE_H_INCLUDED

-#define CQUEUE_H_INCLUDED

+// STC queue

+/*

+#include <stc/crandom.h>

+#include <stdio.h>

 

-/*  Queue adapter, default uses clist.

+#define i_val int

+#include <stc/cqueue.h>

 

-    #include <stc/crandom.h>

-    #include <stc/cqueue.h>

-    using_cdeq(i, int);

-    using_cqueue(i, cdeq_i);

+int main() {

+    int n = 10000000;

+    stc64_t rng = stc64_init(1234);

+    stc64_uniform_t dist = stc64_uniform_init(0, n);

 

-    int main() {

-        int n = 10000000;

-        stc64_t rng = stc64_init(1234);

-        stc64_uniform_t dist = stc64_uniform_init(rng, 0, n);

+    c_forauto (cqueue_int, Q)

+    {

+        // Push ten million random numbers onto the queue.

+        for (int i=0; i<n; ++i)

+            cqueue_int_push(&Q, stc64_uniform(&rng, &dist));

 

-        c_forvar (cqueue_i queue = cqueue_i_init(), cqueue_i_del(&queue))

-        {

-            // Push ten million random numbers onto the queue.

-            for (int i=0; i<n; ++i)

-                cqueue_i_push(&queue, stc64_uniform(&dist));

-

-            // Push or pop on the queue ten million times

-            printf("%d\n", n);

-            for (int i=n; i>0; --i) {

-                int r = stc64_uniform(&dist);

-                if (r & 1)

-                    ++n, cqueue_i_push(&queue, r);

-                else

-                    --n, cqueue_i_pop(&queue);

-            }

+        // Push or pop on the queue ten million times

+        printf("before: size, capacity: %d, %d\n", n, cqueue_int_size(Q), cqueue_int_capacity(Q));

+        for (int i=n; i>0; --i) {

+            int r = stc64_uniform(&rng, &dist);

+            if (r & 1)

+                ++n, cqueue_int_push(&Q, r);

+            else

+                --n, cqueue_int_pop(&Q);

         }

-        printf("%d\n", n);

+        printf("after: size, capacity: %d, %d\n", n, cqueue_int_size(Q), cqueue_int_capacity(Q));

     }

+}

 */

-#include "cdeq.h"

 

-#define using_cqueue(X, ctype) \

-            _c_using_cqueue(cqueue_##X, ctype)

+#define i_module cqueue

+#define i_queue

+#define _push_back _push

+#define _pop_front _pop

 

-#define _c_using_cqueue(Self, ctype) \

-    typedef struct { ctype rep; size_t size; } Self; \

-    typedef ctype##_value_t cx_value_t; \

-    typedef ctype##_rawvalue_t cx_rawvalue_t; \

-    typedef ctype##_iter_t cx_iter_t; \

-\

-    STC_INLINE Self               cx_memb(_init)(void) { return c_make(Self){ctype##_init(), 0}; } \

-    STC_INLINE Self               cx_memb(_clone)(Self q) { return c_make(Self){ctype##_clone(q.rep), q.size}; } \

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

-                                    { return ctype##_value_clone(val); } \

-    STC_INLINE void             cx_memb(_clear)(Self* self) {ctype##_clear(&self->rep); self->size = 0; } \

-    STC_INLINE void             cx_memb(_del)(Self* self) {ctype##_del(&self->rep); } \

-\

-    STC_INLINE size_t           cx_memb(_size)(Self q) { return q.size; } \

-    STC_INLINE bool             cx_memb(_empty)(Self q) { return q.size == 0; } \

-    STC_INLINE cx_value_t*    cx_memb(_front)(const Self* self) { return ctype##_front(&self->rep); } \

-    STC_INLINE cx_value_t*    cx_memb(_back)(const Self* self) { return ctype##_back(&self->rep); } \

-\

-    STC_INLINE void             cx_memb(_pop)(Self* self) {ctype##_pop_front(&self->rep); --self->size; } \

-    STC_INLINE void             cx_memb(_push)(Self* self, ctype##_value_t value) \

-                                    {ctype##_push_back(&self->rep, value); ++self->size; } \

-    STC_INLINE void             cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) \

-                                    {ctype##_emplace_back(&self->rep, raw); ++self->size; } \

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

-                                    {ctype##_emplace_items(&self->rep, arr, n); self->size += n; } \

-\

-    STC_INLINE cx_iter_t      cx_memb(_begin)(const Self* self) { return ctype##_begin(&self->rep); } \

-    STC_INLINE cx_iter_t      cx_memb(_end)(const Self* self) { return ctype##_end(&self->rep); } \

-    STC_INLINE void             cx_memb(_next)(cx_iter_t* it) {ctype##_next(it); } \

-    struct stc_trailing_semicolon

+#include "cdeq.h"

 

-#endif

+#undef _push_back

+#undef _pop_front

+#undef i_queue

diff --git a/include/stc/cstack.h b/include/stc/cstack.h
index ea116be2..c0d89c78 100644
--- a/include/stc/cstack.h
+++ b/include/stc/cstack.h
@@ -95,7 +95,7 @@ STC_INLINE cx_iter_t cx_memb(_begin)(const Self* self)
 STC_INLINE cx_iter_t cx_memb(_end)(const Self* self)

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

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

-STC_INLINE cx_iter_t cx_memb(_advance)(cx_iter_t it, intptr_t offs) 

+STC_INLINE cx_iter_t cx_memb(_advance)(cx_iter_t it, intptr_t offs)

     { it.ref += offs; return it; }

 

 #include "template.h"

diff --git a/include/stc/test_new_cpque.c b/include/stc/test_new_pque.c
index d9d66c09..d9d66c09 100644
--- a/include/stc/test_new_cpque.c
+++ b/include/stc/test_new_pque.c
diff --git a/include/stc/test_new_queue.c b/include/stc/test_new_queue.c
new file mode 100644
index 00000000..fc8e3997
--- /dev/null
+++ b/include/stc/test_new_queue.c
@@ -0,0 +1,30 @@
+#include <stc/crandom.h>

+#include <stdio.h>

+

+#define i_val int

+#include <stc/cqueue.h>

+#include <time.h>

+

+int main() {

+    int n = 8000000;

+    stc64_t rng = stc64_init(time(NULL));

+    stc64_uniform_t dist = stc64_uniform_init(0, n);

+

+    c_forauto (cqueue_int, Q)

+    {

+        // Push eight million random numbers onto the queue.

+        for (int i=0; i<n; ++i)

+            cqueue_int_push(&Q, stc64_uniform(&rng, &dist));

+

+        // Push or pop on the queue ten million times

+        printf("befor: size %zu, capacity %zu\n", cqueue_int_size(Q), cqueue_int_capacity(Q));

+        for (int i=n; i>0; --i) {

+            int r = stc64_uniform(&rng, &dist);

+            if (r & 1)

+                cqueue_int_push(&Q, r);

+            else

+                cqueue_int_pop(&Q);

+        }

+        printf("after: size %zu, capacity %zu\n", cqueue_int_size(Q), cqueue_int_capacity(Q));

+    }

+}
\ No newline at end of file