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