X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSparseBitVector.h;h=dabcb028e99868660285aff61415b7c9bee004ff;hb=76d38384542e2f596e14eb8e80b8e1c6a2652fd1;hp=fe63f9f24717e62dd4da886515b27d8eb9d664a4;hpb=729bd28f62d83c9681702264a79c4ab03c7c11ec;p=oota-llvm.git

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index fe63f9f2471..dabcb028e99 100644
--- 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.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -17,11 +17,11 @@
 
 #include <cassert>
 #include <cstring>
-#include <algorithm>
 #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
@@ -39,7 +39,8 @@ namespace llvm {
 
 
 template <unsigned ElementSize = 128>
-struct SparseBitVectorElement {
+struct SparseBitVectorElement
+  : ilist_node<SparseBitVectorElement<ElementSize> > {
 public:
   typedef unsigned long BitWord;
   enum {
@@ -48,48 +49,23 @@ public:
     BITS_PER_ELEMENT = ElementSize
   };
 
-  SparseBitVectorElement<ElementSize> *getNext() const {
-    return Next;
-  }
-  SparseBitVectorElement<ElementSize> *getPrev() const {
-    return Prev;
-  }
-
-  void setNext(SparseBitVectorElement<ElementSize> *RHS) {
-    Next = RHS;
-  }
-  void setPrev(SparseBitVectorElement<ElementSize> *RHS) {
-    Prev = RHS;
-  }
-
 private:
-  SparseBitVectorElement<ElementSize> *Next;
-  SparseBitVectorElement<ElementSize> *Prev;
   // Index of Element in terms of where first bit starts.
   unsigned ElementIndex;
   BitWord Bits[BITWORDS_PER_ELEMENT];
   // Needed for sentinels
+  friend class ilist_sentinel_traits<SparseBitVectorElement>;
   SparseBitVectorElement() {
-    ElementIndex = ~0UL;
+    ElementIndex = ~0U;
     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
   }
 
-  friend struct ilist_traits<SparseBitVectorElement<ElementSize> >;
 public:
   explicit SparseBitVectorElement(unsigned Idx) {
     ElementIndex = Idx;
     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
   }
 
-  ~SparseBitVectorElement() {
-  }
-
-  // Copy ctor.
-  SparseBitVectorElement(const SparseBitVectorElement &RHS) {
-    ElementIndex = RHS.ElementIndex;
-    std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
-  }
-
   // Comparison.
   bool operator==(const SparseBitVectorElement &RHS) const {
     if (ElementIndex != RHS.ElementIndex)
@@ -166,6 +142,7 @@ public:
           assert(0 && "Unsupported!");
       }
     assert(0 && "Illegal empty element");
+    return 0; // Not reached
   }
 
   /// find_next - Returns the index of the next set bit starting from the
@@ -483,6 +460,26 @@ public:
     CurrElementIter = Elements.begin ();
   }
 
+  // Clear.
+  void clear() {
+    Elements.clear();
+  }
+
+  // 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) {
     if (Elements.empty())
@@ -614,8 +611,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;
@@ -654,8 +653,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;
@@ -689,6 +690,7 @@ public:
                                const SparseBitVector<ElementSize> &RHS2)
   {
     Elements.clear();
+    CurrElementIter = Elements.begin();
     ElementListConstIter Iter1 = RHS1.Elements.begin();
     ElementListConstIter Iter2 = RHS2.Elements.begin();
 
@@ -732,7 +734,6 @@ public:
         ++Iter1;
       }
 
-    CurrElementIter = Elements.begin();
     return;
   }
 
@@ -840,7 +841,36 @@ inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 template <unsigned ElementSize>
 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
                         const SparseBitVector<ElementSize> *RHS) {
-  return LHS &= (*RHS);
+  return LHS &= *RHS;
+}
+
+// Convenience functions for infix union, intersection, difference operators.
+
+template <unsigned ElementSize>
+inline SparseBitVector<ElementSize>
+operator|(const SparseBitVector<ElementSize> &LHS,
+          const SparseBitVector<ElementSize> &RHS) {
+  SparseBitVector<ElementSize> Result(LHS);
+  Result |= RHS;
+  return Result;
+}
+
+template <unsigned ElementSize>
+inline SparseBitVector<ElementSize>
+operator&(const SparseBitVector<ElementSize> &LHS,
+          const SparseBitVector<ElementSize> &RHS) {
+  SparseBitVector<ElementSize> Result(LHS);
+  Result &= RHS;
+  return Result;
+}
+
+template <unsigned ElementSize>
+inline SparseBitVector<ElementSize>
+operator-(const SparseBitVector<ElementSize> &LHS,
+          const SparseBitVector<ElementSize> &RHS) {
+  SparseBitVector<ElementSize> Result;
+  Result.intersectWithComplement(LHS, RHS);
+  return Result;
 }
 
 
@@ -853,10 +883,8 @@ void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) {
   for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
     out << *bi << " ";
   }
-    out << " ]\n";
-}
+  out << " ]\n";
 }
-
-
+} // end namespace llvm
 
 #endif