From d3bb64882aa00c9c1b3056d74796b59fc2180f0e Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 2 Sep 2020 11:07:52 +0200 Subject: Rewrote cpqueue to a real adapter class. Added some missing functions in cvec, clist, cmap. Added c_init() and c_destroy() generic algoritms on containers. --- examples/ex_gaussian.c | 6 ++-- examples/geek7.c | 13 +++---- examples/heap.c | 29 +++++++++------ examples/inits.c | 34 ++++++++---------- examples/phonebook.c | 72 +++++++++++++++++++++++++++++++++++++ examples/priority.c | 19 +++++----- stc/cdefs.h | 14 ++++++-- stc/clist.h | 7 +++- stc/cmap.h | 3 ++ stc/cpqueue.h | 96 ++++++++++++++++++++++++++++---------------------- stc/cvec.h | 16 +++++---- 11 files changed, 211 insertions(+), 98 deletions(-) create mode 100644 examples/phonebook.c diff --git a/examples/ex_gaussian.c b/examples/ex_gaussian.c index dcb78d7b..75efec51 100644 --- a/examples/ex_gaussian.c +++ b/examples/ex_gaussian.c @@ -19,7 +19,7 @@ declare_cvec(e, cmap_i_entry_t, c_default_destroy, compare); int main() { enum {N = 10000000}; - const double Mean = 12.0, StdDev = 8.0, Mag = 12000.0 / StdDev; + const double Mean = -12.0, StdDev = 8.0, Mag = 12000.0 / StdDev; printf("Demo of gaussian / normal distribution of %d random samples\n", N); @@ -32,7 +32,7 @@ int main() cmap_i mhist = cmap_init; for (size_t i = 0; i < N; ++i) { int index = round( crand_normal_f64(&dist) ); - ++ cmap_i_insert(&mhist, index, 0)->value; + cmap_i_insert(&mhist, index, 0)->value += 1; } // Transfer map to vec and sort it by map keys. @@ -55,4 +55,4 @@ int main() cstr_destroy(&bar); cmap_i_destroy(&mhist); cvec_e_destroy(&vhist); -} \ No newline at end of file +} diff --git a/examples/geek7.c b/examples/geek7.c index 9a60c0a9..65af4486 100644 --- a/examples/geek7.c +++ b/examples/geek7.c @@ -24,11 +24,12 @@ After inserting all the elements excluding the ones which are to be deleted, Pop #include #include #include +#include #include declare_cmap(ii, int, int); declare_cvec(i, int); -declare_cvec_pqueue(i, >); +declare_cpqueue(i, >, cvec); // Find k minimum element from arr[0..m-1] after deleting // elements from del[0..n-1] @@ -43,7 +44,7 @@ void findElementsAfterDel(int arr[], int m, int del[], cmap_ii_insert(&mp, del[i], 0)->value++; } - cvec_i heap = cvec_init; + cpqueue_i heap = cpqueue_i_init(); for (int i = 0; i < m; ++i) { @@ -62,17 +63,17 @@ void findElementsAfterDel(int arr[], int m, int del[], // Else push it in the min heap else - cvec_i_pqueue_push(&heap, arr[i]); + cpqueue_i_push(&heap, arr[i]); } // Print top k elements in the min heap for (int i = 0; i < k; ++i) { - printf("%d ", cvec_i_pqueue_top(&heap)); + printf("%d ", *cpqueue_i_top(&heap)); // Pop the top element - cvec_i_pqueue_pop(&heap); + cpqueue_i_pop(&heap); } - cvec_i_destroy(&heap); + cpqueue_i_destroy(&heap); } int main() diff --git a/examples/heap.c b/examples/heap.c index c6624819..82b351fd 100644 --- a/examples/heap.c +++ b/examples/heap.c @@ -1,36 +1,45 @@ #include #include #include +#include #include declare_cvec(f, float); -declare_cvec_pqueue(f, >); +declare_cpqueue(f, >, cvec); int main() { uint32_t seed = time(NULL); - crand_rng32_t pcg = crand_rng32_init(seed); - int N = 30000000, M = 100; - cvec_f vec = cvec_init; + crand_rng32_t pcg; + int N = 3000000, M = 100; + + cpqueue_f pq = cpqueue_f_init(); + + pcg = crand_rng32_init(seed); clock_t start = clock(); for (int i=0; i #include #include +#include #include #include @@ -16,37 +17,35 @@ declare_cvec(ip, ipair_t, c_default_destroy, ipair_compare); declare_clist(ip, ipair_t, c_default_destroy, ipair_compare); declare_cvec(f, float); -declare_cvec_pqueue(f, >); +declare_cpqueue(f, >, cvec); int main(void) { // CVEC FLOAT / PRIORITY QUEUE - cvec_f floats = cvec_init; - c_push(&floats, cvec_f, c_items(4.0f, 2.0f, 5.0f, 3.0f, 1.0f)); + c_init(cvec_f, floats, c_items(4.0f, 2.0f, 5.0f, 3.0f, 1.0f)); c_foreach (i, cvec_f, floats) printf("%.1f ", *i.item); puts(""); // CVEC PRIORITY QUEUE - cvec_f_pqueue_build(&floats); // reorganise vec - c_push(&floats, cvec_f_pqueue, c_items(40.0f, 20.0f, 50.0f, 30.0f, 10.0f)); + cpqueue_f_build(&floats); // reorganise vec + c_push(&floats, cpqueue_f, c_items(40.0f, 20.0f, 50.0f, 30.0f, 10.0f)); // sorted: while (cvec_size(floats) > 0) { - printf("%.1f ", cvec_f_pqueue_top(&floats)); - cvec_f_pqueue_pop(&floats); + printf("%.1f ", *cpqueue_f_top(&floats)); + cpqueue_f_pop(&floats); } puts("\n"); - cvec_f_destroy(&floats); + cpqueue_f_destroy(&floats); // CMAP ID int year = 2020; - cmap_id idnames = cmap_init; - c_push(&idnames, cmap_id, c_items( + c_init(cmap_id, idnames, c_items( {100, cstr_make("Hello")}, {110, cstr_make("World")}, {120, cstr_from("Howdy, -%d-", year)}, @@ -59,10 +58,7 @@ int main(void) { // CMAP CNT - cmap_cnt countries = cmap_init; - - cmap_cnt_insert(&countries, "Greenland", 0)->value += 20; - c_push(&countries, cmap_cnt, c_items( + c_init(cmap_cnt, countries, c_items( {"Norway", 100}, {"Denmark", 50}, {"Iceland", 10}, @@ -72,7 +68,7 @@ int main(void) { {"Spain", 10}, {"France", 10}, )); - + cmap_cnt_insert(&countries, "Greenland", 0)->value += 20; cmap_cnt_insert(&countries, "Sweden", 0)->value += 20; cmap_cnt_insert(&countries, "Norway", 0)->value += 20; cmap_cnt_insert(&countries, "Finland", 0)->value += 20; @@ -84,14 +80,14 @@ int main(void) { // CVEC PAIR - cvec_ip pairs1 = cvec_init; - c_push(&pairs1, cvec_ip, c_items( + c_init(cvec_ip, pairs1, c_items( {5, 6}, {3, 4}, {1, 2}, {7, 8}, )); cvec_ip_sort(&pairs1); + c_foreach (i, cvec_ip, pairs1) printf("(%d %d) ", i.item->x, i.item->y); puts(""); @@ -99,14 +95,14 @@ int main(void) { // CLIST PAIR - clist_ip pairs2 = clist_init; - c_push(&pairs2, clist_ip, c_items( + c_init(clist_ip, pairs2, c_items( {5, 6}, {3, 4}, {1, 2}, {7, 8}, )); clist_ip_sort(&pairs2); + c_foreach (i, clist_ip, pairs2) printf("(%d %d) ", i.item->value.x, i.item->value.y); puts(""); diff --git a/examples/phonebook.c b/examples/phonebook.c new file mode 100644 index 00000000..15df04e3 --- /dev/null +++ b/examples/phonebook.c @@ -0,0 +1,72 @@ +// The MIT License (MIT) +// Copyright (c) 2018 Maksim Andrianov +// +// Permission is hereby granted, free of charge, to any person obtaining a copy +// of this software and associated documentation files (the "Software"), to +// deal in the Software without restriction, including without limitation the +// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or +// sell copies of the Software, and to permit persons to whom the Software is +// furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be included in +// all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +// IN THE SOFTWARE. + +// Program to emulates the phone book. + +#include +#include +#include + +declare_cmap_str(); + +void print_phone_book(cmap_str phone_book) +{ + c_foreach (i, cmap_str, phone_book) + printf("%s\t- %s\n", i.item->key.str, i.item->value.str); +} + +int main(int argc, char **argv) +{ + bool erased; + cmap_str phone_book = cmap_init; + c_push(&phone_book, cmap_str, c_items( + {"Lilia Friedman", "(892) 670-4739"}, + {"Tariq Beltran", "(489) 600-7575"}, + {"Laiba Juarez", "(303) 885-5692"}, + {"Elliott Mooney", "(945) 616-4482"}, + )); + + printf("Phone book:\n"); + print_phone_book(phone_book); + + cmap_try_emplace(str, &phone_book, "Zak Byers", cstr_make("(551) 396-1880")); + cmap_try_emplace(str, &phone_book, "Zak Byers", cstr_make("(551) 396-1990")); + + printf("\nPhone book after adding Zak Byers:\n"); + print_phone_book(phone_book); + + if (cmap_str_find(&phone_book, "Tariq Beltran") != NULL) + printf("\nTariq Beltran is in phone book\n"); + + erased = cmap_str_erase(&phone_book, "Tariq Beltran"); + erased = cmap_str_erase(&phone_book, "Elliott Mooney"); + + printf("\nPhone book after erasing Tariq and Elliott:\n"); + print_phone_book(phone_book); + + cmap_str_put(&phone_book, "Zak Byers", "(555) 396-188"); + + printf("\nPhone book after update phone of Zak Byers:\n"); + print_phone_book(phone_book); + + cmap_str_destroy(&phone_book); + puts("done"); +} \ No newline at end of file diff --git a/examples/priority.c b/examples/priority.c index 7dfff7da..2451d2d2 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -1,34 +1,35 @@ #include #include +#include #include #include #include declare_cvec(i, int64_t); -declare_cvec_pqueue(i, >); // min-heap (increasing values) +declare_cpqueue(i, >, cvec); // min-heap (increasing values) int main() { - size_t N = 100000000; + size_t N = 10000000; crand_rng64_t pcg = crand_rng64_init(time(NULL)); crand_uniform_i64_t dist = crand_uniform_i64_init(pcg, 0, N * 10); - cvec_i heap = cvec_init; + cpqueue_i heap = cpqueue_i_init(); // Push ten million random numbers to priority queue for (int i=0; inext->value #define clist_back(list) (list).last->value -#define clist_empty(list) ((list).last == NULL) #define declare_clist_7(tag, Value, valueDestroy, RawValue, valueCompareRaw, valueToRaw, valueFromRaw) \ @@ -96,6 +96,11 @@ \ 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);} \ + STC_INLINE Value \ + clist_##tag##_value_from_raw(RawValue rawValue) {return valueFromRaw(rawValue);} \ + \ STC_API void \ clist_##tag##_destroy(clist_##tag* self); \ STC_INLINE void \ diff --git a/stc/cmap.h b/stc/cmap.h index 86ed5f75..9d9589e0 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -54,6 +54,7 @@ int main(void) { #include "cdefs.h" #define cmap_init {NULL, NULL, 0, 0, 0.85f, 0.15f} +#define cmap_empty(m) ((m).size == 0) #define cmap_size(m) ((size_t) (m).size) #define cmap_bucket_count(m) ((size_t) (m).bucket_count) #define cset_init cmap_init @@ -179,6 +180,8 @@ typedef struct { \ \ STC_INLINE ctype##_##tag \ ctype##_##tag##_init(void) {ctype##_##tag m = cmap_init; return m;} \ +STC_INLINE bool \ +ctype##_##tag##_empty(ctype##_##tag m) {return m.size == 0;} \ STC_INLINE size_t \ ctype##_##tag##_size(ctype##_##tag m) {return (size_t) m.size;} \ STC_INLINE size_t \ diff --git a/stc/cpqueue.h b/stc/cpqueue.h index ed66f3cb..77dd8e62 100644 --- a/stc/cpqueue.h +++ b/stc/cpqueue.h @@ -26,65 +26,76 @@ #include #include declare_cvec(f, float); - declare_cvec_pqueue(f, >); // min-heap (increasing values) + declare_cpqueue(f, >, cvec); // 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); - cvec_f queue = cvec_init; + cpqueue_f queue = cpqueue_init; // Push ten million random numbers onto the queue. for (int i=0; i<10000000; ++i) - cvec_f_pqueue_push(&queue, crandom_uniform_f32(&gen, dist)); + cpqueue_f_push(&queue, crandom_uniform_f32(&gen, dist)); // Extract the 100 smallest. for (int i=0; i<100; ++i) { - printf("%f ", cvec_f_pqueue_top(&queue)); - cvec_f_pqueue_pop(&queue); + printf("%f ", *cpqueue_f_top(&queue)); + cpqueue_f_pop(&queue); } - cvec_f_destroy(&queue); + cpqueue_f_destroy(&queue); } */ #ifndef CPQUEUE__H__ #define CPQUEUE__H__ -#include "cvec.h" +#include "cdefs.h" -#define declare_cvec_pqueue(tag, cmpOpr) /* < or > */ \ +#define declare_cpqueue(tag, cmpOpr, type) /* 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; \ +STC_INLINE cpqueue_##tag \ +cpqueue_##tag##_init() {return type##_##tag##_init();} \ +STC_INLINE size_t \ +cpqueue_##tag##_size(cpqueue_##tag q) {return type##_##tag##_size(q);} \ +STC_INLINE bool \ +cpqueue_##tag##_empty(cpqueue_##tag q) {return type##_##tag##_empty(q);} \ +STC_INLINE void \ +cpqueue_##tag##_destroy(cpqueue_##tag* self) {type##_##tag##_destroy(self);} \ STC_API void \ -cvec_##tag##_pqueue_build(cvec_##tag* self); \ +cpqueue_##tag##_build(cpqueue_##tag* self); \ STC_API void \ -cvec_##tag##_pqueue_erase(cvec_##tag* self, size_t i); \ -STC_INLINE cvec_##tag##_value_t \ -cvec_##tag##_pqueue_top(cvec_##tag* self) {return self->data[0];} \ +cpqueue_##tag##_erase(cpqueue_##tag* self, size_t i); \ +STC_INLINE cpqueue_##tag##_value_t* \ +cpqueue_##tag##_top(cpqueue_##tag* self) {return &self->data[0];} \ STC_INLINE void \ -cvec_##tag##_pqueue_pop(cvec_##tag* self) {cvec_##tag##_pqueue_erase(self, 0);} \ +cpqueue_##tag##_pop(cpqueue_##tag* self) {cpqueue_##tag##_erase(self, 0);} \ STC_API void \ -cvec_##tag##_pqueue_push_v(cvec_##tag* self, cvec_##tag##_value_t value); \ +cpqueue_##tag##_push_v(cpqueue_##tag* self, cpqueue_##tag##_value_t value); \ STC_INLINE void \ -cvec_##tag##_pqueue_push(cvec_##tag* self, cvec_##tag##_rawvalue_t rawValue) { \ - cvec_##tag##_pqueue_push_v(self, cvec_##tag##_value_from_raw(rawValue)); \ +cpqueue_##tag##_push(cpqueue_##tag* self, cpqueue_##tag##_rawvalue_t rawValue) { \ + cpqueue_##tag##_push_v(self, type##_##tag##_value_from_raw(rawValue)); \ } \ STC_API void \ -cvec_##tag##_pqueue_push_n(cvec_##tag *self, const cvec_##tag##_input_t in[], size_t size); \ +cpqueue_##tag##_push_n(cpqueue_##tag *self, const cpqueue_##tag##_input_t in[], size_t size); \ \ -implement_cvec_pqueue(tag, cmpOpr) \ -typedef cvec_##tag##_value_t cvec_##tag##_pqueue_input_t +implement_cpqueue(tag, cmpOpr, type) /* -------------------------- IMPLEMENTATION ------------------------- */ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define implement_cvec_pqueue(tag, cmpOpr) \ +#define implement_cpqueue(tag, cmpOpr, type) \ \ STC_INLINE void \ -_cvec_##tag##_pqueue_sift_down(cvec_##tag##_value_t* arr, size_t i, size_t n) { \ +_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 && cvec_##tag##_value_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ + if (c < n && type##_##tag##_value_compare(&arr[c], &arr[c + 1]) cmpOpr 0) \ ++c; \ - if (cvec_##tag##_value_compare(&arr[r], &arr[c]) cmpOpr 0) { \ - cvec_##tag##_value_t t = arr[r]; arr[r] = arr[c]; arr[r = c] = t; \ + if (type##_##tag##_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; \ c <<= 1; \ @@ -92,38 +103,39 @@ _cvec_##tag##_pqueue_sift_down(cvec_##tag##_value_t* arr, size_t i, size_t n) { } \ \ STC_API void \ -cvec_##tag##_pqueue_build(cvec_##tag* self) { \ - size_t n = cvec_size(*self); \ - cvec_##tag##_value_t *arr = self->data - 1; \ +cpqueue_##tag##_build(cpqueue_##tag* self) { \ + size_t n = cpqueue_##tag##_size(*self); \ + cpqueue_##tag##_value_t *arr = self->data - 1; \ for (size_t k = n >> 1; k != 0; --k) \ - _cvec_##tag##_pqueue_sift_down(arr, k, n); \ + _cpqueue_##tag##_sift_down(arr, k, n); \ } \ \ STC_API void \ -cvec_##tag##_pqueue_erase(cvec_##tag* self, size_t i) { \ - size_t n = cvec_size(*self) - 1; \ +cpqueue_##tag##_erase(cpqueue_##tag* self, size_t i) { \ + size_t n = cpqueue_##tag##_size(*self) - 1; \ self->data[i] = self->data[n]; \ - cvec_##tag##_pop_back(self); \ - _cvec_##tag##_pqueue_sift_down(self->data - 1, i + 1, n); \ + type##_##tag##_pop_back(self); \ + _cpqueue_##tag##_sift_down(self->data - 1, i + 1, n); \ } \ \ STC_API void \ -cvec_##tag##_pqueue_push_v(cvec_##tag* self, cvec_##tag##_value_t value) { \ - cvec_##tag##_push_back(self, value); /* sift-up the value */ \ - size_t n = cvec_size(*self), c = n; \ - cvec_##tag##_value_t *arr = self->data - 1; \ - for (; c > 1 && cvec_##tag##_value_compare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ +cpqueue_##tag##_push_v(cpqueue_##tag* self, cpqueue_##tag##_value_t value) { \ + type##_##tag##_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) \ arr[c] = arr[c >> 1]; \ if (c != n) arr[c] = value; \ } \ STC_API void \ -cvec_##tag##_pqueue_push_n(cvec_##tag *self, const cvec_##tag##_input_t in[], size_t size) { \ - cvec_##tag##_reserve(self, cvec_size(*self) + size); \ - for (size_t i=0; i