/// getMaxElement - Find the subtree associated with the highest ranged
/// key value.
ImutAVLTree* getMaxElement() {
ImutAVLTree *T = this;
/// getMaxElement - Find the subtree associated with the highest ranged
/// key value.
ImutAVLTree* getMaxElement() {
ImutAVLTree *T = this;
/// method returns false for an instance of ImutAVLTree, all subtrees
/// will also have this method return false. The converse is not true.
bool isMutable() const { return IsMutable; }
/// method returns false for an instance of ImutAVLTree, all subtrees
/// will also have this method return false. The converse is not true.
bool isMutable() const { return IsMutable; }
/// hasCachedDigest - Returns true if the digest for this tree is cached.
/// This can only be true if the tree is immutable.
bool hasCachedDigest() const { return IsDigestCached; }
/// hasCachedDigest - Returns true if the digest for this tree is cached.
/// This can only be true if the tree is immutable.
bool hasCachedDigest() const { return IsDigestCached; }
/// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
void markedCachedDigest() {
assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
/// markedCachedDigest - Clears the NoCachedDigest flag for a tree.
void markedCachedDigest() {
assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
// We need to clear the mutability bit in case we are
// destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
IsMutable = false;
// We need to clear the mutability bit in case we are
// destroying the node as part of a sweep in ImutAVLFactory::recoverNodes().
IsMutable = false;
//===--------------------------------------------------===//
// A bunch of quick helper functions used for reasoning
// about the properties of trees and their children.
//===--------------------------------------------------===//
// A bunch of quick helper functions used for reasoning
// about the properties of trees and their children.
T = (TreeTy*) A.Allocate<TreeTy>();
}
new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
T = (TreeTy*) A.Allocate<TreeTy>();
}
new (T) TreeTy(this, L, R, V, incrementHeight(L,R));
return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
}
return createNode(createNode(LL,L,LRL), LR, createNode(LRR,V,R));
}
return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
}
return createNode(createNode(L,V,RLL), RL, createNode(RLR,R,RR));
}
public:
/// Constructs a set from a pointer to a tree root. In general one
/// should use a Factory object to create sets instead of directly
public:
/// Constructs a set from a pointer to a tree root. In general one
/// should use a Factory object to create sets instead of directly
typename TreeTy::Factory *getTreeFactory() const {
return const_cast<typename TreeTy::Factory *>(&F);
}
typename TreeTy::Factory *getTreeFactory() const {
return const_cast<typename TreeTy::Factory *>(&F);
}
- Factory(const Factory& RHS); // DO NOT IMPLEMENT
- void operator=(const Factory& RHS); // DO NOT IMPLEMENT
+ Factory(const Factory& RHS) LLVM_DELETED_FUNCTION;
+ void operator=(const Factory& RHS) LLVM_DELETED_FUNCTION;
// NOTE: This may some day replace the current ImmutableSet.
template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
class ImmutableSetRef {
// NOTE: This may some day replace the current ImmutableSet.
template <typename ValT, typename ValInfo = ImutContainerInfo<ValT> >
class ImmutableSetRef {
typedef typename ValInfo::value_type_ref value_type_ref;
typedef ImutAVLTree<ValInfo> TreeTy;
typedef typename TreeTy::Factory FactoryTy;
typedef typename ValInfo::value_type_ref value_type_ref;
typedef ImutAVLTree<ValInfo> TreeTy;
typedef typename TreeTy::Factory FactoryTy;
public:
/// Constructs a set from a pointer to a tree root. In general one
/// should use a Factory object to create sets instead of directly
public:
/// Constructs a set from a pointer to a tree root. In general one
/// should use a Factory object to create sets instead of directly
static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
return ImmutableSetRef(0, F);
}
static inline ImmutableSetRef getEmptySet(FactoryTy *F) {
return ImmutableSetRef(0, F);
}
ImmutableSetRef add(value_type_ref V) {
return ImmutableSetRef(Factory->add(Root, V), Factory);
}
ImmutableSetRef add(value_type_ref V) {
return ImmutableSetRef(Factory->add(Root, V), Factory);
}
ImmutableSetRef remove(value_type_ref V) {
return ImmutableSetRef(Factory->remove(Root, V), Factory);
}
ImmutableSetRef remove(value_type_ref V) {
return ImmutableSetRef(Factory->remove(Root, V), Factory);
}
/// Returns true if the set contains the specified value.
bool contains(value_type_ref V) const {
return Root ? Root->contains(V) : false;
}
/// Returns true if the set contains the specified value.
bool contains(value_type_ref V) const {
return Root ? Root->contains(V) : false;
}
ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
return ImmutableSet<ValT>(canonicalize ?
Factory->getCanonicalTree(Root) : Root);
}
ImmutableSet<ValT> asImmutableSet(bool canonicalize = true) const {
return ImmutableSet<ValT>(canonicalize ?
Factory->getCanonicalTree(Root) : Root);
}
bool operator==(const ImmutableSetRef &RHS) const {
return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
}
bool operator==(const ImmutableSetRef &RHS) const {
return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
}
bool operator!=(const ImmutableSetRef &RHS) const {
return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
}
/// isEmpty - Return true if the set contains no elements.
bool isEmpty() const { return !Root; }
bool operator!=(const ImmutableSetRef &RHS) const {
return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
}
/// isEmpty - Return true if the set contains no elements.
bool isEmpty() const { return !Root; }
/// isSingleton - Return true if the set contains exactly one element.
/// This method runs in constant time.
bool isSingleton() const { return getHeight() == 1; }
/// isSingleton - Return true if the set contains exactly one element.
/// This method runs in constant time.
bool isSingleton() const { return getHeight() == 1; }
//===--------------------------------------------------===//
// Iterators.
//===--------------------------------------------------===//
//===--------------------------------------------------===//
// Iterators.
//===--------------------------------------------------===//
inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
inline value_type *operator->() const { return &(operator*()); }
};
inline bool operator!=(const iterator& RHS) const { return RHS.itr != itr; }
inline value_type *operator->() const { return &(operator*()); }
};
//===--------------------------------------------------===//
// Utility methods.
//===--------------------------------------------------===//
//===--------------------------------------------------===//
// Utility methods.
//===--------------------------------------------------===//
inline void Profile(FoldingSetNodeID& ID) const {
return Profile(ID,*this);
}
inline void Profile(FoldingSetNodeID& ID) const {
return Profile(ID,*this);
}
//===--------------------------------------------------===//
// For testing.
//===--------------------------------------------------===//
//===--------------------------------------------------===//
// For testing.
//===--------------------------------------------------===//