14#ifndef LLVM_ADT_IMMUTABLESET_H
15#define LLVM_ADT_IMMUTABLESET_H
43template <
typename ImutInfo >
80 key_type_ref CurrentKey = ImutInfo::KeyOfValue(
T->getValue());
81 if (ImutInfo::isEqual(K,CurrentKey))
83 else if (ImutInfo::isLess(K,CurrentKey))
122 if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(
getValue()),
123 ImutInfo::KeyOfValue(V)))
127 if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(
getValue()),
128 ImutInfo::DataOfValue(V)))
148 while (LItr != LEnd && RItr != REnd) {
149 if (&*LItr == &*RItr) {
162 return LItr == LEnd && RItr == REnd;
187 &&
"Height calculation wrong");
189 assert((HL > HR ? HL-HR : HR-HL) <= 2
190 &&
"Balancing invariant violated");
194 ImutInfo::KeyOfValue(
getValue()))) &&
195 "Value in left child is not less that current value");
198 ImutInfo::isLess(ImutInfo::KeyOfValue(
getValue()),
200 "Current value is not less that value of right child");
216 unsigned height : 28;
218 unsigned IsMutable : 1;
220 unsigned IsDigestCached : 1;
222 unsigned IsCanonicalized : 1;
237 : factory(f), left(l), right(r), height(height), IsMutable(
true),
241 if (right) right->
retain();
250 bool isMutable()
const {
return IsMutable; }
254 bool hasCachedDigest()
const {
return IsDigestCached; }
269 void markImmutable() {
270 assert(isMutable() &&
"Mutable flag already removed.");
275 void markedCachedDigest() {
276 assert(!hasCachedDigest() &&
"NoCachedDigest flag already removed.");
277 IsDigestCached =
true;
282 void setHeight(
unsigned h) {
283 assert(isMutable() &&
"Only a mutable tree can have its height changed.");
287 static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
292 digest +=
L->computeDigest();
296 ImutInfo::Profile(
ID,V);
297 digest +=
ID.ComputeHash();
300 digest +=
R->computeDigest();
308 if (hasCachedDigest())
313 markedCachedDigest();
335 if (IsCanonicalized) {
342 factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
348 factory->freeNodes.push_back(
this);
352template <
typename ImutInfo>
362template <
typename ImutInfo >
373 std::vector<TreeTy*> createdNodes;
374 std::vector<TreeTy*> freeNodes;
376 bool ownsAllocator()
const {
396 if (ownsAllocator())
delete &getAllocator();
435 return (hl > hr ? hl : hr) + 1;
442 for ( ;
I!=
E ; ++
I, ++TI) {
443 if (TI == TE || !
I->isElementEqual(&*TI))
462 if (!freeNodes.empty()) {
463 T = freeNodes.back();
464 freeNodes.pop_back();
471 createdNodes.push_back(
T);
480 for (
unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
482 if (
N->isMutable() &&
N->refCount == 0)
485 createdNodes.clear();
495 assert(!
isEmpty(L) &&
"Left tree cannot be empty to have a height >= 2");
503 assert(!
isEmpty(LR) &&
"LR cannot be empty because it has a height >= 1");
512 assert(!
isEmpty(R) &&
"Right tree cannot be empty to have a height >= 2");
520 assert(!
isEmpty(RL) &&
"RL cannot be empty because it has a height >= 1");
539 key_type_ref K = ImutInfo::KeyOfValue(V);
540 key_type_ref KCurrent = ImutInfo::KeyOfValue(
getValue(
T));
542 if (ImutInfo::isEqual(K,KCurrent))
544 else if (ImutInfo::isLess(K,KCurrent))
560 key_type_ref KCurrent = ImutInfo::KeyOfValue(
getValue(
T));
562 if (ImutInfo::isEqual(K,KCurrent)) {
564 }
else if (ImutInfo::isLess(K,KCurrent)) {
596 if (!
T || !
T->isMutable())
608 if (TNew->IsCanonicalized)
613 unsigned digest = TNew->computeDigest();
618 for (
TreeTy *
T = entry ;
T !=
nullptr;
T =
T->next) {
626 if (TNew->refCount == 0)
636 TNew->IsCanonicalized =
true;
662 if (Root) stack.
push_back(
reinterpret_cast<uintptr_t
>(Root));
667 return *
reinterpret_cast<TreeTy *
>(stack.
back() & ~Flags);
700 return stack == x.stack;
704 return !(*
this == x);
714 stack.
push_back(
reinterpret_cast<uintptr_t
>(L));
720 stack.
push_back(
reinterpret_cast<uintptr_t
>(R));
742 stack.
back() &= ~Flags;
747 stack.
back() &= ~Flags;
762 InternalIteratorTy InternalItr;
781 return InternalItr == x.InternalItr;
785 return !(*
this == x);
793 while (!InternalItr.atEnd() &&
794 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
801 while (!InternalItr.atBeginning() &&
802 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
808 InternalItr.skipToParent();
810 while (!InternalItr.atEnd() &&
811 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
821 ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
822 typename std::iterator_traits<
823 typename T::TreeTy::iterator>::iterator_category,
824 const typename T::value_type> {
830 return this->
I->getValue();
862#define PROFILE_INTEGER_INFO(X)\
863template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
876#undef PROFILE_INTEGER_INFO
924 return std::equal_to<key_type>()(
LHS,
RHS);
928 return std::less<key_type>()(
LHS,
RHS);
960template <
typename ValT,
typename ValInfo = ImutContainerInfo<ValT>>
979 const bool Canonicalize;
983 : Canonicalize(canonicalize) {}
986 :
F(
Alloc), Canonicalize(canonicalize) {}
1004 TreeTy *NewT =
F.add(Old.Root.get(), V);
1005 return ImmutableSet(Canonicalize ?
F.getCanonicalTree(NewT) : NewT);
1016 TreeTy *NewT =
F.remove(Old.Root.get(), V);
1017 return ImmutableSet(Canonicalize ?
F.getCanonicalTree(NewT) : NewT);
1031 return Root ? Root->contains(V) :
false;
1035 return Root &&
RHS.Root ? Root->isEqual(*
RHS.Root.get()) : Root ==
RHS.Root;
1039 return Root &&
RHS.Root ? Root->isNotEqual(*
RHS.Root.get())
1044 if (Root) { Root->retain(); }
1070 unsigned getHeight()
const {
return Root ? Root->getHeight() : 0; }
1073 ID.AddPointer(S.Root.get());
1086template <
typename ValT,
typename ValInfo = ImutContainerInfo<ValT>>
1119 return Root ? Root->contains(V) :
false;
1124 canonicalize ? Factory->getCanonicalTree(Root.
get()) : Root.
get());
1130 return Root &&
RHS.Root ? Root->isEqual(*
RHS.Root.get()) : Root ==
RHS.Root;
1134 return Root &&
RHS.Root ? Root->isNotEqual(*
RHS.Root.get())
1158 unsigned getHeight()
const {
return Root ? Root->getHeight() : 0; }
1161 ID.AddPointer(S.Root.get());
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_PREFERRED_TYPE(T)
\macro LLVM_PREFERRED_TYPE Adjust type of bit-field in debug info.
Given that RA is a live value
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file defines a hash set that can be used to remove duplication of nodes in a graph.
#define PROFILE_INTEGER_INFO(X)
This file defines the RefCountedBase, ThreadSafeRefCountedBase, and IntrusiveRefCntPtr classes.
This file defines the SmallVector class.
Allocate memory in an ever growing pool, as if by bump-pointer.
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
static void Profile(FoldingSetNodeID &ID, const ImmutableSetRef &S)
void Profile(FoldingSetNodeID &ID) const
ImmutableSetRef add(value_type_ref V)
bool contains(value_type_ref V) const
Returns true if the set contains the specified value.
bool operator!=(const ImmutableSetRef &RHS) const
ImmutableSetRef remove(value_type_ref V)
ImutAVLValueIterator< ImmutableSetRef > iterator
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
bool isEmpty() const
isEmpty - Return true if the set contains no elements.
typename ValInfo::value_type value_type
ImmutableSetRef(TreeTy *R, FactoryTy *F)
Constructs a set from a pointer to a tree root.
typename ValInfo::value_type_ref value_type_ref
unsigned getHeight() const
ImmutableSet< ValT > asImmutableSet(bool canonicalize=true) const
typename TreeTy::Factory FactoryTy
static ImmutableSetRef getEmptySet(FactoryTy *F)
void validateTree() const
bool operator==(const ImmutableSetRef &RHS) const
TreeTy * getRootWithoutRetain() const
Factory(const Factory &RHS)=delete
void operator=(const Factory &RHS)=delete
TreeTy::Factory * getTreeFactory() const
BumpPtrAllocator & getAllocator()
Factory(BumpPtrAllocator &Alloc, bool canonicalize=true)
ImmutableSet getEmptySet()
getEmptySet - Returns an immutable set that contains no elements.
Factory(bool canonicalize=true)
ImmutableSet remove(ImmutableSet Old, value_type_ref V)
remove - Creates a new immutable set that contains all of the values of the original set with the exc...
ImmutableSet add(ImmutableSet Old, value_type_ref V)
add - Creates a new immutable set that contains all of the values of the original set with the additi...
bool operator!=(const ImmutableSet &RHS) const
typename ValInfo::value_type value_type
bool operator==(const ImmutableSet &RHS) const
bool isEmpty() const
isEmpty - Return true if the set contains no elements.
ImmutableSet(TreeTy *R)
Constructs a set from a pointer to a tree root.
bool isSingleton() const
isSingleton - Return true if the set contains exactly one element.
TreeTy * getRootWithoutRetain() const
void validateTree() const
bool contains(value_type_ref V) const
Returns true if the set contains the specified value.
void Profile(FoldingSetNodeID &ID) const
unsigned getHeight() const
static void Profile(FoldingSetNodeID &ID, const ImmutableSet &S)
ImutAVLValueIterator< ImmutableSet > iterator
typename ValInfo::value_type_ref value_type_ref
static unsigned maskCacheIndex(unsigned I)
TreeTy * balanceTree(TreeTy *L, value_type_ref V, TreeTy *R)
balanceTree - Used by add_internal and remove_internal to balance a newly created tree.
unsigned getHeight(TreeTy *T) const
ImutAVLFactory(BumpPtrAllocator &Alloc)
TreeTy * add_internal(value_type_ref V, TreeTy *T)
add_internal - Creates a new tree that includes the specified data and the data from the original tre...
value_type_ref getValue(TreeTy *T) const
static bool compareTreeWithSection(TreeTy *T, typename TreeTy::iterator &TI, typename TreeTy::iterator &TE)
TreeTy * getLeft(TreeTy *T) const
TreeTy * getCanonicalTree(TreeTy *TNew)
TreeTy * add(TreeTy *T, value_type_ref V)
TreeTy * getRight(TreeTy *T) const
TreeTy * getEmptyTree() const
TreeTy * removeMinBinding(TreeTy *T, TreeTy *&Noderemoved)
TreeTy * createNode(TreeTy *newLeft, TreeTy *oldTree, TreeTy *newRight)
TreeTy * combineTrees(TreeTy *L, TreeTy *R)
TreeTy * remove_internal(key_type_ref K, TreeTy *T)
remove_internal - Creates a new tree that includes all the data from the original tree except the spe...
TreeTy * createNode(TreeTy *L, value_type_ref V, TreeTy *R)
unsigned incrementHeight(TreeTy *L, TreeTy *R) const
TreeTy * remove(TreeTy *T, key_type_ref V)
void markImmutable(TreeTy *T)
markImmutable - Clears the mutable bits of a root and all of its descendants.
bool isEmpty(TreeTy *T) const
ImutAVLTreeGenericIterator()=default
std::ptrdiff_t difference_type
bool operator==(const ImutAVLTreeGenericIterator &x) const
std::bidirectional_iterator_tag iterator_category
ImutAVLTreeGenericIterator(const TreeTy *Root)
ImutAVLTreeGenericIterator & operator--()
TreeTy & operator*() const
TreeTy * operator->() const
uintptr_t getVisitState() const
bool operator!=(const ImutAVLTreeGenericIterator &x) const
ImutAVLTreeGenericIterator & operator++()
bool operator!=(const ImutAVLTreeInOrderIterator &x) const
TreeTy * operator->() const
ImutAVLTreeInOrderIterator & operator++()
ImutAVLTreeInOrderIterator & operator--()
std::bidirectional_iterator_tag iterator_category
ImutAVLTreeInOrderIterator()
TreeTy & operator*() const
ImutAVLTreeInOrderIterator(const TreeTy *Root)
bool operator==(const ImutAVLTreeInOrderIterator &x) const
std::ptrdiff_t difference_type
unsigned size() const
size - Returns the number of nodes in the tree, which includes both leaves and non-leaf nodes.
iterator end() const
end - Returns an iterator for the tree that denotes the end of an inorder traversal.
const value_type & getValue() const
getValue - Returns the data value associated with the tree node.
unsigned getHeight() const
getHeight - Returns the height of the tree.
typename ImutInfo::key_type_ref key_type_ref
ImutAVLFactory< ImutInfo > Factory
ImutAVLTree * find(key_type_ref K)
find - Finds the subtree associated with the specified key value.
typename ImutInfo::value_type_ref value_type_ref
unsigned validateTree() const
validateTree - A utility method that checks that the balancing and ordering invariants of the tree ar...
bool isNotEqual(const ImutAVLTree &RHS) const
isNotEqual - Compares two trees for structural inequality.
bool isEqual(const ImutAVLTree &RHS) const
isEqual - Compares two trees for structural equality and returns true if they are equal.
ImutAVLTree * getLeft() const
Return a pointer to the left subtree.
ImutAVLTreeInOrderIterator< ImutInfo > iterator
typename ImutInfo::value_type value_type
ImutAVLTree * getRight() const
Return a pointer to the right subtree.
bool isElementEqual(const ImutAVLTree *RHS) const
bool contains(key_type_ref K)
contains - Returns true if this tree contains a subtree (node) that has an data element that matches ...
ImutAVLTree * getMaxElement()
getMaxElement - Find the subtree associated with the highest ranged key value.
iterator begin() const
begin - Returns an iterator that iterates over the nodes of the tree in an inorder traversal.
bool isElementEqual(value_type_ref V) const
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
CRTP base class for adapting an iterator to a different type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
This is an optimization pass for GlobalISel generic memory operations.
static void Profile(const T &X, FoldingSetNodeID &ID)
Generic iterator that wraps a T::TreeTy::iterator and exposes iterator::getValue() on dereference.
ImutAVLValueIterator()=default
ImutAVLValueIterator::reference operator*() const
ImutAVLValueIterator(typename T::TreeTy *Tree)
static bool isDataEqual(data_type_ref, data_type_ref)
value_type_ref key_type_ref
static key_type_ref KeyOfValue(value_type_ref D)
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
typename ImutProfileInfo< T * >::value_type_ref value_type_ref
typename ImutProfileInfo< T * >::value_type value_type
static data_type_ref DataOfValue(value_type_ref)
static bool isLess(key_type_ref LHS, key_type_ref RHS)
ImutContainerInfo - Generic definition of comparison operations for elements of immutable containers ...
static bool isLess(key_type_ref LHS, key_type_ref RHS)
typename ImutProfileInfo< T >::value_type value_type
static bool isEqual(key_type_ref LHS, key_type_ref RHS)
static bool isDataEqual(data_type_ref, data_type_ref)
static data_type_ref DataOfValue(value_type_ref)
static key_type_ref KeyOfValue(value_type_ref D)
value_type_ref key_type_ref
typename ImutProfileInfo< T >::value_type_ref value_type_ref
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Generic profile template.
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
Profile traits for integers.
static void Profile(FoldingSetNodeID &ID, value_type_ref X)
static void retain(ImutAVLTree< ImutInfo > *Tree)
Class you can specialize to provide custom retain/release functionality for a type.