From c2966d1879c825cfaf0e7d6848a5da052ee4a038 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Sat, 18 Jul 2015 00:54:44 +1000 Subject: [PATCH] agar: Re-entrant Abstract Graph Algorithms New module Signed-off-by: David Gibson --- ccan/agar/LICENSE | 1 + ccan/agar/_info | 48 +++++++ ccan/agar/agar.c | 232 +++++++++++++++++++++++++++++++++ ccan/agar/agar.h | 73 +++++++++++ ccan/agar/test/api-adjacency.c | 86 ++++++++++++ ccan/agar/test/api-bfs.c | 106 +++++++++++++++ ccan/agar/test/api-dfs.c | 106 +++++++++++++++ ccan/agar/test/chain.c | 30 +++++ ccan/agar/test/error-graph.c | 55 ++++++++ ccan/agar/test/full.c | 45 +++++++ ccan/agar/test/grid.c | 81 ++++++++++++ ccan/agar/test/parallel.c | 62 +++++++++ ccan/agar/test/simple-graphr.h | 200 ++++++++++++++++++++++++++++ ccan/agar/test/traversal1.c | 114 ++++++++++++++++ ccan/agar/test/trivial.c | 36 +++++ 15 files changed, 1275 insertions(+) create mode 120000 ccan/agar/LICENSE create mode 100644 ccan/agar/_info create mode 100644 ccan/agar/agar.c create mode 100644 ccan/agar/agar.h create mode 100644 ccan/agar/test/api-adjacency.c create mode 100644 ccan/agar/test/api-bfs.c create mode 100644 ccan/agar/test/api-dfs.c create mode 100644 ccan/agar/test/chain.c create mode 100644 ccan/agar/test/error-graph.c create mode 100644 ccan/agar/test/full.c create mode 100644 ccan/agar/test/grid.c create mode 100644 ccan/agar/test/parallel.c create mode 100644 ccan/agar/test/simple-graphr.h create mode 100644 ccan/agar/test/traversal1.c create mode 100644 ccan/agar/test/trivial.c diff --git a/ccan/agar/LICENSE b/ccan/agar/LICENSE new file mode 120000 index 00000000..dc314eca --- /dev/null +++ b/ccan/agar/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1 \ No newline at end of file diff --git a/ccan/agar/_info b/ccan/agar/_info new file mode 100644 index 00000000..d62b2e54 --- /dev/null +++ b/ccan/agar/_info @@ -0,0 +1,48 @@ +#include "config.h" +#include +#include + +/** + * agar - Re-entrant Abstract Graph Algorithms + * + * This modules contains re-entrant versions of the graph algorithms + * in the aga module. + * + * The versions in the aga module require some node-local storage. + * This means that the calling code: + * a) Needs to actually allocate memory per node. That may or may + * not be natural depending on its internal representation. + * b) Multiple algorithms can't run at once (easily), since they all + * need to use the aga_node structures. + * + * This module provides versions without those restrictions, by + * allocating per-node storage itself for each run, and associating + * those with the caller's representation of nodes via a hash table. + * + * License: LGPL (v2.1 or any later version) + * Author: David Gibson + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/aga\n"); + printf("ccan/container_of\n"); + printf("ccan/hash\n"); + printf("ccan/htable\n"); + printf("ccan/tal"); + return 0; + } + + if (strcmp(argv[1], "testdepends") == 0) { + printf("ccan/array_size\n"); + printf("ccan/container_of\n"); + printf("ccan/ptrint\n"); + return 0; + } + + return 1; +} diff --git a/ccan/agar/agar.c b/ccan/agar/agar.c new file mode 100644 index 00000000..b2809abd --- /dev/null +++ b/ccan/agar/agar.c @@ -0,0 +1,232 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#include "config.h" + +#include + +#include +#include +#include +#include +#include + +#include + +#define HASH_BASE 0 + +struct agar_node { + const void *nr; + struct aga_node n; +}; + +struct agar_state { + struct agar_graph *gr; + struct aga_graph g; + struct htable nodes; +}; + +static size_t agar_node_hash(const struct agar_node *nn) +{ + return hash_pointer(nn->nr, HASH_BASE); +} + +static size_t agar_rehash(const void *elem, void *p) +{ + return agar_node_hash(elem); +} + +static bool agar_node_cmp(const void *candidate, void *ptr) +{ + struct agar_node *nn = (struct agar_node *)candidate; + + return (nn->nr == ptr); +} + +static struct aga_node *nr_to_n(struct agar_state *sr, const void *nr) +{ + struct agar_node *nn; + size_t hash = hash_pointer(nr, HASH_BASE); + bool rc; + + nn = htable_get(&sr->nodes, hash, agar_node_cmp, nr); + if (!nn) { + nn = tal(sr, struct agar_node); + assert(nn); + + nn->nr = nr; + aga_node_init(&nn->n); + + rc = htable_add(&sr->nodes, hash, nn); + assert(rc); + } + + return nn ? &nn->n : NULL; +} + +static const void *n_to_nr(struct agar_state *sr, const struct aga_node *n) +{ + struct agar_node *nn = container_of(n, struct agar_node, n); + + return nn->nr; +} + +static int convert_edge_info(const struct aga_graph *g, + const struct aga_node *n, + const void *e, struct aga_edge_info *ei) +{ + struct agar_state *sr = container_of(g, struct agar_state, g); + const void *nr = n_to_nr(sr, n); + struct agar_edge_info eir; + int rc; + + eir.to = NULL; + + rc = sr->gr->edge_info(sr->gr, nr, e, &eir); + + if (eir.to) + ei->to = nr_to_n(sr, eir.to); + else + ei->to = NULL; + + return rc; +} + +static const void *convert_first_edge(const struct aga_graph *g, + const struct aga_node *n) +{ + struct agar_state *sr = container_of(g, struct agar_state, g); + const void *nr = n_to_nr(sr, n); + + return sr->gr->first_edge(sr->gr, nr); +} + +static const void *convert_next_edge(const struct aga_graph *g, + const struct aga_node *n, + const void *e) +{ + struct agar_state *sr = container_of(g, struct agar_state, g); + const void *nr = n_to_nr(sr, n); + + return sr->gr->next_edge(sr->gr, nr, e); +} + +void agar_init_graph(struct agar_graph *gr, + agar_first_edge_fn first_edge, + agar_next_edge_fn next_edge, + agar_edge_info_fn edge_info) +{ + gr->edge_info = edge_info; + gr->first_edge = first_edge; + gr->next_edge = next_edge; +} + +int agar_error(struct agar_state *sr) +{ + return aga_error(&sr->g); +} + +static void agar_destruct_htable(struct agar_state *sr) +{ + htable_clear(&sr->nodes); +} + +static struct agar_state *agar_new(void *ctx, struct agar_graph *gr) +{ + struct agar_state *sr = tal(ctx, struct agar_state); + + assert(sr); + + sr->gr = gr; + htable_init(&sr->nodes, agar_rehash, NULL); + tal_add_destructor(sr, agar_destruct_htable); + aga_init_graph(&sr->g, convert_first_edge, convert_next_edge, + convert_edge_info); + + return sr; +} + +const void *agar_first_edge(const struct agar_graph *gr, const void *nr) +{ + return gr->first_edge(gr, nr); +} + +const void *agar_next_edge(const struct agar_graph *gr, + const void *nr, const void *e) +{ + if (!e) + return NULL; + else + return gr->next_edge(gr, nr, e); +} + +int agar_edge_info(const struct agar_graph *gr, const void *nr, const void *e, + struct agar_edge_info *eir) +{ + int rc; + + eir->to = NULL; + rc = gr->edge_info(gr, nr, e, eir); + assert(rc <= 0); + return rc; +} + +/* + * Depth first search + */ + +struct agar_dfs_state { + struct agar_state sr; +}; + +struct agar_state *agar_dfs_new(void *ctx, struct agar_graph *gr) +{ + struct agar_state *sr = agar_new(ctx, gr); + + if (aga_dfs_start(&sr->g) < 0) { + tal_free(sr); + return NULL; + } + + return sr; +} + +bool agar_dfs_explore(struct agar_state *sr, const void *nr, + const void **nextr) +{ + struct aga_node *next; + + next = aga_dfs_explore(&sr->g, nr_to_n(sr, nr)); + if (!next) + return false; + + *nextr = n_to_nr(sr, next); + return true; +} + +/* + * Breadth first search + */ + +struct agar_state *agar_bfs_new(void *ctx, struct agar_graph *gr) +{ + struct agar_state *sr = agar_new(ctx, gr); + + if (aga_bfs_start(&sr->g) < 0) { + tal_free(sr); + return NULL; + } + + return sr; +} + +bool agar_bfs_explore(struct agar_state *sr, const void *nr, + const void **nextr) +{ + struct aga_node *next; + + next = aga_bfs_explore(&sr->g, nr_to_n(sr, nr)); + if (!next) + return false; + + *nextr = n_to_nr(sr, next); + return true; +} diff --git a/ccan/agar/agar.h b/ccan/agar/agar.h new file mode 100644 index 00000000..495ef7c3 --- /dev/null +++ b/ccan/agar/agar.h @@ -0,0 +1,73 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_AGAR_H +#define CCAN_AGAR_H +#include "config.h" +#include +#include + +#include + +struct agar_edge_info { + const void *to; +}; + +struct agar_graph; +struct agar_state; + +typedef int (*agar_edge_info_fn)(const struct agar_graph *gr, + const void *nr, + const void *e, + struct agar_edge_info *ei); +typedef const void *(*agar_first_edge_fn)(const struct agar_graph *gr, + const void *nr); +typedef const void *(*agar_next_edge_fn)(const struct agar_graph *gr, + const void *nr, + const void *e); + +struct agar_graph { + agar_edge_info_fn edge_info; + agar_first_edge_fn first_edge; + agar_next_edge_fn next_edge; +}; + +void agar_init_graph(struct agar_graph *gr, + agar_first_edge_fn first_edge, + agar_next_edge_fn next_edge, + agar_edge_info_fn edge_info); +int agar_error(struct agar_state *sr); + +const void *agar_first_edge(const struct agar_graph *g, const void *nr); +const void *agar_next_edge(const struct agar_graph *g, const void *nr, + const void *e); +int agar_edge_info(const struct agar_graph *g, const void *nr, const void *e, + struct agar_edge_info *eir); + +#define agar_for_each_edge(_e, _gr, _nr) \ + for ((_e) = agar_first_edge((_gr), (_nr)); (_e); \ + (_e) = aga_next_edge((_gr), (_nr), (_e))) + +#define agar_for_each_edge_info(_e, _eir, _err, _gr, _nr) \ + for ((_e) = agar_first_edge((_gr), (_nr)); \ + (_e) && ((((_err) = agar_edge_info((_gr), (_nr), (_e), &(_eir)))) == 0); \ + (_e) = agar_next_edge((_gr), (_nr), (_e))) \ + if ((_eir).to) + +/* + * Depth first search + */ +struct agar_state *agar_dfs_new(void *ctx, struct agar_graph *gr); +bool agar_dfs_explore(struct agar_state *sr, const void *nr, + const void **nextr); +#define agar_dfs(_nr, _sr, _startr) \ + for ((_nr) = (_startr); agar_dfs_explore((_sr), (_nr), &(_nr)); ) + +/* + * Breadth first search + */ +struct agar_state *agar_bfs_new(void *ctx, struct agar_graph *gr); +bool agar_bfs_explore(struct agar_state *sr, const void *nr, + const void **nextr); +#define agar_bfs(_nr, _sr, _startr) \ + for ((_nr) = (_startr); agar_bfs_explore((_sr), (_nr), &(_nr)); ) + +#endif /* CCAN_AGAR_H */ diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c new file mode 100644 index 00000000..c17ead55 --- /dev/null +++ b/ccan/agar/test/api-adjacency.c @@ -0,0 +1,86 @@ +#include "config.h" + +#include +#include + +#include +#include + +#include + +#include "simple-graphr.h" + +static void test_adjacency(const char *name, + const struct agar_graph *gr, + const struct adjacency_listr *atr) +{ + int i; + + for (i = 0; atr[i].from != 0; i++) { + const void *e; + struct agar_edge_info eir; + int j = 0; + int err; + ptrint_t *from = int2ptr(atr[i].from); + + agar_for_each_edge_info(e, eir, err, gr, from) { + const void *cmpto; + + assert(j < MAX_EDGES); + cmpto = int2ptr(atr[i].to[j]); + ok(cmpto == eir.to, + "%s: %p #%d -> #%ld (expected #%d -> #%d)", name, e, + atr[i].from, ptr2int(eir.to), + atr[i].from, atr[i].to[j]); + + j++; + } + if (atr[i].to[j] < 0) { + ok(err == atr[i].to[j], "%s: %p #%d -> ERROR %d", + name, e, atr[i].from, atr[i].to[j]); + continue; /* Move onto next node on errors */ + } + assert(j < MAX_EDGES); + ok(atr[i].to[j] == 0, + "%s: %p #%d -> --- (expected #%d -> #%d)", name, e, + atr[i].from, atr[i].from, atr[i].to[j]); + } +} + +int main(void) +{ + struct trivial_graphr tgr; + struct parallel_graphr pgr; + struct full_graphr fgr; + struct chain_graphr cgr; + struct grid_graphr ggr1, ggr2; + struct error_graphr egr; + + plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6); + + trivial_graphr_init(&tgr); + test_adjacency("trivial", &tgr.gr, trivial_adjacencyr); + + parallel_graphr_init(&pgr, 3); + test_adjacency("parallel nlinks 3", &pgr.gr, + parallel_adjacencyr_nlinks3); + + full_graphr_init(&fgr, 5); + test_adjacency("full 5", &fgr.gr, full_adjacencyr_5); + + chain_graphr_init(&cgr, 8); + test_adjacency("chain 8", &cgr.fgr.gr, chain_adjacencyr_8); + + grid_graphr_init(&ggr1, 3, 3, true, true, false, false); + test_adjacency("grid 3x3 right-down", &ggr1.gr, + grid_adjacencyr_3x3_rightdown); + + grid_graphr_init(&ggr2, 3, 3, true, true, true, true); + test_adjacency("grid 3x3 all", &ggr2.gr, + grid_adjacencyr_3x3_all); + + error_graphr_init(&egr); + test_adjacency("error graph", &egr.gr, error_adjacencyr); + + return exit_status(); +} diff --git a/ccan/agar/test/api-bfs.c b/ccan/agar/test/api-bfs.c new file mode 100644 index 00000000..8823df8c --- /dev/null +++ b/ccan/agar/test/api-bfs.c @@ -0,0 +1,106 @@ +#include "config.h" + +#include +#include + +#include +#include +#include +#include + +#include + +#include "simple-graphr.h" + +#define test_bfs_partial(sr, first, ...) \ + do { \ + int cmp[] = { __VA_ARGS__ }; \ + bool stillok = true; \ + const void *node; \ + int i = 0; \ + agar_bfs(node, (sr), int2ptr(first)) { \ + int index = ptr2int(node); \ + diag("Visited %d\n", index); \ + if (i >= ARRAY_SIZE(cmp) || (index != cmp[i])) \ + stillok = false; \ + i++; \ + } \ + ok1(stillok); \ + } while (0) + +#define test_bfs(gr, first, ...) \ + do { \ + struct agar_state *sr; \ + ok1((sr = agar_bfs_new(NULL, (gr)))); \ + test_bfs_partial(sr, first, __VA_ARGS__); \ + tal_free(sr); \ + } while (0) + +int main(void) +{ + struct trivial_graphr tgr; + struct parallel_graphr pgr; + struct full_graphr fgr; + struct chain_graphr cgr; + struct grid_graphr ggr1, ggr2; + struct error_graphr egr; + struct traversal1_graphr t1gr; + struct agar_state *sr; + const void *nr; + + plan_tests(2 * 13 + 12 + 10); + + trivial_graphr_init(&tgr); + test_bfs(&tgr.gr, 1, 1); + + parallel_graphr_init(&pgr, 3); + test_bfs(&pgr.gr, 1, 1, 2); + + full_graphr_init(&fgr, 5); + test_bfs(&fgr.gr, 1, 1, 2, 3, 4, 5); + test_bfs(&fgr.gr, 3, 3, 1, 2, 4, 5); + + chain_graphr_init(&cgr, 8); + test_bfs(&cgr.fgr.gr, 1, 1, 2, 3, 4, 5, 6, 7, 8); + test_bfs(&cgr.fgr.gr, 8, 8, 7, 6, 5, 4, 3, 2, 1); + test_bfs(&cgr.fgr.gr, 5, 5, 4, 6, 3, 7, 2, 8, 1); + + grid_graphr_init(&ggr1, 3, 3, true, true, false, false); + test_bfs(&ggr1.gr, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9); + test_bfs(&ggr1.gr, 5, 5, 6, 8, 9); + test_bfs(&ggr1.gr, 9, 9); + + grid_graphr_init(&ggr2, 3, 3, true, true, true, true); + test_bfs(&ggr2.gr, 1, 1, 2, 4, 3, 5, 7, 6, 8, 9); + test_bfs(&ggr2.gr, 5, 5, 6, 8, 4, 2, 9, 3, 7, 1); + test_bfs(&ggr2.gr, 9, 9, 8, 6, 7, 5, 3, 4, 2, 1); + + error_graphr_init(&egr); + test_bfs(&egr.gr, 1, 1, 2); + ok((sr = agar_bfs_new(NULL, &egr.gr)), "started error traversal"); + ok1(agar_bfs_explore(sr, int2ptr(3), &nr)); + ok(ptr2int(nr) == 3, "Expected node #3, actually #%ld", ptr2int(nr)); + ok1(agar_bfs_explore(sr, nr, &nr)); + ok(ptr2int(nr) == 4, "Expected node #4, actually #%ld", ptr2int(nr)); + ok1(!agar_bfs_explore(sr, nr, &nr)); + ok1(agar_error(sr) == -1); + ok1(!agar_bfs_explore(sr, nr, &nr)); + tal_free(sr); + test_bfs(&egr.gr, 1, 1, 2); + + traversal1_graphr_init(&t1gr); + test_bfs(&t1gr.gr, 1, 1, 2, 3, 4, 5, 6); + test_bfs(&t1gr.gr, 9, 9, 8, 7, 6, 5, 4); + + ok1((sr = agar_bfs_new(NULL, &t1gr.gr))); + test_bfs_partial(sr, 1, 1, 2, 3, 4, 5, 6); + test_bfs_partial(sr, 9, 9, 8, 7); + tal_free(sr); + + ok1((sr = agar_bfs_new(NULL, &t1gr.gr))); + test_bfs_partial(sr, 9, 9, 8, 7, 6, 5, 4); + test_bfs_partial(sr, 1, 1, 2, 3); + tal_free(sr); + + return exit_status(); +} diff --git a/ccan/agar/test/api-dfs.c b/ccan/agar/test/api-dfs.c new file mode 100644 index 00000000..2a7e4cea --- /dev/null +++ b/ccan/agar/test/api-dfs.c @@ -0,0 +1,106 @@ +#include "config.h" + +#include +#include + +#include +#include +#include +#include + +#include + +#include "simple-graphr.h" + +#define test_dfs_partial(sr, first, ...) \ + do { \ + int cmp[] = { __VA_ARGS__ }; \ + bool stillok = true; \ + const void *node; \ + int i = 0; \ + agar_dfs(node, (sr), int2ptr(first)) { \ + int index = ptr2int(node); \ + diag("Visited %d\n", index); \ + if (i >= ARRAY_SIZE(cmp) || (index != cmp[i])) \ + stillok = false; \ + i++; \ + } \ + ok1(stillok); \ + } while (0) + +#define test_dfs(gr, first, ...) \ + do { \ + struct agar_state *sr; \ + ok1((sr = agar_dfs_new(NULL, (gr)))); \ + test_dfs_partial(sr, first, __VA_ARGS__); \ + tal_free(sr); \ + } while (0) + +int main(void) +{ + struct trivial_graphr tgr; + struct parallel_graphr pgr; + struct full_graphr fgr; + struct chain_graphr cgr; + struct grid_graphr ggr1, ggr2; + struct error_graphr egr; + struct traversal1_graphr t1gr; + struct agar_state *sr; + const void *nr; + + plan_tests(2 * 13 + 12 + 10); + + trivial_graphr_init(&tgr); + test_dfs(&tgr.gr, 1, 1); + + parallel_graphr_init(&pgr, 3); + test_dfs(&pgr.gr, 1, 1, 2); + + full_graphr_init(&fgr, 5); + test_dfs(&fgr.gr, 1, 1, 2, 3, 4, 5); + test_dfs(&fgr.gr, 3, 3, 1, 2, 4, 5); + + chain_graphr_init(&cgr, 8); + test_dfs(&cgr.fgr.gr, 1, 1, 2, 3, 4, 5, 6, 7, 8); + test_dfs(&cgr.fgr.gr, 8, 8, 7, 6, 5, 4, 3, 2, 1); + test_dfs(&cgr.fgr.gr, 5, 5, 4, 3, 2, 1, 6, 7, 8); + + grid_graphr_init(&ggr1, 3, 3, true, true, false, false); + test_dfs(&ggr1.gr, 1, 1, 2, 3, 6, 9, 5, 8, 4, 7); + test_dfs(&ggr1.gr, 5, 5, 6, 9, 8); + test_dfs(&ggr1.gr, 9, 9); + + grid_graphr_init(&ggr2, 3, 3, true, true, true, true); + test_dfs(&ggr2.gr, 1, 1, 2, 3, 6, 9, 8, 7, 4, 5); + test_dfs(&ggr2.gr, 5, 5, 6, 9, 8, 7, 4, 1, 2, 3); + test_dfs(&ggr2.gr, 9, 9, 8, 7, 4, 5, 6, 3, 2, 1); + + error_graphr_init(&egr); + test_dfs(&egr.gr, 1, 1, 2); + ok((sr = agar_dfs_new(NULL, &egr.gr)), "started error traversal"); + ok1(agar_dfs_explore(sr, int2ptr(3), &nr)); + ok(ptr2int(nr) == 3, "Expected node #3, actually #%ld", ptr2int(nr)); + ok1(agar_dfs_explore(sr, nr, &nr)); + ok(ptr2int(nr) == 4, "Expected node #4, actually #%ld", ptr2int(nr)); + ok1(!agar_dfs_explore(sr, nr, &nr)); + ok(agar_error(sr) == -1, "Error is %d (expected -1)", agar_error(sr)); + ok1(!agar_dfs_explore(sr, nr, &nr)); + tal_free(sr); + test_dfs(&egr.gr, 1, 1, 2); + + traversal1_graphr_init(&t1gr); + test_dfs(&t1gr.gr, 1, 1, 2, 4, 5, 3, 6); + test_dfs(&t1gr.gr, 9, 9, 8, 6, 5, 7, 4); + + ok1((sr = agar_dfs_new(NULL, &t1gr.gr))); + test_dfs_partial(sr, 1, 1, 2, 4, 5, 3, 6); + test_dfs_partial(sr, 9, 9, 8, 7); + tal_free(sr); + + ok1((sr = agar_dfs_new(NULL, &t1gr.gr))); + test_dfs_partial(sr, 9, 9, 8, 6, 5, 7, 4); + test_dfs_partial(sr, 1, 1, 2, 3); + tal_free(sr); + + return exit_status(); +} diff --git a/ccan/agar/test/chain.c b/ccan/agar/test/chain.c new file mode 100644 index 00000000..e563deab --- /dev/null +++ b/ccan/agar/test/chain.c @@ -0,0 +1,30 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#include "simple-graphr.h" + +static int chain_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *e, + struct agar_edge_info *eir) +{ + int fromi = ptr2int(nr); + int toi = ptr2int(e); + + if ((toi == fromi + 1) || (fromi == toi + 1)) + eir->to = int2ptr(toi); + + return 0; +} + +void chain_graphr_init(struct chain_graphr *cgr, int nnodes) +{ + cgr->fgr.nnodes = nnodes; + agar_init_graph(&cgr->fgr.gr, full_first_edge_r, full_next_edge_r, + chain_edge_info_r); +} diff --git a/ccan/agar/test/error-graph.c b/ccan/agar/test/error-graph.c new file mode 100644 index 00000000..efd83a37 --- /dev/null +++ b/ccan/agar/test/error-graph.c @@ -0,0 +1,55 @@ +#include "config.h" + +#include + +#include +#include +#include + +#include "simple-graphr.h" + +static const void *error_first_edge_r(const struct agar_graph *gr, + const void *nr) +{ + return int2ptr(1); +} + +static const void *error_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *e) +{ + assert(ptr2int(e) == 1); + + return NULL; +} + +static int error_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *e, + struct agar_edge_info *eir) +{ + int fromindex = ptr2int(nr); + + switch (fromindex) { + case 1: + eir->to = int2ptr(2); + break; + + case 2: + eir->to = NULL; + break; + + case 3: + eir->to = int2ptr(4); + break; + + default: + return -1; + } + + return 0; +} + +void error_graphr_init(struct error_graphr *egr) +{ + agar_init_graph(&egr->gr, error_first_edge_r, error_next_edge_r, + error_edge_info_r); +} diff --git a/ccan/agar/test/full.c b/ccan/agar/test/full.c new file mode 100644 index 00000000..dab6c502 --- /dev/null +++ b/ccan/agar/test/full.c @@ -0,0 +1,45 @@ +#include "config.h" + +#include +#include + +#include +#include + +#include + +#include "simple-graphr.h" + +const void *full_first_edge_r(const struct agar_graph *gr, + const void *nr) +{ + return int2ptr(1); +} + +const void *full_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *e) +{ + struct full_graphr *fgr = container_of(gr, struct full_graphr, gr); + int ni = ptr2int(e); + + ni += 1; + if (ni <= fgr->nnodes) + return int2ptr(ni); + else + return NULL; +} + +static int full_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *edge, + struct agar_edge_info *eir) +{ + eir->to = edge; + return 0; +} + +void full_graphr_init(struct full_graphr *fgr, int nnodes) +{ + fgr->nnodes = nnodes; + agar_init_graph(&fgr->gr, full_first_edge_r, full_next_edge_r, + full_edge_info_r); +} diff --git a/ccan/agar/test/grid.c b/ccan/agar/test/grid.c new file mode 100644 index 00000000..3b59c382 --- /dev/null +++ b/ccan/agar/test/grid.c @@ -0,0 +1,81 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#include "simple-graphr.h" + +static const void *grid_first_edge_r(const struct agar_graph *gr, + const void *nr) +{ + return int2ptr(1); +} + +static const void *grid_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *e) +{ + int index = ptr2int(e); + + if (index < 4) + return int2ptr(index + 1); + else + return NULL; +} + +static int grid_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *e, + struct agar_edge_info *eir) +{ + struct grid_graphr *ggr = container_of(gr, struct grid_graphr, gr); + int ni = ptr2int(nr); + int x = ((ni - 1) % ggr->nx) + 1; + int y = ((ni - 1) / ggr->nx) + 1; + int i = ptr2int(e); + + assert((x >= 1) && (x <= ggr->nx)); + assert((y >= 1) && (y <= ggr->ny)); + + switch (i) { + case 1: /* right */ + if (ggr->right && (x != ggr->nx)) + eir->to = int2ptr(ni + 1); + break; + + case 2: /* down */ + if (ggr->down && (y != ggr->ny)) + eir->to = int2ptr(ni + ggr->nx); + break; + + case 3: /* left */ + if (ggr->left && (x != 1)) + eir->to = int2ptr(ni - 1); + break; + + case 4: /* up */ + if (ggr->up && (y != 1)) + eir->to = int2ptr(ni - ggr->nx); + break; + + default: + assert(0); + } + return 0; +} + +void grid_graphr_init(struct grid_graphr *ggr, int nx, int ny, + bool right, bool down, bool left, bool up) +{ + ggr->nx = nx; + ggr->ny = ny; + ggr->right = right; + ggr->down = down; + ggr->left = left; + ggr->up = up; + + agar_init_graph(&ggr->gr, grid_first_edge_r, grid_next_edge_r, + grid_edge_info_r); +} diff --git a/ccan/agar/test/parallel.c b/ccan/agar/test/parallel.c new file mode 100644 index 00000000..741ff3a3 --- /dev/null +++ b/ccan/agar/test/parallel.c @@ -0,0 +1,62 @@ +#include "config.h" + +#include + +#include +#include +#include + +#include "simple-graphr.h" + +static const void *parallel_first_edge_r(const struct agar_graph *gr, + const void *nr) +{ + const struct parallel_graphr *pgr + = container_of(gr, struct parallel_graphr, gr); + + if (ptr2int(nr) != 1) { + assert(ptr2int(nr) == 2); + return NULL; + } + + if (pgr->nlinks) + return int2ptr(1); + else + return NULL; +} + +static const void *parallel_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *edge) +{ + const struct parallel_graphr *pgr + = container_of(gr, struct parallel_graphr, gr); + int index = ptr2int(edge); + + if (ptr2int(nr) != 1) { + assert(ptr2int(nr) == 2); + return NULL; + } + + if (index < pgr->nlinks) + return int2ptr(index + 1); + else + return NULL; +} + +static int parallel_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *edge, + struct agar_edge_info *eir) +{ + assert(ptr2int(nr) == 1); + + eir->to = int2ptr(2); + return 0; +} + +void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks) +{ + pgr->nlinks = nlinks; + + agar_init_graph(&pgr->gr, parallel_first_edge_r, parallel_next_edge_r, + parallel_edge_info_r); +} diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h new file mode 100644 index 00000000..de48ff68 --- /dev/null +++ b/ccan/agar/test/simple-graphr.h @@ -0,0 +1,200 @@ +#ifndef _SIMPLE_GRAPHR_H +#define _SIMPLE_GRAPHR_H + +#include + +#define MAX_EDGES 16 /* Max edges per node */ + +struct adjacency_listr { + int from; + int to[MAX_EDGES]; +}; + +/* Trivial graph + * + * (A) + * + * The simplest possible graph: one node, no edges + */ +struct trivial_graphr { + struct agar_graph gr; +}; +void trivial_graphr_init(struct trivial_graphr *tgr); +static const struct adjacency_listr trivial_adjacencyr[] = { + {1, {}}, + {}, +}; + +/* Parallel graph + * + * -- + * / \ + * (A) => (B) + * \ / + * -- + * + * Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B. + */ +struct parallel_graphr { + int nlinks; + struct agar_graph gr; +}; +void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks); +static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = { + {1, {2, 2, 2}}, + {2, {}}, + {}, +}; + +/* Full graph + * + * n nodes with an edge from every node to every other node (including + * itself) + */ +struct full_graphr { + int nnodes; + struct agar_graph gr; +}; +void full_graphr_init(struct full_graphr *fgr, int nnodes); +static const struct adjacency_listr full_adjacencyr_5[] = { + {1, {1, 2, 3, 4, 5}}, + {2, {1, 2, 3, 4, 5}}, + {3, {1, 2, 3, 4, 5}}, + {4, {1, 2, 3, 4, 5}}, + {5, {1, 2, 3, 4, 5}}, + {}, +}; +const void *full_first_edge_r(const struct agar_graph *gr, const void *nr); +const void *full_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *e); + + +/* Chain graph + * + * --> --> --> + * A B C D + * <-- <-- <-- + * + * nnodes nodes arranged in a linear sequence, edges from each node to + * the previous and next + */ +struct chain_graphr { + struct full_graphr fgr; +}; +void chain_graphr_init(struct chain_graphr *cgr, int nnodes); +static const struct adjacency_listr chain_adjacencyr_8[] = { + {1, {2}}, + {2, {1, 3}}, + {3, {2, 4}}, + {4, {3, 5}}, + {5, {4, 6}}, + {6, {5, 7}}, + {7, {6, 8}}, + {8, {7}}, + {}, +}; + + +/* Grid graph(s) + * + * A -> B -> C + * | | | + * v v v + * D -> E -> F + * | | | + * v v v + * G -> H -> I + * + * nx * ny nodes arranged in an nx * ny grid. Depending on + * parameters, edges to the node to the right / down / left / up of + * each node + */ +struct grid_graphr { + int nx, ny; + bool right, down, left, up; + struct agar_graph gr; +}; +void grid_graphr_init(struct grid_graphr *ggr, int nx, int ny, + bool right, bool down, bool left, bool up); +static const struct adjacency_listr grid_adjacencyr_3x3_rightdown[] = { + {1, {2, 4}}, + {2, {3, 5}}, + {3, {6}}, + {4, {5, 7}}, + {5, {6, 8}}, + {6, {9}}, + {7, {8}}, + {8, {9}}, + {9, {}}, + {}, +}; +static const struct adjacency_listr grid_adjacencyr_3x3_all[] = { + {1, {2, 4}}, + {2, {3, 5, 1}}, + {3, {6, 2}}, + {4, {5, 7, 1}}, + {5, {6, 8, 4, 2}}, + {6, {9, 5, 3}}, + {7, {8, 4}}, + {8, {9, 7, 5}}, + {9, {8, 6}}, + {}, +}; + +/* Error graph + * + * A -> B + * + * C -> D -> ??? + * + * This is for testing reporting of errors by the edge_info function. + * 5 nodes are arranged as above, with the link from D always + * returning an error. + */ +struct error_graphr { + struct agar_graph gr; +}; +void error_graphr_init(struct error_graphr *eg); +static const struct adjacency_listr error_adjacencyr[] = { + {1, {2}}, + {2, {}}, + {3, {4}}, + {4, {-1}}, + {}, +}; + +/* Traversal-1 graph + * + * -> D <- + * / \ + * -> B G <- + * / \ / \ + * A => E <= I + * \ / \ / + * -> C H <- + * \ / + * -> F <- + * + * This provides an example of a graph which can't be traversed (with + * DFS or BFS) from a single starting node. It can be traversed with + * two starting points, but several nodes can be reached from either, + * complicating the logic to avoid double-traversal. + */ +struct traversal1_graphr { + struct agar_graph gr; +}; +void traversal1_graphr_init(struct traversal1_graphr *t1gr); +static const struct adjacency_listr traversal1_adjacency[] = { + {1, {2, 3}}, + {2, {4, 5}}, + {3, {5, 6}}, + {4, {}}, + {5, {}}, + {6, {}}, + {7, {5, 4}}, + {8, {6, 5}}, + {9, {8, 7}}, + {}, +}; + +#endif /* _SIMPLE_GRAPHR_H */ diff --git a/ccan/agar/test/traversal1.c b/ccan/agar/test/traversal1.c new file mode 100644 index 00000000..0a465989 --- /dev/null +++ b/ccan/agar/test/traversal1.c @@ -0,0 +1,114 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#include "simple-graphr.h" + +static const void *traversal1_first_edge_r(const struct agar_graph *gr, + const void *nr) +{ + int ni = ptr2int(nr); + + switch (ni) { + case 1: + case 2: + case 3: + + case 7: + case 8: + case 9: + return int2ptr(1); + + case 4: + case 5: + case 6: + return NULL; + + default: + assert(0); + } +} + +static const void *traversal1_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *e) +{ + int ni = ptr2int(nr); + int index = ptr2int(e); + + assert((ni < 4) || (ni > 6)); + if (index == 1) + return int2ptr(2); + else if (index == 2) + return NULL; + else + assert(0); +} + +static int traversal1_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *e, + struct agar_edge_info *eir) +{ + int ni = ptr2int(nr); + int index = ptr2int(e); + + assert((index == 1) || (index == 2)); + + switch (ni) { + case 1: + if (index == 1) + eir->to = int2ptr(2); + else + eir->to = int2ptr(3); + break; + + case 2: + if (index == 1) + eir->to = int2ptr(4); + else + eir->to = int2ptr(5); + break; + case 3: + if (index == 1) + eir->to = int2ptr(5); + else + eir->to = int2ptr(6); + break; + + case 7: + if (index == 1) + eir->to = int2ptr(5); + else + eir->to = int2ptr(4); + break; + + case 8: + if (index == 1) + eir->to = int2ptr(6); + else + eir->to = int2ptr(5); + break; + + case 9: + if (index == 1) + eir->to = int2ptr(8); + else + eir->to = int2ptr(7); + break; + + default: + assert(0); + } + return 0; +} + +void traversal1_graphr_init(struct traversal1_graphr *t1gr) +{ + agar_init_graph(&t1gr->gr, + traversal1_first_edge_r, traversal1_next_edge_r, + traversal1_edge_info_r); +} diff --git a/ccan/agar/test/trivial.c b/ccan/agar/test/trivial.c new file mode 100644 index 00000000..55a81997 --- /dev/null +++ b/ccan/agar/test/trivial.c @@ -0,0 +1,36 @@ +#include "config.h" + +#include + +#include +#include + +#include + +#include "simple-graphr.h" + +static const void *trivial_first_edge_r(const struct agar_graph *g, + const void *nr) +{ + assert(ptr2int(nr) == 1); + return NULL; +} + +static const void *trivial_next_edge_r(const struct agar_graph *gr, + const void *nr, const void *edge) +{ + assert(0); +} + +static int trivial_edge_info_r(const struct agar_graph *gr, + const void *nr, const void *edge, + struct agar_edge_info *eir) +{ + assert(0); +} + +void trivial_graphr_init(struct trivial_graphr *tgr) +{ + agar_init_graph(&tgr->gr, trivial_first_edge_r, trivial_next_edge_r, + trivial_edge_info_r); +} -- 2.39.2