class ImutAVLTree

Declaration

template <typename ImutInfo>
class ImutAVLTree { /* full declaration omitted */ };

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:41

Templates

ImutInfo

Method Overview

  • public llvm::ImutAVLTree::iterator begin() const
  • public bool contains(llvm::ImutAVLTree::key_type_ref K)
  • public void destroy()
  • public llvm::ImutAVLTree::iterator end() const
  • public ImutAVLTree<ImutInfo> * find(llvm::ImutAVLTree::key_type_ref K)
  • public template <typename Callback>void foreach(Callback & C)
  • public unsigned int getHeight() const
  • public ImutAVLTree<ImutInfo> * getLeft() const
  • public ImutAVLTree<ImutInfo> * getMaxElement()
  • public ImutAVLTree<ImutInfo> * getRight() const
  • public const llvm::ImutAVLTree::value_type & getValue() const
  • public bool isElementEqual(const ImutAVLTree<ImutInfo> * RHS) const
  • public bool isElementEqual(llvm::ImutAVLTree::value_type_ref V) const
  • public bool isEqual(const ImutAVLTree<ImutInfo> & RHS) const
  • public bool isNotEqual(const ImutAVLTree<ImutInfo> & RHS) const
  • public void release()
  • public void retain()
  • public unsigned int size() const
  • public unsigned int validateTree() const

Methods

llvm::ImutAVLTree::iterator begin() const

Description

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.

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:111

bool contains(llvm::ImutAVLTree::key_type_ref K)

Description

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.

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:169

Parameters

llvm::ImutAVLTree::key_type_ref K

void destroy()

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:338

llvm::ImutAVLTree::iterator end() const

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:115

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

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:74

Parameters

llvm::ImutAVLTree::key_type_ref K

template <typename Callback>
void foreach (Callback& C)

Description

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.

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:175

Templates

Callback

Parameters

Callback& C

unsigned int getHeight() const

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:67

ImutAVLTree<ImutInfo>* getLeft() const

Description

Return a pointer to the left subtree. This value is NULL if there is no left subtree.

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:59

ImutAVLTree<ImutInfo>* getMaxElement()

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:90

ImutAVLTree<ImutInfo>* getRight() const

Description

Return a pointer to the right subtree. This value is NULL if there is no right subtree.

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:63

const llvm::ImutAVLTree::value_type& getValue()
    const

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:70

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:131

Parameters

const ImutAVLTree<ImutInfo>* RHS

bool isElementEqual(
    llvm::ImutAVLTree::value_type_ref V) const

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:117

Parameters

llvm::ImutAVLTree::value_type_ref V

bool isEqual(
    const ImutAVLTree<ImutInfo>& RHS) const

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:138

Parameters

const ImutAVLTree<ImutInfo>& RHS

bool isNotEqual(
    const ImutAVLTree<ImutInfo>& RHS) const

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:164

Parameters

const ImutAVLTree<ImutInfo>& RHS

void release()

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:332

void retain()

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:330

unsigned int size() const

Description

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

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:99

unsigned int validateTree() const

Description

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.

Declared at: llvm/include/llvm/ADT/ImmutableSet.h:191