[libc] add features to bitset

[michaelrj]

Summary

This patch adds the flip, set_range, and operator== functions to bitset.
These will be used in scanf.

[sivachandra]

Please add unit-tests for the new methods.

libc/src/__support/CPP/bitset.h

40

This method is not in std::bitset so we should not include it here. You can define a helper function in the other patch with the same functionality.

[michaelrj]

libc/src/__support/CPP/bitset.h

40

defining this function outside of the bitset class is less efficient because the internal Data array is private. I could implement it as a loop of calls to set but that would be masking one bit at a time.

[sivachandra]

libc/src/__support/CPP/bitset.h

40

Sigh, OK! Nevermind then.

[michaelrj]

add unit tests and a "reset" function to support those tests. Also squash some bugs found with the tests.

libc/src/__support/CPP/bitset.h

 template <size_t NumberOfBits> struct bitset {
   static_assert(NumberOfBits != 0,
                 "Cannot create a __llvm_libc::cpp::bitset of size 0.");
 
   constexpr void set(size_t Index) {
     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<NumberOfBits> &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
 
 #endif // LLVM_LIBC_SRC_SUPPORT_CPP_BITSET_H

libc/test/src/__support/CPP/bitset_test.cpp

TEST(LlvmLibcBitsetTest, SettingBitXDoesNotResetBitY) {
   __llvm_libc::cpp::bitset<128> bitset;
   for (size_t i = 0; i < 128; ++i)
     bitset.set(i);
 
   // Verify all bits are now set.
   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();
+}