An immutable (persistent) ordered set backed by a reference-counted AVL tree.
Declared in <llvm/ADT/ImmutableSet.h>
template<
typename ValT,
typename ValInfo = ImutContainerInfo<ValT>,
bool Canonicalize = true>
class ImmutableSet;
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.
| Name | Description |
|---|---|
Factory | Factory for creating and updating immutable sets. |
| 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. |
| 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. |
| Name | Description |
|---|---|
Profile | Profiles S for folding-set hashing (hashes the root pointer). |
| Name | Description |
|---|---|
llvm::ImmutableSet::Factory | Factory for creating and updating immutable sets. |