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