llvm::ImutAVLTree< ImutInfo > Class Template Reference

#include <ImmutableSet.h>

Inheritance diagram for llvm::ImutAVLTree< ImutInfo >:

Collaboration diagram for llvm::ImutAVLTree< ImutInfo >:

List of all members.

Public Types

typedef ImutInfo::key_type_ref key_type_ref

typedef ImutInfo::value_type value_type

typedef ImutInfo::value_type_ref value_type_ref

typedef ImutAVLFactory< ImutInfo > Factory

typedef
ImutAVLTreeInOrderIterator
< ImutInfo > iterator

Public Member Functions

ImutAVLTree * getLeft () const

ImutAVLTree * getRight () const

unsigned getHeight () const

const value_type & getValue () const

getValue - Returns the data value associated with the tree node.

ImutAVLTree * find (key_type_ref K)

unsigned size () const

iterator begin () const

iterator end () const

bool ElementEqual (value_type_ref V) const

bool ElementEqual (const ImutAVLTree *RHS) const

bool isEqual (const ImutAVLTree &RHS) const

bool isNotEqual (const ImutAVLTree &RHS) const

bool contains (const key_type_ref K)

template<typename Callback>

void foreach (Callback &C)

unsigned verify () const

void Profile (llvm::FoldingSetNodeID &ID)

Profile - Profiling for ImutAVLTree.

Friends

class ImutAVLFactory< ImutInfo >

class ImutAVLTreeGenericIterator< ImutInfo >

class FoldingSet< ImutAVLTree >

Detailed Description

template<typename ImutInfo>
class llvm::ImutAVLTree< ImutInfo >

Definition at line 34 of file ImmutableSet.h.

Member Typedef Documentation

template<typename ImutInfo>

typedef ImutInfo::key_type_ref llvm::ImutAVLTree< ImutInfo >::key_type_ref

Definition at line 36 of file ImmutableSet.h.

template<typename ImutInfo>

typedef ImutInfo::value_type llvm::ImutAVLTree< ImutInfo >::value_type

Definition at line 37 of file ImmutableSet.h.

template<typename ImutInfo>

typedef ImutInfo::value_type_ref llvm::ImutAVLTree< ImutInfo >::value_type_ref

Definition at line 38 of file ImmutableSet.h.

template<typename ImutInfo>

typedef ImutAVLFactory<ImutInfo> llvm::ImutAVLTree< ImutInfo >::Factory

Definition at line 40 of file ImmutableSet.h.

template<typename ImutInfo>

typedef ImutAVLTreeInOrderIterator<ImutInfo> llvm::ImutAVLTree< ImutInfo >::iterator

Definition at line 46 of file ImmutableSet.h.

Member Function Documentation

template<typename ImutInfo>

ImutAVLTree* llvm::ImutAVLTree< ImutInfo >::getLeft ( ) const [inline]

getLeft - Returns a pointer to the left subtree. This value is NULL if there is no left subtree.

Definition at line 54 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ImutInfo >::find(), llvm::ImutAVLTree< ImutInfo >::foreach(), llvm::ImutAVLTree< ImutInfo >::size(), and llvm::ImutAVLTree< ImutInfo >::verify().

template<typename ImutInfo>

ImutAVLTree* llvm::ImutAVLTree< ImutInfo >::getRight ( ) const [inline]

getRight - Returns a pointer to the right subtree. This value is NULL if there is no right subtree.

Definition at line 62 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ImutInfo >::find(), llvm::ImutAVLTree< ImutInfo >::foreach(), llvm::ImutAVLTree< ImutInfo >::size(), and llvm::ImutAVLTree< ImutInfo >::verify().

template<typename ImutInfo>

unsigned llvm::ImutAVLTree< ImutInfo >::getHeight ( ) const [inline]

getHeight - Returns the height of the tree. A tree with no subtrees has a height of 1.

Definition at line 67 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ImutInfo >::verify().

template<typename ImutInfo>

const value_type& llvm::ImutAVLTree< ImutInfo >::getValue ( ) const [inline]

getValue - Returns the data value associated with the tree node.

Definition at line 70 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ImutInfo >::ElementEqual(), llvm::ImutAVLTree< ImutInfo >::find(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::lookup(), and llvm::ImutAVLTree< ImutInfo >::verify().

template<typename ImutInfo>

ImutAVLTree* llvm::ImutAVLTree< ImutInfo >::find ( key_type_ref K ) [inline]

find - Finds the subtree associated with the specified key value. This method returns NULL if no matching subtree is found.

Definition at line 74 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::getLeft(), llvm::ImutAVLTree< ImutInfo >::getRight(), llvm::ImutAVLTree< ImutInfo >::getValue(), and T.

Referenced by llvm::ImutAVLTree< ImutInfo >::contains().

template<typename ImutInfo>

unsigned llvm::ImutAVLTree< ImutInfo >::size ( ) const [inline]

size - Returns the number of nodes in the tree, which includes both leaves and non-leaf nodes.

Definition at line 93 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::getLeft(), llvm::ImutAVLTree< ImutInfo >::getRight(), L, and R.

template<typename ImutInfo>

iterator llvm::ImutAVLTree< ImutInfo >::begin ( ) const [inline]

begin - Returns an iterator that iterates over the nodes of the tree in an inorder traversal. The returned iterator thus refers to the the tree node with the minimum data element.

Definition at line 105 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ImutInfo >::isEqual().

template<typename ImutInfo>

iterator llvm::ImutAVLTree< ImutInfo >::end ( ) const [inline]

end - Returns an iterator for the tree that denotes the end of an inorder traversal.

Definition at line 109 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ImutInfo >::isEqual().

template<typename ImutInfo>

bool llvm::ImutAVLTree< ImutInfo >::ElementEqual ( value_type_ref V ) const [inline]

Definition at line 111 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::getValue().

Referenced by llvm::ImutAVLTree< ImutInfo >::ElementEqual().

template<typename ImutInfo>

bool llvm::ImutAVLTree< ImutInfo >::ElementEqual ( const ImutAVLTree< ImutInfo > * RHS ) const [inline]

Definition at line 125 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::ElementEqual(), and llvm::ImutAVLTree< ImutInfo >::getValue().

template<typename ImutInfo>

bool llvm::ImutAVLTree< ImutInfo >::isEqual ( const ImutAVLTree< ImutInfo > & RHS ) const [inline]

isEqual - Compares two trees for structural equality and returns true if they are equal. This worst case performance of this operation is

Definition at line 132 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::begin(), llvm::ImutAVLTree< ImutInfo >::end(), and llvm::ImutAVLTreeInOrderIterator< ImutInfo >::SkipSubTree().

Referenced by llvm::ImutAVLTree< ImutInfo >::isNotEqual().

template<typename ImutInfo>

bool llvm::ImutAVLTree< ImutInfo >::isNotEqual ( const ImutAVLTree< ImutInfo > & RHS ) const [inline]

isNotEqual - Compares two trees for structural inequality. Performance is the same is isEqual.

Definition at line 158 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::isEqual().

template<typename ImutInfo>

bool llvm::ImutAVLTree< ImutInfo >::contains ( const key_type_ref K ) [inline]

contains - Returns true if this tree contains a subtree (node) that has an data element that matches the specified key. Complexity is logarithmic in the size of the tree.

Definition at line 163 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::find().

template<typename ImutInfo>

template<typename Callback>

void llvm::ImutAVLTree< ImutInfo >::foreach ( Callback & C ) [inline]

foreach - A member template the accepts invokes operator() on a functor object (specifed by Callback) for every node/subtree in the tree. Nodes are visited using an inorder traversal.

Definition at line 169 of file ImmutableSet.h.

References llvm::CallingConv::C, llvm::ImutAVLTree< ImutInfo >::getLeft(), llvm::ImutAVLTree< ImutInfo >::getRight(), L, and R.

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::foreach().

template<typename ImutInfo>

unsigned llvm::ImutAVLTree< ImutInfo >::verify ( ) const [inline]

verify - A utility method that checks that the balancing and ordering invariants of the tree are satisifed. It is a recursive method that returns the height of the tree, which is then consumed by the enclosing verify call. External callers should ignore the return value. An invalid tree will cause an assertion to fire in a debug build.

Definition at line 183 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::getHeight(), llvm::ImutAVLTree< ImutInfo >::getLeft(), llvm::ImutAVLTree< ImutInfo >::getRight(), llvm::ImutAVLTree< ImutInfo >::getValue(), and llvm::ImutAVLTree< ImutInfo >::verify().

Referenced by llvm::ImutAVLTree< ImutInfo >::verify(), and llvm::ImmutableMap< KeyT, ValT, ValInfo >::verify().

template<typename ImutInfo>

void llvm::ImutAVLTree< ImutInfo >::Profile ( llvm::FoldingSetNodeID & ID ) [inline]

Profile - Profiling for ImutAVLTree.

Definition at line 209 of file ImmutableSet.h.

References llvm::FoldingSetNodeID::AddInteger().

Friends And Related Function Documentation

template<typename ImutInfo>

friend class ImutAVLFactory< ImutInfo > [friend]

Definition at line 41 of file ImmutableSet.h.

template<typename ImutInfo>

friend class ImutAVLTreeGenericIterator< ImutInfo > [friend]

Definition at line 43 of file ImmutableSet.h.

template<typename ImutInfo>

friend class FoldingSet< ImutAVLTree > [friend]

Definition at line 44 of file ImmutableSet.h.

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

ImmutableSet.h


Public Types
typedef ImutInfo::key_type_ref	key_type_ref
typedef ImutInfo::value_type	value_type
typedef ImutInfo::value_type_ref	value_type_ref
typedef ImutAVLFactory< ImutInfo >	Factory
typedef ImutAVLTreeInOrderIterator < ImutInfo >	iterator
Public Member Functions
ImutAVLTree *	getLeft () const
ImutAVLTree *	getRight () const
unsigned	getHeight () const
const value_type &	getValue () const
	getValue - Returns the data value associated with the tree node.
ImutAVLTree *	find (key_type_ref K)
unsigned	size () const
iterator	begin () const
iterator	end () const
bool	ElementEqual (value_type_ref V) const
bool	ElementEqual (const ImutAVLTree *RHS) const
bool	isEqual (const ImutAVLTree &RHS) const
bool	isNotEqual (const ImutAVLTree &RHS) const
bool	contains (const key_type_ref K)
template<typename Callback>
void	foreach (Callback &C)
unsigned	verify () const
void	Profile (llvm::FoldingSetNodeID &ID)
	Profile - Profiling for ImutAVLTree.
Friends
class	ImutAVLFactory< ImutInfo >
class	ImutAVLTreeGenericIterator< ImutInfo >
class	FoldingSet< ImutAVLTree >

llvm::ImutAVLTree< ImutInfo > Class Template Reference

Public Types

Public Member Functions

Friends

Detailed Description

template<typename ImutInfo> class llvm::ImutAVLTree< ImutInfo >

Member Typedef Documentation

Member Function Documentation

Friends And Related Function Documentation

template<typename ImutInfo>
class llvm::ImutAVLTree< ImutInfo >