#include "llvm/ADT/ImmutableSet.h"

Inheritance diagram for llvm::ImutAVLTree< ImutInfo, Canonicalize >:

Public Types
using	key_type_ref = typename ImutInfo::key_type_ref
using	value_type = typename ImutInfo::value_type
using	value_type_ref = typename ImutInfo::value_type_ref
using	Factory = ImutAVLFactory<ImutInfo, Canonicalize>
using	iterator = ImutAVLTreeInOrderIterator<ImutInfo, Canonicalize>

Public Member Functions
ImutAVLTree *	getLeft () const
	Return a pointer to the left subtree.
ImutAVLTree *	getRight () const
	Return a pointer to the right subtree.
unsigned	getHeight () const
	Returns the height of the tree. A tree with no subtrees has a height of 1.
const value_type &	getValue () const
	Returns the data value associated with the tree node.
ImutAVLTree *	find (key_type_ref K)
	Finds the subtree associated with the specified key value.
ImutAVLTree *	getMaxElement ()
	Find the subtree associated with the highest ranged key value.
unsigned	size () const
	Returns the number of nodes in the tree, which includes both leaves and.
iterator	begin () const
	Returns an iterator that iterates over the nodes of the tree in an inorder traversal.
iterator	end () const
	Returns an iterator for the tree that denotes the end of an inorder traversal.
bool	isElementEqual (value_type_ref V) const
bool	isElementEqual (const ImutAVLTree *RHS) const
bool	isEqual (const ImutAVLTree &RHS) const
	Compares two trees for structural equality and returns true if they are equal.
bool	isNotEqual (const ImutAVLTree &RHS) const
	Compares two trees for structural inequality.
bool	contains (key_type_ref K)
	Returns true if this tree contains a subtree (node) that has an data element that matches the specified key.
unsigned	validateTree () const
	A utility method that checks that the balancing and ordering invariants of the tree are satisfied.
void	retain ()
void	release ()
LLVM_ATTRIBUTE_NOINLINE void	destroy ()

Friends
class	ImutAVLFactory< ImutInfo, Canonicalize >

Detailed Description

template<typename ImutInfo, bool Canonicalize = true>
class llvm::ImutAVLTree< ImutInfo, Canonicalize >

Definition at line 75 of file ImmutableSet.h.

Member Typedef Documentation

◆ Factory

template<typename ImutInfo, bool Canonicalize = true>

using llvm::ImutAVLTree< ImutInfo, Canonicalize >::Factory = ImutAVLFactory<ImutInfo, Canonicalize>

Definition at line 82 of file ImmutableSet.h.

◆ iterator

template<typename ImutInfo, bool Canonicalize = true>

using llvm::ImutAVLTree< ImutInfo, Canonicalize >::iterator = ImutAVLTreeInOrderIterator<ImutInfo, Canonicalize>

Definition at line 83 of file ImmutableSet.h.

◆ key_type_ref

template<typename ImutInfo, bool Canonicalize = true>

using llvm::ImutAVLTree< ImutInfo, Canonicalize >::key_type_ref = typename ImutInfo::key_type_ref

Definition at line 79 of file ImmutableSet.h.

◆ value_type

template<typename ImutInfo, bool Canonicalize = true>

using llvm::ImutAVLTree< ImutInfo, Canonicalize >::value_type = typename ImutInfo::value_type

Definition at line 80 of file ImmutableSet.h.

◆ value_type_ref

template<typename ImutInfo, bool Canonicalize = true>

using llvm::ImutAVLTree< ImutInfo, Canonicalize >::value_type_ref = typename ImutInfo::value_type_ref

Definition at line 81 of file ImmutableSet.h.

Member Function Documentation

◆ begin()

template<typename ImutInfo, bool Canonicalize = true>

iterator llvm::ImutAVLTree< ImutInfo, Canonicalize >::begin ( ) const

inline

Returns an iterator that iterates over the nodes of the tree in an inorder traversal.

The returned iterator thus refers to the tree node with the minimum data element.

Definition at line 147 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::isEqual().

◆ contains()

template<typename ImutInfo, bool Canonicalize = true>

bool llvm::ImutAVLTree< ImutInfo, Canonicalize >::contains ( key_type_ref K )

inline

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 205 of file ImmutableSet.h.

◆ destroy()

template<typename ImutInfo, bool Canonicalize = true>

LLVM_ATTRIBUTE_NOINLINE void llvm::ImutAVLTree< ImutInfo, Canonicalize >::destroy ( )

inline

Definition at line 360 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getCanonicalTree(), and llvm::ImutAVLTree< ValInfo, Canonicalize >::release().

◆ end()

template<typename ImutInfo, bool Canonicalize = true>

iterator llvm::ImutAVLTree< ImutInfo, Canonicalize >::end ( ) const

inline

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

Definition at line 151 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::isEqual().

◆ find()

template<typename ImutInfo, bool Canonicalize = true>

ImutAVLTree * llvm::ImutAVLTree< ImutInfo, Canonicalize >::find ( key_type_ref K )

inline

Finds the subtree associated with the specified key value.

This method returns NULL if no matching subtree is found.

Definition at line 111 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::contains().

◆ getHeight()

template<typename ImutInfo, bool Canonicalize = true>

unsigned llvm::ImutAVLTree< ImutInfo, Canonicalize >::getHeight ( ) const

inline

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

Definition at line 104 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::validateTree().

◆ getLeft()

template<typename ImutInfo, bool Canonicalize = true>

ImutAVLTree * llvm::ImutAVLTree< ImutInfo, Canonicalize >::getLeft ( ) const

inline

Return a pointer to the left subtree.

This value is NULL if there is no left subtree.

Definition at line 97 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::size(), and llvm::ImutAVLTree< ValInfo, Canonicalize >::validateTree().

◆ getMaxElement()

template<typename ImutInfo, bool Canonicalize = true>

ImutAVLTree * llvm::ImutAVLTree< ImutInfo, Canonicalize >::getMaxElement ( )

inline

Find the subtree associated with the highest ranged key value.

Definition at line 126 of file ImmutableSet.h.

◆ getRight()

template<typename ImutInfo, bool Canonicalize = true>

ImutAVLTree * llvm::ImutAVLTree< ImutInfo, Canonicalize >::getRight ( ) const

inline

Return a pointer to the right subtree.

This value is NULL if there is no right subtree.

Definition at line 101 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::size(), and llvm::ImutAVLTree< ValInfo, Canonicalize >::validateTree().

◆ getValue()

template<typename ImutInfo, bool Canonicalize = true>

const value_type & llvm::ImutAVLTree< ImutInfo, Canonicalize >::getValue ( ) const

inline

Returns the data value associated with the tree node.

Definition at line 107 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::isElementEqual(), and llvm::ImutAVLTree< ValInfo, Canonicalize >::validateTree().

◆ isElementEqual() [1/2]

template<typename ImutInfo, bool Canonicalize = true>

bool llvm::ImutAVLTree< ImutInfo, Canonicalize >::isElementEqual ( const ImutAVLTree< ImutInfo, Canonicalize > * RHS ) const

inline

Definition at line 167 of file ImmutableSet.h.

◆ isElementEqual() [2/2]

template<typename ImutInfo, bool Canonicalize = true>

bool llvm::ImutAVLTree< ImutInfo, Canonicalize >::isElementEqual ( value_type_ref V ) const

inline

Definition at line 153 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::isElementEqual(), and llvm::ImutAVLTree< ValInfo, Canonicalize >::isEqual().

◆ isEqual()

template<typename ImutInfo, bool Canonicalize = true>

bool llvm::ImutAVLTree< ImutInfo, Canonicalize >::isEqual ( const ImutAVLTree< ImutInfo, Canonicalize > & RHS ) const

inline

Compares two trees for structural equality and returns true if they are equal.

The worst case performance of this operation is linear in the sizes of the trees.

Definition at line 174 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getCanonicalTree(), and llvm::ImutAVLTree< ValInfo, Canonicalize >::isNotEqual().

◆ isNotEqual()

template<typename ImutInfo, bool Canonicalize = true>

bool llvm::ImutAVLTree< ImutInfo, Canonicalize >::isNotEqual ( const ImutAVLTree< ImutInfo, Canonicalize > & RHS ) const

inline

Compares two trees for structural inequality.

Performance is the same as isEqual.

Definition at line 200 of file ImmutableSet.h.

◆ release()

template<typename ImutInfo, bool Canonicalize = true>

void llvm::ImutAVLTree< ImutInfo, Canonicalize >::release ( )

inline

Definition at line 354 of file ImmutableSet.h.

◆ retain()

template<typename ImutInfo, bool Canonicalize = true>

void llvm::ImutAVLTree< ImutInfo, Canonicalize >::retain ( )

inline

Definition at line 352 of file ImmutableSet.h.

◆ size()

template<typename ImutInfo, bool Canonicalize = true>

unsigned llvm::ImutAVLTree< ImutInfo, Canonicalize >::size ( ) const

inline

Returns the number of nodes in the tree, which includes both leaves and.

Definition at line 135 of file ImmutableSet.h.

◆ validateTree()

template<typename ImutInfo, bool Canonicalize = true>

unsigned llvm::ImutAVLTree< ImutInfo, Canonicalize >::validateTree ( ) const

inline

A utility method that checks that the balancing and ordering invariants of the tree are satisfied.

It is a recursive method that returns the height of the tree, which is then consumed by the enclosing validateTree call. External callers should ignore the return value. An invalid tree will cause an assertion to fire in a debug build.

Definition at line 212 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::validateTree().

◆ ImutAVLFactory< ImutInfo, Canonicalize >

template<typename ImutInfo, bool Canonicalize = true>

friend class ImutAVLFactory< ImutInfo, Canonicalize >

friend

Definition at line 69 of file ImmutableSet.h.

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

include/llvm/ADT/ImmutableSet.h

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ Factory

◆ iterator

◆ key_type_ref

◆ value_type

◆ value_type_ref

Member Function Documentation

◆ begin()

◆ contains()

◆ destroy()

◆ end()

◆ find()

◆ getHeight()

◆ getLeft()

◆ getMaxElement()

◆ getRight()

◆ getValue()

◆ isElementEqual() [1/2]

◆ isElementEqual() [2/2]

◆ isEqual()

◆ isNotEqual()

◆ release()

◆ retain()

◆ size()

◆ validateTree()

Friends And Related Symbol Documentation

◆ ImutAVLFactory< ImutInfo, Canonicalize >