Line data    Source code

       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 "SkTDArray.h"
      12             : #include "SkTemplates.h"
      13             : 
      14           0 : class SkBitSet {
      15             : public:
      16           0 :     explicit SkBitSet(int numberOfBits) {
      17           0 :         SkASSERT(numberOfBits >= 0);
      18           0 :         fDwordCount = (numberOfBits + 31) / 32;  // Round up size to 32-bit boundary.
      19           0 :         if (fDwordCount > 0) {
      20           0 :             fBitData.reset((uint32_t*)sk_calloc_throw(fDwordCount * sizeof(uint32_t)));
      21             :         }
      22           0 :     }
      23             : 
      24             :     SkBitSet(const SkBitSet&) = delete;
      25             :     SkBitSet& operator=(const SkBitSet&) = delete;
      26             : 
      27             :     /** Set the value of the index-th bit to true.  */
      28           0 :     void set(int index) {
      29           0 :         uint32_t mask = 1 << (index & 31);
      30           0 :         uint32_t* chunk = this->internalGet(index);
      31           0 :         SkASSERT(chunk);
      32           0 :         *chunk |= mask;
      33           0 :     }
      34             : 
      35             :     template<typename T>
      36             :     void setAll(T* array, int len) {
      37             :         static_assert(std::is_integral<T>::value, "T is integral");
      38             :         for (int i = 0; i < len; ++i) {
      39             :             this->set(static_cast<int>(array[i]));
      40             :         }
      41             :     }
      42             : 
      43           0 :     bool has(int index) const {
      44           0 :         const uint32_t* chunk = this->internalGet(index);
      45           0 :         uint32_t mask = 1 << (index & 31);
      46           0 :         return chunk && SkToBool(*chunk & mask);
      47             :     }
      48             : 
      49             :     /** Export indices of set bits to T array. */
      50             :     template<typename T>
      51           0 :     void exportTo(SkTDArray<T>* array) const {
      52             :         static_assert(std::is_integral<T>::value, "T is integral");
      53           0 :         SkASSERT(array);
      54           0 :         uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get());
      55           0 :         for (unsigned int i = 0; i < fDwordCount; ++i) {
      56           0 :             uint32_t value = data[i];
      57           0 :             if (value) {  // There are set bits
      58           0 :                 unsigned int index = i * 32;
      59           0 :                 for (unsigned int j = 0; j < 32; ++j) {
      60           0 :                     if (0x1 & (value >> j)) {
      61           0 :                         array->push(index + j);
      62             :                     }
      63             :                 }
      64             :             }
      65             :         }
      66           0 :     }
      67             : 
      68             : private:
      69             :     std::unique_ptr<uint32_t, SkFunctionWrapper<void, void, sk_free>> fBitData;
      70             :     size_t fDwordCount;  // Dword (32-bit) count of the bitset.
      71             : 
      72           0 :     uint32_t* internalGet(int index) const {
      73           0 :         size_t internalIndex = index / 32;
      74           0 :         if (internalIndex >= fDwordCount) {
      75           0 :             return nullptr;
      76             :         }
      77           0 :         return fBitData.get() + internalIndex;
      78             :     }
      79             : };
      80             : 
      81             : 
      82             : #endif