Implement TLSLDM.

[oota-llvm.git] / include / llvm / ADT / ImmutableIntervalMap.h

diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h
index 74ae5f3553870f766c8f43ec8acd81304e034c41..968ce152779fa6f67c53df8df48afa384519d866 100644 (file)
--- a/include/llvm/ADT/ImmutableIntervalMap.h
+++ b/include/llvm/ADT/ImmutableIntervalMap.h
@@ -16,14 +16,14 @@ namespace llvm {
 
 class Interval {
 private:
-  uint64_t Start;
-  uint64_t End;
+  int64_t Start;
+  int64_t End;
 
 public:
-  Interval(uint64_t S, uint64_t E) : Start(S), End(E) {}
+  Interval(int64_t S, int64_t E) : Start(S), End(E) {}
 
-  uint64_t getStart() const { return Start; }
-  uint64_t getEnd() const { return End; }
+  int64_t getStart() const { return Start; }
+  int64_t getEnd() const { return End; }
 };
 
 template <typename T>
@@ -79,8 +79,6 @@ struct ImutIntervalInfo {
   }
 };
 
-template <typename ImutInfo> class ImutIntervalAVLFactory;
-
 template <typename ImutInfo>
 class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
   typedef ImutAVLTree<ImutInfo> TreeTy;
@@ -92,9 +90,12 @@ class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
   typedef typename ImutInfo::data_type_ref  data_type_ref;
 
 public:
+  ImutIntervalAVLFactory(BumpPtrAllocator &Alloc) 
+    : ImutAVLFactory<ImutInfo>(Alloc) {}
+
   TreeTy *Add(TreeTy *T, value_type_ref V) {
     T = Add_internal(V,T);
-    MarkImmutable(T);
+    this->MarkImmutable(T);
     return T;
   }
 
@@ -102,83 +103,84 @@ public:
     if (!T)
       return NULL;
 
-    key_type_ref CurrentKey = ImutInfo::KeyOfValue(Value(T));
+    key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->Value(T));
 
     if (ImutInfo::isContainedIn(K, CurrentKey))
       return T;
     else if (ImutInfo::isLess(K, CurrentKey))
-      return Find(Left(T), K);
+      return Find(this->Left(T), K);
     else
-      return Find(Right(T), K);
+      return Find(this->Right(T), K);
   }
 
 private:
   TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
     key_type_ref K = ImutInfo::KeyOfValue(V);
     T = RemoveAllOverlaps(T, K);
-    if (isEmpty(T))
-      return CreateNode(NULL, V, NULL);
+    if (this->isEmpty(T))
+      return this->CreateNode(NULL, V, NULL);
 
     assert(!T->isMutable());
 
-    key_type_ref KCurrent = ImutInfo::KeyOfValue(Value(T));
+    key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T));
 
     if (ImutInfo::isLess(K, KCurrent))
-      return Balance(Add_internal(V, Left(T)), Value(T), Right(T));
+      return this->Balance(Add_internal(V, this->Left(T)), this->Value(T), 
+                                        this->Right(T));
     else
-      return Balance(Left(T), Value(T), Add_internal(V, Right(T)));
+      return this->Balance(this->Left(T), this->Value(T), 
+                           Add_internal(V, this->Right(T)));
   }
 
   // Remove all overlaps from T.
   TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
-    TreeTy *OldTree, *NewTree;
-    NewTree = T;
-
+    bool Changed;
     do {
-      OldTree = NewTree;
-      NewTree = RemoveOverlap(OldTree, K);
-    } while (NewTree != OldTree);
+      Changed = false;
+      T = RemoveOverlap(T, K, Changed);
+      this->MarkImmutable(T);
+    } while (Changed);
 
-    return NewTree;
+    return T;
   }
 
   // Remove one overlap from T.
-  TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K) {
+  TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
     if (!T)
       return NULL;
-    Interval CurrentK = ImutInfo::KeyOfValue(Value(T));
+    Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
 
     // If current key does not overlap the inserted key.
     if (CurrentK.getStart() > K.getEnd())
-      return RemoveOverlap(Left(T), K);
+      return this->Balance(RemoveOverlap(this->Left(T), K, Changed),
+                           this->Value(T), this->Right(T));
     else if (CurrentK.getEnd() < K.getStart())
-      return RemoveOverlap(Right(T), K);
+      return this->Balance(this->Left(T), this->Value(T), 
+                           RemoveOverlap(this->Right(T), K, Changed));
 
     // Current key overlaps with the inserted key.
     // Remove the current key.
-    TreeTy *OldNode = T;
-    T = Remove_internal(CurrentK, T);
+    Changed = true;
+    data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
+    T = this->Remove_internal(CurrentK, T);
     // Add back the unoverlapped part of the current key.
     if (CurrentK.getStart() < K.getStart()) {
       if (CurrentK.getEnd() <= K.getEnd()) {
         Interval NewK(CurrentK.getStart(), K.getStart()-1);
-        return Add_internal(std::make_pair<key_type, data_type>(NewK, 
-                                     ImutInfo::DataOfValue(Value(OldNode))), T);
+        return Add_internal(std::make_pair(NewK, OldData), T);
       } else {
         Interval NewK1(CurrentK.getStart(), K.getStart()-1);
-        T = Add_internal(std::make_pair<key_type, data_type>(NewK1, 
-                                     ImutInfo::DataOfValue(Value(OldNode))), T);
+        T = Add_internal(std::make_pair(NewK1, OldData), T); 
 
         Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
-        return Add_internal(std::make_pair<key_type, data_type>(NewK2,
-                                     ImutInfo::DataOfValue(Value(OldNode))), T);
+        return Add_internal(std::make_pair(NewK2, OldData), T);
       }
     } else {
       if (CurrentK.getEnd() > K.getEnd()) {
         Interval NewK(K.getEnd()+1, CurrentK.getEnd());
-        return Add_internal(std::make_pair<key_type, data_type>(NewK, 
-                                     ImutInfo::DataOfValue(Value(OldNode))), T);
-      }
+        return Add_internal(std::make_pair(NewK, OldData), T);
+      } else
+        return T;
     }
   }
 };
@@ -205,6 +207,8 @@ public:
     ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
 
   public:
+    Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
+
     ImmutableIntervalMap GetEmptyMap() { 
       return ImmutableIntervalMap(F.GetEmptyTree()); 
     }
@@ -227,7 +231,6 @@ public:
       else
         return 0;
     }
-
   };
 
 private: