if (strcmp(argv[1], "testdepends") == 0) {
printf("ccan/container_of\n");
+ printf("ccan/ptrint\n");
return 0;
}
--- /dev/null
+#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;
+ struct traversal1_graph t1g;
+
+ plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6 + 21);
+
+ 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);
+
+ traversal1_graph_init(&t1g);
+ test_adjacency("traversal1 graph", &t1g.sg, traversal1_adjacency);
+
+ return exit_status();
+}
--- /dev/null
+#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,
+ struct aga_node *edge,
+ struct aga_edge_info *ei)
+{
+ if ((edge == node + 1) || (node == edge + 1))
+ ei->to = edge;
+
+ return 0;
+}
+
+void chain_graph_init(struct chain_graph *cg, int nnodes)
+{
+ cg->fg.nnodes = nnodes;
+ simple_graph_init(&cg->fg.sg, full_first_edge, full_next_edge,
+ chain_edge_info);
+}
--- /dev/null
+#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 ptrint_t *error_first_edge(const struct aga_graph *g,
+ const struct aga_node *n)
+{
+ return int2ptr(1);
+}
+
+static ptrint_t *error_next_edge(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *edge)
+{
+ assert(edge == int2ptr(1));
+
+ return NULL;
+}
+
+static int error_edge_info(const struct aga_graph *g, const struct aga_node *n,
+ ptrint_t *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_first_edge, error_next_edge,
+ error_edge_info);
+}
--- /dev/null
+#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"
+
+struct aga_node *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];
+}
+
+struct aga_node *full_next_edge(const struct aga_graph *g,
+ const struct aga_node *node,
+ struct aga_node *edge)
+{
+ struct full_graph *fg = container_of(g, struct full_graph, sg.g);
+ int index = (edge - fg->sg.nodes);
+
+ if (index < fg->nnodes)
+ return &fg->sg.nodes[index + 1];
+ else
+ return NULL;
+}
+
+static int full_edge_info(const struct aga_graph *g,
+ const struct aga_node *node,
+ struct aga_node *edge,
+ struct aga_edge_info *ei)
+{
+ ei->to = edge;
+ 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_first_edge, full_next_edge,
+ full_edge_info);
+}
--- /dev/null
+#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 ptrint_t *grid_first_edge(const struct aga_graph *g,
+ const struct aga_node *n)
+{
+ return int2ptr(1);
+}
+
+static ptrint_t *grid_next_edge(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *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,
+ ptrint_t *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_first_edge, grid_next_edge,
+ grid_edge_info);
+}
--- /dev/null
+#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 ptrint_t *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 ptrint_t *parallel_next_edge(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *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,
+ ptrint_t *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_first_edge, parallel_next_edge,
+ parallel_edge_info);
+}
--- /dev/null
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+void simple_graph_init_(struct simple_graph *sg)
+{
+ int i;
+
+ for (i = 0; i < MAX_NODES; i++)
+ aga_node_init(&sg->nodes[i]);
+}
--- /dev/null
+#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);
+#define simple_graph_init(sg_, fefn_, nefn_, eifn_) \
+ do { \
+ simple_graph_init_((sg_)); \
+ aga_init_graph(&(sg_)->g, (fefn_), (nefn_), (eifn_)); \
+ } while (0)
+
+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}},
+ {},
+};
+struct aga_node *full_first_edge(const struct aga_graph *g,
+ const struct aga_node *node);
+struct aga_node *full_next_edge(const struct aga_graph *g,
+ const struct aga_node *node,
+ struct aga_node *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}},
+ {},
+};
+
+/* 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_graph {
+ struct simple_graph sg;
+};
+void traversal1_graph_init(struct traversal1_graph *t1g);
+static const struct adjacency_list traversal1_adjacency[] = {
+ {1, {2, 3}},
+ {2, {4, 5}},
+ {3, {5, 6}},
+ {4, {}},
+ {5, {}},
+ {6, {}},
+ {7, {5, 4}},
+ {8, {6, 5}},
+ {9, {8, 7}},
+ {},
+};
+
+#endif /* _TEST_GRAPHS_H */
--- /dev/null
+#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 ptrint_t *traversal1_first_edge(const struct aga_graph *g,
+ const struct aga_node *n)
+{
+ struct traversal1_graph *t1g = container_of(g, struct traversal1_graph,
+ sg.g);
+ int ni = n - t1g->sg.nodes;
+
+ 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 ptrint_t *traversal1_next_edge(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e)
+{
+ struct traversal1_graph *t1g = container_of(g, struct traversal1_graph,
+ sg.g);
+ int ni = n - t1g->sg.nodes;
+ 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(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e, struct aga_edge_info *ei)
+{
+ struct traversal1_graph *t1g = container_of(g, struct traversal1_graph,
+ sg.g);
+ int ni = n - t1g->sg.nodes;
+ int index = ptr2int(e);
+
+ assert((index == 1) || (index == 2));
+
+ switch (ni) {
+ case 1:
+ if (index == 1)
+ ei->to = &t1g->sg.nodes[2];
+ else
+ ei->to = &t1g->sg.nodes[3];
+ break;
+
+ case 2:
+ if (index == 1)
+ ei->to = &t1g->sg.nodes[4];
+ else
+ ei->to = &t1g->sg.nodes[5];
+ break;
+ case 3:
+ if (index == 1)
+ ei->to = &t1g->sg.nodes[5];
+ else
+ ei->to = &t1g->sg.nodes[6];
+ break;
+
+ case 7:
+ if (index == 1)
+ ei->to = &t1g->sg.nodes[5];
+ else
+ ei->to = &t1g->sg.nodes[4];
+ break;
+
+ case 8:
+ if (index == 1)
+ ei->to = &t1g->sg.nodes[6];
+ else
+ ei->to = &t1g->sg.nodes[5];
+ break;
+
+ case 9:
+ if (index == 1)
+ ei->to = &t1g->sg.nodes[8];
+ else
+ ei->to = &t1g->sg.nodes[7];
+ break;
+
+ default:
+ assert(0);
+ }
+ return 0;
+}
+
+void traversal1_graph_init(struct traversal1_graph *t1g)
+{
+ simple_graph_init(&t1g->sg, traversal1_first_edge,
+ traversal1_next_edge,
+ traversal1_edge_info);
+}
--- /dev/null
+#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_first_edge, trivial_next_edge,
+ trivial_edge_info);
+}
projects / ccan / commitdiff