class ImutAVLTree

Declaration

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

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

Templates

ImutInfo

Member Variables

private llvm::ImutAVLTree::Factory* factory
private ImutAVLTree<ImutInfo>* left
private ImutAVLTree<ImutInfo>* right
private ImutAVLTree<ImutInfo>* prev = nullptr
private ImutAVLTree<ImutInfo>* next = nullptr
private unsigned int height
private bool IsMutable
private bool IsDigestCached
private bool IsCanonicalized
private llvm::ImutAVLTree::value_type value
private uint32_t digest = 0
private uint32_t refCount = 0

Method Overview

  • private ImutAVLTree<ImutInfo>(llvm::ImutAVLTree::Factory * f, ImutAVLTree<ImutInfo> * l, ImutAVLTree<ImutInfo> * r, llvm::ImutAVLTree::value_type_ref v, unsigned int height)
  • public llvm::ImutAVLTree::iterator begin() const
  • private uint32_t computeDigest()
  • private static uint32_t computeDigest(ImutAVLTree<ImutInfo> * L, ImutAVLTree<ImutInfo> * R, llvm::ImutAVLTree::value_type_ref V)
  • 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 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
  • private bool hasCachedDigest() 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
  • private bool isMutable() const
  • public bool isNotEqual(const ImutAVLTree<ImutInfo> & RHS) const
  • private void markImmutable()
  • private void markedCachedDigest()
  • public void release()
  • public void retain()
  • private void setHeight(unsigned int h)
  • public unsigned int size() const
  • public unsigned int validateTree() const

Methods

ImutAVLTree<ImutInfo>(
    llvm::ImutAVLTree::Factory* f,
    ImutAVLTree<ImutInfo>* l,
    ImutAVLTree<ImutInfo>* r,
    llvm::ImutAVLTree::value_type_ref v,
    unsigned int height)

Description

ImutAVLTree - Internal constructor that is only called by ImutAVLFactory.

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

Parameters

llvm::ImutAVLTree::Factory* f
ImutAVLTree<ImutInfo>* l
ImutAVLTree<ImutInfo>* r
llvm::ImutAVLTree::value_type_ref v
unsigned int height

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:113

uint32_t computeDigest()

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

static uint32_t computeDigest(
    ImutAVLTree<ImutInfo>* L,
    ImutAVLTree<ImutInfo>* R,
    llvm::ImutAVLTree::value_type_ref V)

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

Parameters

ImutAVLTree<ImutInfo>* L
ImutAVLTree<ImutInfo>* R
llvm::ImutAVLTree::value_type_ref V

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:171

Parameters

llvm::ImutAVLTree::key_type_ref K

void destroy()

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

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:117

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:76

Parameters

llvm::ImutAVLTree::key_type_ref K

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:69

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:61

ImutAVLTree<ImutInfo>* getMaxElement()

Description

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

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

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:65

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:72

bool hasCachedDigest() const

Description

hasCachedDigest - Returns true if the digest for this tree is cached. This can only be true if the tree is immutable.

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

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

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

Parameters

const ImutAVLTree<ImutInfo>* RHS

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

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

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:140

Parameters

const ImutAVLTree<ImutInfo>& RHS

bool isMutable() const

Description

isMutable - Returns true if the left and right subtree references (as well as height) can be changed. If this method returns false, the tree is truly immutable. Trees returned from an ImutAVLFactory object should always have this method return true. Further, if this method returns false for an instance of ImutAVLTree, all subtrees will also have this method return false. The converse is not true.

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

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:166

Parameters

const ImutAVLTree<ImutInfo>& RHS

void markImmutable()

Description

markImmutable - Clears the mutable flag for a tree. After this happens, it is an error to call setLeft(), setRight(), and setHeight().

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

void markedCachedDigest()

Description

markedCachedDigest - Clears the NoCachedDigest flag for a tree.

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

void release()

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

void retain()

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

void setHeight(unsigned int h)

Description

setHeight - Changes the height of the tree. Used internally by ImutAVLFactory.

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

Parameters

unsigned int h

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:101

unsigned int validateTree() const

Description

validateTree - 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.

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