14#ifndef LLVM_ADT_IMMUTABLESET_H
15#define LLVM_ADT_IMMUTABLESET_H
42template <
typename ImutInfo >
79 key_type_ref CurrentKey = ImutInfo::KeyOfValue(
T->getValue());
80 if (ImutInfo::isEqual(K,CurrentKey))
82 else if (ImutInfo::isLess(K,CurrentKey))
121 if (!ImutInfo::isEqual(ImutInfo::KeyOfValue(
getValue()),
122 ImutInfo::KeyOfValue(V)))
126 if (!ImutInfo::isDataEqual(ImutInfo::DataOfValue(
getValue()),
127 ImutInfo::DataOfValue(V)))
147 while (LItr != LEnd && RItr != REnd) {
148 if (&*LItr == &*RItr) {
161 return LItr == LEnd && RItr == REnd;
186 &&
"Height calculation wrong");
188 assert((HL > HR ? HL-HR : HR-HL) <= 2
189 &&
"Balancing invariant violated");
193 ImutInfo::KeyOfValue(
getValue()))) &&
194 "Value in left child is not less that current value");
197 ImutInfo::isLess(ImutInfo::KeyOfValue(
getValue()),
199 "Current value is not less that value of right child");
215 unsigned height : 28;
217 bool IsDigestCached : 1;
218 bool IsCanonicalized : 1;
233 : factory(f), left(l), right(r), height(height), IsMutable(
true),
237 if (right) right->
retain();
246 bool isMutable()
const {
return IsMutable; }
250 bool hasCachedDigest()
const {
return IsDigestCached; }
265 void markImmutable() {
266 assert(isMutable() &&
"Mutable flag already removed.");
271 void markedCachedDigest() {
272 assert(!hasCachedDigest() &&
"NoCachedDigest flag already removed.");
273 IsDigestCached =
true;
278 void setHeight(
unsigned h) {
279 assert(isMutable() &&
"Only a mutable tree can have its height changed.");
283 static uint32_t computeDigest(ImutAVLTree *L, ImutAVLTree *R,
288 digest +=
L->computeDigest();
292 ImutInfo::Profile(
ID,V);
293 digest +=
ID.ComputeHash();
296 digest +=
R->computeDigest();
304 if (hasCachedDigest())
309 markedCachedDigest();
331 if (IsCanonicalized) {
338 factory->Cache[factory->maskCacheIndex(computeDigest())] = next;
344 factory->freeNodes.push_back(
this);
348template <
typename ImutInfo>
358template <
typename ImutInfo >
369 std::vector<TreeTy*> createdNodes;
370 std::vector<TreeTy*> freeNodes;
372 bool ownsAllocator()
const {
392 if (ownsAllocator())
delete &getAllocator();
431 return (hl > hr ? hl : hr) + 1;
438 for ( ;
I!=
E ; ++
I, ++TI) {
439 if (TI == TE || !
I->isElementEqual(&*TI))
458 if (!freeNodes.empty()) {
459 T = freeNodes.back();
460 freeNodes.pop_back();
467 createdNodes.push_back(
T);
476 for (
unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
478 if (
N->isMutable() &&
N->refCount == 0)
481 createdNodes.clear();
491 assert(!
isEmpty(L) &&
"Left tree cannot be empty to have a height >= 2");
499 assert(!
isEmpty(LR) &&
"LR cannot be empty because it has a height >= 1");
508 assert(!
isEmpty(R) &&
"Right tree cannot be empty to have a height >= 2");
516 assert(!
isEmpty(RL) &&
"RL cannot be empty because it has a height >= 1");
535 key_type_ref K = ImutInfo::KeyOfValue(V);
536 key_type_ref KCurrent = ImutInfo::KeyOfValue(
getValue(
T));
538 if (ImutInfo::isEqual(K,KCurrent))
540 else if (ImutInfo::isLess(K,KCurrent))
556 key_type_ref KCurrent = ImutInfo::KeyOfValue(
getValue(
T));
558 if (ImutInfo::isEqual(K,KCurrent)) {
560 }
else if (ImutInfo::isLess(K,KCurrent)) {
592 if (!
T || !
T->isMutable())
604 if (TNew->IsCanonicalized)
609 unsigned digest = TNew->computeDigest();
614 for (
TreeTy *
T = entry ;
T !=
nullptr;
T =
T->next) {
622 if (TNew->refCount == 0)
632 TNew->IsCanonicalized =
true;
658 if (Root) stack.
push_back(
reinterpret_cast<uintptr_t
>(Root));
663 return *
reinterpret_cast<TreeTy *
>(stack.
back() & ~Flags);
696 return stack == x.stack;
700 return !(*
this == x);
710 stack.
push_back(
reinterpret_cast<uintptr_t
>(L));
716 stack.
push_back(
reinterpret_cast<uintptr_t
>(R));
738 stack.
back() &= ~Flags;
743 stack.
back() &= ~Flags;
758 InternalIteratorTy InternalItr;
777 return InternalItr == x.InternalItr;
781 return !(*
this == x);
789 while (!InternalItr.atEnd() &&
790 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
797 while (!InternalItr.atBeginning() &&
798 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
804 InternalItr.skipToParent();
806 while (!InternalItr.atEnd() &&
807 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
817 ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
818 typename std::iterator_traits<
819 typename T::TreeTy::iterator>::iterator_category,
820 const typename T::value_type> {
826 return this->
I->getValue();
858#define PROFILE_INTEGER_INFO(X)\
859template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
872#undef PROFILE_INTEGER_INFO
920 return std::equal_to<key_type>()(
LHS,
RHS);
924 return std::less<key_type>()(
LHS,
RHS);
956template <
typename ValT,
typename ValInfo = ImutContainerInfo<ValT>>
975 const bool Canonicalize;
979 : Canonicalize(canonicalize) {}
982 :
F(
Alloc), Canonicalize(canonicalize) {}
1000 TreeTy *NewT =
F.add(Old.Root.get(), V);
1001 return ImmutableSet(Canonicalize ?
F.getCanonicalTree(NewT) : NewT);
1012 TreeTy *NewT =
F.remove(Old.Root.get(), V);
1013 return ImmutableSet(Canonicalize ?
F.getCanonicalTree(NewT) : NewT);
1027 return Root ? Root->contains(V) :
false;
1031 return Root &&
RHS.Root ? Root->isEqual(*
RHS.Root.get()) : Root ==
RHS.Root;
1035 return Root &&
RHS.Root ? Root->isNotEqual(*
RHS.Root.get())
1040 if (Root) { Root->retain(); }
1066 unsigned getHeight()
const {
return Root ? Root->getHeight() : 0; }
1069 ID.AddPointer(S.Root.get());
1082template <
typename ValT,
typename ValInfo = ImutContainerInfo<ValT>>
1115 return Root ? Root->contains(V) :
false;
1120 canonicalize ? Factory->getCanonicalTree(Root.
get()) : Root.
get());
1126 return Root &&
RHS.Root ? Root->isEqual(*
RHS.Root.get()) : Root ==
RHS.Root;
1130 return Root &&
RHS.Root ? Root->isNotEqual(*
RHS.Root.get())
1154 unsigned getHeight()
const {
return Root ? Root->getHeight() : 0; }
1157 ID.AddPointer(S.Root.get());
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")
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.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.