#include "llvm/Support/Allocator.h"
#include "llvm/ADT/FoldingSet.h"
-#include "llvm/Support/DataTypes.h"
+#include "llvm/System/DataTypes.h"
#include <cassert>
#include <functional>
//===----------------------------------------------------------------------===//
template <typename ImutInfo> class ImutAVLFactory;
+template <typename ImutInfo> class ImutIntervalAVLFactory;
template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
template <typename ImutInfo> class ImutAVLTreeGenericIterator;
typedef ImutAVLFactory<ImutInfo> Factory;
friend class ImutAVLFactory<ImutInfo>;
+ friend class ImutIntervalAVLFactory<ImutInfo>;
friend class ImutAVLTreeGenericIterator<ImutInfo>;
friend class FoldingSet<ImutAVLTree>;
/// getLeft - Returns a pointer to the left subtree. This value
/// is NULL if there is no left subtree.
- ImutAVLTree* getLeft() const {
- assert (!isMutable() && "Node is incorrectly marked mutable.");
-
- return reinterpret_cast<ImutAVLTree*>(Left);
- }
+ ImutAVLTree *getLeft() const { return Left; }
/// getRight - Returns a pointer to the right subtree. This value is
/// NULL if there is no right subtree.
- ImutAVLTree* getRight() const { return Right; }
+ ImutAVLTree *getRight() const { return Right; }
/// getHeight - Returns the height of the tree. A tree with no subtrees
/// has a height of 1.
return NULL;
}
+
+ /// getMaxElement - Find the subtree associated with the highest ranged
+ /// key value.
+ ImutAVLTree* getMaxElement() {
+ ImutAVLTree *T = this;
+ ImutAVLTree *Right = T->getRight();
+ while (Right) { T = Right; Right = T->getRight(); }
+ return T;
+ }
/// size - Returns the number of nodes in the tree, which includes
/// both leaves and non-leaf nodes.
/// contains - Returns true if this tree contains a subtree (node) that
/// has an data element that matches the specified key. Complexity
/// is logarithmic in the size of the tree.
- bool contains(const key_type_ref K) { return (bool) find(K); }
+ bool contains(key_type_ref K) { return (bool) find(K); }
/// foreach - A member template the accepts invokes operator() on a functor
/// object (specifed by Callback) for every node/subtree in the tree.
unsigned verify() const {
unsigned HL = getLeft() ? getLeft()->verify() : 0;
unsigned HR = getRight() ? getRight()->verify() : 0;
+ (void) HL;
+ (void) HR;
- assert (getHeight() == ( HL > HR ? HL : HR ) + 1
- && "Height calculation wrong.");
+ assert(getHeight() == ( HL > HR ? HL : HR ) + 1
+ && "Height calculation wrong");
- assert ((HL > HR ? HL-HR : HR-HL) <= 2
- && "Balancing invariant violated.");
+ assert((HL > HR ? HL-HR : HR-HL) <= 2
+ && "Balancing invariant violated");
+ assert(!getLeft()
+ || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
+ ImutInfo::KeyOfValue(getValue()))
+ && "Value in left child is not less that current value");
- assert (!getLeft()
- || ImutInfo::isLess(ImutInfo::KeyOfValue(getLeft()->getValue()),
- ImutInfo::KeyOfValue(getValue()))
- && "Value in left child is not less that current value.");
-
- assert (!getRight()
- || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
- ImutInfo::KeyOfValue(getRight()->getValue()))
- && "Current value is not less that value of right child.");
+ assert(!getRight()
+ || ImutInfo::isLess(ImutInfo::KeyOfValue(getValue()),
+ ImutInfo::KeyOfValue(getRight()->getValue()))
+ && "Current value is not less that value of right child");
return getHeight();
}
//===----------------------------------------------------===//
private:
- uintptr_t Left;
+ ImutAVLTree* Left;
ImutAVLTree* Right;
- unsigned Height;
+ unsigned Height : 28;
+ unsigned Mutable : 1;
+ unsigned CachedDigest : 1;
value_type Value;
- unsigned Digest;
+ uint32_t Digest;
//===----------------------------------------------------===//
// Internal methods (node manipulation; used by Factory).
//===----------------------------------------------------===//
private:
-
- enum { Mutable = 0x1 };
-
/// ImutAVLTree - Internal constructor that is only called by
/// ImutAVLFactory.
- ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height)
- : Left(reinterpret_cast<uintptr_t>(l) | Mutable),
- Right(r), Height(height), Value(v), Digest(0) {}
-
+ ImutAVLTree(ImutAVLTree* l, ImutAVLTree* r, value_type_ref v,
+ unsigned height)
+ : Left(l), Right(r), Height(height), Mutable(true), CachedDigest(false),
+ Value(v), Digest(0) {}
/// isMutable - Returns true if the left and right subtree references
/// (as well as height) can be changed. If this method returns false,
/// object should always have this method return true. Further, if 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 Left & Mutable; }
-
- /// getSafeLeft - Returns the pointer to the left tree by always masking
- /// out the mutable bit. This is used internally by ImutAVLFactory,
- /// as no trees returned to the client should have the mutable flag set.
- ImutAVLTree* getSafeLeft() const {
- return reinterpret_cast<ImutAVLTree*>(Left & ~Mutable);
- }
+ bool isMutable() const { return Mutable; }
+
+ /// 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 CachedDigest; }
//===----------------------------------------------------===//
// Mutating operations. A tree root can be manipulated as
// immutable.
//===----------------------------------------------------===//
-
/// MarkImmutable - Clears the mutable flag for a tree. After this happens,
- /// it is an error to call setLeft(), setRight(), and setHeight(). It
- /// is also then safe to call getLeft() instead of getSafeLeft().
+ /// it is an error to call setLeft(), setRight(), and setHeight().
void MarkImmutable() {
- assert (isMutable() && "Mutable flag already removed.");
- Left &= ~Mutable;
+ assert(isMutable() && "Mutable flag already removed.");
+ Mutable = false;
+ }
+
+ /// MarkedCachedDigest - Clears the NoCachedDigest flag for a tree.
+ void MarkedCachedDigest() {
+ assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
+ CachedDigest = true;
}
/// setLeft - Changes the reference of the left subtree. Used internally
/// by ImutAVLFactory.
void setLeft(ImutAVLTree* NewLeft) {
- assert (isMutable() &&
- "Only a mutable tree can have its left subtree changed.");
-
- Left = reinterpret_cast<uintptr_t>(NewLeft) | Mutable;
+ assert(isMutable() &&
+ "Only a mutable tree can have its left subtree changed.");
+ Left = NewLeft;
+ CachedDigest = false;
}
/// setRight - Changes the reference of the right subtree. Used internally
/// by ImutAVLFactory.
void setRight(ImutAVLTree* NewRight) {
- assert (isMutable() &&
- "Only a mutable tree can have its right subtree changed.");
+ assert(isMutable() &&
+ "Only a mutable tree can have its right subtree changed.");
Right = NewRight;
+ CachedDigest = false;
}
/// setHeight - Changes the height of the tree. Used internally by
/// ImutAVLFactory.
void setHeight(unsigned h) {
- assert (isMutable() && "Only a mutable tree can have its height changed.");
+ assert(isMutable() && "Only a mutable tree can have its height changed.");
Height = h;
}
-
static inline
- unsigned ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
- unsigned digest = 0;
+ uint32_t ComputeDigest(ImutAVLTree* L, ImutAVLTree* R, value_type_ref V) {
+ uint32_t digest = 0;
- if (L) digest += L->ComputeDigest();
+ if (L)
+ digest += L->ComputeDigest();
- { // Compute digest of stored data.
- FoldingSetNodeID ID;
- ImutInfo::Profile(ID,V);
- digest += ID.ComputeHash();
- }
+ // Compute digest of stored data.
+ FoldingSetNodeID ID;
+ ImutInfo::Profile(ID,V);
+ digest += ID.ComputeHash();
- if (R) digest += R->ComputeDigest();
+ if (R)
+ digest += R->ComputeDigest();
return digest;
}
- inline unsigned ComputeDigest() {
- if (Digest) return Digest;
-
- unsigned X = ComputeDigest(getSafeLeft(), getRight(), getValue());
- if (!isMutable()) Digest = X;
+ inline uint32_t ComputeDigest() {
+ // Check the lowest bit to determine if digest has actually been
+ // pre-computed.
+ if (hasCachedDigest())
+ return Digest;
+ uint32_t X = ComputeDigest(getLeft(), getRight(), getValue());
+ Digest = X;
+ MarkedCachedDigest();
return X;
}
};
// These have succinct names so that the balancing code
// is as terse (and readable) as possible.
//===--------------------------------------------------===//
-private:
+protected:
bool isEmpty(TreeTy* T) const { return !T; }
- unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
- TreeTy* Left(TreeTy* T) const { return T->getSafeLeft(); }
+ unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
+ TreeTy* Left(TreeTy* T) const { return T->getLeft(); }
TreeTy* Right(TreeTy* T) const { return T->getRight(); }
value_type_ref Value(TreeTy* T) const { return T->Value; }
unsigned IncrementHeight(TreeTy* L, TreeTy* R) const {
unsigned hl = Height(L);
unsigned hr = Height(R);
- return ( hl > hr ? hl : hr ) + 1;
+ return (hl > hr ? hl : hr) + 1;
}
-
static bool CompareTreeWithSection(TreeTy* T,
typename TreeTy::iterator& TI,
typename TreeTy::iterator& TE) {
// returned to the caller.
//===--------------------------------------------------===//
- TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {
- // Search the FoldingSet bucket for a Tree with the same digest.
- FoldingSetNodeID ID;
- unsigned digest = TreeTy::ComputeDigest(L, R, V);
- ID.AddInteger(digest);
- unsigned hash = ID.ComputeHash();
-
- typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash);
- typename CacheTy::bucket_iterator E = Cache.bucket_end(hash);
-
- for (; I != E; ++I) {
- TreeTy* T = &*I;
-
- if (T->ComputeDigest() != digest)
- continue;
-
- // We found a collision. Perform a comparison of Contents('T')
- // with Contents('L')+'V'+Contents('R').
-
- typename TreeTy::iterator TI = T->begin(), TE = T->end();
-
- // First compare Contents('L') with the (initial) contents of T.
- if (!CompareTreeWithSection(L, TI, TE))
- continue;
-
- // Now compare the new data element.
- if (TI == TE || !TI->ElementEqual(V))
- continue;
-
- ++TI;
-
- // Now compare the remainder of 'T' with 'R'.
- if (!CompareTreeWithSection(R, TI, TE))
- continue;
-
- if (TI != TE) // Contents('R') did not match suffix of 'T'.
- continue;
-
- // Trees did match! Return 'T'.
- return T;
- }
-
- // No tree with the contents: Contents('L')+'V'+Contents('R').
- // Create it.
-
- // Allocate the new tree node and insert it into the cache.
+ TreeTy* CreateNode(TreeTy* L, value_type_ref V, TreeTy* R) {
BumpPtrAllocator& A = getAllocator();
TreeTy* T = (TreeTy*) A.Allocate<TreeTy>();
- new (T) TreeTy(L,R,V,IncrementHeight(L,R));
-
- // We do not insert 'T' into the FoldingSet here. This is because
- // this tree is still mutable and things may get rebalanced.
- // Because our digest is associative and based on the contents of
- // the set, this should hopefully not cause any strange bugs.
- // 'T' is inserted by 'MarkImmutable'.
-
+ new (T) TreeTy(L, R, V, IncrementHeight(L,R));
return T;
}
TreeTy* CreateNode(TreeTy* L, TreeTy* OldTree, TreeTy* R) {
- assert (!isEmpty(OldTree));
+ assert(!isEmpty(OldTree));
if (OldTree->isMutable()) {
OldTree->setLeft(L);
OldTree->setRight(R);
- OldTree->setHeight(IncrementHeight(L,R));
+ OldTree->setHeight(IncrementHeight(L, R));
return OldTree;
}
- else return CreateNode(L, Value(OldTree), R);
+ else
+ return CreateNode(L, Value(OldTree), R);
}
/// Balance - Used by Add_internal and Remove_internal to
unsigned hr = Height(R);
if (hl > hr + 2) {
- assert (!isEmpty(L) &&
- "Left tree cannot be empty to have a height >= 2.");
+ assert(!isEmpty(L) && "Left tree cannot be empty to have a height >= 2");
TreeTy* LL = Left(L);
TreeTy* LR = Right(L);
if (Height(LL) >= Height(LR))
return CreateNode(LL, L, CreateNode(LR,V,R));
- assert (!isEmpty(LR) &&
- "LR cannot be empty because it has a height >= 1.");
+ assert(!isEmpty(LR) && "LR cannot be empty because it has a height >= 1");
TreeTy* LRL = Left(LR);
TreeTy* LRR = Right(LR);
return CreateNode(CreateNode(LL,L,LRL), LR, CreateNode(LRR,V,R));
}
else if (hr > hl + 2) {
- assert (!isEmpty(R) &&
- "Right tree cannot be empty to have a height >= 2.");
+ assert(!isEmpty(R) && "Right tree cannot be empty to have a height >= 2");
TreeTy* RL = Left(R);
TreeTy* RR = Right(R);
if (Height(RR) >= Height(RL))
return CreateNode(CreateNode(L,V,RL), R, RR);
- assert (!isEmpty(RL) &&
- "RL cannot be empty because it has a height >= 1.");
+ assert(!isEmpty(RL) && "RL cannot be empty because it has a height >= 1");
TreeTy* RLL = Left(RL);
TreeTy* RLR = Right(RL);
if (isEmpty(T))
return CreateNode(T, V, T);
- assert (!T->isMutable());
+ assert(!T->isMutable());
key_type_ref K = ImutInfo::KeyOfValue(V);
key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
if (isEmpty(T))
return T;
- assert (!T->isMutable());
+ assert(!T->isMutable());
key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
}
TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {
- assert (!isEmpty(T));
+ assert(!isEmpty(T));
if (isEmpty(Left(T))) {
NodeRemoved = T;
T->MarkImmutable();
MarkImmutable(Left(T));
MarkImmutable(Right(T));
+ }
+
+public:
+ TreeTy *GetCanonicalTree(TreeTy *TNew) {
+ if (!TNew)
+ return NULL;
+
+ // Search the FoldingSet bucket for a Tree with the same digest.
+ FoldingSetNodeID ID;
+ unsigned digest = TNew->ComputeDigest();
+ ID.AddInteger(digest);
+ unsigned hash = ID.ComputeHash();
+
+ typename CacheTy::bucket_iterator I = Cache.bucket_begin(hash);
+ typename CacheTy::bucket_iterator E = Cache.bucket_end(hash);
+
+ for (; I != E; ++I) {
+ TreeTy *T = &*I;
+
+ if (T->ComputeDigest() != digest)
+ continue;
+
+ // We found a collision. Perform a comparison of Contents('T')
+ // with Contents('TNew')
+ typename TreeTy::iterator TI = T->begin(), TE = T->end();
+
+ if (!CompareTreeWithSection(TNew, TI, TE))
+ continue;
+
+ if (TI != TE)
+ continue; // T has more contents than TNew.
+
+ // Trees did match! Return 'T'.
+ return T;
+ }
- // Now that the node is immutable it can safely be inserted
- // into the node cache.
- llvm::FoldingSetNodeID ID;
- ID.AddInteger(T->ComputeDigest());
- Cache.InsertNode(T, (void*) &*Cache.bucket_end(ID.ComputeHash()));
+ // 'TNew' is the only tree of its kind. Return it.
+ Cache.InsertNode(TNew, (void*) &*Cache.bucket_end(hash));
+ return TNew;
}
};
}
TreeTy* operator*() const {
- assert (!stack.empty());
+ assert(!stack.empty());
return reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
}
uintptr_t getVisitState() {
- assert (!stack.empty());
+ assert(!stack.empty());
return stack.back() & Flags;
}
}
void SkipToParent() {
- assert (!stack.empty());
+ assert(!stack.empty());
stack.pop_back();
if (stack.empty())
stack.back() |= VisitedRight;
break;
default:
- assert (false && "Unreachable.");
+ assert(false && "Unreachable.");
}
}
inline bool operator!=(const _Self& x) const { return !operator==(x); }
_Self& operator++() {
- assert (!stack.empty());
+ assert(!stack.empty());
TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
- assert (Current);
+ assert(Current);
switch (getVisitState()) {
case VisitedNone:
- if (TreeTy* L = Current->getSafeLeft())
+ if (TreeTy* L = Current->getLeft())
stack.push_back(reinterpret_cast<uintptr_t>(L));
else
stack.back() |= VisitedLeft;
break;
default:
- assert (false && "Unreachable.");
+ assert(false && "Unreachable.");
}
return *this;
}
_Self& operator--() {
- assert (!stack.empty());
+ assert(!stack.empty());
TreeTy* Current = reinterpret_cast<TreeTy*>(stack.back() & ~Flags);
- assert (Current);
+ assert(Current);
switch (getVisitState()) {
case VisitedNone:
break;
default:
- assert (false && "Unreachable.");
+ assert(false && "Unreachable.");
}
return *this;
typedef ImutAVLTree<ValInfo> TreeTy;
private:
- TreeTy* Root;
-
+ TreeTy *Root;
+
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
class Factory {
typename TreeTy::Factory F;
+ const bool Canonicalize;
public:
- Factory() {}
+ Factory(bool canonicalize = true)
+ : Canonicalize(canonicalize) {}
- Factory(BumpPtrAllocator& Alloc)
- : F(Alloc) {}
+ Factory(BumpPtrAllocator& Alloc, bool canonicalize = true)
+ : F(Alloc), Canonicalize(canonicalize) {}
/// GetEmptySet - Returns an immutable set that contains no elements.
- ImmutableSet GetEmptySet() { return ImmutableSet(F.GetEmptyTree()); }
+ ImmutableSet GetEmptySet() {
+ return ImmutableSet(F.GetEmptyTree());
+ }
/// Add - Creates a new immutable set that contains all of the values
/// of the original set with the addition of the specified value. If
/// The memory allocated to represent the set is released when the
/// factory object that created the set is destroyed.
ImmutableSet Add(ImmutableSet Old, value_type_ref V) {
- return ImmutableSet(F.Add(Old.Root,V));
+ TreeTy *NewT = F.Add(Old.Root, V);
+ return ImmutableSet(Canonicalize ? F.GetCanonicalTree(NewT) : NewT);
}
/// Remove - Creates a new immutable set that contains all of the values
/// The memory allocated to represent the set is released when the
/// factory object that created the set is destroyed.
ImmutableSet Remove(ImmutableSet Old, value_type_ref V) {
- return ImmutableSet(F.Remove(Old.Root,V));
+ TreeTy *NewT = F.Remove(Old.Root, V);
+ return ImmutableSet(Canonicalize ? F.GetCanonicalTree(NewT) : NewT);
}
BumpPtrAllocator& getAllocator() { return F.getAllocator(); }
private:
- Factory(const Factory& RHS) {};
- void operator=(const Factory& RHS) {};
+ Factory(const Factory& RHS); // DO NOT IMPLEMENT
+ void operator=(const Factory& RHS); // DO NOT IMPLEMENT
};
friend class Factory;
/// contains - Returns true if the set contains the specified value.
- bool contains(const value_type_ref V) const {
+ bool contains(value_type_ref V) const {
return Root ? Root->contains(V) : false;
}
return Root && RHS.Root ? Root->isNotEqual(*RHS.Root) : Root != RHS.Root;
}
- TreeTy* getRoot() const { return Root; }
+ TreeTy *getRoot() {
+ return Root;
+ }
/// isEmpty - Return true if the set contains no elements.
bool isEmpty() const { return !Root; }
class iterator {
typename TreeTy::iterator itr;
-
- iterator() {}
iterator(TreeTy* t) : itr(t) {}
friend class ImmutableSet<ValT,ValInfo>;
public:
+ iterator() {}
inline value_type_ref operator*() const { return itr->getValue(); }
inline iterator& operator++() { ++itr; return *this; }
inline iterator operator++(int) { iterator tmp(*this); ++itr; return tmp; }
// Utility methods.
//===--------------------------------------------------===//
- inline unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
+ unsigned getHeight() const { return Root ? Root->getHeight() : 0; }
static inline void Profile(FoldingSetNodeID& ID, const ImmutableSet& S) {
ID.AddPointer(S.Root);
projects / oota-llvm.git / blobdiff