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