[ccan] [PATCH 7/7] agar: Re-entrant Abstract Graph Algorithms
David Gibson
david at gibson.dropbear.id.au
Sat Jul 25 20:50:12 AEST 2015
New module
Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
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 0000000..dc314ec
--- /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 0000000..d62b2e5
--- /dev/null
+++ b/ccan/agar/_info
@@ -0,0 +1,48 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * 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 <david at gibson.dropbear.id.au>
+ */
+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 0000000..b2809ab
--- /dev/null
+++ b/ccan/agar/agar.c
@@ -0,0 +1,232 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#include "config.h"
+
+#include <stdbool.h>
+
+#include <ccan/aga/aga.h>
+#include <ccan/hash/hash.h>
+#include <ccan/htable/htable.h>
+#include <ccan/container_of/container_of.h>
+#include <ccan/tal/tal.h>
+
+#include <ccan/agar/agar.h>
+
+#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 0000000..495ef7c
--- /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 <string.h>
+#include <stdbool.h>
+
+#include <ccan/aga/aga.h>
+
+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 0000000..c17ead5
--- /dev/null
+++ b/ccan/agar/test/api-adjacency.c
@@ -0,0 +1,86 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/agar/agar.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/tap/tap.h>
+
+#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 0000000..8823df8
--- /dev/null
+++ b/ccan/agar/test/api-bfs.c
@@ -0,0 +1,106 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/tal/tal.h>
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#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 0000000..2a7e4ce
--- /dev/null
+++ b/ccan/agar/test/api-dfs.c
@@ -0,0 +1,106 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/tal/tal.h>
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#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 0000000..e563dea
--- /dev/null
+++ b/ccan/agar/test/chain.c
@@ -0,0 +1,30 @@
+#include "config.h"
+
+#include <stdlib.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#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 0000000..efd83a3
--- /dev/null
+++ b/ccan/agar/test/error-graph.c
@@ -0,0 +1,55 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/agar/agar.h>
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#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 0000000..dab6c50
--- /dev/null
+++ b/ccan/agar/test/full.c
@@ -0,0 +1,45 @@
+#include "config.h"
+
+#include <stdlib.h>
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#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 0000000..3b59c38
--- /dev/null
+++ b/ccan/agar/test/grid.c
@@ -0,0 +1,81 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#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 0000000..741ff3a
--- /dev/null
+++ b/ccan/agar/test/parallel.c
@@ -0,0 +1,62 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/agar/agar.h>
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#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 0000000..de48ff6
--- /dev/null
+++ b/ccan/agar/test/simple-graphr.h
@@ -0,0 +1,200 @@
+#ifndef _SIMPLE_GRAPHR_H
+#define _SIMPLE_GRAPHR_H
+
+#include <stdbool.h>
+
+#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 0000000..0a46598
--- /dev/null
+++ b/ccan/agar/test/traversal1.c
@@ -0,0 +1,114 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#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 0000000..55a8199
--- /dev/null
+++ b/ccan/agar/test/trivial.c
@@ -0,0 +1,36 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#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.4.3
More information about the ccan
mailing list