//
// 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.
//
//===----------------------------------------------------------------------===//
//
#ifndef LLVM_ADT_SPARSEBITVECTOR_H
#define LLVM_ADT_SPARSEBITVECTOR_H
-#include <cassert>
-#include <cstring>
-#include <algorithm>
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
#include "llvm/Support/DataTypes.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
-#include "llvm/ADT/ilist"
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+#include <climits>
+
namespace llvm {
/// SparseBitVector is an implementation of a bitvector that is sparse by only
template <unsigned ElementSize = 128>
-struct SparseBitVectorElement {
+struct SparseBitVectorElement
+ : public ilist_node<SparseBitVectorElement<ElementSize> > {
public:
typedef unsigned long BitWord;
+ typedef unsigned size_type;
enum {
- BITWORD_SIZE = sizeof(BitWord) * 8,
+ BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
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 struct 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)
return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
}
- unsigned count() const {
+ size_type count() const {
unsigned NumBits = 0;
for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
if (sizeof(BitWord) == 4)
else if (sizeof(BitWord) == 8)
NumBits += CountPopulation_64(Bits[i]);
else
- assert(0 && "Unsupported!");
+ llvm_unreachable("Unsupported!");
return NumBits;
}
for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
if (Bits[i] != 0) {
if (sizeof(BitWord) == 4)
- return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
- else if (sizeof(BitWord) == 8)
- return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
- else
- assert(0 && "Unsupported!");
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ if (sizeof(BitWord) == 8)
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ llvm_unreachable("Unsupported!");
}
- assert(0 && "Illegal empty element");
+ llvm_unreachable("Illegal empty element");
}
/// find_next - Returns the index of the next set bit starting from the
&& "Word Position outside of element");
// Mask off previous bits.
- Copy &= ~0L << BitPos;
+ Copy &= ~0UL << BitPos;
if (Copy != 0) {
if (sizeof(BitWord) == 4)
- return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
- else if (sizeof(BitWord) == 8)
- return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
- else
- assert(0 && "Unsupported!");
+ return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
+ if (sizeof(BitWord) == 8)
+ return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
+ llvm_unreachable("Unsupported!");
}
// Check subsequent words.
for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
if (Bits[i] != 0) {
if (sizeof(BitWord) == 4)
- return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
- else if (sizeof(BitWord) == 8)
- return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
- else
- assert(0 && "Unsupported!");
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ if (sizeof(BitWord) == 8)
+ return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
+ llvm_unreachable("Unsupported!");
}
return -1;
}
}
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;
- }
+template <unsigned ElementSize>
+struct ilist_traits<SparseBitVectorElement<ElementSize> >
+ : public ilist_default_traits<SparseBitVectorElement<ElementSize> > {
+ typedef SparseBitVectorElement<ElementSize> Element;
+
+ Element *createSentinel() const { return static_cast<Element *>(&Sentinel); }
+ static void destroySentinel(Element *) {}
+
+ Element *provideInitialHead() const { return createSentinel(); }
+ Element *ensureHead(Element *) const { return createSentinel(); }
+ static void noteHead(Element *, Element *) {}
+
+private:
+ mutable ilist_half_node<Element> Sentinel;
};
template <unsigned ElementSize = 128>
AtEnd = true;
return;
}
- // Set up for next non zero word in bitmap.
+ // Set up for next non-zero word in bitmap.
BitNumber = Iter->index() * ElementSize;
NextSetBitNumber = Iter->find_first();
BitNumber += NextSetBitNumber;
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())
// 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;
return changed;
}
- // Intersect our bitmap with the complement of the RHS and return true if ours
- // changed.
+ // Intersect our bitmap with the complement of the RHS and return true
+ // if ours changed.
bool intersectWithComplement(const SparseBitVector &RHS) {
bool changed = false;
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;
}
- // Three argument version of intersectWithComplement. Result of RHS1 & ~RHS2
- // is stored into this bitmap.
+ // Three argument version of intersectWithComplement.
+ // Result of RHS1 & ~RHS2 is stored into this bitmap.
void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
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;
}
return false;
}
+ // Return true iff all bits set in this SparseBitVector are
+ // also set in RHS.
+ bool contains(const SparseBitVector<ElementSize> &RHS) const {
+ SparseBitVector<ElementSize> Result(*this);
+ Result &= RHS;
+ return (Result == RHS);
+ }
+
// Return the first set bit in the bitmap. Return -1 if no bits are set.
int find_first() const {
if (Elements.empty())
}
iterator end() const {
- return iterator(this, ~0);
- }
-
- // 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;
+ return iterator(this, true);
}
};
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.
-// Dump a SparseBitVector to a stream
template <unsigned ElementSize>
-void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) {
- out << "[ ";
+inline SparseBitVector<ElementSize>
+operator|(const SparseBitVector<ElementSize> &LHS,
+ const SparseBitVector<ElementSize> &RHS) {
+ SparseBitVector<ElementSize> Result(LHS);
+ Result |= RHS;
+ return Result;
+}
- typename SparseBitVector<ElementSize>::iterator bi;
- for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
- out << *bi << " ";
- }
- out << " ]\n";
+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>
+void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
+ out << "[";
+
+ typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
+ be = LHS.end();
+ if (bi != be) {
+ out << *bi;
+ for (++bi; bi != be; ++bi) {
+ out << " " << *bi;
+ }
+ }
+ out << "]\n";
+}
+} // end namespace llvm
+
#endif
projects / oota-llvm.git / blobdiff