From 1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c Mon Sep 17 00:00:00 2001 From: Lorry Tar Creator Date: Tue, 27 Jun 2017 06:07:23 +0000 Subject: webkitgtk-2.16.5 --- Source/WTF/wtf/Bitmap.h | 208 +++++++++++++++++++++++++++++++++++------------- 1 file changed, 153 insertions(+), 55 deletions(-) (limited to 'Source/WTF/wtf/Bitmap.h') diff --git a/Source/WTF/wtf/Bitmap.h b/Source/WTF/wtf/Bitmap.h index 7b288f9ed..89b2c9da8 100644 --- a/Source/WTF/wtf/Bitmap.h +++ b/Source/WTF/wtf/Bitmap.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2010 Apple Inc. All rights reserved. + * Copyright (C) 2010, 2016 Apple Inc. All rights reserved. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -27,22 +27,22 @@ namespace WTF { -enum BitmapAtomicMode { - // This makes concurrentTestAndSet behave just like testAndSet. - BitmapNotAtomic, - - // This makes concurrentTestAndSet use compareAndSwap, so that it's - // atomic even when used concurrently. - BitmapAtomic -}; - -template +template class Bitmap { + WTF_MAKE_FAST_ALLOCATED; + + static_assert(sizeof(WordType) <= sizeof(unsigned), "WordType must not be bigger than unsigned"); public: Bitmap(); + static constexpr size_t size() + { + return bitmapSize; + } + bool get(size_t) const; void set(size_t); + void set(size_t, bool); bool testAndSet(size_t); bool testAndClear(size_t); bool concurrentTestAndSet(size_t); @@ -50,14 +50,29 @@ public: size_t nextPossiblyUnset(size_t) const; void clear(size_t); void clearAll(); - int64_t findRunOfZeros(size_t) const; - size_t count(size_t = 0) const; + int64_t findRunOfZeros(size_t runLength) const; + size_t count(size_t start = 0) const; size_t isEmpty() const; size_t isFull() const; + + void merge(const Bitmap&); + void filter(const Bitmap&); + void exclude(const Bitmap&); + + template + void forEachSetBit(const Func&) const; + + void mergeAndClear(Bitmap&); + void setAndClear(Bitmap&); + + bool operator==(const Bitmap&) const; + bool operator!=(const Bitmap&) const; + + unsigned hash() const; private: static const unsigned wordSize = sizeof(WordType) * 8; - static const unsigned words = (size + wordSize - 1) / wordSize; + static const unsigned words = (bitmapSize + wordSize - 1) / wordSize; // the literal '1' is of type signed int. We want to use an unsigned // version of the correct size when doing the calculations because if @@ -69,26 +84,35 @@ private: std::array bits; }; -template -inline Bitmap::Bitmap() +template +inline Bitmap::Bitmap() { clearAll(); } -template -inline bool Bitmap::get(size_t n) const +template +inline bool Bitmap::get(size_t n) const { return !!(bits[n / wordSize] & (one << (n % wordSize))); } -template -inline void Bitmap::set(size_t n) +template +inline void Bitmap::set(size_t n) { bits[n / wordSize] |= (one << (n % wordSize)); } -template -inline bool Bitmap::testAndSet(size_t n) +template +inline void Bitmap::set(size_t n, bool value) +{ + if (value) + set(n); + else + clear(n); +} + +template +inline bool Bitmap::testAndSet(size_t n) { WordType mask = one << (n % wordSize); size_t index = n / wordSize; @@ -97,8 +121,8 @@ inline bool Bitmap::testAndSet(size_t n) return result; } -template -inline bool Bitmap::testAndClear(size_t n) +template +inline bool Bitmap::testAndClear(size_t n) { WordType mask = one << (n % wordSize); size_t index = n / wordSize; @@ -107,14 +131,9 @@ inline bool Bitmap::testAndClear(size_t n) return result; } -template -inline bool Bitmap::concurrentTestAndSet(size_t n) +template +inline bool Bitmap::concurrentTestAndSet(size_t n) { - if (atomicMode == BitmapNotAtomic) - return testAndSet(n); - - ASSERT(atomicMode == BitmapAtomic); - WordType mask = one << (n % wordSize); size_t index = n / wordSize; WordType* wordPtr = bits.data() + index; @@ -123,18 +142,13 @@ inline bool Bitmap::concurrentTestAndSet(size_t n) oldValue = *wordPtr; if (oldValue & mask) return true; - } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue | mask)); + } while (!atomicCompareExchangeWeakRelaxed(wordPtr, oldValue, static_cast(oldValue | mask))); return false; } -template -inline bool Bitmap::concurrentTestAndClear(size_t n) +template +inline bool Bitmap::concurrentTestAndClear(size_t n) { - if (atomicMode == BitmapNotAtomic) - return testAndClear(n); - - ASSERT(atomicMode == BitmapAtomic); - WordType mask = one << (n % wordSize); size_t index = n / wordSize; WordType* wordPtr = bits.data() + index; @@ -143,37 +157,37 @@ inline bool Bitmap::concurrentTestAndClear(size_t n) oldValue = *wordPtr; if (!(oldValue & mask)) return false; - } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue & ~mask)); + } while (!atomicCompareExchangeWeakRelaxed(wordPtr, oldValue, static_cast(oldValue & ~mask))); return true; } -template -inline void Bitmap::clear(size_t n) +template +inline void Bitmap::clear(size_t n) { bits[n / wordSize] &= ~(one << (n % wordSize)); } -template -inline void Bitmap::clearAll() +template +inline void Bitmap::clearAll() { memset(bits.data(), 0, sizeof(bits)); } -template -inline size_t Bitmap::nextPossiblyUnset(size_t start) const +template +inline size_t Bitmap::nextPossiblyUnset(size_t start) const { if (!~bits[start / wordSize]) return ((start / wordSize) + 1) * wordSize; return start + 1; } -template -inline int64_t Bitmap::findRunOfZeros(size_t runLength) const +template +inline int64_t Bitmap::findRunOfZeros(size_t runLength) const { if (!runLength) runLength = 1; - for (size_t i = 0; i <= (size - runLength) ; i++) { + for (size_t i = 0; i <= (bitmapSize - runLength) ; i++) { bool found = true; for (size_t j = i; j <= (i + runLength - 1) ; j++) { if (get(j)) { @@ -187,8 +201,8 @@ inline int64_t Bitmap::findRunOfZeros(size_t runLeng return -1; } -template -inline size_t Bitmap::count(size_t start) const +template +inline size_t Bitmap::count(size_t start) const { size_t result = 0; for ( ; (start % wordSize); ++start) { @@ -200,8 +214,8 @@ inline size_t Bitmap::count(size_t start) const return result; } -template -inline size_t Bitmap::isEmpty() const +template +inline size_t Bitmap::isEmpty() const { for (size_t i = 0; i < words; ++i) if (bits[i]) @@ -209,8 +223,8 @@ inline size_t Bitmap::isEmpty() const return true; } -template -inline size_t Bitmap::isFull() const +template +inline size_t Bitmap::isFull() const { for (size_t i = 0; i < words; ++i) if (~bits[i]) @@ -218,5 +232,89 @@ inline size_t Bitmap::isFull() const return true; } +template +inline void Bitmap::merge(const Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) + bits[i] |= other.bits[i]; +} + +template +inline void Bitmap::filter(const Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) + bits[i] &= other.bits[i]; +} + +template +inline void Bitmap::exclude(const Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) + bits[i] &= ~other.bits[i]; +} + +template +template +inline void Bitmap::forEachSetBit(const Func& func) const +{ + for (size_t i = 0; i < words; ++i) { + WordType word = bits[i]; + if (!word) + continue; + size_t base = i * wordSize; + for (size_t j = 0; j < wordSize; ++j) { + if (word & 1) + func(base + j); + word >>= 1; + } + } +} + +template +inline void Bitmap::mergeAndClear(Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) { + bits[i] |= other.bits[i]; + other.bits[i] = 0; + } +} + +template +inline void Bitmap::setAndClear(Bitmap& other) +{ + for (size_t i = 0; i < words; ++i) { + bits[i] = other.bits[i]; + other.bits[i] = 0; + } +} + +template +inline bool Bitmap::operator==(const Bitmap& other) const +{ + for (size_t i = 0; i < words; ++i) { + if (bits[i] != other.bits[i]) + return false; + } + return true; +} + +template +inline bool Bitmap::operator!=(const Bitmap& other) const +{ + return !(*this == other); +} + +template +inline unsigned Bitmap::hash() const +{ + unsigned result = 0; + for (size_t i = 0; i < words; ++i) + result ^= IntHash::hash(bits[i]); + return result; } + +} // namespace WTF + +using WTF::Bitmap; + #endif -- cgit v1.2.1