--- /dev/null
+../../licenses/LGPL-2.1
\ No newline at end of file
--- /dev/null
+#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;
+}
--- /dev/null
+/* 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;
+ }
+}
--- /dev/null
+/* 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 */
--- /dev/null
+#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();
+}