//
// 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 <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
template <unsigned ElementSize = 128>
-struct SparseBitVectorElement {
+struct SparseBitVectorElement
+ : ilist_node<SparseBitVectorElement<ElementSize> > {
public:
typedef unsigned long BitWord;
enum {
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)
bool test_and_set (unsigned Idx) {
bool old = test(Idx);
- if (!old)
+ if (!old) {
set(Idx);
- return !old;
+ return true;
+ }
+ return false;
}
void reset(unsigned Idx) {
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");
BitWord old = changed ? 0 : Bits[i];
Bits[i] |= RHS.Bits[i];
- if (old != Bits[i])
+ if (!changed && old != Bits[i])
changed = true;
}
return changed;
if (Bits[i] != 0)
allzero = false;
- if (old != Bits[i])
+ if (!changed && old != Bits[i])
changed = true;
}
- BecameZero = !allzero;
+ BecameZero = allzero;
return changed;
}
// Intersect this Element with the complement of RHS and return true if this
// one changed. BecameZero is set to true if this element became all-zero
// bits.
bool intersectWithComplement(const SparseBitVectorElement &RHS,
- bool &BecameZero) {
+ bool &BecameZero) {
bool changed = false;
bool allzero = true;
if (Bits[i] != 0)
allzero = false;
- if (old != Bits[i])
+ if (!changed && old != Bits[i])
changed = true;
}
- BecameZero = !allzero;
+ BecameZero = allzero;
return changed;
}
// Three argument version of intersectWithComplement that intersects
if (Bits[i] != 0)
allzero = false;
}
- BecameZero = !allzero;
+ BecameZero = allzero;
+ }
+
+ // Get a hash value for this element;
+ uint64_t getHashValue() const {
+ uint64_t HashVal = 0;
+ for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
+ HashVal ^= Bits[i];
+ }
+ return HashVal;
}
};
--ElementIter;
} else {
while (ElementIter != Elements.end() &&
- ElementIter->index() <= ElementIndex)
+ ElementIter->index() < ElementIndex)
++ElementIter;
- --ElementIter;
}
CurrElementIter = ElementIter;
return ElementIter;
WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
Bits = Iter->word(WordNumber);
Bits >>= NextSetBitNumber % BITWORD_SIZE;
+ BitNumber = Iter->index() * ElementSize;
+ BitNumber += NextSetBitNumber;
}
}
}
bool operator==(const SparseBitVectorIterator &RHS) const {
// If they are both at the end, ignore the rest of the fields.
- if (AtEnd == RHS.AtEnd)
+ if (AtEnd && RHS.AtEnd)
return true;
// Otherwise they are the same if they have the same bit number and
// bitmap.
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())
if (ElementIter == Elements.end() ||
ElementIter->index() != ElementIndex) {
Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
- // Insert does insert before, and lower bound gives the one before.
- ElementIter = Elements.insert(++ElementIter, Element);
+ // We may have hit the beginning of our SparseBitVector, in which case,
+ // we may need to insert right after this element, which requires moving
+ // the current iterator forward one, because insert does insert before.
+ if (ElementIter != Elements.end() &&
+ ElementIter->index() < ElementIndex)
+ ElementIter = Elements.insert(++ElementIter, Element);
+ else
+ ElementIter = Elements.insert(ElementIter, Element);
}
}
+ CurrElementIter = ElementIter;
+
ElementIter->set(Idx % ElementSize);
}
bool test_and_set (unsigned Idx) {
bool old = test(Idx);
- if (!old)
+ if (!old) {
set(Idx);
- return !old;
+ return true;
+ }
+ return false;
+ }
+
+ bool operator!=(const SparseBitVector &RHS) const {
+ return !(*this == RHS);
+ }
+
+ bool operator==(const SparseBitVector &RHS) const {
+ ElementListConstIter Iter1 = Elements.begin();
+ ElementListConstIter Iter2 = RHS.Elements.begin();
+
+ for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
+ ++Iter1, ++Iter2) {
+ if (*Iter1 != *Iter2)
+ return false;
+ }
+ return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
}
// Union our bitmap with the RHS and return true if we changed.
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;
- // See if the first bitmap element is the same in both. This is only
- // possible if they are the same bitmap.
- if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
- if (*Iter1 == *Iter2)
- return false;
-
while (Iter2 != RHS.Elements.end()) {
if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
Elements.insert(Iter1,
if (Elements.empty() && RHS.Elements.empty())
return false;
- // See if the first bitmap element is the same in both. This is only
- // possible if they are the same bitmap.
- if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
- if (*Iter1 == *Iter2)
- 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;
changed |= Iter1->intersectWith(*Iter2, BecameZero);
if (BecameZero) {
ElementListIter IterTmp = Iter1;
+ ++Iter1;
Elements.erase(IterTmp);
+ } else {
+ ++Iter1;
}
- ++Iter1;
++Iter2;
} else {
ElementListIter IterTmp = Iter1;
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;
- // See if the first bitmap element is the same in both. This is only
- // possible if they are the same bitmap.
- if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
- if (*Iter1 == *Iter2) {
- Elements.clear();
- return true;
- }
-
// 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;
changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
if (BecameZero) {
ElementListIter IterTmp = Iter1;
+ ++Iter1;
Elements.erase(IterTmp);
+ } else {
+ ++Iter1;
}
- ++Iter1;
++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;
- // See if the first bitmap element is the same in both. This is only
- // possible if they are the same bitmap.
- if (Iter1 != RHS1.Elements.end() && Iter2 != RHS2.Elements.end())
- if (*Iter1 == *Iter2) {
- return;
- }
-
// Loop through, intersecting as we go, erasing elements when necessary.
while (Iter2 != RHS2.Elements.end()) {
if (Iter1 == RHS1.Elements.end())
}
else
delete NewElement;
-
++Iter1;
++Iter2;
} else {
+ SparseBitVectorElement<ElementSize> *NewElement =
+ new SparseBitVectorElement<ElementSize>(*Iter1);
+ Elements.push_back(NewElement);
++Iter1;
}
}
++Iter1;
}
- CurrElementIter = Elements.begin();
return;
}
if (Elements.empty() && RHS.Elements.empty())
return false;
- // See if the first bitmap element is the same in both. This is only
- // possible if they are the same bitmap.
- if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
- if (*Iter1 == *Iter2) {
- return true;
- }
-
// Loop through, intersecting stopping when we hit bits in common.
while (Iter2 != RHS.Elements.end()) {
if (Iter1 == Elements.end())
}
iterator end() const {
- return iterator(this, ~0);
+ return iterator(this, true);
}
+ // Get a hash value for this bitmap.
+ uint64_t getHashValue() const {
+ uint64_t HashVal = 0;
+ for (ElementListConstIter Iter = Elements.begin();
+ Iter != Elements.end();
+ ++Iter) {
+ HashVal ^= Iter->index();
+ HashVal ^= Iter->getHashValue();
+ }
+ return HashVal;
+ }
};
// Convenience functions to allow Or and And without dereferencing in the user
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;
+}
+
// Dump a SparseBitVector to a stream
template <unsigned ElementSize>
for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
out << *bi << " ";
}
- out << "\n";
-}
-
+ out << " ]\n";
}
+} // end namespace llvm
#endif
projects / oota-llvm.git / blobdiff