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

   1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
   2 #ifndef CCAN_DGRAPH_H
   3 #define CCAN_DGRAPH_H
   4 #include "config.h"
   5 #include <ccan/tlist/tlist.h>
   6 #include <ccan/typesafe_cb/typesafe_cb.h>
   7 #include <stdbool.h>
   8
   9 enum dgraph_dir {
  10         DGRAPH_FROM,
  11         DGRAPH_TO
  12 };
  13
  14 /* strust tlist_dgraph_edge: a list of edges */
  15 TLIST_TYPE(dgraph_edge, struct dgraph_edge);
  16
  17 /**
  18  * struct dgraph_node - a node in a directed graph.
  19  * @edge: edges indexed by enum dgraph_dir.
  20  *
  21  * edge[DGRAPH_FROM] edges have n[DGRAPH_FROM] == this.
  22  * edge[DGRAPH_TO] edges have n[DGRAPH_TO] == this.
  23  */
  24 struct dgraph_node {
  25         struct tlist_dgraph_edge edge[2];
  26 };
  27
  28 /**
  29  * struct dgraph_edge - an edge in a directed graph.
  30  * @list: our nodes's list of edges, indexed by enum dgraph_dir.
  31  * @n: the nodes, indexed by enum dgraph_dir.
  32  */
  33 struct dgraph_edge {
  34         struct list_node list[2];
  35         struct dgraph_node *n[2];
  36 };
  37
  38 void dgraph_init_node(struct dgraph_node *n);
  39 void dgraph_clear_node(struct dgraph_node *n);
  40 void dgraph_add_edge(struct dgraph_node *from, struct dgraph_node *to);
  41 bool dgraph_del_edge(struct dgraph_node *from, struct dgraph_node *to);
  42
  43 #ifdef CCAN_DGRAPH_DEBUG
  44 #define dgraph_debug(n) dgraph_check((n), __func__)
  45 #else
  46 #define dgraph_debug(n) (n)
  47 #endif
  48
  49 /* You can dgraph_clear_node() the node you're on safely. */
  50 #define dgraph_traverse_from(n, fn, arg)                                \
  51         dgraph_traverse(dgraph_debug(n), DGRAPH_FROM,                   \
  52                         typesafe_cb_preargs(bool, void *, (fn), (arg),  \
  53                                             struct dgraph_node *),      \
  54                         (arg))
  55
  56 #define dgraph_traverse_to(n, fn, arg)                                  \
  57         dgraph_traverse(dgraph_debug(n), DGRAPH_TO,                     \
  58                         typesafe_cb_preargs(bool, void *, (fn), (arg),  \
  59                                             struct dgraph_node *),      \
  60                         (arg))
  61
  62 void dgraph_traverse(const struct dgraph_node *n,
  63                      enum dgraph_dir dir,
  64                      bool (*fn)(struct dgraph_node *from, void *data),
  65                      const void *data);
  66
  67 #define dgraph_for_each_edge(n, i, dir)         \
  68         tlist_for_each(&dgraph_debug(n)->edge[dir], i, list[dir])
  69
  70 #define dgraph_for_each_edge_safe(n, i, next, dir)              \
  71         tlist_for_each_safe(&dgraph_debug(n)->edge[dir], i, next, list[dir])
  72
  73 /**
  74  * dgraph_check - check a graph for consistency
  75  * @n: the dgraph_node to check.
  76  * @abortstr: the string to print on aborting, or NULL.
  77  *
  78  * Returns @n if the list is consistent, NULL if not (it can never
  79  * return NULL if @abortstr is set).
  80  *
  81  * See also: tlist_check()
  82  */
  83 struct dgraph_node *dgraph_check(const struct dgraph_node *n,
  84                                  const char *abortstr);
  85 #endif /* CCAN_DGRAPH_H */