1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
2 #include <ccan/dgraph/dgraph.h>
6 void dgraph_init_node(struct dgraph_node *n)
8 tlist_init(&n->edge[DGRAPH_FROM]);
9 tlist_init(&n->edge[DGRAPH_TO]);
12 static void free_edge(struct dgraph_edge *e)
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],
21 void dgraph_clear_node(struct dgraph_node *n)
23 struct dgraph_edge *e;
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) {
35 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
37 struct dgraph_edge *e = malloc(sizeof(*e));
39 (void)dgraph_debug(from);
40 (void)dgraph_debug(to);
41 e->n[DGRAPH_FROM] = from;
43 tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
44 tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]);
47 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
49 struct dgraph_edge *e, *next;
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) {
62 static bool traverse_depth_first(struct dgraph_node *n,
64 bool (*fn)(struct dgraph_node *, void *),
67 struct dgraph_edge *e, *next;
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))
74 return fn(n, (void *)data);
77 void dgraph_traverse(const struct dgraph_node *n,
79 bool (*fn)(struct dgraph_node *, void *),
82 struct dgraph_edge *e, *next;
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))
92 const struct dgraph_node *ret;
96 static bool find_backedge(const struct dgraph_node *from,
97 const struct dgraph_node *to,
100 struct dgraph_edge *e;
102 tlist_for_each(&from->edge[dir], e, list[dir]) {
103 if (e->n[!dir] == to)
109 static bool dgraph_check_node(struct dgraph_node *n, void *info_)
111 struct check_info *info = info_;
113 struct dgraph_edge *e;
115 for (dir = DGRAPH_FROM; dir <= DGRAPH_TO; dir++) {
116 /* First, check edges list. */
117 if (!tlist_check(&n->edge[dir], info->abortstr)) {
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))
127 if (info->abortstr) {
129 "%s: node %p %s edge doesnt"
130 " point back to %p\n",
131 info->abortstr, e->n[!dir],
133 ? "DGRAPH_FROM" : "DGRAPH_TO",
141 if (info->abortstr) {
143 "%s: node %p %s edge %p points"
147 ? "DGRAPH_FROM" : "DGRAPH_TO",
159 struct dgraph_node *dgraph_check(const struct dgraph_node *n,
160 const char *abortstr)
162 struct check_info info;
164 /* This gets set to NULL by dgraph_check_node on failure. */
166 info.abortstr = abortstr;
168 dgraph_check_node((struct dgraph_node *)info.ret, &info);
171 dgraph_traverse(n, DGRAPH_FROM, dgraph_check_node, &info);
173 dgraph_traverse(n, DGRAPH_TO, dgraph_check_node, &info);
174 return (void *)info.ret;