dgraph: new module for directed graphs.

diff --git a/ccan/dgraph/LICENSE b/ccan/dgraph/LICENSE
new file mode 120000 (symlink)
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/dgraph/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file

diff --git a/ccan/dgraph/_info b/ccan/dgraph/_info
new file mode 100644 (file)
index 0000000..10c8296
--- /dev/null
+++ b/ccan/dgraph/_info
@@ -0,0 +1,24 @@
+#include "config.h"
+#include <string.h>
+
+/**
+ * dgraph - simple directed graph module
+ *
+ * This code implements a simple directed graph, with nodes and edges.
+ *
+ * License: LGPL (v2.1 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/tlist\n");
+               printf("ccan/typesafe_cb\n");
+               return 0;
+       }
+
+       return 1;
+}

diff --git a/ccan/dgraph/dgraph.c b/ccan/dgraph/dgraph.c
new file mode 100644 (file)
index 0000000..9a6f662
--- /dev/null
+++ b/ccan/dgraph/dgraph.c
@@ -0,0 +1,80 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#include <ccan/dgraph/dgraph.h>
+#include <stdlib.h>
+
+void dgraph_init_node(struct dgraph_node *n)
+{
+       tlist_init(&n->edge[DGRAPH_FROM]);
+       tlist_init(&n->edge[DGRAPH_TO]);
+}
+
+static void free_edge(struct dgraph_edge *e)
+{
+       tlist_del_from(&e->n[DGRAPH_FROM]->edge[DGRAPH_FROM],
+                      e, list[DGRAPH_FROM]);
+       tlist_del_from(&e->n[DGRAPH_TO]->edge[DGRAPH_TO],
+                      e, list[DGRAPH_TO]);
+       free(e);
+}
+
+void dgraph_clear_node(struct dgraph_node *n)
+{
+       struct dgraph_edge *e;
+       unsigned int i;
+
+       for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
+               while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
+                       assert(e->n[i] == n);
+                       free_edge(e);
+               }
+       }
+}
+
+void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
+{
+       struct dgraph_edge *e = malloc(sizeof(*e));
+       e->n[DGRAPH_FROM] = from;
+       e->n[DGRAPH_TO] = to;
+       tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
+       tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]);
+}
+
+bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
+{
+       struct dgraph_edge *e, *next;
+
+       dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
+               if (e->n[DGRAPH_TO] == to) {
+                       free_edge(e);
+                       return true;
+               }
+       }
+       return false;
+}
+
+static bool traverse_depth_first(struct dgraph_node *n,
+                                enum dgraph_dir dir,
+                                bool (*fn)(struct dgraph_node *, void *),
+                                const void *data)
+{
+       struct dgraph_edge *e, *next;
+
+       dgraph_for_each_edge_safe(n, e, next, dir) {
+               if (!traverse_depth_first(e->n[!dir], dir, fn, data))
+                       return false;
+       }
+       return fn(n, (void *)data);
+}
+
+void dgraph_traverse(struct dgraph_node *n,
+                    enum dgraph_dir dir,
+                    bool (*fn)(struct dgraph_node *, void *),
+                    const void *data)
+{
+       struct dgraph_edge *e, *next;
+
+       dgraph_for_each_edge_safe(n, e, next, dir) {
+               if (!traverse_depth_first(e->n[!dir], dir, fn, data))
+                       break;
+       }
+}

diff --git a/ccan/dgraph/dgraph.h b/ccan/dgraph/dgraph.h
new file mode 100644 (file)
index 0000000..dd1723f
--- /dev/null
+++ b/ccan/dgraph/dgraph.h
@@ -0,0 +1,67 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#ifndef CCAN_DGRAPH_H
+#define CCAN_DGRAPH_H
+#include "config.h"
+#include <ccan/tlist/tlist.h>
+#include <ccan/typesafe_cb/typesafe_cb.h>
+#include <stdbool.h>
+
+enum dgraph_dir {
+       DGRAPH_FROM,
+       DGRAPH_TO
+};
+
+/* strust tlist_dgraph_edge: a list of edges */
+TLIST_TYPE(dgraph_edge, struct dgraph_edge);
+
+/**
+ * struct dgraph_node - a node in a directed graph.
+ * @edge: edges indexed by enum dgraph_dir.
+ *
+ * edge[DGRAPH_FROM] edges have n[DGRAPH_FROM] == this.
+ * edge[DGRAPH_TO] edges have n[DGRAPH_TO] == this.
+ */
+struct dgraph_node {
+       struct tlist_dgraph_edge edge[2];
+};
+
+/**
+ * struct dgraph_edge - an edge in a directed graph.
+ * @list: our nodes's list of edges, indexed by enum dgraph_dir.
+ * @n: the nodes, indexed by enum dgraph_dir.
+ */
+struct dgraph_edge {
+       struct list_node list[2];
+       struct dgraph_node *n[2];
+};
+
+void dgraph_init_node(struct dgraph_node *n);
+void dgraph_clear_node(struct dgraph_node *n);
+void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to);
+bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to);
+
+/* You can dgraph_clear_node() the node you're on safely. */
+#define dgraph_traverse_from(n, fn, arg)                               \
+       dgraph_traverse((n), DGRAPH_FROM,                               \
+                       typesafe_cb_preargs(bool, void *, (fn), (arg),  \
+                                           struct dgraph_node *),      \
+                       (arg))
+
+#define dgraph_traverse_to(n, fn, arg)                                 \
+       dgraph_traverse((n), DGRAPH_TO,                                 \
+                       typesafe_cb_preargs(bool, void *, (fn), (arg),  \
+                                           struct dgraph_node *),      \
+                       (arg))
+
+void dgraph_traverse(struct dgraph_node *n,
+                    enum dgraph_dir dir,
+                    bool (*fn)(struct dgraph_node *from, void *data),
+                    const void *data);
+
+#define dgraph_for_each_edge(n, i, dir)                \
+       tlist_for_each(&(n)->edge[dir], i, list[dir])
+
+#define dgraph_for_each_edge_safe(n, i, next, dir)             \
+       tlist_for_each_safe(&(n)->edge[dir], i, next, list[dir])
+
+#endif /* CCAN_DGRAPH_H */

diff --git a/ccan/dgraph/test/run.c b/ccan/dgraph/test/run.c
new file mode 100644 (file)
index 0000000..b868c18
--- /dev/null
+++ b/ccan/dgraph/test/run.c
@@ -0,0 +1,116 @@
+#include <ccan/dgraph/dgraph.h>
+/* Include the C files directly. */
+#include <ccan/dgraph/dgraph.c>
+#include <ccan/tap/tap.h>
+
+static bool count_nodes(struct dgraph_node *n, unsigned int *count)
+{
+       (*count)++;
+       return true;
+}
+
+static bool stop_traverse(struct dgraph_node *n, unsigned int *count)
+{
+       if (--(*count) == 0)
+               return false;
+       return true;
+}
+
+int main(void)
+{
+       struct dgraph_node n1, n2, n3;
+       unsigned int count = 0;
+
+       /* This is how many tests you plan to run */
+       plan_tests(25);
+
+       dgraph_init_node(&n1);
+       count = 0;
+       dgraph_traverse_from(&n1, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n1, count_nodes, &count);
+       ok1(count == 0);
+
+       dgraph_init_node(&n2);
+       dgraph_add_edge(&n1, &n2);
+       count = 0;
+       dgraph_traverse_from(&n1, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_to(&n1, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 1);
+
+       dgraph_init_node(&n3);
+       dgraph_add_edge(&n2, &n3);
+       count = 0;
+       dgraph_traverse_from(&n1, count_nodes, &count);
+       ok1(count == 2);
+       count = 0;
+       dgraph_traverse_to(&n1, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_from(&n3, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n3, count_nodes, &count);
+       ok1(count == 2);
+
+       /* Check stopping traverse. */
+       count = 1;
+       dgraph_traverse_from(&n1, stop_traverse, &count);
+       ok1(count == 0);
+       count = 2;
+       dgraph_traverse_from(&n1, stop_traverse, &count);
+       ok1(count == 0);
+       count = 3;
+       dgraph_traverse_from(&n1, stop_traverse, &count);
+       ok1(count == 1);
+
+       dgraph_clear_node(&n1);
+
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 1);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n3, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n3, count_nodes, &count);
+       ok1(count == 1);
+
+       ok1(dgraph_del_edge(&n2, &n3));
+       count = 0;
+       dgraph_traverse_from(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n2, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_from(&n3, count_nodes, &count);
+       ok1(count == 0);
+       count = 0;
+       dgraph_traverse_to(&n3, count_nodes, &count);
+       ok1(count == 0);
+
+       ok1(!dgraph_del_edge(&n2, &n3));
+       dgraph_clear_node(&n2);
+
+       /* This exits depending on whether all tests passed */
+       return exit_status();
+}