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 #include <climits>
15 #include <cstring>
16 #include <limits>
17 #include <memory>
18 
19 class SkBitSet {
20 public:
SkBitSet(size_t size)21     explicit SkBitSet(size_t size)
22         : fSize(size)
23         // May http://wg21.link/p0593 be accepted.
24         , fChunks((Chunk*)sk_calloc_throw(NumChunksFor(fSize) * sizeof(Chunk)))
25     {}
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     // Use std::optional<size_t> when possible.
93     class OptionalIndex {
94         bool fHasValue;
95         size_t fValue;
96     public:
OptionalIndex()97         OptionalIndex() : fHasValue(false) {}
OptionalIndex(size_t index)98         constexpr OptionalIndex(size_t index) : fHasValue(true), fValue(index) {}
99 
100         constexpr size_t* operator->() { return &fValue; }
101         constexpr const size_t* operator->() const { return &fValue; }
102         constexpr size_t& operator*() & { return fValue; }
103         constexpr const size_t& operator*() const& { return fValue; }
104         constexpr size_t&& operator*() && { return std::move(fValue); }
105         constexpr const size_t&& operator*() const&& { return std::move(fValue); }
106 
107         constexpr explicit operator bool() const noexcept { return fHasValue; }
has_value()108         constexpr bool has_value() const noexcept { return fHasValue; }
109 
value()110         constexpr size_t& value() & { return fValue; }
value()111         constexpr const size_t& value() const & { return fValue; }
value()112         constexpr size_t&& value() && { return std::move(fValue); }
value()113         constexpr const size_t&& value() const && { return std::move(fValue); }
114 
value_or(U && defaultValue)115         template<typename U> constexpr size_t value_or(U&& defaultValue) const& {
116             return bool(*this) ? **this
117                                : static_cast<size_t>(std::forward<U>(defaultValue));
118         }
value_or(U && defaultValue)119         template<typename U> constexpr size_t value_or(U&& defaultValue) && {
120             return bool(*this) ? std::move(**this)
121                                : static_cast<size_t>(std::forward<U>(defaultValue));
122         }
123     };
124 
125     // If any bits are set, returns the index of the first.
findFirst()126     OptionalIndex findFirst() {
127         const Chunk* chunks = fChunks.get();
128         const size_t numChunks = NumChunksFor(fSize);
129         for (size_t i = 0; i < numChunks; ++i) {
130             if (Chunk chunk = chunks[i]) {  // There are set bits
131                 static_assert(kChunkBits <= std::numeric_limits<uint32_t>::digits, "SkCTZ");
132                 const size_t bitIndex = i * kChunkBits + SkCTZ(chunk);
133                 return OptionalIndex(bitIndex);
134             }
135         }
136         return OptionalIndex();
137     }
138 
139     // If any bits are not set, returns the index of the first.
findFirstUnset()140     OptionalIndex findFirstUnset() {
141         const Chunk* chunks = fChunks.get();
142         const size_t numChunks = NumChunksFor(fSize);
143         for (size_t i = 0; i < numChunks; ++i) {
144             if (Chunk chunk = ~chunks[i]) {  // if there are unset bits ...
145                 static_assert(kChunkBits <= std::numeric_limits<uint32_t>::digits, "SkCTZ");
146                 const size_t bitIndex = i * kChunkBits + SkCTZ(chunk);
147                 if (bitIndex >= fSize) {
148                     break;
149                 }
150                 return OptionalIndex(bitIndex);
151             }
152         }
153         return OptionalIndex();
154     }
155 
156 private:
157     size_t fSize;
158 
159     using Chunk = uint32_t;
160     static_assert(std::numeric_limits<Chunk>::radix == 2);
161     static constexpr size_t kChunkBits = std::numeric_limits<Chunk>::digits;
162     static_assert(kChunkBits == sizeof(Chunk)*CHAR_BIT, "SkBitSet must use every bit in a Chunk");
163     std::unique_ptr<Chunk, SkFunctionWrapper<void(void*), sk_free>> fChunks;
164 
chunkFor(size_t index)165     Chunk* chunkFor(size_t index) const {
166         return fChunks.get() + (index / kChunkBits);
167     }
168 
ChunkMaskFor(size_t index)169     static constexpr Chunk ChunkMaskFor(size_t index) {
170         return (Chunk)1 << (index & (kChunkBits-1));
171     }
172 
NumChunksFor(size_t size)173     static constexpr size_t NumChunksFor(size_t size) {
174         return (size + (kChunkBits-1)) / kChunkBits;
175     }
176 };
177 
178 #endif
179