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