Index: Source/WTF/wtf/Bitmap.h |
diff --git a/Source/WTF/wtf/Bitmap.h b/Source/WTF/wtf/Bitmap.h |
deleted file mode 100644 |
index 76a2ca4b3bfc7f95a5c2efb718f66e74ac20b971..0000000000000000000000000000000000000000 |
--- a/Source/WTF/wtf/Bitmap.h |
+++ /dev/null |
@@ -1,225 +0,0 @@ |
-/* |
- * Copyright (C) 2010 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 |
- * License as published by the Free Software Foundation; either |
- * version 2 of the License, or (at your option) any later version. |
- * |
- * This library is distributed in the hope that it will be useful, |
- * but WITHOUT ANY WARRANTY; without even the implied warranty of |
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
- * Lesser General Public License for more details. |
- * |
- * You should have received a copy of the GNU Lesser General Public |
- * License along with this library; if not, write to the Free Software |
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
- * |
- */ |
-#ifndef Bitmap_h |
-#define Bitmap_h |
- |
-#include <wtf/Atomics.h> |
-#include <wtf/FixedArray.h> |
-#include <wtf/StdLibExtras.h> |
-#include <stdint.h> |
-#include <string.h> |
- |
-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<size_t size, BitmapAtomicMode atomicMode = BitmapNotAtomic> |
-class Bitmap { |
-private: |
- typedef uint32_t WordType; |
- |
-public: |
- Bitmap(); |
- |
- bool get(size_t) const; |
- void set(size_t); |
- bool testAndSet(size_t); |
- bool testAndClear(size_t); |
- bool concurrentTestAndSet(size_t); |
- bool concurrentTestAndClear(size_t); |
- 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; |
- size_t isEmpty() const; |
- size_t isFull() const; |
- |
-private: |
- static const WordType wordSize = sizeof(WordType) * 8; |
- static const WordType words = (size + 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 |
- // WordType is larger than int, '1 << 31' will first be sign extended |
- // and then casted to unsigned, meaning that set(31) when WordType is |
- // a 64 bit unsigned int would give 0xffff8000 |
- static const WordType one = 1; |
- |
- FixedArray<WordType, words> bits; |
-}; |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline Bitmap<size, atomicMode>::Bitmap() |
-{ |
- clearAll(); |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline bool Bitmap<size, atomicMode>::get(size_t n) const |
-{ |
- return !!(bits[n / wordSize] & (one << (n % wordSize))); |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline void Bitmap<size, atomicMode>::set(size_t n) |
-{ |
- bits[n / wordSize] |= (one << (n % wordSize)); |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline bool Bitmap<size, atomicMode>::testAndSet(size_t n) |
-{ |
- WordType mask = one << (n % wordSize); |
- size_t index = n / wordSize; |
- bool result = bits[index] & mask; |
- bits[index] |= mask; |
- return result; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline bool Bitmap<size, atomicMode>::testAndClear(size_t n) |
-{ |
- WordType mask = one << (n % wordSize); |
- size_t index = n / wordSize; |
- bool result = bits[index] & mask; |
- bits[index] &= ~mask; |
- return result; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline bool Bitmap<size, atomicMode>::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; |
- WordType oldValue; |
- do { |
- oldValue = *wordPtr; |
- if (oldValue & mask) |
- return true; |
- } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue | mask)); |
- return false; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline bool Bitmap<size, atomicMode>::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; |
- WordType oldValue; |
- do { |
- oldValue = *wordPtr; |
- if (!(oldValue & mask)) |
- return false; |
- } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue & ~mask)); |
- return true; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline void Bitmap<size, atomicMode>::clear(size_t n) |
-{ |
- bits[n / wordSize] &= ~(one << (n % wordSize)); |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline void Bitmap<size, atomicMode>::clearAll() |
-{ |
- memset(bits.data(), 0, sizeof(bits)); |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline size_t Bitmap<size, atomicMode>::nextPossiblyUnset(size_t start) const |
-{ |
- if (!~bits[start / wordSize]) |
- return ((start / wordSize) + 1) * wordSize; |
- return start + 1; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline int64_t Bitmap<size, atomicMode>::findRunOfZeros(size_t runLength) const |
-{ |
- if (!runLength) |
- runLength = 1; |
- |
- for (size_t i = 0; i <= (size - runLength) ; i++) { |
- bool found = true; |
- for (size_t j = i; j <= (i + runLength - 1) ; j++) { |
- if (get(j)) { |
- found = false; |
- break; |
- } |
- } |
- if (found) |
- return i; |
- } |
- return -1; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline size_t Bitmap<size, atomicMode>::count(size_t start) const |
-{ |
- size_t result = 0; |
- for ( ; (start % wordSize); ++start) { |
- if (get(start)) |
- ++result; |
- } |
- for (size_t i = start / wordSize; i < words; ++i) |
- result += WTF::bitCount(bits[i]); |
- return result; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline size_t Bitmap<size, atomicMode>::isEmpty() const |
-{ |
- for (size_t i = 0; i < words; ++i) |
- if (bits[i]) |
- return false; |
- return true; |
-} |
- |
-template<size_t size, BitmapAtomicMode atomicMode> |
-inline size_t Bitmap<size, atomicMode>::isFull() const |
-{ |
- for (size_t i = 0; i < words; ++i) |
- if (~bits[i]) |
- return false; |
- return true; |
-} |
- |
-} |
-#endif |