|
0
|
1 /* Graph representation.
|
|
145
|
2 Copyright (C) 2007-2020 Free Software Foundation, Inc.
|
|
0
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify it under
|
|
|
7 the terms of the GNU General Public License as published by the Free
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
9 version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
111
|
20 #ifndef GCC_GRAPHDS_H
|
|
|
21 #define GCC_GRAPHDS_H
|
|
|
22
|
|
0
|
23 /* Structure representing edge of a graph. */
|
|
|
24
|
|
|
25 struct graph_edge
|
|
|
26 {
|
|
|
27 int src, dest; /* Source and destination. */
|
|
|
28 struct graph_edge *pred_next, *succ_next;
|
|
|
29 /* Next edge in predecessor and successor lists. */
|
|
|
30 void *data; /* Data attached to the edge. */
|
|
|
31 };
|
|
|
32
|
|
|
33 /* Structure representing vertex of a graph. */
|
|
|
34
|
|
|
35 struct vertex
|
|
|
36 {
|
|
|
37 struct graph_edge *pred, *succ;
|
|
|
38 /* Lists of predecessors and successors. */
|
|
|
39 int component; /* Number of dfs restarts before reaching the
|
|
|
40 vertex. */
|
|
|
41 int post; /* Postorder number. */
|
|
|
42 void *data; /* Data attached to the vertex. */
|
|
|
43 };
|
|
|
44
|
|
|
45 /* Structure representing a graph. */
|
|
|
46
|
|
|
47 struct graph
|
|
|
48 {
|
|
111
|
49 int n_vertices; /* Number of vertices. */
|
|
|
50 struct vertex *vertices; /* The vertices. */
|
|
|
51 struct obstack ob; /* Obstack for vertex and edge allocation. */
|
|
0
|
52 };
|
|
|
53
|
|
|
54 struct graph *new_graph (int);
|
|
|
55 void dump_graph (FILE *, struct graph *);
|
|
|
56 struct graph_edge *add_edge (struct graph *, int, int);
|
|
|
57 void identify_vertices (struct graph *, int, int);
|
|
111
|
58 typedef bool (*skip_edge_callback) (struct graph_edge *);
|
|
0
|
59 int graphds_dfs (struct graph *, int *, int,
|
|
111
|
60 vec<int> *, bool, bitmap, skip_edge_callback = NULL);
|
|
|
61 int graphds_scc (struct graph *, bitmap, skip_edge_callback = NULL);
|
|
0
|
62 void graphds_domtree (struct graph *, int, int *, int *, int *);
|
|
111
|
63 typedef void (*graphds_edge_callback) (struct graph *,
|
|
|
64 struct graph_edge *, void *);
|
|
|
65 void for_each_edge (struct graph *, graphds_edge_callback, void *);
|
|
0
|
66 void free_graph (struct graph *g);
|
|
111
|
67
|
|
|
68 #endif /* GCC_GRAPHDS_H */
|
