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