1d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 3d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org */ 7d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 8d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org#ifndef SkBitSet_DEFINED 9d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org#define SkBitSet_DEFINED 10d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 1117e66e2d341ab684eec7841fd383af85bb4aa625vandebo@chromium.org#include "SkTDArray.h" 12e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary#include "SkTemplates.h" 13d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 14d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.orgclass SkBitSet { 15d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.orgpublic: 16e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary explicit SkBitSet(int numberOfBits) { 17e202bd8b71f6aa184c2c8ce6f653755de1331c88halcanary SkASSERT(numberOfBits >= 0); 18e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary fDwordCount = (numberOfBits + 31) / 32; // Round up size to 32-bit boundary. 19e202bd8b71f6aa184c2c8ce6f653755de1331c88halcanary if (fDwordCount > 0) { 20e202bd8b71f6aa184c2c8ce6f653755de1331c88halcanary fBitData.reset((uint32_t*)sk_calloc_throw(fDwordCount * sizeof(uint32_t))); 21e202bd8b71f6aa184c2c8ce6f653755de1331c88halcanary } 22e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary } 23e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary 24530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary SkBitSet(const SkBitSet&) = delete; 25530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary SkBitSet& operator=(const SkBitSet&) = delete; 26d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 27e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary /** Set the value of the index-th bit to true. */ 28e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary void set(int index) { 29e099dd73dff0f447029323e918118a189bb27679mtklein uint32_t mask = 1 << (index & 31); 30e099dd73dff0f447029323e918118a189bb27679mtklein uint32_t* chunk = this->internalGet(index); 31e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary SkASSERT(chunk); 32e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary *chunk |= mask; 33e099dd73dff0f447029323e918118a189bb27679mtklein } 34530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary 35530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary template<typename T> 36530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary void setAll(T* array, int len) { 37530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary static_assert(std::is_integral<T>::value, "T is integral"); 38530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary for (int i = 0; i < len; ++i) { 39530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary this->set(static_cast<int>(array[i])); 40530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary } 41530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary } 42d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 43e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary bool has(int index) const { 44e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary const uint32_t* chunk = this->internalGet(index); 45e099dd73dff0f447029323e918118a189bb27679mtklein uint32_t mask = 1 << (index & 31); 46e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary return chunk && SkToBool(*chunk & mask); 47e099dd73dff0f447029323e918118a189bb27679mtklein } 48d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 49e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary /** Export indices of set bits to T array. */ 50b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com template<typename T> 51b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com void exportTo(SkTDArray<T>* array) const { 52530032a18e373ee673ae96fdbfa1fae6292f8f08halcanary static_assert(std::is_integral<T>::value, "T is integral"); 53b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com SkASSERT(array); 54b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get()); 55b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com for (unsigned int i = 0; i < fDwordCount; ++i) { 56b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com uint32_t value = data[i]; 57b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com if (value) { // There are set bits 58b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com unsigned int index = i * 32; 59b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com for (unsigned int j = 0; j < 32; ++j) { 60b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com if (0x1 & (value >> j)) { 61b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com array->push(index + j); 62b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com } 63b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com } 64b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com } 65b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com } 66b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com } 6717e66e2d341ab684eec7841fd383af85bb4aa625vandebo@chromium.org 68d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.orgprivate: 69e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary std::unique_ptr<uint32_t, SkFunctionWrapper<void, void, sk_free>> fBitData; 70e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary size_t fDwordCount; // Dword (32-bit) count of the bitset. 71d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 729859428e71c6041928e6dd741ae3284017e78e81vandebo@chromium.org uint32_t* internalGet(int index) const { 73d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org size_t internalIndex = index / 32; 74e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary if (internalIndex >= fDwordCount) { 75e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary return nullptr; 76e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary } 77e2348ccb477b97847cd147161a57fbbbfc8bba10halcanary return fBitData.get() + internalIndex; 78d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org } 79d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org}; 80d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 81d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org 82d3a8c94dfdabb333b12da3ff796d1f558cb06fbavandebo@chromium.org#endif 83