1 /* Graph representation.
2    Copyright (C) 2007-2018 Free Software Foundation, Inc.
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 
20 #ifndef GCC_GRAPHDS_H
21 #define GCC_GRAPHDS_H
22 
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 {
49   int n_vertices;	   /* Number of vertices.  */
50   struct vertex *vertices; /* The vertices.  */
51   struct obstack ob;	   /* Obstack for vertex and edge allocation.  */
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);
58 typedef bool (*skip_edge_callback) (struct graph_edge *);
59 int graphds_dfs (struct graph *, int *, int,
60 		 vec<int> *, bool, bitmap, skip_edge_callback = NULL);
61 int graphds_scc (struct graph *, bitmap, skip_edge_callback = NULL);
62 void graphds_domtree (struct graph *, int, int *, int *, int *);
63 typedef void (*graphds_edge_callback) (struct graph *,
64 				       struct graph_edge *, void *);
65 void for_each_edge (struct graph *, graphds_edge_callback, void *);
66 void free_graph (struct graph *g);
67 
68 #endif /* GCC_GRAPHDS_H */
69