LLVM  14.0.0git
Public Types | Public Member Functions | Protected Types | Protected Attributes | List of all members
llvm::DirectedGraph< NodeType, EdgeType > Class Template Reference

Directed graph. More...

#include "llvm/ADT/DirectedGraph.h"

Inheritance diagram for llvm::DirectedGraph< NodeType, EdgeType >:
Inheritance graph
[legend]
Collaboration diagram for llvm::DirectedGraph< NodeType, EdgeType >:
Collaboration graph
[legend]

Public Types

using iterator = typename NodeListTy::iterator
 
using const_iterator = typename NodeListTy::const_iterator
 
using DGraphType = DirectedGraph< NodeType, EdgeType >
 

Public Member Functions

 DirectedGraph ()=default
 
 DirectedGraph (NodeType &N)
 
 DirectedGraph (const DGraphType &G)
 
 DirectedGraph (DGraphType &&RHS)
 
DGraphTypeoperator= (const DGraphType &G)
 
DGraphTypeoperator= (const DGraphType &&G)
 
const_iterator begin () const
 
const_iterator end () const
 
iterator begin ()
 
iterator end ()
 
const NodeType & front () const
 
NodeType & front ()
 
const NodeType & back () const
 
NodeType & back ()
 
size_t size () const
 
const_iterator findNode (const NodeType &N) const
 Find the given node N in the table. More...
 
iterator findNode (const NodeType &N)
 
bool addNode (NodeType &N)
 Add the given node N to the graph if it is not already present. More...
 
bool findIncomingEdgesToNode (const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const
 Collect in EL all edges that are coming into node N. More...
 
bool removeNode (NodeType &N)
 Remove the given node N from the graph. More...
 
bool connect (NodeType &Src, NodeType &Dst, EdgeType &E)
 Assuming nodes Src and Dst are already in the graph, connect node Src to node Dst using the provided edge E. More...
 

Protected Types

using NodeListTy = SmallVector< NodeType *, 10 >
 
using EdgeListTy = SmallVector< EdgeType *, 10 >
 

Protected Attributes

NodeListTy Nodes
 

Detailed Description

template<class NodeType, class EdgeType>
class llvm::DirectedGraph< NodeType, EdgeType >

Directed graph.

The graph is represented by a table of nodes. Each node contains a (possibly empty) list of outgoing edges. Each edge contains the target node it connects to.

Definition at line 172 of file DirectedGraph.h.

Member Typedef Documentation

◆ const_iterator

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::const_iterator = typename NodeListTy::const_iterator

Definition at line 178 of file DirectedGraph.h.

◆ DGraphType

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::DGraphType = DirectedGraph<NodeType, EdgeType>

Definition at line 179 of file DirectedGraph.h.

◆ EdgeListTy

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::EdgeListTy = SmallVector<EdgeType *, 10>
protected

Definition at line 175 of file DirectedGraph.h.

◆ iterator

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::iterator = typename NodeListTy::iterator

Definition at line 177 of file DirectedGraph.h.

◆ NodeListTy

template<class NodeType , class EdgeType >
using llvm::DirectedGraph< NodeType, EdgeType >::NodeListTy = SmallVector<NodeType *, 10>
protected

Definition at line 174 of file DirectedGraph.h.

Constructor & Destructor Documentation

◆ DirectedGraph() [1/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( )
default

◆ DirectedGraph() [2/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( NodeType &  N)
inlineexplicit

Definition at line 182 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::addNode(), and N.

◆ DirectedGraph() [3/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( const DGraphType G)
inline

Definition at line 183 of file DirectedGraph.h.

◆ DirectedGraph() [4/4]

template<class NodeType , class EdgeType >
llvm::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( DGraphType &&  RHS)
inline

Definition at line 184 of file DirectedGraph.h.

Member Function Documentation

◆ addNode()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::addNode ( NodeType &  N)
inline

◆ back() [1/2]

template<class NodeType , class EdgeType >
NodeType& llvm::DirectedGraph< NodeType, EdgeType >::back ( )
inline

Definition at line 201 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ back() [2/2]

template<class NodeType , class EdgeType >
const NodeType& llvm::DirectedGraph< NodeType, EdgeType >::back ( ) const
inline

Definition at line 200 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ begin() [1/2]

template<class NodeType , class EdgeType >
iterator llvm::DirectedGraph< NodeType, EdgeType >::begin ( )
inline

Definition at line 196 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ begin() [2/2]

template<class NodeType , class EdgeType >
const_iterator llvm::DirectedGraph< NodeType, EdgeType >::begin ( ) const
inline

◆ connect()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::connect ( NodeType &  Src,
NodeType &  Dst,
EdgeType &  E 
)
inline

Assuming nodes Src and Dst are already in the graph, connect node Src to node Dst using the provided edge E.

Return true if Src is not already connected to Dst via E, and false otherwise.

Definition at line 264 of file DirectedGraph.h.

References assert(), E, llvm::DirectedGraph< NodeType, EdgeType >::findNode(), and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

Referenced by llvm::DDGBuilder::createDefUseEdge(), llvm::DDGBuilder::createMemoryEdge(), llvm::DDGBuilder::createRootedEdge(), and llvm::DDGBuilder::mergeNodes().

◆ end() [1/2]

template<class NodeType , class EdgeType >
iterator llvm::DirectedGraph< NodeType, EdgeType >::end ( )
inline

Definition at line 197 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ end() [2/2]

template<class NodeType , class EdgeType >
const_iterator llvm::DirectedGraph< NodeType, EdgeType >::end ( ) const
inline

◆ findIncomingEdgesToNode()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::findIncomingEdgesToNode ( const NodeType &  N,
SmallVectorImpl< EdgeType * > &  EL 
) const
inline

Collect in EL all edges that are coming into node N.

Return true if at least one edge was found, and false otherwise.

Definition at line 225 of file DirectedGraph.h.

References llvm::append_range(), assert(), llvm::SmallVectorImpl< T >::clear(), N, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ findNode() [1/2]

template<class NodeType , class EdgeType >
iterator llvm::DirectedGraph< NodeType, EdgeType >::findNode ( const NodeType &  N)
inline

Definition at line 210 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::findNode(), and N.

◆ findNode() [2/2]

template<class NodeType , class EdgeType >
const_iterator llvm::DirectedGraph< NodeType, EdgeType >::findNode ( const NodeType &  N) const
inline

◆ front() [1/2]

template<class NodeType , class EdgeType >
NodeType& llvm::DirectedGraph< NodeType, EdgeType >::front ( )
inline

Definition at line 199 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ front() [2/2]

template<class NodeType , class EdgeType >
const NodeType& llvm::DirectedGraph< NodeType, EdgeType >::front ( ) const
inline

Definition at line 198 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ operator=() [1/2]

template<class NodeType , class EdgeType >
DGraphType& llvm::DirectedGraph< NodeType, EdgeType >::operator= ( const DGraphType &&  G)
inline

Definition at line 189 of file DirectedGraph.h.

References G, move, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ operator=() [2/2]

template<class NodeType , class EdgeType >
DGraphType& llvm::DirectedGraph< NodeType, EdgeType >::operator= ( const DGraphType G)
inline

Definition at line 185 of file DirectedGraph.h.

References G, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

◆ removeNode()

template<class NodeType , class EdgeType >
bool llvm::DirectedGraph< NodeType, EdgeType >::removeNode ( NodeType &  N)
inline

Remove the given node N from the graph.

If the node has incoming or outgoing edges, they are also removed. Return true if the node was found and then removed, and false if the node was not found in the graph to begin with.

Definition at line 242 of file DirectedGraph.h.

References E, llvm::SmallVectorImpl< T >::erase(), llvm::DirectedGraph< NodeType, EdgeType >::findNode(), IT, N, and llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

Referenced by llvm::DDGBuilder::mergeNodes().

◆ size()

template<class NodeType , class EdgeType >
size_t llvm::DirectedGraph< NodeType, EdgeType >::size ( ) const
inline

Definition at line 203 of file DirectedGraph.h.

References llvm::DirectedGraph< NodeType, EdgeType >::Nodes.

Member Data Documentation

◆ Nodes

template<class NodeType , class EdgeType >
NodeListTy llvm::DirectedGraph< NodeType, EdgeType >::Nodes
protected

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