dgraph: add dgraph_check and CCAN_DGRAPH_DEBUG
[ccan] / ccan / dgraph / dgraph.c
1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
2 #include <ccan/dgraph/dgraph.h>
3 #include <stdlib.h>
4 #include <stdio.h>
5
6 void dgraph_init_node(struct dgraph_node *n)
7 {
8         tlist_init(&n->edge[DGRAPH_FROM]);
9         tlist_init(&n->edge[DGRAPH_TO]);
10 }
11
12 static void free_edge(struct dgraph_edge *e)
13 {
14         tlist_del_from(&e->n[DGRAPH_FROM]->edge[DGRAPH_FROM],
15                        e, list[DGRAPH_FROM]);
16         tlist_del_from(&e->n[DGRAPH_TO]->edge[DGRAPH_TO],
17                        e, list[DGRAPH_TO]);
18         free(e);
19 }
20
21 void dgraph_clear_node(struct dgraph_node *n)
22 {
23         struct dgraph_edge *e;
24         unsigned int i;
25
26         (void)dgraph_debug(n);
27         for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
28                 while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
29                         assert(e->n[i] == n);
30                         free_edge(e);
31                 }
32         }
33 }
34
35 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
36 {
37         struct dgraph_edge *e = malloc(sizeof(*e));
38
39         (void)dgraph_debug(from);
40         (void)dgraph_debug(to);
41         e->n[DGRAPH_FROM] = from;
42         e->n[DGRAPH_TO] = to;
43         tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
44         tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]);
45 }
46
47 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
48 {
49         struct dgraph_edge *e, *next;
50
51         (void)dgraph_debug(from);
52         (void)dgraph_debug(to);
53         dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
54                 if (e->n[DGRAPH_TO] == to) {
55                         free_edge(e);
56                         return true;
57                 }
58         }
59         return false;
60 }
61
62 static bool traverse_depth_first(struct dgraph_node *n,
63                                  enum dgraph_dir dir,
64                                  bool (*fn)(struct dgraph_node *, void *),
65                                  const void *data)
66 {
67         struct dgraph_edge *e, *next;
68
69         /* dgraph_for_each_edge_safe, without dgraph_debug() */
70         tlist_for_each_safe(&n->edge[dir], e, next, list[dir]) {
71                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
72                         return false;
73         }
74         return fn(n, (void *)data);
75 }
76
77 void dgraph_traverse(const struct dgraph_node *n,
78                      enum dgraph_dir dir,
79                      bool (*fn)(struct dgraph_node *, void *),
80                      const void *data)
81 {
82         struct dgraph_edge *e, *next;
83
84         /* dgraph_for_each_edge_safe, without dgraph_debug() */
85         tlist_for_each_safe(&n->edge[dir], e, next, list[dir]) {
86                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
87                         break;
88         }
89 }
90
91 struct check_info {
92         const struct dgraph_node *ret;
93         const char *abortstr;
94 };
95
96 static bool find_backedge(const struct dgraph_node *from,
97                           const struct dgraph_node *to,
98                           enum dgraph_dir dir)
99 {
100         struct dgraph_edge *e;
101
102         tlist_for_each(&from->edge[dir], e, list[dir]) {
103                 if (e->n[!dir] == to)
104                         return true;
105         }
106         return false;
107 }
108
109 static bool dgraph_check_node(struct dgraph_node *n, void *info_)
110 {
111         struct check_info *info = info_;
112         unsigned int dir;
113         struct dgraph_edge *e;
114
115         for (dir = DGRAPH_FROM; dir <= DGRAPH_TO; dir++) {
116                 /* First, check edges list. */
117                 if (!tlist_check(&n->edge[dir], info->abortstr)) {
118                         info->ret = NULL;
119                         return false;
120                 }
121
122                 /* dgraph_for_each_edge() without check! */
123                 tlist_for_each(&n->edge[dir], e, list[dir]) {
124                         if (e->n[dir] == n) {
125                                 if (find_backedge(e->n[!dir], n, !dir))
126                                         continue;
127                                 if (info->abortstr) {
128                                         fprintf(stderr,
129                                                 "%s: node %p %s edge doesnt"
130                                                 " point back to %p\n",
131                                                 info->abortstr, e->n[!dir],
132                                                 !dir == DGRAPH_FROM
133                                                 ? "DGRAPH_FROM" : "DGRAPH_TO",
134                                                 n);
135                                         abort();
136                                 }
137                                 info->ret = NULL;
138                                 return false;
139                         }
140
141                         if (info->abortstr) {
142                                 fprintf(stderr,
143                                         "%s: node %p %s edge %p points"
144                                         " to %p\n",
145                                         info->abortstr, n,
146                                         dir == DGRAPH_FROM
147                                         ? "DGRAPH_FROM" : "DGRAPH_TO",
148                                         e, e->n[dir]);
149                                 abort();
150                         }
151                         info->ret = NULL;
152                         return false;
153                 }
154         }
155
156         return true;
157 }
158
159 struct dgraph_node *dgraph_check(const struct dgraph_node *n,
160                                  const char *abortstr)
161 {
162         struct check_info info;
163
164         /* This gets set to NULL by dgraph_check_node on failure. */
165         info.ret = n;
166         info.abortstr = abortstr;
167
168         dgraph_check_node((struct dgraph_node *)info.ret, &info);
169
170         if (info.ret)
171                 dgraph_traverse(n, DGRAPH_FROM, dgraph_check_node, &info);
172         if (info.ret)
173                 dgraph_traverse(n, DGRAPH_TO, dgraph_check_node, &info);
174         return (void *)info.ret;
175 }