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