blob: 5a1c10ff69c7d3e80ac86b65924ee5227def4fd7 [file] [log] [blame]
Corentin Wallez4a9ef4e2018-07-18 11:40:26 +02001// Copyright 2017 The Dawn Authors
Corentin Wallezf07e3bd2017-04-20 14:38:20 -04002//
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 Wallezfffe6df2017-07-06 14:41:13 -040015#ifndef COMMON_BITSETITERATOR_H_
16#define COMMON_BITSETITERATOR_H_
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040017
Corentin Wallezfd589f32017-07-10 13:46:05 -040018#include "common/Assert.h"
Corentin Wallezfffe6df2017-07-06 14:41:13 -040019#include "common/Math.h"
Austin Eng7a4685f2020-06-17 22:35:19 +000020#include "common/UnderlyingType.h"
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040021
22#include <bitset>
23#include <limits>
24
25// This is ANGLE's BitSetIterator class with a customizable return type
Austin Enged8a8c02021-06-04 22:23:56 +000026// TODO(crbug.com/dawn/306): it could be optimized, in particular when N <= 64
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040027
Corentin Wallezfd589f32017-07-10 13:46:05 -040028template <typename T>
29T roundUp(const T value, const T alignment) {
30 auto temp = value + alignment - static_cast<T>(1);
31 return temp - temp % alignment;
32}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040033
Corentin Wallezfd589f32017-07-10 13:46:05 -040034template <size_t N, typename T>
35class BitSetIterator final {
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050036 public:
37 BitSetIterator(const std::bitset<N>& bitset);
38 BitSetIterator(const BitSetIterator& other);
39 BitSetIterator& operator=(const BitSetIterator& other);
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040040
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050041 class Iterator final {
42 public:
43 Iterator(const std::bitset<N>& bits);
44 Iterator& operator++();
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040045
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050046 bool operator==(const Iterator& other) const;
47 bool operator!=(const Iterator& other) const;
Austin Eng7a4685f2020-06-17 22:35:19 +000048
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050049 T operator*() const {
Austin Eng7a4685f2020-06-17 22:35:19 +000050 using U = UnderlyingType<T>;
Corentin Wallez519edd52020-07-08 18:50:30 +000051 ASSERT(static_cast<U>(mCurrentBit) <= std::numeric_limits<U>::max());
Austin Eng7a4685f2020-06-17 22:35:19 +000052 return static_cast<T>(static_cast<U>(mCurrentBit));
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050053 }
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040054
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050055 private:
56 unsigned long getNextBit();
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040057
Corentin Wallez4bfc1532020-04-14 18:15:14 +000058 static constexpr size_t kBitsPerWord = sizeof(uint32_t) * 8;
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050059 std::bitset<N> mBits;
60 unsigned long mCurrentBit;
61 unsigned long mOffset;
62 };
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040063
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050064 Iterator begin() const {
65 return Iterator(mBits);
66 }
67 Iterator end() const {
68 return Iterator(std::bitset<N>(0));
69 }
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040070
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050071 private:
72 const std::bitset<N> mBits;
Corentin Wallezfd589f32017-07-10 13:46:05 -040073};
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040074
Corentin Wallezfd589f32017-07-10 13:46:05 -040075template <size_t N, typename T>
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050076BitSetIterator<N, T>::BitSetIterator(const std::bitset<N>& bitset) : mBits(bitset) {
Corentin Wallezfd589f32017-07-10 13:46:05 -040077}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040078
Corentin Wallezfd589f32017-07-10 13:46:05 -040079template <size_t N, typename T>
Corentin Wallez9d01c6c2017-11-24 11:45:29 -050080BitSetIterator<N, T>::BitSetIterator(const BitSetIterator& other) : mBits(other.mBits) {
Corentin Wallezfd589f32017-07-10 13:46:05 -040081}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040082
Corentin Wallezfd589f32017-07-10 13:46:05 -040083template <size_t N, typename T>
84BitSetIterator<N, T>& BitSetIterator<N, T>::operator=(const BitSetIterator& other) {
85 mBits = other.mBits;
86 return *this;
87}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040088
Corentin Wallezfd589f32017-07-10 13:46:05 -040089template <size_t N, typename T>
90BitSetIterator<N, T>::Iterator::Iterator(const std::bitset<N>& bits)
91 : mBits(bits), mCurrentBit(0), mOffset(0) {
92 if (bits.any()) {
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040093 mCurrentBit = getNextBit();
Corentin Wallezfd589f32017-07-10 13:46:05 -040094 } else {
Corentin Wallez4bfc1532020-04-14 18:15:14 +000095 mOffset = static_cast<unsigned long>(roundUp(N, kBitsPerWord));
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040096 }
Corentin Wallezfd589f32017-07-10 13:46:05 -040097}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -040098
Corentin Wallezfd589f32017-07-10 13:46:05 -040099template <size_t N, typename T>
100typename BitSetIterator<N, T>::Iterator& BitSetIterator<N, T>::Iterator::operator++() {
Corentin Wallez83a9c9d2018-07-18 13:37:54 +0200101 DAWN_ASSERT(mBits.any());
Corentin Wallezfd589f32017-07-10 13:46:05 -0400102 mBits.set(mCurrentBit - mOffset, 0);
103 mCurrentBit = getNextBit();
104 return *this;
105}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400106
Corentin Wallezfd589f32017-07-10 13:46:05 -0400107template <size_t N, typename T>
108bool BitSetIterator<N, T>::Iterator::operator==(const Iterator& other) const {
109 return mOffset == other.mOffset && mBits == other.mBits;
110}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400111
Corentin Wallezfd589f32017-07-10 13:46:05 -0400112template <size_t N, typename T>
113bool BitSetIterator<N, T>::Iterator::operator!=(const Iterator& other) const {
114 return !(*this == other);
115}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400116
Corentin Wallezfd589f32017-07-10 13:46:05 -0400117template <size_t N, typename T>
118unsigned long BitSetIterator<N, T>::Iterator::getNextBit() {
119 static std::bitset<N> wordMask(std::numeric_limits<uint32_t>::max());
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400120
Corentin Wallezfd589f32017-07-10 13:46:05 -0400121 while (mOffset < N) {
Kai Ninomiya78c8b832017-07-21 17:00:22 -0700122 uint32_t wordBits = static_cast<uint32_t>((mBits & wordMask).to_ulong());
Corentin Wallezfd589f32017-07-10 13:46:05 -0400123 if (wordBits != 0ul) {
124 return ScanForward(wordBits) + mOffset;
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400125 }
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400126
Corentin Wallez4bfc1532020-04-14 18:15:14 +0000127 mBits >>= kBitsPerWord;
128 mOffset += kBitsPerWord;
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400129 }
Corentin Wallezfd589f32017-07-10 13:46:05 -0400130 return 0;
131}
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400132
Corentin Wallezfd589f32017-07-10 13:46:05 -0400133// Helper to avoid needing to specify the template parameter size
134template <size_t N>
135BitSetIterator<N, uint32_t> IterateBitSet(const std::bitset<N>& bitset) {
136 return BitSetIterator<N, uint32_t>(bitset);
Corentin Wallezf07e3bd2017-04-20 14:38:20 -0400137}
138
Corentin Wallezfffe6df2017-07-06 14:41:13 -0400139#endif // COMMON_BITSETITERATOR_H_