2 * Copyright 2011 Google Inc.
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
8 #ifndef SkBitSet_DEFINED
9 #define SkBitSet_DEFINED
11 #include "include/private/SkMalloc.h"
12 #include "include/private/SkTemplates.h"
13 #include "src/core/SkMathPriv.h"
23 explicit SkBitSet(size_t size)
25 // May http://wg21.link/p0593 be accepted.
26 , fChunks((Chunk*)sk_calloc_throw(NumChunksFor(fSize) * sizeof(Chunk)))
29 SkBitSet(const SkBitSet&) = delete;
30 SkBitSet& operator=(const SkBitSet&) = delete;
31 SkBitSet(SkBitSet&& that) { *this = std::move(that); }
32 SkBitSet& operator=(SkBitSet&& that) {
34 this->fSize = that.fSize;
35 this->fChunks = std::move(that.fChunks);
40 ~SkBitSet() = default;
42 /** Set the value of the index-th bit to true. */
43 void set(size_t index) {
44 SkASSERT(index < fSize);
45 *this->chunkFor(index) |= ChunkMaskFor(index);
48 /** Sets every bit in the bitset to true. */
50 Chunk* chunks = fChunks.get();
51 const size_t numChunks = NumChunksFor(fSize);
52 std::memset(chunks, 0xFF, sizeof(Chunk) * numChunks);
55 /** Set the value of the index-th bit to false. */
56 void reset(size_t index) {
57 SkASSERT(index < fSize);
58 *this->chunkFor(index) &= ~ChunkMaskFor(index);
61 /** Sets every bit in the bitset to false. */
63 Chunk* chunks = fChunks.get();
64 const size_t numChunks = NumChunksFor(fSize);
65 std::memset(chunks, 0, sizeof(Chunk) * numChunks);
68 bool test(size_t index) const {
69 SkASSERT(index < fSize);
70 return SkToBool(*this->chunkFor(index) & ChunkMaskFor(index));
77 // Calls f(size_t index) for each set index.
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)) {
94 using OptionalIndex = std::optional<size_t>;
96 // If any bits are set, returns the index of the first.
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);
107 return OptionalIndex();
110 // If any bits are not set, returns the index of the first.
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) {
121 return OptionalIndex(bitIndex);
124 return OptionalIndex();
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;
136 Chunk* chunkFor(size_t index) const {
137 return fChunks.get() + (index / kChunkBits);
140 static constexpr Chunk ChunkMaskFor(size_t index) {
141 return (Chunk)1 << (index & (kChunkBits-1));
144 static constexpr size_t NumChunksFor(size_t size) {
145 return (size + (kChunkBits-1)) / kChunkBits;