From fb25143685df32ed91b84da9fb7f2e821ed7daaf Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 26 Mar 2021 07:11:32 +0100 Subject: Changed cpque declaration to using_cpque(X, Value, valueCompare), and valueCompare optional: more consistent with STC conventions. --- README.md | 4 +- benchmarks/cpque_benchmark.cpp | 2 +- docs/cpque_api.md | 11 +++-- examples/cpque.c | 16 ++++---- examples/inits.c | 4 +- examples/priority.c | 2 +- examples/stc_astar.c | 92 +++++++++++++++++++++--------------------- stc/ccommon.h | 4 +- stc/cpque.h | 21 +++++----- 9 files changed, 77 insertions(+), 79 deletions(-) diff --git a/README.md b/README.md index 9c26dc70..1af76f2f 100644 --- a/README.md +++ b/README.md @@ -1,7 +1,7 @@ ![Standard Template Containers](docs/pics/containers.jpg) -STC - Standard Template Containers -================================== +STC - Standard Template Containers for C +======================================== Introduction ------------ diff --git a/benchmarks/cpque_benchmark.cpp b/benchmarks/cpque_benchmark.cpp index d3c00803..c8d327ff 100644 --- a/benchmarks/cpque_benchmark.cpp +++ b/benchmarks/cpque_benchmark.cpp @@ -5,7 +5,7 @@ #include using_cvec(f, float); -using_cpque(f, cvec_f, >); +using_cpque(f, cvec_f, -c_default_compare); int main() { diff --git a/docs/cpque_api.md b/docs/cpque_api.md index 313a0e92..822b4ad5 100644 --- a/docs/cpque_api.md +++ b/docs/cpque_api.md @@ -10,13 +10,12 @@ See the c++ class [std::priority_queue](https://en.cppreference.com/w/cpp/contai ```c #include -using_cpque(X, ctype); // default dir = `<` : max-heap -using_cpque(X, ctype, dir); // uses valueCompare from ctype -using_cpque(X, ctype, dir, valueCompare); +using_cpque(X, ctype); // uses valueCompare from ctype +using_cpque(X, ctype, valueCompare); ``` The macro `using_cpque()` must be instantiated in the global scope. **cpque** uses normally **cvec_X** -or **cdeq_X** as underlying implementation, specified as `ctype`. The *dir* must be given as -`<` or `>`, specifying *max-heap* or *min-heap* for the priority queue. +or **cdeq_X** as underlying implementation, specified as `ctype`. The *valueCompare* can be specified +to control the order in the priority queue. By default, the function *`ctype`_value_compare(x, y)* from the underlying vector type is used for comparing values (priorities). `X` is a type tag name and will affect the names of all cpque types and methods. @@ -61,7 +60,7 @@ cpque_X_value_t cpque_X_value_clone(cpque_X_value_t val); #include using_cvec(i, int64_t); -using_cpque(i, cvec_i, >); // adaptor type, '>' = min-heap +using_cpque(i, cvec_i, -c_default_compare); // min-heap int main() { diff --git a/examples/cpque.c b/examples/cpque.c index ae869832..f9de44f1 100644 --- a/examples/cpque.c +++ b/examples/cpque.c @@ -4,12 +4,12 @@ // Implements c++ example: https://en.cppreference.com/w/cpp/container/priority_queue using_cvec(i, int); -using_cpque(imax, cvec_i); -using_cpque(imin, cvec_i, >); +#define imix_less(x, y) ((*(x) ^ 1) < (*(y) ^ 1)) +#define imix_cmp(x, y) c_less_compare(imix_less, x, y) -#define myless(left, right) ((left ^ 1) < (right ^ 1)) -static int cmp(const int *x, const int *y) { return myless(*y, *x) - myless(*x, *y); } -using_cpque(imix, cvec_i, <, cmp); +using_cpque(imax, cvec_i); +using_cpque(imin, cvec_i, -c_default_compare); +using_cpque(imix, cvec_i, imix_cmp); #define PRINT_Q(Q) \ void print_##Q(Q q) { \ @@ -37,13 +37,13 @@ int main() { print_cpque_imax(q); - cpque_imin q2 = cpque_imin_init(); + cpque_imin q2 = cpque_imin_init(); cpque_imin_emplace_n(&q2, data, c_arraylen(data)); print_cpque_imin(q2); - // Using myless cmp to compare elements. - cpque_imix q3 = cpque_imix_init(); + // Using imix_less to compare elements. + cpque_imix q3 = cpque_imix_init(); c_forrange (n, c_arraylen(data)) cpque_imix_push(&q3, n); diff --git a/examples/inits.c b/examples/inits.c index 23c7b551..26518e33 100644 --- a/examples/inits.c +++ b/examples/inits.c @@ -17,7 +17,7 @@ inline static int ipair_compare(const ipair_t* a, const ipair_t* b) { using_cvec(ip, ipair_t, ipair_compare); using_clist(ip, ipair_t, ipair_compare); using_cvec(f, float); -using_cpque(f, cvec_f, >); +using_cpque(f, cvec_f); int main(void) { @@ -34,7 +34,7 @@ int main(void) cpque_f_make_heap(&floats); c_emplace_items(&floats, cpque_f, {40.0f, 20.0f, 50.0f, 30.0f, 10.0f}); - // sorted: + puts("\npop and show high priorites first:"); while (! cpque_f_empty(floats)) { printf("%.1f ", *cpque_f_top(&floats)); cpque_f_pop(&floats); diff --git a/examples/priority.c b/examples/priority.c index 10e2f32a..ed7db584 100644 --- a/examples/priority.c +++ b/examples/priority.c @@ -7,7 +7,7 @@ #include using_cvec(i, int64_t); -using_cpque(i, cvec_i, >); // min-heap (increasing values) +using_cpque(i, cvec_i, -c_default_compare); // min-heap (increasing values) int main() { size_t N = 10000000; diff --git a/examples/stc_astar.c b/examples/stc_astar.c index d096c9fc..c22af8a8 100644 --- a/examples/stc_astar.c +++ b/examples/stc_astar.c @@ -17,42 +17,42 @@ typedef struct { } MazePoint; MazePoint -mpoint_init(int x, int y, int width) +mpnt_init(int x, int y, int width) { MazePoint p = { x, y, 0, width }; return p; } int -mpoint_compare_priority(const MazePoint* a, const MazePoint* b) +mpnt_compare_priority(const MazePoint* a, const MazePoint* b) { //return 0; // NB! gives 14 steps shorter path!? hmm.. - return (a->priorty > b->priorty) - (a->priorty < b->priorty); + return c_default_compare(&b->priorty, &a->priorty); // note: high priority is low cost } int -mpoint_equal(MazePoint* a, MazePoint* b) +mpnt_equal(MazePoint* a, MazePoint* b) { return a->x == b->x && a->y == b->y; } MazePoint -mpoint_from(cstr maze, const char* c, int width) +mpnt_from(cstr maze, const char* c, int width) { int index = cstr_find(maze, c); - return mpoint_init(index % width, index / width, width); + return mpnt_init(index % width, index / width, width); } int -mpoint_index(const MazePoint* p) +mpnt_index(const MazePoint* p) { return p->x + p->width * p->y; } int -mpoint_key_compare(const MazePoint* a, const MazePoint* b) +mpnt_key_compare(const MazePoint* a, const MazePoint* b) { - int i = mpoint_index(a); - int j = mpoint_index(b); + int i = mpnt_index(a); + int j = mpnt_index(b); return (i > j) - (i < j); } @@ -66,29 +66,29 @@ typedef struct { MazePoint b; } MazeStep; -using_cdeq(mp, MazePoint, mpoint_compare_priority); -using_cpque(mp, cdeq_mp, >); -using_csmap(ms, MazePoint, MazePoint, mpoint_key_compare); // step -using_csmap(mc, MazePoint, int, mpoint_key_compare); // cost +using_cdeq(pnt, MazePoint, c_no_compare); +using_cpque(pnt, cdeq_pnt, mpnt_compare_priority); +using_csmap(step, MazePoint, MazePoint, mpnt_key_compare); +using_csmap(cost, MazePoint, int, mpnt_key_compare); -cdeq_mp +cdeq_pnt astar(cstr maze, int width) { - MazePoint start = mpoint_from(maze, "@", width); - MazePoint goal = mpoint_from(maze, "!", width); - cpque_mp frontier = cpque_mp_init(); - csmap_ms came_from = csmap_ms_init(); - csmap_mc cost_so_far = csmap_mc_init(); + MazePoint start = mpnt_from(maze, "@", width); + MazePoint goal = mpnt_from(maze, "!", width); + cpque_pnt frontier = cpque_pnt_init(); + csmap_step came_from = csmap_step_init(); + csmap_cost cost_so_far = csmap_cost_init(); - cpque_mp_push(&frontier, start); - csmap_mc_emplace(&cost_so_far, start, 0); + cpque_pnt_push(&frontier, start); + csmap_cost_insert(&cost_so_far, start, 0); - while (!cpque_mp_empty(frontier)) + while (!cpque_pnt_empty(frontier)) { - MazePoint current = *cpque_mp_top(&frontier); - cpque_mp_pop(&frontier); - if (mpoint_equal(¤t, &goal)) + MazePoint current = *cpque_pnt_top(&frontier); + cpque_pnt_pop(&frontier); + if (mpnt_equal(¤t, &goal)) break; MazePoint deltas[] = { { -1, +1, 0, width }, { 0, +1, 0, width }, { 1, +1, 0, width }, @@ -99,33 +99,33 @@ astar(cstr maze, int width) c_forrange (i, c_arraylen(deltas)) { MazePoint delta = deltas[i]; - MazePoint next = mpoint_init(current.x + delta.x, current.y + delta.y, width); - int new_cost = *csmap_mc_at(&cost_so_far, current); - if (maze.str[mpoint_index(&next)] != '#') + MazePoint next = mpnt_init(current.x + delta.x, current.y + delta.y, width); + int new_cost = *csmap_cost_at(&cost_so_far, current); + if (maze.str[mpnt_index(&next)] != '#') { - csmap_mc_value_t* cost = csmap_mc_find(&cost_so_far, next).ref; + csmap_cost_value_t* cost = csmap_cost_find(&cost_so_far, next).ref; if (!cost || new_cost < cost->second) { - csmap_mc_emplace_or_assign(&cost_so_far, next, new_cost); // update (put) + csmap_cost_put(&cost_so_far, next, new_cost); // update next.priorty = new_cost + abs(goal.x - next.x) + abs(goal.y - next.y); - cpque_mp_push(&frontier, next); - csmap_ms_emplace_or_assign(&came_from, next, current); + cpque_pnt_push(&frontier, next); + csmap_step_put(&came_from, next, current); } } } } MazePoint current = goal; - cdeq_mp path = cdeq_mp_init(); + cdeq_pnt path = cdeq_pnt_init(); - while(!mpoint_equal(¤t, &start)) + while(!mpnt_equal(¤t, &start)) { - cdeq_mp_push_front(&path, current); - current = *csmap_ms_at(&came_from, current); + cdeq_pnt_push_front(&path, current); + current = *csmap_step_at(&came_from, current); } - cdeq_mp_push_front(&path, start); - cpque_mp_del(&frontier); - csmap_ms_del(&came_from); - csmap_mc_del(&cost_so_far); + cdeq_pnt_push_front(&path, start); + cpque_pnt_del(&frontier); + csmap_step_del(&came_from); + csmap_cost_del(&cost_so_far); return path; } @@ -157,14 +157,14 @@ main(void) "# # # # # # #\n" "#########################################################################\n"); int width = cstr_find(maze, "\n") + 1; - cdeq_mp path = astar(maze, width); + cdeq_pnt path = astar(maze, width); - printf("length: %zu\n", cdeq_mp_size(path)); + printf("length: %zu\n", cdeq_pnt_size(path)); - c_foreach (it, cdeq_mp, path) - maze.str[mpoint_index(it.ref)] = 'o'; + c_foreach (it, cdeq_pnt, path) + maze.str[mpnt_index(it.ref)] = 'x'; printf("%s", maze.str); cstr_del(&maze); - cdeq_mp_del(&path); + cdeq_pnt_del(&path); } \ No newline at end of file diff --git a/stc/ccommon.h b/stc/ccommon.h index 29790333..ec01d731 100644 --- a/stc/ccommon.h +++ b/stc/ccommon.h @@ -65,6 +65,7 @@ #define c_container_of(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member))) +#define c_struct(S) typedef struct S S; struct S #define c_new(...) c_MACRO_OVERLOAD(c_new, __VA_ARGS__) #define c_new_1(T) ((T *) c_malloc(sizeof(T))) #define c_new_2(T, n) ((T *) c_malloc(sizeof(T)*(n))) @@ -78,9 +79,10 @@ #define c_swap(T, x, y) do { T _c_t = x; x = y; y = _c_t; } while (0) #define c_arraylen(a) (sizeof (a)/sizeof (a)[0]) -#define c_default_compare(x, y) (c_default_less(y, x) - c_default_less(x, y)) +#define c_default_compare(x, y) c_less_compare(c_default_less, x, y) #define c_default_less(x, y) (*(x) < *(y)) #define c_no_compare(x, y) (assert(!"c_no_compare() called"), 0) +#define c_less_compare(less, x, y) (less(y, x) - less(x, y)) #define c_default_equals(x, y) (*(x) == *(y)) #define c_trivial_equals(x, y) (memcmp(x, y, sizeof *(x)) == 0) diff --git a/stc/cpque.h b/stc/cpque.h index abb14565..8e08724f 100644 --- a/stc/cpque.h +++ b/stc/cpque.h @@ -26,7 +26,7 @@ #include #include using_cvec(f, float); - using_cpque(f, cvec_f, >); // min-heap (increasing values) + using_cpque(f, cvec_f, -c_default_compare); // min-heap (increasing values) int main() { stc64_t rng = stc64_init(1234); @@ -52,12 +52,9 @@ #define using_cpque(...) c_MACRO_OVERLOAD(using_cpque, __VA_ARGS__) #define using_cpque_2(X, ctype) \ - using_cpque_3(X, ctype, <) + using_cpque_3(X, ctype, ctype##_value_compare) -#define using_cpque_3(X, ctype, cmpOpr) /* cmpOpr: < or > */ \ - using_cpque_4(X, ctype, cmpOpr, ctype##_value_compare) - -#define using_cpque_4(X, ctype, cmpOpr, valueCompare) \ +#define using_cpque_3(X, ctype, valueCompare) \ typedef ctype##_t cpque_##X; \ typedef ctype##_value_t cpque_##X##_value_t; \ typedef ctype##_rawvalue_t cpque_##X##_rawvalue_t; \ @@ -94,7 +91,7 @@ STC_API void \ cpque_##X##_emplace_n(cpque_##X *self, const cpque_##X##_rawvalue_t arr[], size_t size); \ \ - _c_implement_cpque(X, ctype, cmpOpr, valueCompare) \ + _c_implement_cpque(X, ctype, valueCompare) \ typedef cpque_##X cpque_##X##_t @@ -102,14 +99,14 @@ #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -#define _c_implement_cpque(X, ctype, cmpOpr, valueCompare) \ +#define _c_implement_cpque(X, ctype, valueCompare) \ \ STC_INLINE void \ _cpque_##X##_sift_down(cpque_##X##_value_t* arr, size_t i, size_t n) { \ size_t r = i, c = i << 1; \ while (c <= n) { \ - c += (c < n && valueCompare(&arr[c], &arr[c + 1]) cmpOpr 0); \ - if (valueCompare(&arr[r], &arr[c]) cmpOpr 0) { \ + c += (c < n && valueCompare(&arr[c], &arr[c + 1]) < 0); \ + if (valueCompare(&arr[r], &arr[c]) < 0) { \ cpque_##X##_value_t tmp = arr[r]; arr[r] = arr[c]; arr[r = c] = tmp; \ } else \ return; \ @@ -138,7 +135,7 @@ ctype##_push_back(self, value); /* sift-up the value */ \ size_t n = cpque_##X##_size(*self), c = n; \ cpque_##X##_value_t *arr = self->data - 1; \ - for (; c > 1 && valueCompare(&arr[c >> 1], &value) cmpOpr 0; c >>= 1) \ + for (; c > 1 && valueCompare(&arr[c >> 1], &value) < 0; c >>= 1) \ arr[c] = arr[c >> 1]; \ if (c != n) arr[c] = value; \ } \ @@ -148,7 +145,7 @@ } #else -#define _c_implement_cpque(X, ctype, cmpOpr, valueCompare) +#define _c_implement_cpque(X, ctype, valueCompare) #endif #endif -- cgit v1.2.3