| /* | |
| * Copyright 2011 Google Inc. | |
| * | |
| * Use of this source code is governed by a BSD-style license that can be | |
| * found in the LICENSE file. | |
| */ | |
| #ifndef SkBitSet_DEFINED | |
| #define SkBitSet_DEFINED | |
| #include "include/private/SkMalloc.h" | |
| #include "include/private/SkTemplates.h" | |
| #include "src/core/SkMathPriv.h" | |
| #include <climits> | |
| #include <limits> | |
| #include <memory> | |
| class SkBitSet { | |
| public: | |
| explicit SkBitSet(size_t size) | |
| : fSize(size) | |
| // May http://wg21.link/p0593 be accepted. | |
| , fChunks((Chunk*)sk_calloc_throw(numChunksFor(fSize) * sizeof(Chunk))) | |
| {} | |
| SkBitSet(const SkBitSet&) = delete; | |
| SkBitSet& operator=(const SkBitSet&) = delete; | |
| SkBitSet(SkBitSet&& that) : fSize(that.fSize), fChunks(std::move(that.fChunks)) { | |
| that.fSize = 0; | |
| } | |
| SkBitSet& operator=(SkBitSet&& that) { | |
| this->fSize = that.fSize; | |
| this->fChunks = std::move(that.fChunks); | |
| that.fSize = 0; | |
| return *this; | |
| } | |
| ~SkBitSet() = default; | |
| /** Set the value of the index-th bit to true. */ | |
| void set(size_t index) { | |
| SkASSERT(index < fSize); | |
| *this->chunkFor(index) |= chunkMaskFor(index); | |
| } | |
| /** Set the value of the index-th bit to false. */ | |
| void reset(size_t index) { | |
| SkASSERT(index < fSize); | |
| *this->chunkFor(index) &= ~chunkMaskFor(index); | |
| } | |
| bool test(size_t index) const { | |
| SkASSERT(index < fSize); | |
| return SkToBool(*this->chunkFor(index) & chunkMaskFor(index)); | |
| } | |
| size_t size() const { | |
| return fSize; | |
| } | |
| // Calls f(size_t index) for each set index. | |
| template<typename FN> | |
| void forEachSetIndex(FN f) const { | |
| const Chunk* chunks = fChunks.get(); | |
| const size_t numChunks = numChunksFor(fSize); | |
| for (size_t i = 0; i < numChunks; ++i) { | |
| if (Chunk chunk = chunks[i]) { // There are set bits | |
| const size_t index = i * ChunkBits; | |
| for (size_t j = 0; j < ChunkBits; ++j) { | |
| if (0x1 & (chunk >> j)) { | |
| f(index + j); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| // Use std::optional<size_t> when possible. | |
| class OptionalIndex { | |
| bool fHasValue; | |
| size_t fValue; | |
| public: | |
| OptionalIndex() : fHasValue(false) {} | |
| constexpr OptionalIndex(size_t index) : fHasValue(true), fValue(index) {} | |
| constexpr size_t* operator->() { return &fValue; } | |
| constexpr const size_t* operator->() const { return &fValue; } | |
| constexpr size_t& operator*() & { return fValue; } | |
| constexpr const size_t& operator*() const& { return fValue; } | |
| constexpr size_t&& operator*() && { return std::move(fValue); } | |
| constexpr const size_t&& operator*() const&& { return std::move(fValue); } | |
| constexpr explicit operator bool() const noexcept { return fHasValue; } | |
| constexpr bool has_value() const noexcept { return fHasValue; } | |
| constexpr size_t& value() & { return fValue; } | |
| constexpr const size_t& value() const & { return fValue; } | |
| constexpr size_t&& value() && { return std::move(fValue); } | |
| constexpr const size_t&& value() const && { return std::move(fValue); } | |
| template<typename U> constexpr size_t value_or(U&& defaultValue) const& { | |
| return bool(*this) ? **this | |
| : static_cast<size_t>(std::forward<U>(defaultValue)); | |
| } | |
| template<typename U> constexpr size_t value_or(U&& defaultValue) && { | |
| return bool(*this) ? std::move(**this) | |
| : static_cast<size_t>(std::forward<U>(defaultValue)); | |
| } | |
| }; | |
| // If any bits are set returns the index of the first. | |
| OptionalIndex findFirst() { | |
| const Chunk* chunks = fChunks.get(); | |
| const size_t numChunks = numChunksFor(fSize); | |
| for (size_t i = 0; i < numChunks; ++i) { | |
| if (Chunk chunk = chunks[i]) { // There are set bits | |
| static_assert(ChunkBits <= std::numeric_limits<uint32_t>::digits, "SkCTZ"); | |
| return OptionalIndex(i * ChunkBits + SkCTZ(chunk)); | |
| } | |
| } | |
| return OptionalIndex(); | |
| } | |
| private: | |
| size_t fSize; | |
| using Chunk = uint32_t; | |
| static_assert(std::numeric_limits<Chunk>::radix == 2); | |
| static constexpr size_t ChunkBits = std::numeric_limits<Chunk>::digits; | |
| static_assert(ChunkBits == sizeof(Chunk)*CHAR_BIT, "It would work, but don't waste bits."); | |
| std::unique_ptr<Chunk, SkFunctionWrapper<void(void*), sk_free>> fChunks; | |
| Chunk* chunkFor(size_t index) const { | |
| return fChunks.get() + (index / ChunkBits); | |
| } | |
| static constexpr Chunk chunkMaskFor(size_t index) { | |
| return (Chunk)1 << (index & (ChunkBits-1)); | |
| } | |
| static constexpr size_t numChunksFor(size_t size) { | |
| return (size + (ChunkBits-1)) / ChunkBits; | |
| } | |
| }; | |
| #endif |