Add a new (simple) StringMap::clear method, patch by Pratik

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

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 56db805647e6c7d7eb52df041ade618046dff640..adeb541d3d0acb9a124a7e9b958c452ffc3f4aa9 100644 (file)
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by Daniel Berlin and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -21,7 +21,7 @@
 #include "llvm/Support/DataTypes.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/MathExtras.h"
-#include "llvm/ADT/ilist"
+#include "llvm/ADT/ilist.h"
 namespace llvm {
 
 /// SparseBitVector is an implementation of a bitvector that is sparse by only
@@ -70,7 +70,7 @@ private:
   BitWord Bits[BITWORDS_PER_ELEMENT];
   // Needed for sentinels
   SparseBitVectorElement() {
-    ElementIndex = ~0UL;
+    ElementIndex = ~0U;
     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
   }
 
@@ -89,6 +89,14 @@ public:
     ElementIndex = RHS.ElementIndex;
     std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
   }
+  
+  // Assignment 
+  SparseBitVectorElement& operator=(const SparseBitVectorElement& RHS) {
+    ElementIndex = RHS.ElementIndex;
+    std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
+    
+    return *this;
+  }
 
   // Comparison.
   bool operator==(const SparseBitVectorElement &RHS) const {
@@ -166,17 +174,17 @@ public:
           assert(0 && "Unsupported!");
       }
     assert(0 && "Illegal empty element");
+    return 0; // Not reached
   }
 
-  /// 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");
@@ -390,7 +398,7 @@ class SparseBitVector {
 
       // See if we ran out of Bits in this word.
       if (!Bits) {
-        int NextSetBitNumber = Iter->find_next((BitNumber - 1) % ElementSize) ;
+        int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
         // If we ran out of set bits in this element, move to next element.
         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
           ++Iter;
@@ -483,6 +491,21 @@ public:
 
     CurrElementIter = Elements.begin ();
   }
+  
+  // Assignment
+  SparseBitVector& operator=(const SparseBitVector& RHS) {
+    Elements.clear();
+    
+    ElementListConstIter ElementIter = RHS.Elements.begin();
+    while (ElementIter != RHS.Elements.end()) {
+      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
+      ++ElementIter;
+    }
+
+    CurrElementIter = Elements.begin ();
+    
+    return *this;
+  }
 
   // Test, Reset, and Set a bit in the bitmap.
   bool test(unsigned Idx) {
@@ -546,7 +569,7 @@ public:
       }
     }
     CurrElementIter = ElementIter;
-      
+
     ElementIter->set(Idx % ElementSize);
   }
 
@@ -581,8 +604,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 +638,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 +674,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 +699,7 @@ public:
         }
         ++Iter2;
       } else {
-        ElementListIter IterTmp = Iter1;
         ++Iter1;
-        Elements.erase(IterTmp);
       }
     }
     CurrElementIter = Elements.begin();
@@ -692,11 +717,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 +746,9 @@ public:
         ++Iter1;
         ++Iter2;
       } else {
+        SparseBitVectorElement<ElementSize> *NewElement =
+          new SparseBitVectorElement<ElementSize>(*Iter1);
+        Elements.push_back(NewElement);
         ++Iter1;
       }
     }
@@ -731,7 +761,6 @@ public:
         ++Iter1;
       }
 
-    CurrElementIter = Elements.begin();
     return;
   }
 
@@ -799,7 +828,7 @@ public:
   }
 
   iterator end() const {
-    return iterator(this, ~0);
+    return iterator(this, true);
   }
 
   // Get a hash value for this bitmap.