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 /* You can dgraph_clear_node() the node you're on safely. */
  44 #define dgraph_traverse_from(n, fn, arg)                                \
  45         dgraph_traverse((n), DGRAPH_FROM,                               \
  46                         typesafe_cb_preargs(bool, void *, (fn), (arg),  \
  47                                             struct dgraph_node *),      \
  48                         (arg))
  49
  50 #define dgraph_traverse_to(n, fn, arg)                                  \
  51         dgraph_traverse((n), DGRAPH_TO,                                 \
  52                         typesafe_cb_preargs(bool, void *, (fn), (arg),  \
  53                                             struct dgraph_node *),      \
  54                         (arg))
  55
  56 void dgraph_traverse(struct dgraph_node *n,
  57                      enum dgraph_dir dir,
  58                      bool (*fn)(struct dgraph_node *from, void *data),
  59                      const void *data);
  60
  61 #define dgraph_for_each_edge(n, i, dir)         \
  62         tlist_for_each(&(n)->edge[dir], i, list[dir])
  63
  64 #define dgraph_for_each_edge_safe(n, i, next, dir)              \
  65         tlist_for_each_safe(&(n)->edge[dir], i, next, list[dir])
  66
  67 #endif /* CCAN_DGRAPH_H */