agar: Remove unnecessary NULL check
[ccan] / ccan / agar / agar.c
1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #include "config.h"
3
4 #include <stdbool.h>
5
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>
11
12 #include <ccan/agar/agar.h>
13
14 #define HASH_BASE 0
15
16 struct agar_node {
17         const void *nr;
18         struct aga_node n;
19 };
20
21 struct agar_state {
22         struct agar_graph *gr;
23         struct aga_graph g;
24         struct htable nodes;
25 };
26
27 static size_t agar_node_hash(const struct agar_node *nn)
28 {
29         return hash_pointer(nn->nr, HASH_BASE);
30 }
31
32 static size_t agar_rehash(const void *elem, void *p)
33 {
34         return agar_node_hash(elem);
35 }
36
37 static bool agar_node_cmp(const void *candidate, void *ptr)
38 {
39         struct agar_node *nn = (struct agar_node *)candidate;
40
41         return (nn->nr == ptr);
42 }
43
44 static struct aga_node *nr_to_n(struct agar_state *sr, const void *nr)
45 {
46         struct agar_node *nn;
47         size_t hash = hash_pointer(nr, HASH_BASE);
48         bool rc;
49
50         nn = htable_get(&sr->nodes, hash, agar_node_cmp, nr);
51         if (!nn) {
52                 nn = tal(sr, struct agar_node);
53                 assert(nn);
54
55                 nn->nr = nr;
56                 aga_node_init(&nn->n);
57
58                 rc = htable_add(&sr->nodes, hash, nn);
59                 assert(rc);
60         }
61
62         return &nn->n;
63 }
64
65 static const void *n_to_nr(struct agar_state *sr, const struct aga_node *n)
66 {
67         struct agar_node *nn = container_of(n, struct agar_node, n);
68
69         return nn->nr;
70 }
71
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)
75 {
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;
79         int rc;
80
81         eir.to = NULL;
82         eir.icost = ei->icost; /* Inherit the default from aga */
83
84         rc = sr->gr->edge_info(sr->gr, nr, e, &eir);
85
86         if (eir.to)
87                 ei->to = nr_to_n(sr, eir.to);
88         else
89                 ei->to = NULL;
90
91         ei->icost = eir.icost;
92
93         return rc;
94 }
95
96 static const void *convert_first_edge(const struct aga_graph *g,
97                                       const struct aga_node *n)
98 {
99         struct agar_state *sr = container_of(g, struct agar_state, g);
100         const void *nr = n_to_nr(sr, n);
101
102         return sr->gr->first_edge(sr->gr, nr);
103 }
104
105 static const void *convert_next_edge(const struct aga_graph *g,
106                                      const struct aga_node *n,
107                                      const void *e)
108 {
109         struct agar_state *sr = container_of(g, struct agar_state, g);
110         const void *nr = n_to_nr(sr, n);
111
112         return sr->gr->next_edge(sr->gr, nr, e);
113 }
114
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)
119 {
120         gr->edge_info = edge_info;
121         gr->first_edge = first_edge;
122         gr->next_edge = next_edge;
123 }
124
125 int agar_error(struct agar_state *sr)
126 {
127         return aga_error(&sr->g);
128 }
129
130 static void agar_destruct_htable(struct agar_state *sr)
131 {
132         htable_clear(&sr->nodes);
133 }
134
135 static struct agar_state *agar_new(void *ctx, struct agar_graph *gr)
136 {
137         struct agar_state *sr = tal(ctx, struct agar_state);
138
139         assert(sr);
140
141         sr->gr = gr;
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,
145                        convert_edge_info);
146
147         return sr;
148 }
149
150 const void *agar_first_edge(const struct agar_graph *gr, const void *nr)
151 {
152         return gr->first_edge(gr, nr);
153 }
154
155 const void *agar_next_edge(const struct agar_graph *gr,
156                            const void *nr, const void *e)
157 {
158         if (!e)
159                 return NULL;
160         else
161                 return gr->next_edge(gr, nr, e);
162 }
163
164 int agar_edge_info(const struct agar_graph *gr, const void *nr, const void *e,
165                    struct agar_edge_info *eir)
166 {
167         int rc;
168
169         eir->to = NULL;
170         eir->icost = 1;
171         rc = gr->edge_info(gr, nr, e, eir);
172         assert(rc <= 0);
173         return rc;
174 }
175
176 /*
177  * Depth first search
178  */
179
180 struct agar_dfs_state {
181         struct agar_state sr;
182 };
183
184 struct agar_state *agar_dfs_new(void *ctx, struct agar_graph *gr)
185 {
186         struct agar_state *sr = agar_new(ctx, gr);
187
188         if (aga_dfs_start(&sr->g) < 0) {
189                 tal_free(sr);
190                 return NULL;
191         }
192
193         return sr;
194 }
195
196 bool agar_dfs_explore(struct agar_state *sr, const void *nr,
197                       const void **nextr)
198 {
199         struct aga_node *next;
200
201         next = aga_dfs_explore(&sr->g, nr_to_n(sr, nr));
202         if (!next)
203                 return false;
204
205         *nextr = n_to_nr(sr, next);
206         return true;
207 }
208
209 /*
210  * Breadth first search
211  */
212
213 struct agar_state *agar_bfs_new(void *ctx, struct agar_graph *gr)
214 {
215         struct agar_state *sr = agar_new(ctx, gr);
216
217         if (aga_bfs_start(&sr->g) < 0) {
218                 tal_free(sr);
219                 return NULL;
220         }
221
222         return sr;
223 }
224
225 bool agar_bfs_explore(struct agar_state *sr, const void *nr,
226                       const void **nextr)
227 {
228         struct aga_node *next;
229
230         next = aga_bfs_explore(&sr->g, nr_to_n(sr, nr));
231         if (!next)
232                 return false;
233
234         *nextr = n_to_nr(sr, next);
235         return true;
236 }
237
238 /*
239  * Dijkstra's algorithm
240  */
241
242 struct agar_state *agar_dijkstra_new(void *ctx, struct agar_graph *gr,
243                                      const void *nr)
244 {
245         struct agar_state *sr = agar_new(ctx, gr);
246
247         if (aga_dijkstra_start(&sr->g, nr_to_n(sr, nr)) < 0) {
248                 tal_free(sr);
249                 return NULL;
250         }
251
252         return sr;
253 }
254
255 bool agar_dijkstra_step(struct agar_state *sr, const void **nextr)
256 {
257         struct aga_node *next = aga_dijkstra_step(&sr->g);
258
259         if (!next)
260                 return false;
261
262         *nextr = n_to_nr(sr, next);
263         return true;
264 }
265
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)
269 {
270         struct aga_node *dest = nr_to_n(sr, destr);
271         struct aga_node *prev;
272
273         if (!aga_dijkstra_path(&sr->g, dest, total_cost, &prev, prevedge))
274                 return false;
275
276         /*
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. */
283         if (prevr && prev)
284                 *prevr = n_to_nr(sr, prev);
285
286         return true;
287 }
288
289 void agar_dijkstra_complete(struct agar_state *sr)
290 {
291         aga_dijkstra_complete(&sr->g);
292 }
293
294
295 /*
296  * Bellman-Ford algorithm
297  */
298
299 struct agar_state *agar_bellman_ford_new(void *ctx, struct agar_graph *gr,
300                                          const void *nr)
301 {
302         struct agar_state *sr = agar_new(ctx, gr);
303
304         if (aga_bellman_ford_start(&sr->g, nr_to_n(sr, nr)) < 0) {
305                 tal_free(sr);
306                 return NULL;
307         }
308
309         return sr;
310 }
311
312 bool agar_bellman_ford_path(struct agar_state *sr, const void *destr,
313                             aga_icost_t *total_cost,
314                             const void **prevr, const void **prevedge)
315 {
316         struct aga_node *dest = nr_to_n(sr, destr);
317         struct aga_node *prev;
318
319         if (!aga_bellman_ford_path(&sr->g, dest, total_cost, &prev, prevedge))
320                 return false;
321
322         /*
323          * When destr is the same as the source node, there obviously
324          * isn't a previous node or edge.  In that case aga sets them
325          * to NULL.  But for agar, NULL could be a valid node
326          * references (particularly if using ptrint).  So we don't
327          * have much choice here but to leave *prevr as undefined when
328          * destr is the source node. */
329         if (prevr && prev)
330                 *prevr = n_to_nr(sr, prev);
331
332         return true;
333 }
334
335 void agar_bellman_ford_complete(struct agar_state *sr)
336 {
337         aga_bellman_ford_complete(&sr->g);
338 }