| 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 |