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
  83         rc = sr->gr->edge_info(sr->gr, nr, e, &eir);
  84
  85         if (eir.to)
  86                 ei->to = nr_to_n(sr, eir.to);
  87         else
  88                 ei->to = NULL;
  89
  90         return rc;
  91 }
  92
  93 static const void *convert_first_edge(const struct aga_graph *g,
  94                                       const struct aga_node *n)
  95 {
  96         struct agar_state *sr = container_of(g, struct agar_state, g);
  97         const void *nr = n_to_nr(sr, n);
  98
  99         return sr->gr->first_edge(sr->gr, nr);
 100 }
 101
 102 static const void *convert_next_edge(const struct aga_graph *g,
 103                                      const struct aga_node *n,
 104                                      const void *e)
 105 {
 106         struct agar_state *sr = container_of(g, struct agar_state, g);
 107         const void *nr = n_to_nr(sr, n);
 108
 109         return sr->gr->next_edge(sr->gr, nr, e);
 110 }
 111
 112 void agar_init_graph(struct agar_graph *gr,
 113                      agar_first_edge_fn first_edge,
 114                      agar_next_edge_fn next_edge,
 115                      agar_edge_info_fn edge_info)
 116 {
 117         gr->edge_info = edge_info;
 118         gr->first_edge = first_edge;
 119         gr->next_edge = next_edge;
 120 }
 121
 122 int agar_error(struct agar_state *sr)
 123 {
 124         return aga_error(&sr->g);
 125 }
 126
 127 static void agar_destruct_htable(struct agar_state *sr)
 128 {
 129         htable_clear(&sr->nodes);
 130 }
 131
 132 static struct agar_state *agar_new(void *ctx, struct agar_graph *gr)
 133 {
 134         struct agar_state *sr = tal(ctx, struct agar_state);
 135
 136         assert(sr);
 137
 138         sr->gr = gr;
 139         htable_init(&sr->nodes, agar_rehash, NULL);
 140         tal_add_destructor(sr, agar_destruct_htable);
 141         aga_init_graph(&sr->g, convert_first_edge, convert_next_edge,
 142                        convert_edge_info);
 143
 144         return sr;
 145 }
 146
 147 const void *agar_first_edge(const struct agar_graph *gr, const void *nr)
 148 {
 149         return gr->first_edge(gr, nr);
 150 }
 151
 152 const void *agar_next_edge(const struct agar_graph *gr,
 153                            const void *nr, const void *e)
 154 {
 155         if (!e)
 156                 return NULL;
 157         else
 158                 return gr->next_edge(gr, nr, e);
 159 }
 160
 161 int agar_edge_info(const struct agar_graph *gr, const void *nr, const void *e,
 162                    struct agar_edge_info *eir)
 163 {
 164         int rc;
 165
 166         eir->to = NULL;
 167         rc = gr->edge_info(gr, nr, e, eir);
 168         assert(rc <= 0);
 169         return rc;
 170 }
 171
 172 /*
 173  * Depth first search
 174  */
 175
 176 struct agar_dfs_state {
 177         struct agar_state sr;
 178 };
 179
 180 struct agar_state *agar_dfs_new(void *ctx, struct agar_graph *gr)
 181 {
 182         struct agar_state *sr = agar_new(ctx, gr);
 183
 184         if (aga_dfs_start(&sr->g) < 0) {
 185                 tal_free(sr);
 186                 return NULL;
 187         }
 188
 189         return sr;
 190 }
 191
 192 bool agar_dfs_explore(struct agar_state *sr, const void *nr,
 193                       const void **nextr)
 194 {
 195         struct aga_node *next;
 196
 197         next = aga_dfs_explore(&sr->g, nr_to_n(sr, nr));
 198         if (!next)
 199                 return false;
 200
 201         *nextr = n_to_nr(sr, next);
 202         return true;
 203 }
 204
 205 /*
 206  * Breadth first search
 207  */
 208
 209 struct agar_state *agar_bfs_new(void *ctx, struct agar_graph *gr)
 210 {
 211         struct agar_state *sr = agar_new(ctx, gr);
 212
 213         if (aga_bfs_start(&sr->g) < 0) {
 214                 tal_free(sr);
 215                 return NULL;
 216         }
 217
 218         return sr;
 219 }
 220
 221 bool agar_bfs_explore(struct agar_state *sr, const void *nr,
 222                       const void **nextr)
 223 {
 224         struct aga_node *next;
 225
 226         next = aga_bfs_explore(&sr->g, nr_to_n(sr, nr));
 227         if (!next)
 228                 return false;
 229
 230         *nextr = n_to_nr(sr, next);
 231         return true;
 232 }