LLVM  6.0.0svn
Classes | Public Member Functions | Static Public Member Functions | List of all members
llvm::scc_iterator< GraphT, GT > Class Template Reference

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG. More...

#include "llvm/ADT/SCCIterator.h"

Inheritance diagram for llvm::scc_iterator< GraphT, GT >:
Inheritance graph
[legend]
Collaboration diagram for llvm::scc_iterator< GraphT, GT >:
Collaboration graph
[legend]

Public Member Functions

bool isAtEnd () const
 Direct loop termination test which is more efficient than comparison with end(). More...
 
bool operator== (const scc_iterator &x) const
 
scc_iteratoroperator++ ()
 
reference operator* () const
 
bool hasLoop () const
 Test if the current SCC has a loop. More...
 
void ReplaceNode (NodeRef Old, NodeRef New)
 This informs the scc_iterator that the specified Old node has been deleted, and New is to be used in its place. More...
 
- Public Member Functions inherited from llvm::iterator_facade_base< scc_iterator< GraphT, GT >, std::forward_iterator_tag, const std::vector< GT::NodeRef >, ptrdiff_t >
scc_iterator< GraphT, GT > operator+ (ptrdiff_t n) const
 
scc_iterator< GraphT, GT > operator- (ptrdiff_t n) const
 
scc_iterator< GraphT, GT > & operator++ ()
 
scc_iterator< GraphT, GT > operator++ (int)
 
scc_iterator< GraphT, GT > & operator-- ()
 
scc_iterator< GraphT, GT > operator-- (int)
 
bool operator!= (const scc_iterator< GraphT, GT > &RHS) const
 
bool operator> (const scc_iterator< GraphT, GT > &RHS) const
 
bool operator<= (const scc_iterator< GraphT, GT > &RHS) const
 
bool operator>= (const scc_iterator< GraphT, GT > &RHS) const
 
const std::vector< GT::NodeRef > * operator-> ()
 
const std::vector< GT::NodeRef > * operator-> () const
 
ReferenceProxy operator[] (ptrdiff_t n)
 
ReferenceProxy operator[] (ptrdiff_t n) const
 

Static Public Member Functions

static scc_iterator begin (const GraphT &G)
 
static scc_iterator end (const GraphT &)
 

Additional Inherited Members

- Protected Types inherited from llvm::iterator_facade_base< scc_iterator< GraphT, GT >, std::forward_iterator_tag, const std::vector< GT::NodeRef >, ptrdiff_t >
enum  
 

Detailed Description

template<class GraphT, class GT = GraphTraits<GraphT>>
class llvm::scc_iterator< GraphT, GT >

Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.

This is implemented using Tarjan's DFS algorithm using an internal stack to build up a vector of nodes in a particular SCC. Note that it is a forward iterator and thus you cannot backtrack or re-visit nodes.

Definition at line 43 of file SCCIterator.h.

Member Function Documentation

◆ begin()

template<class GraphT, class GT = GraphTraits<GraphT>>
static scc_iterator llvm::scc_iterator< GraphT, GT >::begin ( const GraphT &  G)
inlinestatic

Definition at line 102 of file SCCIterator.h.

Referenced by llvm::scc_begin().

◆ end()

template<class GraphT, class GT = GraphTraits<GraphT>>
static scc_iterator llvm::scc_iterator< GraphT, GT >::end ( const GraphT &  )
inlinestatic

Definition at line 105 of file SCCIterator.h.

Referenced by llvm::scc_end().

◆ hasLoop()

template<class GraphT , class GT >
bool llvm::scc_iterator< GraphT, GT >::hasLoop ( ) const

Test if the current SCC has a loop.

If the SCC has more than one node, this is trivially true. If not, it may still contain a loop if the node has an edge back to itself.

Definition at line 213 of file SCCIterator.h.

References assert().

Referenced by llvm::scc_iterator< GraphT, GT >::operator*().

◆ isAtEnd()

template<class GraphT, class GT = GraphTraits<GraphT>>
bool llvm::scc_iterator< GraphT, GT >::isAtEnd ( ) const
inline

Direct loop termination test which is more efficient than comparison with end().

Definition at line 109 of file SCCIterator.h.

References assert().

◆ operator*()

template<class GraphT, class GT = GraphTraits<GraphT>>
reference llvm::scc_iterator< GraphT, GT >::operator* ( ) const
inline

Definition at line 123 of file SCCIterator.h.

References assert(), and llvm::scc_iterator< GraphT, GT >::hasLoop().

◆ operator++()

template<class GraphT, class GT = GraphTraits<GraphT>>
scc_iterator& llvm::scc_iterator< GraphT, GT >::operator++ ( )
inline

Definition at line 118 of file SCCIterator.h.

◆ operator==()

template<class GraphT, class GT = GraphTraits<GraphT>>
bool llvm::scc_iterator< GraphT, GT >::operator== ( const scc_iterator< GraphT, GT > &  x) const
inline

Definition at line 114 of file SCCIterator.h.

◆ ReplaceNode()

template<class GraphT, class GT = GraphTraits<GraphT>>
void llvm::scc_iterator< GraphT, GT >::ReplaceNode ( NodeRef  Old,
NodeRef  New 
)
inline

The documentation for this class was generated from the following file: