OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2011 Google Inc. | 2 * Copyright 2011 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 | |
9 #ifndef SkBitSet_DEFINED | 8 #ifndef SkBitSet_DEFINED |
10 #define SkBitSet_DEFINED | 9 #define SkBitSet_DEFINED |
11 | 10 |
12 #include "SkTypes.h" | |
13 #include "SkTDArray.h" | 11 #include "SkTDArray.h" |
| 12 #include "SkTemplates.h" |
14 | 13 |
15 class SkBitSet { | 14 class SkBitSet { |
16 public: | 15 public: |
17 /** NumberOfBits must be greater than zero. | 16 explicit SkBitSet(int numberOfBits) { |
18 */ | 17 SkASSERT(numberOfBits > 0); |
19 explicit SkBitSet(int numberOfBits); | 18 fDwordCount = (numberOfBits + 31) / 32; // Round up size to 32-bit boun
dary. |
| 19 fBitData.reset((uint32_t*)sk_calloc_throw(fDwordCount * sizeof(uint32_t)
)); |
| 20 } |
| 21 |
20 SkBitSet(const SkBitSet&) = delete; | 22 SkBitSet(const SkBitSet&) = delete; |
21 SkBitSet(SkBitSet&&); | |
22 SkBitSet& operator=(const SkBitSet&) = delete; | 23 SkBitSet& operator=(const SkBitSet&) = delete; |
23 SkBitSet& operator=(SkBitSet&& rhs); | |
24 | 24 |
25 bool operator==(const SkBitSet& rhs); | 25 /** Set the value of the index-th bit to true. */ |
26 bool operator!=(const SkBitSet& rhs); | 26 void set(int index) { |
27 | |
28 /** Clear all data. | |
29 */ | |
30 void clearAll(); | |
31 | |
32 /** Set the value of the index-th bit. | |
33 */ | |
34 void setBit(int index, bool value) { | |
35 uint32_t mask = 1 << (index & 31); | 27 uint32_t mask = 1 << (index & 31); |
36 uint32_t* chunk = this->internalGet(index); | 28 uint32_t* chunk = this->internalGet(index); |
37 if (value) { | 29 SkASSERT(chunk); |
38 *chunk |= mask; | 30 *chunk |= mask; |
39 } else { | |
40 *chunk &= ~mask; | |
41 } | |
42 } | 31 } |
43 void set(int index) { this->setBit(index, true); } | |
44 | 32 |
45 template<typename T> | 33 template<typename T> |
46 void setAll(T* array, int len) { | 34 void setAll(T* array, int len) { |
47 static_assert(std::is_integral<T>::value, "T is integral"); | 35 static_assert(std::is_integral<T>::value, "T is integral"); |
48 for (int i = 0; i < len; ++i) { | 36 for (int i = 0; i < len; ++i) { |
49 this->set(static_cast<int>(array[i])); | 37 this->set(static_cast<int>(array[i])); |
50 } | 38 } |
51 } | 39 } |
52 | 40 |
53 /** Test if bit index is set. | 41 bool has(int index) const { |
54 */ | 42 const uint32_t* chunk = this->internalGet(index); |
55 bool isBitSet(int index) const { | |
56 uint32_t mask = 1 << (index & 31); | 43 uint32_t mask = 1 << (index & 31); |
57 return SkToBool(*this->internalGet(index) & mask); | 44 return chunk && SkToBool(*chunk & mask); |
58 } | 45 } |
59 bool has(int index) const { return this->isBitSet(index); } | |
60 | 46 |
61 /** Or bits from source. false is returned if this doesn't have the same | 47 /** Export indices of set bits to T array. */ |
62 * bit count as source. | |
63 */ | |
64 bool orBits(const SkBitSet& source); | |
65 | |
66 /** Export indices of set bits to T array. | |
67 */ | |
68 template<typename T> | 48 template<typename T> |
69 void exportTo(SkTDArray<T>* array) const { | 49 void exportTo(SkTDArray<T>* array) const { |
70 static_assert(std::is_integral<T>::value, "T is integral"); | 50 static_assert(std::is_integral<T>::value, "T is integral"); |
71 SkASSERT(array); | 51 SkASSERT(array); |
72 uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get()); | 52 uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get()); |
73 for (unsigned int i = 0; i < fDwordCount; ++i) { | 53 for (unsigned int i = 0; i < fDwordCount; ++i) { |
74 uint32_t value = data[i]; | 54 uint32_t value = data[i]; |
75 if (value) { // There are set bits | 55 if (value) { // There are set bits |
76 unsigned int index = i * 32; | 56 unsigned int index = i * 32; |
77 for (unsigned int j = 0; j < 32; ++j) { | 57 for (unsigned int j = 0; j < 32; ++j) { |
78 if (0x1 & (value >> j)) { | 58 if (0x1 & (value >> j)) { |
79 array->push(index + j); | 59 array->push(index + j); |
80 } | 60 } |
81 } | 61 } |
82 } | 62 } |
83 } | 63 } |
84 } | 64 } |
85 | 65 |
86 private: | 66 private: |
87 SkAutoFree fBitData; | 67 std::unique_ptr<uint32_t, SkFunctionWrapper<void, void, sk_free>> fBitData; |
88 // Dword (32-bit) count of the bitset. | 68 size_t fDwordCount; // Dword (32-bit) count of the bitset. |
89 size_t fDwordCount; | |
90 size_t fBitCount; | |
91 | 69 |
92 uint32_t* internalGet(int index) const { | 70 uint32_t* internalGet(int index) const { |
93 SkASSERT((size_t)index < fBitCount); | |
94 size_t internalIndex = index / 32; | 71 size_t internalIndex = index / 32; |
95 SkASSERT(internalIndex < fDwordCount); | 72 if (internalIndex >= fDwordCount) { |
96 return reinterpret_cast<uint32_t*>(fBitData.get()) + internalIndex; | 73 return nullptr; |
| 74 } |
| 75 return fBitData.get() + internalIndex; |
97 } | 76 } |
98 }; | 77 }; |
99 | 78 |
100 | 79 |
101 #endif | 80 #endif |
OLD | NEW |