LLVM  6.0.0svn
Classes | Public Types | Public Member Functions | List of all members
llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI > Class Template Reference

A Graph object represents a Directed Graph and is used in XRay to compute and store function call graphs and associated statistical information. More...

#include "llvm/XRay/Graph.h"

Classes

class  EdgeView
 A class for ranging over all the edges in the graph. More...
 
class  InOutEdgeView
 A class for ranging over the incoming edges incident to a vertex. More...
 
class  VertexView
 A class for ranging over the vertices in the graph. More...
 

Public Types

typedef VI VertexIdentifier
 These objects are used to name edges and vertices in the graph. More...
 
typedef std::pair< VI, VIEdgeIdentifier
 
using VertexValueType = detail::DenseMapPair< VertexIdentifier, VertexAttribute >
 This type is the value_type of all iterators which range over vertices, Determined by the Vertices DenseMap. More...
 
using EdgeValueType = detail::DenseMapPair< EdgeIdentifier, EdgeAttribute >
 This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap. More...
 
using size_type = std::size_t
 
using ConstInEdgeIterator = NeighborEdgeIteratorT< true, false >
 A const iterator type for iterating through the set of edges entering a vertex. More...
 
using InEdgeIterator = NeighborEdgeIteratorT< false, false >
 An iterator type for iterating through the set of edges leaving a vertex. More...
 
using ConstOutEdgeIterator = NeighborEdgeIteratorT< true, true >
 A const iterator type for iterating through the set of edges entering a vertex. More...
 
using OutEdgeIterator = NeighborEdgeIteratorT< false, true >
 An iterator type for iterating through the set of edges leaving a vertex. More...
 
using ConstVertexIterator = typename VertexMapT::const_iterator
 A const iterator type for iterating through the whole vertex set of the graph. More...
 
using VertexIterator = typename VertexMapT::iterator
 An iterator type for iterating through the whole vertex set of the graph. More...
 
using ConstEdgeIterator = typename EdgeMapT::const_iterator
 A const iterator for iterating through the entire edge set of the graph. More...
 
using EdgeIterator = typename EdgeMapT::iterator
 An iterator for iterating through the entire edge set of the graph. More...
 

Public Member Functions

void clear ()
 Empty the Graph. More...
 
VertexView< falsevertices ()
 Returns a view object allowing iteration over the vertices of the graph. More...
 
VertexView< truevertices () const
 
EdgeView< falseedges ()
 Returns a view object allowing iteration over the edges of the graph. More...
 
EdgeView< trueedges () const
 
InOutEdgeView< false, trueoutEdges (const VertexIdentifier I)
 Returns a view object allowing iteration over the edges which start at a vertex I. More...
 
InOutEdgeView< true, trueoutEdges (const VertexIdentifier I) const
 
InOutEdgeView< false, falseinEdges (const VertexIdentifier I)
 Returns a view object allowing iteration over the edges which point to a vertex I. More...
 
InOutEdgeView< true, falseinEdges (const VertexIdentifier I) const
 
VertexAttribute & operator[] (const VertexIdentifier &I)
 Looks up the vertex with identifier I, if it does not exist it default constructs it. More...
 
EdgeAttribute & operator[] (const EdgeIdentifier &I)
 Looks up the edge with identifier I, if it does not exist it default constructs it, if it's endpoints do not exist it also default constructs them. More...
 
Expected< VertexAttribute & > at (const VertexIdentifier &I)
 Looks up a vertex with Identifier I, or an error if it does not exist. More...
 
Expected< const VertexAttribute & > at (const VertexIdentifier &I) const
 
Expected< EdgeAttribute & > at (const EdgeIdentifier &I)
 Looks up an edge with Identifier I, or an error if it does not exist. More...
 
Expected< const EdgeAttribute & > at (const EdgeIdentifier &I) const
 
size_type count (const VertexIdentifier &I) const
 Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise. More...
 
size_type count (const EdgeIdentifier &I) const
 Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise. More...
 
std::pair< VertexIterator, boolinsert (const std::pair< VertexIdentifier, VertexAttribute > &Val)
 Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second. More...
 
std::pair< VertexIterator, boolinsert (std::pair< VertexIdentifier, VertexAttribute > &&Val)
 
std::pair< EdgeIterator, boolinsert (const std::pair< EdgeIdentifier, EdgeAttribute > &Val)
 Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second. More...
 
std::pair< EdgeIterator, boolinsert (std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
 Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second. More...
 

Detailed Description

template<typename VertexAttribute, typename EdgeAttribute, typename VI = int32_t>
class llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >

A Graph object represents a Directed Graph and is used in XRay to compute and store function call graphs and associated statistical information.

The graph takes in four template parameters, these are:

Graph is CopyConstructible, CopyAssignable, MoveConstructible and MoveAssignable but is not EqualityComparible or LessThanComparible.

Usage Example Graph with weighted edges and vertices: Graph<int, int, int> G;

G[1] = 0; G[2] = 2; G[{1,2}] = 1; G[{2,1}] = -1; for(const auto &v : G.vertices()){ // Do something with the vertices in the graph; } for(const auto &e : G.edges()){ // Do something with the edges in the graph; }

Usage Example with StrRef keys. Graph<int, double, StrRef> StrG; char va[] = "Vertex A"; char vaa[] = "Vertex A"; char vb[] = "Vertex B"; // Vertices are referenced by String Refs. G[va] = 0; G[vb] = 1; G[{va, vb}] = 1.0; cout() << G[vaa] << " " << G[{vaa, vb}]; //prints "0 1.0".

Definition at line 75 of file Graph.h.

Member Typedef Documentation

◆ ConstEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstEdgeIterator = typename EdgeMapT::const_iterator

A const iterator for iterating through the entire edge set of the graph.

Has a const EdgeValueType as its value_type

Definition at line 299 of file Graph.h.

◆ ConstInEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstInEdgeIterator = NeighborEdgeIteratorT<true, false>

A const iterator type for iterating through the set of edges entering a vertex.

Has a const EdgeValueType as its value_type

Definition at line 176 of file Graph.h.

◆ ConstOutEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstOutEdgeIterator = NeighborEdgeIteratorT<true, true>

A const iterator type for iterating through the set of edges entering a vertex.

Has a const EdgeValueType as its value_type

Definition at line 187 of file Graph.h.

◆ ConstVertexIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::ConstVertexIterator = typename VertexMapT::const_iterator

A const iterator type for iterating through the whole vertex set of the graph.

Has a const VertexValueType as its value_type

Definition at line 262 of file Graph.h.

◆ EdgeIdentifier

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
typedef std::pair<VI, VI> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeIdentifier

Definition at line 79 of file Graph.h.

◆ EdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeIterator = typename EdgeMapT::iterator

An iterator for iterating through the entire edge set of the graph.

Has an EdgeValueType as its value_type

Definition at line 304 of file Graph.h.

◆ EdgeValueType

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::EdgeValueType = detail::DenseMapPair<EdgeIdentifier, EdgeAttribute>

This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap.

Definition at line 88 of file Graph.h.

◆ InEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::InEdgeIterator = NeighborEdgeIteratorT<false, false>

An iterator type for iterating through the set of edges leaving a vertex.

Has an EdgeValueType as its value_type

Definition at line 181 of file Graph.h.

◆ OutEdgeIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::OutEdgeIterator = NeighborEdgeIteratorT<false, true>

An iterator type for iterating through the set of edges leaving a vertex.

Has an EdgeValueType as its value_type

Definition at line 192 of file Graph.h.

◆ size_type

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::size_type = std::size_t

Definition at line 90 of file Graph.h.

◆ VertexIdentifier

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
typedef VI llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexIdentifier

These objects are used to name edges and vertices in the graph.

Definition at line 78 of file Graph.h.

◆ VertexIterator

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexIterator = typename VertexMapT::iterator

An iterator type for iterating through the whole vertex set of the graph.

Has a VertexValueType as its value_type

Definition at line 267 of file Graph.h.

◆ VertexValueType

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
using llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::VertexValueType = detail::DenseMapPair<VertexIdentifier, VertexAttribute>

This type is the value_type of all iterators which range over vertices, Determined by the Vertices DenseMap.

Definition at line 84 of file Graph.h.

Member Function Documentation

◆ at() [1/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected<VertexAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const VertexIdentifier I)
inline

Looks up a vertex with Identifier I, or an error if it does not exist.

Definition at line 399 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::make_error_code().

◆ at() [2/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected<const VertexAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const VertexIdentifier I) const
inline

◆ at() [3/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected<EdgeAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const EdgeIdentifier I)
inline

Looks up an edge with Identifier I, or an error if it does not exist.

Definition at line 418 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::make_error_code().

◆ at() [4/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
Expected<const EdgeAttribute &> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::at ( const EdgeIdentifier I) const
inline

◆ clear()

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
void llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::clear ( )
inline

◆ count() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
size_type llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::count ( const VertexIdentifier I) const
inline

Looks for a vertex with identifier I, returns 1 if one exists, and 0 otherwise.

Definition at line 438 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count().

◆ count() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
size_type llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::count ( const EdgeIdentifier I) const
inline

Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.

Definition at line 444 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count().

◆ edges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
EdgeView<false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::edges ( )
inline

Returns a view object allowing iteration over the edges of the graph.

also allows access to the size of the edge set.

Definition at line 356 of file Graph.h.

◆ edges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
EdgeView<true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::edges ( ) const
inline

Definition at line 358 of file Graph.h.

◆ inEdges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView<false, false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::inEdges ( const VertexIdentifier  I)
inline

Returns a view object allowing iteration over the edges which point to a vertex I.

Definition at line 372 of file Graph.h.

References I.

◆ inEdges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView<true, false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::inEdges ( const VertexIdentifier  I) const
inline

Definition at line 376 of file Graph.h.

References I.

◆ insert() [1/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair<VertexIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( const std::pair< VertexIdentifier, VertexAttribute > &  Val)
inline

Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.

Definition at line 449 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ insert() [2/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair<VertexIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( std::pair< VertexIdentifier, VertexAttribute > &&  Val)
inline

◆ insert() [3/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair<EdgeIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( const std::pair< EdgeIdentifier, EdgeAttribute > &  Val)
inline

Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

If the key is already in the map, it returns false and doesn't update the value.

Definition at line 462 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ insert() [4/4]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
std::pair<EdgeIterator, bool> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( std::pair< EdgeIdentifier, EdgeAttribute > &&  Val)
inline

Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

If the key is already in the map, it returns false and doesn't update the value.

Definition at line 479 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

◆ operator[]() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
VertexAttribute& llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::operator[] ( const VertexIdentifier I)
inline

Looks up the vertex with identifier I, if it does not exist it default constructs it.

Definition at line 382 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct().

◆ operator[]() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
EdgeAttribute& llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::operator[] ( const EdgeIdentifier I)
inline

Looks up the edge with identifier I, if it does not exist it default constructs it, if it's endpoints do not exist it also default constructs them.

Definition at line 389 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), and P.

◆ outEdges() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView<false, true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::outEdges ( const VertexIdentifier  I)
inline

Returns a view object allowing iteration over the edges which start at a vertex I.

Definition at line 362 of file Graph.h.

References I.

◆ outEdges() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
InOutEdgeView<true, true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::outEdges ( const VertexIdentifier  I) const
inline

Definition at line 366 of file Graph.h.

References I.

◆ vertices() [1/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
VertexView<false> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::vertices ( )
inline

Returns a view object allowing iteration over the vertices of the graph.

also allows access to the size of the vertex set.

Definition at line 350 of file Graph.h.

◆ vertices() [2/2]

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>
VertexView<true> llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::vertices ( ) const
inline

Definition at line 352 of file Graph.h.


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