#include "llvm/ADT/ImmutableSet.h"

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 >

using	iterator = ImutAVLTreeInOrderIterator< ImutInfo >

Public Member Functions
ImutAVLTree *	getLeft () const
	Return a pointer to the left subtree. More...

ImutAVLTree *	getRight () const
	Return a pointer to the right subtree. More...

unsigned	getHeight () const
	getHeight - Returns the height of the tree. More...

const value_type &	getValue () const
	getValue - Returns the data value associated with the tree node. More...

ImutAVLTree *	find (key_type_ref K)
	find - Finds the subtree associated with the specified key value. More...

ImutAVLTree *	getMaxElement ()
	getMaxElement - Find the subtree associated with the highest ranged key value. More...

unsigned	size () const
	size - Returns the number of nodes in the tree, which includes both leaves and non-leaf nodes. More...

iterator	begin () const
	begin - Returns an iterator that iterates over the nodes of the tree in an inorder traversal. More...

iterator	end () const
	end - Returns an iterator for the tree that denotes the end of an inorder traversal. More...

bool	isElementEqual (value_type_ref V) const

bool	isElementEqual (const ImutAVLTree *RHS) const

bool	isEqual (const ImutAVLTree &RHS) const
	isEqual - Compares two trees for structural equality and returns true if they are equal. More...

bool	isNotEqual (const ImutAVLTree &RHS) const
	isNotEqual - Compares two trees for structural inequality. More...

bool	contains (key_type_ref K)
	contains - Returns true if this tree contains a subtree (node) that has an data element that matches the specified key. More...

template<typename Callback >
void	foreach (Callback &C)
	foreach - A member template the accepts invokes operator() on a functor object (specifed by Callback) for every node/subtree in the tree. More...

unsigned	validateTree () const
	validateTree - A utility method that checks that the balancing and ordering invariants of the tree are satisifed. More...

void	retain ()

void	release ()

void	destroy ()

Friends
class	ImutAVLFactory< ImutInfo >

class	ImutIntervalAVLFactory< ImutInfo >

class	ImutAVLTreeGenericIterator< ImutInfo >

Detailed Description

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

Definition at line 42 of file ImmutableSet.h.

Member Typedef Documentation

◆ Factory

template<typename ImutInfo >

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

Definition at line 47 of file ImmutableSet.h.

◆ iterator

template<typename ImutInfo >

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

Definition at line 48 of file ImmutableSet.h.

◆ key_type_ref

template<typename ImutInfo >

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

Definition at line 44 of file ImmutableSet.h.

◆ value_type

template<typename ImutInfo >

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

Definition at line 45 of file ImmutableSet.h.

◆ value_type_ref

template<typename ImutInfo >

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

Definition at line 46 of file ImmutableSet.h.

Member Function Documentation

◆ begin()

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

Referenced by llvm::ImutAVLFactory< ImutInfo >::compareTreeWithSection(), llvm::ImutAVLFactory< ImutInfo >::getCanonicalTree(), and llvm::ImutAVLTree< ImutInfo >::isEqual().

◆ contains()

template<typename ImutInfo >

bool llvm::ImutAVLTree< ImutInfo >::contains ( 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 170 of file ImmutableSet.h.

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

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::contains(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::contains(), llvm::ImmutableSet< ValT, ValInfo >::contains(), and llvm::ImmutableSetRef< ValT, ValInfo >::contains().

◆ destroy()

template<typename ImutInfo >

void llvm::ImutAVLTree< ImutInfo >::destroy ( )

inline

Definition at line 340 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::maskCacheIndex(), and llvm::ImutAVLTree< ImutInfo >::release().

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

◆ end()

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

Referenced by llvm::ImutAVLFactory< ImutInfo >::compareTreeWithSection(), llvm::ImutAVLFactory< ImutInfo >::getCanonicalTree(), and llvm::ImutAVLTree< ImutInfo >::isEqual().

◆ find()

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

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

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

◆ foreach()

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

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

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

◆ getHeight()

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

Referenced by llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::getHeight(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::getHeight(), llvm::ImutAVLFactory< ImutInfo >::getHeight(), llvm::ImmutableSet< ValT, ValInfo >::getHeight(), llvm::ImmutableSetRef< ValT, ValInfo >::getHeight(), llvm::ImutAVLFactory< ImutInfo >::incrementHeight(), llvm::ImmutableSet< ValT, ValInfo >::isSingleton(), llvm::ImmutableSetRef< ValT, ValInfo >::isSingleton(), and llvm::ImutAVLTree< ImutInfo >::validateTree().

◆ getLeft()

template<typename ImutInfo >

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

inline

Return a pointer to the left subtree.

This value is NULL if there is no left subtree.

Definition at line 60 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLTree< ImutInfo >::find(), llvm::ImutAVLTree< ImutInfo >::foreach(), llvm::ImutAVLFactory< ImutInfo >::getLeft(), llvm::ImutAVLFactory< ImutInfo >::markImmutable(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), llvm::ImutAVLFactory< ImutInfo >::removeMinBinding(), llvm::ImutAVLTree< ImutInfo >::size(), and llvm::ImutAVLTree< ImutInfo >::validateTree().

◆ getMaxElement()

template<typename ImutInfo >

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

inline

getMaxElement - Find the subtree associated with the highest ranged key value.

Definition at line 91 of file ImmutableSet.h.

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

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::getMaxElement(), and llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::getMaxElement().

◆ getRight()

template<typename ImutInfo >

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

inline

Return a pointer to the right subtree.

This value is NULL if there is no right subtree.

Definition at line 64 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLTree< ImutInfo >::find(), llvm::ImutAVLTree< ImutInfo >::foreach(), llvm::ImutAVLTree< ImutInfo >::getMaxElement(), llvm::ImutAVLFactory< ImutInfo >::getRight(), llvm::ImutAVLFactory< ImutInfo >::markImmutable(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), llvm::ImutAVLFactory< ImutInfo >::removeMinBinding(), llvm::ImutAVLTree< ImutInfo >::size(), and llvm::ImutAVLTree< ImutInfo >::validateTree().

◆ getValue()

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

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::combineTrees(), llvm::ImutAVLFactory< ImutInfo >::createNode(), llvm::ImutAVLTree< ImutInfo >::find(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::getMaxElement(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::getMaxElement(), llvm::ImutAVLTree< ImutInfo >::isElementEqual(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::lookup(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::lookup(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), llvm::ImutAVLFactory< ImutInfo >::removeMinBinding(), and llvm::ImutAVLTree< ImutInfo >::validateTree().

◆ isElementEqual() [1/2]

template<typename ImutInfo >

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

inline

Definition at line 118 of file ImmutableSet.h.

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

Referenced by llvm::ImutAVLFactory< ImutInfo >::compareTreeWithSection(), llvm::ImutAVLTree< ImutInfo >::isElementEqual(), and llvm::ImutAVLTree< ImutInfo >::isEqual().

◆ isElementEqual() [2/2]

template<typename ImutInfo >

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

inline

Definition at line 132 of file ImmutableSet.h.

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

◆ isEqual()

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

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

Referenced by llvm::ImutAVLTree< ImutInfo >::isNotEqual(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::operator==(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::operator==(), llvm::ImmutableSet< ValT, ValInfo >::operator==(), and llvm::ImmutableSetRef< ValT, ValInfo >::operator==().

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

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

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::operator!=(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::operator!=(), llvm::ImmutableSet< ValT, ValInfo >::operator!=(), and llvm::ImmutableSetRef< ValT, ValInfo >::operator!=().

◆ release()

template<typename ImutInfo >

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

inline

Definition at line 334 of file ImmutableSet.h.

References assert(), and llvm::ImutAVLTree< ImutInfo >::destroy().

Referenced by llvm::ImutAVLTree< ImutInfo >::destroy(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::manualRelease(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::manualRelease(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::operator=(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::operator=(), llvm::ImmutableSet< ValT, ValInfo >::operator=(), llvm::ImmutableSetRef< ValT, ValInfo >::operator=(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::~ImmutableMap(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::~ImmutableMapRef(), llvm::ImmutableSet< ValT, ValInfo >::~ImmutableSet(), and llvm::ImmutableSetRef< ValT, ValInfo >::~ImmutableSetRef().

◆ retain()

template<typename ImutInfo >

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

inline

Definition at line 332 of file ImmutableSet.h.

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::getRoot(), llvm::ImmutableSet< ValT, ValInfo >::getRoot(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::ImmutableMap(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::ImmutableMapRef(), llvm::ImmutableSet< ValT, ValInfo >::ImmutableSet(), llvm::ImmutableSetRef< ValT, ValInfo >::ImmutableSetRef(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::manualRetain(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::manualRetain(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::operator=(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::operator=(), llvm::ImmutableSet< ValT, ValInfo >::operator=(), llvm::ImmutableSetRef< ValT, ValInfo >::operator=(), and llvm::ImutAVLTree< ImutInfo >::validateTree().

◆ size()

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

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

◆ validateTree()

template<typename ImutInfo >

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

inline

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

References assert(), llvm::FoldingSetNodeID::ComputeHash(), llvm::ImutAVLTree< ImutInfo >::getHeight(), llvm::ImutAVLTree< ImutInfo >::getLeft(), llvm::ImutAVLTree< ImutInfo >::getRight(), llvm::ImutAVLTree< ImutInfo >::getValue(), llvm::RISCVFenceField::R, llvm::ImutAVLTree< ImutInfo >::retain(), llvm::ImutAVLTree< ImutInfo >::validateTree(), and X.

Referenced by llvm::ImutAVLTree< ImutInfo >::validateTree(), llvm::ImmutableSet< ValT, ValInfo >::validateTree(), and llvm::ImmutableSetRef< ValT, ValInfo >::validateTree().

Friends And Related Function Documentation

◆ ImutAVLFactory< ImutInfo >

template<typename ImutInfo >

friend class ImutAVLFactory< ImutInfo >

friend

Definition at line 50 of file ImmutableSet.h.

◆ ImutAVLTreeGenericIterator< ImutInfo >

template<typename ImutInfo >

friend class ImutAVLTreeGenericIterator< ImutInfo >

friend

Definition at line 52 of file ImmutableSet.h.

◆ ImutIntervalAVLFactory< ImutInfo >

template<typename ImutInfo >

friend class ImutIntervalAVLFactory< ImutInfo >

friend

Definition at line 51 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

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

Member Typedef Documentation

◆ Factory

◆ iterator

◆ key_type_ref

◆ value_type

◆ value_type_ref

Member Function Documentation

◆ begin()

◆ contains()

◆ destroy()

◆ end()

◆ find()

◆ foreach()

◆ getHeight()

◆ getLeft()

◆ getMaxElement()

◆ getRight()

◆ getValue()

◆ isElementEqual() [1/2]

◆ isElementEqual() [2/2]

◆ isEqual()

◆ isNotEqual()

◆ release()

◆ retain()

◆ size()

◆ validateTree()

Friends And Related Function Documentation

◆ ImutAVLFactory< ImutInfo >

◆ ImutAVLTreeGenericIterator< ImutInfo >

◆ ImutIntervalAVLFactory< ImutInfo >

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