From ad4c5377cf7e2f5812e2053e51550239fcd38d45 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 10 Sep 2021 19:01:45 +0200 Subject: Added support for cqueue.h Added test. --- include/stc/cdeq.h | 132 +++++++++++++++++++++++++------------------ include/stc/cqueue.h | 94 +++++++++++------------------- include/stc/cstack.h | 2 +- include/stc/test_new_cpque.c | 63 --------------------- include/stc/test_new_pque.c | 63 +++++++++++++++++++++ include/stc/test_new_queue.c | 30 ++++++++++ 6 files changed, 205 insertions(+), 179 deletions(-) delete mode 100644 include/stc/test_new_cpque.c create mode 100644 include/stc/test_new_pque.c create mode 100644 include/stc/test_new_queue.c (limited to 'include') 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) { @@ -91,18 +89,42 @@ cx_memb(_with_capacity)(size_t 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 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 +#include -/* Queue adapter, default uses clist. +#define i_val int +#include - #include - #include - 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; i0; --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_cpque.c deleted file mode 100644 index d9d66c09..00000000 --- a/include/stc/test_new_cpque.c +++ /dev/null @@ -1,63 +0,0 @@ -#include - -forward_cpque(pnt, struct Point); - -struct MyStruct { - cpque_pnt priority_queue; - int id; -}; - -#define i_val int -#include "cstack.h" - -#define i_val int -#include "cpque.h" - -struct Point { int x, y; } typedef Point; - -int Point_cmp(const Point* a, const Point* b) { - int c = c_default_compare(&a->x, &b->x); - return c ? c : c_default_compare(&a->y, &b->y); -} -#define f_tag pnt // f: was forward declared. -#define i_val Point -#define i_cmp Point_cmp -#include "cpque.h" - -#include - -int main() -{ - cstack_int istk = cstack_int_init(); - cstack_int_push(&istk, 123); - cstack_int_push(&istk, 321); - // print - c_foreach (i, cstack_int, istk) - printf(" %d", *i.ref); - cstack_int_del(&istk); - puts(""); - - cpque_pnt pque = cpque_pnt_init(); - cpque_pnt_push(&pque, (Point){23, 80}); - cpque_pnt_push(&pque, (Point){12, 32}); - cpque_pnt_push(&pque, (Point){54, 74}); - cpque_pnt_push(&pque, (Point){12, 62}); - // print - while (!cpque_pnt_empty(pque)) { - cpque_pnt_value_t *v = cpque_pnt_top(&pque); - printf(" (%d,%d)", v->x, v->y); - cpque_pnt_pop(&pque); - } - // free - cpque_pnt_del(&pque); - puts(""); - - cpque_int ique = cpque_int_init(); - cpque_int_push(&ique, 123); - cpque_int_push(&ique, 321); - // print - for (int i=0; i + +forward_cpque(pnt, struct Point); + +struct MyStruct { + cpque_pnt priority_queue; + int id; +}; + +#define i_val int +#include "cstack.h" + +#define i_val int +#include "cpque.h" + +struct Point { int x, y; } typedef Point; + +int Point_cmp(const Point* a, const Point* b) { + int c = c_default_compare(&a->x, &b->x); + return c ? c : c_default_compare(&a->y, &b->y); +} +#define f_tag pnt // f: was forward declared. +#define i_val Point +#define i_cmp Point_cmp +#include "cpque.h" + +#include + +int main() +{ + cstack_int istk = cstack_int_init(); + cstack_int_push(&istk, 123); + cstack_int_push(&istk, 321); + // print + c_foreach (i, cstack_int, istk) + printf(" %d", *i.ref); + cstack_int_del(&istk); + puts(""); + + cpque_pnt pque = cpque_pnt_init(); + cpque_pnt_push(&pque, (Point){23, 80}); + cpque_pnt_push(&pque, (Point){12, 32}); + cpque_pnt_push(&pque, (Point){54, 74}); + cpque_pnt_push(&pque, (Point){12, 62}); + // print + while (!cpque_pnt_empty(pque)) { + cpque_pnt_value_t *v = cpque_pnt_top(&pque); + printf(" (%d,%d)", v->x, v->y); + cpque_pnt_pop(&pque); + } + // free + cpque_pnt_del(&pque); + puts(""); + + cpque_int ique = cpque_int_init(); + cpque_int_push(&ique, 123); + cpque_int_push(&ique, 321); + // print + for (int i=0; i +#include + +#define i_val int +#include +#include + +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; i0; --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 -- cgit v1.2.3