1/*
2 * Copyright (C) 2012-2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include "Algorithm.h"
29#include "BInline.h"
30#include <climits>
31
32namespace bmalloc {
33
34constexpr size_t bitsArrayLength(size_t numBits) { return (numBits + 31) / 32; }
35
36class BitsWordView {
37public:
38 typedef BitsWordView ViewType;
39
40 BitsWordView() { }
41
42 BitsWordView(const uint32_t* array, size_t numBits)
43 : m_words(array)
44 , m_numBits(numBits)
45 {
46 }
47
48 size_t numBits() const
49 {
50 return m_numBits;
51 }
52
53 uint32_t word(size_t index) const
54 {
55 RELEASE_BASSERT(index < bitsArrayLength(numBits()));
56 return m_words[index];
57 }
58
59private:
60 const uint32_t* m_words { nullptr };
61 size_t m_numBits { 0 };
62};
63
64template<size_t passedNumBits>
65class BitsWordOwner {
66public:
67 typedef BitsWordView ViewType;
68
69 BitsWordOwner()
70 {
71 clearAll();
72 }
73
74 BitsWordOwner(const BitsWordOwner& other)
75 {
76 *this = other;
77 }
78
79 BitsWordView view() const { return BitsWordView(m_words, numBits()); }
80
81 BitsWordOwner& operator=(const BitsWordOwner& other)
82 {
83 memcpy(m_words, other.m_words, arrayLength() * sizeof(uint32_t));
84 return *this;
85 }
86
87 void setAll()
88 {
89 memset(m_words, 255, arrayLength() * sizeof(uint32_t));
90 }
91
92 void clearAll()
93 {
94 memset(m_words, 0, arrayLength() * sizeof(uint32_t));
95 }
96
97 void set(const BitsWordOwner& other)
98 {
99 memcpy(m_words, other.m_words, arrayLength() * sizeof(uint32_t));
100 }
101
102 size_t numBits() const
103 {
104 return passedNumBits;
105 }
106
107 size_t arrayLength() const
108 {
109 return bitsArrayLength(numBits());
110 }
111
112 uint32_t word(size_t index) const
113 {
114 RELEASE_BASSERT(index < arrayLength());
115 return m_words[index];
116 }
117
118 uint32_t& word(size_t index)
119 {
120 RELEASE_BASSERT(index < arrayLength());
121 return m_words[index];
122 }
123
124 const uint32_t* words() const { return m_words; }
125 uint32_t* words() { return m_words; }
126
127private:
128 uint32_t m_words[bitsArrayLength(passedNumBits)];
129};
130
131template<typename Left, typename Right>
132class BitsAndWords {
133public:
134 typedef BitsAndWords ViewType;
135
136 BitsAndWords(const Left& left, const Right& right)
137 : m_left(left)
138 , m_right(right)
139 {
140 RELEASE_BASSERT(m_left.numBits() == m_right.numBits());
141 }
142
143 BitsAndWords view() const { return *this; }
144
145 size_t numBits() const
146 {
147 return m_left.numBits();
148 }
149
150 uint32_t word(size_t index) const
151 {
152 return m_left.word(index) & m_right.word(index);
153 }
154
155private:
156 Left m_left;
157 Right m_right;
158};
159
160template<typename Left, typename Right>
161class BitsOrWords {
162public:
163 typedef BitsOrWords ViewType;
164
165 BitsOrWords(const Left& left, const Right& right)
166 : m_left(left)
167 , m_right(right)
168 {
169 RELEASE_BASSERT(m_left.numBits() == m_right.numBits());
170 }
171
172 BitsOrWords view() const { return *this; }
173
174 size_t numBits() const
175 {
176 return m_left.numBits();
177 }
178
179 uint32_t word(size_t index) const
180 {
181 return m_left.word(index) | m_right.word(index);
182 }
183
184private:
185 Left m_left;
186 Right m_right;
187};
188
189template<typename View>
190class BitsNotWords {
191public:
192 typedef BitsNotWords ViewType;
193
194 BitsNotWords(const View& view)
195 : m_view(view)
196 {
197 }
198
199 BitsNotWords view() const { return *this; }
200
201 size_t numBits() const
202 {
203 return m_view.numBits();
204 }
205
206 uint32_t word(size_t index) const
207 {
208 return ~m_view.word(index);
209 }
210
211private:
212 View m_view;
213};
214
215template<size_t> class Bits;
216
217template<typename Words>
218class BitsImpl {
219public:
220 BitsImpl()
221 : m_words()
222 {
223 }
224
225 BitsImpl(const Words& words)
226 : m_words(words)
227 {
228 }
229
230 BitsImpl(Words&& words)
231 : m_words(std::move(words))
232 {
233 }
234
235 size_t numBits() const { return m_words.numBits(); }
236 size_t size() const { return numBits(); }
237
238 size_t arrayLength() const { return bitsArrayLength(numBits()); }
239
240 template<typename Other>
241 bool operator==(const Other& other) const
242 {
243 if (numBits() != other.numBits())
244 return false;
245 for (size_t i = arrayLength(); i--;) {
246 if (m_words.word(i) != other.m_words.word(i))
247 return false;
248 }
249 return true;
250 }
251
252 template<typename Other>
253 bool operator!=(const Other& other) const
254 {
255 return !(*this == other);
256 }
257
258 bool at(size_t index) const
259 {
260 return atImpl(index);
261 }
262
263 bool operator[](size_t index) const
264 {
265 return atImpl(index);
266 }
267
268 bool isEmpty() const
269 {
270 for (size_t index = arrayLength(); index--;) {
271 if (m_words.word(index))
272 return false;
273 }
274 return true;
275 }
276
277 template<typename OtherWords>
278 BitsImpl<BitsAndWords<typename Words::ViewType, typename OtherWords::ViewType>> operator&(const BitsImpl<OtherWords>& other) const
279 {
280 return BitsImpl<BitsAndWords<typename Words::ViewType, typename OtherWords::ViewType>>(BitsAndWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
281 }
282
283 template<typename OtherWords>
284 BitsImpl<BitsOrWords<typename Words::ViewType, typename OtherWords::ViewType>> operator|(const BitsImpl<OtherWords>& other) const
285 {
286 return BitsImpl<BitsOrWords<typename Words::ViewType, typename OtherWords::ViewType>>(BitsOrWords<typename Words::ViewType, typename OtherWords::ViewType>(wordView(), other.wordView()));
287 }
288
289 BitsImpl<BitsNotWords<typename Words::ViewType>> operator~() const
290 {
291 return BitsImpl<BitsNotWords<typename Words::ViewType>>(BitsNotWords<typename Words::ViewType>(wordView()));
292 }
293
294 template<typename Func>
295 BINLINE void forEachSetBit(const Func& func) const
296 {
297 size_t n = arrayLength();
298 for (size_t i = 0; i < n; ++i) {
299 uint32_t word = m_words.word(i);
300 size_t j = i * 32;
301 while (word) {
302 if (word & 1)
303 func(j);
304 word >>= 1;
305 j++;
306 }
307 }
308 }
309
310 template<typename Func>
311 BINLINE void forEachClearBit(const Func& func) const
312 {
313 (~*this).forEachSetBit(func);
314 }
315
316 template<typename Func>
317 void forEachBit(bool value, const Func& func) const
318 {
319 if (value)
320 forEachSetBit(func);
321 else
322 forEachClearBit(func);
323 }
324
325 // Starts looking for bits at the index you pass. If that index contains the value you want,
326 // then it will return that index. Returns numBits when we get to the end. For example, you
327 // can write a loop to iterate over all set bits like this:
328 //
329 // for (size_t i = bits.findBit(0, true); i < bits.numBits(); i = bits.findBit(i + 1, true))
330 // ...
331 BINLINE size_t findBit(size_t startIndex, bool value) const
332 {
333 // If value is true, this produces 0. If value is false, this produces UINT_MAX. It's
334 // written this way so that it performs well regardless of whether value is a constant.
335 uint32_t skipValue = -(static_cast<uint32_t>(value) ^ 1);
336
337 size_t numWords = bitsArrayLength(m_words.numBits());
338
339 size_t wordIndex = startIndex / 32;
340 size_t startIndexInWord = startIndex - wordIndex * 32;
341
342 while (wordIndex < numWords) {
343 uint32_t word = m_words.word(wordIndex);
344 if (word != skipValue) {
345 size_t index = startIndexInWord;
346 if (findBitInWord(word, index, 32, value))
347 return wordIndex * 32 + index;
348 }
349
350 wordIndex++;
351 startIndexInWord = 0;
352 }
353
354 return numBits();
355 }
356
357 BINLINE size_t findSetBit(size_t index) const
358 {
359 return findBit(index, true);
360 }
361
362 BINLINE size_t findClearBit(size_t index) const
363 {
364 return findBit(index, false);
365 }
366
367 typename Words::ViewType wordView() const { return m_words.view(); }
368
369private:
370 // You'd think that we could remove this friend if we used protected, but you'd be wrong,
371 // because templates.
372 template<size_t> friend class Bits;
373
374 bool atImpl(size_t index) const
375 {
376 RELEASE_BASSERT(index < numBits());
377 return !!(m_words.word(index >> 5) & (1 << (index & 31)));
378 }
379
380 Words m_words;
381};
382
383template<size_t passedNumBits>
384class Bits : public BitsImpl<BitsWordOwner<passedNumBits>> {
385public:
386 Bits() { }
387
388 Bits(const Bits&) = default;
389 Bits& operator=(const Bits&) = default;
390
391 template<typename OtherWords>
392 Bits(const BitsImpl<OtherWords>& other)
393 {
394 *this = other;
395 }
396
397 template<typename OtherWords>
398 Bits& operator=(const BitsImpl<OtherWords>& other)
399 {
400 if (this->numBits() != other.numBits())
401 resize(other.numBits());
402
403 for (unsigned i = this->arrayLength(); i--;)
404 this->m_words.word(i) = other.m_words.word(i);
405 return *this;
406 }
407
408 void resize(size_t numBits)
409 {
410 this->m_words.resize(numBits);
411 }
412
413 void setAll()
414 {
415 this->m_words.setAll();
416 }
417
418 void clearAll()
419 {
420 this->m_words.clearAll();
421 }
422
423 // Returns true if the contents of this bitvector changed.
424 template<typename OtherWords>
425 bool setAndCheck(const BitsImpl<OtherWords>& other)
426 {
427 bool changed = false;
428 RELEASE_BASSERT(this->numBits() == other.numBits());
429 for (unsigned i = this->arrayLength(); i--;) {
430 changed |= this->m_words.word(i) != other.m_words.word(i);
431 this->m_words.word(i) = other.m_words.word(i);
432 }
433 return changed;
434 }
435
436 template<typename OtherWords>
437 Bits& operator|=(const BitsImpl<OtherWords>& other)
438 {
439 RELEASE_BASSERT(this->numBits() == other.numBits());
440 for (unsigned i = this->arrayLength(); i--;)
441 this->m_words.word(i) |= other.m_words.word(i);
442 return *this;
443 }
444
445 template<typename OtherWords>
446 Bits& operator&=(const BitsImpl<OtherWords>& other)
447 {
448 RELEASE_BASSERT(this->numBits() == other.numBits());
449 for (unsigned i = this->arrayLength(); i--;)
450 this->m_words.word(i) &= other.m_words.word(i);
451 return *this;
452 }
453
454 bool at(size_t index) const
455 {
456 return this->atImpl(index);
457 }
458
459 bool operator[](size_t index) const
460 {
461 return this->atImpl(index);
462 }
463
464 class BitReference {
465 public:
466 BitReference() { }
467
468 BitReference(uint32_t* word, uint32_t mask)
469 : m_word(word)
470 , m_mask(mask)
471 {
472 }
473
474 explicit operator bool() const
475 {
476 return !!(*m_word & m_mask);
477 }
478
479 BitReference& operator=(bool value)
480 {
481 if (value)
482 *m_word |= m_mask;
483 else
484 *m_word &= ~m_mask;
485 return *this;
486 }
487
488 private:
489 uint32_t* m_word { nullptr };
490 uint32_t m_mask { 0 };
491 };
492
493 BitReference at(size_t index)
494 {
495 RELEASE_BASSERT(index < this->numBits());
496 return BitReference(&this->m_words.word(index >> 5), 1 << (index & 31));
497 }
498
499 BitReference operator[](size_t index)
500 {
501 return at(index);
502 }
503};
504
505} // namespace bmalloc
506
507