1 
2 /*
3  * Copyright 2011 Google Inc.
4  *
5  * Use of this source code is governed by a BSD-style license that can be
6  * found in the LICENSE file.
7  */
8 
9 
10 #ifndef SkBitSet_DEFINED
11 #define SkBitSet_DEFINED
12 
13 #include "SkTypes.h"
14 #include "SkTDArray.h"
15 
16 class SkBitSet {
17 public:
18     /** NumberOfBits must be greater than zero.
19      */
20     explicit SkBitSet(int numberOfBits);
21     explicit SkBitSet(const SkBitSet& source);
22 
23     SkBitSet& operator=(const SkBitSet& rhs);
24     bool operator==(const SkBitSet& rhs);
25     bool operator!=(const SkBitSet& rhs);
26 
27     /** Clear all data.
28      */
29     void clearAll();
30 
31     /** Set the value of the index-th bit.
32      */
setBit(int index,bool value)33     void setBit(int index, bool value) {
34         uint32_t mask = 1 << (index & 31);
35         uint32_t* chunk = this->internalGet(index);
36         if (value) {
37             *chunk |= mask;
38         } else {
39             *chunk &= ~mask;
40         }
41     }
42 
43     /** Test if bit index is set.
44      */
isBitSet(int index)45     bool isBitSet(int index) const {
46         uint32_t mask = 1 << (index & 31);
47         return SkToBool(*this->internalGet(index) & mask);
48     }
49 
50     /** Or bits from source.  false is returned if this doesn't have the same
51      *  bit count as source.
52      */
53     bool orBits(const SkBitSet& source);
54 
55     /** Export indices of set bits to T array.
56      */
57     template<typename T>
exportTo(SkTDArray<T> * array)58     void exportTo(SkTDArray<T>* array) const {
59         SkASSERT(array);
60         uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get());
61         for (unsigned int i = 0; i < fDwordCount; ++i) {
62             uint32_t value = data[i];
63             if (value) {  // There are set bits
64                 unsigned int index = i * 32;
65                 for (unsigned int j = 0; j < 32; ++j) {
66                     if (0x1 & (value >> j)) {
67                         array->push(index + j);
68                     }
69                 }
70             }
71         }
72     }
73 
74 private:
75     SkAutoFree fBitData;
76     // Dword (32-bit) count of the bitset.
77     size_t fDwordCount;
78     size_t fBitCount;
79 
internalGet(int index)80     uint32_t* internalGet(int index) const {
81         SkASSERT((size_t)index < fBitCount);
82         size_t internalIndex = index / 32;
83         SkASSERT(internalIndex < fDwordCount);
84         return reinterpret_cast<uint32_t*>(fBitData.get()) + internalIndex;
85     }
86 };
87 
88 
89 #endif
90