1 files changed, 52 insertions, 61 deletions

diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index 676a198..ac06a40 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -51,13 +51,11 @@ public:
 
   /// 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.
@@ -190,23 +188,22 @@ public:
     unsigned HL = getLeft() ? getLeft()->verify() : 0;
     unsigned HR = getRight() ? getRight()->verify() : 0;
 
-    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();
   }
@@ -221,9 +218,11 @@ public:
   //===----------------------------------------------------===//
 
 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;
 
@@ -232,15 +231,12 @@ private:
   //===----------------------------------------------------===//
 
 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,
@@ -248,11 +244,11 @@ private:
   ///  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
@@ -269,13 +265,13 @@ private:
   ///   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
@@ -283,7 +279,8 @@ private:
   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
@@ -293,9 +290,7 @@ private:
            "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
@@ -397,7 +392,7 @@ public:
 private:
 
   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; }
@@ -405,7 +400,7 @@ private:
   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,
@@ -434,17 +429,17 @@ private:
   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
@@ -459,8 +454,7 @@ private:
     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);
@@ -468,8 +462,7 @@ private:
       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);
@@ -477,8 +470,7 @@ private:
       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);
@@ -486,8 +478,7 @@ private:
       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);
@@ -505,7 +496,7 @@ private:
     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));
@@ -526,7 +517,7 @@ private:
     if (isEmpty(T))
       return T;
 
-    assert (!T->isMutable());
+    assert(!T->isMutable());
 
     key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
 
@@ -548,7 +539,7 @@ private:
   }
 
   TreeTy* RemoveMinBinding(TreeTy* T, TreeTy*& NodeRemoved) {
-    assert (!isEmpty(T));
+    assert(!isEmpty(T));
 
     if (isEmpty(Left(T))) {
       NodeRemoved = T;
@@ -641,12 +632,12 @@ public:
   }
 
   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;
   }
 
@@ -658,7 +649,7 @@ public:
   }
 
   void SkipToParent() {
-    assert (!stack.empty());
+    assert(!stack.empty());
     stack.pop_back();
 
     if (stack.empty())
@@ -672,7 +663,7 @@ public:
         stack.back() |= VisitedRight;
         break;
       default:
-        assert (false && "Unreachable.");
+        assert(false && "Unreachable.");
     }
   }
 
@@ -690,10 +681,10 @@ public:
   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:
@@ -717,17 +708,17 @@ public:
         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:
@@ -752,7 +743,7 @@ public:
         break;
 
       default:
-        assert (false && "Unreachable.");
+        assert(false && "Unreachable.");
     }
 
     return *this;
@@ -1051,7 +1042,7 @@ public:
   // 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);