[ccan] [PATCH 4/4] agar: Re-entrant Abstract Graph Algorithms

David Gibson david at gibson.dropbear.id.au
Mon Jul 7 22:51:03 EST 2014


The graph algorithms 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 patch adds a new "agar" module which uses the aga module to provide
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.

Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
 ccan/agar/LICENSE          |   1 +
 ccan/agar/_info            |  39 ++++++++
 ccan/agar/agar.c           | 140 ++++++++++++++++++++++++++
 ccan/agar/agar.h           |  30 ++++++
 ccan/agar/test/helper.h    |  19 ++++
 ccan/agar/test/run-chain.c | 111 +++++++++++++++++++++
 ccan/agar/test/run-grid.c  | 244 +++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 584 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/helper.h
 create mode 100644 ccan/agar/test/run-chain.c
 create mode 100644 ccan/agar/test/run-grid.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..0261b4e
--- /dev/null
+++ b/ccan/agar/_info
@@ -0,0 +1,39 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * agar - Abstract Graph Algorithms (Re-entrant)
+ *
+ * This modules contains several standard graph algorithms,
+ * implemented so that they don't rely on a specific represnetation of
+ * the graph structure.  Instead, user supplied callbacks can compute
+ * the graph's edges as required.  Graph nodes can even be constructed
+ * on the fly as they're discovered by edge traversal.
+ *
+ * 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");
+		return 0;
+	}
+
+	return 1;
+}
diff --git a/ccan/agar/agar.c b/ccan/agar/agar.c
new file mode 100644
index 0000000..e7453a9
--- /dev/null
+++ b/ccan/agar/agar.c
@@ -0,0 +1,140 @@
+/* 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 {
+	void *xnode;
+	struct aga_node n;
+};
+
+struct agar_state {
+	struct agar_graph *gr;
+	struct aga_graph g;
+	struct htable nodes;
+	agar_visit_fn visit;
+};
+
+static size_t agar_node_hash(const struct agar_node *node)
+{
+	return hash_pointer(node->xnode, 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 *nr = (struct agar_node *)candidate;
+
+	return (nr->xnode == ptr);
+}
+
+static struct agar_node *get_agar_node(struct agar_state *s, void *xnode)
+{
+	struct agar_node *nr;
+	size_t hash = hash_pointer(xnode, HASH_BASE);
+
+	nr = htable_get(&s->nodes, hash, agar_node_cmp, xnode);
+	if (nr)
+		return nr;
+
+	nr = tal(s, struct agar_node);
+	if (!nr)
+		abort();
+
+	nr->xnode = xnode;
+	aga_node_init(&nr->n);
+
+	if (!htable_add(&s->nodes, hash, nr))
+		abort();
+
+	return nr;
+}
+
+static void *agar_to_aga_edge(struct aga_graph *g, struct aga_node *node,
+			      struct aga_edge *edge, void *p)
+{
+	struct agar_state *s = container_of(g, struct agar_state, g);
+	struct agar_node *nr = container_of(node, struct agar_node, n);
+	struct agar_edge er;
+
+	p = s->gr->edge_fn(s->gr, nr->xnode, &er, p);
+	if (p) {
+		struct agar_node *to = get_agar_node(s, er.to);
+		
+		edge->to = &to->n;
+	}
+
+	return p;
+}
+
+static int agar_to_aga_visit(struct aga_graph *g,
+			     struct aga_node *n, void *opaque)
+{
+	struct agar_state *s = container_of(g, struct agar_state, g);
+	struct agar_node *nr = container_of(n, struct agar_node, n);
+
+	return s->visit(nr->xnode, opaque);
+}
+
+void agar_init(struct agar_graph *g, agar_edge_fn edge_fn)
+{
+	g->edge_fn = edge_fn;
+}
+
+static struct agar_state *agar_start(struct agar_graph *gr, agar_visit_fn fn)
+{
+	struct agar_state *s = tal(NULL, struct agar_state);
+
+	s->gr = gr;
+	htable_init(&s->nodes, agar_rehash, NULL);
+	aga_init(&s->g, agar_to_aga_edge);
+	s->visit = fn;
+	return s;
+}
+
+static void agar_finish(struct agar_state *s)
+{
+	htable_clear(&s->nodes);
+	tal_free(s);
+}
+
+int agar_depth_first_search(struct agar_graph *g, void *start,
+			    agar_visit_fn fn, void *opaque)
+{
+	struct agar_state *s = agar_start(g, fn);
+	int ret;
+
+	ret = aga_depth_first_search(&s->g, &get_agar_node(s, start)->n,
+				     agar_to_aga_visit, opaque);
+
+	agar_finish(s);
+
+	return ret;
+}
+
+int agar_breadth_first_search(struct agar_graph *g, void *start,
+			      agar_visit_fn fn, void *opaque)
+{
+	struct agar_state *s = agar_start(g, fn);
+	int ret;
+
+	ret = aga_breadth_first_search(&s->g, &get_agar_node(s, start)->n,
+				       agar_to_aga_visit, opaque);
+	agar_finish(s);
+
+	return ret;
+}
diff --git a/ccan/agar/agar.h b/ccan/agar/agar.h
new file mode 100644
index 0000000..dde2c81
--- /dev/null
+++ b/ccan/agar/agar.h
@@ -0,0 +1,30 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#ifndef CCAN_AGAR_H
+#define CCAN_AGAR_H
+#include "config.h"
+#include <string.h>
+
+struct agar_edge {
+	void *to;
+};
+
+struct agar_graph;
+
+typedef void *(*agar_edge_fn)(struct agar_graph *, void *,
+			      struct agar_edge *, void *);
+
+struct agar_graph {
+	agar_edge_fn edge_fn;
+};
+
+void agar_init(struct agar_graph *g, agar_edge_fn edge_fn);
+
+typedef int(*agar_visit_fn)(void *, void *);
+
+int agar_depth_first_search(struct agar_graph *g, void *start,
+			    agar_visit_fn fn, void *opaque);
+
+int agar_breadth_first_search(struct agar_graph *g, void *start,
+			      agar_visit_fn fn, void *opaque);
+
+#endif /* CCAN_AGAR_H */
diff --git a/ccan/agar/test/helper.h b/ccan/agar/test/helper.h
new file mode 100644
index 0000000..e159472
--- /dev/null
+++ b/ccan/agar/test/helper.h
@@ -0,0 +1,19 @@
+#define MAX_TRACE 128
+
+struct tracebuf {
+	int n;
+	int l[MAX_TRACE];
+};
+
+static void add_trace(struct tracebuf *tb, int val)
+{
+	assert(tb->n < MAX_TRACE);
+	tb->l[tb->n++] = val;
+}
+
+#define check_trace(tb, ...)  \
+	do { \
+		int cmp[] = { __VA_ARGS__ };		\
+		ok1((ARRAY_SIZE(cmp) == (tb)->n) \
+		    && (memcmp(cmp, (tb)->l, sizeof(cmp)) == 0));	\
+	} while (0)
diff --git a/ccan/agar/test/run-chain.c b/ccan/agar/test/run-chain.c
new file mode 100644
index 0000000..8f8be7e
--- /dev/null
+++ b/ccan/agar/test/run-chain.c
@@ -0,0 +1,111 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/agar/agar.h>
+/* Include the C files directly. */
+#include <ccan/agar/agar.c>
+#include <ccan/tap/tap.h>
+
+#include <ccan/array_size/array_size.h>
+
+#include "helper.h"
+
+#define CHAIN_LENGTH 8
+
+struct agar_graph chain_graph;
+
+static void *chain_edge_fn(struct agar_graph *g, void *node,
+			   struct agar_edge *edge, void *p)
+{
+	int n = (ptrdiff_t)node;
+	ptrdiff_t prev = p ? (ptrdiff_t) p : 0;
+	ptrdiff_t next;
+
+	switch (prev) {
+	case 0:
+		next = (n > 0) ? -1 : 1;
+		break;
+
+	case -1:
+		next = (n < (CHAIN_LENGTH - 1)) ? 1 : 0;
+		break;
+
+	case 1:
+		next = 0;
+		break;
+	}
+
+	if (!next)
+		return NULL;
+
+	edge->to = (void *)(n + next);
+	return (void *)next;
+}
+
+static void setup(void)
+{
+	agar_init(&chain_graph, chain_edge_fn);
+}
+
+static int visit_fn(void *node, void *opaque)
+{
+	struct tracebuf *tb = (struct tracebuf *)opaque;
+	int index = (ptrdiff_t)node;
+
+	diag("Visited %d\n", index);
+
+	add_trace(tb, index);
+
+	return 0;
+}
+
+int main(void)
+{
+	struct tracebuf tb;
+
+	setup();
+
+	/* This is how many tests you plan to run */
+	plan_tests(6);
+
+	/* Depth-first traverse forwards */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&chain_graph, (void *)0, visit_fn, &tb);
+	check_trace(&tb, 0, 1, 2, 3, 4, 5, 6, 7);
+
+	/* Depth-first traverse backwards */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&chain_graph, (void *)(CHAIN_LENGTH - 1),
+				visit_fn, &tb);
+	check_trace(&tb, 7, 6, 5, 4, 3, 2, 1, 0);
+
+	/* Depth-first traverse outwards */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&chain_graph, (void *)(CHAIN_LENGTH/2),
+				visit_fn, &tb);
+	check_trace(&tb, 4, 3, 2, 1, 0, 5, 6, 7);
+
+
+	/* Breadth-first traversee forwards */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&chain_graph, (void *)0, visit_fn, &tb);
+	check_trace(&tb, 0, 1, 2, 3, 4, 5, 6, 7);
+
+	/* Breadth-first traversee backwards */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&chain_graph, (void *)(CHAIN_LENGTH - 1),
+				  visit_fn, &tb);
+	check_trace(&tb, 7, 6, 5, 4, 3, 2, 1, 0);
+
+	/* Breadth-first traversee outwards */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&chain_graph, (void *)(CHAIN_LENGTH/2),
+				  visit_fn, &tb);
+	check_trace(&tb, 4, 3, 5, 2, 6, 1, 7, 0);
+
+
+	/* This exits depending on whether all tests passed */
+	return exit_status();
+}
diff --git a/ccan/agar/test/run-grid.c b/ccan/agar/test/run-grid.c
new file mode 100644
index 0000000..638cd71
--- /dev/null
+++ b/ccan/agar/test/run-grid.c
@@ -0,0 +1,244 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+/* Include the C files directly. */
+#include <ccan/agar/agar.c>
+#include <ccan/tap/tap.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/array_size/array_size.h>
+
+#include "helper.h"
+
+#define GRID_X 3
+#define GRID_Y 3
+#define GRID_SIZE (GRID_X * GRID_Y)
+
+static struct agar_graph grid_graph_a;
+static struct agar_graph grid_graph_b;
+
+static void *grid_edge_fn_a(struct agar_graph *g, void *node,
+			    struct agar_edge *edge, void *p)
+{
+	int n = (ptrdiff_t)node;
+	ptrdiff_t x = n % GRID_X;
+	ptrdiff_t y = n / GRID_X;
+	int index = p ? (ptrdiff_t) p : 0;
+	bool done = false;
+
+	do {
+		switch (index) {
+		case 0:
+			if (x < (GRID_X - 1)) {
+				edge->to = (void *)(y * GRID_Y + x + 1);
+				done = true;
+			}
+			break;
+
+		case 1:
+			if (y < (GRID_Y - 1)) {
+				edge->to = (void *)((y + 1) * GRID_Y + x);
+				done = true;
+			}
+			break;
+
+		default:
+			assert(index == 2);
+			return NULL;
+		};
+
+		index++;
+	} while (!done);
+
+	return (void *)((ptrdiff_t)index);
+}
+
+static void *grid_edge_fn_b(struct agar_graph *g, void *node,
+			    struct agar_edge *edge, void *p)
+{
+	int n = (ptrdiff_t)node;
+	ptrdiff_t x = n % GRID_X;
+	ptrdiff_t y = n / GRID_X;
+	int index = p ? (ptrdiff_t) p : 0;
+	bool done = false;
+
+	do {
+		switch (index) {
+		case 0:
+			if (x < (GRID_X - 1)) {
+				edge->to = (void *)(y * GRID_Y + x + 1);
+				done = true;
+			}
+			break;
+
+		case 1:
+			if (y < (GRID_Y - 1)) {
+				edge->to = (void *)((y + 1) * GRID_Y + x);
+				done = true;
+			}
+			break;
+
+		case 2:
+			if (x > 0) {
+				edge->to = (void *)(y * GRID_Y + x - 1);
+				done = true;
+			}
+			break;
+
+		case 3:
+			if (y > 0) {
+				edge->to = (void *)((y - 1) * GRID_Y + x);
+				done = true;
+			}
+			break;
+
+		default:
+			assert(index == 4);
+			return NULL;
+		};
+
+		index++;
+	} while (!done);
+
+	return (void *)((ptrdiff_t)index);
+}
+
+static void setup(void)
+{
+	agar_init(&grid_graph_a, grid_edge_fn_a);
+	agar_init(&grid_graph_b, grid_edge_fn_b);
+}
+
+static int visit_fn(void *node, void *opaque)
+{
+	int n = (ptrdiff_t)node;
+	int x = n % GRID_X;
+	int y = n / GRID_X;
+	struct tracebuf *tb = (struct tracebuf *)opaque;
+
+	diag("Visited (%d, %d)\n", x, y);
+
+	add_trace(tb, n);
+
+	return 0;
+}
+
+int main(void)
+{
+	struct tracebuf tb;
+
+	setup();
+
+	/* This is how many tests you plan to run */
+	plan_tests(20);
+
+	/* (A) Depth-first traverse from top-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_a, (void *)0, visit_fn, &tb);
+	check_trace(&tb, 0, 1, 2, 5, 8, 4, 7, 3, 6);
+
+	/* (A) Depth-first traverse from top-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_a, (void *)2, visit_fn, &tb);
+	check_trace(&tb, 2, 5, 8);
+
+	/* (A) Depth-first traverse from bottom-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_a, (void *)6, visit_fn, &tb);
+	check_trace(&tb, 6, 7, 8);
+
+	/* (A) Depth-first traverse from bottom-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_a, (void *)8, visit_fn, &tb);
+	check_trace(&tb, 8);
+
+	/* (A) Depth-first traverse from centre */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_a, (void *)4, visit_fn, &tb);
+	check_trace(&tb, 4, 5, 8, 7);
+
+
+	/* (A) Breadth-first traverse from top-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_a, (void *)0, visit_fn, &tb);
+	check_trace(&tb, 0, 1, 3, 2, 4, 6, 5, 7, 8);
+
+	/* (A) Breadth-first traverse from top-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_a, (void *)2, visit_fn, &tb);
+	check_trace(&tb, 2, 5, 8);
+
+	/* (A) Breadth-first traverse from bottom-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_a, (void *)6, visit_fn, &tb);
+	check_trace(&tb, 6, 7, 8);
+
+	/* (A) Breadth-first traverse from bottom-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_a, (void *)8, visit_fn, &tb);
+	check_trace(&tb, 8);
+
+	/* (A) Breadth-first traverse from centre */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_a, (void *)4, visit_fn, &tb);
+	check_trace(&tb, 4, 5, 7, 8);
+
+
+	/* (B) Depth-first traverse from top-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_b, (void *)0, visit_fn, &tb);
+	check_trace(&tb, 0, 1, 2, 5, 8, 7, 6, 3, 4);
+
+	/* (B) Depth-first traverse from top-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_b, (void *)2, visit_fn, &tb);
+	check_trace(&tb, 2, 5, 8, 7, 6, 3, 4, 1, 0);
+
+	/* (B) Depth-first traverse from bottom-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_b, (void *)6, visit_fn, &tb);
+	check_trace(&tb, 6, 7, 8, 5, 4, 3, 0, 1, 2);
+
+	/* (B) Depth-first traverse from bottom-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_b, (void *)8, visit_fn, &tb);
+	check_trace(&tb, 8, 7, 6, 3, 4, 5, 2, 1, 0);
+
+	/* (B) Depth-first traverse from centre */
+	memset(&tb, 0, sizeof(tb));
+	agar_depth_first_search(&grid_graph_b, (void *)4, visit_fn, &tb);
+	check_trace(&tb, 4, 5, 8, 7, 6, 3, 0, 1, 2);
+
+
+	/* (B) Breadth-first traverse from top-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_b, (void *)0, visit_fn, &tb);
+	check_trace(&tb, 0, 1, 3, 2, 4, 6, 5, 7, 8);
+
+	/* (B) Breadth-first traverse from top-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_b, (void *)2, visit_fn, &tb);
+	check_trace(&tb, 2, 5, 1, 8, 4, 0, 7, 3, 6);
+
+	/* (B) Breadth-first traverse from bottom-left */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_b, (void *)6, visit_fn, &tb);
+	check_trace(&tb, 6, 7, 3, 8, 4, 0, 5, 1, 2);
+
+	/* (B) Breadth-first traverse from bottom-right */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_b, (void *)8, visit_fn, &tb);
+	check_trace(&tb, 8, 7, 5, 6, 4, 2, 3, 1, 0);
+
+	/* (B) Breadth-first traverse from centre */
+	memset(&tb, 0, sizeof(tb));
+	agar_breadth_first_search(&grid_graph_b, (void *)4, visit_fn, &tb);
+	check_trace(&tb, 4, 5, 7, 3, 1, 8, 2, 6, 0);
+
+
+	/* This exits depending on whether all tests passed */
+	return exit_status();
+}
-- 
1.9.3



More information about the ccan mailing list