From 89987eee11ad1ef0b5fcbfd5beb3c392e2cb5471 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 7 Sep 2021 22:14:55 +0200 Subject: Added cstack and cpque (priority queue) + test. --- include/stc/cpque.h | 203 ++++++++++++++++++++----------------------- include/stc/cstack.h | 99 ++++++++++----------- include/stc/forward.h | 36 ++++---- include/stc/test_new_cpque.c | 63 ++++++++++++++ 4 files changed, 223 insertions(+), 178 deletions(-) create mode 100644 include/stc/test_new_cpque.c (limited to 'include') diff --git a/include/stc/cpque.h b/include/stc/cpque.h index a9bc6b56..9b2939a7 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -21,126 +21,111 @@ * SOFTWARE. */ -/* Priority-Queue adapter (implemented as heap), default uses cvec. - - #include - #include - using_cvec(f, float); - using_cpque(f, cvec_f, -c_default_compare); // min-heap (increasing values) +#ifndef CPQUE_H_INCLUDED +#define CPQUE_H_INCLUDED +#include +#include "ccommon.h" +#include "forward.h" +#endif - int main() { - stc64_t rng = stc64_init(1234); - stc64_uniformf_t dist = stc64_uniformf_init(10.0f, 100.0f); +#define i_module cpque +#include "template.h" - c_forvar (cpque_f queue = cpque_f_init(), cpque_f_del(&queue)) - { - // Push ten million random numbers onto the queue. - for (int i=0; i<10000000; ++i) - cpque_f_push(&queue, stc64_uniformf(&rng, dist)); +#if !defined i_fwd + cx_deftypes(_c_cpque_types, Self, i_val); +#endif +typedef i_valraw cx_rawvalue_t; - // Extract the 100 smallest. - for (int i=0; i<100; ++i) { - printf("%f ", *cpque_f_top(queue)); - cpque_f_pop(&queue); - } - } - } -*/ -#ifndef CPQUEUE_H_INCLUDED -#define CPQUEUE_H_INCLUDED +STC_API void cx_memb(_make_heap)(Self* self); +STC_API void cx_memb(_erase_at)(Self* self, size_t idx); +STC_API void cx_memb(_push)(Self* self, cx_value_t value); +STC_API void cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n); +STC_API Self cx_memb(_clone)(Self q); -#include "cvec.h" +STC_INLINE Self cx_memb(_init)(void) + { return (Self){0, 0, 0}; } +STC_INLINE void cx_memb(_clear)(Self* self) + { while (self->size) i_valdel(&self->data[--self->size]); } +STC_INLINE size_t cx_memb(_size)(Self q) + { return q.size; } +STC_INLINE bool cx_memb(_empty)(Self q) + { return !q.size; } +STC_INLINE size_t cx_memb(_capacity)(Self q) + { return q.capacity; } +STC_INLINE void cx_memb(_pop)(Self* self) + { cx_memb(_erase_at)(self, 0); } +STC_INLINE cx_value_t* cx_memb(_top)(const Self* self) + { return &self->data[0]; } + +STC_INLINE void cx_memb(_push_back_)(Self* self, cx_value_t value) { + if (self->size == self->capacity) + self->data = realloc(self->data, (self->capacity = self->size*3/2 + 4)*sizeof value); + self->data[ self->size++ ] = value; +} +STC_INLINE void cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) + { cx_memb(_push)(self, i_valfrom(raw)); } -#define using_cpque(...) c_MACRO_OVERLOAD(using_cpque, __VA_ARGS__) +STC_INLINE void cx_memb(_del)(Self* self) + { cx_memb(_clear)(self); free(self->data); } + +STC_INLINE int cx_memb(_value_compare)(const cx_value_t* x, const cx_value_t* y) { + cx_rawvalue_t rx = i_valto(x), ry = i_valto(y); + return i_cmp(&rx, &ry); +} -#define using_cpque_2(X, ctype) \ - _c_using_cpque(cpque_##X, ctype, ctype##_value_compare) -#define using_cpque_3(X, ctype, i_cmp) \ - _c_using_cpque(cpque_##X, ctype, i_cmp) +/* -------------------------- IMPLEMENTATION ------------------------- */ +#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) || defined(i_imp) -#define _c_using_cpque(Self, ctype, i_cmp) \ - typedef ctype Self; \ - typedef ctype##_value_t cx_value_t; \ - typedef ctype##_rawvalue_t cx_rawvalue_t; \ -\ - STC_INLINE Self cx_memb(_init)(void) { return ctype##_init(); } \ - STC_INLINE Self cx_memb(_clone)(Self pq) { return ctype##_clone(pq); } \ - 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); } \ - STC_INLINE void cx_memb(_del)(Self* self) {ctype##_del(self); } \ -\ - STC_INLINE size_t cx_memb(_size)(Self pq) { return ctype##_size(pq); } \ - STC_INLINE bool cx_memb(_empty)(Self pq) { return ctype##_empty(pq); } \ - \ - STC_API void cx_memb(_make_heap)(Self* self); \ - STC_API void cx_memb(_erase_at)(Self* self, size_t idx); \ - STC_INLINE \ - const cx_value_t* cx_memb(_top)(const Self* self) { return &self->data[0]; } \ - STC_INLINE void cx_memb(_pop)(Self* self) { cx_memb(_erase_at)(self, 0); } \ - \ - STC_API void cx_memb(_push)(Self* self, cx_value_t value); \ - STC_INLINE void cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) \ - { cx_memb(_push)(self, ctype##_value_fromraw(raw)); } \ - STC_API void cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n); \ -\ - _c_implement_cpque(Self, ctype, i_cmp) \ - struct stc_trailing_semicolon +STC_API void +cx_memb(_sift_down_)(cx_value_t* arr, size_t i, size_t n) { + size_t r = i, c = i << 1; + while (c <= n) { + c += (c < n && i_cmp(&arr[c], &arr[c + 1]) < 0); + if (i_cmp(&arr[r], &arr[c]) < 0) { + cx_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; + } else + return; + c <<= 1; + } +} +STC_API void +cx_memb(_make_heap)(Self* self) { + size_t n = cx_memb(_size)(*self); + cx_value_t *arr = self->data - 1; + for (size_t k = n >> 1; k != 0; --k) + cx_memb(_sift_down_)(arr, k, n); +} -/* -------------------------- IMPLEMENTATION ------------------------- */ +STC_API Self cx_memb(_clone)(Self q) { + Self out = {(cx_value_t*) c_malloc(q.size*sizeof(cx_value_t)), q.size, q.size}; + for (cx_value_t *a = out.data, *b = a + q.size; a != b; ++a) *a = i_valfrom(i_valto(q.data++)); + return out; +} -#if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) +STC_API void +cx_memb(_erase_at)(Self* self, size_t idx) { + size_t n = cx_memb(_size)(*self) - 1; + self->data[idx] = self->data[n]; + --self->size; + cx_memb(_sift_down_)(self->data - 1, idx + 1, n); +} -#define _c_implement_cpque(Self, ctype, i_cmp) \ -\ - STC_INLINE void \ - cx_memb(_sift_down_)(cx_value_t* arr, size_t i, size_t n) { \ - size_t r = i, c = i << 1; \ - while (c <= n) { \ - c += (c < n && i_cmp(&arr[c], &arr[c + 1]) < 0); \ - if (i_cmp(&arr[r], &arr[c]) < 0) { \ - cx_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \ - } else \ - return; \ - c <<= 1; \ - } \ - } \ -\ - STC_API void \ - cx_memb(_make_heap)(Self* self) { \ - size_t n = cx_memb(_size)(*self); \ - cx_value_t *arr = self->data - 1; \ - for (size_t k = n >> 1; k != 0; --k) \ - cx_memb(_sift_down_)(arr, k, n); \ - } \ -\ - STC_API void \ - cx_memb(_erase_at)(Self* self, size_t idx) { \ - size_t n = cx_memb(_size)(*self) - 1; \ - self->data[idx] = self->data[n]; \ - ctype##_pop_back(self); \ - cx_memb(_sift_down_)(self->data - 1, idx + 1, n); \ - } \ -\ - STC_API void \ - cx_memb(_push)(Self* self, cx_value_t value) { \ - ctype##_push_back(self, value); /* sift-up the value */ \ - size_t n = cx_memb(_size)(*self), c = n; \ - cx_value_t *arr = self->data - 1; \ - for (; c > 1 && i_cmp(&arr[c >> 1], &value) < 0; c >>= 1) \ - arr[c] = arr[c >> 1]; \ - if (c != n) arr[c] = value; \ - } \ -\ - STC_API 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)(self, ctype##_value_fromraw(arr[i])); \ - } \ +STC_API void +cx_memb(_push)(Self* self, cx_value_t value) { + cx_memb(_push_back_)(self, value); /* sift-up the value */ + size_t n = cx_memb(_size)(*self), c = n; + cx_value_t *arr = self->data - 1; + for (; c > 1 && i_cmp(&arr[c >> 1], &value) < 0; c >>= 1) + arr[c] = arr[c >> 1]; + if (c != n) arr[c] = value; +} -#else -#define _c_implement_cpque(Self, ctype, i_cmp) -#endif +STC_API 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)(self, i_valfrom(arr[i])); +} #endif +#include "template.h" diff --git a/include/stc/cstack.h b/include/stc/cstack.h index 30fc4f71..b754525f 100644 --- a/include/stc/cstack.h +++ b/include/stc/cstack.h @@ -20,63 +20,60 @@ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE * SOFTWARE. */ + #ifndef CSTACK_H_INCLUDED #define CSTACK_H_INCLUDED +#include +#include "ccommon.h" +#include "forward.h" +#endif -/* Stack adapter, default uses cvec. - - #include - #include - - using_cvec(i, int); - using_cstack(i, cvec_i); +#define i_module cstack +#include "template.h" - int main() { - c_forvar (cstack_i stack = cstack_i_init(), cstack_i_del(&stack)) - { - for (int i=0; i<100; ++i) - cstack_i_push(&stack, i*i); +#if !defined i_fwd + cx_deftypes(_c_cstack_types, Self, i_val); +#endif +typedef i_valraw cx_rawvalue_t; - for (int i=0; i<90; ++i) - cstack_i_pop(&stack); +STC_INLINE Self cx_memb(_init)(void) + { return (Self){0, 0, 0}; } +STC_INLINE void cx_memb(_clear)(Self* self) + { while (self->size) i_valdel(&self->data[--self->size]); } +STC_INLINE size_t cx_memb(_size)(Self v) + { return v.size; } +STC_INLINE bool cx_memb(_empty)(Self v) + { return !v.size; } +STC_INLINE size_t cx_memb(_capacity)(Self v) + { return v.capacity; } +STC_INLINE void cx_memb(_pop)(Self* self) + { --self->size; } +STC_INLINE cx_value_t* cx_memb(_top)(const Self* self) + { return &self->data[self->size - 1]; } +STC_INLINE void cx_memb(_push)(Self* self, cx_value_t value) { + if (self->size == self->capacity) + self->data = realloc(self->data, (self->capacity = self->size*3/2 + 4)*sizeof value); + self->data[ self->size++ ] = value; +} +STC_INLINE void cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) + { cx_memb(_push)(self, i_valfrom(raw)); } - printf("top: %d\n", *cstack_i_top(&stack)); - } - } -*/ -#include "cvec.h" +STC_INLINE void cx_memb(_del)(Self* self) { + size_t i = self->size; + while (i--) i_valdel(&self->data[i]); + free(self->data); +} -#define using_cstack(X, ctype) \ - _c_using_cstack(cstack_##X, ctype) +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 + self->size}; } +STC_INLINE void cx_memb(_next)(cx_iter_t* it) {++it->ref; } -#define _c_using_cstack(Self, ctype) \ - typedef ctype 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 ctype##_init(); } \ - STC_INLINE Self cx_memb(_clone)(Self st) { return ctype##_clone(st); } \ - 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); } \ - STC_INLINE void cx_memb(_del)(Self* self) {ctype##_del(self); } \ -\ - STC_INLINE size_t cx_memb(_size)(Self st) { return ctype##_size(st); } \ - STC_INLINE bool cx_memb(_empty)(Self st) { return ctype##_empty(st); } \ - STC_INLINE cx_value_t* cx_memb(_top)(const Self* self) { return ctype##_back(self); } \ -\ - STC_INLINE void cx_memb(_pop)(Self* self) {ctype##_pop_back(self); } \ - STC_INLINE void cx_memb(_push)(Self* self, ctype##_value_t value) \ - {ctype##_push_back(self, value); } \ - STC_INLINE void cx_memb(_emplace)(Self* self, cx_rawvalue_t raw) \ - {ctype##_emplace_back(self, raw); } \ - STC_INLINE void cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size_t n) \ - {ctype##_emplace_items(self, arr, n); } \ -\ - STC_INLINE cx_iter_t cx_memb(_begin)(const Self* self) { return ctype##_begin(self); } \ - STC_INLINE cx_iter_t cx_memb(_end)(const Self* self) { return ctype##_end(self); } \ - STC_INLINE void cx_memb(_next)(cx_iter_t* it) {ctype##_next(it); } \ - struct stc_trailing_semicolon +STC_INLINE Self cx_memb(_clone)(Self v) { + Self out = {(cx_value_t*) c_malloc(v.size*sizeof(cx_value_t)), v.size, v.size}; + for (cx_value_t *a = out.data, *b = a + v.size; a != b; ++a) *a = i_valfrom(i_valto(v.data++)); + return out; +} -#endif +#include "template.h" diff --git a/include/stc/forward.h b/include/stc/forward.h index c2ac5e39..78bc9173 100644 --- a/include/stc/forward.h +++ b/include/stc/forward.h @@ -23,6 +23,8 @@ #ifndef STC_FORWARD_H_INCLUDED #define STC_FORWARD_H_INCLUDED +#include + #define forward_carray2(TAG, VAL) _c_carray2_types(carray2##TAG, VAL) #define forward_carray3(TAG, VAL) _c_carray3_types(carray2##TAG, VAL) #define forward_cdeq(TAG, VAL) _c_cdeq_types(cdeq_##TAG, VAL) @@ -32,9 +34,9 @@ #define forward_cset(TAG, KEY) _c_chash_types(cset_##TAG, cset, KEY, KEY, c_false, c_true) #define forward_csset(TAG, KEY) _c_aatree_types(csset_##TAG, KEY, KEY, c_false, c_true) #define forward_csptr(TAG, VAL) _csptr_types(csptr_##TAG, VAL) -#define forward_cpque(TAG, ctype) _c_cpque_types(cpque_##TAG, ctype) -#define forward_cqueue(TAG, ctype) _c_cqueue_types(cqueue_##TAG, ctype) -#define forward_cstack(TAG, ctype) _c_cstack_types(cstack_##TAG, ctype) +#define forward_cpque(TAG, VAL) _c_cpque_types(cpque_##TAG, VAL) +#define forward_cstack(TAG, VAL) _c_cstack_types(cstack_##TAG, VAL) +//#define forward_cqueue(TAG, VAL) _c_cqueue_types(cqueue_##TAG, VAL) #define forward_cvec(TAG, VAL) _c_cvec_types(cvec_##TAG, VAL) #ifndef MAP_SIZE_T @@ -131,22 +133,20 @@ long* use_count; \ } SELF -#define _c_cpque_types(SELF, ctype) \ - typedef ctype##_value_t SELF##_value_t; \ - typedef ctype##_rawvalue_t SELF##_rawvalue_t; \ - typedef ctype SELF - -#define _c_cqueue_types(SELF, ctype) \ - typedef ctype##_value_t SELF##_value_t; \ - typedef ctype##_rawvalue_t SELF##_rawvalue_t; \ - typedef ctype##_iter_t SELF##_iter_t; \ - typedef struct { ctype rep; size_t size; } SELF +#define _c_cstack_types(SELF, VAL) \ + typedef VAL SELF##_value_t; \ + typedef struct { SELF##_value_t *ref; } SELF##_iter_t; \ + typedef struct SELF { \ + SELF##_value_t* data; \ + size_t size, capacity; \ + } SELF -#define _c_cstack_types(SELF, ctype) \ - typedef ctype##_value_t SELF##_value_t; \ - typedef ctype##_rawvalue_t SELF##_rawvalue_t; \ - typedef ctype##_iter_t SELF##_iter_t; \ - typedef ctype SELF +#define _c_cpque_types(SELF, VAL) \ + typedef VAL SELF##_value_t; \ + typedef struct SELF { \ + SELF##_value_t* data; \ + size_t size, capacity; \ + } SELF #define _c_cvec_types(SELF, VAL) \ typedef VAL SELF##_value_t; \ diff --git a/include/stc/test_new_cpque.c b/include/stc/test_new_cpque.c new file mode 100644 index 00000000..d9d66c09 --- /dev/null +++ b/include/stc/test_new_cpque.c @@ -0,0 +1,63 @@ +#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