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 void aga_init_graph_(struct aga_graph *g,
 169                      aga_first_edge_fn first_edge,
 170                      aga_next_edge_fn next_edge,
 171                      aga_edge_info_fn edge_info);
 172 #define aga_init_graph(g_, fefn_, nefn_, eifn_)                         \
 173         do {                                                            \
 174                 struct aga_node *n_;                                    \
 175                 struct aga_edge_info *ei_;                              \
 176                 BUILD_ASSERT(check_types_match((fefn_)((g_), n_),       \
 177                                                (nefn_)((g_), n_,        \
 178                                                        (fefn_)((g_), n_))) \
 179                              == 0);                                     \
 180                 BUILD_ASSERT(check_type((eifn_)((g_), n_,               \
 181                                                 (fefn_)((g_), n_), ei_), \
 182                                         int) == 0);                     \
 183                 aga_init_graph_((g_), (aga_first_edge_fn)(fefn_),       \
 184                                 (aga_next_edge_fn)(nefn_),              \
 185                                 (aga_edge_info_fn)(eifn_));             \
 186         } while (0)
 187
 188 int aga_error(const struct aga_graph *g);
 189
 190 static inline void aga_node_init(struct aga_node *node)
 191 {
 192         memset(node, 0, sizeof(*node));
 193 }
 194
 195 void aga_finish(struct aga_graph *g);
 196
 197 const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n);
 198 const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
 199                           const void *e);
 200 int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
 201                   const void *e, struct aga_edge_info *ei);
 202
 203 #define aga_for_each_edge(_e, _g, _n)                                   \
 204         for ((_e) = aga_first_edge((_g), (_n)); (_e);                   \
 205              (_e) = aga_next_edge((_g), (_n), (_e)))
 206
 207 #define aga_for_each_edge_info(_e, _ei, _err, _g, _n)                   \
 208         for ((_e) = aga_first_edge((_g), (_n));                         \
 209              (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \
 210              (_e) = aga_next_edge((_g), (_n), (_e)))                    \
 211                 if ((_ei).to)
 212
 213 /*
 214  * Depth first search
 215  */
 216
 217 int aga_dfs_start(struct aga_graph *g);
 218 struct aga_node *aga_dfs_explore(struct aga_graph *g, struct aga_node *n);
 219
 220 #define aga_dfs(_n, _g, _start)                                 \
 221         for ((_n) = (_start); ((_n) = aga_dfs_explore((_g), (_n))) != NULL; )
 222
 223
 224 /*
 225  * Breadth first search
 226  */
 227
 228 int aga_bfs_start(struct aga_graph *g);
 229 struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
 230
 231 #define aga_bfs(_n, _g, _start)                                 \
 232         for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
 233
 234 #endif /* CCAN_AGA_H */