llvm::ImutAVLFactory

Synopsis

Declared in <llvm/ADT/ImmutableSet.h>

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

Description

Allocates nodes from a bump-pointer allocator, reclaims discarded intermediates after each operation, and optionally canonicalizes structurally equal trees.

Member Functions

Name	Description
`ImutAVLFactory` [constructor]	Constructors
`~ImutAVLFactory` [destructor]	Destroys the factory and, if it owns the allocator, frees all allocated memory.
`add`	Returns a new tree containing all elements of `T` plus `V.`
`getCanonicalTree`	Returns a canonical representative for `TNew,` reusing an existing tree with the same structure and contents when one is found in the cache.
`getEmptyTree`	Returns the canonical empty-tree representation (null).
`mergeTrees`	Merges `A` and `B` in a single traversal, sharing non-overlapping subtrees.
`remove`	Returns a new tree containing all elements of `T` except the one with key `V.`
`unionTrees`	Returns the set union of `A` and `B` (keeping `A's` element on matching keys). Shorthand for the fully sharing `mergeTrees`.

Protected Member Functions

Name	Description
`add_internal`	Creates a new tree that includes `V` and the data from `T.`
`balanceTree`	Used by add_internal and remove_internal to balance a newly created tree.
`combineTrees`	Joins two trees after removing a root node: the maximum of `R` becomes the new root, with `L` as the left subtree.
`createNode`	`createNode` overloads
`getHeight`	Return the height of `T,` or 0 if `T` is null.
`getLeft`	Returns the left subtree of `T,` or nullptr if `T` is empty.
`getRight`	Returns the right subtree of `T,` or nullptr if `T` is empty.
`getValue`	Return the element stored at tree node `T.`
`incrementHeight`	Returns one plus the greater subtree height of `L` and `R.`
`isEmpty`	Returns true if `T` is the empty tree (null).
`joinTrees`	Combines `L,` value `V,` and `R` into one balanced tree.
`merge_internal`	Merges `A` and `B` by splitting `B` at each of `A's` keys.
`recoverNodes`	Mark `Result's` nodes immutable and destroy discarded balancing nodes.
`removeMinBinding`	Removes and returns the minimum node of `T,` storing it in `Noderemoved` and returning the remaining tree.
`remove_internal`	Creates a new tree with all data from `T` except key `K.`
`splitLookup`	Splits `T` around key `K` into lesser and greater trees.
`transformTree`	Rebuilds `T` with each element replaced by `Combine.`

Protected Static Member Functions

Name	Description
`maskCacheIndex`	Clears the low bits of `I` so the digest is never a DenseMap tombstone or empty key.

Friends

Name	Description
`llvm::ImutAVLTree`	A reference-counted node in a persistent (functional) AVL tree.