#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 {
- return reinterpret_cast<ImutAVLTree*>(Left & ~LeftFlags);
- }
+ 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.
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 ((HL > HR ? HL-HR : HR-HL) <= 2
- && "Balancing invariant violated.");
+ assert(getHeight() == ( HL > HR ? HL : HR ) + 1
+ && "Height calculation wrong");
+ 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;
uint32_t Digest;
//===----------------------------------------------------===//
private:
-
- enum { Mutable = 0x1, NoCachedDigest = 0x2, LeftFlags = 0x3 };
-
/// 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 | NoCachedDigest)),
- 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; }
+ 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 !(Left & NoCachedDigest); }
+ bool hasCachedDigest() const { return CachedDigest; }
//===----------------------------------------------------===//
// Mutating operations. A tree root can be manipulated as
/// it is an error to call setLeft(), setRight(), and setHeight().
void MarkImmutable() {
assert(isMutable() && "Mutable flag already removed.");
- Left &= ~Mutable;
+ Mutable = false;
}
/// MarkedCachedDigest - Clears the NoCachedDigest flag for a tree.
void MarkedCachedDigest() {
assert(!hasCachedDigest() && "NoCachedDigest flag already removed.");
- Left &= ~NoCachedDigest;
+ CachedDigest = true;
}
/// setLeft - Changes the reference of the left subtree. Used internally
void setLeft(ImutAVLTree* NewLeft) {
assert(isMutable() &&
"Only a mutable tree can have its left subtree changed.");
- Left = reinterpret_cast<uintptr_t>(NewLeft) | LeftFlags;
+ Left = NewLeft;
+ CachedDigest = false;
}
/// setRight - Changes the reference of the right subtree. Used internally
"Only a mutable tree can have its right subtree changed.");
Right = NewRight;
- // Set the NoCachedDigest flag.
- Left = Left | NoCachedDigest;
-
+ CachedDigest = false;
}
/// setHeight - Changes the height of the tree. Used internally by
// 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; }
+ 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,
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));
+ 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
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;
continue;
// We found a collision. Perform a comparison of Contents('T')
- // with Contents('L')+'V'+Contents('R').
+ // with Contents('TNew')
typename TreeTy::iterator TI = T->begin(), TE = T->end();
- // First compare Contents('L') with the (initial) contents of T.
- if (!CompareTreeWithSection(TNew->getLeft(), TI, TE))
- continue;
-
- // Now compare the new data element.
- if (TI == TE || !TI->ElementEqual(TNew->getValue()))
- continue;
-
- ++TI;
-
- // Now compare the remainder of 'T' with 'R'.
- if (!CompareTreeWithSection(TNew->getRight(), TI, TE))
+ if (!CompareTreeWithSection(TNew, TI, TE))
continue;
if (TI != TE)
- continue; // Contents('R') did not match suffix of 'T'.
+ continue; // T has more contents than TNew.
// Trees did match! Return 'T'.
return T;
}
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:
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;
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;
// 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