Author: Jan Patrick Lehr Date: 2026-05-05T14:51:00+02:00 New Revision: 94de08a3640a89144c2d9f071da0b5e778a3905d
URL: https://github.com/llvm/llvm-project/commit/94de08a3640a89144c2d9f071da0b5e778a3905d DIFF: https://github.com/llvm/llvm-project/commit/94de08a3640a89144c2d9f071da0b5e778a3905d.diff LOG: Revert "[ADT] Bitset: add shift operators, word accessors, and etc (#193400)" This reverts commit 462b60ba14f28b15422c0197c19a0e9fd65fb887. Added: Modified: llvm/include/llvm/ADT/Bitset.h llvm/unittests/ADT/BitsetTest.cpp Removed: ################################################################################ diff --git a/llvm/include/llvm/ADT/Bitset.h b/llvm/include/llvm/ADT/Bitset.h index 38e9684df9714..9dc0f24b1d9f5 100644 --- a/llvm/include/llvm/ADT/Bitset.h +++ b/llvm/include/llvm/ADT/Bitset.h @@ -18,7 +18,6 @@ #include "llvm/ADT/bit.h" #include <array> -#include <cassert> #include <climits> #include <cstdint> @@ -52,9 +51,8 @@ template <unsigned NumBits> class Bitset { constexpr void maskLastWord() { Bits[getLastWordIndex()] &= RemainderMask; } -public: - explicit constexpr Bitset( - const std::array<uint64_t, (NumBits + 63) / 64> &B) { +protected: + constexpr Bitset(const std::array<uint64_t, (NumBits + 63) / 64> &B) { if constexpr (sizeof(BitWord) == sizeof(uint64_t)) { for (size_t I = 0; I != B.size(); ++I) Bits[I] = B[I]; @@ -72,6 +70,8 @@ template <unsigned NumBits> class Bitset { } maskLastWord(); } + +public: constexpr Bitset() = default; constexpr Bitset(std::initializer_list<unsigned> Init) { for (auto I : Init) @@ -194,102 +194,6 @@ template <unsigned NumBits> class Bitset { } return false; } - - constexpr Bitset &operator<<=(unsigned N) { - if (N == 0) - return *this; - if (N >= NumBits) - return *this = Bitset(); - const unsigned WordShift = N / BitwordBits; - const unsigned BitShift = N % BitwordBits; - if (BitShift == 0) { - for (unsigned I = NumWords; I > WordShift;) { - --I; - Bits[I] = Bits[I - WordShift]; - } - } else { - const unsigned CarryShift = BitwordBits - BitShift; - for (unsigned I = NumWords - 1; I > WordShift; --I) { - Bits[I] = (Bits[I - WordShift] << BitShift) | - (Bits[I - WordShift - 1] >> CarryShift); - } - Bits[WordShift] = Bits[0] << BitShift; - } - for (unsigned I = 0; I < WordShift; ++I) - Bits[I] = 0; - maskLastWord(); - return *this; - } - - constexpr Bitset operator<<(unsigned N) const { - Bitset Result(*this); - Result <<= N; - return Result; - } - - constexpr Bitset &operator>>=(unsigned N) { - if (N == 0) - return *this; - if (N >= NumBits) - return *this = Bitset(); - const unsigned WordShift = N / BitwordBits; - const unsigned BitShift = N % BitwordBits; - if (BitShift == 0) { - for (unsigned I = 0; I < NumWords - WordShift; ++I) - Bits[I] = Bits[I + WordShift]; - } else { - const unsigned CarryShift = BitwordBits - BitShift; - for (unsigned I = 0; I < NumWords - WordShift - 1; ++I) { - Bits[I] = (Bits[I + WordShift] >> BitShift) | - (Bits[I + WordShift + 1] << CarryShift); - } - Bits[NumWords - WordShift - 1] = Bits[NumWords - 1] >> BitShift; - } - for (unsigned I = NumWords - WordShift; I < NumWords; ++I) - Bits[I] = 0; - maskLastWord(); - return *this; - } - - constexpr Bitset operator>>(unsigned N) const { - Bitset Result(*this); - Result >>= N; - return Result; - } - - /// Return the I-th 64-bit word of the bitset, from least significant to most. - /// - /// All words other than the last contain exactly 64 stored bits. The last - /// word (\p I == \c getNumWords64() - 1) may cover fewer than 64 stored bits - /// when \c NumBits is not a multiple of 64; in that case the unused high bits - /// are reported as 0. - constexpr uint64_t getWord64(unsigned I) const { - assert(I < getNumWords64() && "Word index out of range"); - if constexpr (BitwordBits == 64) { - return Bits[I]; - } else { - static_assert(BitwordBits == 32, "Unsupported word size"); - // When Bitword is 32-bit, for a valid I, the first word is always - // present, but the second may not be present. - uint64_t Lo = Bits[2 * I]; - uint64_t Hi = (2 * I + 1 < NumWords) ? Bits[2 * I + 1] : 0; - return Lo | (Hi << 32); - } - } - - /// Return the index of the highest set bit, or -1 if no bits are set. - constexpr int findLastSet() const { - for (unsigned I = NumWords; I > 0;) { - --I; - if (Bits[I] != 0) - return I * BitwordBits + - (BitwordBits - 1 - countl_zero_constexpr(Bits[I])); - } - return -1; - } - - /// Return the number of 64-bit words needed to hold all bits. - static constexpr unsigned getNumWords64() { return (NumBits + 63) / 64; } }; } // end namespace llvm diff --git a/llvm/unittests/ADT/BitsetTest.cpp b/llvm/unittests/ADT/BitsetTest.cpp index fc5f2bf8e844d..678197e31a379 100644 --- a/llvm/unittests/ADT/BitsetTest.cpp +++ b/llvm/unittests/ADT/BitsetTest.cpp @@ -14,52 +14,59 @@ using namespace llvm; namespace { template <unsigned NumBits> -bool verifyBitsetValue(const Bitset<NumBits> &Bits, - const std::array<uint64_t, (NumBits + 63) / 64> &Ref) { - for (unsigned I = 0; I != NumBits; ++I) { - bool ReferenceVal = - (Ref[I / 64] & (static_cast<uint64_t>(1) << (I % 64))) != 0; - if (ReferenceVal != Bits.test(I)) - return false; +class TestBitsetUInt64Array : public Bitset<NumBits> { + static constexpr unsigned NumElts = (NumBits + 63) / 64; + +public: + TestBitsetUInt64Array(const std::array<uint64_t, NumElts> &B) + : Bitset<NumBits>(B) {} + + bool verifyValue(const std::array<uint64_t, NumElts> &B) const { + for (unsigned I = 0; I != NumBits; ++I) { + bool ReferenceVal = + (B[(I / 64)] & (static_cast<uint64_t>(1) << (I % 64))) != 0; + if (ReferenceVal != this->test(I)) + return false; + } + + return true; } - return true; -} -template <unsigned NumBits> -void verifyBitsetStorageSize(size_t Elements64, size_t Elements32) { - if constexpr (sizeof(uintptr_t) == sizeof(uint64_t)) - EXPECT_EQ(sizeof(Bitset<NumBits>), Elements64 * sizeof(uintptr_t)); - else - EXPECT_EQ(sizeof(Bitset<NumBits>), Elements32 * sizeof(uintptr_t)); -} + void verifyStorageSize(size_t elements_64_bit, size_t elements_32_bit) { + if constexpr (sizeof(uintptr_t) == sizeof(uint64_t)) + EXPECT_EQ(sizeof(*this), elements_64_bit * sizeof(uintptr_t)); + else + EXPECT_EQ(sizeof(*this), elements_32_bit * sizeof(uintptr_t)); + } +}; TEST(BitsetTest, Construction) { std::array<uint64_t, 2> TestVals = {0x123456789abcdef3, 0x1337d3a0b22c24}; - Bitset<96> Test(TestVals); - EXPECT_TRUE(verifyBitsetValue(Test, TestVals)); - verifyBitsetStorageSize<96>(2, 3); + TestBitsetUInt64Array<96> Test(TestVals); + EXPECT_TRUE(Test.verifyValue(TestVals)); + Test.verifyStorageSize(2, 3); - Bitset<65> Test1(TestVals); - EXPECT_TRUE(verifyBitsetValue(Test1, TestVals)); - verifyBitsetStorageSize<65>(2, 3); + TestBitsetUInt64Array<65> Test1(TestVals); + EXPECT_TRUE(Test1.verifyValue(TestVals)); + Test1.verifyStorageSize(2, 3); std::array<uint64_t, 1> TestSingleVal = {0x12345678abcdef99}; - Bitset<64> Test64(TestSingleVal); - EXPECT_TRUE(verifyBitsetValue(Test64, TestSingleVal)); - verifyBitsetStorageSize<64>(1, 2); + TestBitsetUInt64Array<64> Test64(TestSingleVal); + EXPECT_TRUE(Test64.verifyValue(TestSingleVal)); + Test64.verifyStorageSize(1, 2); - Bitset<30> Test30(TestSingleVal); - EXPECT_TRUE(verifyBitsetValue(Test30, TestSingleVal)); - verifyBitsetStorageSize<30>(1, 1); + TestBitsetUInt64Array<30> Test30(TestSingleVal); + EXPECT_TRUE(Test30.verifyValue(TestSingleVal)); + Test30.verifyStorageSize(1, 1); - Bitset<32> Test32(TestSingleVal); - EXPECT_TRUE(verifyBitsetValue(Test32, TestSingleVal)); - verifyBitsetStorageSize<32>(1, 1); + TestBitsetUInt64Array<32> Test32(TestSingleVal); + EXPECT_TRUE(Test32.verifyValue(TestSingleVal)); + Test32.verifyStorageSize(1, 1); - Bitset<33> Test33(TestSingleVal); - EXPECT_TRUE(verifyBitsetValue(Test33, TestSingleVal)); - verifyBitsetStorageSize<33>(1, 2); + TestBitsetUInt64Array<33> Test33(TestSingleVal); + EXPECT_TRUE(Test33.verifyValue(TestSingleVal)); + Test33.verifyStorageSize(1, 2); } TEST(BitsetTest, SetAndQuery) { @@ -71,7 +78,7 @@ TEST(BitsetTest, SetAndQuery) { EXPECT_FALSE(A.none()); static_assert(Bitset<64>().set().all()); - EXPECT_TRUE(Bitset<33>().set().all()); + static_assert(Bitset<33>().set().all()); // Test set() with single bit. Bitset<64> B; @@ -82,11 +89,11 @@ TEST(BitsetTest, SetAndQuery) { EXPECT_FALSE(B.test(15)); static_assert(Bitset<64>().set(10).test(10)); - EXPECT_TRUE(Bitset<64>().set(0).set(63).test(0)); - EXPECT_TRUE(Bitset<64>().set(0).set(63).test(63)); - EXPECT_TRUE(Bitset<33>().set(32).test(32)); - EXPECT_TRUE(Bitset<128>().set(64).set(127).test(64)); - EXPECT_TRUE(Bitset<128>().set(64).set(127).test(127)); + static_assert(Bitset<64>().set(0).set(63).test(0) && + Bitset<64>().set(0).set(63).test(63)); + static_assert(Bitset<33>().set(32).test(32)); + static_assert(Bitset<128>().set(64).set(127).test(64) && + Bitset<128>().set(64).set(127).test(127)); // Test reset() with single bit. Bitset<64> C({10, 20, 30}); @@ -96,9 +103,9 @@ TEST(BitsetTest, SetAndQuery) { EXPECT_TRUE(C.test(30)); static_assert(!Bitset<64>({10, 20}).reset(10).test(10)); - EXPECT_TRUE(Bitset<64>({10, 20}).reset(10).test(20)); - EXPECT_FALSE(Bitset<96>({31, 32, 63}).reset(32).test(32)); - EXPECT_TRUE(Bitset<33>({0, 32}).reset(0).test(32)); + static_assert(Bitset<64>({10, 20}).reset(10).test(20)); + static_assert(!Bitset<96>({31, 32, 63}).reset(32).test(32)); + static_assert(Bitset<33>({0, 32}).reset(0).test(32)); // Test flip() with single bit. Bitset<64> D({10, 20}); @@ -109,10 +116,10 @@ TEST(BitsetTest, SetAndQuery) { EXPECT_TRUE(D.test(30)); static_assert(!Bitset<64>({10, 20}).flip(10).test(10)); - EXPECT_TRUE(Bitset<64>({10, 20}).flip(30).test(30)); - EXPECT_TRUE(Bitset<100>({50, 99}).flip(50).test(99)); - EXPECT_FALSE(Bitset<100>({50, 99}).flip(50).test(50)); - EXPECT_TRUE(Bitset<33>().flip(32).test(32)); + static_assert(Bitset<64>({10, 20}).flip(30).test(30)); + static_assert(Bitset<100>({50, 99}).flip(50).test(99) && + !Bitset<100>({50, 99}).flip(50).test(50)); + static_assert(Bitset<33>().flip(32).test(32)); // Test operator[]. Bitset<64> E({5, 15, 25}); @@ -121,10 +128,9 @@ TEST(BitsetTest, SetAndQuery) { EXPECT_TRUE(E[15]); static_assert(Bitset<64>({10, 20})[10]); - EXPECT_FALSE(Bitset<64>({10, 20})[15]); - EXPECT_TRUE(Bitset<128>({127})[127]); - EXPECT_TRUE(Bitset<96>({63, 64})[63]); - EXPECT_TRUE(Bitset<96>({63, 64})[64]); + static_assert(!Bitset<64>({10, 20})[15]); + static_assert(Bitset<128>({127})[127]); + static_assert(Bitset<96>({63, 64})[63] && Bitset<96>({63, 64})[64]); // Test size(). EXPECT_EQ(A.size(), 64u); @@ -132,14 +138,14 @@ TEST(BitsetTest, SetAndQuery) { EXPECT_EQ(F.size(), 33u); static_assert(Bitset<64>().size() == 64); - EXPECT_EQ(Bitset<128>().size(), 128u); - EXPECT_EQ(Bitset<33>().size(), 33u); + static_assert(Bitset<128>().size() == 128); + static_assert(Bitset<33>().size() == 33); // Test any() and none(). static_assert(!Bitset<64>().any()); - EXPECT_TRUE(Bitset<64>().none()); - EXPECT_TRUE(Bitset<64>({10}).any()); - EXPECT_FALSE(Bitset<64>({10}).none()); + static_assert(Bitset<64>().none()); + static_assert(Bitset<64>({10}).any()); + static_assert(!Bitset<64>({10}).none()); } TEST(BitsetTest, ComparisonOperators) { @@ -151,12 +157,12 @@ TEST(BitsetTest, ComparisonOperators) { EXPECT_FALSE(A == C); static_assert(Bitset<64>({10, 20}) == Bitset<64>({10, 20})); - EXPECT_TRUE(Bitset<64>({10, 20}) != Bitset<64>({10, 21})); + static_assert(Bitset<64>({10, 20}) != Bitset<64>({10, 21})); // Test operator< (lexicographic comparison, bit 0 is least significant). static_assert(Bitset<64>({5, 11}) < Bitset<64>({5, 10})); // At bit 10: A=0, B=1. - EXPECT_FALSE(Bitset<64>({5, 10}) < Bitset<64>({5, 10})); + static_assert(!(Bitset<64>({5, 10}) < Bitset<64>({5, 10}))); } TEST(BitsetTest, BitwiseNot) { @@ -167,8 +173,8 @@ TEST(BitsetTest, BitwiseNot) { EXPECT_TRUE(B.none()); static_assert((~Bitset<64>()).all()); - EXPECT_TRUE((~Bitset<64>().set()).none()); - EXPECT_TRUE((~Bitset<33>().set()).none()); + static_assert((~Bitset<64>().set()).none()); + static_assert((~Bitset<33>().set()).none()); } TEST(BitsetTest, BitwiseOperators) { @@ -183,11 +189,11 @@ TEST(BitsetTest, BitwiseOperators) { EXPECT_EQ(Result1.count(), 2u); static_assert((Bitset<64>({10, 20}) & Bitset<64>({20, 30})).test(20)); - EXPECT_FALSE((Bitset<64>({10, 20}) & Bitset<64>({20, 30})).test(10)); - EXPECT_EQ((Bitset<64>({10, 20}) & Bitset<64>({20, 30})).count(), 1u); - EXPECT_EQ((Bitset<96>({31, 32, 63, 64}) & Bitset<96>({32, 64, 95})).count(), - 2u); - EXPECT_TRUE((Bitset<33>({0, 32}) & Bitset<33>({32})).test(32)); + static_assert(!(Bitset<64>({10, 20}) & Bitset<64>({20, 30})).test(10)); + static_assert((Bitset<64>({10, 20}) & Bitset<64>({20, 30})).count() == 1); + static_assert( + (Bitset<96>({31, 32, 63, 64}) & Bitset<96>({32, 64, 95})).count() == 2); + static_assert((Bitset<33>({0, 32}) & Bitset<33>({32})).test(32)); // Test operator&=. Bitset<64> C({10, 20, 30}); @@ -197,17 +203,20 @@ TEST(BitsetTest, BitwiseOperators) { EXPECT_TRUE(C.test(30)); EXPECT_FALSE(C.test(40)); - static_assert([] { + constexpr Bitset<64> TestAnd = [] { Bitset<64> X({10, 20, 30}); X &= Bitset<64>({20, 30, 40}); - return X.test(20) && X.test(30) && !X.test(10); - }()); - - Bitset<100> TestAnd100({10, 50, 99}); - TestAnd100 &= Bitset<100>({50, 99}); - EXPECT_EQ(TestAnd100.count(), 2u); - EXPECT_TRUE(TestAnd100.test(50)); - EXPECT_TRUE(TestAnd100.test(99)); + return X; + }(); + static_assert(TestAnd.test(20) && TestAnd.test(30) && !TestAnd.test(10)); + + constexpr Bitset<100> TestAnd100 = [] { + Bitset<100> X({10, 50, 99}); + X &= Bitset<100>({50, 99}); + return X; + }(); + static_assert(TestAnd100.count() == 2 && TestAnd100.test(50) && + TestAnd100.test(99)); // Test operator|. Bitset<64> D({10, 20}); @@ -219,8 +228,9 @@ TEST(BitsetTest, BitwiseOperators) { EXPECT_EQ(Result2.count(), 3u); static_assert((Bitset<64>({10}) | Bitset<64>({20})).count() == 2); - EXPECT_EQ((Bitset<128>({0, 64, 127}) | Bitset<128>({64, 100})).count(), 4u); - EXPECT_EQ((Bitset<33>({0, 16}) | Bitset<33>({16, 32})).count(), 3u); + static_assert((Bitset<128>({0, 64, 127}) | Bitset<128>({64, 100})).count() == + 4); + static_assert((Bitset<33>({0, 16}) | Bitset<33>({16, 32})).count() == 3); // Test operator|=. Bitset<64> F({10, 20}); @@ -229,15 +239,19 @@ TEST(BitsetTest, BitwiseOperators) { EXPECT_TRUE(F.test(20)); EXPECT_TRUE(F.test(30)); - static_assert([] { + constexpr Bitset<64> TestOr = [] { Bitset<64> X({10}); X |= Bitset<64>({20}); - return X.test(10) && X.test(20); - }()); + return X; + }(); + static_assert(TestOr.test(10) && TestOr.test(20)); - Bitset<96> TestOr96({31, 63}); - TestOr96 |= Bitset<96>({32, 64}); - EXPECT_EQ(TestOr96.count(), 4u); + constexpr Bitset<96> TestOr96 = [] { + Bitset<96> X({31, 63}); + X |= Bitset<96>({32, 64}); + return X; + }(); + static_assert(TestOr96.count() == 4); // Test operator^. Bitset<64> G({10, 20, 30}); @@ -250,11 +264,11 @@ TEST(BitsetTest, BitwiseOperators) { EXPECT_EQ(Result3.count(), 2u); static_assert((Bitset<64>({10, 20}) ^ Bitset<64>({20, 30})).test(10)); - EXPECT_FALSE((Bitset<64>({10, 20}) ^ Bitset<64>({20, 30})).test(20)); - EXPECT_TRUE((Bitset<64>({10, 20}) ^ Bitset<64>({20, 30})).test(30)); - EXPECT_EQ((Bitset<64>({10, 20}) ^ Bitset<64>({20, 30})).count(), 2u); - EXPECT_EQ((Bitset<100>({0, 50, 99}) ^ Bitset<100>({50})).count(), 2u); - EXPECT_EQ((Bitset<33>({0, 32}) ^ Bitset<33>({0, 16})).count(), 2u); + static_assert(!(Bitset<64>({10, 20}) ^ Bitset<64>({20, 30})).test(20)); + static_assert((Bitset<64>({10, 20}) ^ Bitset<64>({20, 30})).test(30)); + static_assert((Bitset<64>({10, 20}) ^ Bitset<64>({20, 30})).count() == 2); + static_assert((Bitset<100>({0, 50, 99}) ^ Bitset<100>({50})).count() == 2); + static_assert((Bitset<33>({0, 32}) ^ Bitset<33>({0, 16})).count() == 2); // Test operator^=. Bitset<64> I({10, 20, 30}); @@ -264,236 +278,20 @@ TEST(BitsetTest, BitwiseOperators) { EXPECT_FALSE(I.test(30)); EXPECT_TRUE(I.test(40)); - static_assert([] { + constexpr Bitset<64> TestXor = [] { Bitset<64> X({10, 20}); X ^= Bitset<64>({20, 30}); - return X.test(10) && !X.test(20) && X.test(30); - }()); - - Bitset<128> TestXor128({0, 64, 127}); - TestXor128 ^= Bitset<128>({64}); - EXPECT_EQ(TestXor128.count(), 2u); - EXPECT_TRUE(TestXor128.test(0)); - EXPECT_TRUE(TestXor128.test(127)); -} - -TEST(BitsetTest, ShiftOperators) { - // Test left shift. - static_assert((Bitset<64>({0}) << 10).test(10)); - EXPECT_FALSE((Bitset<64>({0}) << 10).test(0)); - EXPECT_TRUE((Bitset<64>({63}) << 1).none()); - EXPECT_TRUE((Bitset<128>({0}) << 64).test(64)); - EXPECT_TRUE((Bitset<128>({63}) << 1).test(64)); - EXPECT_TRUE((Bitset<128>({127}) << 1).none()); - - // Test right shift. - static_assert((Bitset<64>({10}) >> 10).test(0)); - EXPECT_FALSE((Bitset<64>({10}) >> 10).test(10)); - EXPECT_TRUE((Bitset<64>({0}) >> 1).none()); - EXPECT_TRUE((Bitset<128>({64}) >> 64).test(0)); - EXPECT_TRUE((Bitset<128>({64}) >> 1).test(63)); - EXPECT_TRUE((Bitset<128>({0}) >> 1).none()); - - // Test shift by 0. - EXPECT_TRUE((Bitset<64>({10, 20}) << 0) == Bitset<64>({10, 20})); - EXPECT_TRUE((Bitset<64>({10, 20}) >> 0) == Bitset<64>({10, 20})); - - // Test shift by NumBits (clears all). - EXPECT_TRUE((Bitset<64>({0, 63}) << 64).none()); - EXPECT_TRUE((Bitset<64>({0, 63}) >> 64).none()); - EXPECT_TRUE((Bitset<128>({0, 127}) << 128).none()); - EXPECT_TRUE((Bitset<128>({0, 127}) >> 128).none()); -} - -TEST(BitsetTest, GetNumWords64) { - static_assert(Bitset<1>::getNumWords64() == 1); - EXPECT_EQ(Bitset<32>::getNumWords64(), 1u); - EXPECT_EQ(Bitset<64>::getNumWords64(), 1u); - EXPECT_EQ(Bitset<65>::getNumWords64(), 2u); - EXPECT_EQ(Bitset<96>::getNumWords64(), 2u); - EXPECT_EQ(Bitset<128>::getNumWords64(), 2u); - EXPECT_EQ(Bitset<129>::getNumWords64(), 3u); -} - -TEST(BitsetTest, GetWord64) { - // Single-word bitset. - constexpr auto B64 = Bitset<64>(std::array<uint64_t, 1>{0xdeadbeefcafe1234}); - static_assert(B64.getWord64(0) == 0xdeadbeefcafe1234); - - // Multi-word bitset. - Bitset<128> B128( - std::array<uint64_t, 2>{0x1111222233334444, 0xaaaabbbbccccdddd}); - EXPECT_EQ(B128.getWord64(0), 0x1111222233334444u); - EXPECT_EQ(B128.getWord64(1), uint64_t(0xaaaabbbbccccdddd)); - - // Partial last word - high bits should be masked off. - Bitset<96> B96( - std::array<uint64_t, 2>{0xffffffffffffffff, 0xffffffffffffffff}); - EXPECT_EQ(B96.getWord64(0), uint64_t(0xffffffffffffffff)); - // Only lower 32 bits. - EXPECT_EQ(B96.getWord64(1), uint64_t(0x00000000ffffffff)); - - // Empty bitset. - EXPECT_EQ(Bitset<64>().getWord64(0), 0u); - EXPECT_EQ(Bitset<128>().getWord64(0), 0u); - EXPECT_EQ(Bitset<128>().getWord64(1), 0u); -} - -TEST(BitsetTest, FindLastSet) { - // Empty bitset returns -1. - static_assert(Bitset<64>().findLastSet() == -1); - EXPECT_EQ(Bitset<128>().findLastSet(), -1); - - // Single bit set. - EXPECT_EQ(Bitset<64>({0}).findLastSet(), 0); - EXPECT_EQ(Bitset<64>({63}).findLastSet(), 63); - EXPECT_EQ(Bitset<64>({31}).findLastSet(), 31); - EXPECT_EQ(Bitset<128>({0}).findLastSet(), 0); - EXPECT_EQ(Bitset<128>({64}).findLastSet(), 64); - EXPECT_EQ(Bitset<128>({127}).findLastSet(), 127); - - // Multiple bits - returns highest. - EXPECT_EQ(Bitset<64>({0, 10, 50}).findLastSet(), 50); - EXPECT_EQ(Bitset<128>({0, 63, 64, 100}).findLastSet(), 100); - - // All bits set. - EXPECT_EQ(Bitset<64>().set().findLastSet(), 63); - EXPECT_EQ(Bitset<128>().set().findLastSet(), 127); - EXPECT_EQ(Bitset<96>().set().findLastSet(), 95); - - // Non-power-of-2 sizes. - EXPECT_EQ(Bitset<33>({32}).findLastSet(), 32); - EXPECT_EQ(Bitset<33>({0, 32}).findLastSet(), 32); - EXPECT_EQ(Bitset<65>({64}).findLastSet(), 64); -} - -TEST(BitsetTest, ShiftMultiWords) { - constexpr auto B192 = Bitset<192>({0, 64, 128}); - static_assert((B192 << 1) == Bitset<192>({1, 65, 129})); - EXPECT_TRUE((B192 >> 1) == Bitset<192>({63, 127})); - EXPECT_TRUE((B192 << 64) == Bitset<192>({64, 128})); - EXPECT_TRUE((B192 >> 64) == Bitset<192>({0, 64})); - EXPECT_TRUE((Bitset<192>({63, 127}) << 1) == Bitset<192>({64, 128})); - EXPECT_TRUE((Bitset<192>({64, 128}) >> 1) == Bitset<192>({63, 127})); -} - -TEST(BitsetTest, ShiftBoundaryBitShifts) { - static_assert((Bitset<128>({1}) << 63) == Bitset<128>({64})); - EXPECT_TRUE((Bitset<128>({64}) >> 63) == Bitset<128>({1})); - EXPECT_TRUE((Bitset<192>({1, 65}) << 63) == Bitset<192>({64, 128})); - // Shift by NumBits - 1. - EXPECT_TRUE((Bitset<64>({0}) << 63) == Bitset<64>({63})); - EXPECT_TRUE((Bitset<64>({63}) >> 63) == Bitset<64>({0})); - EXPECT_TRUE((Bitset<33>({0}) << 32) == Bitset<33>({32})); - // Full-width shift of a fully-set bitset loses exactly one bit, and the - // bit that is lost must be the boundary bit. - EXPECT_EQ((Bitset<128>().set() << 1).count(), 127u); - EXPECT_EQ((Bitset<128>().set() >> 1).count(), 127u); - EXPECT_EQ((Bitset<100>().set() >> 1).count(), 99u); - EXPECT_FALSE((Bitset<100>().set() >> 1).test(99)); - EXPECT_FALSE((Bitset<100>().set() << 1).test(0)); - EXPECT_FALSE((Bitset<128>().set() >> 1).test(127)); - EXPECT_FALSE((Bitset<128>().set() << 1).test(0)); -} - -TEST(BitsetTest, ShiftExcessAmount) { - static_assert((Bitset<64>().set() << 65).none()); - EXPECT_TRUE((Bitset<64>().set() >> 200).none()); - EXPECT_TRUE((Bitset<33>({0, 10, 32}) << 1000).none()); - EXPECT_TRUE((Bitset<128>({0, 127}) >> 1000).none()); - EXPECT_TRUE((Bitset<192>().set() << 193).none()); -} - -TEST(BitsetTest, ShiftDoesNotMutateOperand) { - // Non-mutating operator<< / operator>> must leave the source unchanged. - Bitset<128> X({5, 70}); - Bitset<128> YL = X << 1; - EXPECT_TRUE(YL == Bitset<128>({6, 71})); - EXPECT_TRUE(X == Bitset<128>({5, 70})); - - Bitset<128> YR = X >> 1; - EXPECT_TRUE(YR == Bitset<128>({4, 69})); - EXPECT_TRUE(X == Bitset<128>({5, 70})); - - static_assert([] { - Bitset<128> X({5, 70}); - Bitset<128> Y = X << 1; - return Y == Bitset<128>({6, 71}) && X == Bitset<128>({5, 70}); - }()); -} - -TEST(BitsetTest, ShiftAssignReturnsReference) { - static_assert([] { - Bitset<64> X({0}); - (X <<= 3) <<= 2; - return X == Bitset<64>({5}); - }()); - - Bitset<128> R({100}); - (R >>= 30) >>= 10; - EXPECT_TRUE(R == Bitset<128>({60})); -} - -TEST(BitsetTest, GetWord64ConsistencyWithTest) { - // For every set bit, getWord64 must report it in the expected 64-bit word. - constexpr auto B100 = Bitset<100>({0, 50, 64, 99}); - static_assert((B100.getWord64(0) & 1) != 0); - EXPECT_NE(B100.getWord64(0) & (uint64_t(1) << 50), 0u); - EXPECT_NE(B100.getWord64(1) & 1, 0u); - EXPECT_NE(B100.getWord64(1) & (uint64_t(1) << 35), 0u); -} - -TEST(BitsetTest, GetWord64AfterMutation) { - // getWord64() reflects subsequent set / shift. - static_assert([] { - Bitset<128> X; - X.set(5).set(70); - return X.getWord64(0) == (uint64_t(1) << 5) && - X.getWord64(1) == (uint64_t(1) << 6); - }()); - - Bitset<128> Shifted = Bitset<128>({5}) << 64; - EXPECT_EQ(Shifted.getWord64(0), 0u); - EXPECT_EQ(Shifted.getWord64(1), uint64_t(1) << 5); -} - -TEST(BitsetTest, GetNumWords64MoreWidths) { - static_assert(Bitset<2>::getNumWords64() == 1); - EXPECT_EQ(Bitset<192>::getNumWords64(), 3u); - EXPECT_EQ(Bitset<193>::getNumWords64(), 4u); - EXPECT_EQ(Bitset<256>::getNumWords64(), 4u); -} - -TEST(BitsetTest, FindLastSetSmallWidths) { - static_assert(Bitset<1>().findLastSet() == -1); - EXPECT_EQ(Bitset<1>({0}).findLastSet(), 0); - EXPECT_EQ(Bitset<2>({0, 1}).findLastSet(), 1); - EXPECT_EQ(Bitset<32>({31}).findLastSet(), 31); - EXPECT_EQ(Bitset<32>().set().findLastSet(), 31); -} - -TEST(BitsetTest, FindLastSetMultiWordScan) { - static_assert(Bitset<192>({70}).findLastSet() == 70); - EXPECT_EQ(Bitset<192>({64, 70, 127}).findLastSet(), 127); - EXPECT_EQ(Bitset<192>({3}).findLastSet(), 3); - EXPECT_EQ(Bitset<100>({99}).findLastSet(), 99); - // Highest set bit lives in the lowest word; the loop must scan past - // multiple empty trailing words. - EXPECT_EQ(Bitset<192>({0}).findLastSet(), 0); - EXPECT_EQ(Bitset<256>({1}).findLastSet(), 1); -} - -TEST(BitsetTest, FindLastSetAfterMutation) { - static_assert(Bitset<128>({0, 50, 100}).reset(100).findLastSet() == 50); - - Bitset<64> B = Bitset<64>({10}) << 20; - EXPECT_EQ(B.findLastSet(), 30); - - Bitset<64> C = Bitset<64>({63}) >> 10; - EXPECT_EQ(C.findLastSet(), 53); - - Bitset<64> D = Bitset<64>({63}) << 1; - EXPECT_EQ(D.findLastSet(), -1); + return X; + }(); + static_assert(TestXor.test(10) && !TestXor.test(20) && TestXor.test(30)); + + constexpr Bitset<128> TestXor128 = [] { + Bitset<128> X({0, 64, 127}); + X ^= Bitset<128>({64}); + return X; + }(); + static_assert(TestXor128.count() == 2 && TestXor128.test(0) && + TestXor128.test(127)); } } // namespace _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
