A reference‐counted node in a persistent (functional) AVL tree.

Synopsis

Declared in <llvm/ADT/ImmutableSet.h>

template<
    typename ImutInfo,
    bool Canonicalize = true>
class ImutAVLTree;

Description

Each node stores one element and optional left/right subtrees. Updates allocate new nodes along the spine while sharing unchanged subtrees. When Canonicalize is true, finished trees may be interned via the factory's digest cache.

Type Aliases

Name

Description

Factory

The factory type that allocates and updates trees of this node type.

iterator

In‐order iterator over tree nodes of this AVL tree type.

key_type_ref

A reference to a lookup key, as defined by ImutInfo.

value_type

The type of a stored element (for sets, the element itself).

value_type_ref

A reference to a stored element.

Member Functions

Name

Description

begin

Returns an iterator to the minimum node in in‐order traversal.

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.

destroy

Recursively releases child subtrees, unlinks this node from the canonicalization cache if needed, and returns the node to the factory's free list for reuse.

end

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

find

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

getHeight

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

getLeft

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

getMaxElement

Find the subtree associated with the highest ranged key value.

getRight

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

getValue

Returns the data value associated with the tree node.

isElementEqual

isElementEqual overloads

isEqual

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.

isNotEqual

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

release

Decrements the reference count; destroys the node when it reaches zero.

retain

Increments the reference count of this tree node.

size

Returns the number of nodes in the tree, including leaves and non‐leaves.

validateTree

Checks that the tree's balancing and ordering invariants hold.

Friends

Name

Description

llvm::ImutIntervalAVLFactory

Forward declaration of a factory for interval‐keyed immutable AVL trees. Declared here so it can be a friend of ImutAVLTree and access internal node APIs.

llvm::ImutAVLFactory

Factory for creating and updating persistent AVL trees.

Created with MrDocs