X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fdgraph%2Fdgraph.c;h=eb5a62d2c7a3d52223c61fc7aa221d30e33d242f;hp=9a6f66245dbe9ff533353ee308d56422dfe6134e;hb=bc1ebe804ee892ef18eef1b48589c50c14230dd3;hpb=02358a946a10fc2222b9966f3861cdc10a5550b8

diff --git a/ccan/dgraph/dgraph.c b/ccan/dgraph/dgraph.c
index 9a6f6624..eb5a62d2 100644
--- a/ccan/dgraph/dgraph.c
+++ b/ccan/dgraph/dgraph.c
@@ -1,6 +1,7 @@
 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
 #include <ccan/dgraph/dgraph.h>
 #include <stdlib.h>
+#include <stdio.h>
 
 void dgraph_init_node(struct dgraph_node *n)
 {
@@ -22,6 +23,7 @@ void dgraph_clear_node(struct dgraph_node *n)
 	struct dgraph_edge *e;
 	unsigned int i;
 
+	(void)dgraph_debug(n);
 	for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
 		while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
 			assert(e->n[i] == n);
@@ -33,6 +35,9 @@ void dgraph_clear_node(struct dgraph_node *n)
 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
 {
 	struct dgraph_edge *e = malloc(sizeof(*e));
+
+	(void)dgraph_debug(from);
+	(void)dgraph_debug(to);
 	e->n[DGRAPH_FROM] = from;
 	e->n[DGRAPH_TO] = to;
 	tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
@@ -43,6 +48,8 @@ bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
 {
 	struct dgraph_edge *e, *next;
 
+	(void)dgraph_debug(from);
+	(void)dgraph_debug(to);
 	dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
 		if (e->n[DGRAPH_TO] == to) {
 			free_edge(e);
@@ -59,22 +66,110 @@ static bool traverse_depth_first(struct dgraph_node *n,
 {
 	struct dgraph_edge *e, *next;
 
-	dgraph_for_each_edge_safe(n, e, next, dir) {
+	/* dgraph_for_each_edge_safe, without dgraph_debug() */
+	tlist_for_each_safe(&n->edge[dir], e, next, list[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,
+void dgraph_traverse(const 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) {
+	/* dgraph_for_each_edge_safe, without dgraph_debug() */
+	tlist_for_each_safe(&n->edge[dir], e, next, list[dir]) {
 		if (!traverse_depth_first(e->n[!dir], dir, fn, data))
 			break;
 	}
 }
+
+struct check_info {
+	const struct dgraph_node *ret;
+	const char *abortstr;
+};
+
+static bool find_backedge(const struct dgraph_node *from,
+			  const struct dgraph_node *to,
+			  enum dgraph_dir dir)
+{
+	struct dgraph_edge *e;
+
+	tlist_for_each(&from->edge[dir], e, list[dir]) {
+		if (e->n[!dir] == to)
+			return true;
+	}
+	return false;
+}
+
+static bool dgraph_check_node(struct dgraph_node *n, void *info_)
+{
+	struct check_info *info = info_;
+	unsigned int dir;
+	struct dgraph_edge *e;
+
+	for (dir = DGRAPH_FROM; dir <= DGRAPH_TO; dir++) {
+		/* First, check edges list. */
+		if (!tlist_check(&n->edge[dir], info->abortstr)) {
+			info->ret = NULL;
+			return false;
+		}
+
+		/* dgraph_for_each_edge() without check! */
+		tlist_for_each(&n->edge[dir], e, list[dir]) {
+			if (e->n[dir] == n) {
+				if (find_backedge(e->n[!dir], n, !dir))
+					continue;
+				if (info->abortstr) {
+					fprintf(stderr,
+						"%s: node %p %s edge doesnt"
+						" point back to %p\n",
+						info->abortstr, e->n[!dir],
+						!dir == DGRAPH_FROM
+						? "DGRAPH_FROM" : "DGRAPH_TO",
+						n);
+					abort();
+				}
+				info->ret = NULL;
+				return false;
+			}
+
+			if (info->abortstr) {
+				fprintf(stderr,
+					"%s: node %p %s edge %p points"
+					" to %p\n",
+					info->abortstr, n,
+					dir == DGRAPH_FROM
+					? "DGRAPH_FROM" : "DGRAPH_TO",
+					e, e->n[dir]);
+				abort();
+			}
+			info->ret = NULL;
+			return false;
+		}
+	}
+
+	return true;
+}
+
+struct dgraph_node *dgraph_check(const struct dgraph_node *n,
+				 const char *abortstr)
+{
+	struct check_info info;
+
+	/* This gets set to NULL by dgraph_check_node on failure. */
+	info.ret = n;
+	info.abortstr = abortstr;
+
+	dgraph_check_node((struct dgraph_node *)info.ret, &info);
+
+	if (info.ret)
+		dgraph_traverse(n, DGRAPH_FROM, dgraph_check_node, &info);
+	if (info.ret)
+		dgraph_traverse(n, DGRAPH_TO, dgraph_check_node, &info);
+	return (void *)info.ret;
+}