Corentin Wallez | 4a9ef4e | 2018-07-18 11:40:26 +0200 | [diff] [blame] | 1 | // Copyright 2017 The Dawn Authors |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | // you may not use this file except in compliance with the License. |
| 5 | // You may obtain a copy of the License at |
| 6 | // |
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | // |
| 9 | // Unless required by applicable law or agreed to in writing, software |
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | // See the License for the specific language governing permissions and |
| 13 | // limitations under the License. |
| 14 | |
Corentin Wallez | fffe6df | 2017-07-06 14:41:13 -0400 | [diff] [blame] | 15 | #ifndef COMMON_BITSETITERATOR_H_ |
| 16 | #define COMMON_BITSETITERATOR_H_ |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 17 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 18 | #include "common/Assert.h" |
Corentin Wallez | fffe6df | 2017-07-06 14:41:13 -0400 | [diff] [blame] | 19 | #include "common/Math.h" |
Austin Eng | 7a4685f | 2020-06-17 22:35:19 +0000 | [diff] [blame] | 20 | #include "common/UnderlyingType.h" |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 21 | |
| 22 | #include <bitset> |
| 23 | #include <limits> |
| 24 | |
| 25 | // This is ANGLE's BitSetIterator class with a customizable return type |
Austin Eng | ed8a8c0 | 2021-06-04 22:23:56 +0000 | [diff] [blame] | 26 | // TODO(crbug.com/dawn/306): it could be optimized, in particular when N <= 64 |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 27 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 28 | template <typename T> |
| 29 | T roundUp(const T value, const T alignment) { |
| 30 | auto temp = value + alignment - static_cast<T>(1); |
| 31 | return temp - temp % alignment; |
| 32 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 33 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 34 | template <size_t N, typename T> |
| 35 | class BitSetIterator final { |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 36 | public: |
| 37 | BitSetIterator(const std::bitset<N>& bitset); |
| 38 | BitSetIterator(const BitSetIterator& other); |
| 39 | BitSetIterator& operator=(const BitSetIterator& other); |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 40 | |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 41 | class Iterator final { |
| 42 | public: |
| 43 | Iterator(const std::bitset<N>& bits); |
| 44 | Iterator& operator++(); |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 45 | |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 46 | bool operator==(const Iterator& other) const; |
| 47 | bool operator!=(const Iterator& other) const; |
Austin Eng | 7a4685f | 2020-06-17 22:35:19 +0000 | [diff] [blame] | 48 | |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 49 | T operator*() const { |
Austin Eng | 7a4685f | 2020-06-17 22:35:19 +0000 | [diff] [blame] | 50 | using U = UnderlyingType<T>; |
Corentin Wallez | 519edd5 | 2020-07-08 18:50:30 +0000 | [diff] [blame] | 51 | ASSERT(static_cast<U>(mCurrentBit) <= std::numeric_limits<U>::max()); |
Austin Eng | 7a4685f | 2020-06-17 22:35:19 +0000 | [diff] [blame] | 52 | return static_cast<T>(static_cast<U>(mCurrentBit)); |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 53 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 54 | |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 55 | private: |
| 56 | unsigned long getNextBit(); |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 57 | |
Corentin Wallez | 4bfc153 | 2020-04-14 18:15:14 +0000 | [diff] [blame] | 58 | static constexpr size_t kBitsPerWord = sizeof(uint32_t) * 8; |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 59 | std::bitset<N> mBits; |
| 60 | unsigned long mCurrentBit; |
| 61 | unsigned long mOffset; |
| 62 | }; |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 63 | |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 64 | Iterator begin() const { |
| 65 | return Iterator(mBits); |
| 66 | } |
| 67 | Iterator end() const { |
| 68 | return Iterator(std::bitset<N>(0)); |
| 69 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 70 | |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 71 | private: |
| 72 | const std::bitset<N> mBits; |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 73 | }; |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 74 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 75 | template <size_t N, typename T> |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 76 | BitSetIterator<N, T>::BitSetIterator(const std::bitset<N>& bitset) : mBits(bitset) { |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 77 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 78 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 79 | template <size_t N, typename T> |
Corentin Wallez | 9d01c6c | 2017-11-24 11:45:29 -0500 | [diff] [blame] | 80 | BitSetIterator<N, T>::BitSetIterator(const BitSetIterator& other) : mBits(other.mBits) { |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 81 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 82 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 83 | template <size_t N, typename T> |
| 84 | BitSetIterator<N, T>& BitSetIterator<N, T>::operator=(const BitSetIterator& other) { |
| 85 | mBits = other.mBits; |
| 86 | return *this; |
| 87 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 88 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 89 | template <size_t N, typename T> |
| 90 | BitSetIterator<N, T>::Iterator::Iterator(const std::bitset<N>& bits) |
| 91 | : mBits(bits), mCurrentBit(0), mOffset(0) { |
| 92 | if (bits.any()) { |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 93 | mCurrentBit = getNextBit(); |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 94 | } else { |
Corentin Wallez | 4bfc153 | 2020-04-14 18:15:14 +0000 | [diff] [blame] | 95 | mOffset = static_cast<unsigned long>(roundUp(N, kBitsPerWord)); |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 96 | } |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 97 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 98 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 99 | template <size_t N, typename T> |
| 100 | typename BitSetIterator<N, T>::Iterator& BitSetIterator<N, T>::Iterator::operator++() { |
Corentin Wallez | 83a9c9d | 2018-07-18 13:37:54 +0200 | [diff] [blame] | 101 | DAWN_ASSERT(mBits.any()); |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 102 | mBits.set(mCurrentBit - mOffset, 0); |
| 103 | mCurrentBit = getNextBit(); |
| 104 | return *this; |
| 105 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 106 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 107 | template <size_t N, typename T> |
| 108 | bool BitSetIterator<N, T>::Iterator::operator==(const Iterator& other) const { |
| 109 | return mOffset == other.mOffset && mBits == other.mBits; |
| 110 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 111 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 112 | template <size_t N, typename T> |
| 113 | bool BitSetIterator<N, T>::Iterator::operator!=(const Iterator& other) const { |
| 114 | return !(*this == other); |
| 115 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 116 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 117 | template <size_t N, typename T> |
| 118 | unsigned long BitSetIterator<N, T>::Iterator::getNextBit() { |
| 119 | static std::bitset<N> wordMask(std::numeric_limits<uint32_t>::max()); |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 120 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 121 | while (mOffset < N) { |
Kai Ninomiya | 78c8b83 | 2017-07-21 17:00:22 -0700 | [diff] [blame] | 122 | uint32_t wordBits = static_cast<uint32_t>((mBits & wordMask).to_ulong()); |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 123 | if (wordBits != 0ul) { |
| 124 | return ScanForward(wordBits) + mOffset; |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 125 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 126 | |
Corentin Wallez | 4bfc153 | 2020-04-14 18:15:14 +0000 | [diff] [blame] | 127 | mBits >>= kBitsPerWord; |
| 128 | mOffset += kBitsPerWord; |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 129 | } |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 130 | return 0; |
| 131 | } |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 132 | |
Corentin Wallez | fd589f3 | 2017-07-10 13:46:05 -0400 | [diff] [blame] | 133 | // Helper to avoid needing to specify the template parameter size |
| 134 | template <size_t N> |
| 135 | BitSetIterator<N, uint32_t> IterateBitSet(const std::bitset<N>& bitset) { |
| 136 | return BitSetIterator<N, uint32_t>(bitset); |
Corentin Wallez | f07e3bd | 2017-04-20 14:38:20 -0400 | [diff] [blame] | 137 | } |
| 138 | |
Corentin Wallez | fffe6df | 2017-07-06 14:41:13 -0400 | [diff] [blame] | 139 | #endif // COMMON_BITSETITERATOR_H_ |