This helper class creates traversal for a graph. More...

Data Structures
class	iterator

Public Types
typedef alloc::set< iterator > ::type	iterator_list

typedef iterator	reverse_iterator

Public Member Functions
	DFSTraversal (_NodeTy *entry)

int	size () const

_NodeTy *	operator[] (unsigned i) const

int	operator[] (_NodeTy *v) const

int	num_decendants (int v) const

bool	is_ancestor (int v, int w) const

bool	is_decendant (int w, int v) const

iterator	begin ()

iterator	end ()

reverse_iterator	rbegin ()

reverse_iterator	rend ()

Private Types
typedef alloc::vector< _NodeTy * > ::type	NodeMapTy

typedef alloc::map< _NodeTy *, int >::type	IndexMapTy

typedef alloc::vector< int >::type	ParentMapTy

typedef alloc::vector< int >::type	DecendantMapTy

typedef alloc::set< _NodeTy * > ::type	NodeListTy

typedef alloc::set< int >::type	SuccessorListTy

typedef alloc::vector < SuccessorListTy >::type	SuccessorListMapTy

Private Member Functions
NodeListTy &	successor (_NodeTy *v, NodeListTy &list)

int	num_nodes (_NodeTy *v) const

int	dfs (_NodeTy *v)

template<>
DFSTraversal< BeginInst > ::NodeListTy &	successor (BeginInst *v, NodeListTy &list)

template<>
int	num_nodes (BeginInst *v) const

template<>
DFSTraversal < MachineBasicBlock > ::NodeListTy &	successor (MachineBasicBlock *v, NodeListTy &list)

template<>
int	num_nodes (MachineBasicBlock *v) const

template<>
DFSTraversal< BeginInst > ::NodeListTy &	successor (BeginInst *v, NodeListTy &list)

template<>
int	num_nodes (BeginInst *v) const

Private Attributes
NodeMapTy	vertex

IndexMapTy	index

ParentMapTy	parent

SuccessorListMapTy	succ

DecendantMapTy	number_decendants

int	n

int	_size

Friends
class	DFSTraversal::iterator

Detailed Description

template<class _NodeTy>
class cacao::jit::compiler2::DFSTraversal< _NodeTy >

This helper class creates traversal for a graph.

The only information required from the graph is the successor relation successor() and number of vertices num_nodes.

Definition at line 51 of file GraphHelper.hpp.

Member Typedef Documentation

template<class _NodeTy>

typedef alloc::vector<int>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::DecendantMapTy

private

Definition at line 56 of file GraphHelper.hpp.

template<class _NodeTy>

typedef alloc::map<_NodeTy *,int>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::IndexMapTy

private

Definition at line 54 of file GraphHelper.hpp.

template<class _NodeTy>

typedef alloc::set<iterator>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::iterator_list

Definition at line 77 of file GraphHelper.hpp.

template<class _NodeTy>

typedef alloc::set<_NodeTy *>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::NodeListTy

private

Definition at line 58 of file GraphHelper.hpp.

template<class _NodeTy>

typedef alloc::vector<_NodeTy *>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::NodeMapTy

private

Definition at line 53 of file GraphHelper.hpp.

template<class _NodeTy>

typedef alloc::vector<int>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::ParentMapTy

private

Definition at line 55 of file GraphHelper.hpp.

template<class _NodeTy>

typedef iterator cacao::jit::compiler2::DFSTraversal< _NodeTy >::reverse_iterator

Definition at line 234 of file GraphHelper.hpp.

template<class _NodeTy>

typedef alloc::vector<SuccessorListTy>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::SuccessorListMapTy

private

Definition at line 60 of file GraphHelper.hpp.

template<class _NodeTy>

typedef alloc::set<int>::type cacao::jit::compiler2::DFSTraversal< _NodeTy >::SuccessorListTy

private

Definition at line 59 of file GraphHelper.hpp.

Constructor & Destructor Documentation

template<class _NodeTy>

cacao::jit::compiler2::DFSTraversal< _NodeTy >::DFSTraversal ( _NodeTy * entry )

inlineexplicit

Definition at line 80 of file GraphHelper.hpp.

Member Function Documentation

template<class _NodeTy>

iterator cacao::jit::compiler2::DFSTraversal< _NodeTy >::begin ( )

inline

Definition at line 236 of file GraphHelper.hpp.

template<class _NodeTy>

int cacao::jit::compiler2::DFSTraversal< _NodeTy >::dfs ( _NodeTy * v )

private

Definition at line 256 of file GraphHelper.hpp.

template<class _NodeTy>

iterator cacao::jit::compiler2::DFSTraversal< _NodeTy >::end ( )

inline

Definition at line 240 of file GraphHelper.hpp.

template<class _NodeTy>

bool cacao::jit::compiler2::DFSTraversal< _NodeTy >::is_ancestor	(	int	v,
		int	w
	)		const

inline

Definition at line 132 of file GraphHelper.hpp.

template<class _NodeTy>

bool cacao::jit::compiler2::DFSTraversal< _NodeTy >::is_decendant	(	int	w,
		int	v
	)		const

inline

Definition at line 146 of file GraphHelper.hpp.

template<class _NodeTy>

int cacao::jit::compiler2::DFSTraversal< _NodeTy >::num_decendants ( int v ) const

inline

Definition at line 122 of file GraphHelper.hpp.

template<>

int cacao::jit::compiler2::DFSTraversal< BeginInst >::num_nodes ( BeginInst * v ) const

private

Definition at line 61 of file GraphHelper.cpp.

template<class _NodeTy>

int cacao::jit::compiler2::DFSTraversal< _NodeTy >::num_nodes ( _NodeTy * v ) const

private

template<>

int cacao::jit::compiler2::DFSTraversal< MachineBasicBlock >::num_nodes ( MachineBasicBlock * v ) const

private

Definition at line 75 of file GraphHelper.cpp.

template<>

int cacao::jit::compiler2::DFSTraversal< BeginInst >::num_nodes ( BeginInst * v ) const

private

template<class _NodeTy>

_NodeTy* cacao::jit::compiler2::DFSTraversal< _NodeTy >::operator[] ( unsigned i ) const

inline

Definition at line 111 of file GraphHelper.hpp.

template<class _NodeTy>

int cacao::jit::compiler2::DFSTraversal< _NodeTy >::operator[] ( _NodeTy * v ) const

inline

Definition at line 115 of file GraphHelper.hpp.

template<class _NodeTy>

reverse_iterator cacao::jit::compiler2::DFSTraversal< _NodeTy >::rbegin ( )

inline

Definition at line 244 of file GraphHelper.hpp.

template<class _NodeTy>

reverse_iterator cacao::jit::compiler2::DFSTraversal< _NodeTy >::rend ( )

inline

Definition at line 248 of file GraphHelper.hpp.

template<class _NodeTy>

int cacao::jit::compiler2::DFSTraversal< _NodeTy >::size ( ) const

inline

Definition at line 107 of file GraphHelper.hpp.

template<>

DFSTraversal< BeginInst >::NodeListTy & cacao::jit::compiler2::DFSTraversal< BeginInst >::successor	(	BeginInst *	v,
		NodeListTy &	list
	)

private

Definition at line 41 of file GraphHelper.cpp.

template<>

DFSTraversal< MachineBasicBlock >::NodeListTy & cacao::jit::compiler2::DFSTraversal< MachineBasicBlock >::successor	(	MachineBasicBlock *	v,
		NodeListTy &	list
	)