/* 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.
#include "obstack.h"
#include "bitmap.h"
#include "vec.h"
-#include "vecprim.h"
#include "graphds.h"
/* Dumps graph G into F. */
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;
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;
}
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;
/* 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)