/* Graph representation and manipulation functions.
- Copyright (C) 2007
- Free Software Foundation, Inc.
+ Copyright (C) 2007-2013 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "obstack.h"
#include "bitmap.h"
#include "vec.h"
-#include "vecprim.h"
#include "graphds.h"
/* Dumps graph G into F. */
dump_graph (FILE *f, struct graph *g)
{
int i;
- struct edge *e;
+ struct graph_edge *e;
for (i = 0; i < g->n_vertices; i++)
{
/* Adds an edge from F to T to graph G. The new edge is returned. */
-struct edge *
+struct graph_edge *
add_edge (struct graph *g, int f, int t)
{
- struct edge *e = XNEW (struct edge);
+ struct graph_edge *e = XNEW (struct graph_edge);
struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
{
struct vertex *vv = &g->vertices[v];
struct vertex *uu = &g->vertices[u];
- struct edge *e, *next;
+ struct graph_edge *e, *next;
for (e = uu->succ; e; e = next)
{
direction given by FORWARD. */
static inline int
-dfs_edge_src (struct edge *e, bool forward)
+dfs_edge_src (struct graph_edge *e, bool forward)
{
return forward ? e->src : e->dest;
}
the direction given by FORWARD. */
static inline int
-dfs_edge_dest (struct edge *e, bool forward)
+dfs_edge_dest (struct graph_edge *e, bool forward)
{
return forward ? e->dest : e->src;
}
/* Helper function for graphds_dfs. Returns the first edge after E (including
E), in the graph direction given by FORWARD, that belongs to SUBGRAPH. */
-static inline struct edge *
-foll_in_subgraph (struct edge *e, bool forward, bitmap subgraph)
+static inline struct graph_edge *
+foll_in_subgraph (struct graph_edge *e, bool forward, bitmap subgraph)
{
int d;
/* Helper function for graphds_dfs. Select the first edge from V in G, in the
direction given by FORWARD, that belongs to SUBGRAPH. */
-static inline struct edge *
+static inline struct graph_edge *
dfs_fst_edge (struct graph *g, int v, bool forward, bitmap subgraph)
{
- struct edge *e;
+ struct graph_edge *e;
e = (forward ? g->vertices[v].succ : g->vertices[v].pred);
return foll_in_subgraph (e, forward, subgraph);
/* Helper function for graphds_dfs. Returns the next edge after E, in the
graph direction given by FORWARD, that belongs to SUBGRAPH. */
-static inline struct edge *
-dfs_next_edge (struct edge *e, bool forward, bitmap subgraph)
+static inline struct graph_edge *
+dfs_next_edge (struct graph_edge *e, bool forward, bitmap subgraph)
{
return foll_in_subgraph (forward ? e->succ_next : e->pred_next,
forward, subgraph);
of the graph (number of the restarts of DFS). */
int
-graphds_dfs (struct graph *g, int *qs, int nq, VEC (int, heap) **qt,
+graphds_dfs (struct graph *g, int *qs, int nq, vec<int> *qt,
bool forward, bitmap subgraph)
{
int i, tick = 0, v, comp = 0, top;
- struct edge *e;
- struct edge **stack = XNEWVEC (struct edge *, g->n_vertices);
+ struct graph_edge *e;
+ struct graph_edge **stack = XNEWVEC (struct graph_edge *, g->n_vertices);
bitmap_iterator bi;
unsigned av;
if (!e)
{
if (qt)
- VEC_safe_push (int, heap, *qt, v);
+ qt->safe_push (v);
g->vertices[v].post = tick++;
if (!top)
numbers assigned by the previous pass. If SUBGRAPH is not NULL, it
specifies the subgraph of G whose strongly connected components we want
to determine.
-
+
After running this function, v->component is the number of the strongly
connected component for each vertex of G. Returns the number of the
sccs of G. */
graphds_scc (struct graph *g, bitmap subgraph)
{
int *queue = XNEWVEC (int, g->n_vertices);
- VEC (int, heap) *postorder = NULL;
+ vec<int> postorder = vNULL;
int nq, i, comp;
unsigned v;
bitmap_iterator bi;
}
graphds_dfs (g, queue, nq, &postorder, false, subgraph);
- gcc_assert (VEC_length (int, postorder) == (unsigned) nq);
+ gcc_assert (postorder.length () == (unsigned) nq);
for (i = 0; i < nq; i++)
- queue[i] = VEC_index (int, postorder, nq - i - 1);
+ queue[i] = postorder[nq - i - 1];
comp = graphds_dfs (g, queue, nq, NULL, true, subgraph);
free (queue);
- VEC_free (int, heap, postorder);
+ postorder.release ();
return comp;
}
void
for_each_edge (struct graph *g, graphds_edge_callback callback)
{
- struct edge *e;
+ struct graph_edge *e;
int i;
for (i = 0; i < g->n_vertices; i++)
void
free_graph (struct graph *g)
{
- struct edge *e, *n;
+ struct graph_edge *e, *n;
struct vertex *v;
int i;
graphds_domtree (struct graph *g, int entry,
int *parent, int *son, int *brother)
{
- VEC (int, heap) *postorder = NULL;
+ vec<int> postorder = vNULL;
int *marks = XCNEWVEC (int, g->n_vertices);
int mark = 1, i, v, idom;
bool changed = true;
- struct edge *e;
+ struct graph_edge *e;
/* We use a slight modification of the standard iterative algorithm, as
described in
-
+
K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
Algorithm
brother[i] = -1;
}
graphds_dfs (g, &entry, 1, &postorder, true, NULL);
- gcc_assert (VEC_length (int, postorder) == (unsigned) g->n_vertices);
- gcc_assert (VEC_index (int, postorder, g->n_vertices - 1) == entry);
+ gcc_assert (postorder.length () == (unsigned) g->n_vertices);
+ gcc_assert (postorder[g->n_vertices - 1] == entry);
while (changed)
{
for (i = g->n_vertices - 2; i >= 0; i--)
{
- v = VEC_index (int, postorder, i);
+ v = postorder[i];
idom = -1;
for (e = g->vertices[v].pred; e; e = e->pred_next)
{
}
free (marks);
- VEC_free (int, heap, postorder);
+ postorder.release ();
for (i = 0; i < g->n_vertices; i++)
if (parent[i] != -1)
projects / gcc.git / blobdiff