llvm::ImmutableSet

An immutable (persistent) ordered set backed by a reference-counted AVL tree.

Synopsis

Declared in <llvm/ADT/ImmutableSet.h>

template<
    typename ValT,
    typename ValInfo = ImutContainerInfo<ValT>,
    bool Canonicalize = true>
class ImmutableSet;

Description

Copying an ImmutableSet is cheap: it shares the underlying tree nodes. Updates go through Factory and return a new set while leaving the old one unchanged. When Canonicalize is true, structurally equal sets from the same factory share the same root pointer.

Types

NameDescription
Factory Factory for creating and updating immutable sets.

Type Aliases

NameDescription
TreeTy The underlying AVL tree node type.
iterator Iterator over set elements in ascending key order.
value_type The type of a stored set element.
value_type_ref A reference to a stored set element.

Member Functions

NameDescription
ImmutableSet [constructor]Construct from tree root R.
Profile Profiles this set for folding-set hashing.
begin Returns an iterator to the first element in in-order traversal.
contains Returns true if the set contains the specified value.
end Returns the past-the-end iterator for in-order traversal.
getHeight Returns the height of the AVL tree (0 if empty).
getRoot Returns the tree root with an extra retain for the caller.
getRootWithoutRetain Returns the tree root without changing its reference count.
isEmpty Return true if the set contains no elements.
isSingleton Return true if the set contains exactly one element. This method runs in constant time.
validateTree Checks that the AVL balancing and ordering invariants hold for this set.
operator== Returns true if this set and RHS have equal contents.
operator!= Compares two sets for inequality. For a canonicalizing factory this is an O(1) pointer comparison; otherwise it is a structural comparison.

Static Member Functions

NameDescription
Profile Profiles S for folding-set hashing (hashes the root pointer).

Friends

NameDescription
llvm::ImmutableSet::FactoryFactory for creating and updating immutable sets.