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)
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
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()
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)
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)
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()
void destroy()
Declared at: llvm/include/llvm/ADT/ImmutableSet.h:326
¶llvm::ImutAVLTree::iterator end() const
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)
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
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
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()
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
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
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
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
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
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
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
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
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()
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()
void markedCachedDigest()
Description
markedCachedDigest - Clears the NoCachedDigest flag for a tree.
Declared at: llvm/include/llvm/ADT/ImmutableSet.h:271
¶void release()
void release()
Declared at: llvm/include/llvm/ADT/ImmutableSet.h:320
¶void retain()
void retain()
Declared at: llvm/include/llvm/ADT/ImmutableSet.h:318
¶void setHeight(unsigned int h)
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
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
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