From bc1ebe804ee892ef18eef1b48589c50c14230dd3 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 14 Jan 2013 18:05:14 +1030 Subject: [PATCH] dgraph: add dgraph_check and CCAN_DGRAPH_DEBUG This is good form for datastructures, so caller can track weird bugs. Signed-off-by: Rusty Russell --- ccan/dgraph/dgraph.c | 101 +++++++++++++++++++++++++- ccan/dgraph/dgraph.h | 28 ++++++-- ccan/dgraph/test/run-debug.c | 135 +++++++++++++++++++++++++++++++++++ ccan/dgraph/test/run.c | 20 +++++- 4 files changed, 275 insertions(+), 9 deletions(-) create mode 100644 ccan/dgraph/test/run-debug.c 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 #include +#include 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; +} diff --git a/ccan/dgraph/dgraph.h b/ccan/dgraph/dgraph.h index dd1723fb..6c82798c 100644 --- a/ccan/dgraph/dgraph.h +++ b/ccan/dgraph/dgraph.h @@ -40,28 +40,46 @@ 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); +#ifdef CCAN_DGRAPH_DEBUG +#define dgraph_debug(n) dgraph_check((n), __func__) +#else +#define dgraph_debug(n) (n) +#endif + /* You can dgraph_clear_node() the node you're on safely. */ #define dgraph_traverse_from(n, fn, arg) \ - dgraph_traverse((n), DGRAPH_FROM, \ + dgraph_traverse(dgraph_debug(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, \ + dgraph_traverse(dgraph_debug(n), DGRAPH_TO, \ typesafe_cb_preargs(bool, void *, (fn), (arg), \ struct dgraph_node *), \ (arg)) -void dgraph_traverse(struct dgraph_node *n, +void dgraph_traverse(const 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]) + tlist_for_each(&dgraph_debug(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]) + tlist_for_each_safe(&dgraph_debug(n)->edge[dir], i, next, list[dir]) +/** + * dgraph_check - check a graph for consistency + * @n: the dgraph_node to check. + * @abortstr: the string to print on aborting, or NULL. + * + * Returns @n if the list is consistent, NULL if not (it can never + * return NULL if @abortstr is set). + * + * See also: tlist_check() + */ +struct dgraph_node *dgraph_check(const struct dgraph_node *n, + const char *abortstr); #endif /* CCAN_DGRAPH_H */ diff --git a/ccan/dgraph/test/run-debug.c b/ccan/dgraph/test/run-debug.c new file mode 100644 index 00000000..d9d3265e --- /dev/null +++ b/ccan/dgraph/test/run-debug.c @@ -0,0 +1,135 @@ +#define CCAN_DGRAPH_DEBUG 1 +#include +/* Include the C files directly. */ +#include +#include + +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(42); + + dgraph_init_node(&n1); + ok1(dgraph_check(&n1, NULL) == &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); + ok1(dgraph_check(&n2, NULL) == &n2); + dgraph_add_edge(&n1, &n2); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &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); + ok1(dgraph_check(&n3, NULL) == &n3); + dgraph_add_edge(&n2, &n3); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &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); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &n3); + + 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_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &n3); + + ok1(!dgraph_del_edge(&n2, &n3)); + dgraph_clear_node(&n2); + + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &n3); + + /* This exits depending on whether all tests passed */ + return exit_status(); +} diff --git a/ccan/dgraph/test/run.c b/ccan/dgraph/test/run.c index b868c18a..0253ac24 100644 --- a/ccan/dgraph/test/run.c +++ b/ccan/dgraph/test/run.c @@ -22,9 +22,10 @@ int main(void) unsigned int count = 0; /* This is how many tests you plan to run */ - plan_tests(25); + plan_tests(42); dgraph_init_node(&n1); + ok1(dgraph_check(&n1, NULL) == &n1); count = 0; dgraph_traverse_from(&n1, count_nodes, &count); ok1(count == 0); @@ -33,7 +34,10 @@ int main(void) ok1(count == 0); dgraph_init_node(&n2); + ok1(dgraph_check(&n2, NULL) == &n2); dgraph_add_edge(&n1, &n2); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); count = 0; dgraph_traverse_from(&n1, count_nodes, &count); ok1(count == 1); @@ -48,7 +52,11 @@ int main(void) ok1(count == 1); dgraph_init_node(&n3); + ok1(dgraph_check(&n3, NULL) == &n3); dgraph_add_edge(&n2, &n3); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &n3); count = 0; dgraph_traverse_from(&n1, count_nodes, &count); ok1(count == 2); @@ -80,6 +88,9 @@ int main(void) ok1(count == 1); dgraph_clear_node(&n1); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &n3); count = 0; dgraph_traverse_from(&n2, count_nodes, &count); @@ -107,10 +118,17 @@ int main(void) count = 0; dgraph_traverse_to(&n3, count_nodes, &count); ok1(count == 0); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &n3); ok1(!dgraph_del_edge(&n2, &n3)); dgraph_clear_node(&n2); + ok1(dgraph_check(&n1, NULL) == &n1); + ok1(dgraph_check(&n2, NULL) == &n2); + ok1(dgraph_check(&n3, NULL) == &n3); + /* This exits depending on whether all tests passed */ return exit_status(); } -- 2.39.2