tdb2: copy tdb1's changed expansion logic.
[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
5 void dgraph_init_node(struct dgraph_node *n)
6 {
7         tlist_init(&n->edge[DGRAPH_FROM]);
8         tlist_init(&n->edge[DGRAPH_TO]);
9 }
10
11 static void free_edge(struct dgraph_edge *e)
12 {
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],
16                        e, list[DGRAPH_TO]);
17         free(e);
18 }
19
20 void dgraph_clear_node(struct dgraph_node *n)
21 {
22         struct dgraph_edge *e;
23         unsigned int i;
24
25         for (i = DGRAPH_FROM; i <= DGRAPH_TO; i++) {
26                 while ((e = tlist_top(&n->edge[i], list[i])) != NULL) {
27                         assert(e->n[i] == n);
28                         free_edge(e);
29                 }
30         }
31 }
32
33 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to)
34 {
35         struct dgraph_edge *e = malloc(sizeof(*e));
36         e->n[DGRAPH_FROM] = from;
37         e->n[DGRAPH_TO] = to;
38         tlist_add(&from->edge[DGRAPH_FROM], e, list[DGRAPH_FROM]);
39         tlist_add(&to->edge[DGRAPH_TO], e, list[DGRAPH_TO]);
40 }
41
42 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to)
43 {
44         struct dgraph_edge *e, *next;
45
46         dgraph_for_each_edge_safe(from, e, next, DGRAPH_FROM) {
47                 if (e->n[DGRAPH_TO] == to) {
48                         free_edge(e);
49                         return true;
50                 }
51         }
52         return false;
53 }
54
55 static bool traverse_depth_first(struct dgraph_node *n,
56                                  enum dgraph_dir dir,
57                                  bool (*fn)(struct dgraph_node *, void *),
58                                  const void *data)
59 {
60         struct dgraph_edge *e, *next;
61
62         dgraph_for_each_edge_safe(n, e, next, dir) {
63                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
64                         return false;
65         }
66         return fn(n, (void *)data);
67 }
68
69 void dgraph_traverse(struct dgraph_node *n,
70                      enum dgraph_dir dir,
71                      bool (*fn)(struct dgraph_node *, void *),
72                      const void *data)
73 {
74         struct dgraph_edge *e, *next;
75
76         dgraph_for_each_edge_safe(n, e, next, dir) {
77                 if (!traverse_depth_first(e->n[!dir], dir, fn, data))
78                         break;
79         }
80 }