summaryrefslogtreecommitdiff
path: root/Source/WTF/wtf/FastBitVector.h
diff options
context:
space:
mode:
authorLorry Tar Creator <lorry-tar-importer@lorry>2017-06-27 06:07:23 +0000
committerLorry Tar Creator <lorry-tar-importer@lorry>2017-06-27 06:07:23 +0000
commit1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c (patch)
tree46dcd36c86e7fbc6e5df36deb463b33e9967a6f7 /Source/WTF/wtf/FastBitVector.h
parent32761a6cee1d0dee366b885b7b9c777e67885688 (diff)
downloadWebKitGtk-tarball-master.tar.gz
Diffstat (limited to 'Source/WTF/wtf/FastBitVector.h')
-rw-r--r--Source/WTF/wtf/FastBitVector.h561
1 files changed, 473 insertions, 88 deletions
diff --git a/Source/WTF/wtf/FastBitVector.h b/Source/WTF/wtf/FastBitVector.h
index f96180d9e..9119a1d51 100644
--- a/Source/WTF/wtf/FastBitVector.h
+++ b/Source/WTF/wtf/FastBitVector.h
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2012, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2012, 2013, 2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -23,173 +23,558 @@
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#ifndef FastBitVector_h
-#define FastBitVector_h
+#pragma once
#include <string.h>
+#include <wtf/Atomics.h>
#include <wtf/FastMalloc.h>
+#include <wtf/PrintStream.h>
#include <wtf/StdLibExtras.h>
namespace WTF {
class PrintStream;
-class FastBitVector {
+inline size_t fastBitVectorArrayLength(size_t numBits) { return (numBits + 31) / 32; }
+
+class FastBitVectorWordView {
public:
- FastBitVector()
- : m_array(0)
- , m_numBits(0)
+ typedef FastBitVectorWordView ViewType;
+
+ FastBitVectorWordView() { }
+
+ FastBitVectorWordView(const uint32_t* array, size_t numBits)
+ : m_words(array)
+ , m_numBits(numBits)
{
}
- FastBitVector(const FastBitVector& other)
- : m_array(0)
- , m_numBits(0)
+ size_t numBits() const
+ {
+ return m_numBits;
+ }
+
+ uint32_t word(size_t index) const
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(index < fastBitVectorArrayLength(numBits()));
+ return m_words[index];
+ }
+
+private:
+ const uint32_t* m_words { nullptr };
+ size_t m_numBits { 0 };
+};
+
+class FastBitVectorWordOwner {
+public:
+ typedef FastBitVectorWordView ViewType;
+
+ FastBitVectorWordOwner() = default;
+
+ FastBitVectorWordOwner(FastBitVectorWordOwner&& other)
+ : m_words(std::exchange(other.m_words, nullptr))
+ , m_numBits(std::exchange(other.m_numBits, 0))
+ {
+ }
+
+ FastBitVectorWordOwner(const FastBitVectorWordOwner& other)
{
*this = other;
}
- ~FastBitVector()
+ ~FastBitVectorWordOwner()
{
- if (m_array)
- fastFree(m_array);
+ if (m_words)
+ fastFree(m_words);
}
- FastBitVector& operator=(const FastBitVector& other)
+ FastBitVectorWordView view() const { return FastBitVectorWordView(m_words, m_numBits); }
+
+ FastBitVectorWordOwner& operator=(const FastBitVectorWordOwner& other)
{
- size_t length = other.arrayLength();
- uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(length, 4));
- memcpy(newArray, other.m_array, length * 4);
- if (m_array)
- fastFree(m_array);
- m_array = newArray;
- m_numBits = other.m_numBits;
+ if (arrayLength() != other.arrayLength())
+ setEqualsSlow(other);
+ else {
+ memcpy(m_words, other.m_words, arrayLength() * sizeof(uint32_t));
+ m_numBits = other.m_numBits;
+ }
return *this;
}
- size_t numBits() const { return m_numBits; }
+ FastBitVectorWordOwner& operator=(FastBitVectorWordOwner&& other)
+ {
+ std::swap(m_words, other.m_words);
+ std::swap(m_numBits, other.m_numBits);
+ return *this;
+ }
+
+ void setAll()
+ {
+ memset(m_words, 255, arrayLength() * sizeof(uint32_t));
+ }
+
+ void clearAll()
+ {
+ memset(m_words, 0, arrayLength() * sizeof(uint32_t));
+ }
+
+ void set(const FastBitVectorWordOwner& other)
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(m_numBits == other.m_numBits);
+ memcpy(m_words, other.m_words, arrayLength() * sizeof(uint32_t));
+ }
+
+ size_t numBits() const
+ {
+ return m_numBits;
+ }
+
+ size_t arrayLength() const
+ {
+ return fastBitVectorArrayLength(numBits());
+ }
void resize(size_t numBits)
{
- // Use fastCalloc instead of fastRealloc because we expect the common
- // use case for this method to be initializing the size of the bitvector.
-
- size_t newLength = arrayLength(numBits);
- uint32_t* newArray = static_cast<uint32_t*>(fastCalloc(newLength, 4));
- memcpy(newArray, m_array, arrayLength() * 4);
- if (m_array)
- fastFree(m_array);
- m_array = newArray;
+ if (arrayLength() != fastBitVectorArrayLength(numBits))
+ resizeSlow(numBits);
m_numBits = numBits;
}
- void setAll()
+ uint32_t word(size_t index) const
{
- memset(m_array, 255, arrayLength() * 4);
+ ASSERT_WITH_SECURITY_IMPLICATION(index < arrayLength());
+ return m_words[index];
}
- void clearAll()
+ uint32_t& word(size_t index)
{
- memset(m_array, 0, arrayLength() * 4);
+ ASSERT_WITH_SECURITY_IMPLICATION(index < arrayLength());
+ return m_words[index];
}
- void set(const FastBitVector& other)
+ const uint32_t* words() const { return m_words; }
+ uint32_t* words() { return m_words; }
+
+private:
+ WTF_EXPORT_PRIVATE void setEqualsSlow(const FastBitVectorWordOwner& other);
+ WTF_EXPORT_PRIVATE void resizeSlow(size_t numBits);
+
+ uint32_t* m_words { nullptr };
+ size_t m_numBits { 0 };
+};
+
+template<typename Left, typename Right>
+class FastBitVectorAndWords {
+public:
+ typedef FastBitVectorAndWords ViewType;
+
+ FastBitVectorAndWords(const Left& left, const Right& right)
+ : m_left(left)
+ , m_right(right)
{
- ASSERT(m_numBits == other.m_numBits);
- memcpy(m_array, other.m_array, arrayLength() * 4);
+ ASSERT_WITH_SECURITY_IMPLICATION(m_left.numBits() == m_right.numBits());
}
- bool setAndCheck(const FastBitVector& other)
+ FastBitVectorAndWords view() const { return *this; }
+
+ size_t numBits() const
{
- bool changed = false;
- ASSERT(m_numBits == other.m_numBits);
- for (unsigned i = arrayLength(); i--;) {
- changed |= m_array[i] != other.m_array[i];
- m_array[i] = other.m_array[i];
+ return m_left.numBits();
+ }
+
+ uint32_t word(size_t index) const
+ {
+ return m_left.word(index) & m_right.word(index);
+ }
+
+private:
+ Left m_left;
+ Right m_right;
+};
+
+template<typename Left, typename Right>
+class FastBitVectorOrWords {
+public:
+ typedef FastBitVectorOrWords ViewType;
+
+ FastBitVectorOrWords(const Left& left, const Right& right)
+ : m_left(left)
+ , m_right(right)
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(m_left.numBits() == m_right.numBits());
+ }
+
+ FastBitVectorOrWords view() const { return *this; }
+
+ size_t numBits() const
+ {
+ return m_left.numBits();
+ }
+
+ uint32_t word(size_t index) const
+ {
+ return m_left.word(index) | m_right.word(index);
+ }
+
+private:
+ Left m_left;
+ Right m_right;
+};
+
+template<typename View>
+class FastBitVectorNotWords {
+public:
+ typedef FastBitVectorNotWords ViewType;
+
+ FastBitVectorNotWords(const View& view)
+ : m_view(view)
+ {
+ }
+
+ FastBitVectorNotWords view() const { return *this; }
+
+ size_t numBits() const
+ {
+ return m_view.numBits();
+ }
+
+ uint32_t word(size_t index) const
+ {
+ return ~m_view.word(index);
+ }
+
+private:
+ View m_view;
+};
+
+class FastBitVector;
+
+template<typename Words>
+class FastBitVectorImpl {
+public:
+ FastBitVectorImpl()
+ : m_words()
+ {
+ }
+
+ FastBitVectorImpl(const Words& words)
+ : m_words(words)
+ {
+ }
+
+ FastBitVectorImpl(Words&& words)
+ : m_words(WTFMove(words))
+ {
+ }
+
+ size_t numBits() const { return m_words.numBits(); }
+ size_t size() const { return numBits(); }
+
+ size_t arrayLength() const { return fastBitVectorArrayLength(numBits()); }
+
+ template<typename Other>
+ bool operator==(const Other& other) const
+ {
+ if (numBits() != other.numBits())
+ return false;
+ for (size_t i = arrayLength(); i--;) {
+ if (m_words.word(i) != other.m_words.word(i))
+ return false;
}
- return changed;
+ return true;
}
- bool equals(const FastBitVector& other) const
+ template<typename Other>
+ bool operator!=(const Other& other) const
{
- ASSERT(m_numBits == other.m_numBits);
- // Use my own comparison loop because memcmp does more than what I want
- // and bcmp is not as standard.
- for (unsigned i = arrayLength(); i--;) {
- if (m_array[i] != other.m_array[i])
+ return !(*this == other);
+ }
+
+ bool at(size_t index) const
+ {
+ return atImpl(index);
+ }
+
+ bool operator[](size_t index) const
+ {
+ return atImpl(index);
+ }
+
+ size_t bitCount() const
+ {
+ size_t result = 0;
+ for (size_t index = arrayLength(); index--;)
+ result += WTF::bitCount(m_words.word(index));
+ return result;
+ }
+
+ bool isEmpty() const
+ {
+ for (size_t index = arrayLength(); index--;) {
+ if (m_words.word(index))
return false;
}
return true;
}
- void merge(const FastBitVector& other)
+ template<typename OtherWords>
+ FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>> operator&(const FastBitVectorImpl<OtherWords>& other) const
{
- ASSERT(m_numBits == other.m_numBits);
- for (unsigned i = arrayLength(); i--;)
- m_array[i] |= other.m_array[i];
+ return FastBitVectorImpl<FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorAndWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
}
- void filter(const FastBitVector& other)
+ template<typename OtherWords>
+ FastBitVectorImpl<FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>> operator|(const FastBitVectorImpl<OtherWords>& other) const
{
- ASSERT(m_numBits == other.m_numBits);
- for (unsigned i = arrayLength(); i--;)
- m_array[i] &= other.m_array[i];
+ return FastBitVectorImpl<FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>>(FastBitVectorOrWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
}
- void exclude(const FastBitVector& other)
+ FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>> operator~() const
{
- ASSERT(m_numBits == other.m_numBits);
- for (unsigned i = arrayLength(); i--;)
- m_array[i] &= ~other.m_array[i];
+ return FastBitVectorImpl<FastBitVectorNotWords<typename Words::ViewType>>(FastBitVectorNotWords<typename Words::ViewType>(wordView()));
}
- void set(size_t i)
+ template<typename Func>
+ ALWAYS_INLINE void forEachSetBit(const Func& func) const
{
- ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
- m_array[i >> 5] |= (1 << (i & 31));
+ size_t n = arrayLength();
+ for (size_t i = 0; i < n; ++i) {
+ uint32_t word = m_words.word(i);
+ size_t j = i * 32;
+ while (word) {
+ if (word & 1)
+ func(j);
+ word >>= 1;
+ j++;
+ }
+ }
}
- void clear(size_t i)
+ template<typename Func>
+ ALWAYS_INLINE void forEachClearBit(const Func& func) const
{
- ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
- m_array[i >> 5] &= ~(1 << (i & 31));
+ (~*this).forEachSetBit(func);
}
- void set(size_t i, bool value)
+ template<typename Func>
+ void forEachBit(bool value, const Func& func) const
{
if (value)
- set(i);
+ forEachSetBit(func);
else
- clear(i);
+ forEachClearBit(func);
}
- bool get(size_t i) const
+ // Starts looking for bits at the index you pass. If that index contains the value you want,
+ // then it will return that index. Returns numBits when we get to the end. For example, you
+ // can write a loop to iterate over all set bits like this:
+ //
+ // for (size_t i = 0; i < bits.numBits(); i = bits.findBit(i + 1, true))
+ // ...
+ ALWAYS_INLINE size_t findBit(size_t startIndex, bool value) const
{
- ASSERT_WITH_SECURITY_IMPLICATION(i < m_numBits);
- return !!(m_array[i >> 5] & (1 << (i & 31)));
+ // If value is true, this produces 0. If value is false, this produces UINT_MAX. It's
+ // written this way so that it performs well regardless of whether value is a constant.
+ uint32_t skipValue = -(static_cast<uint32_t>(value) ^ 1);
+
+ size_t numWords = fastBitVectorArrayLength(m_words.numBits());
+
+ size_t wordIndex = startIndex / 32;
+ size_t startIndexInWord = startIndex - wordIndex * 32;
+
+ while (wordIndex < numWords) {
+ uint32_t word = m_words.word(wordIndex);
+ if (word != skipValue) {
+ size_t index = startIndexInWord;
+ if (findBitInWord(word, index, 32, value))
+ return wordIndex * 32 + index;
+ }
+
+ wordIndex++;
+ startIndexInWord = 0;
+ }
+
+ return numBits();
}
- size_t bitCount() const
+ ALWAYS_INLINE size_t findSetBit(size_t index) const
{
- size_t result = 0;
- for (unsigned i = arrayLength(); i--;)
- result += WTF::bitCount(m_array[i]);
- return result;
+ return findBit(index, true);
+ }
+
+ ALWAYS_INLINE size_t findClearBit(size_t index) const
+ {
+ return findBit(index, false);
+ }
+
+ void dump(PrintStream& out) const
+ {
+ for (size_t i = 0; i < numBits(); ++i)
+ out.print((*this)[i] ? "1" : "-");
}
- WTF_EXPORT_PRIVATE void dump(PrintStream&) const;
+ typename Words::ViewType wordView() const { return m_words.view(); }
private:
- static size_t arrayLength(size_t numBits) { return (numBits + 31) >> 5; }
- size_t arrayLength() const { return arrayLength(m_numBits); }
+ // You'd think that we could remove this friend if we used protected, but you'd be wrong,
+ // because templates.
+ friend class FastBitVector;
+
+ bool atImpl(size_t index) const
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(index < numBits());
+ return !!(m_words.word(index >> 5) & (1 << (index & 31)));
+ }
- uint32_t* m_array; // No, this can't be an std::unique_ptr<uint32_t[]>.
- size_t m_numBits;
+ Words m_words;
};
-} // namespace WTF
+class FastBitVector : public FastBitVectorImpl<FastBitVectorWordOwner> {
+public:
+ FastBitVector() { }
+
+ FastBitVector(const FastBitVector&) = default;
+ FastBitVector& operator=(const FastBitVector&) = default;
+
+ template<typename OtherWords>
+ FastBitVector(const FastBitVectorImpl<OtherWords>& other)
+ {
+ *this = other;
+ }
+
+ template<typename OtherWords>
+ FastBitVector& operator=(const FastBitVectorImpl<OtherWords>& other)
+ {
+ if (UNLIKELY(numBits() != other.numBits()))
+ resize(other.numBits());
+
+ for (unsigned i = arrayLength(); i--;)
+ m_words.word(i) = other.m_words.word(i);
+ return *this;
+ }
+
+ void resize(size_t numBits)
+ {
+ m_words.resize(numBits);
+ }
+
+ void setAll()
+ {
+ m_words.setAll();
+ }
+
+ void clearAll()
+ {
+ m_words.clearAll();
+ }
+
+ WTF_EXPORT_PRIVATE void clearRange(size_t begin, size_t end);
-using WTF::FastBitVector;
+ // Returns true if the contents of this bitvector changed.
+ template<typename OtherWords>
+ bool setAndCheck(const FastBitVectorImpl<OtherWords>& other)
+ {
+ bool changed = false;
+ ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
+ for (unsigned i = arrayLength(); i--;) {
+ changed |= m_words.word(i) != other.m_words.word(i);
+ m_words.word(i) = other.m_words.word(i);
+ }
+ return changed;
+ }
+
+ template<typename OtherWords>
+ FastBitVector& operator|=(const FastBitVectorImpl<OtherWords>& other)
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
+ for (unsigned i = arrayLength(); i--;)
+ m_words.word(i) |= other.m_words.word(i);
+ return *this;
+ }
+
+ template<typename OtherWords>
+ FastBitVector& operator&=(const FastBitVectorImpl<OtherWords>& other)
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(numBits() == other.numBits());
+ for (unsigned i = arrayLength(); i--;)
+ m_words.word(i) &= other.m_words.word(i);
+ return *this;
+ }
+
+ bool at(size_t index) const
+ {
+ return atImpl(index);
+ }
+
+ bool operator[](size_t index) const
+ {
+ return atImpl(index);
+ }
+
+ class BitReference {
+ public:
+ BitReference() { }
+
+ BitReference(uint32_t* word, uint32_t mask)
+ : m_word(word)
+ , m_mask(mask)
+ {
+ }
+
+ explicit operator bool() const
+ {
+ return !!(*m_word & m_mask);
+ }
+
+ BitReference& operator=(bool value)
+ {
+ if (value)
+ *m_word |= m_mask;
+ else
+ *m_word &= ~m_mask;
+ return *this;
+ }
+
+ private:
+ uint32_t* m_word { nullptr };
+ uint32_t m_mask { 0 };
+ };
+
+ BitReference at(size_t index)
+ {
+ ASSERT_WITH_SECURITY_IMPLICATION(index < numBits());
+ return BitReference(&m_words.word(index >> 5), 1 << (index & 31));
+ }
+
+ BitReference operator[](size_t index)
+ {
+ return at(index);
+ }
+
+ // Returns true if the contents changed.
+ ALWAYS_INLINE bool atomicSetAndCheck(size_t index, bool value)
+ {
+ uint32_t* pointer = &m_words.word(index >> 5);
+ uint32_t mask = 1 << (index & 31);
+ for (;;) {
+ uint32_t oldValue = *pointer;
+ uint32_t newValue;
+ if (value) {
+ if (oldValue & mask)
+ return false;
+ newValue = oldValue | mask;
+ } else {
+ if (!(oldValue & mask))
+ return false;
+ newValue = oldValue & ~mask;
+ }
+ if (atomicCompareExchangeWeakRelaxed(pointer, oldValue, newValue))
+ return true;
+ }
+ }
+};
-#endif // FastBitVector_h
+} // namespace WTF
+using WTF::FastBitVector;