180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2011 Google Inc. 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkBitSet_DEFINED 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkBitSet_DEFINED 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTypes.h" 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTDArray.h" 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkBitSet { 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** NumberOfBits must be greater than zero. 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru explicit SkBitSet(int numberOfBits); 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru explicit SkBitSet(const SkBitSet& source); 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 237839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkBitSet& operator=(const SkBitSet& rhs); 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool operator==(const SkBitSet& rhs); 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool operator!=(const SkBitSet& rhs); 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Clear all data. 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void clearAll(); 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Set the value of the index-th bit. 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void setBit(int index, bool value); 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Test if bit index is set. 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool isBitSet(int index) const; 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Or bits from source. false is returned if this doesn't have the same 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * bit count as source. 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool orBits(const SkBitSet& source); 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /** Export indices of set bits to T array. 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru template<typename T> 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void exportTo(SkTDArray<T>* array) const { 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(array); 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get()); 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (unsigned int i = 0; i < fDwordCount; ++i) { 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t value = data[i]; 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (value) { // There are set bits 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru unsigned int index = i * 32; 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (unsigned int j = 0; j < 32; ++j) { 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (0x1 & (value >> j)) { 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru array->push(index + j); 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkAutoFree fBitData; 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // Dword (32-bit) count of the bitset. 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t fDwordCount; 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t fBitCount; 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint32_t* internalGet(int index) const { 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT((size_t)index < fBitCount); 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t internalIndex = index / 32; 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(internalIndex < fDwordCount); 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return reinterpret_cast<uint32_t*>(fBitData.get()) + internalIndex; 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 79