X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fdgraph%2Fdgraph.c;fp=ccan%2Fdgraph%2Fdgraph.c;h=9a6f66245dbe9ff533353ee308d56422dfe6134e;hp=0000000000000000000000000000000000000000;hb=ed4ee95401575dd314f7ca5b3719e0e22ef0c6e5;hpb=4c6f5a73a0817641571fad7383ec3604487889f8

diff --git a/ccan/dgraph/dgraph.c b/ccan/dgraph/dgraph.c
new file mode 100644
index 00000000..9a6f6624
--- /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;
+	}
+}