From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- gfx/angle/checkout/src/common/bitset_utils.h | 1106 ++++++++++++++++++++++++++ 1 file changed, 1106 insertions(+) create mode 100644 gfx/angle/checkout/src/common/bitset_utils.h (limited to 'gfx/angle/checkout/src/common/bitset_utils.h') 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 + +#include + +#include "common/angleutils.h" +#include "common/debug.h" +#include "common/mathutil.h" +#include "common/platform.h" + +namespace angle +{ +// Given x, create 1 << x. +template +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(x) < sizeof(BitsT) * 8); + + return (static_cast(1) << static_cast(x)); +} + +// Given x, create (1 << x) - 1, i.e. a mask with x bits set. +template +constexpr BitsT BitMask(ParamT x) +{ + if (static_cast(x) == 0) + { + return 0; + } + return ((Bit(static_cast(static_cast(x) - 1)) - 1) << 1) | 1; +} + +template +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 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(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(static_cast(x)); } + + private: + BitsT mBits; +}; + +template +constexpr BitSetT::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 +constexpr BitSetT::BitSetT(BitsT value) : mBits(value & Mask(N)) +{} + +template +constexpr BitSetT::BitSetT(std::initializer_list init) : mBits(0) +{ + for (ParamT element : init) + { + mBits |= Bit(element); + } + ASSERT(mBits == (mBits & Mask(N))); +} + +template +constexpr BitSetT::BitSetT(const BitSetT &other) : mBits(other.mBits) +{} + +template +constexpr BitSetT &BitSetT::operator=(const BitSetT &other) +{ + mBits = other.mBits; + return *this; +} + +template +constexpr bool BitSetT::operator==(const BitSetT &other) const +{ + return mBits == other.mBits; +} + +template +constexpr bool BitSetT::operator!=(const BitSetT &other) const +{ + return mBits != other.mBits; +} + +template +constexpr bool BitSetT::operator[](ParamT pos) const +{ + return test(pos); +} + +template +constexpr bool BitSetT::test(ParamT pos) const +{ + return (mBits & Bit(pos)) != 0; +} + +template +constexpr bool BitSetT::all() const +{ + ASSERT(mBits == (mBits & Mask(N))); + return mBits == Mask(N); +} + +template +constexpr bool BitSetT::any() const +{ + ASSERT(mBits == (mBits & Mask(N))); + return (mBits != 0); +} + +template +constexpr bool BitSetT::none() const +{ + ASSERT(mBits == (mBits & Mask(N))); + return (mBits == 0); +} + +template +constexpr std::size_t BitSetT::count() const +{ + return gl::BitCount(mBits); +} + +template +constexpr BitSetT &BitSetT::operator&=(const BitSetT &other) +{ + mBits &= other.mBits; + return *this; +} + +template +constexpr BitSetT &BitSetT::operator|=(const BitSetT &other) +{ + mBits |= other.mBits; + return *this; +} + +template +constexpr BitSetT &BitSetT::operator^=(const BitSetT &other) +{ + mBits = mBits ^ other.mBits; + return *this; +} + +template +constexpr BitSetT BitSetT::operator~() const +{ + return BitSetT(~mBits & Mask(N)); +} + +template +constexpr BitSetT &BitSetT::operator&=(BitsT value) +{ + mBits &= value; + return *this; +} + +template +constexpr BitSetT &BitSetT::operator|=(BitsT value) +{ + mBits |= value; + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template +constexpr BitSetT &BitSetT::operator^=(BitsT value) +{ + mBits ^= value; + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template +constexpr BitSetT BitSetT::operator<<(std::size_t pos) const +{ + return BitSetT((mBits << pos) & Mask(N)); +} + +template +constexpr BitSetT &BitSetT::operator<<=(std::size_t pos) +{ + mBits = mBits << pos & Mask(N); + return *this; +} + +template +constexpr BitSetT BitSetT::operator>>(std::size_t pos) const +{ + return BitSetT(mBits >> pos); +} + +template +constexpr BitSetT &BitSetT::operator>>=(std::size_t pos) +{ + mBits = (mBits >> pos) & Mask(N); + return *this; +} + +template +constexpr BitSetT &BitSetT::set() +{ + ASSERT(mBits == (mBits & Mask(N))); + mBits = Mask(N); + return *this; +} + +template +constexpr BitSetT &BitSetT::set(ParamT pos, bool value) +{ + ASSERT(static_cast(pos) < N); + if (value) + { + mBits |= Bit(pos); + } + else + { + reset(pos); + } + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template +constexpr BitSetT &BitSetT::reset() +{ + ASSERT(mBits == (mBits & Mask(N))); + mBits = 0; + return *this; +} + +template +constexpr BitSetT &BitSetT::reset(ParamT pos) +{ + ASSERT(static_cast(pos) < N); + ASSERT(mBits == (mBits & Mask(N))); + mBits &= ~Bit(pos); + return *this; +} + +template +constexpr BitSetT &BitSetT::flip() +{ + ASSERT(mBits == (mBits & Mask(N))); + mBits ^= Mask(N); + return *this; +} + +template +constexpr BitSetT &BitSetT::flip(ParamT pos) +{ + ASSERT(static_cast(pos) < N); + mBits ^= Bit(pos); + ASSERT(mBits == (mBits & Mask(N))); + return *this; +} + +template +constexpr ParamT BitSetT::first() const +{ + ASSERT(!none()); + return static_cast(gl::ScanForward(mBits)); +} + +template +constexpr ParamT BitSetT::last() const +{ + ASSERT(!none()); + return static_cast(gl::ScanReverse(mBits)); +} + +template +BitSetT::Iterator::Iterator(const BitSetT &bits) : mBitsCopy(bits), mCurrentBit(0) +{ + if (bits.any()) + { + mCurrentBit = getNextBit(); + } +} + +template +ANGLE_INLINE typename BitSetT::Iterator & +BitSetT::Iterator::operator++() +{ + ASSERT(mBitsCopy.any()); + mBitsCopy.reset(static_cast(mCurrentBit)); + mCurrentBit = getNextBit(); + return *this; +} + +template +bool BitSetT::Iterator::operator==(const Iterator &other) const +{ + return mBitsCopy == other.mBitsCopy; +} + +template +bool BitSetT::Iterator::operator!=(const Iterator &other) const +{ + return !(*this == other); +} + +template +ParamT BitSetT::Iterator::operator*() const +{ + return static_cast(mCurrentBit); +} + +template +std::size_t BitSetT::Iterator::getNextBit() +{ + if (mBitsCopy.none()) + { + return 0; + } + + return gl::ScanForward(mBitsCopy.mBits); +} + +template +using BitSet8 = BitSetT; + +template +using BitSet16 = BitSetT; + +template +using BitSet32 = BitSetT; + +template +using BitSet64 = BitSetT; + +template +class BitSetArray; + +namespace priv +{ + +template +using EnableIfBitsFit = typename std::enable_if::type; + +template +struct GetBitSet +{ + using Type = BitSetArray; +}; + +// Prefer 64-bit bitsets on 64-bit CPUs. They seem faster than 32-bit. +#if defined(ANGLE_IS_64_BIT_CPU) +template +struct GetBitSet> +{ + using Type = BitSet64; +}; +constexpr std::size_t kDefaultBitSetSize = 64; +using BaseBitSetType = BitSet64; +#else +template +struct GetBitSet> +{ + using Type = BitSet32; +}; +constexpr std::size_t kDefaultBitSetSize = 32; +using BaseBitSetType = BitSet32; +#endif // defined(ANGLE_IS_64_BIT_CPU) + +} // namespace priv + +template +using BitSet = typename priv::GetBitSet::Type; + +template +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 init); + + BitSetArray(const BitSetArray &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 &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 is set as mCurrentParent and only + // for usecases that need to mutate the bitset while iterating we perform a copy of + // into 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(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 operator&(const angle::BitSetArray &other) const; + constexpr BitSetArray operator|(const angle::BitSetArray &other) const; + constexpr BitSetArray operator^(const angle::BitSetArray &other) const; + + // Relational Operators + constexpr bool operator==(const angle::BitSetArray &other) const; + constexpr bool operator!=(const angle::BitSetArray &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 &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(rx::Log2(static_cast(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 mBaseBitSetArray; +}; + +template +constexpr BitSetArray::BitSetArray() +{ + static_assert(N > priv::kDefaultBitSetSize, "BitSetArray type can't support requested size."); + reset(); +} + +template +constexpr BitSetArray::BitSetArray(std::initializer_list init) +{ + reset(); + + for (param_type element : init) + { + size_t index = element >> kShiftForDivision; + size_t offset = element & kDefaultBitSetSizeMinusOne; + mBaseBitSetArray[index].set(offset, true); + } +} + +template +BitSetArray::BitSetArray(const BitSetArray &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] = other.mBaseBitSetArray[index]; + } +} + +template +BitSetArray::Iterator::Iterator(const BitSetArray &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 +typename BitSetArray::Iterator &BitSetArray::Iterator::operator++() +{ + ++mCurrentIterator; + while (mCurrentIterator == mCurrentParent->mBaseBitSetArray[mIndex].end()) + { + mIndex++; + if (mIndex >= mCurrentParent->kArraySize) + { + break; + } + mCurrentIterator = mCurrentParent->mBaseBitSetArray[mIndex].begin(); + } + return *this; +} + +template +bool BitSetArray::Iterator::operator==(const BitSetArray::Iterator &other) const +{ + return mCurrentIterator == other.mCurrentIterator; +} + +template +bool BitSetArray::Iterator::operator!=(const BitSetArray::Iterator &other) const +{ + return mCurrentIterator != other.mCurrentIterator; +} + +template +std::size_t BitSetArray::Iterator::operator*() const +{ + return (mIndex * priv::kDefaultBitSetSize) + *mCurrentIterator; +} + +template +constexpr BitSetArray &BitSetArray::operator=(const BitSetArray &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] = other.mBaseBitSetArray[index]; + } + return *this; +} + +template +constexpr BitSetArray &BitSetArray::operator&=(const BitSetArray &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] &= other.mBaseBitSetArray[index]; + } + return *this; +} + +template +constexpr BitSetArray &BitSetArray::operator|=(const BitSetArray &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] |= other.mBaseBitSetArray[index]; + } + return *this; +} + +template +constexpr BitSetArray &BitSetArray::operator^=(const BitSetArray &other) +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + mBaseBitSetArray[index] ^= other.mBaseBitSetArray[index]; + } + return *this; +} + +template +constexpr BitSetArray BitSetArray::operator&(const angle::BitSetArray &other) const +{ + angle::BitSetArray result(other); + result &= *this; + return result; +} + +template +constexpr BitSetArray BitSetArray::operator|(const angle::BitSetArray &other) const +{ + angle::BitSetArray result(other); + result |= *this; + return result; +} + +template +constexpr BitSetArray BitSetArray::operator^(const angle::BitSetArray &other) const +{ + angle::BitSetArray result(other); + result ^= *this; + return result; +} + +template +constexpr bool BitSetArray::operator==(const angle::BitSetArray &other) const +{ + for (std::size_t index = 0; index < kArraySize; index++) + { + if (mBaseBitSetArray[index] != other.mBaseBitSetArray[index]) + { + return false; + } + } + return true; +} + +template +constexpr bool BitSetArray::operator!=(const angle::BitSetArray &other) const +{ + return !(*this == other); +} + +template +constexpr BitSetArray BitSetArray::operator~() const +{ + angle::BitSetArray 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 +constexpr bool BitSetArray::operator[](std::size_t pos) const +{ + ASSERT(pos < size()); + return test(pos); +} + +template +constexpr BitSetArray &BitSetArray::set() +{ + for (BaseBitSet &baseBitSet : mBaseBitSetArray) + { + baseBitSet.set(); + } + // The last element in mBaseBitSetArray may need special handling + mBaseBitSetArray[kArraySize - 1] &= kLastElementMask; + + return *this; +} + +template +constexpr BitSetArray &BitSetArray::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 +constexpr BitSetArray &BitSetArray::reset() +{ + for (BaseBitSet &baseBitSet : mBaseBitSetArray) + { + baseBitSet.reset(); + } + return *this; +} + +template +constexpr BitSetArray &BitSetArray::reset(std::size_t pos) +{ + ASSERT(pos < size()); + return set(pos, false); +} + +template +constexpr bool BitSetArray::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 +constexpr bool BitSetArray::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 +constexpr bool BitSetArray::any() const +{ + for (const BaseBitSet &baseBitSet : mBaseBitSetArray) + { + if (baseBitSet.any()) + { + return true; + } + } + return false; +} + +template +constexpr bool BitSetArray::none() const +{ + for (const BaseBitSet &baseBitSet : mBaseBitSetArray) + { + if (!baseBitSet.none()) + { + return false; + } + } + return true; +} + +template +constexpr std::size_t BitSetArray::count() const +{ + size_t count = 0; + for (const BaseBitSet &baseBitSet : mBaseBitSetArray) + { + count += baseBitSet.count(); + } + return count; +} + +template +constexpr bool BitSetArray::intersects(const BitSetArray &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 +constexpr BitSetArray &BitSetArray::flip() +{ + for (BaseBitSet &baseBitSet : mBaseBitSetArray) + { + baseBitSet.flip(); + } + + // The last element in mBaseBitSetArray may need special handling + mBaseBitSetArray[kArraySize - 1] &= kLastElementMask; + return *this; +} + +template +constexpr typename BitSetArray::param_type BitSetArray::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 +constexpr typename BitSetArray::param_type BitSetArray::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 +constexpr typename BitSetArray::value_type BitSetArray::bits(size_t index) const +{ + return mBaseBitSetArray[index].bits(); +} +} // namespace angle + +template +inline constexpr angle::BitSetT operator&( + const angle::BitSetT &lhs, + const angle::BitSetT &rhs) +{ + angle::BitSetT result(lhs); + result &= rhs.bits(); + return result; +} + +template +inline constexpr angle::BitSetT operator|( + const angle::BitSetT &lhs, + const angle::BitSetT &rhs) +{ + angle::BitSetT result(lhs); + result |= rhs.bits(); + return result; +} + +template +inline constexpr angle::BitSetT operator^( + const angle::BitSetT &lhs, + const angle::BitSetT &rhs) +{ + angle::BitSetT result(lhs); + result ^= rhs.bits(); + return result; +} + +template +inline bool operator==(angle::BitSetT &lhs, angle::BitSetT &rhs) +{ + return lhs.bits() == rhs.bits(); +} + +template +inline bool operator!=(angle::BitSetT &lhs, angle::BitSetT &rhs) +{ + return !(lhs == rhs); +} + +#endif // COMMON_BITSETITERATOR_H_ -- cgit v1.2.3