LLVM 23.0.0git
Public Types | Public Member Functions | Friends | List of all members
llvm::ImutAVLTree< ImutInfo > Class Template Reference

#include "llvm/ADT/ImmutableSet.h"

Inheritance diagram for llvm::ImutAVLTree< ImutInfo >:
[legend]

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.
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 ()
void destroy ()

Friends

class ImutAVLFactory< ImutInfo >
class ImutIntervalAVLFactory< ImutInfo >
class ImutAVLTreeGenericIterator< ImutInfo >

Detailed Description

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

Definition at line 46 of file ImmutableSet.h.

Member Typedef Documentation

◆ Factory

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

Definition at line 51 of file ImmutableSet.h.

◆ iterator

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

Definition at line 52 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 48 of file ImmutableSet.h.

◆ value_type

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

Definition at line 49 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 50 of file ImmutableSet.h.

Member Function Documentation

◆ begin()

template<typename ImutInfo>
iterator llvm::ImutAVLTree< ImutInfo >::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 114 of file ImmutableSet.h.

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

◆ contains()

template<typename ImutInfo>
bool llvm::ImutAVLTree< ImutInfo >::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 172 of file ImmutableSet.h.

◆ destroy()

template<typename ImutInfo>
void llvm::ImutAVLTree< ImutInfo >::destroy ( )
inline

Definition at line 327 of file ImmutableSet.h.

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

◆ end()

template<typename ImutInfo>
iterator llvm::ImutAVLTree< ImutInfo >::end ( ) const
inline

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

Definition at line 118 of file ImmutableSet.h.

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

◆ find()

template<typename ImutInfo>
ImutAVLTree * llvm::ImutAVLTree< ImutInfo >::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 78 of file ImmutableSet.h.

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

◆ getHeight()

template<typename ImutInfo>
unsigned llvm::ImutAVLTree< ImutInfo >::getHeight ( ) const
inline

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

Definition at line 71 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ValInfo >::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 64 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTreeGenericIterator< ImutInfo >::operator++(), llvm::ImutAVLTreeGenericIterator< ImutInfo >::operator--(), llvm::ImutAVLTree< ValInfo >::size(), and llvm::ImutAVLTree< ValInfo >::validateTree().

◆ getMaxElement()

template<typename ImutInfo>
ImutAVLTree * llvm::ImutAVLTree< ImutInfo >::getMaxElement ( )
inline

Find the subtree associated with the highest ranged key value.

Definition at line 93 of file ImmutableSet.h.

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

Referenced by llvm::ImutAVLTreeGenericIterator< ImutInfo >::operator++(), llvm::ImutAVLTreeGenericIterator< ImutInfo >::operator--(), llvm::ImutAVLTree< ValInfo >::size(), and llvm::ImutAVLTree< ValInfo >::validateTree().

◆ getValue()

template<typename ImutInfo>
const value_type & llvm::ImutAVLTree< ImutInfo >::getValue ( ) const
inline

Returns the data value associated with the tree node.

Definition at line 74 of file ImmutableSet.h.

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

◆ isElementEqual() [1/2]

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

Definition at line 134 of file ImmutableSet.h.

◆ isElementEqual() [2/2]

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

Definition at line 120 of file ImmutableSet.h.

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

◆ isEqual()

template<typename ImutInfo>
bool llvm::ImutAVLTree< ImutInfo >::isEqual ( const ImutAVLTree< ImutInfo > & 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 141 of file ImmutableSet.h.

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

◆ isNotEqual()

template<typename ImutInfo>
bool llvm::ImutAVLTree< ImutInfo >::isNotEqual ( const ImutAVLTree< ImutInfo > & RHS) const
inline

Compares two trees for structural inequality.

Performance is the same as isEqual.

Definition at line 167 of file ImmutableSet.h.

◆ release()

template<typename ImutInfo>
void llvm::ImutAVLTree< ImutInfo >::release ( )
inline

Definition at line 321 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo >::ImutAVLTree< ImutInfo >.

◆ retain()

template<typename ImutInfo>
void llvm::ImutAVLTree< ImutInfo >::retain ( )
inline

Definition at line 319 of file ImmutableSet.h.

Referenced by llvm::IntrusiveRefCntPtrInfo< ImutAVLTree< ImutInfo > >::retain().

◆ size()

template<typename ImutInfo>
unsigned llvm::ImutAVLTree< ImutInfo >::size ( ) const
inline

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

Definition at line 102 of file ImmutableSet.h.

◆ validateTree()

template<typename ImutInfo>
unsigned llvm::ImutAVLTree< ImutInfo >::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 179 of file ImmutableSet.h.

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

◆ ImutAVLFactory< ImutInfo >

template<typename ImutInfo>
friend class ImutAVLFactory< ImutInfo >
friend

Definition at line 1 of file ImmutableSet.h.

◆ ImutAVLTreeGenericIterator< ImutInfo >

template<typename ImutInfo>
friend class ImutAVLTreeGenericIterator< ImutInfo >
friend

Definition at line 1 of file ImmutableSet.h.

◆ ImutIntervalAVLFactory< ImutInfo >

template<typename ImutInfo>
friend class ImutIntervalAVLFactory< ImutInfo >
friend

Definition at line 1 of file ImmutableSet.h.

The documentation for this class was generated from the following file:
Generated on for LLVM by doxygen 1.14.0