From af12926547b1a09b4513ba149d13ea9f84d4c528 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 2 Sep 2020 19:49:51 +0200 Subject: Added cqueue.h and cstack.h adapters. Updated cpqueue.h API to be more consistent. --- README.md | 6 +++--- examples/complex.c | 22 ++++++++++----------- examples/geek7.c | 8 ++++---- examples/heap.c | 6 +++--- examples/inits.c | 4 ++-- examples/priority.c | 4 ++-- examples/stack.c | 18 +++++++++++++++++ stc/clist.h | 9 +++------ stc/cpqueue.h | 56 ++++++++++++++++++++++++++--------------------------- 9 files changed, 74 insertions(+), 59 deletions(-) create mode 100644 examples/stack.c diff --git a/README.md b/README.md index 1fa84c5e..03ecaf99 100644 --- a/README.md +++ b/README.md @@ -278,12 +278,12 @@ declare_clist(fx, double); int main() { clist_fx list = clist_init; - crandom_eng64_t eng = crandom_eng64_init(time(NULL)); - crandom_uniform_f64_t dist = crandom_uniform_f64_init(100.0, 1000.0); + crand_eng64_t eng = crand_eng64_init(time(NULL)); + crand_uniform_f64_t dist = crand_uniform_f64_init(100.0, 1000.0); int k; for (int i = 0; i < 10000000; ++i) - clist_fx_push_back(&list, crandom_uniform_f64(&eng, dist)); + clist_fx_push_back(&list, crand_uniform_f64(&eng, dist)); k = 0; c_foreach (i, clist_fx, list) if (++k <= 100) printf("%8d: %10f\n", k, i.item->value); else break; diff --git a/examples/complex.c b/examples/complex.c index 08a3b505..8810bac5 100644 --- a/examples/complex.c +++ b/examples/complex.c @@ -6,32 +6,32 @@ void check_destroy(float* v) {printf("destroy %g\n", *v);} declare_carray(f, float, check_destroy); // normally omit the last argument - float type need no destroy. -declare_clist(t2, carray2f, carray2f_destroy, c_no_compare); -declare_cmap(il, int, clist_t2, clist_t2_destroy); -declare_cmap_strkey(sm, cmap_il, cmap_il_destroy); +declare_clist(y, carray2f, carray2f_destroy, c_no_compare); +declare_cmap(g, int, clist_y, clist_y_destroy); +declare_cmap_strkey(s, cmap_g, cmap_g_destroy); int main() { int xdim = 4, ydim = 6; int x = 1, y = 5, tableKey = 42; const char* strKey = "first"; - cmap_sm theMap = cmap_init; + cmap_s myMap = cmap_init; { // Construct. carray2f table = carray2f_make(ydim, xdim, 0.f); printf("table: (%zu, %zu)\n", carray2_ydim(table), carray2_xdim(table)); - clist_t2 tableList = clist_init; + clist_y tableList = clist_init; // Put in some data. - cmap_il listMap = cmap_init; + cmap_g listMap = cmap_init; *carray2f_at(&table, y, x) = 3.1415927; // table[y][x] - clist_t2_push_back(&tableList, table); - cmap_il_put(&listMap, tableKey, tableList); - cmap_sm_put(&theMap, strKey, listMap); + clist_y_push_back(&tableList, table); + cmap_g_put(&listMap, tableKey, tableList); + cmap_s_put(&myMap, strKey, listMap); } { // Access the data entry - carray2f table = clist_back(cmap_il_find(&cmap_sm_find(&theMap, strKey)->value, tableKey)->value); + carray2f table = *clist_y_back(&cmap_g_find(&cmap_s_find(&myMap, strKey)->value, tableKey)->value); printf("value (%d, %d) is: %f\n", y, x, *carray2f_at(&table, y, x)); } - cmap_sm_destroy(&theMap); // free up the whole shebang! + c_destroy(cmap_s, &myMap); // free up everything! } \ No newline at end of file diff --git a/examples/geek7.c b/examples/geek7.c index 2ff33223..9004a1a8 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -29,10 +29,10 @@ After inserting all the elements excluding the ones which are to be deleted, Pop declare_cmap(ii, int, int); declare_cvec(i, int); -declare_cpqueue(i, >, cvec); +declare_cpqueue(i, cvec_i, >); -// Find k minimum element from arr[0..m-1] after deleting -// elements from del[0..n-1] +// Find k minimum element from arr[0..m-1] after deleting +// elements from del[0..n-1] void findElementsAfterDel(int arr[], int m, int del[], int n, int k) { @@ -68,7 +68,7 @@ void findElementsAfterDel(int arr[], int m, int del[], // Print top k elements in the min heap for (int i = 0; i < k; ++i) { - printf("%d ", cpqueue_i_top(heap)); + printf("%d ", *cpqueue_i_top(&heap)); // Pop the top element cpqueue_i_pop(&heap); diff --git a/examples/heap.c b/examples/heap.c index 0ff6e059..5917dd30 100644 --- a/examples/heap.c +++ b/examples/heap.c @@ -5,7 +5,7 @@ #include declare_cvec(f, float); -declare_cpqueue(f, >, cvec); +declare_cpqueue(f, cvec_f, >); int main() { @@ -24,7 +24,7 @@ int main() printf("Built priority queue: %f secs\n", (clock() - start) / (float) CLOCKS_PER_SEC); for (int i=0; i, cvec); +declare_cpqueue(f, cvec_f, >); int main(void) { @@ -36,7 +36,7 @@ int main(void) { // sorted: while (cvec_size(floats) > 0) { - printf("%.1f ", cpqueue_f_top(floats)); + printf("%.1f ", *cpqueue_f_top(&floats)); cpqueue_f_pop(&floats); } puts("\n"); diff --git a/examples/priority.c b/examples/priority.c index 0204779d..82e78621 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -7,7 +7,7 @@ #include declare_cvec(i, int64_t); -declare_cpqueue(i, >, cvec); // min-heap (increasing values) +declare_cpqueue(i, cvec_i, >); // min-heap (increasing values) int main() { size_t N = 10000000; @@ -28,7 +28,7 @@ int main() { // Extract the hundred smallest. for (int i=0; i<100; ++i) { - printf("%zd ", cpqueue_i_top(heap)); + printf("%zd ", *cpqueue_i_top(&heap)); cpqueue_i_pop(&heap); } cpqueue_i_destroy(&heap); diff --git a/examples/stack.c b/examples/stack.c new file mode 100644 index 00000000..2aa8364b --- /dev/null +++ b/examples/stack.c @@ -0,0 +1,18 @@ + +#include +#include + +declare_cvec(i, int); +declare_cstack(i, cvec_i); + +int main() { + cstack_i stack = cstack_i_init(); + + for (int i=0; i<100; ++i) + cstack_i_push(&stack, i*i); + + for (int i=0; i<90; ++i) + cstack_i_pop(&stack); + + printf("top: %d\n", *cstack_i_top(&stack)); +} \ No newline at end of file diff --git a/stc/clist.h b/stc/clist.h index 615176df..4cba9d1f 100644 --- a/stc/clist.h +++ b/stc/clist.h @@ -39,10 +39,10 @@ int main() { clist_ix list = clist_init; - crandom_eng32_t pcg = crandom_eng32_init(12345); + crand_rng32_t pcg = crand_rng32_init(12345); int n; for (int i=0; i<1000000; ++i) // one million - clist_ix_push_back(&list, crandom_i32(&pcg)); + clist_ix_push_back(&list, crand_i32(&pcg)); n = 0; c_foreach (i, clist_ix, list) if (++n % 10000 == 0) printf("%8d: %10zd\n", n, i.item->value); @@ -84,9 +84,6 @@ #define clist_init {NULL} #define clist_empty(list) ((list).last == NULL) -#define clist_front(list) (list).last->next->value -#define clist_back(list) (list).last->value - #define declare_clist_7(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ \ @@ -97,7 +94,7 @@ STC_INLINE clist_##tag \ clist_##tag##_init(void) {clist_##tag x = clist_init; return x;} \ STC_INLINE bool \ - clist_##tag##_empty(clist_##tag* self) {return clist_empty(*self);} \ + clist_##tag##_empty(clist_##tag l) {return clist_empty(l);} \ STC_INLINE Value \ clist_##tag##_value_from_raw(RawValue rawValue) {return valueFromRaw(rawValue);} \ \ diff --git a/stc/cpqueue.h b/stc/cpqueue.h index 15fd980a..b2c81478 100644 --- a/stc/cpqueue.h +++ b/stc/cpqueue.h @@ -26,19 +26,19 @@ #include #include declare_cvec(f, float); - declare_cpqueue(f, >, cvec); // min-heap (increasing values) + declare_cpqueue(f, cvec_f, >); // min-heap (increasing values) int main() { - crandom_eng32_t gen = crandom_eng32_init(1234); - crandom_uniform_f32_t dist = crandom_uniform_f32_init(10.0f, 100.0f); + crand_rng32_t gen = crand_rng32_init(1234); + crand_uniform_f32_t dist = crand_uniform_f32_init(10.0f, 100.0f); - cpqueue_f queue = cpqueue_init; + cpqueue_f queue = cpqueue_f_init(); // Push ten million random numbers onto the queue. for (int i=0; i<10000000; ++i) - cpqueue_f_push(&queue, crandom_uniform_f32(&gen, dist)); + cpqueue_f_push(&queue, crand_uniform_f32(&gen, dist)); // Extract the 100 smallest. for (int i=0; i<100; ++i) { - printf("%f ", cpqueue_f_top(queue)); + printf("%f ", *cpqueue_f_top(queue)); cpqueue_f_pop(&queue); } cpqueue_f_destroy(&queue); @@ -48,53 +48,53 @@ #ifndef CPQUEUE__H__ #define CPQUEUE__H__ -#include "cdefs.h" +#include "cvec.h" -#define declare_cpqueue(tag, cmpOpr, type) /* cmpOpr: < or > */ \ +#define declare_cpqueue(tag, ctype, cmpOpr) /* cmpOpr: < or > */ \ \ -typedef type##_##tag cpqueue_##tag; \ -typedef type##_##tag##_value_t cpqueue_##tag##_value_t; \ -typedef type##_##tag##_rawvalue_t cpqueue_##tag##_rawvalue_t; \ -typedef type##_##tag##_input_t cpqueue_##tag##_input_t; \ +typedef ctype cpqueue_##tag; \ +typedef ctype##_value_t cpqueue_##tag##_value_t; \ +typedef ctype##_rawvalue_t cpqueue_##tag##_rawvalue_t; \ +typedef ctype##_input_t cpqueue_##tag##_input_t; \ STC_INLINE cpqueue_##tag \ -cpqueue_##tag##_init() {return type##_##tag##_init();} \ +cpqueue_##tag##_init() {return ctype##_init();} \ STC_INLINE size_t \ -cpqueue_##tag##_size(cpqueue_##tag pq) {return type##_##tag##_size(pq);} \ +cpqueue_##tag##_size(cpqueue_##tag pq) {return ctype##_size(pq);} \ STC_INLINE bool \ -cpqueue_##tag##_empty(cpqueue_##tag pq) {return type##_##tag##_empty(pq);} \ +cpqueue_##tag##_empty(cpqueue_##tag pq) {return ctype##_empty(pq);} \ STC_INLINE void \ -cpqueue_##tag##_destroy(cpqueue_##tag* self) {type##_##tag##_destroy(self);} \ +cpqueue_##tag##_destroy(cpqueue_##tag* self) {ctype##_destroy(self);} \ STC_API void \ cpqueue_##tag##_build(cpqueue_##tag* self); \ STC_API void \ cpqueue_##tag##_erase(cpqueue_##tag* self, size_t i); \ -STC_INLINE cpqueue_##tag##_value_t \ -cpqueue_##tag##_top(cpqueue_##tag pq) {return pq.data[0];} \ +STC_INLINE const cpqueue_##tag##_value_t* \ +cpqueue_##tag##_top(const cpqueue_##tag* self) {return &self->data[0];} \ STC_INLINE void \ cpqueue_##tag##_pop(cpqueue_##tag* self) {cpqueue_##tag##_erase(self, 0);} \ STC_API void \ cpqueue_##tag##_push_v(cpqueue_##tag* self, cpqueue_##tag##_value_t value); \ STC_INLINE void \ cpqueue_##tag##_push(cpqueue_##tag* self, cpqueue_##tag##_rawvalue_t rawValue) { \ - cpqueue_##tag##_push_v(self, type##_##tag##_value_from_raw(rawValue)); \ + cpqueue_##tag##_push_v(self, ctype##_value_from_raw(rawValue)); \ } \ STC_API void \ cpqueue_##tag##_push_n(cpqueue_##tag *self, const cpqueue_##tag##_input_t in[], size_t size); \ \ -implement_cpqueue(tag, cmpOpr, type) +implement_cpqueue(tag, ctype, cmpOpr) /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_cpqueue(tag, cmpOpr, type) \ +#define implement_cpqueue(tag, ctype, cmpOpr) \ \ STC_INLINE void \ _cpqueue_##tag##_sift_down(cpqueue_##tag##_value_t* arr, size_t i, size_t n) { \ size_t r = i, c = i << 1; \ while (c <= n) { \ - if (c < n && type##_##tag##_value_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ + if (c < n && ctype##_value_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ ++c; \ - if (type##_##tag##_value_compare(&arr[r], &arr[c]) cmpOpr 0) { \ + if (ctype##_value_compare(&arr[r], &arr[c]) cmpOpr 0) { \ cpqueue_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ } else \ return; \ @@ -114,28 +114,28 @@ STC_API void \ cpqueue_##tag##_erase(cpqueue_##tag* self, size_t i) { \ size_t n = cpqueue_##tag##_size(*self) - 1; \ self->data[i] = self->data[n]; \ - type##_##tag##_pop_back(self); \ + ctype##_pop_back(self); \ _cpqueue_##tag##_sift_down(self->data - 1, i + 1, n); \ } \ \ STC_API void \ cpqueue_##tag##_push_v(cpqueue_##tag* self, cpqueue_##tag##_value_t value) { \ - type##_##tag##_push_back(self, value); /* sift-up the value */ \ + ctype##_push_back(self, value); /* sift-up the value */ \ size_t n = cpqueue_##tag##_size(*self), c = n; \ cpqueue_##tag##_value_t *arr = self->data - 1; \ - for (; c > 1 && type##_##tag##_value_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ + for (; c > 1 && ctype##_value_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ arr[c] = arr[c >> 1]; \ if (c != n) arr[c] = value; \ } \ STC_API void \ cpqueue_##tag##_push_n(cpqueue_##tag *self, const cpqueue_##tag##_input_t in[], size_t size) { \ - type##_##tag##_reserve(self, cpqueue_##tag##_size(*self) + size); \ + ctype##_reserve(self, cpqueue_##tag##_size(*self) + size); \ for (size_t i=0; i