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

Name

Description

Factory

Factory for creating and updating immutable sets.

Type Aliases

Name

Description

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

Name

Description

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

Name

Description

Profile

Profiles S for folding‐set hashing (hashes the root pointer).

Friends

Name

Description

llvm::ImmutableSet::Factory

Factory for creating and updating immutable sets.

Created with MrDocs