diff options
Diffstat (limited to 'gfx/angle/checkout/src/common/bitset_utils.h')
| -rw-r--r-- | gfx/angle/checkout/src/common/bitset_utils.h | 1106 |
1 files changed, 1106 insertions, 0 deletions
diff --git a/gfx/angle/checkout/src/common/bitset_utils.h b/gfx/angle/checkout/src/common/bitset_utils.h new file mode 100644 index 0000000000..ee9a3f1b9b --- /dev/null +++ b/gfx/angle/checkout/src/common/bitset_utils.h @@ -0,0 +1,1106 @@ +// +// Copyright 2015 The ANGLE Project Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. +// +// bitset_utils: +// Bitset-related helper classes, such as a fast iterator to scan for set bits. +// + +#ifndef COMMON_BITSETITERATOR_H_ +#define COMMON_BITSETITERATOR_H_ + +#include <stdint.h> + +#include <array> + +#include "common/angleutils.h" +#include "common/debug.h" +#include "common/mathutil.h" +#include "common/platform.h" + +namespace angle +{ +// Given x, create 1 << x. +template <typename BitsT, typename ParamT> +constexpr BitsT Bit(ParamT x) +{ + // It's undefined behavior if the shift size is equal to or larger than the width of the type. + ASSERT(static_cast<size_t>(x) < sizeof(BitsT) * 8); + + return (static_cast<BitsT>(1) << static_cast<size_t>(x)); +} + +// Given x, create (1 << x) - 1, i.e. a mask with x bits set. +template <typename BitsT, typename ParamT> +constexpr BitsT BitMask(ParamT x) +{ + if (static_cast<size_t>(x) == 0) + { + return 0; + } + return ((Bit<BitsT>(static_cast<ParamT>(static_cast<size_t>(x) - 1)) - 1) << 1) | 1; +} + +template <size_t N, typename BitsT, typename ParamT = std::size_t> +class BitSetT final +{ + public: + class Reference final + { + public: + ~Reference() {} + Reference &operator=(bool x) + { + mParent->set(mBit, x); + return *this; + } + explicit operator bool() const { return mParent->test(mBit); } + + private: + friend class BitSetT; + + Reference(BitSetT *parent, ParamT bit) : mParent(parent), mBit(bit) {} + + BitSetT *mParent; + ParamT mBit; + }; + + class Iterator final + { + public: + Iterator(const BitSetT &bits); + Iterator &operator++(); + + bool operator==(const Iterator &other) const; + bool operator!=(const Iterator &other) const; + ParamT operator*() const; + + // These helper functions allow mutating an iterator in-flight. + // They only operate on later bits to ensure we don't iterate the same bit twice. + void resetLaterBit(std::size_t index) + { + ASSERT(index > mCurrentBit); + mBitsCopy.reset(index); + } + + void setLaterBit(std::size_t index) + { + ASSERT(index > mCurrentBit); + mBitsCopy.set(index); + } + + void setLaterBits(const BitSetT &bits) + { + ASSERT((BitSetT(bits) &= Mask(mCurrentBit + 1)).none()); + mBitsCopy |= bits; + } + + private: + std::size_t getNextBit(); + + BitSetT mBitsCopy; + std::size_t mCurrentBit; + }; + + using value_type = BitsT; + using param_type = ParamT; + + constexpr BitSetT(); + constexpr explicit BitSetT(BitsT value); + constexpr explicit BitSetT(std::initializer_list<ParamT> init); + + constexpr BitSetT(const BitSetT &other); + constexpr BitSetT &operator=(const BitSetT &other); + + constexpr bool operator==(const BitSetT &other) const; + constexpr bool operator!=(const BitSetT &other) const; + + constexpr bool operator[](ParamT pos) const; + Reference operator[](ParamT pos) { return Reference(this, pos); } + + constexpr bool test(ParamT pos) const; + + constexpr bool all() const; + constexpr bool any() const; + constexpr bool none() const; + constexpr std::size_t count() const; + + constexpr static std::size_t size() { return N; } + + constexpr BitSetT &operator&=(const BitSetT &other); + constexpr BitSetT &operator|=(const BitSetT &other); + constexpr BitSetT &operator^=(const BitSetT &other); + constexpr BitSetT operator~() const; + + constexpr BitSetT &operator&=(BitsT value); + constexpr BitSetT &operator|=(BitsT value); + constexpr BitSetT &operator^=(BitsT value); + + constexpr BitSetT operator<<(std::size_t pos) const; + constexpr BitSetT &operator<<=(std::size_t pos); + constexpr BitSetT operator>>(std::size_t pos) const; + constexpr BitSetT &operator>>=(std::size_t pos); + + constexpr BitSetT &set(); + constexpr BitSetT &set(ParamT pos, bool value = true); + + constexpr BitSetT &reset(); + constexpr BitSetT &reset(ParamT pos); + + constexpr BitSetT &flip(); + constexpr BitSetT &flip(ParamT pos); + + constexpr unsigned long to_ulong() const { return static_cast<unsigned long>(mBits); } + constexpr BitsT bits() const { return mBits; } + + Iterator begin() const { return Iterator(*this); } + Iterator end() const { return Iterator(BitSetT()); } + + constexpr static BitSetT Zero() { return BitSetT(); } + + constexpr ParamT first() const; + constexpr ParamT last() const; + + // Produces a mask of ones up to the "x"th bit. + constexpr static BitsT Mask(std::size_t x) { return BitMask<BitsT>(static_cast<ParamT>(x)); } + + private: + BitsT mBits; +}; + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT>::BitSetT() : mBits(0) +{ + static_assert(N > 0, "Bitset type cannot support zero bits."); + static_assert(N <= sizeof(BitsT) * 8, "Bitset type cannot support a size this large."); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT>::BitSetT(BitsT value) : mBits(value & Mask(N)) +{} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT>::BitSetT(std::initializer_list<ParamT> init) : mBits(0) +{ + for (ParamT element : init) + { + mBits |= Bit<BitsT>(element); + } + ASSERT(mBits == (mBits & Mask(N))); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT>::BitSetT(const BitSetT &other) : mBits(other.mBits) +{} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator=(const BitSetT &other) +{ + mBits = other.mBits; + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr bool BitSetT<N, BitsT, ParamT>::operator==(const BitSetT &other) const +{ + return mBits == other.mBits; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr bool BitSetT<N, BitsT, ParamT>::operator!=(const BitSetT &other) const +{ + return mBits != other.mBits; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr bool BitSetT<N, BitsT, ParamT>::operator[](ParamT pos) const +{ + return test(pos); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr bool BitSetT<N, BitsT, ParamT>::test(ParamT pos) const +{ + return (mBits & Bit<BitsT>(pos)) != 0; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr bool BitSetT<N, BitsT, ParamT>::all() const +{ + ASSERT(mBits == (mBits & Mask(N))); + return mBits == Mask(N); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr bool BitSetT<N, BitsT, ParamT>::any() const +{ + ASSERT(mBits == (mBits & Mask(N))); + return (mBits != 0); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr bool BitSetT<N, BitsT, ParamT>::none() const +{ + ASSERT(mBits == (mBits & Mask(N))); + return (mBits == 0); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr std::size_t BitSetT<N, BitsT, ParamT>::count() const +{ + return gl::BitCount(mBits); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(const BitSetT &other) +{ + mBits &= other.mBits; + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(const BitSetT &other) +{ + mBits |= other.mBits; + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(const BitSetT &other) +{ + mBits = mBits ^ other.mBits; + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator~() const +{ + return BitSetT<N, BitsT, ParamT>(~mBits & Mask(N)); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(BitsT value) +{ + mBits &= value; + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(BitsT value) +{ + mBits |= value; + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(BitsT value) +{ + mBits ^= value; + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator<<(std::size_t pos) const +{ + return BitSetT<N, BitsT, ParamT>((mBits << pos) & Mask(N)); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator<<=(std::size_t pos) +{ + mBits = mBits << pos & Mask(N); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator>>(std::size_t pos) const +{ + return BitSetT<N, BitsT, ParamT>(mBits >> pos); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator>>=(std::size_t pos) +{ + mBits = (mBits >> pos) & Mask(N); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set() +{ + ASSERT(mBits == (mBits & Mask(N))); + mBits = Mask(N); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set(ParamT pos, bool value) +{ + ASSERT(static_cast<size_t>(pos) < N); + if (value) + { + mBits |= Bit<BitsT>(pos); + } + else + { + reset(pos); + } + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset() +{ + ASSERT(mBits == (mBits & Mask(N))); + mBits = 0; + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset(ParamT pos) +{ + ASSERT(static_cast<size_t>(pos) < N); + ASSERT(mBits == (mBits & Mask(N))); + mBits &= ~Bit<BitsT>(pos); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip() +{ + ASSERT(mBits == (mBits & Mask(N))); + mBits ^= Mask(N); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip(ParamT pos) +{ + ASSERT(static_cast<size_t>(pos) < N); + mBits ^= Bit<BitsT>(pos); + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr ParamT BitSetT<N, BitsT, ParamT>::first() const +{ + ASSERT(!none()); + return static_cast<ParamT>(gl::ScanForward(mBits)); +} + +template <size_t N, typename BitsT, typename ParamT> +constexpr ParamT BitSetT<N, BitsT, ParamT>::last() const +{ + ASSERT(!none()); + return static_cast<ParamT>(gl::ScanReverse(mBits)); +} + +template <size_t N, typename BitsT, typename ParamT> +BitSetT<N, BitsT, ParamT>::Iterator::Iterator(const BitSetT &bits) : mBitsCopy(bits), mCurrentBit(0) +{ + if (bits.any()) + { + mCurrentBit = getNextBit(); + } +} + +template <size_t N, typename BitsT, typename ParamT> +ANGLE_INLINE typename BitSetT<N, BitsT, ParamT>::Iterator & +BitSetT<N, BitsT, ParamT>::Iterator::operator++() +{ + ASSERT(mBitsCopy.any()); + mBitsCopy.reset(static_cast<ParamT>(mCurrentBit)); + mCurrentBit = getNextBit(); + return *this; +} + +template <size_t N, typename BitsT, typename ParamT> +bool BitSetT<N, BitsT, ParamT>::Iterator::operator==(const Iterator &other) const +{ + return mBitsCopy == other.mBitsCopy; +} + +template <size_t N, typename BitsT, typename ParamT> +bool BitSetT<N, BitsT, ParamT>::Iterator::operator!=(const Iterator &other) const +{ + return !(*this == other); +} + +template <size_t N, typename BitsT, typename ParamT> +ParamT BitSetT<N, BitsT, ParamT>::Iterator::operator*() const +{ + return static_cast<ParamT>(mCurrentBit); +} + +template <size_t N, typename BitsT, typename ParamT> +std::size_t BitSetT<N, BitsT, ParamT>::Iterator::getNextBit() +{ + if (mBitsCopy.none()) + { + return 0; + } + + return gl::ScanForward(mBitsCopy.mBits); +} + +template <size_t N> +using BitSet8 = BitSetT<N, uint8_t>; + +template <size_t N> +using BitSet16 = BitSetT<N, uint16_t>; + +template <size_t N> +using BitSet32 = BitSetT<N, uint32_t>; + +template <size_t N> +using BitSet64 = BitSetT<N, uint64_t>; + +template <std::size_t N> +class BitSetArray; + +namespace priv +{ + +template <size_t N, typename T> +using EnableIfBitsFit = typename std::enable_if<N <= sizeof(T) * 8>::type; + +template <size_t N, typename Enable = void> +struct GetBitSet +{ + using Type = BitSetArray<N>; +}; + +// Prefer 64-bit bitsets on 64-bit CPUs. They seem faster than 32-bit. +#if defined(ANGLE_IS_64_BIT_CPU) +template <size_t N> +struct GetBitSet<N, EnableIfBitsFit<N, uint64_t>> +{ + using Type = BitSet64<N>; +}; +constexpr std::size_t kDefaultBitSetSize = 64; +using BaseBitSetType = BitSet64<kDefaultBitSetSize>; +#else +template <size_t N> +struct GetBitSet<N, EnableIfBitsFit<N, uint32_t>> +{ + using Type = BitSet32<N>; +}; +constexpr std::size_t kDefaultBitSetSize = 32; +using BaseBitSetType = BitSet32<kDefaultBitSetSize>; +#endif // defined(ANGLE_IS_64_BIT_CPU) + +} // namespace priv + +template <size_t N> +using BitSet = typename priv::GetBitSet<N>::Type; + +template <std::size_t N> +class BitSetArray final +{ + public: + using BaseBitSet = priv::BaseBitSetType; + using value_type = BaseBitSet::value_type; + using param_type = BaseBitSet::param_type; + + constexpr BitSetArray(); + constexpr explicit BitSetArray(std::initializer_list<param_type> init); + + BitSetArray(const BitSetArray<N> &other); + + class Reference final + { + public: + ~Reference() {} + Reference &operator=(bool x) + { + mParent.set(mPosition, x); + return *this; + } + explicit operator bool() const { return mParent.test(mPosition); } + + private: + friend class BitSetArray; + + Reference(BitSetArray &parent, std::size_t pos) : mParent(parent), mPosition(pos) {} + + BitSetArray &mParent; + std::size_t mPosition; + }; + class Iterator final + { + public: + Iterator(const BitSetArray<N> &bitSetArray, std::size_t index); + Iterator &operator++(); + bool operator==(const Iterator &other) const; + bool operator!=(const Iterator &other) const; + size_t operator*() const; + + // These helper functions allow mutating an iterator in-flight. + // They only operate on later bits to ensure we don't iterate the same bit twice. + void resetLaterBit(std::size_t pos) + { + ASSERT(pos > (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator); + prepareCopy(); + mParentCopy.reset(pos); + updateIteratorBit(pos, false); + } + + void setLaterBit(std::size_t pos) + { + ASSERT(pos > (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator); + prepareCopy(); + mParentCopy.set(pos); + updateIteratorBit(pos, true); + } + + void setLaterBits(const BitSetArray &bits) + { + prepareCopy(); + mParentCopy |= bits; + updateIteratorBits(bits); + } + + private: + ANGLE_INLINE void prepareCopy() + { + ASSERT(mParent.mBaseBitSetArray[mIndex].end() == + mParentCopy.mBaseBitSetArray[mIndex].end()); + if (mParentCopy.none()) + { + mParentCopy = mParent; + mCurrentParent = &mParentCopy; + } + } + + ANGLE_INLINE void updateIteratorBit(std::size_t pos, bool setBit) + { + // Get the index and offset, update current interator if within range + size_t index = pos >> kShiftForDivision; + size_t offset = pos & kDefaultBitSetSizeMinusOne; + if (index == mIndex) + { + if (setBit) + { + mCurrentIterator.setLaterBit(offset); + } + else + { + mCurrentIterator.resetLaterBit(offset); + } + } + } + + ANGLE_INLINE void updateIteratorBits(const BitSetArray &bits) + { + mCurrentIterator.setLaterBits(bits.mBaseBitSetArray[mIndex]); + } + + // Problem - + // We want to provide the fastest path possible for usecases that iterate though the bitset. + // + // Options - + // 1) For non-mutating iterations the const ref <mParent> is set as mCurrentParent and only + // for usecases that need to mutate the bitset while iterating we perform a copy of + // <mParent> into <mParentCopy> and modify its bits accordingly. + // 2) The alternate approach was to perform a copy all the time in the constructor + // irrespective of whether it was a mutating usecase or not. + // + // Experiment - + // BitSetIteratorPerfTest was run on a Windows machine with Intel CPU and these were the + // results - + // 1) Copy only when necessary - + // RESULT BitSetIteratorPerf.wall_time: run = 116.1067374961 ns + // RESULT BitSetIteratorPerf.trial_steps : run = 8416124 count + // RESULT BitSetIteratorPerf.total_steps : run = 16832251 count + // 2) Copy always - + // RESULT BitSetIteratorPerf.wall_time: run = 242.7446459439 ns + // RESULT BitSetIteratorPerf.trial_steps : run = 4171416 count + // RESULT BitSetIteratorPerf.total_steps : run = 8342834 count + // + // Resolution - + // We settled on the copy only when necessary path. + size_t mIndex; + const BitSetArray &mParent; + BitSetArray mParentCopy; + const BitSetArray *mCurrentParent; + typename BaseBitSet::Iterator mCurrentIterator; + }; + + constexpr static std::size_t size() { return N; } + Iterator begin() const { return Iterator(*this, 0); } + Iterator end() const { return Iterator(*this, kArraySize); } + constexpr unsigned long to_ulong() const + { + // TODO(anglebug.com/5628): Handle serializing more than kDefaultBitSetSize + for (std::size_t index = 1; index < kArraySize; index++) + { + ASSERT(mBaseBitSetArray[index].none()); + } + return static_cast<unsigned long>(mBaseBitSetArray[0].to_ulong()); + } + + // Assignment operators + constexpr BitSetArray &operator=(const BitSetArray &other); + constexpr BitSetArray &operator&=(const BitSetArray &other); + constexpr BitSetArray &operator|=(const BitSetArray &other); + constexpr BitSetArray &operator^=(const BitSetArray &other); + + // Bitwise operators + constexpr BitSetArray<N> operator&(const angle::BitSetArray<N> &other) const; + constexpr BitSetArray<N> operator|(const angle::BitSetArray<N> &other) const; + constexpr BitSetArray<N> operator^(const angle::BitSetArray<N> &other) const; + + // Relational Operators + constexpr bool operator==(const angle::BitSetArray<N> &other) const; + constexpr bool operator!=(const angle::BitSetArray<N> &other) const; + + // Unary operators + constexpr BitSetArray operator~() const; + constexpr bool operator[](std::size_t pos) const; + constexpr Reference operator[](std::size_t pos) + { + ASSERT(pos < size()); + return Reference(*this, pos); + } + + // Setter, getters and other helper methods + constexpr BitSetArray &set(); + constexpr BitSetArray &set(std::size_t pos, bool value = true); + constexpr BitSetArray &reset(); + constexpr BitSetArray &reset(std::size_t pos); + constexpr bool test(std::size_t pos) const; + constexpr bool all() const; + constexpr bool any() const; + constexpr bool none() const; + constexpr std::size_t count() const; + constexpr bool intersects(const BitSetArray &other) const; + constexpr BitSetArray<N> &flip(); + constexpr param_type first() const; + constexpr param_type last() const; + + constexpr value_type bits(size_t index) const; + + private: + static constexpr std::size_t kDefaultBitSetSizeMinusOne = priv::kDefaultBitSetSize - 1; + static constexpr std::size_t kShiftForDivision = + static_cast<std::size_t>(rx::Log2(static_cast<unsigned int>(priv::kDefaultBitSetSize))); + static constexpr std::size_t kArraySize = + ((N + kDefaultBitSetSizeMinusOne) >> kShiftForDivision); + constexpr static std::size_t kLastElementCount = (N & kDefaultBitSetSizeMinusOne); + constexpr static std::size_t kLastElementMask = priv::BaseBitSetType::Mask( + kLastElementCount == 0 ? priv::kDefaultBitSetSize : kLastElementCount); + + std::array<BaseBitSet, kArraySize> mBaseBitSetArray; +}; + +template <std::size_t N> +constexpr BitSetArray<N>::BitSetArray() +{ + static_assert(N > priv::kDefaultBitSetSize, "BitSetArray type can't support requested size."); + reset(); +} + +template <std::size_t N> +constexpr BitSetArray<N>::BitSetArray(std::initializer_list<param_type> init) +{ + reset(); + + for (param_type element : init) + { + size_t index = element >> kShiftForDivision; + size_t offset = element & kDefaultBitSetSizeMinusOne; + mBaseBitSetArray[index].set(offset, true); + } +} + +template <size_t N> +BitSetArray<N>::BitSetArray(const BitSetArray<N> &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] = other.mBaseBitSetArray[index]; + } +} + +template <size_t N> +BitSetArray<N>::Iterator::Iterator(const BitSetArray<N> &bitSetArray, std::size_t index) + : mIndex(index), + mParent(bitSetArray), + mCurrentParent(&mParent), + mCurrentIterator(mParent.mBaseBitSetArray[0].begin()) +{ + while (mIndex < mCurrentParent->kArraySize) + { + if (mCurrentParent->mBaseBitSetArray[mIndex].any()) + { + break; + } + mIndex++; + } + + if (mIndex < mCurrentParent->kArraySize) + { + mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin(); + } + else + { + mCurrentIterator = mCurrentParent->mBaseBitSetArray[mCurrentParent->kArraySize - 1].end(); + } +} + +template <std::size_t N> +typename BitSetArray<N>::Iterator &BitSetArray<N>::Iterator::operator++() +{ + ++mCurrentIterator; + while (mCurrentIterator == mCurrentParent->mBaseBitSetArray[mIndex].end()) + { + mIndex++; + if (mIndex >= mCurrentParent->kArraySize) + { + break; + } + mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin(); + } + return *this; +} + +template <std::size_t N> +bool BitSetArray<N>::Iterator::operator==(const BitSetArray<N>::Iterator &other) const +{ + return mCurrentIterator == other.mCurrentIterator; +} + +template <std::size_t N> +bool BitSetArray<N>::Iterator::operator!=(const BitSetArray<N>::Iterator &other) const +{ + return mCurrentIterator != other.mCurrentIterator; +} + +template <std::size_t N> +std::size_t BitSetArray<N>::Iterator::operator*() const +{ + return (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::operator=(const BitSetArray<N> &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] = other.mBaseBitSetArray[index]; + } + return *this; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::operator&=(const BitSetArray<N> &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] &= other.mBaseBitSetArray[index]; + } + return *this; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::operator|=(const BitSetArray<N> &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] |= other.mBaseBitSetArray[index]; + } + return *this; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::operator^=(const BitSetArray<N> &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] ^= other.mBaseBitSetArray[index]; + } + return *this; +} + +template <std::size_t N> +constexpr BitSetArray<N> BitSetArray<N>::operator&(const angle::BitSetArray<N> &other) const +{ + angle::BitSetArray<N> result(other); + result &= *this; + return result; +} + +template <std::size_t N> +constexpr BitSetArray<N> BitSetArray<N>::operator|(const angle::BitSetArray<N> &other) const +{ + angle::BitSetArray<N> result(other); + result |= *this; + return result; +} + +template <std::size_t N> +constexpr BitSetArray<N> BitSetArray<N>::operator^(const angle::BitSetArray<N> &other) const +{ + angle::BitSetArray<N> result(other); + result ^= *this; + return result; +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::operator==(const angle::BitSetArray<N> &other) const +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + if (mBaseBitSetArray[index] != other.mBaseBitSetArray[index]) + { + return false; + } + } + return true; +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::operator!=(const angle::BitSetArray<N> &other) const +{ + return !(*this == other); +} + +template <std::size_t N> +constexpr BitSetArray<N> BitSetArray<N>::operator~() const +{ + angle::BitSetArray<N> result; + for (std::size_t index = 0; index < kArraySize; index++) + { + result.mBaseBitSetArray[index] |= ~mBaseBitSetArray[index]; + } + // The last element in result may need special handling + result.mBaseBitSetArray[kArraySize - 1] &= kLastElementMask; + + return result; +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::operator[](std::size_t pos) const +{ + ASSERT(pos < size()); + return test(pos); +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::set() +{ + for (BaseBitSet &baseBitSet : mBaseBitSetArray) + { + baseBitSet.set(); + } + // The last element in mBaseBitSetArray may need special handling + mBaseBitSetArray[kArraySize - 1] &= kLastElementMask; + + return *this; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::set(std::size_t pos, bool value) +{ + ASSERT(pos < size()); + // Get the index and offset, then set the bit + size_t index = pos >> kShiftForDivision; + size_t offset = pos & kDefaultBitSetSizeMinusOne; + mBaseBitSetArray[index].set(offset, value); + return *this; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::reset() +{ + for (BaseBitSet &baseBitSet : mBaseBitSetArray) + { + baseBitSet.reset(); + } + return *this; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::reset(std::size_t pos) +{ + ASSERT(pos < size()); + return set(pos, false); +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::test(std::size_t pos) const +{ + ASSERT(pos < size()); + // Get the index and offset, then test the bit + size_t index = pos >> kShiftForDivision; + size_t offset = pos & kDefaultBitSetSizeMinusOne; + return mBaseBitSetArray[index].test(offset); +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::all() const +{ + constexpr priv::BaseBitSetType kLastElementBitSet = priv::BaseBitSetType(kLastElementMask); + + for (std::size_t index = 0; index < kArraySize - 1; index++) + { + if (!mBaseBitSetArray[index].all()) + { + return false; + } + } + + // The last element in mBaseBitSetArray may need special handling + return mBaseBitSetArray[kArraySize - 1] == kLastElementBitSet; +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::any() const +{ + for (const BaseBitSet &baseBitSet : mBaseBitSetArray) + { + if (baseBitSet.any()) + { + return true; + } + } + return false; +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::none() const +{ + for (const BaseBitSet &baseBitSet : mBaseBitSetArray) + { + if (!baseBitSet.none()) + { + return false; + } + } + return true; +} + +template <std::size_t N> +constexpr std::size_t BitSetArray<N>::count() const +{ + size_t count = 0; + for (const BaseBitSet &baseBitSet : mBaseBitSetArray) + { + count += baseBitSet.count(); + } + return count; +} + +template <std::size_t N> +constexpr bool BitSetArray<N>::intersects(const BitSetArray<N> &other) const +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + if ((mBaseBitSetArray[index].bits() & other.mBaseBitSetArray[index].bits()) != 0) + { + return true; + } + } + return false; +} + +template <std::size_t N> +constexpr BitSetArray<N> &BitSetArray<N>::flip() +{ + for (BaseBitSet &baseBitSet : mBaseBitSetArray) + { + baseBitSet.flip(); + } + + // The last element in mBaseBitSetArray may need special handling + mBaseBitSetArray[kArraySize - 1] &= kLastElementMask; + return *this; +} + +template <std::size_t N> +constexpr typename BitSetArray<N>::param_type BitSetArray<N>::first() const +{ + ASSERT(any()); + for (size_t arrayIndex = 0; arrayIndex < kArraySize; ++arrayIndex) + { + const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex]; + if (baseBitSet.any()) + { + return baseBitSet.first() + arrayIndex * priv::kDefaultBitSetSize; + } + } + UNREACHABLE(); + return 0; +} + +template <std::size_t N> +constexpr typename BitSetArray<N>::param_type BitSetArray<N>::last() const +{ + ASSERT(any()); + for (size_t arrayIndex = kArraySize; arrayIndex > 0; --arrayIndex) + { + const BaseBitSet &baseBitSet = mBaseBitSetArray[arrayIndex - 1]; + if (baseBitSet.any()) + { + return baseBitSet.last() + (arrayIndex - 1) * priv::kDefaultBitSetSize; + } + } + UNREACHABLE(); + return 0; +} + +template <std::size_t N> +constexpr typename BitSetArray<N>::value_type BitSetArray<N>::bits(size_t index) const +{ + return mBaseBitSetArray[index].bits(); +} +} // namespace angle + +template <size_t N, typename BitsT, typename ParamT> +inline constexpr angle::BitSetT<N, BitsT, ParamT> operator&( + const angle::BitSetT<N, BitsT, ParamT> &lhs, + const angle::BitSetT<N, BitsT, ParamT> &rhs) +{ + angle::BitSetT<N, BitsT, ParamT> result(lhs); + result &= rhs.bits(); + return result; +} + +template <size_t N, typename BitsT, typename ParamT> +inline constexpr angle::BitSetT<N, BitsT, ParamT> operator|( + const angle::BitSetT<N, BitsT, ParamT> &lhs, + const angle::BitSetT<N, BitsT, ParamT> &rhs) +{ + angle::BitSetT<N, BitsT, ParamT> result(lhs); + result |= rhs.bits(); + return result; +} + +template <size_t N, typename BitsT, typename ParamT> +inline constexpr angle::BitSetT<N, BitsT, ParamT> operator^( + const angle::BitSetT<N, BitsT, ParamT> &lhs, + const angle::BitSetT<N, BitsT, ParamT> &rhs) +{ + angle::BitSetT<N, BitsT, ParamT> result(lhs); + result ^= rhs.bits(); + return result; +} + +template <size_t N, typename BitsT, typename ParamT> +inline bool operator==(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs) +{ + return lhs.bits() == rhs.bits(); +} + +template <size_t N, typename BitsT, typename ParamT> +inline bool operator!=(angle::BitSetT<N, BitsT, ParamT> &lhs, angle::BitSetT<N, BitsT, ParamT> &rhs) +{ + return !(lhs == rhs); +} + +#endif // COMMON_BITSETITERATOR_H_ |