1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
2 #include <ccan/dgraph/dgraph.h>
5 void dgraph_init_node(struct dgraph_node *n)
7 tlist_init(&n->edge[DGRAPH_FROM]);
8 tlist_init(&n->edge[DGRAPH_TO]);
11 static void free_edge(struct dgraph_edge *e)
13 tlist_del_from(&e->n[DGRAPH_FROM]->edge[DGRAPH_FROM],
14 e, list[DGRAPH_FROM]);
15 tlist_del_from(&e->n[DGRAPH_TO]->edge[DGRAPH_TO],
20 void dgraph_clear_node(struct dgraph_node *n)
22 struct dgraph_edge *e;
25 for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
26 while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
33 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
35 struct dgraph_edge *e = malloc(sizeof(*e));
36 e->n[DGRAPH_FROM] = from;
38 tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
39 tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]);
42 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
44 struct dgraph_edge *e, *next;
46 dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
47 if (e->n[DGRAPH_TO] == to) {
55 static bool traverse_depth_first(struct dgraph_node *n,
57 bool (*fn)(struct dgraph_node *, void *),
60 struct dgraph_edge *e, *next;
62 dgraph_for_each_edge_safe(n, e, next, dir) {
63 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
66 return fn(n, (void *)data);
69 void dgraph_traverse(struct dgraph_node *n,
71 bool (*fn)(struct dgraph_node *, void *),
74 struct dgraph_edge *e, *next;
76 dgraph_for_each_edge_safe(n, e, next, dir) {
77 if (!traverse_depth_first(e->n[!dir], dir, fn, data))