2 * Copyright (C) 2010 Apple Inc. All rights reserved.
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22 #include <wtf/Atomics.h>
23 #include <wtf/FixedArray.h>
24 #include <wtf/StdLibExtras.h>
30 enum BitmapAtomicMode {
31 // This makes concurrentTestAndSet behave just like testAndSet.
34 // This makes concurrentTestAndSet use compareAndSwap, so that it's
35 // atomic even when used concurrently.
39 template<size_t size, BitmapAtomicMode atomicMode = BitmapNotAtomic>
42 typedef uint32_t WordType;
47 bool get(size_t) const;
49 bool testAndSet(size_t);
50 bool testAndClear(size_t);
51 bool concurrentTestAndSet(size_t);
52 bool concurrentTestAndClear(size_t);
53 size_t nextPossiblyUnset(size_t) const;
56 int64_t findRunOfZeros(size_t) const;
57 size_t count(size_t = 0) const;
58 size_t isEmpty() const;
59 size_t isFull() const;
62 static const WordType wordSize = sizeof(WordType) * 8;
63 static const WordType words = (size + wordSize - 1) / wordSize;
65 // the literal '1' is of type signed int. We want to use an unsigned
66 // version of the correct size when doing the calculations because if
67 // WordType is larger than int, '1 << 31' will first be sign extended
68 // and then casted to unsigned, meaning that set(31) when WordType is
69 // a 64 bit unsigned int would give 0xffff8000
70 static const WordType one = 1;
72 FixedArray<WordType, words> bits;
75 template<size_t size, BitmapAtomicMode atomicMode>
76 inline Bitmap<size, atomicMode>::Bitmap()
81 template<size_t size, BitmapAtomicMode atomicMode>
82 inline bool Bitmap<size, atomicMode>::get(size_t n) const
84 return !!(bits[n / wordSize] & (one << (n % wordSize)));
87 template<size_t size, BitmapAtomicMode atomicMode>
88 inline void Bitmap<size, atomicMode>::set(size_t n)
90 bits[n / wordSize] |= (one << (n % wordSize));
93 template<size_t size, BitmapAtomicMode atomicMode>
94 inline bool Bitmap<size, atomicMode>::testAndSet(size_t n)
96 WordType mask = one << (n % wordSize);
97 size_t index = n / wordSize;
98 bool result = bits[index] & mask;
103 template<size_t size, BitmapAtomicMode atomicMode>
104 inline bool Bitmap<size, atomicMode>::testAndClear(size_t n)
106 WordType mask = one << (n % wordSize);
107 size_t index = n / wordSize;
108 bool result = bits[index] & mask;
109 bits[index] &= ~mask;
113 template<size_t size, BitmapAtomicMode atomicMode>
114 inline bool Bitmap<size, atomicMode>::concurrentTestAndSet(size_t n)
116 if (atomicMode == BitmapNotAtomic)
117 return testAndSet(n);
119 ASSERT(atomicMode == BitmapAtomic);
121 WordType mask = one << (n % wordSize);
122 size_t index = n / wordSize;
123 WordType* wordPtr = bits.data() + index;
129 } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue | mask));
133 template<size_t size, BitmapAtomicMode atomicMode>
134 inline bool Bitmap<size, atomicMode>::concurrentTestAndClear(size_t n)
136 if (atomicMode == BitmapNotAtomic)
137 return testAndClear(n);
139 ASSERT(atomicMode == BitmapAtomic);
141 WordType mask = one << (n % wordSize);
142 size_t index = n / wordSize;
143 WordType* wordPtr = bits.data() + index;
147 if (!(oldValue & mask))
149 } while (!weakCompareAndSwap(wordPtr, oldValue, oldValue & ~mask));
153 template<size_t size, BitmapAtomicMode atomicMode>
154 inline void Bitmap<size, atomicMode>::clear(size_t n)
156 bits[n / wordSize] &= ~(one << (n % wordSize));
159 template<size_t size, BitmapAtomicMode atomicMode>
160 inline void Bitmap<size, atomicMode>::clearAll()
162 memset(bits.data(), 0, sizeof(bits));
165 template<size_t size, BitmapAtomicMode atomicMode>
166 inline size_t Bitmap<size, atomicMode>::nextPossiblyUnset(size_t start) const
168 if (!~bits[start / wordSize])
169 return ((start / wordSize) + 1) * wordSize;
173 template<size_t size, BitmapAtomicMode atomicMode>
174 inline int64_t Bitmap<size, atomicMode>::findRunOfZeros(size_t runLength) const
179 for (size_t i = 0; i <= (size - runLength) ; i++) {
181 for (size_t j = i; j <= (i + runLength - 1) ; j++) {
193 template<size_t size, BitmapAtomicMode atomicMode>
194 inline size_t Bitmap<size, atomicMode>::count(size_t start) const
197 for ( ; (start % wordSize); ++start) {
201 for (size_t i = start / wordSize; i < words; ++i)
202 result += WTF::bitCount(bits[i]);
206 template<size_t size, BitmapAtomicMode atomicMode>
207 inline size_t Bitmap<size, atomicMode>::isEmpty() const
209 for (size_t i = 0; i < words; ++i)
215 template<size_t size, BitmapAtomicMode atomicMode>
216 inline size_t Bitmap<size, atomicMode>::isFull() const
218 for (size_t i = 0; i < words; ++i)