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