[ccan] [PATCH 2/6] aga: Simple test graphs

David Gibson david at gibson.dropbear.id.au
Wed May 27 21:21:24 AEST 2015


This adds code for a number of example graphs for use in tests of the aga
module.  They also demonstrate several different ways of constructing
graphs using the aga callbacks.

It adds one actual testcase, which just verifies that the example graph
look like what they're supposed to.  Specifically it computes a set of
adjacency lists for the example graphs from the callback code, then
compares that to a canned example of what it should be.

Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
 ccan/aga/_info                |   1 +
 ccan/aga/test/api-adjacency.c |  89 +++++++++++++++++++++
 ccan/aga/test/chain.c         |  29 +++++++
 ccan/aga/test/error-graph.c   |  56 +++++++++++++
 ccan/aga/test/full.c          |  52 ++++++++++++
 ccan/aga/test/grid.c          |  84 ++++++++++++++++++++
 ccan/aga/test/parallel.c      |  62 +++++++++++++++
 ccan/aga/test/simple-graph.c  |  15 ++++
 ccan/aga/test/simple-graph.h  | 180 ++++++++++++++++++++++++++++++++++++++++++
 ccan/aga/test/trivial.c       |  39 +++++++++
 10 files changed, 607 insertions(+)
 create mode 100644 ccan/aga/test/api-adjacency.c
 create mode 100644 ccan/aga/test/chain.c
 create mode 100644 ccan/aga/test/error-graph.c
 create mode 100644 ccan/aga/test/full.c
 create mode 100644 ccan/aga/test/grid.c
 create mode 100644 ccan/aga/test/parallel.c
 create mode 100644 ccan/aga/test/simple-graph.c
 create mode 100644 ccan/aga/test/simple-graph.h
 create mode 100644 ccan/aga/test/trivial.c

diff --git a/ccan/aga/_info b/ccan/aga/_info
index ff1bc33..551bec1 100644
--- a/ccan/aga/_info
+++ b/ccan/aga/_info
@@ -26,6 +26,7 @@ int main(int argc, char *argv[])
 
 	if (strcmp(argv[1], "testdepends") == 0) {
 		printf("ccan/container_of\n");
+		printf("ccan/ptrint\n");
 		return 0;
 	}
 
diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c
new file mode 100644
index 0000000..1ef0c12
--- /dev/null
+++ b/ccan/aga/test/api-adjacency.c
@@ -0,0 +1,89 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+
+#include <ccan/tap/tap.h>
+
+#include "simple-graph.h"
+
+static void test_adjacency(const char *name,
+			   const struct simple_graph *sg,
+			   const struct adjacency_list *at)
+{
+	int i;
+
+	for (i = 0; at[i].from != 0; i++) {
+		const void *e;
+		struct aga_edge_info ei;
+		int j = 0;
+		const struct aga_node *from;
+		int err;
+
+		assert(i < MAX_NODES);
+
+		from = &sg->nodes[at[i].from];
+
+		aga_for_each_edge_info(e, ei, err, &sg->g, from) {
+			const struct aga_node *cmpto;
+
+			assert(j < MAX_EDGES);
+			cmpto = &sg->nodes[at[i].to[j]];
+			ok(cmpto == ei.to,
+			   "%s: %p #%d -> #%ld (expected #%d -> #%d)", name, e,
+			   at[i].from, (ei.to - sg->nodes),
+			   at[i].from, at[i].to[j]);
+
+			j++;
+		}
+		if (at[i].to[j] < 0) {
+			ok(err == at[i].to[j], "%s: %p #%d -> ERROR %d",
+			   name, e, at[i].from, at[i].to[j]);
+			continue; /* Move onto next node on errors */
+		}
+		assert(j < MAX_EDGES);
+		ok(at[i].to[j] == 0,
+		   "%s: %p #%d -> --- (expected #%d -> #%d)", name, e,
+		   at[i].from, at[i].from, at[i].to[j]);
+	}
+}
+
+int main(void)
+{
+	struct trivial_graph tg;
+	struct parallel_graph pg;
+	struct full_graph fg;
+	struct chain_graph cg;
+	struct grid_graph gg1, gg2;
+	struct error_graph eg;
+
+	plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6);
+
+	trivial_graph_init(&tg);
+	test_adjacency("trivial", &tg.sg, trivial_adjacency);
+
+	parallel_graph_init(&pg, 3);
+	test_adjacency("parallel nlinks 3", &pg.sg,
+		       parallel_adjacency_nlinks3);
+
+	full_graph_init(&fg, 5);
+	test_adjacency("full 5", &fg.sg, full_adjacency_5);
+
+	chain_graph_init(&cg, 8);
+	test_adjacency("chain 8", &cg.fg.sg, chain_adjacency_8);
+
+	grid_graph_init(&gg1, 3, 3, true, true, false, false);
+	test_adjacency("grid 3x3 right-down", &gg1.sg,
+		       grid_adjacency_3x3_rightdown);
+
+	grid_graph_init(&gg2, 3, 3, true, true, true, true);
+	test_adjacency("grid 3x3 all", &gg2.sg,
+		       grid_adjacency_3x3_all);
+
+	error_graph_init(&eg);
+	test_adjacency("error graph", &eg.sg, error_adjacency);
+
+	return exit_status();
+}
diff --git a/ccan/aga/test/chain.c b/ccan/aga/test/chain.c
new file mode 100644
index 0000000..c7c439b
--- /dev/null
+++ b/ccan/aga/test/chain.c
@@ -0,0 +1,29 @@
+#include "config.h"
+
+#include <stdlib.h>
+
+#include <ccan/container_of/container_of.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static int chain_edge_info(const struct aga_graph *g,
+			   const struct aga_node *node,
+			   const void *edge,
+			   struct aga_edge_info *ei)
+{
+	struct aga_node *tonode = (struct aga_node *)edge;
+
+	if ((tonode == node + 1) || (node == tonode + 1))
+		ei->to = tonode;
+
+	return 0;
+}
+
+void chain_graph_init(struct chain_graph *cg, int nnodes)
+{
+	cg->fg.nnodes = nnodes;
+	simple_graph_init(&cg->fg.sg, chain_edge_info,
+			  full_first_edge, full_next_edge);
+}
diff --git a/ccan/aga/test/error-graph.c b/ccan/aga/test/error-graph.c
new file mode 100644
index 0000000..f7c2caa
--- /dev/null
+++ b/ccan/aga/test/error-graph.c
@@ -0,0 +1,56 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include "simple-graph.h"
+
+static const void *error_first_edge(const struct aga_graph *g,
+				    const struct aga_node *n)
+{
+	return int2ptr(1);
+}
+
+static const void *error_next_edge(const struct aga_graph *g,
+				   const struct aga_node *n,
+				   const void *edge)
+{
+	assert(edge == int2ptr(1));
+
+	return NULL;
+}
+
+static int error_edge_info(const struct aga_graph *g, const struct aga_node *n,
+			   const void *edge, struct aga_edge_info *ei)
+{
+	struct error_graph *eg = container_of(g, struct error_graph, sg.g);
+	int fromindex = n - eg->sg.nodes;
+
+	switch (fromindex) {
+	case 1:
+		ei->to = &eg->sg.nodes[2];
+		break;
+
+	case 2:
+		ei->to = NULL;
+		break;
+
+	case 3:
+		ei->to = &eg->sg.nodes[4];
+		break;
+
+	default:
+		return -1;
+	}
+
+	return 0;
+}
+
+void error_graph_init(struct error_graph *eg)
+{
+	simple_graph_init(&eg->sg, error_edge_info,
+			  error_first_edge, error_next_edge);
+}
diff --git a/ccan/aga/test/full.c b/ccan/aga/test/full.c
new file mode 100644
index 0000000..17f34a5
--- /dev/null
+++ b/ccan/aga/test/full.c
@@ -0,0 +1,52 @@
+#include "config.h"
+
+#include <stdlib.h>
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+const void *full_first_edge(const struct aga_graph *g,
+			    const struct aga_node *node)
+{
+	struct full_graph *fg = container_of(g, struct full_graph, sg.g);
+
+	return &fg->sg.nodes[1];
+}
+
+const void *full_next_edge(const struct aga_graph *g,
+			   const struct aga_node *node,
+			   const void *edge)
+{
+	struct full_graph *fg = container_of(g, struct full_graph, sg.g);
+	const struct aga_node *tonode = (struct aga_node *)edge;
+
+	tonode += 1;
+	if (tonode < &fg->sg.nodes[fg->nnodes + 1])
+		return tonode;
+	else
+		return NULL;
+}
+
+static int full_edge_info(const struct aga_graph *g,
+			  const struct aga_node *node,
+			  const void *edge,
+			  struct aga_edge_info *ei)
+{
+	struct aga_node *tonode = (struct aga_node *)edge;
+
+	ei->to = tonode;
+	return 0;
+}
+
+void full_graph_init(struct full_graph *fg, int nnodes)
+{
+	assert(nnodes < MAX_NODES);
+	
+	fg->nnodes = nnodes;
+	simple_graph_init(&fg->sg, full_edge_info,
+			  full_first_edge, full_next_edge);
+}
diff --git a/ccan/aga/test/grid.c b/ccan/aga/test/grid.c
new file mode 100644
index 0000000..d736f7f
--- /dev/null
+++ b/ccan/aga/test/grid.c
@@ -0,0 +1,84 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static const void *grid_first_edge(const struct aga_graph *g,
+				   const struct aga_node *n)
+{
+	return int2ptr(1);
+}
+
+static const void *grid_next_edge(const struct aga_graph *g,
+				  const struct aga_node *n,
+				  const void *e)
+{
+	int index = ptr2int(e);
+
+	if (index < 4)
+		return int2ptr(index + 1);
+	else
+		return NULL;	       
+}
+
+static int grid_edge_info(const struct aga_graph *g,
+			  const struct aga_node *n,
+			  const void *e, struct aga_edge_info *ei)
+{
+	struct grid_graph *gg = container_of(g, struct grid_graph, sg.g);
+	int ni = n - gg->sg.nodes;
+	int x = ((ni - 1) % gg->nx) + 1;
+	int y = ((ni - 1) / gg->nx) + 1;
+	int i = ptr2int(e);
+
+	assert((x >= 1) && (x <= gg->nx));
+	assert((y >= 1) && (y <= gg->ny));
+
+	switch (i) {
+	case 1: /* right */
+		if (gg->right && (x != gg->nx))
+			ei->to = &gg->sg.nodes[ni + 1];
+		break;
+
+	case 2: /* down */
+		if (gg->down && (y != gg->ny))
+			ei->to = &gg->sg.nodes[ni + gg->nx];
+		break;
+		
+	case 3: /* left */
+		if (gg->left && (x != 1))
+			ei->to = &gg->sg.nodes[ni - 1];
+		break;
+
+	case 4: /* up */
+		if (gg->up && (y != 1))
+			ei->to = &gg->sg.nodes[ni - gg->nx];
+		break;
+
+	default:
+		assert(0);
+	}
+	return 0;
+}
+
+void grid_graph_init(struct grid_graph *gg, int nx, int ny,
+		     bool right, bool down, bool left, bool up)
+{
+	assert((nx * ny) < MAX_NODES);
+
+	gg->nx = nx;
+	gg->ny = ny;
+	gg->right = right;
+	gg->down = down;
+	gg->left = left;
+	gg->up = up;
+
+	simple_graph_init(&gg->sg, grid_edge_info,
+		       grid_first_edge, grid_next_edge);
+}
diff --git a/ccan/aga/test/parallel.c b/ccan/aga/test/parallel.c
new file mode 100644
index 0000000..ee27c32
--- /dev/null
+++ b/ccan/aga/test/parallel.c
@@ -0,0 +1,62 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include "simple-graph.h"
+
+static const void *parallel_first_edge(const struct aga_graph *g,
+				       const struct aga_node *n)
+{
+	struct parallel_graph *pg = container_of(g, struct parallel_graph, sg.g);
+
+	if (n != &pg->sg.nodes[1]) {
+		assert(n == &pg->sg.nodes[2]);
+		return NULL;
+	}
+
+	if (pg->nlinks)
+		return int2ptr(1);
+	else
+		return NULL;
+}
+
+static const void *parallel_next_edge(const struct aga_graph *g,
+				      const struct aga_node *n,
+				      const void *edge)
+{
+	struct parallel_graph *pg = container_of(g, struct parallel_graph, sg.g);
+	int index = ptr2int(edge);
+
+	if (n != &pg->sg.nodes[1]) {
+		assert(n == &pg->sg.nodes[2]);
+		return NULL;
+	}
+
+	if (index < pg->nlinks)
+		return int2ptr(index + 1);
+	else
+		return NULL;
+}
+
+static int parallel_edge_info(const struct aga_graph *g, const struct aga_node *n,
+			      const void *edge, struct aga_edge_info *ei)
+{
+	struct parallel_graph *pg = container_of(g, struct parallel_graph, sg.g);
+
+	assert(n == &pg->sg.nodes[1]);
+
+	ei->to = &pg->sg.nodes[2];
+	return 0;
+}
+
+void parallel_graph_init(struct parallel_graph *pg, int nlinks)
+{
+	pg->nlinks = nlinks;
+
+	simple_graph_init(&pg->sg, parallel_edge_info,
+			  parallel_first_edge, parallel_next_edge);
+}
diff --git a/ccan/aga/test/simple-graph.c b/ccan/aga/test/simple-graph.c
new file mode 100644
index 0000000..53ab783
--- /dev/null
+++ b/ccan/aga/test/simple-graph.c
@@ -0,0 +1,15 @@
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+void simple_graph_init(struct simple_graph *sg, aga_edge_info_fn edge_info,
+		       aga_first_edge_fn first_edge,
+		       aga_next_edge_fn next_edge)
+{
+	int i;
+
+	for (i = 0; i < MAX_NODES; i++)
+		aga_node_init(&sg->nodes[i]);
+
+	aga_init_graph(&sg->g, edge_info, first_edge, next_edge);
+}
diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
new file mode 100644
index 0000000..0bb266e
--- /dev/null
+++ b/ccan/aga/test/simple-graph.h
@@ -0,0 +1,180 @@
+#ifndef _TEST_GRAPHS_H
+#define _TEST_GRAPHS_H
+
+#include <stdbool.h>
+
+#define MAX_NODES	16
+#define MAX_EDGES	16 /* Max edges per node */
+
+struct simple_graph {
+	struct aga_graph g;
+	/* We don't use nodes[0] just to avoid awkward -1 and +1 in
+	 * the code */
+	struct aga_node nodes[MAX_NODES + 1];
+};
+
+void simple_graph_init(struct simple_graph *sg, aga_edge_info_fn edge_info,
+		       aga_first_edge_fn first_edge,
+		       aga_next_edge_fn next_edge);
+
+struct adjacency_list {
+	int from;
+	int to[MAX_EDGES];
+};
+
+/* Trivial graph
+ *
+ *	(A)
+ *
+ * The simplest possible graph: one node, no edges
+ */
+struct trivial_graph {
+	struct simple_graph sg;
+};
+void trivial_graph_init(struct trivial_graph *tg);
+static const struct adjacency_list trivial_adjacency[] = {
+	{1, {}},
+	{},
+};
+
+/* Parallel graph
+ *
+ *          --
+ *         /  \
+ *      (A)    => (B)
+ *         \  /
+ *          --
+ *
+ * Two nodes (A & B), with PARALLEL_NLINKS edges all from A->B.
+ */
+struct parallel_graph {
+	int nlinks;
+	struct simple_graph sg;
+};
+void parallel_graph_init(struct parallel_graph *pg, int nlinks);
+static const struct adjacency_list parallel_adjacency_nlinks3[] = {
+	{1, {2, 2, 2}},
+	{2, {}},
+	{},
+};
+
+/* Full graph
+ *
+ * n nodes with an edge from every node to every other node (including
+ * itself)
+ */
+struct full_graph {
+	int nnodes;
+	struct simple_graph sg;
+};
+void full_graph_init(struct full_graph *fg, int nnodes);
+static const struct adjacency_list full_adjacency_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(const struct aga_graph *g,
+			    const struct aga_node *node);
+const void *full_next_edge(const struct aga_graph *g,
+			   const struct aga_node *node,
+			   const void *edge);
+
+
+/* Chain graph
+ *
+ *  --> --> -->
+ * A   B   C   D
+ *  <-- <-- <--
+ *
+ * nnodes nodes arranged in a linear sequence, edges from each node to
+ * the previous and next
+ */
+struct chain_graph {
+	struct full_graph fg;
+};
+void chain_graph_init(struct chain_graph *cg, int nnodes);
+static const struct adjacency_list chain_adjacency_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_graph {
+	int nx, ny;
+	bool right, down, left, up;
+	struct simple_graph sg;
+};
+void grid_graph_init(struct grid_graph *gg, int nx, int ny,
+		     bool right, bool down, bool left, bool up);
+static const struct adjacency_list grid_adjacency_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_list grid_adjacency_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_graph {
+	struct simple_graph sg;
+};
+void error_graph_init(struct error_graph *eg);
+static const struct adjacency_list error_adjacency[] = {
+	{1, {2}},
+	{2, {}},
+	{3, {4}},
+	{4, {-1}},
+	{},
+};
+
+#endif /* _TEST_GRAPHS_H */
diff --git a/ccan/aga/test/trivial.c b/ccan/aga/test/trivial.c
new file mode 100644
index 0000000..3fcefb7
--- /dev/null
+++ b/ccan/aga/test/trivial.c
@@ -0,0 +1,39 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static const void *trivial_first_edge(const struct aga_graph *g,
+				      const struct aga_node *node)
+{
+	struct trivial_graph *tg = container_of(g, struct trivial_graph, sg.g);
+
+	assert(node == &tg->sg.nodes[1]);
+	return NULL;
+}
+
+static const void *trivial_next_edge(const struct aga_graph *g,
+				     const struct aga_node *node,
+				     const void *edge)
+{
+	assert(0);
+}
+
+static int trivial_edge_info(const struct aga_graph *g,
+			     const struct aga_node *node,
+			     const void *edge,
+			     struct aga_edge_info *ei)
+{
+	assert(0);
+}
+
+void trivial_graph_init(struct trivial_graph *tg)
+{
+	simple_graph_init(&tg->sg, trivial_edge_info,
+			  trivial_first_edge, trivial_next_edge);
+}
-- 
2.1.0



More information about the ccan mailing list