MarkedBlock should know what objects are live during marking
[WebKit-https.git] / Source / WTF / wtf / Bitmap.h
1 /*
2  *  Copyright (C) 2010, 2016 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
28 namespace WTF {
29
30 template<size_t bitmapSize, typename WordType = uint32_t>
31 class Bitmap {
32     WTF_MAKE_FAST_ALLOCATED;
33     
34     static_assert(sizeof(WordType) <= sizeof(unsigned), "WordType must not be bigger than unsigned");
35 public:
36     Bitmap();
37
38     static constexpr size_t size()
39     {
40         return bitmapSize;
41     }
42
43     bool get(size_t) const;
44     void set(size_t);
45     void set(size_t, bool);
46     bool testAndSet(size_t);
47     bool testAndClear(size_t);
48     bool concurrentTestAndSet(size_t);
49     bool concurrentTestAndClear(size_t);
50     size_t nextPossiblyUnset(size_t) const;
51     void clear(size_t);
52     void clearAll();
53     int64_t findRunOfZeros(size_t runLength) const;
54     size_t count(size_t start = 0) const;
55     size_t isEmpty() const;
56     size_t isFull() const;
57     
58     void merge(const Bitmap&);
59     void filter(const Bitmap&);
60     void exclude(const Bitmap&);
61     
62     template<typename Func>
63     void forEachSetBit(const Func&) const;
64     
65     void mergeAndClear(Bitmap&);
66     void setAndClear(Bitmap&);
67     
68     bool operator==(const Bitmap&) const;
69     bool operator!=(const Bitmap&) const;
70     
71     unsigned hash() const;
72
73 private:
74     static const unsigned wordSize = sizeof(WordType) * 8;
75     static const unsigned words = (bitmapSize + wordSize - 1) / wordSize;
76
77     // the literal '1' is of type signed int.  We want to use an unsigned
78     // version of the correct size when doing the calculations because if
79     // WordType is larger than int, '1 << 31' will first be sign extended
80     // and then casted to unsigned, meaning that set(31) when WordType is
81     // a 64 bit unsigned int would give 0xffff8000
82     static const WordType one = 1;
83
84     std::array<WordType, words> bits;
85 };
86
87 template<size_t bitmapSize, typename WordType>
88 inline Bitmap<bitmapSize, WordType>::Bitmap()
89 {
90     clearAll();
91 }
92
93 template<size_t bitmapSize, typename WordType>
94 inline bool Bitmap<bitmapSize, WordType>::get(size_t n) const
95 {
96     return !!(bits[n / wordSize] & (one << (n % wordSize)));
97 }
98
99 template<size_t bitmapSize, typename WordType>
100 inline void Bitmap<bitmapSize, WordType>::set(size_t n)
101 {
102     bits[n / wordSize] |= (one << (n % wordSize));
103 }
104
105 template<size_t bitmapSize, typename WordType>
106 inline void Bitmap<bitmapSize, WordType>::set(size_t n, bool value)
107 {
108     if (value)
109         set(n);
110     else
111         clear(n);
112 }
113
114 template<size_t bitmapSize, typename WordType>
115 inline bool Bitmap<bitmapSize, WordType>::testAndSet(size_t n)
116 {
117     WordType mask = one << (n % wordSize);
118     size_t index = n / wordSize;
119     bool result = bits[index] & mask;
120     bits[index] |= mask;
121     return result;
122 }
123
124 template<size_t bitmapSize, typename WordType>
125 inline bool Bitmap<bitmapSize, WordType>::testAndClear(size_t n)
126 {
127     WordType mask = one << (n % wordSize);
128     size_t index = n / wordSize;
129     bool result = bits[index] & mask;
130     bits[index] &= ~mask;
131     return result;
132 }
133
134 template<size_t bitmapSize, typename WordType>
135 inline bool Bitmap<bitmapSize, WordType>::concurrentTestAndSet(size_t n)
136 {
137     WordType mask = one << (n % wordSize);
138     size_t index = n / wordSize;
139     WordType* wordPtr = bits.data() + index;
140     WordType oldValue;
141     do {
142         oldValue = *wordPtr;
143         if (oldValue & mask)
144             return true;
145     } while (!weakCompareAndSwap(wordPtr, oldValue, static_cast<WordType>(oldValue | mask)));
146     return false;
147 }
148
149 template<size_t bitmapSize, typename WordType>
150 inline bool Bitmap<bitmapSize, WordType>::concurrentTestAndClear(size_t n)
151 {
152     WordType mask = one << (n % wordSize);
153     size_t index = n / wordSize;
154     WordType* wordPtr = bits.data() + index;
155     WordType oldValue;
156     do {
157         oldValue = *wordPtr;
158         if (!(oldValue & mask))
159             return false;
160     } while (!weakCompareAndSwap(wordPtr, oldValue, static_cast<WordType>(oldValue & ~mask)));
161     return true;
162 }
163
164 template<size_t bitmapSize, typename WordType>
165 inline void Bitmap<bitmapSize, WordType>::clear(size_t n)
166 {
167     bits[n / wordSize] &= ~(one << (n % wordSize));
168 }
169
170 template<size_t bitmapSize, typename WordType>
171 inline void Bitmap<bitmapSize, WordType>::clearAll()
172 {
173     memset(bits.data(), 0, sizeof(bits));
174 }
175
176 template<size_t bitmapSize, typename WordType>
177 inline size_t Bitmap<bitmapSize, WordType>::nextPossiblyUnset(size_t start) const
178 {
179     if (!~bits[start / wordSize])
180         return ((start / wordSize) + 1) * wordSize;
181     return start + 1;
182 }
183
184 template<size_t bitmapSize, typename WordType>
185 inline int64_t Bitmap<bitmapSize, WordType>::findRunOfZeros(size_t runLength) const
186 {
187     if (!runLength) 
188         runLength = 1; 
189      
190     for (size_t i = 0; i <= (bitmapSize - runLength) ; i++) {
191         bool found = true; 
192         for (size_t j = i; j <= (i + runLength - 1) ; j++) { 
193             if (get(j)) {
194                 found = false; 
195                 break;
196             }
197         }
198         if (found)  
199             return i; 
200     }
201     return -1;
202 }
203
204 template<size_t bitmapSize, typename WordType>
205 inline size_t Bitmap<bitmapSize, WordType>::count(size_t start) const
206 {
207     size_t result = 0;
208     for ( ; (start % wordSize); ++start) {
209         if (get(start))
210             ++result;
211     }
212     for (size_t i = start / wordSize; i < words; ++i)
213         result += WTF::bitCount(static_cast<unsigned>(bits[i]));
214     return result;
215 }
216
217 template<size_t bitmapSize, typename WordType>
218 inline size_t Bitmap<bitmapSize, WordType>::isEmpty() const
219 {
220     for (size_t i = 0; i < words; ++i)
221         if (bits[i])
222             return false;
223     return true;
224 }
225
226 template<size_t bitmapSize, typename WordType>
227 inline size_t Bitmap<bitmapSize, WordType>::isFull() const
228 {
229     for (size_t i = 0; i < words; ++i)
230         if (~bits[i])
231             return false;
232     return true;
233 }
234
235 template<size_t bitmapSize, typename WordType>
236 inline void Bitmap<bitmapSize, WordType>::merge(const Bitmap& other)
237 {
238     for (size_t i = 0; i < words; ++i)
239         bits[i] |= other.bits[i];
240 }
241
242 template<size_t bitmapSize, typename WordType>
243 inline void Bitmap<bitmapSize, WordType>::filter(const Bitmap& other)
244 {
245     for (size_t i = 0; i < words; ++i)
246         bits[i] &= other.bits[i];
247 }
248
249 template<size_t bitmapSize, typename WordType>
250 inline void Bitmap<bitmapSize, WordType>::exclude(const Bitmap& other)
251 {
252     for (size_t i = 0; i < words; ++i)
253         bits[i] &= ~other.bits[i];
254 }
255
256 template<size_t bitmapSize, typename WordType>
257 template<typename Func>
258 inline void Bitmap<bitmapSize, WordType>::forEachSetBit(const Func& func) const
259 {
260     for (size_t i = 0; i < words; ++i) {
261         WordType word = bits[i];
262         if (!word)
263             continue;
264         size_t base = i * wordSize;
265         for (size_t j = 0; j < wordSize; ++j) {
266             if (word & 1)
267                 func(base + j);
268             word >>= 1;
269         }
270     }
271 }
272
273 template<size_t bitmapSize, typename WordType>
274 inline void Bitmap<bitmapSize, WordType>::mergeAndClear(Bitmap& other)
275 {
276     for (size_t i = 0; i < words; ++i) {
277         bits[i] |= other.bits[i];
278         other.bits[i] = 0;
279     }
280 }
281
282 template<size_t bitmapSize, typename WordType>
283 inline void Bitmap<bitmapSize, WordType>::setAndClear(Bitmap& other)
284 {
285     for (size_t i = 0; i < words; ++i) {
286         bits[i] = other.bits[i];
287         other.bits[i] = 0;
288     }
289 }
290
291 template<size_t bitmapSize, typename WordType>
292 inline bool Bitmap<bitmapSize, WordType>::operator==(const Bitmap& other) const
293 {
294     for (size_t i = 0; i < words; ++i) {
295         if (bits[i] != other.bits[i])
296             return false;
297     }
298     return true;
299 }
300
301 template<size_t bitmapSize, typename WordType>
302 inline bool Bitmap<bitmapSize, WordType>::operator!=(const Bitmap& other) const
303 {
304     return !(*this == other);
305 }
306
307 template<size_t bitmapSize, typename WordType>
308 inline unsigned Bitmap<bitmapSize, WordType>::hash() const
309 {
310     unsigned result = 0;
311     for (size_t i = 0; i < words; ++i)
312         result ^= IntHash<WordType>::hash(bits[i]);
313     return result;
314 }
315
316 } // namespace WTF
317
318 using WTF::Bitmap;
319
320 #endif