//
// 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.
//
//===----------------------------------------------------------------------===//
//
#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
BitWord Bits[BITWORDS_PER_ELEMENT];
// Needed for sentinels
SparseBitVectorElement() {
- ElementIndex = ~0UL;
+ ElementIndex = ~0U;
memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
}
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 {
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");
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) {
}
}
CurrElementIter = ElementIter;
-
+
ElementIter->set(Idx % ElementSize);
}
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()) {
// 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;
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;
}
++Iter2;
} else {
- ElementListIter IterTmp = Iter1;
++Iter1;
- Elements.erase(IterTmp);
}
}
CurrElementIter = Elements.begin();
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.
++Iter1;
++Iter2;
} else {
+ SparseBitVectorElement<ElementSize> *NewElement =
+ new SparseBitVectorElement<ElementSize>(*Iter1);
+ Elements.push_back(NewElement);
++Iter1;
}
}
++Iter1;
}
- CurrElementIter = Elements.begin();
return;
}
}
iterator end() const {
- return iterator(this, ~0);
+ return iterator(this, true);
}
// Get a hash value for this bitmap.