projects / thirdparty / gcc.git / blame
| Commit | Line | Data |
|---|---|---|
| 66f97d31 ZD |
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 | |
| 9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
| 66f97d31 ZD |
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 | |
| 9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
| 19 | <http://www.gnu.org/licenses/>. */ | |
| 66f97d31 ZD |
20 | |
| 21 | /* Structure representing edge of a graph. */ | |
| 22 | ||
| ae50c0cb | 23 | struct graph_edge |
| 66f97d31 ZD |
24 | { |
| 25 | int src, dest; /* Source and destination. */ | |
| ae50c0cb | 26 | struct graph_edge *pred_next, *succ_next; |
| 66f97d31 ZD |
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 | { | |
| ae50c0cb | 35 | struct graph_edge *pred, *succ; |
| 66f97d31 ZD |
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. */ | |
| 50 | }; | |
| 51 | ||
| 52 | struct graph *new_graph (int); | |
| 53 | void dump_graph (FILE *, struct graph *); | |
| ae50c0cb | 54 | struct graph_edge *add_edge (struct graph *, int, int); |
| 66f97d31 ZD |
55 | void identify_vertices (struct graph *, int, int); |
| 56 | int graphds_dfs (struct graph *, int *, int, | |
| 57 | VEC (int, heap) **, bool, bitmap); | |
| 58 | int graphds_scc (struct graph *, bitmap); | |
| 59 | void graphds_domtree (struct graph *, int, int *, int *, int *); | |
| ae50c0cb | 60 | typedef void (*graphds_edge_callback) (struct graph *, struct graph_edge *); |
| 66f97d31 ZD |
61 | void for_each_edge (struct graph *, graphds_edge_callback); |
| 62 | void free_graph (struct graph *g); |