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/SkMalloc.h" 12 #include "include/private/SkTOptional.h" 13 #include "include/private/SkTemplates.h" 14 #include "src/core/SkMathPriv.h" 15 #include <climits> 16 #include <cstring> 17 #include <limits> 18 #include <memory> 19 20 class SkBitSet { 21 public: SkBitSet(size_t size)22 explicit SkBitSet(size_t size) 23 : fSize(size) 24 // May http://wg21.link/p0593 be accepted. 25 , fChunks((Chunk*)sk_calloc_throw(NumChunksFor(fSize) * sizeof(Chunk))) 26 {} 27 28 SkBitSet(const SkBitSet&) = delete; 29 SkBitSet& operator=(const SkBitSet&) = delete; SkBitSet(SkBitSet && that)30 SkBitSet(SkBitSet&& that) { *this = std::move(that); } 31 SkBitSet& operator=(SkBitSet&& that) { 32 if (this != &that) { 33 this->fSize = that.fSize; 34 this->fChunks = std::move(that.fChunks); 35 that.fSize = 0; 36 } 37 return *this; 38 } 39 ~SkBitSet() = default; 40 41 /** Set the value of the index-th bit to true. */ set(size_t index)42 void set(size_t index) { 43 SkASSERT(index < fSize); 44 *this->chunkFor(index) |= ChunkMaskFor(index); 45 } 46 47 /** Sets every bit in the bitset to true. */ set()48 void set() { 49 Chunk* chunks = fChunks.get(); 50 const size_t numChunks = NumChunksFor(fSize); 51 std::memset(chunks, 0xFF, sizeof(Chunk) * numChunks); 52 } 53 54 /** Set the value of the index-th bit to false. */ reset(size_t index)55 void reset(size_t index) { 56 SkASSERT(index < fSize); 57 *this->chunkFor(index) &= ~ChunkMaskFor(index); 58 } 59 60 /** Sets every bit in the bitset to false. */ reset()61 void reset() { 62 Chunk* chunks = fChunks.get(); 63 const size_t numChunks = NumChunksFor(fSize); 64 std::memset(chunks, 0, sizeof(Chunk) * numChunks); 65 } 66 test(size_t index)67 bool test(size_t index) const { 68 SkASSERT(index < fSize); 69 return SkToBool(*this->chunkFor(index) & ChunkMaskFor(index)); 70 } 71 size()72 size_t size() const { 73 return fSize; 74 } 75 76 // Calls f(size_t index) for each set index. 77 template<typename FN> forEachSetIndex(FN f)78 void forEachSetIndex(FN f) const { 79 const Chunk* chunks = fChunks.get(); 80 const size_t numChunks = NumChunksFor(fSize); 81 for (size_t i = 0; i < numChunks; ++i) { 82 if (Chunk chunk = chunks[i]) { // There are set bits 83 const size_t index = i * kChunkBits; 84 for (size_t j = 0; j < kChunkBits; ++j) { 85 if (0x1 & (chunk >> j)) { 86 f(index + j); 87 } 88 } 89 } 90 } 91 } 92 93 using OptionalIndex = skstd::optional<size_t>; 94 95 // If any bits are set, returns the index of the first. findFirst()96 OptionalIndex findFirst() { 97 const Chunk* chunks = fChunks.get(); 98 const size_t numChunks = NumChunksFor(fSize); 99 for (size_t i = 0; i < numChunks; ++i) { 100 if (Chunk chunk = chunks[i]) { // There are set bits 101 static_assert(kChunkBits <= std::numeric_limits<uint32_t>::digits, "SkCTZ"); 102 const size_t bitIndex = i * kChunkBits + SkCTZ(chunk); 103 return OptionalIndex(bitIndex); 104 } 105 } 106 return OptionalIndex(); 107 } 108 109 // If any bits are not set, returns the index of the first. findFirstUnset()110 OptionalIndex findFirstUnset() { 111 const Chunk* chunks = fChunks.get(); 112 const size_t numChunks = NumChunksFor(fSize); 113 for (size_t i = 0; i < numChunks; ++i) { 114 if (Chunk chunk = ~chunks[i]) { // if there are unset bits ... 115 static_assert(kChunkBits <= std::numeric_limits<uint32_t>::digits, "SkCTZ"); 116 const size_t bitIndex = i * kChunkBits + SkCTZ(chunk); 117 if (bitIndex >= fSize) { 118 break; 119 } 120 return OptionalIndex(bitIndex); 121 } 122 } 123 return OptionalIndex(); 124 } 125 126 private: 127 size_t fSize; 128 129 using Chunk = uint32_t; 130 static_assert(std::numeric_limits<Chunk>::radix == 2); 131 inline static constexpr size_t kChunkBits = std::numeric_limits<Chunk>::digits; 132 static_assert(kChunkBits == sizeof(Chunk)*CHAR_BIT, "SkBitSet must use every bit in a Chunk"); 133 std::unique_ptr<Chunk, SkFunctionWrapper<void(void*), sk_free>> fChunks; 134 chunkFor(size_t index)135 Chunk* chunkFor(size_t index) const { 136 return fChunks.get() + (index / kChunkBits); 137 } 138 ChunkMaskFor(size_t index)139 static constexpr Chunk ChunkMaskFor(size_t index) { 140 return (Chunk)1 << (index & (kChunkBits-1)); 141 } 142 NumChunksFor(size_t size)143 static constexpr size_t NumChunksFor(size_t size) { 144 return (size + (kChunkBits-1)) / kChunkBits; 145 } 146 }; 147 148 #endif 149