Use vector for child storage instead of map. This will also make

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

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index b02eb3e48059762f89c412ca632ba7b67ce582b7..8dbf0c7001f7988ef7d8519f2256c284a164f162 100644 (file)
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -168,15 +168,14 @@ public:
     assert(0 && "Illegal empty element");
   }
 
-  /// find_next - Returns the index of the next set bit following the
-  /// "Prev" bit. Returns -1 if the next set bit is not found.
-  int find_next(unsigned Prev) const {
-    ++Prev;
-    if (Prev >= BITS_PER_ELEMENT)
+  /// find_next - Returns the index of the next set bit starting from the
+  /// "Curr" bit. Returns -1 if the next set bit is not found.
+  int find_next(unsigned Curr) const {
+    if (Curr >= BITS_PER_ELEMENT)
       return -1;
 
-    unsigned WordPos = Prev / BITWORD_SIZE;
-    unsigned BitPos = Prev % BITWORD_SIZE;
+    unsigned WordPos = Curr / BITWORD_SIZE;
+    unsigned BitPos = Curr % BITWORD_SIZE;
     BitWord Copy = Bits[WordPos];
     assert (WordPos <= BITWORDS_PER_ELEMENT
             && "Word Position outside of element");
@@ -546,7 +545,7 @@ public:
       }
     }
     CurrElementIter = ElementIter;
-      
+
     ElementIter->set(Idx % ElementSize);
   }
 
@@ -581,8 +580,8 @@ public:
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
 
-    // Check if both bitmaps are empty
-    if (Elements.empty() && RHS.Elements.empty())
+    // If RHS is empty, we are done
+    if (RHS.Elements.empty())
       return false;
 
     while (Iter2 != RHS.Elements.end()) {
@@ -615,8 +614,10 @@ public:
 
     // Loop through, intersecting as we go, erasing elements when necessary.
     while (Iter2 != RHS.Elements.end()) {
-      if (Iter1 == Elements.end())
+      if (Iter1 == Elements.end()) {
+        CurrElementIter = Elements.begin();
         return changed;
+      }
 
       if (Iter1->index() > Iter2->index()) {
         ++Iter2;
@@ -649,14 +650,16 @@ public:
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
 
-    // Check if they are both empty
-    if (Elements.empty() && RHS.Elements.empty())
+    // If either our bitmap or RHS is empty, we are done
+    if (Elements.empty() || RHS.Elements.empty())
       return false;
 
     // Loop through, intersecting as we go, erasing elements when necessary.
     while (Iter2 != RHS.Elements.end()) {
-      if (Iter1 == Elements.end())
+      if (Iter1 == Elements.end()) {
+        CurrElementIter = Elements.begin();
         return changed;
+      }
 
       if (Iter1->index() > Iter2->index()) {
         ++Iter2;
@@ -672,9 +675,7 @@ public:
         }
         ++Iter2;
       } else {
-        ElementListIter IterTmp = Iter1;
         ++Iter1;
-        Elements.erase(IterTmp);
       }
     }
     CurrElementIter = Elements.begin();
@@ -692,11 +693,13 @@ public:
                                const SparseBitVector<ElementSize> &RHS2)
   {
     Elements.clear();
+    CurrElementIter = Elements.begin();
     ElementListConstIter Iter1 = RHS1.Elements.begin();
     ElementListConstIter Iter2 = RHS2.Elements.begin();
 
-    // Check if they are both empty.
-    if (RHS1.empty() && RHS2.empty())
+    // If RHS1 is empty, we are done
+    // If RHS2 is empty, we still have to copy RHS1
+    if (RHS1.Elements.empty())
       return;
 
     // Loop through, intersecting as we go, erasing elements when necessary.
@@ -719,6 +722,9 @@ public:
         ++Iter1;
         ++Iter2;
       } else {
+        SparseBitVectorElement<ElementSize> *NewElement =
+          new SparseBitVectorElement<ElementSize>(*Iter1);
+        Elements.push_back(NewElement);
         ++Iter1;
       }
     }
@@ -731,7 +737,6 @@ public:
         ++Iter1;
       }
 
-    CurrElementIter = Elements.begin();
     return;
   }
 
@@ -799,7 +804,7 @@ public:
   }
 
   iterator end() const {
-    return iterator(this, ~0);
+    return iterator(this, true);
   }
 
   // Get a hash value for this bitmap.