1/* Graph representation.
2   Copyright (C) 2007-2015 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
25struct 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
35struct 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
47struct 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
54struct graph *new_graph (int);
55void dump_graph (FILE *, struct graph *);
56struct graph_edge *add_edge (struct graph *, int, int);
57void identify_vertices (struct graph *, int, int);
58int graphds_dfs (struct graph *, int *, int,
59		 vec<int> *, bool, bitmap);
60int graphds_scc (struct graph *, bitmap);
61void graphds_domtree (struct graph *, int, int *, int *, int *);
62typedef void (*graphds_edge_callback) (struct graph *, struct graph_edge *);
63void for_each_edge (struct graph *, graphds_edge_callback);
64void free_graph (struct graph *g);
65
66#endif /* GCC_GRAPHDS_H */
67