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