1/*
2 * Copyright (C) 2010 Apple Inc. All rights reserved.
3 *
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.
8 *
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.
13 *
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
17 *
18 */
19#ifndef Bitmap_h
20#define Bitmap_h
21
22#include <array>
23#include <wtf/Atomics.h>
24#include <wtf/StdLibExtras.h>
25#include <stdint.h>
26#include <string.h>
27
28namespace WTF {
29
30enum BitmapAtomicMode {
31 // This makes concurrentTestAndSet behave just like testAndSet.
32 BitmapNotAtomic,
33
34 // This makes concurrentTestAndSet use compareAndSwap, so that it's
35 // atomic even when used concurrently.
36 BitmapAtomic
37};
38
39template<size_t Size, BitmapAtomicMode atomicMode = BitmapNotAtomic, typename WordType = uint32_t>
40class Bitmap {
41 WTF_MAKE_FAST_ALLOCATED;
42public:
43 Bitmap();
44
45 bool get(size_t) const;
46 void set(size_t);
47 bool testAndSet(size_t);
48 bool testAndClear(size_t);
49 bool concurrentTestAndSet(size_t);
50 bool concurrentTestAndClear(size_t);
51 size_t nextPossiblyUnset(size_t) const;
52 void clear(size_t);
53 void clearAll();
54 int64_t findRunOfZeros(size_t) const;
55 size_t count(size_t = 0) const;
56 size_t isEmpty() const;
57 size_t isFull() const;
58
59private:
60 static const unsigned wordSize = sizeof(WordType) * 8;
61 static const unsigned words = (Size + wordSize - 1) / wordSize;
62
63 // the literal '1' is of type signed int. We want to use an unsigned
64 // version of the correct size when doing the calculations because if
65 // WordType is larger than int, '1 << 31' will first be sign extended
66 // and then casted to unsigned, meaning that set(31) when WordType is
67 // a 64 bit unsigned int would give 0xffff8000
68 static const WordType one = 1;
69
70 std::array<WordType, words> bits;
71};
72
73template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
74inline Bitmap<size, atomicMode, WordType>::Bitmap()
75{
76 clearAll();
77}
78
79template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
80inline bool Bitmap<size, atomicMode, WordType>::get(size_t n) const
81{
82 return !!(bits[n / wordSize] & (one << (n % wordSize)));
83}
84
85template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
86inline void Bitmap<size, atomicMode, WordType>::set(size_t n)
87{
88 bits[n / wordSize] |= (one << (n % wordSize));
89}
90
91template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
92inline bool Bitmap<size, atomicMode, WordType>::testAndSet(size_t n)
93{
94 WordType mask = one << (n % wordSize);
95 size_t index = n / wordSize;
96 bool result = bits[index] & mask;
97 bits[index] |= mask;
98 return result;
99}
100
101template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
102inline bool Bitmap<size, atomicMode, WordType>::testAndClear(size_t n)
103{
104 WordType mask = one << (n % wordSize);
105 size_t index = n / wordSize;
106 bool result = bits[index] & mask;
107 bits[index] &= ~mask;
108 return result;
109}
110
111template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
112inline bool Bitmap<size, atomicMode, WordType>::concurrentTestAndSet(size_t n)
113{
114 if (atomicMode == BitmapNotAtomic)
115 return testAndSet(n);
116
117 ASSERT(atomicMode == BitmapAtomic);
118
119 WordType mask = one << (n % wordSize);
120 size_t index = n / wordSize;
121 WordType* wordPtr = bits.data() + index;
122 WordType oldValue;
123 do {
124 oldValue = *wordPtr;
125 if (oldValue & mask)
126 return true;
127 } while (!weakCompareAndSwap(wordPtr, oldValue, static_cast<WordType>(oldValue | mask)));
128 return false;
129}
130
131template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
132inline bool Bitmap<size, atomicMode, WordType>::concurrentTestAndClear(size_t n)
133{
134 if (atomicMode == BitmapNotAtomic)
135 return testAndClear(n);
136
137 ASSERT(atomicMode == BitmapAtomic);
138
139 WordType mask = one << (n % wordSize);
140 size_t index = n / wordSize;
141 WordType* wordPtr = bits.data() + index;
142 WordType oldValue;
143 do {
144 oldValue = *wordPtr;
145 if (!(oldValue & mask))
146 return false;
147 } while (!weakCompareAndSwap(wordPtr, oldValue, static_cast<WordType>(oldValue & ~mask)));
148 return true;
149}
150
151template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
152inline void Bitmap<size, atomicMode, WordType>::clear(size_t n)
153{
154 bits[n / wordSize] &= ~(one << (n % wordSize));
155}
156
157template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
158inline void Bitmap<size, atomicMode, WordType>::clearAll()
159{
160 memset(bits.data(), 0, sizeof(bits));
161}
162
163template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
164inline size_t Bitmap<size, atomicMode, WordType>::nextPossiblyUnset(size_t start) const
165{
166 if (!~bits[start / wordSize])
167 return ((start / wordSize) + 1) * wordSize;
168 return start + 1;
169}
170
171template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
172inline int64_t Bitmap<size, atomicMode, WordType>::findRunOfZeros(size_t runLength) const
173{
174 if (!runLength)
175 runLength = 1;
176
177 for (size_t i = 0; i <= (size - runLength) ; i++) {
178 bool found = true;
179 for (size_t j = i; j <= (i + runLength - 1) ; j++) {
180 if (get(j)) {
181 found = false;
182 break;
183 }
184 }
185 if (found)
186 return i;
187 }
188 return -1;
189}
190
191template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
192inline size_t Bitmap<size, atomicMode, WordType>::count(size_t start) const
193{
194 size_t result = 0;
195 for ( ; (start % wordSize); ++start) {
196 if (get(start))
197 ++result;
198 }
199 for (size_t i = start / wordSize; i < words; ++i)
200 result += WTF::bitCount(static_cast<unsigned>(bits[i]));
201 return result;
202}
203
204template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
205inline size_t Bitmap<size, atomicMode, WordType>::isEmpty() const
206{
207 for (size_t i = 0; i < words; ++i)
208 if (bits[i])
209 return false;
210 return true;
211}
212
213template<size_t size, BitmapAtomicMode atomicMode, typename WordType>
214inline size_t Bitmap<size, atomicMode, WordType>::isFull() const
215{
216 for (size_t i = 0; i < words; ++i)
217 if (~bits[i])
218 return false;
219 return true;
220}
221
222}
223#endif
224