endian: add constant versions.

[ccan] / ccan / dgraph / dgraph.c

diff --git a/ccan/dgraph/dgraph.c b/ccan/dgraph/dgraph.c
index 9a6f66245dbe9ff533353ee308d56422dfe6134e..eb5a62d2c7a3d52223c61fc7aa221d30e33d242f 100644 (file)
--- 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>
 /* 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)
 {
 
 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;
 
        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);
        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_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]);
        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;
 
 {
        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);
        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;
 
 {
        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);
 }
 
                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;
 
                     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;
        }
 }
                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;
+}