blob: 4ca80e1edb0cc191b341063c92e5dbec6128305c [file] [log] [blame]
/*
* 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 <cstring>
#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) { *this = std::move(that); }
SkBitSet& operator=(SkBitSet&& that) {
if (this != &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);
}
/** Sets every bit in the bitset to true. */
void set() {
Chunk* chunks = fChunks.get();
const size_t numChunks = NumChunksFor(fSize);
std::memset(chunks, 0xFF, sizeof(Chunk) * numChunks);
}
/** Set the value of the index-th bit to false. */
void reset(size_t index) {
SkASSERT(index < fSize);
*this->chunkFor(index) &= ~ChunkMaskFor(index);
}
/** Sets every bit in the bitset to false. */
void reset() {
Chunk* chunks = fChunks.get();
const size_t numChunks = NumChunksFor(fSize);
std::memset(chunks, 0, sizeof(Chunk) * numChunks);
}
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 * kChunkBits;
for (size_t j = 0; j < kChunkBits; ++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(kChunkBits <= std::numeric_limits<uint32_t>::digits, "SkCTZ");
const size_t bitIndex = i * kChunkBits + SkCTZ(chunk);
return OptionalIndex(bitIndex);
}
}
return OptionalIndex();
}
// If any bits are not set, returns the index of the first.
OptionalIndex findFirstUnset() {
const Chunk* chunks = fChunks.get();
const size_t numChunks = NumChunksFor(fSize);
for (size_t i = 0; i < numChunks; ++i) {
if (Chunk chunk = ~chunks[i]) { // if there are unset bits ...
static_assert(kChunkBits <= std::numeric_limits<uint32_t>::digits, "SkCTZ");
const size_t bitIndex = i * kChunkBits + SkCTZ(chunk);
if (bitIndex >= fSize) {
break;
}
return OptionalIndex(bitIndex);
}
}
return OptionalIndex();
}
private:
size_t fSize;
using Chunk = uint32_t;
static_assert(std::numeric_limits<Chunk>::radix == 2);
static constexpr size_t kChunkBits = std::numeric_limits<Chunk>::digits;
static_assert(kChunkBits == sizeof(Chunk)*CHAR_BIT, "SkBitSet must use every bit in a Chunk");
std::unique_ptr<Chunk, SkFunctionWrapper<void(void*), sk_free>> fChunks;
Chunk* chunkFor(size_t index) const {
return fChunks.get() + (index / kChunkBits);
}
static constexpr Chunk ChunkMaskFor(size_t index) {
return (Chunk)1 << (index & (kChunkBits-1));
}
static constexpr size_t NumChunksFor(size_t size) {
return (size + (kChunkBits-1)) / kChunkBits;
}
};
#endif