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