From fa2871406affad4d96a54554f80c7418a716b98c Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sun, 12 Sep 2021 23:04:33 +0200 Subject: Renamed input macro i_module to i_prefix. Replaced astar.c example. Now supports that user defines i_prefix. --- README.md | 61 ++++++++-------- examples/astar.c | 167 ++++++++++++++++++++++++++++++++++++++++++++ examples/stc_astar.c | 184 ------------------------------------------------- include/stc/cdeq.h | 4 +- include/stc/clist.h | 4 +- include/stc/cmap.h | 4 +- include/stc/cpque.h | 7 +- include/stc/cqueue.h | 4 +- include/stc/cset.h | 4 +- include/stc/csmap.h | 4 +- include/stc/csset.h | 4 +- include/stc/cstack.h | 6 +- include/stc/cvec.h | 4 +- include/stc/template.h | 4 +- 14 files changed, 227 insertions(+), 234 deletions(-) create mode 100644 examples/astar.c delete mode 100644 examples/stc_astar.c diff --git a/README.md b/README.md index 599762ef..b0e45236 100644 --- a/README.md +++ b/README.md @@ -90,7 +90,6 @@ int Point_compare(const struct Point* a, const struct Point* b) { return cmp ? cmp : c_default_compare(&a->y, &b->y); } -#define i_tag i32 #define i_key int #include // unordered set @@ -99,71 +98,67 @@ int Point_compare(const struct Point* a, const struct Point* b) { #define i_cmp Point_compare #include // vector, struct as elements -#define i_tag i32 #define i_val int #include // deque of int -#define i_tag i32 #define i_val int #include // singly linked list -#define i_tag i32 #define i_val int #include -#define i_tag i32 #define i_key int #define i_val int #include // sorted map int main(void) { // define six containers with automatic call of init and del (destruction after scope exit) - c_forauto (cset_i32, set) + c_forauto (cset_int, set) c_forauto (cvec_pnt, vec) - c_forauto (cdeq_i32, deq) - c_forauto (clist_i32, lst) - c_forauto (cstack_i32, stk) - c_forauto (csmap_i32, map) + c_forauto (cdeq_int, deq) + c_forauto (clist_int, lst) + c_forauto (cstack_int, stk) + c_forauto (csmap_int, map) { // add some elements to each container - c_emplace(cset_i32, set, {10, 20, 30}); + c_emplace(cset_int, set, {10, 20, 30}); c_emplace(cvec_pnt, vec, { {10, 1}, {20, 2}, {30, 3} }); - c_emplace(cdeq_i32, deq, {10, 20, 30}); - c_emplace(clist_i32, lst, {10, 20, 30}); - c_emplace(cstack_i32, stk, {10, 20, 30}); - c_emplace(csmap_i32, map, { {20, 2}, {10, 1}, {30, 3} }); + c_emplace(cdeq_int, deq, {10, 20, 30}); + c_emplace(clist_int, lst, {10, 20, 30}); + c_emplace(cstack_int, stk, {10, 20, 30}); + c_emplace(csmap_int, map, { {20, 2}, {10, 1}, {30, 3} }); // add one more element to each container - cset_i32_insert(&set, 40); + cset_int_insert(&set, 40); cvec_pnt_push_back(&vec, (struct Point) {40, 4}); - cdeq_i32_push_front(&deq, 5); - clist_i32_push_front(&lst, 5); - cstack_i32_push(&stk, 40); - csmap_i32_insert(&map, 40, 4); + cdeq_int_push_front(&deq, 5); + clist_int_push_front(&lst, 5); + cstack_int_push(&stk, 40); + csmap_int_insert(&map, 40, 4); // find an element in each container - cset_i32_iter_t i1 = cset_i32_find(&set, 20); + cset_int_iter_t i1 = cset_int_find(&set, 20); cvec_pnt_iter_t i2 = cvec_pnt_find(&vec, (struct Point) {20, 2}); - cdeq_i32_iter_t i3 = cdeq_i32_find(&deq, 20); - clist_i32_iter_t i4 = clist_i32_find(&lst, 20); - csmap_i32_iter_t i5 = csmap_i32_find(&map, 20); + cdeq_int_iter_t i3 = cdeq_int_find(&deq, 20); + clist_int_iter_t i4 = clist_int_find(&lst, 20); + csmap_int_iter_t i5 = csmap_int_find(&map, 20); printf("\nFound: %d, (%g, %g), %d, %d, [%d: %d]\n", *i1.ref, i2.ref->x, i2.ref->y, *i3.ref, *i4.ref, i5.ref->first, i5.ref->second); // erase the elements found - cset_i32_erase_at(&set, i1); + cset_int_erase_at(&set, i1); cvec_pnt_erase_at(&vec, i2); - cdeq_i32_erase_at(&deq, i3); - clist_i32_erase_at(&lst, i4); - csmap_i32_erase_at(&map, i5); + cdeq_int_erase_at(&deq, i3); + clist_int_erase_at(&lst, i4); + csmap_int_erase_at(&map, i5); printf("After erasing elements found:"); - printf("\n set:"); c_foreach (i, cset_i32, set) printf(" %d", *i.ref); + printf("\n set:"); c_foreach (i, cset_int, set) printf(" %d", *i.ref); printf("\n vec:"); c_foreach (i, cvec_pnt, vec) printf(" (%g, %g)", i.ref->x, i.ref->y); - printf("\n deq:"); c_foreach (i, cdeq_i32, deq) printf(" %d", *i.ref); - printf("\n lst:"); c_foreach (i, clist_i32, lst) printf(" %d", *i.ref); - printf("\n stk:"); c_foreach (i, cstack_i32, stk) printf(" %d", *i.ref); - printf("\n map:"); c_foreach (i, csmap_i32, map) printf(" [%d: %d]", i.ref->first, + printf("\n deq:"); c_foreach (i, cdeq_int, deq) printf(" %d", *i.ref); + printf("\n lst:"); c_foreach (i, clist_int, lst) printf(" %d", *i.ref); + printf("\n stk:"); c_foreach (i, cstack_int, stk) printf(" %d", *i.ref); + printf("\n map:"); c_foreach (i, csmap_int, map) printf(" [%d: %d]", i.ref->first, i.ref->second); } } diff --git a/examples/astar.c b/examples/astar.c new file mode 100644 index 00000000..5571c306 --- /dev/null +++ b/examples/astar.c @@ -0,0 +1,167 @@ +// +// -- An A* pathfinder inspired by the excellent tutorial at Red Blob Games -- +// +// This is a reimplementation of the CTL example to STC: +// https://github.com/glouw/ctl/blob/master/examples/astar.c +// https://www.redblobgames.com/pathfinding/a-star/introduction.html + +#include +#include + +typedef struct +{ + int x; + int y; + int priorty; + int width; +} +point; + +point +point_init(int x, int y, int width) +{ + return (point) { x, y, 0, width }; +} + +int +point_compare_priority(const point* a, const point* b) +{ + return a->priorty < b->priorty; +} + +int +point_equal(const point* a, const point* b) +{ + return a->x == b->x && a->y == b->y; +} + +point +point_from(const cstr* maze, const char* c, int width) +{ + int index = cstr_find(*maze, c); + return point_init(index % width, index / width, width); +} + +int +point_index(const point* p) +{ + return p->x + p->width * p->y; +} + +int +point_key_compare(const point* a, const point* b) +{ + int i = point_index(a); + int j = point_index(b); + return (i == j) ? 0 : (i < j) ? -1 : 1; +} + +#define i_val point +#define i_cmp point_compare_priority +#include + +#define i_val point +#define i_cmp c_no_compare +#include + +#define i_tag pcost +#define i_key point +#define i_val int +#define i_cmp point_key_compare +#include + +#define i_tag pstep +#define i_key point +#define i_val point +#define i_cmp point_key_compare +#include + +cdeq_point +astar(cstr* maze, int width) +{ + cdeq_point path = cdeq_point_init(); + + c_forauto (cpque_point, front) + c_forauto (csmap_pstep, from) + c_forauto (csmap_pcost, costs) + { + point start = point_from(maze, "@", width); + point goal = point_from(maze, "!", width); + csmap_pcost_insert(&costs, start, 0); + cpque_point_push(&front, start); + while (!cpque_point_empty(front)) + { + point current = *cpque_point_top(&front); + cpque_point_pop(&front); + if (point_equal(¤t, &goal)) + break; + point deltas[] = { + { -1, +1, 0, width }, { 0, +1, 0, width }, { 1, +1, 0, width }, + { -1, 0, 0, width }, /* ~ ~ ~ ~ ~ ~ ~ */ { 1, 0, 0, width }, + { -1, -1, 0, width }, { 0, -1, 0, width }, { 1, -1, 0, width }, + }; + for (size_t i = 0; i < c_arraylen(deltas); i++) + { + point delta = deltas[i]; + point next = point_init(current.x + delta.x, current.y + delta.y, width); + int new_cost = *csmap_pcost_at(&costs, current); + if (maze->str[point_index(&next)] != '#') + { + csmap_pcost_value_t *cost = csmap_pcost_get(&costs, next); + if (cost == NULL || new_cost < cost->second) + { + csmap_pcost_insert(&costs, next, new_cost); + next.priorty = new_cost + abs(goal.x - next.x) + abs(goal.y - next.y); + cpque_point_push(&front, next); + csmap_pstep_insert(&from, next, current); + } + } + } + } + point current = goal; + while (!point_equal(¤t, &start)) + { + cdeq_point_push_front(&path, current); + current = *csmap_pstep_at(&from, current); + } + cdeq_point_push_front(&path, start); + } + return path; +} + +int +main(void) +{ + c_forvar (cstr maze = cstr_lit( + "#########################################################################\n" + "# # # # # # #\n" + "# # ######### # ##### ######### ##### ##### ##### # ! #\n" + "# # # # # # # # # #\n" + "######### # ######### ######### ##### # # # ######### #\n" + "# # # # # # # # # # #\n" + "# # ############# # # ######### ##### # ######### # #\n" + "# # # # # # # # # #\n" + "# ############# ##### ##### # ##### ######### # ##### #\n" + "# # # # # # # # # #\n" + "# ##### ##### # ##### # ######### # # # #############\n" + "# # # # # # # # # # # #\n" + "############# # # # ######### # ##### # ##### ##### #\n" + "# # # # # # # # # #\n" + "# ##### # ######### ##### # ##### ##### ############# #\n" + "# # # # # # # # # #\n" + "# # ######### # ##### ######### # # ############# # #\n" + "# # # # # # # # # # #\n" + "# ######### # # # ##### ######### ######### # #########\n" + "# # # # # # # # # #\n" + "# @ # ##### ##### ##### ######### ##### # ######### # #\n" + "# # # # # # #\n" + "#########################################################################\n"), cstr_del(&maze)) + { + int width = cstr_find(maze, "\n") + 1; + c_forvar (cdeq_point path = astar(&maze, width), cdeq_point_del(&path)) + { + c_foreach (it, cdeq_point, path) maze.str[point_index(it.ref)] = 'x'; + printf("%s", maze.str); + } + } +} diff --git a/examples/stc_astar.c b/examples/stc_astar.c deleted file mode 100644 index 4f5075a1..00000000 --- a/examples/stc_astar.c +++ /dev/null @@ -1,184 +0,0 @@ -// -// -- An A* pathfinder inspired by the excellent tutorial at Red Blob Games -- -// -// See: -// https://www.redblobgames.com/pathfinding/a-star/introduction.html - -#include -#include - -typedef struct { - int x, y; - int priorty, width; -} MazePoint; - -MazePoint -mpnt_init(int x, int y, int width) -{ - return c_make(MazePoint){ x, y, 0, width }; -} - -int -mpnt_compare_priority(const MazePoint* a, const MazePoint* b) -{ - //return 0; // NB! gives 14 steps shorter path!? hmm.. - return c_default_compare(&b->priorty, &a->priorty); // note: high priority is low cost -} - -int -mpnt_equal(MazePoint* a, MazePoint* b) -{ - return a->x == b->x && a->y == b->y; -} - -MazePoint -mpnt_from(cstr maze, const char* c, int width) -{ - int index = cstr_find(maze, c); - return mpnt_init(index % width, index / width, width); -} - -int -mpnt_index(const MazePoint* p) -{ - return p->x + p->width * p->y; -} - -int -mpnt_key_compare(const MazePoint* a, const MazePoint* b) -{ - int i = mpnt_index(a); - int j = mpnt_index(b); - return (i > j) - (i < j); -} - -typedef struct { - MazePoint point; - int value; -} MazeCost; - -typedef struct { - MazePoint a; - MazePoint b; -} MazeStep; - -#define i_tag pnt -#define i_val MazePoint -#define i_cmp c_no_compare -#include - -#define i_tag pnt -#define i_val MazePoint -#define i_cmp mpnt_compare_priority -#include - -#define i_tag step -#define i_key MazePoint -#define i_val MazePoint -#define i_cmp mpnt_key_compare -#include - -#define i_tag cost -#define i_key MazePoint -#define i_val int -#define i_cmp mpnt_key_compare -#include - -cdeq_pnt -astar(cstr maze, int width) -{ - MazePoint start = mpnt_from(maze, "@", width); - MazePoint goal = mpnt_from(maze, "!", width); - - cdeq_pnt path = cdeq_pnt_init(); // returned - - cpque_pnt frontier = cpque_pnt_init(); - csmap_step came_from = csmap_step_init(); - csmap_cost cost_so_far = csmap_cost_init(); - c_fordefer (cpque_pnt_del(&frontier), - csmap_step_del(&came_from), - csmap_cost_del(&cost_so_far)) - { - cpque_pnt_push(&frontier, start); - csmap_cost_insert(&cost_so_far, start, 0); - - while (!cpque_pnt_empty(frontier)) - { - 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 }, - { -1, 0, 0, width }, /* ~ ~ ~ ~ ~ ~ ~ */ { 1, 0, 0, width }, - { -1, -1, 0, width }, { 0, -1, 0, width }, { 1, -1, 0, width }, - }; - - c_forrange (i, c_arraylen(deltas)) - { - MazePoint delta = deltas[i]; - 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_cost_value_t* cost = csmap_cost_find(&cost_so_far, next).ref; - if (!cost || new_cost < cost->second) - { - 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_pnt_push(&frontier, next); - csmap_step_put(&came_from, next, current); - } - } - } - } - MazePoint current = goal; - while(!mpnt_equal(¤t, &start)) - { - cdeq_pnt_push_front(&path, current); - current = *csmap_step_at(&came_from, current); - } - cdeq_pnt_push_front(&path, start); - } - return path; -} - -int -main(void) -{ - cstr maze = cstr_from( - "#########################################################################\n" - "# # # # # # #\n" - "# # ######### # ##### ######### ##### ##### ##### # ! #\n" - "# # # # # # # # # #\n" - "######### # ######### ######### ##### # # # ######### #\n" - "# # # # # # # # # # #\n" - "# # ############# # # ######### ##### # ######### # #\n" - "# # # # # # # # # #\n" - "# ############# ##### ##### # ##### ######### # ##### #\n" - "# # # # # # # # # #\n" - "# ##### ##### # ##### # ######### # # # #############\n" - "# # # # # # # # # # # #\n" - "############# # # # ######### # ##### # ##### ##### #\n" - "# # # # # # # # # #\n" - "# ##### # ######### ##### # ##### ##### ############# #\n" - "# # # # # # # # # #\n" - "# # ######### # ##### ######### # # ############# # #\n" - "# # # # # # # # # # #\n" - "# ######### # # # ##### ######### ######### # #########\n" - "# # # # # # # # # #\n" - "# @ # ##### ##### ##### ######### ##### # ######### # #\n" - "# # # # # # #\n" - "#########################################################################\n"); - int width = cstr_find(maze, "\n") + 1; - cdeq_pnt path = astar(maze, width); - - printf("length: %zu\n", cdeq_pnt_size(path)); - - c_foreach (it, cdeq_pnt, path) - maze.str[mpnt_index(it.ref)] = 'x'; - - printf("%s", maze.str); - cstr_del(&maze); - cdeq_pnt_del(&path); -} \ No newline at end of file diff --git a/include/stc/cdeq.h b/include/stc/cdeq.h index c6993427..21a6ece8 100644 --- a/include/stc/cdeq.h +++ b/include/stc/cdeq.h @@ -31,8 +31,8 @@ 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 +#ifndef i_prefix +#define i_prefix cdeq_ #endif #include "template.h" diff --git a/include/stc/clist.h b/include/stc/clist.h index 685601c4..bf96076c 100644 --- a/include/stc/clist.h +++ b/include/stc/clist.h @@ -81,7 +81,9 @@ _c_clist_complete_types(clist_VOID, dummy); #endif // CLIST_H_INCLUDED -#define i_module clist +#ifndef i_prefix +#define i_prefix clist_ +#endif #include "template.h" #if !defined i_fwd diff --git a/include/stc/cmap.h b/include/stc/cmap.h index a03d5c83..36417bc9 100644 --- a/include/stc/cmap.h +++ b/include/stc/cmap.h @@ -59,8 +59,8 @@ int main(void) { typedef struct { size_t idx; uint_fast8_t hx; } chash_bucket_t; #endif // CMAP_H_INCLUDED -#ifndef i_module -#define i_module cmap +#ifndef i_prefix +#define i_prefix cmap_ #define cx_MAP_ONLY c_true #define cx_SET_ONLY c_false #define cx_keyref(vp) (&(vp)->first) diff --git a/include/stc/cpque.h b/include/stc/cpque.h index 4f7e0003..e8f9c471 100644 --- a/include/stc/cpque.h +++ b/include/stc/cpque.h @@ -28,7 +28,10 @@ #include "forward.h" #endif -#define i_module cpque +#ifndef i_prefix +#define i_prefix cpque_ +#endif + #include "template.h" #if !defined i_fwd @@ -43,7 +46,7 @@ STC_API void cx_memb(_emplace_items)(Self *self, const cx_rawvalue_t arr[], size STC_API Self cx_memb(_clone)(Self q); STC_INLINE Self cx_memb(_init)(void) - { return (Self){0, 0, 0}; } + { return c_make(Self){0, 0, 0}; } STC_INLINE Self cx_memb(_with_capacity)(size_t cap) { Self out = {(cx_value_t *) c_malloc(cap*sizeof(cx_value_t)), 0, cap}; diff --git a/include/stc/cqueue.h b/include/stc/cqueue.h index 454913c1..f1d173e2 100644 --- a/include/stc/cqueue.h +++ b/include/stc/cqueue.h @@ -53,7 +53,9 @@ int main() { } */ -#define i_module cqueue +#ifndef i_prefix +#define i_prefix cqueue_ +#endif #define i_queue #define _push_back _push #define _pop_front _pop diff --git a/include/stc/cset.h b/include/stc/cset.h index ffdbca0d..2861ce89 100644 --- a/include/stc/cset.h +++ b/include/stc/cset.h @@ -39,7 +39,9 @@ int main(void) { } */ -#define i_module cset +#ifndef i_prefix +#define i_prefix cset_ +#endif #define cx_MAP_ONLY c_false #define cx_SET_ONLY c_true #define cx_keyref(vp) (vp) diff --git a/include/stc/csmap.h b/include/stc/csmap.h index 46408399..bae2ea96 100644 --- a/include/stc/csmap.h +++ b/include/stc/csmap.h @@ -59,8 +59,8 @@ struct csmap_rep { size_t root, disp, head, size, cap; void* nodes[]; }; #define _csmap_rep(self) c_container_of((self)->nodes, struct csmap_rep, nodes) #endif // CSMAP_H_INCLUDED -#ifndef i_module -#define i_module csmap +#ifndef i_prefix +#define i_prefix csmap_ #define cx_MAP_ONLY c_true #define cx_SET_ONLY c_false #define cx_keyref(vp) (&(vp)->first) diff --git a/include/stc/csset.h b/include/stc/csset.h index 44fbfa54..19cf147c 100644 --- a/include/stc/csset.h +++ b/include/stc/csset.h @@ -42,7 +42,9 @@ int main(void) { } */ -#define i_module csset +#ifndef i_prefix +#define i_prefix csset_ +#endif #define cx_MAP_ONLY c_false #define cx_SET_ONLY c_true #define cx_keyref(vp) (vp) diff --git a/include/stc/cstack.h b/include/stc/cstack.h index c0d89c78..043fbdc6 100644 --- a/include/stc/cstack.h +++ b/include/stc/cstack.h @@ -28,7 +28,9 @@ #include "forward.h" #endif -#define i_module cstack +#ifndef i_prefix +#define i_prefix cstack_ +#endif #include "template.h" #if !defined i_fwd @@ -37,7 +39,7 @@ cx_deftypes(_c_cstack_types, Self, i_val); typedef i_valraw cx_rawvalue_t; STC_INLINE Self cx_memb(_init)(void) - { return (Self){0, 0, 0}; } + { return c_make(Self){0, 0, 0}; } STC_INLINE Self cx_memb(_with_capacity)(size_t cap) { Self out = {(cx_value_t *) c_malloc(cap*sizeof(cx_value_t)), 0, cap}; diff --git a/include/stc/cvec.h b/include/stc/cvec.h index f9f62439..8d379b6e 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -67,7 +67,9 @@ struct cvec_rep { size_t size, cap; void* data[]; }; #define cvec_rep_(self) c_container_of((self)->data, struct cvec_rep, data) #endif // CVEC_H_INCLUDED -#define i_module cvec +#ifndef i_prefix +#define i_prefix cvec_ +#endif #include "template.h" #if !defined i_fwd diff --git a/include/stc/template.h b/include/stc/template.h index 9e183858..062f6939 100644 --- a/include/stc/template.h +++ b/include/stc/template.h @@ -26,7 +26,7 @@ #ifndef STC_TEMPLATE_H_INCLUDED #define STC_TEMPLATE_H_INCLUDED #define cx_memb(name) c_PASTE(Self, name) - #define Self c_PASTE3(i_module, _, i_tag) + #define Self c_PASTE(i_prefix, i_tag) // typedef container types defined in forward.h. VC requires c_EXPAND. #define cx_deftypes(macro, SELF, ...) c_EXPAND(macro(SELF, __VA_ARGS__)) @@ -128,7 +128,7 @@ #else // ------------------------------------------------------- -#undef i_module +#undef i_prefix #undef i_tag #undef f_tag #undef i_imp -- cgit v1.2.3