diff --git a/libc/src/__support/CPP/bitset.h b/libc/src/__support/CPP/bitset.h --- a/libc/src/__support/CPP/bitset.h +++ b/libc/src/__support/CPP/bitset.h @@ -21,18 +21,67 @@ Data[Index / BITS_PER_UNIT] |= mask(Index); } + constexpr void reset() { + for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) + Data[i] = 0; + } + constexpr bool test(size_t Index) const { return Data[Index / BITS_PER_UNIT] & mask(Index); } + constexpr void flip() { + for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) + Data[i] = ~Data[i]; + } + + // This function sets all bits in the range from Start to End (inclusive) to + // true. It assumes that Start <= End. + constexpr void set_range(size_t Start, size_t End) { + size_t start_index = Start / BITS_PER_UNIT; + size_t end_index = End / BITS_PER_UNIT; + + if (start_index == end_index) { + // The reason the left shift is split into two parts (instead of just left + // shifting by End - Start + 1) is because when a number is shifted left + // by 64 then it wraps around to doing nothing, but shifting by 63 and the + // shifting by 1 correctly shifts away all of the bits. + size_t bit_mask = (((size_t(1) << (End - Start)) << 1) - 1) + << (Start - (start_index * BITS_PER_UNIT)); + Data[start_index] |= bit_mask; + } else { + size_t low_bit_mask = + ~((size_t(1) << (Start - (start_index * BITS_PER_UNIT))) - 1); + Data[start_index] |= low_bit_mask; + + for (size_t i = start_index + 1; i < end_index; ++i) + Data[i] = ~size_t(0); + + // Same as above, by splitting the shift the behavior is more consistent. + size_t high_bit_mask = + ((size_t(1) << (End - (end_index * BITS_PER_UNIT))) << 1) - 1; + Data[end_index] |= high_bit_mask; + } + } + + constexpr bool operator==(const bitset &other) { + for (size_t i = 0; i < NUMBER_OF_UNITS; ++i) { + if (Data[i] != other.Data[i]) + return false; + } + return true; + } + private: static constexpr size_t BITS_PER_BYTE = 8; static constexpr size_t BITS_PER_UNIT = BITS_PER_BYTE * sizeof(size_t); + static constexpr size_t NUMBER_OF_UNITS = + (NumberOfBits + BITS_PER_UNIT - 1) / BITS_PER_UNIT; static inline size_t mask(size_t Index) { return size_t{1} << (Index % BITS_PER_UNIT); } - size_t Data[(NumberOfBits + BITS_PER_UNIT - 1) / BITS_PER_UNIT] = {0}; + size_t Data[NUMBER_OF_UNITS] = {0}; }; } // namespace __llvm_libc::cpp diff --git a/libc/test/src/__support/CPP/bitset_test.cpp b/libc/test/src/__support/CPP/bitset_test.cpp --- a/libc/test/src/__support/CPP/bitset_test.cpp +++ b/libc/test/src/__support/CPP/bitset_test.cpp @@ -100,3 +100,124 @@ for (size_t j = 0; j < 128; ++j) EXPECT_TRUE(bitset.test(j)); } + +TEST(LlvmLibcBitsetTest, FlipTest) { + __llvm_libc::cpp::bitset<128> bitset; + + bitset.flip(); + + // Verify all bits are now set. + for (size_t j = 0; j < 128; ++j) + EXPECT_TRUE(bitset.test(j)); + + bitset.flip(); + + // Verify all bits are now unset. + for (size_t j = 0; j < 128; ++j) + EXPECT_FALSE(bitset.test(j)); + + // Set the even bits + for (size_t j = 0; j < 64; ++j) + bitset.set(j * 2); + + // Verify + for (size_t j = 0; j < 128; ++j) + EXPECT_EQ(bitset.test(j), (j % 2) == 0); + + bitset.flip(); + + // Check that the odd set of bits is now true. + for (size_t j = 0; j < 128; ++j) + EXPECT_EQ(bitset.test(j), j % 2 != 0); + + // Set the first half of the bits. + for (size_t j = 0; j < 64; ++j) + bitset.set(j); + + // The pattern should now be 111...1110101...010 + + // Flip to get 000...0001010...101 + bitset.flip(); + + // Verify that the first half of bits are false and the even bits in the + // second half are true. + for (size_t j = 0; j < 128; ++j) + EXPECT_EQ(bitset.test(j), (j > 63) && (j % 2 == 0)); +} + +TEST(LlvmLibcBitsetTest, EqualTest) { + __llvm_libc::cpp::bitset<128> bitset_a; + __llvm_libc::cpp::bitset<128> bitset_b; + + // New sets should be empty, and so they should be equal. + ASSERT_TRUE(bitset_a == bitset_b); + + bitset_a.set(0); + + // Setting one bit should be enough. + ASSERT_FALSE(bitset_a == bitset_b); + + bitset_b.set(64); + + // Setting the same bit on a different unit shouldn't be equal. + ASSERT_FALSE(bitset_a == bitset_b); + + bitset_b.set(0); + + // The first unit matching shouldn't be equal. + ASSERT_FALSE(bitset_a == bitset_b); + + bitset_a.set(64); + + // Now they should be equal. + ASSERT_TRUE(bitset_a == bitset_b); +} + +TEST(LlvmLibcBitsetTest, SetRangeTest) { + __llvm_libc::cpp::bitset<256> bitset; + + // Range from 1 to 1 should only set bit 1 + bitset.set_range(1, 1); + + for (size_t j = 0; j < 256; ++j) + EXPECT_EQ(bitset.test(j), j == 1); + + // reset all bits back to 0. + bitset.reset(); + + // Range from 2 to 5 should set bits 2-5 + bitset.set_range(2, 5); + for (size_t j = 0; j < 256; ++j) + EXPECT_EQ(bitset.test(j), (j >= 2 && j <= 5)); + bitset.reset(); + + // Check setting exactly one unit + bitset.set_range(0, 63); + for (size_t j = 0; j < 256; ++j) + EXPECT_EQ(bitset.test(j), (j >= 0 && j <= 63)); + bitset.reset(); + + // Check ranges across unit boundaries work. + bitset.set_range(1, 64); + for (size_t j = 0; j < 256; ++j) + EXPECT_EQ(bitset.test(j), (j >= 1 && j <= 64)); + bitset.reset(); + + // Same, but closer together. + bitset.set_range(63, 64); + for (size_t j = 0; j < 256; ++j) + EXPECT_EQ(bitset.test(j), (j >= 63 && j <= 64)); + bitset.reset(); + + // Check that ranges with a unit in the middle work. + bitset.set_range(63, 129); + for (size_t j = 0; j < 256; ++j) + EXPECT_EQ(bitset.test(j), (j >= 63 && j <= 129)); + bitset.reset(); + + // Check that the whole range being set works. + bitset.set_range(0, 255); + for (size_t j = 0; j < 256; ++j) + EXPECT_TRUE(bitset.test(j)); + bitset.reset(); +}