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.

typedef std::pair< VI, VI >	EdgeIdentifier

using	VertexValueType = detail::DenseMapPair< VertexIdentifier, VertexAttribute >
	This type is the value_type of all iterators which range over vertices, Determined by the Vertices DenseMap.

using	EdgeValueType = detail::DenseMapPair< EdgeIdentifier, EdgeAttribute >
	This type is the value_type of all iterators which range over edges, Determined by the Edges DenseMap.

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.

using	InEdgeIterator = NeighborEdgeIteratorT< false, false >
	An iterator type for iterating through the set of edges leaving a vertex.

using	ConstOutEdgeIterator = NeighborEdgeIteratorT< true, true >
	A const iterator type for iterating through the set of edges entering a vertex.

using	OutEdgeIterator = NeighborEdgeIteratorT< false, true >
	An iterator type for iterating through the set of edges leaving a vertex.

using	ConstVertexIterator = typename VertexMapT::const_iterator
	A const iterator type for iterating through the whole vertex set of the graph.

using	VertexIterator = typename VertexMapT::iterator
	An iterator type for iterating through the whole vertex set of the graph.

using	ConstEdgeIterator = typename EdgeMapT::const_iterator
	A const iterator for iterating through the entire edge set of the graph.

using	EdgeIterator = typename EdgeMapT::iterator
	An iterator for iterating through the entire edge set of the graph.

Public Member Functions
void	clear ()
	Empty the Graph.

VertexView< false >	vertices ()
	Returns a view object allowing iteration over the vertices of the graph.

VertexView< true >	vertices () const

EdgeView< false >	edges ()
	Returns a view object allowing iteration over the edges of the graph.

EdgeView< true >	edges () const

InOutEdgeView< false, true >	outEdges (const VertexIdentifier I)
	Returns a view object allowing iteration over the edges which start at a vertex I.

InOutEdgeView< true, true >	outEdges (const VertexIdentifier I) const

InOutEdgeView< false, false >	inEdges (const VertexIdentifier I)
	Returns a view object allowing iteration over the edges which point to a vertex I.

InOutEdgeView< true, false >	inEdges (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.

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.

Expected< VertexAttribute & >	at (const VertexIdentifier &I)
	Looks up a vertex with Identifier I, or an error if it does not exist.

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.

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.

size_type	count (const EdgeIdentifier &I) const
	Looks for an edge with Identifier I, returns 1 if one exists and 0 otherwise.

std::pair< VertexIterator, bool >	insert (const std::pair< VertexIdentifier, VertexAttribute > &Val)
	Inserts a vertex into the graph with Identifier Val.first, and Attribute Val.second.

std::pair< VertexIterator, bool >	insert (std::pair< VertexIdentifier, VertexAttribute > &&Val)

std::pair< EdgeIterator, bool >	insert (const std::pair< EdgeIdentifier, EdgeAttribute > &Val)
	Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

std::pair< EdgeIterator, bool >	insert (std::pair< EdgeIdentifier, EdgeAttribute > &&Val)
	Inserts an edge into the graph with Identifier Val.first, and Attribute Val.second.

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:

VertexAttribute, this is a structure which is stored for each vertex. Must be DefaultConstructible, CopyConstructible, CopyAssignable and Destructible.
EdgeAttribute, this is a structure which is stored for each edge Must be DefaultConstructible, CopyConstructible, CopyAssignable and Destructible.
EdgeAttribute, this is a structure which is stored for each variable
VI, this is a type over which DenseMapInfo is defined and is the type used look up strings, available as VertexIdentifier.
If the built in DenseMapInfo is not defined, provide a specialization class type here.

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 74 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 298 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 175 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 186 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 261 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 78 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 303 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 87 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 180 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 191 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 89 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 77 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 266 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 82 of file Graph.h.

Member Function Documentation

◆ at() [1/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 417 of file Graph.h.

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

◆ at() [2/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

Definition at line 426 of file Graph.h.

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

◆ at() [3/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 398 of file Graph.h.

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

◆ at() [4/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

Definition at line 407 of file Graph.h.

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

◆ clear()

template<typename VertexAttribute , typename EdgeAttribute , typename VI = int32_t>

void llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::clear ( )

inline

Empty the Graph.

Definition at line 340 of file Graph.h.

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

◆ count() [1/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 443 of file Graph.h.

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

◆ count() [2/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 437 of file Graph.h.

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

◆ 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 355 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 357 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 371 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 375 of file Graph.h.

References I.

◆ insert() [1/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 461 of file Graph.h.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::FindAndConstruct(), and 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 ( const std::pair< VertexIdentifier, VertexAttribute > & Val )

inline

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

Definition at line 448 of file Graph.h.

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

◆ insert() [3/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 478 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< VertexIterator, bool > llvm::xray::Graph< VertexAttribute, EdgeAttribute, VI >::insert ( std::pair< VertexIdentifier, VertexAttribute > && Val )

inline

Definition at line 453 of file Graph.h.

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

◆ operator[]() [1/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 388 of file Graph.h.

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

◆ operator[]() [2/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 381 of file Graph.h.

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

◆ 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 361 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 365 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 349 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 351 of file Graph.h.

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

include/llvm/XRay/Graph.h

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ ConstEdgeIterator

◆ ConstInEdgeIterator

◆ ConstOutEdgeIterator

◆ ConstVertexIterator

◆ EdgeIdentifier

◆ EdgeIterator

◆ EdgeValueType

◆ InEdgeIterator

◆ OutEdgeIterator

◆ size_type

◆ VertexIdentifier

◆ VertexIterator

◆ VertexValueType

Member Function Documentation

◆ at() [1/4]

◆ at() [2/4]

◆ at() [3/4]

◆ at() [4/4]

◆ clear()

◆ count() [1/2]

◆ count() [2/2]

◆ edges() [1/2]

◆ edges() [2/2]

◆ inEdges() [1/2]

◆ inEdges() [2/2]

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ outEdges() [1/2]

◆ outEdges() [2/2]

◆ vertices() [1/2]

◆ vertices() [2/2]