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 "include/private/SkTemplates.h" 12 13 class SkBitSet { 14 public: SkBitSet(int numberOfBits)15 explicit SkBitSet(int numberOfBits) { 16 SkASSERT(numberOfBits >= 0); 17 fDwordCount = (numberOfBits + 31) / 32; // Round up size to 32-bit boundary. 18 if (fDwordCount > 0) { 19 fBitData.reset((uint32_t*)sk_calloc_throw(fDwordCount * sizeof(uint32_t))); 20 } 21 } 22 23 /** Set the value of the index-th bit to true. */ set(int index)24 void set(int index) { 25 uint32_t mask = 1 << (index & 31); 26 uint32_t* chunk = this->internalGet(index); 27 SkASSERT(chunk); 28 *chunk |= mask; 29 } 30 has(int index)31 bool has(int index) const { 32 const uint32_t* chunk = this->internalGet(index); 33 uint32_t mask = 1 << (index & 31); 34 return chunk && SkToBool(*chunk & mask); 35 } 36 37 // Calls f(unsigned) for each set value. 38 template<typename FN> getSetValues(FN f)39 void getSetValues(FN f) const { 40 const uint32_t* data = fBitData.get(); 41 for (unsigned i = 0; i < fDwordCount; ++i) { 42 if (uint32_t value = data[i]) { // There are set bits 43 unsigned index = i * 32; 44 for (unsigned j = 0; j < 32; ++j) { 45 if (0x1 & (value >> j)) { 46 f(index | j); 47 } 48 } 49 } 50 } 51 } 52 53 private: 54 std::unique_ptr<uint32_t, SkFunctionWrapper<void, void, sk_free>> fBitData; 55 size_t fDwordCount; // Dword (32-bit) count of the bitset. 56 internalGet(int index)57 uint32_t* internalGet(int index) const { 58 size_t internalIndex = index / 32; 59 if (internalIndex >= fDwordCount) { 60 return nullptr; 61 } 62 return fBitData.get() + internalIndex; 63 } 64 }; 65 66 67 #endif 68