git.ozlabs.org Git - ccan/blob - 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 ? &nn->n : NULL;
  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 }