submodule/skia/src/utils/SkBitSet.h

   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
  15 #include <climits>
  16 #include <cstring>
  17 #include <limits>
  18 #include <memory>
  19 #include <optional>
  20
  21 class SkBitSet {
  22 public:
  23     explicit SkBitSet(size_t size)
  24         : fSize(size)
  25         // May http://wg21.link/p0593 be accepted.
  26         , fChunks((Chunk*)sk_calloc_throw(NumChunksFor(fSize) * sizeof(Chunk)))
  27     {}
  28
  29     SkBitSet(const SkBitSet&) = delete;
  30     SkBitSet& operator=(const SkBitSet&) = delete;
  31     SkBitSet(SkBitSet&& that) { *this = std::move(that); }
  32     SkBitSet& operator=(SkBitSet&& that) {
  33         if (this != &that) {
  34             this->fSize = that.fSize;
  35             this->fChunks = std::move(that.fChunks);
  36             that.fSize = 0;
  37         }
  38         return *this;
  39     }
  40     ~SkBitSet() = default;
  41
  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);
  46     }
  47
  48     /** Sets every bit in the bitset to true. */
  49     void set() {
  50         Chunk* chunks = fChunks.get();
  51         const size_t numChunks = NumChunksFor(fSize);
  52         std::memset(chunks, 0xFF, sizeof(Chunk) * numChunks);
  53     }
  54
  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);
  59     }
  60
  61     /** Sets every bit in the bitset to false. */
  62     void reset() {
  63         Chunk* chunks = fChunks.get();
  64         const size_t numChunks = NumChunksFor(fSize);
  65         std::memset(chunks, 0, sizeof(Chunk) * numChunks);
  66     }
  67
  68     bool test(size_t index) const {
  69         SkASSERT(index < fSize);
  70         return SkToBool(*this->chunkFor(index) & ChunkMaskFor(index));
  71     }
  72
  73     size_t size() const {
  74         return fSize;
  75     }
  76
  77     // Calls f(size_t index) for each set index.
  78     template<typename FN>
  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)) {
  87                         f(index + j);
  88                     }
  89                 }
  90             }
  91         }
  92     }
  93
  94     using OptionalIndex = std::optional<size_t>;
  95
  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);
 105             }
 106         }
 107         return OptionalIndex();
 108     }
 109
 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) {
 119                     break;
 120                 }
 121                 return OptionalIndex(bitIndex);
 122             }
 123         }
 124         return OptionalIndex();
 125     }
 126
 127 private:
 128     size_t fSize;
 129
 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;
 135
 136     Chunk* chunkFor(size_t index) const {
 137         return fChunks.get() + (index / kChunkBits);
 138     }
 139
 140     static constexpr Chunk ChunkMaskFor(size_t index) {
 141         return (Chunk)1 << (index & (kChunkBits-1));
 142     }
 143
 144     static constexpr size_t NumChunksFor(size_t size) {
 145         return (size + (kChunkBits-1)) / kChunkBits;
 146     }
 147 };
 148
 149 #endif