1/*
2 * Copyright (C) 2010-2017 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
20#pragma once
21
22#include <array>
23#include <wtf/Atomics.h>
24#include <wtf/HashFunctions.h>
25#include <wtf/StdLibExtras.h>
26#include <stdint.h>
27#include <string.h>
28
29namespace WTF {
30
31template<size_t bitmapSize, typename WordType = uint32_t>
32class Bitmap {
33 WTF_MAKE_FAST_ALLOCATED;
34
35 static_assert(sizeof(WordType) <= sizeof(unsigned), "WordType must not be bigger than unsigned");
36public:
37 constexpr Bitmap();
38
39 static constexpr size_t size()
40 {
41 return bitmapSize;
42 }
43
44 bool get(size_t, Dependency = Dependency()) const;
45 void set(size_t);
46 void set(size_t, bool);
47 bool testAndSet(size_t);
48 bool testAndClear(size_t);
49 bool concurrentTestAndSet(size_t, Dependency = Dependency());
50 bool concurrentTestAndClear(size_t, Dependency = Dependency());
51 size_t nextPossiblyUnset(size_t) const;
52 void clear(size_t);
53 void clearAll();
54 int64_t findRunOfZeros(size_t runLength) const;
55 size_t count(size_t start = 0) const;
56 size_t isEmpty() const;
57 size_t isFull() const;
58
59 void merge(const Bitmap&);
60 void filter(const Bitmap&);
61 void exclude(const Bitmap&);
62
63 void concurrentFilter(const Bitmap&);
64
65 bool subsumes(const Bitmap&) const;
66
67 template<typename Func>
68 void forEachSetBit(const Func&) const;
69
70 size_t findBit(size_t startIndex, bool value) const;
71
72 class iterator {
73 public:
74 iterator()
75 : m_bitmap(nullptr)
76 , m_index(0)
77 {
78 }
79
80 iterator(const Bitmap& bitmap, size_t index)
81 : m_bitmap(&bitmap)
82 , m_index(index)
83 {
84 }
85
86 size_t operator*() const { return m_index; }
87
88 iterator& operator++()
89 {
90 m_index = m_bitmap->findBit(m_index + 1, true);
91 return *this;
92 }
93
94 bool operator==(const iterator& other) const
95 {
96 return m_index == other.m_index;
97 }
98
99 bool operator!=(const iterator& other) const
100 {
101 return !(*this == other);
102 }
103
104 private:
105 const Bitmap* m_bitmap;
106 size_t m_index;
107 };
108
109 // Use this to iterate over set bits.
110 iterator begin() const { return iterator(*this, findBit(0, true)); }
111 iterator end() const { return iterator(*this, bitmapSize); }
112
113 void mergeAndClear(Bitmap&);
114 void setAndClear(Bitmap&);
115
116 bool operator==(const Bitmap&) const;
117 bool operator!=(const Bitmap&) const;
118
119 unsigned hash() const;
120
121private:
122 static const unsigned wordSize = sizeof(WordType) * 8;
123 static const unsigned words = (bitmapSize + wordSize - 1) / wordSize;
124
125 // the literal '1' is of type signed int. We want to use an unsigned
126 // version of the correct size when doing the calculations because if
127 // WordType is larger than int, '1 << 31' will first be sign extended
128 // and then casted to unsigned, meaning that set(31) when WordType is
129 // a 64 bit unsigned int would give 0xffff8000
130 static const WordType one = 1;
131
132 std::array<WordType, words> bits;
133};
134
135template<size_t bitmapSize, typename WordType>
136constexpr Bitmap<bitmapSize, WordType>::Bitmap()
137{
138 clearAll();
139}
140
141template<size_t bitmapSize, typename WordType>
142inline bool Bitmap<bitmapSize, WordType>::get(size_t n, Dependency dependency) const
143{
144 return !!(dependency.consume(this)->bits[n / wordSize] & (one << (n % wordSize)));
145}
146
147template<size_t bitmapSize, typename WordType>
148inline void Bitmap<bitmapSize, WordType>::set(size_t n)
149{
150 bits[n / wordSize] |= (one << (n % wordSize));
151}
152
153template<size_t bitmapSize, typename WordType>
154inline void Bitmap<bitmapSize, WordType>::set(size_t n, bool value)
155{
156 if (value)
157 set(n);
158 else
159 clear(n);
160}
161
162template<size_t bitmapSize, typename WordType>
163inline bool Bitmap<bitmapSize, WordType>::testAndSet(size_t n)
164{
165 WordType mask = one << (n % wordSize);
166 size_t index = n / wordSize;
167 bool result = bits[index] & mask;
168 bits[index] |= mask;
169 return result;
170}
171
172template<size_t bitmapSize, typename WordType>
173inline bool Bitmap<bitmapSize, WordType>::testAndClear(size_t n)
174{
175 WordType mask = one << (n % wordSize);
176 size_t index = n / wordSize;
177 bool result = bits[index] & mask;
178 bits[index] &= ~mask;
179 return result;
180}
181
182template<size_t bitmapSize, typename WordType>
183ALWAYS_INLINE bool Bitmap<bitmapSize, WordType>::concurrentTestAndSet(size_t n, Dependency dependency)
184{
185 WordType mask = one << (n % wordSize);
186 size_t index = n / wordSize;
187 WordType* data = dependency.consume(bits.data()) + index;
188 return !bitwise_cast<Atomic<WordType>*>(data)->transactionRelaxed(
189 [&] (WordType& value) -> bool {
190 if (value & mask)
191 return false;
192
193 value |= mask;
194 return true;
195 });
196}
197
198template<size_t bitmapSize, typename WordType>
199ALWAYS_INLINE bool Bitmap<bitmapSize, WordType>::concurrentTestAndClear(size_t n, Dependency dependency)
200{
201 WordType mask = one << (n % wordSize);
202 size_t index = n / wordSize;
203 WordType* data = dependency.consume(bits.data()) + index;
204 return !bitwise_cast<Atomic<WordType>*>(data)->transactionRelaxed(
205 [&] (WordType& value) -> bool {
206 if (!(value & mask))
207 return false;
208
209 value &= ~mask;
210 return true;
211 });
212}
213
214template<size_t bitmapSize, typename WordType>
215inline void Bitmap<bitmapSize, WordType>::clear(size_t n)
216{
217 bits[n / wordSize] &= ~(one << (n % wordSize));
218}
219
220template<size_t bitmapSize, typename WordType>
221inline void Bitmap<bitmapSize, WordType>::clearAll()
222{
223 memset(bits.data(), 0, sizeof(bits));
224}
225
226template<size_t bitmapSize, typename WordType>
227inline size_t Bitmap<bitmapSize, WordType>::nextPossiblyUnset(size_t start) const
228{
229 if (!~bits[start / wordSize])
230 return ((start / wordSize) + 1) * wordSize;
231 return start + 1;
232}
233
234template<size_t bitmapSize, typename WordType>
235inline int64_t Bitmap<bitmapSize, WordType>::findRunOfZeros(size_t runLength) const
236{
237 if (!runLength)
238 runLength = 1;
239
240 for (size_t i = 0; i <= (bitmapSize - runLength) ; i++) {
241 bool found = true;
242 for (size_t j = i; j <= (i + runLength - 1) ; j++) {
243 if (get(j)) {
244 found = false;
245 break;
246 }
247 }
248 if (found)
249 return i;
250 }
251 return -1;
252}
253
254template<size_t bitmapSize, typename WordType>
255inline size_t Bitmap<bitmapSize, WordType>::count(size_t start) const
256{
257 size_t result = 0;
258 for ( ; (start % wordSize); ++start) {
259 if (get(start))
260 ++result;
261 }
262 for (size_t i = start / wordSize; i < words; ++i)
263 result += WTF::bitCount(static_cast<unsigned>(bits[i]));
264 return result;
265}
266
267template<size_t bitmapSize, typename WordType>
268inline size_t Bitmap<bitmapSize, WordType>::isEmpty() const
269{
270 for (size_t i = 0; i < words; ++i)
271 if (bits[i])
272 return false;
273 return true;
274}
275
276template<size_t bitmapSize, typename WordType>
277inline size_t Bitmap<bitmapSize, WordType>::isFull() const
278{
279 for (size_t i = 0; i < words; ++i)
280 if (~bits[i])
281 return false;
282 return true;
283}
284
285template<size_t bitmapSize, typename WordType>
286inline void Bitmap<bitmapSize, WordType>::merge(const Bitmap& other)
287{
288 for (size_t i = 0; i < words; ++i)
289 bits[i] |= other.bits[i];
290}
291
292template<size_t bitmapSize, typename WordType>
293inline void Bitmap<bitmapSize, WordType>::filter(const Bitmap& other)
294{
295 for (size_t i = 0; i < words; ++i)
296 bits[i] &= other.bits[i];
297}
298
299template<size_t bitmapSize, typename WordType>
300inline void Bitmap<bitmapSize, WordType>::exclude(const Bitmap& other)
301{
302 for (size_t i = 0; i < words; ++i)
303 bits[i] &= ~other.bits[i];
304}
305
306template<size_t bitmapSize, typename WordType>
307inline void Bitmap<bitmapSize, WordType>::concurrentFilter(const Bitmap& other)
308{
309 for (size_t i = 0; i < words; ++i) {
310 for (;;) {
311 WordType otherBits = other.bits[i];
312 if (!otherBits) {
313 bits[i] = 0;
314 break;
315 }
316 WordType oldBits = bits[i];
317 WordType filteredBits = oldBits & otherBits;
318 if (oldBits == filteredBits)
319 break;
320 if (atomicCompareExchangeWeakRelaxed(&bits[i], oldBits, filteredBits))
321 break;
322 }
323 }
324}
325
326template<size_t bitmapSize, typename WordType>
327inline bool Bitmap<bitmapSize, WordType>::subsumes(const Bitmap& other) const
328{
329 for (size_t i = 0; i < words; ++i) {
330 WordType myBits = bits[i];
331 WordType otherBits = other.bits[i];
332 if ((myBits | otherBits) != myBits)
333 return false;
334 }
335 return true;
336}
337
338template<size_t bitmapSize, typename WordType>
339template<typename Func>
340inline void Bitmap<bitmapSize, WordType>::forEachSetBit(const Func& func) const
341{
342 for (size_t i = 0; i < words; ++i) {
343 WordType word = bits[i];
344 if (!word)
345 continue;
346 size_t base = i * wordSize;
347 for (size_t j = 0; j < wordSize; ++j) {
348 if (word & 1)
349 func(base + j);
350 word >>= 1;
351 }
352 }
353}
354
355template<size_t bitmapSize, typename WordType>
356inline size_t Bitmap<bitmapSize, WordType>::findBit(size_t startIndex, bool value) const
357{
358 WordType skipValue = -(static_cast<WordType>(value) ^ 1);
359 size_t wordIndex = startIndex / wordSize;
360 size_t startIndexInWord = startIndex - wordIndex * wordSize;
361
362 while (wordIndex < words) {
363 WordType word = bits[wordIndex];
364 if (word != skipValue) {
365 size_t index = startIndexInWord;
366 if (findBitInWord(word, index, wordSize, value))
367 return wordIndex * wordSize + index;
368 }
369
370 wordIndex++;
371 startIndexInWord = 0;
372 }
373
374 return bitmapSize;
375}
376
377template<size_t bitmapSize, typename WordType>
378inline void Bitmap<bitmapSize, WordType>::mergeAndClear(Bitmap& other)
379{
380 for (size_t i = 0; i < words; ++i) {
381 bits[i] |= other.bits[i];
382 other.bits[i] = 0;
383 }
384}
385
386template<size_t bitmapSize, typename WordType>
387inline void Bitmap<bitmapSize, WordType>::setAndClear(Bitmap& other)
388{
389 for (size_t i = 0; i < words; ++i) {
390 bits[i] = other.bits[i];
391 other.bits[i] = 0;
392 }
393}
394
395template<size_t bitmapSize, typename WordType>
396inline bool Bitmap<bitmapSize, WordType>::operator==(const Bitmap& other) const
397{
398 for (size_t i = 0; i < words; ++i) {
399 if (bits[i] != other.bits[i])
400 return false;
401 }
402 return true;
403}
404
405template<size_t bitmapSize, typename WordType>
406inline bool Bitmap<bitmapSize, WordType>::operator!=(const Bitmap& other) const
407{
408 return !(*this == other);
409}
410
411template<size_t bitmapSize, typename WordType>
412inline unsigned Bitmap<bitmapSize, WordType>::hash() const
413{
414 unsigned result = 0;
415 for (size_t i = 0; i < words; ++i)
416 result ^= IntHash<WordType>::hash(bits[i]);
417 return result;
418}
419
420} // namespace WTF
421
422using WTF::Bitmap;
423