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