14#ifndef LLVM_ADT_IMMUTABLESET_H
15#define LLVM_ADT_IMMUTABLESET_H
43template <
typename ImutInfo >
62 ImutAVLTree *
getLeft()
const {
return left; }
66 ImutAVLTree *
getRight()
const {
return right; }
78 ImutAVLTree *
T =
this;
80 key_type_ref CurrentKey = ImutInfo::KeyOfValue(
T->getValue());
81 if (ImutInfo::isEqual(K,CurrentKey))
83 else if (ImutInfo::isLess(K,CurrentKey))
94 ImutAVLTree *
T =
this;
95 ImutAVLTree *
Right =
T->getRight();
104 if (
const ImutAVLTree* L =
getLeft())
106 if (
const ImutAVLTree* R =
getRight())
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),
238 IsDigestCached(
false), IsCanonicalized(
false), value(v)
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();
305 uint32_t 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 {
377 return (Allocator & 0x1) == 0;
393 : Allocator(reinterpret_cast<uintptr_t>(&
Alloc) | 0x1) {}
396 if (ownsAllocator())
delete &getAllocator();
399 TreeTy*
add(TreeTy*
T, value_type_ref V) {
425 TreeTy*
getLeft(TreeTy*
T)
const {
return T->getLeft(); }
427 value_type_ref
getValue(TreeTy*
T)
const {
return T->value; }
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();
468 T = (TreeTy*)
A.Allocate<TreeTy>();
471 createdNodes.push_back(
T);
475 TreeTy*
createNode(TreeTy* newLeft, TreeTy* oldTree, TreeTy* newRight) {
480 for (
unsigned i = 0, n = createdNodes.size(); i < n; ++i) {
481 TreeTy *
N = createdNodes[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 if (ImutInfo::isDataEqual(ImutInfo::DataOfValue(V),
553 if (ImutInfo::isLess(K, KCurrent))
575 key_type_ref KCurrent = ImutInfo::KeyOfValue(
getValue(
T));
577 if (ImutInfo::isEqual(K, KCurrent))
582 if (ImutInfo::isLess(K, KCurrent))
617 if (!
T || !
T->isMutable())
629 if (TNew->IsCanonicalized)
634 unsigned digest = TNew->computeDigest();
639 for (TreeTy *
T = entry ;
T !=
nullptr;
T =
T->next) {
647 if (TNew->refCount == 0)
657 TNew->IsCanonicalized =
true;
683 if (Root) stack.push_back(
reinterpret_cast<uintptr_t
>(Root));
688 return *
reinterpret_cast<TreeTy *
>(stack.back() & ~
Flags);
694 return stack.back() &
Flags;
697 bool atEnd()
const {
return stack.empty(); }
721 return stack == x.stack;
725 return !(*
this == x);
735 stack.push_back(
reinterpret_cast<uintptr_t
>(L));
741 stack.push_back(
reinterpret_cast<uintptr_t
>(R));
765 stack.push_back(
reinterpret_cast<uintptr_t
>(L) |
VisitedRight);
771 stack.push_back(
reinterpret_cast<uintptr_t
>(R) |
VisitedRight);
783 InternalIteratorTy InternalItr;
802 return InternalItr == x.InternalItr;
806 return !(*
this == x);
814 while (!InternalItr.atEnd() &&
815 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
822 while (!InternalItr.atBeginning() &&
823 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft);
829 InternalItr.skipToParent();
831 while (!InternalItr.atEnd() &&
832 InternalItr.getVisitState() != InternalIteratorTy::VisitedLeft)
842 ImutAVLValueIterator<T>, typename T::TreeTy::iterator,
843 typename std::iterator_traits<
844 typename T::TreeTy::iterator>::iterator_category,
845 const typename T::value_type> {
851 return this->
I->getValue();
883#define PROFILE_INTEGER_INFO(X)\
884template<> struct ImutProfileInfo<X> : ImutProfileInteger<X> {};
897#undef PROFILE_INTEGER_INFO
945 return std::equal_to<key_type>()(
LHS,
RHS);
949 return std::less<key_type>()(
LHS,
RHS);
981template <
typename ValT,
typename ValInfo = ImutContainerInfo<ValT>>
1000 const bool Canonicalize;
1004 : Canonicalize(canonicalize) {}
1007 : F(
Alloc), Canonicalize(canonicalize) {}
1025 TreeTy *NewT = F.add(Old.Root.get(), V);
1026 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1037 TreeTy *NewT = F.remove(Old.Root.get(), V);
1038 return ImmutableSet(Canonicalize ? F.getCanonicalTree(NewT) : NewT);
1052 return Root ? Root->contains(V) :
false;
1056 return Root &&
RHS.Root ? Root->isEqual(*
RHS.Root.get()) : Root ==
RHS.Root;
1060 return Root &&
RHS.Root ? Root->isNotEqual(*
RHS.Root.get())
1065 if (Root) { Root->retain(); }
1091 unsigned getHeight()
const {
return Root ? Root->getHeight() : 0; }
1094 ID.AddPointer(S.Root.get());
1107template <
typename ValT,
typename ValInfo = ImutContainerInfo<ValT>>
1140 return Root ? Root->contains(V) :
false;
1145 canonicalize ? Factory->getCanonicalTree(Root.get()) : Root.get());
1151 return Root &&
RHS.Root ? Root->isEqual(*
RHS.Root.get()) : Root ==
RHS.Root;
1155 return Root &&
RHS.Root ? Root->isNotEqual(*
RHS.Root.get())
1179 unsigned getHeight()
const {
return Root ? Root->getHeight() : 0; }
1182 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.
This file defines the DenseMap class.
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.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
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)
ImutAVLTree< ValInfo > TreeTy
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
ImutAVLTree< ValInfo > TreeTy
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
ImutAVLTree< ImutInfo > value_type
std::ptrdiff_t difference_type
bool operator==(const ImutAVLTreeGenericIterator &x) const
std::bidirectional_iterator_tag iterator_category
ImutAVLTreeGenericIterator(const TreeTy *Root)
ImutAVLTree< ImutInfo > TreeTy
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++()
ImutAVLTree< ImutInfo > TreeTy
ImutAVLTreeInOrderIterator & operator--()
std::bidirectional_iterator_tag iterator_category
ImutAVLTreeInOrderIterator()
TreeTy & operator*() const
ImutAVLTreeInOrderIterator(const TreeTy *Root)
bool operator==(const ImutAVLTreeInOrderIterator &x) const
ImutAVLTree< ImutInfo > value_type
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 ValInfo::key_type_ref key_type_ref
ImutAVLFactory< ValInfo > Factory
ImutAVLTree * find(key_type_ref K)
find - Finds the subtree associated with the specified key value.
typename ValInfo::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< ValInfo > iterator
typename ValInfo::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...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
iterator_adaptor_base()=default
#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.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
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)
value_type value_type_ref
const bool & value_type_ref
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.