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  * - The ei->icost field MAY be set by the edge_info callback to
  76  *   indicate the edge's cost / length represented as an integer (of
  77  *   type aga_icost_t),  Otherwise the cost defaults to 1.
  78  *
  79  * Concurrency
  80  * ===========
  81  *
  82  * - Because the algorithms implemented here keep state in the
  83  *   aga_node structures, only one algorithm can run at a time.
  84  *   Global state for algorithms is stored in the aga_graph structure.
  85  *
  86  * - When you start an algorithm (aga_*_start()) the graph is marked
  87  *   as in-use.
  88  *
  89  * - Subsequent attempts to start an algorithm will fail;
  90  *   aga_*_start() will return -1.
  91  *
  92  * - To release the graph for another algorithm, use aga_finish().
  93  *
  94  * - Calling functions associated with one algorithm while another is
  95  *   running has undefined results.
  96  *
  97  * Errors
  98  * ======
  99  *
 100  * - Errors may be reported by the edge_info callback, or may be
 101  *   detected internally by algorithms.
 102  *
 103  * - Algorithms will generally stop running when they encounter an
 104  *   error; the call which detects the error and subsequent calls will
 105  *   return a "safe", but otherwise meaningless value.
 106  *
 107  * - After an error is encountered aga_error() will return a non-zero
 108  *   value.  Negative values are reserved for errors reported by the
 109  *   user supplied edge callback.  Positive values are reserved for
 110  *   errors detected interally by aga.
 111  *
 112  * - Errors are cleared on aga_finish().
 113  */
 114 #include "config.h"
 115 #include <string.h>
 116
 117 #include <ccan/build_assert/build_assert.h>
 118 #include <ccan/check_type/check_type.h>
 119 #include <ccan/lstack/lstack.h>
 120 #include <ccan/lqueue/lqueue.h>
 121
 122 struct aga_graph;
 123 struct aga_node;
 124
 125 /*
 126  * Callbacks
 127  */
 128 typedef const void *(*aga_first_edge_fn)(const struct aga_graph *g,
 129                                          const struct aga_node *n);
 130 typedef const void *(*aga_next_edge_fn)(const struct aga_graph *g,
 131                                         const struct aga_node *n,
 132                                         const void *e);
 133
 134 typedef long aga_icost_t;
 135
 136 struct aga_edge_info {
 137         struct aga_node *to;
 138         aga_icost_t icost; /* integer edge cost */
 139 };
 140
 141 typedef int (*aga_edge_info_fn)(const struct aga_graph *g,
 142                                 const struct aga_node *n,
 143                                 const void *e, struct aga_edge_info *ei);
 144
 145 /*
 146  * Internal data structures
 147  */
 148
 149 struct aga_node {
 150         int sequence;
 151         union {
 152                 struct {
 153                         struct lstack_link parent;
 154                         const void *edge;
 155                 } dfs;
 156                 struct {
 157                         struct lqueue_link next;
 158                         const void *edge;
 159                 } bfs;
 160         } u;
 161 };
 162
 163 struct aga_graph {
 164         int sequence;
 165         int error;
 166
 167         aga_first_edge_fn first_edge;
 168         aga_next_edge_fn next_edge;
 169         aga_edge_info_fn edge_info;
 170 };
 171
 172 /*
 173  * Core functions
 174  */
 175
 176 /**
 177  * aga_init_graph - Initialize a new abstract graph
 178  * @g: graph structure to initialize
 179  * @first_edge: first edge callback
 180  * @next_edge: next edge callback
 181  * @edge_into: edge info callback
 182  *
 183  * Initialize @g to represent an abstract graph defined by the
 184  * supplied edge callbacks
 185  */
 186 void aga_init_graph_(struct aga_graph *g,
 187                      aga_first_edge_fn first_edge,
 188                      aga_next_edge_fn next_edge,
 189                      aga_edge_info_fn edge_info);
 190 #define aga_init_graph(g_, fefn_, nefn_, eifn_)                         \
 191         do {                                                            \
 192                 struct aga_node *n_;                                    \
 193                 struct aga_edge_info *ei_;                              \
 194                 BUILD_ASSERT(check_types_match((fefn_)((g_), n_),       \
 195                                                (nefn_)((g_), n_,        \
 196                                                        (fefn_)((g_), n_))) \
 197                              == 0);                                     \
 198                 BUILD_ASSERT(check_type((eifn_)((g_), n_,               \
 199                                                 (fefn_)((g_), n_), ei_), \
 200                                         int) == 0);                     \
 201                 aga_init_graph_((g_), (aga_first_edge_fn)(fefn_),       \
 202                                 (aga_next_edge_fn)(nefn_),              \
 203                                 (aga_edge_info_fn)(eifn_));             \
 204         } while (0)
 205
 206 /**
 207  * enum aga_error - Error codes for aga routines
 208  *
 209  * These error codes are returned by aga_error() for errors detected
 210  * within aga itself (rather than errors reported by supplied
 211  * callbacks, which should be negative
 212  */
 213 enum aga_error {
 214         /* No error */
 215         AGA_ERR_NONE = 0,
 216 };
 217
 218 /**
 219  * aga_error - Determine error state of a graph
 220  * @g: the graph
 221  *
 222  * Returns 0 if the graph is not in an error state, negative values
 223  * for error states reported by one of the edge callbacks and
 224  * postitive values for errors detected by aga itself.
 225  */
 226 int aga_error(const struct aga_graph *g);
 227
 228 /**
 229  * aga_node_init - Initialize a graph node
 230  * @node: a graph node
 231  *
 232  * Initialize @node as a new graph node.  This must be called before
 233  * @node is passed to any aga function, or returned from an edge_info
 234  * callback (in the ei->to field)
 235  */
 236 static inline void aga_node_init(struct aga_node *node)
 237 {
 238         memset(node, 0, sizeof(*node));
 239 }
 240
 241 /**
 242  * aga_finish - Finish an aga algorithm
 243  * @g: graph
 244  *
 245  * Wraps up the aga algorithm currently running on @g.  This will
 246  * clear any error conditions.  After this is called it is an error to
 247  * call aga functions on @g apart from aga_*_start() and aga_error.
 248  */
 249 void aga_finish(struct aga_graph *g);
 250
 251 const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n);
 252 const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
 253                           const void *e);
 254 int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
 255                   const void *e, struct aga_edge_info *ei);
 256
 257 #define aga_for_each_edge(_e, _g, _n)                                   \
 258         for ((_e) = aga_first_edge((_g), (_n)); (_e);                   \
 259              (_e) = aga_next_edge((_g), (_n), (_e)))
 260
 261 #define aga_for_each_edge_info(_e, _ei, _err, _g, _n)                   \
 262         for ((_err) = 0, (_e) = aga_first_edge((_g), (_n));             \
 263              (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \
 264              (_e) = aga_next_edge((_g), (_n), (_e)))                    \
 265                 if ((_ei).to)
 266
 267 /*
 268  * Depth first search
 269  */
 270
 271 /**
 272  * aga_dfs_start - Start a depth-first search
 273  * @g: graph to search
 274  *
 275  * Begins the depth-first search algorithm on @g
 276  */
 277 int aga_dfs_start(struct aga_graph *g);
 278
 279 /**
 280  * aga_dfs_explore - One step of depth-first search
 281  * @g: graph to search
 282  * @n: node to start exploration from
 283  *
 284  * If @n has not yet been explored since aga_dfs_start(), returns @n.
 285  * Otherwise returns the next node after @n in depth-first search
 286  * order.  Marks the returned node as explored.
 287  */
 288 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n);
 289
 290 /**
 291  * aga_dfs - Depth-first search
 292  * @_n: pointer to current node (output)
 293  * @_g: graph to search
 294  * @_start: node to start from
 295  *
 296  * Performs a depth first search.  The block following this macro is
 297  * executed with @_n set first to @_start, then to each node reachable
 298  * from @_start in depth first search order.
 299  *
 300  * aga_dfs_start() must be called before this macro is used.
 301  */
 302 #define aga_dfs(_n, _g, _start)                                 \
 303         for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; )
 304
 305
 306 /*
 307  * Breadth first search
 308  */
 309
 310 /**
 311  * aga_bfs_start - Start a breadth-first search
 312  * @g: graph to search
 313  *
 314  * Begins the breadth-first search algorithm on @g
 315  */
 316 int aga_bfs_start(struct aga_graph *g);
 317
 318 /**
 319  * aga_bfs_explore - One step of breadth-first search
 320  * @g: graph to search
 321  * @n: node to start exploration from
 322  *
 323  * If @n has not yet been explored since aga_bfs_start(), returns @n.
 324  * Otherwise returns the next node after @n in breadth-first search
 325  * order.  Marks the returned node as explored.
 326  */
 327 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
 328
 329 /**
 330  * aga_bfs - Breadth-first search
 331  * @_n: pointer to current node (output)
 332  * @_g: graph to search
 333  * @_start: node to start from
 334  *
 335  * Performs a breadth first search.  The block following this macro is
 336  * executed with @_n set first to @_start, then to each node reachable
 337  * from @_start in depth first search order.
 338  *
 339  * aga_bfs_start() must be called before this macro is used.
 340  */
 341 #define aga_bfs(_n, _g, _start)                                 \
 342         for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
 343
 344 #endif /* CCAN_AGA_H */