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
14class SkBitSet {
15public:
16    explicit SkBitSet(int numberOfBits) {
17        SkASSERT(numberOfBits >= 0);
18        fDwordCount = (numberOfBits + 31) / 32;  // Round up size to 32-bit boundary.
19        if (fDwordCount > 0) {
20            fBitData.reset((uint32_t*)sk_calloc_throw(fDwordCount * sizeof(uint32_t)));
21        }
22    }
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    void set(int index) {
29        uint32_t mask = 1 << (index & 31);
30        uint32_t* chunk = this->internalGet(index);
31        SkASSERT(chunk);
32        *chunk |= mask;
33    }
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    bool has(int index) const {
44        const uint32_t* chunk = this->internalGet(index);
45        uint32_t mask = 1 << (index & 31);
46        return chunk && SkToBool(*chunk & mask);
47    }
48
49    /** Export indices of set bits to T array. */
50    template<typename T>
51    void exportTo(SkTDArray<T>* array) const {
52        static_assert(std::is_integral<T>::value, "T is integral");
53        SkASSERT(array);
54        uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get());
55        for (unsigned int i = 0; i < fDwordCount; ++i) {
56            uint32_t value = data[i];
57            if (value) {  // There are set bits
58                unsigned int index = i * 32;
59                for (unsigned int j = 0; j < 32; ++j) {
60                    if (0x1 & (value >> j)) {
61                        array->push(index + j);
62                    }
63                }
64            }
65        }
66    }
67
68private:
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    uint32_t* internalGet(int index) const {
73        size_t internalIndex = index / 32;
74        if (internalIndex >= fDwordCount) {
75            return nullptr;
76        }
77        return fBitData.get() + internalIndex;
78    }
79};
80
81
82#endif
83