From 40736c5763bf61337c8c14e16d8587db021a87d4 Mon Sep 17 00:00:00 2001 From: Simon Hausmann Date: Fri, 6 Jan 2012 14:44:00 +0100 Subject: Imported WebKit commit 2ea9d364d0f6efa8fa64acf19f451504c59be0e4 (http://svn.webkit.org/repository/webkit/trunk@104285) --- Source/JavaScriptCore/wtf/Bitmap.h | 225 +++++++++++++++++++++++++++++++++++++ 1 file changed, 225 insertions(+) create mode 100644 Source/JavaScriptCore/wtf/Bitmap.h (limited to 'Source/JavaScriptCore/wtf/Bitmap.h') diff --git a/Source/JavaScriptCore/wtf/Bitmap.h b/Source/JavaScriptCore/wtf/Bitmap.h new file mode 100644 index 000000000..d7e2528a3 --- /dev/null +++ b/Source/JavaScriptCore/wtf/Bitmap.h @@ -0,0 +1,225 @@ +/* + * 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 "Atomics.h" +#include "FixedArray.h" +#include "StdLibExtras.h" +#include +#include + +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 +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 bits; +}; + +template +inline Bitmap::Bitmap() +{ + clearAll(); +} + +template +inline bool Bitmap::get(size_t n) const +{ + return !!(bits[n / wordSize] & (one << (n % wordSize))); +} + +template +inline void Bitmap::set(size_t n) +{ + bits[n / wordSize] |= (one << (n % wordSize)); +} + +template +inline bool Bitmap::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 +inline bool Bitmap::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 +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; + WordType oldValue; + do { + oldValue = *wordPtr; + if (oldValue & mask) + return true; + } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue | mask)); + return false; +} + +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; + WordType oldValue; + do { + oldValue = *wordPtr; + if (!(oldValue & mask)) + return false; + } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue & ~mask)); + return true; +} + +template +inline void Bitmap::clear(size_t n) +{ + bits[n / wordSize] &= ~(one << (n % wordSize)); +} + +template +inline void Bitmap::clearAll() +{ + memset(bits.data(), 0, sizeof(bits)); +} + +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 +{ + 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 +inline size_t Bitmap::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 +inline size_t Bitmap::isEmpty() const +{ + for (size_t i = 0; i < words; ++i) + if (bits[i]) + return false; + return true; +} + +template +inline size_t Bitmap::isFull() const +{ + for (size_t i = 0; i < words; ++i) + if (~bits[i]) + return false; + return true; +} + +} +#endif -- cgit v1.2.1