Revert commit 158979 (dyatkovskiy) since it is causing several buildbots to

[oota-llvm.git] / include / llvm / Support / IntegersSubsetMapping.h

diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h
index d3d11f03ba11a8163d087ef9d74645ba8c45490f..c79b3c16845bbb663e40c5d6e12ba1ac18d1584a 100644 (file)
--- a/include/llvm/Support/IntegersSubsetMapping.h
+++ b/include/llvm/Support/IntegersSubsetMapping.h
@@ -49,7 +49,7 @@ public:
 
 protected:
 
-  typedef std::vector<Cluster> CaseItems;
+  typedef std::list<Cluster> CaseItems;
   typedef typename CaseItems::iterator CaseItemIt;
   typedef typename CaseItems::const_iterator CaseItemConstIt;
   
@@ -66,6 +66,12 @@ protected:
     }
   };
   
+  struct ClusterLefterThan {
+    bool operator()(const Cluster &C, const RangeTy &R) {
+      return C.first.getHigh() < R.getLow();
+    }
+  };  
+  
   CaseItems Items;
   bool Sorted;
   
@@ -87,11 +93,50 @@ protected:
   
   void sort() {
     if (!Sorted) {
-      std::sort(Items.begin(), Items.end(), ClustersCmp());
+      std::vector<Cluster> clustersVector;
+      clustersVector.reserve(Items.size());
+      clustersVector.insert(clustersVector.begin(), Items.begin(), Items.end());
+      std::sort(clustersVector.begin(), clustersVector.end(), ClustersCmp());
+      Items.clear();
+      Items.insert(Items.begin(), clustersVector.begin(), clustersVector.end());
       Sorted = true;
     }
   }
   
+  void exclude(CaseItemIt &beginIt, RangeTy &R) {
+    
+    std::list<CaseItemIt> ToBeErased;
+
+    CaseItemIt endIt = Items.end();
+    CaseItemIt It =
+          std::lower_bound(beginIt, Items.end(), R, ClusterLefterThan());
+    
+    if (It == endIt)
+      return;
+
+    if (It->first.getLow() < R.getLow())
+      Items.insert(It, std::make_pair(
+          RangeTy(It->first.getLow(), R.getLow()-1),
+          It->second));
+
+    do
+    ToBeErased.push_back(It++);
+    while (It != endIt && It->first.getLow() <= R.getHigh());
+
+    beginIt = It;
+    
+    CaseItemIt &LastRemoved = *(--ToBeErased.end());
+    if (LastRemoved->first.getHigh() > R.getHigh())
+      beginIt = Items.insert(LastRemoved, std::make_pair(
+          RangeTy(R.getHigh() + 1, LastRemoved->first.getHigh()),
+          LastRemoved->second
+          ));
+    
+    for (typename std::list<CaseItemIt>::iterator i = ToBeErased.begin(),
+         e = ToBeErased.end(); i != e; ++i)
+      Items.erase(*i);
+  }   
+
 public:
   
   // Don't public CaseItems itself. Don't allow edit the Items directly. 
@@ -104,7 +149,6 @@ public:
   typedef std::list<Case> Cases;
   
   IntegersSubsetMapping() {
-    Items.reserve(32);
     Sorted = false;
   }
   
@@ -112,7 +156,7 @@ public:
     if (Items.empty())
       return true;
     sort();
-    for (CaseItemIt i = Items.begin(), j = i+1, e = Items.end();
+    for (CaseItemIt j = Items.begin(), i = j++, e = Items.end();
          j != e; i = j++) {
       if (isIntersected(i, j) && i->second != j->second) {
         errItem = j;
@@ -132,8 +176,8 @@ public:
     const IntTy *High = &OldItems.begin()->first.getHigh();
     unsigned Weight = 1;
     SuccessorClass *Successor = OldItems.begin()->second;
-    for (CaseItemIt i = OldItems.begin(), j = i+1, e = OldItems.end();
-        j != e; i = j++) {
+    for (CaseItemIt j = OldItems.begin(), i = j++, e = OldItems.end();
+         j != e; i = j++) {
       if (isJoinable(i, j)) {
         const IntTy *CurHigh = &j->first.getHigh();
         ++Weight;
@@ -176,7 +220,7 @@ public:
   
   /// Adds all ranges and values from given ranges set to the current
   /// mapping.
-  void add(const IntegersSubset &CRS, SuccessorClass *S = 0) {
+  void add(const IntegersSubsetTy &CRS, SuccessorClass *S = 0) {
     for (unsigned i = 0, e = CRS.getNumItems(); i < e; ++i) {
       RangeTy R = CRS.getItem(i);
       add(R, S);
@@ -186,6 +230,18 @@ public:
   /// Removes items from set.
   void removeItem(RangeIterator i) { Items.erase(i); }
   
+  // Excludes RHS subset from current mapping. RHS should consists of non
+  // overlapped ranges only and sorted from left to the right.
+  // method will have unpredictional behaviour in another case. 
+  void exclude(IntegersSubsetTy &RHS) {
+    CaseItemIt startIt = begin();
+    for (unsigned i = 0, e = RHS.getNumItems();
+         i != e && startIt != end(); ++i) {
+      RangeTy R = RHS.getItem(i);
+      exclude(startIt, R);
+    }
+  }  
+  
   /// Builds the finalized case objects.
   void getCases(Cases& TheCases) {
     CRSMap TheCRSMap;
@@ -197,7 +253,7 @@ public:
   
   /// Builds the finalized case objects ignoring successor values, as though
   /// all ranges belongs to the same successor.
-  IntegersSubset getCase() {
+  IntegersSubsetTy getCase() {
     RangesCollection Ranges;
     for (RangeIterator i = this->begin(); i != this->end(); ++i)
       Ranges.push_back(i->first);
@@ -207,6 +263,13 @@ public:
   /// Returns true if there is no ranges and values inside.
   bool empty() const { return Items.empty(); }
   
+  void clear() {
+    Items.clear();
+    // Don't reset Sorted flag:
+    // 1. For empty mapping it matters nothing.
+    // 2. After first item will added Sorted flag will cleared.
+  }  
+  
   RangeIterator begin() { return Items.begin(); }
   RangeIterator end() { return Items.end(); }
 };