1 /* Licensed under LGPLv2+ - see LICENSE file for details */
6 #include <ccan/aga/aga.h>
7 #include <ccan/hash/hash.h>
8 #include <ccan/htable/htable.h>
9 #include <ccan/container_of/container_of.h>
10 #include <ccan/tal/tal.h>
12 #include <ccan/agar/agar.h>
22 struct agar_graph *gr;
27 static size_t agar_node_hash(const struct agar_node *nn)
29 return hash_pointer(nn->nr, HASH_BASE);
32 static size_t agar_rehash(const void *elem, void *p)
34 return agar_node_hash(elem);
37 static bool agar_node_cmp(const void *candidate, void *ptr)
39 struct agar_node *nn = (struct agar_node *)candidate;
41 return (nn->nr == ptr);
44 static struct aga_node *nr_to_n(struct agar_state *sr, const void *nr)
47 size_t hash = hash_pointer(nr, HASH_BASE);
50 nn = htable_get(&sr->nodes, hash, agar_node_cmp, nr);
52 nn = tal(sr, struct agar_node);
56 aga_node_init(&nn->n);
58 rc = htable_add(&sr->nodes, hash, nn);
62 return nn ? &nn->n : NULL;
65 static const void *n_to_nr(struct agar_state *sr, const struct aga_node *n)
67 struct agar_node *nn = container_of(n, struct agar_node, n);
72 static int convert_edge_info(const struct aga_graph *g,
73 const struct aga_node *n,
74 const void *e, struct aga_edge_info *ei)
76 struct agar_state *sr = container_of(g, struct agar_state, g);
77 const void *nr = n_to_nr(sr, n);
78 struct agar_edge_info eir;
82 eir.icost = ei->icost; /* Inherit the default from aga */
84 rc = sr->gr->edge_info(sr->gr, nr, e, &eir);
87 ei->to = nr_to_n(sr, eir.to);
91 ei->icost = eir.icost;
96 static const void *convert_first_edge(const struct aga_graph *g,
97 const struct aga_node *n)
99 struct agar_state *sr = container_of(g, struct agar_state, g);
100 const void *nr = n_to_nr(sr, n);
102 return sr->gr->first_edge(sr->gr, nr);
105 static const void *convert_next_edge(const struct aga_graph *g,
106 const struct aga_node *n,
109 struct agar_state *sr = container_of(g, struct agar_state, g);
110 const void *nr = n_to_nr(sr, n);
112 return sr->gr->next_edge(sr->gr, nr, e);
115 void agar_init_graph(struct agar_graph *gr,
116 agar_first_edge_fn first_edge,
117 agar_next_edge_fn next_edge,
118 agar_edge_info_fn edge_info)
120 gr->edge_info = edge_info;
121 gr->first_edge = first_edge;
122 gr->next_edge = next_edge;
125 int agar_error(struct agar_state *sr)
127 return aga_error(&sr->g);
130 static void agar_destruct_htable(struct agar_state *sr)
132 htable_clear(&sr->nodes);
135 static struct agar_state *agar_new(void *ctx, struct agar_graph *gr)
137 struct agar_state *sr = tal(ctx, struct agar_state);
142 htable_init(&sr->nodes, agar_rehash, NULL);
143 tal_add_destructor(sr, agar_destruct_htable);
144 aga_init_graph(&sr->g, convert_first_edge, convert_next_edge,
150 const void *agar_first_edge(const struct agar_graph *gr, const void *nr)
152 return gr->first_edge(gr, nr);
155 const void *agar_next_edge(const struct agar_graph *gr,
156 const void *nr, const void *e)
161 return gr->next_edge(gr, nr, e);
164 int agar_edge_info(const struct agar_graph *gr, const void *nr, const void *e,
165 struct agar_edge_info *eir)
171 rc = gr->edge_info(gr, nr, e, eir);
180 struct agar_dfs_state {
181 struct agar_state sr;
184 struct agar_state *agar_dfs_new(void *ctx, struct agar_graph *gr)
186 struct agar_state *sr = agar_new(ctx, gr);
188 if (aga_dfs_start(&sr->g) < 0) {
196 bool agar_dfs_explore(struct agar_state *sr, const void *nr,
199 struct aga_node *next;
201 next = aga_dfs_explore(&sr->g, nr_to_n(sr, nr));
205 *nextr = n_to_nr(sr, next);
210 * Breadth first search
213 struct agar_state *agar_bfs_new(void *ctx, struct agar_graph *gr)
215 struct agar_state *sr = agar_new(ctx, gr);
217 if (aga_bfs_start(&sr->g) < 0) {
225 bool agar_bfs_explore(struct agar_state *sr, const void *nr,
228 struct aga_node *next;
230 next = aga_bfs_explore(&sr->g, nr_to_n(sr, nr));
234 *nextr = n_to_nr(sr, next);
239 * Dijkstra's algorithm
242 struct agar_state *agar_dijkstra_new(void *ctx, struct agar_graph *gr,
245 struct agar_state *sr = agar_new(ctx, gr);
247 if (aga_dijkstra_start(&sr->g, nr_to_n(sr, nr)) < 0) {
255 bool agar_dijkstra_step(struct agar_state *sr, const void **nextr)
257 struct aga_node *next = aga_dijkstra_step(&sr->g);
262 *nextr = n_to_nr(sr, next);
266 bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
267 aga_icost_t *total_cost,
268 const void **prevr, const void **prevedge)
270 struct aga_node *dest = nr_to_n(sr, destr);
271 struct aga_node *prev;
273 if (!aga_dijkstra_path(&sr->g, dest, total_cost, &prev, prevedge))
277 * When destr is the same as the source node, there obviously
278 * isn't a previous node or edge. In that case aga, sets them
279 * to NULL. But for agar, NULL could be a valid node
280 * references (particularly if using ptrint). So we don't
281 * have much choice here but to leave *prevr as undefined when
282 * destr is the source node. */
284 *prevr = n_to_nr(sr, prev);
289 void agar_dijkstra_all_paths(struct agar_state *sr)
291 aga_dijkstra_all_paths(&sr->g);