git.ozlabs.org Git - ccan/blob - ccan/aga/aga.h

   1 /* Licensed under LGPLv2+ - see LICENSE file for details */
   2 #ifndef CCAN_AGA_H
   3 #define CCAN_AGA_H
   4 /*
   5  * Abstract Graph Algorithms
   6  *
   7  * This module implements several standard algorithms on "abstract"
   8  * (directed) graphs.  That is to say rather than requiring a specific
   9  * concrete representation of the graph, user-supplied callbacks allow
  10  * the graph to be constructed as it is explored.
  11  *
  12  *
  13  * Node representation
  14  * ===================
  15  *
  16  * Graph nodes are represented by 'struct aga_node'
  17  *
  18  * - These will often be embedded in a caller-specific structure
  19  *   (calling code can then locate its own structures using
  20  *   container_of)
  21  *
  22  * - Nodes are semi-persistent - they MAY be constructed on the fly by
  23  *   the edge_info callback (see below), but MUST then remain in place
  24  *   at least as long as the completion of the current graph
  25  *   algorithm.
  26  *
  27  * - Nodes must be initialized with aga_node_init(), either up front,
  28  *   or as they are constructed on the fly.
  29  *
  30  * - The contents of the structure should be treated as opaque by the
  31  *   caller.
  32  *
  33  *
  34  * Edge representation
  35  * ===================
  36  *
  37  * Graph edges are reported by three caller supplied functions,
  38  * 'first_edge', 'next_edge' and 'edge_info'.
  39  *
  40  * - Edges are identified by a (void *)
  41  * - The combination of a graph, a node and this (void *) MUST
  42  *   uniquely identify an edge
  43  * - Different edges leading from different nodes MAY have the same
  44  *   (void *) identifier
  45  * - NULL has a special meaning (indicating there are no more edges
  46  *   from a given node).
  47  * - Otherwise, edge identifiers are treated as opaque by aga
  48  *
  49  * - Calling first_edge, followed by next_edge repeatedly must iterate
  50  *   through all the edges leading from node n.
  51  *
  52  * - Either first_edge or next_edge may return NULL indicating there
  53  *   are no further edges from this node
  54  *
  55  * - edge_info MAY return a negative value in case of error.  This
  56  *   will generally abort any aga algorithm which encounters it.
  57  *
  58  * - Otherwise edge_info must return 0.  Any other return value will
  59  *   cause an abort().
  60  *
  61  * - edge_info MAY set ei->to to NULL, indicating a "missing" edge,
  62  *   thus there MAY be more edge identifiers than actual edges from a
  63  *   given node.  Otherwise, edge_info MUST fill in the ei->to field
  64  *   with a pointer to the destination node of the given edge
  65  *
  66  * - The ei->to field for a returned edge MAY point to an existing
  67  *   struct aga_node, or it MAY have just been allocated by the edge
  68  *   callback itself.  If the latter, it MUST have been initialized
  69  *   with aga_node_init() before the edge callback returns.
  70  *
  71  * - If a node is contructed by the edge callback, any subsequent
  72  *   reference to that node by the edge callback for *any* node and
  73  *   index MUST use the same pointer.
  74  *
  75  * Concurrency
  76  * ===========
  77  *
  78  * - Because the algorithms implemented here keep state in the
  79  *   aga_node structures, only one algorithm can run at a time.
  80  *   Global state for algorithms is stored in the aga_graph structure.
  81  *
  82  * - When you start an algorithm (aga_*_start()) the graph is marked
  83  *   as in-use.
  84  *
  85  * - Subsequent attempts to start an algorithm will fail;
  86  *   aga_*_start() will return -1.
  87  *
  88  * - To release the graph for another algorithm, use aga_finish().
  89  *
  90  * - Calling functions associated with one algorithm while another is
  91  *   running has undefined results.
  92  *
  93  * Errors
  94  * ======
  95  *
  96  * - Errors may be reported by the edge_info callback, or may be
  97  *   detected internally by algorithms.
  98  *
  99  * - Algorithms will generally stop running when they encounter an
 100  *   error; the call which detects the error and subsequent calls will
 101  *   return a "safe", but otherwise meaningless value.
 102  *
 103  * - After an error is encountered aga_error() will return a non-zero
 104  *   value.  Negative values are reserved for errors reported by the
 105  *   user supplied edge callback.  Positive values are reserved for
 106  *   errors detected interally by aga.
 107  *
 108  * - Errors are cleared on aga_finish().
 109  */
 110 #include "config.h"
 111 #include <string.h>
 112
 113 #include <ccan/build_assert/build_assert.h>
 114 #include <ccan/check_type/check_type.h>
 115 #include <ccan/lstack/lstack.h>
 116 #include <ccan/lqueue/lqueue.h>
 117
 118 struct aga_graph;
 119 struct aga_node;
 120
 121 /*
 122  * Callbacks
 123  */
 124 typedef const void *(*aga_first_edge_fn)(const struct aga_graph *g,
 125                                          const struct aga_node *n);
 126 typedef const void *(*aga_next_edge_fn)(const struct aga_graph *g,
 127                                         const struct aga_node *n,
 128                                         const void *e);
 129
 130 struct aga_edge_info {
 131         struct aga_node *to;
 132 };
 133 typedef int (*aga_edge_info_fn)(const struct aga_graph *g,
 134                                 const struct aga_node *n,
 135                                 const void *e, struct aga_edge_info *ei);
 136
 137 /*
 138  * Internal data structures
 139  */
 140
 141 struct aga_node {
 142         int sequence;
 143         union {
 144                 struct {
 145                         struct lstack_link parent;
 146                         const void *edge;
 147                 } dfs;
 148                 struct {
 149                         struct lqueue_link next;
 150                         const void *edge;
 151                 } bfs;
 152         } u;
 153 };
 154
 155 struct aga_graph {
 156         int sequence;
 157         int error;
 158
 159         aga_first_edge_fn first_edge;
 160         aga_next_edge_fn next_edge;
 161         aga_edge_info_fn edge_info;
 162 };
 163
 164 /*
 165  * Core functions
 166  */
 167
 168 /**
 169  * aga_init_graph - Initialize a new abstract graph
 170  * @g: graph structure to initialize
 171  * @first_edge: first edge callback
 172  * @next_edge: next edge callback
 173  * @edge_into: edge info callback
 174  *
 175  * Initialize @g to represent an abstract graph defined by the
 176  * supplied edge callbacks
 177  */
 178 void aga_init_graph_(struct aga_graph *g,
 179                      aga_first_edge_fn first_edge,
 180                      aga_next_edge_fn next_edge,
 181                      aga_edge_info_fn edge_info);
 182 #define aga_init_graph(g_, fefn_, nefn_, eifn_)                         \
 183         do {                                                            \
 184                 struct aga_node *n_;                                    \
 185                 struct aga_edge_info *ei_;                              \
 186                 BUILD_ASSERT(check_types_match((fefn_)((g_), n_),       \
 187                                                (nefn_)((g_), n_,        \
 188                                                        (fefn_)((g_), n_))) \
 189                              == 0);                                     \
 190                 BUILD_ASSERT(check_type((eifn_)((g_), n_,               \
 191                                                 (fefn_)((g_), n_), ei_), \
 192                                         int) == 0);                     \
 193                 aga_init_graph_((g_), (aga_first_edge_fn)(fefn_),       \
 194                                 (aga_next_edge_fn)(nefn_),              \
 195                                 (aga_edge_info_fn)(eifn_));             \
 196         } while (0)
 197
 198 /**
 199  * aga_error - Determine error state of a graph
 200  * @g: the graph
 201  *
 202  * Returns 0 if the graph is not in an error state, negative values
 203  * for error states reported by one of the edge callbacks and
 204  * postitive values for errors detected by aga itself.
 205  */
 206 int aga_error(const struct aga_graph *g);
 207
 208 /**
 209  * aga_node_init - Initialize a graph node
 210  * @node: a graph node
 211  *
 212  * Initialize @node as a new graph node.  This must be called before
 213  * @node is passed to any aga function, or returned from an edge_info
 214  * callback (in the ei->to field)
 215  */
 216 static inline void aga_node_init(struct aga_node *node)
 217 {
 218         memset(node, 0, sizeof(*node));
 219 }
 220
 221 /**
 222  * aga_finish - Finish an aga algorithm
 223  * @g: graph
 224  *
 225  * Wraps up the aga algorithm currently running on @g.  This will
 226  * clear any error conditions.  After this is called it is an error to
 227  * call aga functions on @g apart from aga_*_start() and aga_error.
 228  */
 229 void aga_finish(struct aga_graph *g);
 230
 231 const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n);
 232 const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
 233                           const void *e);
 234 int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
 235                   const void *e, struct aga_edge_info *ei);
 236
 237 #define aga_for_each_edge(_e, _g, _n)                                   \
 238         for ((_e) = aga_first_edge((_g), (_n)); (_e);                   \
 239              (_e) = aga_next_edge((_g), (_n), (_e)))
 240
 241 #define aga_for_each_edge_info(_e, _ei, _err, _g, _n)                   \
 242         for ((_e) = aga_first_edge((_g), (_n));                         \
 243              (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \
 244              (_e) = aga_next_edge((_g), (_n), (_e)))                    \
 245                 if ((_ei).to)
 246
 247 /*
 248  * Depth first search
 249  */
 250
 251 /**
 252  * aga_dfs_start - Start a depth-first search
 253  * @g: graph to search
 254  *
 255  * Begins the depth-first search algorithm on @g
 256  */
 257 int aga_dfs_start(struct aga_graph *g);
 258
 259 /**
 260  * aga_dfs_explore - One step of depth-first search
 261  * @g: graph to search
 262  * @n: node to start exploration from
 263  *
 264  * If @n has not yet been explored since aga_dfs_start(), returns @n.
 265  * Otherwise returns the next node after @n in depth-first search
 266  * order.  Marks the returned node as explored.
 267  */
 268 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n);
 269
 270 /**
 271  * aga_dfs - Depth-first search
 272  * @_n: pointer to current node (output)
 273  * @_g: graph to search
 274  * @_start: node to start from
 275  *
 276  * Performs a depth first search.  The block following this macro is
 277  * executed with @_n set first to @_start, then to each node reachable
 278  * from @_start in depth first search order.
 279  *
 280  * aga_dfs_start() must be called before this macro is used.
 281  */
 282 #define aga_dfs(_n, _g, _start)                                 \
 283         for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; )
 284
 285
 286 /*
 287  * Breadth first search
 288  */
 289
 290 /**
 291  * aga_bfs_start - Start a breadth-first search
 292  * @g: graph to search
 293  *
 294  * Begins the breadth-first search algorithm on @g
 295  */
 296 int aga_bfs_start(struct aga_graph *g);
 297
 298 /**
 299  * aga_bfs_explore - One step of breadth-first search
 300  * @g: graph to search
 301  * @n: node to start exploration from
 302  *
 303  * If @n has not yet been explored since aga_bfs_start(), returns @n.
 304  * Otherwise returns the next node after @n in breadth-first search
 305  * order.  Marks the returned node as explored.
 306  */
 307 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
 308
 309 /**
 310  * aga_bfs - Breadth-first search
 311  * @_n: pointer to current node (output)
 312  * @_g: graph to search
 313  * @_start: node to start from
 314  *
 315  * Performs a breadth first search.  The block following this macro is
 316  * executed with @_n set first to @_start, then to each node reachable
 317  * from @_start in depth first search order.
 318  *
 319  * aga_bfs_start() must be called before this macro is used.
 320  */
 321 #define aga_bfs(_n, _g, _start)                                 \
 322         for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
 323
 324 #endif /* CCAN_AGA_H */