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