summaryrefslogtreecommitdiffstats
path: root/gnu/llvm/unittests/ADT/BitVectorTest.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gnu/llvm/unittests/ADT/BitVectorTest.cpp')
-rw-r--r--gnu/llvm/unittests/ADT/BitVectorTest.cpp411
1 files changed, 411 insertions, 0 deletions
diff --git a/gnu/llvm/unittests/ADT/BitVectorTest.cpp b/gnu/llvm/unittests/ADT/BitVectorTest.cpp
index 78fd5ce6567..d6a2075ca60 100644
--- a/gnu/llvm/unittests/ADT/BitVectorTest.cpp
+++ b/gnu/llvm/unittests/ADT/BitVectorTest.cpp
@@ -182,6 +182,229 @@ TYPED_TEST(BitVectorTest, TrivialOperation) {
EXPECT_TRUE(Vec.empty());
}
+TYPED_TEST(BitVectorTest, SimpleFindOps) {
+ // Test finding in an empty BitVector.
+ TypeParam A;
+ EXPECT_EQ(-1, A.find_first());
+ EXPECT_EQ(-1, A.find_last());
+ EXPECT_EQ(-1, A.find_first_unset());
+ EXPECT_EQ(-1, A.find_last_unset());
+
+ // Test finding next set and unset bits in a BitVector with multiple words
+ A.resize(100);
+ A.set(12);
+ A.set(13);
+ A.set(75);
+
+ EXPECT_EQ(75, A.find_last());
+ EXPECT_EQ(12, A.find_first());
+ EXPECT_EQ(13, A.find_next(12));
+ EXPECT_EQ(75, A.find_next(13));
+ EXPECT_EQ(-1, A.find_next(75));
+
+ EXPECT_EQ(-1, A.find_prev(12));
+ EXPECT_EQ(12, A.find_prev(13));
+ EXPECT_EQ(13, A.find_prev(75));
+ EXPECT_EQ(75, A.find_prev(90));
+
+ EXPECT_EQ(0, A.find_first_unset());
+ EXPECT_EQ(99, A.find_last_unset());
+ EXPECT_EQ(14, A.find_next_unset(11));
+ EXPECT_EQ(14, A.find_next_unset(12));
+ EXPECT_EQ(14, A.find_next_unset(13));
+ EXPECT_EQ(16, A.find_next_unset(15));
+ EXPECT_EQ(76, A.find_next_unset(74));
+ EXPECT_EQ(76, A.find_next_unset(75));
+ EXPECT_EQ(-1, A.find_next_unset(99));
+
+ A.set(0, 100);
+ EXPECT_EQ(100U, A.count());
+ EXPECT_EQ(0, A.find_first());
+ EXPECT_EQ(-1, A.find_first_unset());
+ EXPECT_EQ(-1, A.find_last_unset());
+ EXPECT_EQ(99, A.find_last());
+ EXPECT_EQ(99, A.find_next(98));
+
+ A.reset(0, 100);
+ EXPECT_EQ(0U, A.count());
+ EXPECT_EQ(-1, A.find_first());
+ EXPECT_EQ(-1, A.find_last());
+ EXPECT_EQ(0, A.find_first_unset());
+ EXPECT_EQ(99, A.find_last_unset());
+ EXPECT_EQ(99, A.find_next_unset(98));
+
+ // Also test with a vector that is small enough to fit in 1 word.
+ A.resize(20);
+ A.set(3);
+ A.set(4);
+ A.set(16);
+ EXPECT_EQ(16, A.find_last());
+ EXPECT_EQ(3, A.find_first());
+ EXPECT_EQ(3, A.find_next(1));
+ EXPECT_EQ(4, A.find_next(3));
+ EXPECT_EQ(16, A.find_next(4));
+ EXPECT_EQ(-1, A.find_next(16));
+
+ EXPECT_EQ(-1, A.find_prev(3));
+ EXPECT_EQ(3, A.find_prev(4));
+ EXPECT_EQ(4, A.find_prev(16));
+ EXPECT_EQ(16, A.find_prev(18));
+
+ EXPECT_EQ(0, A.find_first_unset());
+ EXPECT_EQ(19, A.find_last_unset());
+ EXPECT_EQ(5, A.find_next_unset(3));
+ EXPECT_EQ(5, A.find_next_unset(4));
+ EXPECT_EQ(13, A.find_next_unset(12));
+ EXPECT_EQ(17, A.find_next_unset(15));
+}
+
+TEST(BitVectorTest, FindInRangeMultiWord) {
+ BitVector Vec;
+
+ Vec.resize(200);
+ Vec.set(3, 7);
+ Vec.set(24, 35);
+ Vec.set(50, 70);
+ Vec.set(150);
+ Vec.set(152);
+ Vec.set(154);
+
+ // find first
+ EXPECT_EQ(-1, Vec.find_first_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_first_in(24, 24));
+ EXPECT_EQ(-1, Vec.find_first_in(7, 24));
+
+ EXPECT_EQ(3, Vec.find_first_in(0, 10));
+ EXPECT_EQ(4, Vec.find_first_in(4, 10));
+ EXPECT_EQ(150, Vec.find_first_in(100, 200));
+ EXPECT_EQ(152, Vec.find_first_in(151, 200));
+ EXPECT_EQ(154, Vec.find_first_in(153, 200));
+
+ EXPECT_EQ(-1, Vec.find_first_in(155, 200));
+ Vec.set(199);
+ EXPECT_EQ(199, Vec.find_first_in(199, 200));
+ Vec.reset(199);
+
+ // find last
+ EXPECT_EQ(-1, Vec.find_last_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_last_in(24, 24));
+ EXPECT_EQ(-1, Vec.find_last_in(7, 24));
+
+ EXPECT_EQ(6, Vec.find_last_in(0, 10));
+ EXPECT_EQ(5, Vec.find_last_in(0, 6));
+ EXPECT_EQ(154, Vec.find_last_in(100, 155));
+ EXPECT_EQ(152, Vec.find_last_in(100, 154));
+ EXPECT_EQ(150, Vec.find_last_in(100, 152));
+ EXPECT_EQ(-1, Vec.find_last_in(100, 150));
+ Vec.set(199);
+ EXPECT_EQ(199, Vec.find_last_in(199, 200));
+ Vec.reset(199);
+
+ // find first unset
+ EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
+ EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35));
+
+ EXPECT_EQ(0, Vec.find_first_unset_in(0, 10));
+ EXPECT_EQ(1, Vec.find_first_unset_in(1, 10));
+ EXPECT_EQ(7, Vec.find_first_unset_in(5, 25));
+ EXPECT_EQ(151, Vec.find_first_unset_in(150, 200));
+ EXPECT_EQ(151, Vec.find_first_unset_in(151, 200));
+ EXPECT_EQ(153, Vec.find_first_unset_in(152, 200));
+ EXPECT_EQ(153, Vec.find_first_unset_in(153, 200));
+ EXPECT_EQ(155, Vec.find_first_unset_in(154, 200));
+ EXPECT_EQ(155, Vec.find_first_unset_in(155, 200));
+ EXPECT_EQ(199, Vec.find_first_unset_in(199, 200));
+
+ // find last unset
+ EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
+ EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35));
+
+ EXPECT_EQ(9, Vec.find_last_unset_in(0, 10));
+ EXPECT_EQ(8, Vec.find_last_unset_in(0, 9));
+ EXPECT_EQ(2, Vec.find_last_unset_in(0, 7));
+ EXPECT_EQ(149, Vec.find_last_unset_in(100, 151));
+ EXPECT_EQ(151, Vec.find_last_unset_in(100, 152));
+ EXPECT_EQ(151, Vec.find_last_unset_in(100, 153));
+ EXPECT_EQ(153, Vec.find_last_unset_in(100, 154));
+ EXPECT_EQ(153, Vec.find_last_unset_in(100, 155));
+ EXPECT_EQ(155, Vec.find_last_unset_in(100, 156));
+ EXPECT_EQ(199, Vec.find_last_unset_in(199, 200));
+}
+
+TEST(BitVectorTest, FindInRangeSingleWord) {
+ // When the bit vector contains only a single word, this is slightly different
+ // than when the bit vector contains multiple words, because masks are applied
+ // to the front and back of the same word. So make sure this works.
+ BitVector Vec;
+
+ Vec.resize(25);
+ Vec.set(2, 4);
+ Vec.set(6, 9);
+ Vec.set(12, 15);
+ Vec.set(19);
+ Vec.set(21);
+ Vec.set(23);
+
+ // find first
+ EXPECT_EQ(-1, Vec.find_first_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_first_in(24, 24));
+ EXPECT_EQ(-1, Vec.find_first_in(9, 12));
+
+ EXPECT_EQ(2, Vec.find_first_in(0, 10));
+ EXPECT_EQ(6, Vec.find_first_in(4, 10));
+ EXPECT_EQ(19, Vec.find_first_in(18, 25));
+ EXPECT_EQ(21, Vec.find_first_in(20, 25));
+ EXPECT_EQ(23, Vec.find_first_in(22, 25));
+ EXPECT_EQ(-1, Vec.find_first_in(24, 25));
+
+ // find last
+ EXPECT_EQ(-1, Vec.find_last_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_last_in(24, 24));
+ EXPECT_EQ(-1, Vec.find_last_in(9, 12));
+
+ EXPECT_EQ(8, Vec.find_last_in(0, 10));
+ EXPECT_EQ(3, Vec.find_last_in(0, 6));
+ EXPECT_EQ(23, Vec.find_last_in(18, 25));
+ EXPECT_EQ(21, Vec.find_last_in(18, 23));
+ EXPECT_EQ(19, Vec.find_last_in(18, 21));
+ EXPECT_EQ(-1, Vec.find_last_in(18, 19));
+
+ // find first unset
+ EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
+ EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9));
+
+ EXPECT_EQ(0, Vec.find_first_unset_in(0, 6));
+ EXPECT_EQ(1, Vec.find_first_unset_in(1, 6));
+ EXPECT_EQ(9, Vec.find_first_unset_in(7, 13));
+ EXPECT_EQ(18, Vec.find_first_unset_in(18, 25));
+ EXPECT_EQ(20, Vec.find_first_unset_in(19, 25));
+ EXPECT_EQ(20, Vec.find_first_unset_in(20, 25));
+ EXPECT_EQ(22, Vec.find_first_unset_in(21, 25));
+ EXPECT_EQ(22, Vec.find_first_unset_in(22, 25));
+ EXPECT_EQ(24, Vec.find_first_unset_in(23, 25));
+ EXPECT_EQ(24, Vec.find_first_unset_in(24, 25));
+
+ // find last unset
+ EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
+ EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
+ EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9));
+
+ EXPECT_EQ(5, Vec.find_last_unset_in(0, 6));
+ EXPECT_EQ(4, Vec.find_last_unset_in(0, 5));
+ EXPECT_EQ(1, Vec.find_last_unset_in(0, 4));
+ EXPECT_EQ(11, Vec.find_last_unset_in(7, 13));
+ EXPECT_EQ(24, Vec.find_last_unset_in(18, 25));
+ EXPECT_EQ(22, Vec.find_last_unset_in(18, 24));
+ EXPECT_EQ(22, Vec.find_last_unset_in(18, 23));
+ EXPECT_EQ(20, Vec.find_last_unset_in(18, 22));
+ EXPECT_EQ(20, Vec.find_last_unset_in(18, 21));
+ EXPECT_EQ(18, Vec.find_last_unset_in(18, 20));
+ EXPECT_EQ(18, Vec.find_last_unset_in(18, 19));
+}
+
TYPED_TEST(BitVectorTest, CompoundAssignment) {
TypeParam A;
A.resize(10);
@@ -306,6 +529,128 @@ TYPED_TEST(BitVectorTest, BinOps) {
EXPECT_FALSE(B.anyCommon(A));
}
+typedef std::vector<std::pair<int, int>> RangeList;
+
+template <typename VecType>
+static inline VecType createBitVector(uint32_t Size,
+ const RangeList &setRanges) {
+ VecType V;
+ V.resize(Size);
+ for (auto &R : setRanges)
+ V.set(R.first, R.second);
+ return V;
+}
+
+TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) {
+ // Test that shift ops work when the desired shift amount is less
+ // than one word.
+
+ // 1. Case where the number of bits in the BitVector also fit into a single
+ // word.
+ TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}});
+ TypeParam B = A;
+
+ EXPECT_EQ(4U, A.count());
+ EXPECT_TRUE(A.test(2));
+ EXPECT_TRUE(A.test(3));
+ EXPECT_TRUE(A.test(8));
+ EXPECT_TRUE(A.test(9));
+
+ A >>= 1;
+ EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A);
+
+ A <<= 1;
+ EXPECT_EQ(B, A);
+
+ A >>= 10;
+ EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
+
+ A = B;
+ A <<= 10;
+ EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
+
+ // 2. Case where the number of bits in the BitVector do not fit into a single
+ // word.
+
+ // 31----------------------------------------------------------------------0
+ // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
+ A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}});
+ EXPECT_EQ(40U, A.size());
+ EXPECT_EQ(22U, A.count());
+
+ // 2a. Make sure that left shifting some 1 bits out of the vector works.
+ // 31----------------------------------------------------------------------0
+ // Before:
+ // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
+ // After:
+ // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
+ A <<= 9;
+ EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A);
+
+ // 2b. Make sure that keeping the number of one bits unchanged works.
+ // 31----------------------------------------------------------------------0
+ // Before:
+ // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
+ // After:
+ // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
+ A >>= 6;
+ EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A);
+
+ // 2c. Make sure that right shifting some 1 bits out of the vector works.
+ // 31----------------------------------------------------------------------0
+ // Before:
+ // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
+ // After:
+ // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111
+ A >>= 10;
+ EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A);
+
+ // 3. Big test.
+ A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
+ A <<= 29;
+ EXPECT_EQ(createBitVector<TypeParam>(
+ 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}),
+ A);
+}
+
+TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) {
+ // Test that shift ops work when the desired shift amount is greater than or
+ // equal to the size of a single word.
+ auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
+
+ // Make a copy so we can re-use it later.
+ auto B = A;
+
+ // 1. Shift left by an exact multiple of the word size. This should invoke
+ // only a memmove and no per-word bit operations.
+ A <<= 64;
+ auto Expected = createBitVector<TypeParam>(
+ 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}});
+ EXPECT_EQ(Expected, A);
+
+ // 2. Shift left by a non multiple of the word size. This should invoke both
+ // a memmove and per-word bit operations.
+ A = B;
+ A <<= 93;
+ EXPECT_EQ(createBitVector<TypeParam>(
+ 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}),
+ A);
+
+ // 1. Shift right by an exact multiple of the word size. This should invoke
+ // only a memmove and no per-word bit operations.
+ A = B;
+ A >>= 64;
+ EXPECT_EQ(
+ createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A);
+
+ // 2. Shift left by a non multiple of the word size. This should invoke both
+ // a memmove and per-word bit operations.
+ A = B;
+ A >>= 93;
+ EXPECT_EQ(
+ createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A);
+}
+
TYPED_TEST(BitVectorTest, RangeOps) {
TypeParam A;
A.resize(256);
@@ -425,5 +770,71 @@ TYPED_TEST(BitVectorTest, MoveAssignment) {
EXPECT_EQ(C, B);
}
+template<class TypeParam>
+static void testEmpty(const TypeParam &A) {
+ EXPECT_TRUE(A.empty());
+ EXPECT_EQ((size_t)0, A.size());
+ EXPECT_EQ((size_t)0, A.count());
+ EXPECT_FALSE(A.any());
+ EXPECT_TRUE(A.all());
+ EXPECT_TRUE(A.none());
+ EXPECT_EQ(-1, A.find_first());
+ EXPECT_EQ(A, TypeParam());
+}
+
+/// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0
+TYPED_TEST(BitVectorTest, EmptyVector) {
+ TypeParam A;
+ testEmpty(A);
+
+ TypeParam B;
+ B.reset();
+ testEmpty(B);
+
+ TypeParam C;
+ C.clear();
+ testEmpty(C);
+
+ TypeParam D(A);
+ testEmpty(D);
+
+ TypeParam E;
+ E = A;
+ testEmpty(E);
+
+ TypeParam F;
+ E.reset(A);
+ testEmpty(E);
+}
+
+TYPED_TEST(BitVectorTest, Iterators) {
+ TypeParam Filled(10, true);
+ EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end());
+ unsigned Counter = 0;
+ for (unsigned Bit : Filled.set_bits())
+ EXPECT_EQ(Bit, Counter++);
+
+ TypeParam Empty;
+ EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end());
+ for (unsigned Bit : Empty.set_bits()) {
+ (void)Bit;
+ EXPECT_TRUE(false);
+ }
+
+ TypeParam ToFill(100, false);
+ ToFill.set(0);
+ EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end());
+ EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end());
+ EXPECT_EQ(*ToFill.set_bits_begin(), 0U);
+ ToFill.reset(0);
+ EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end());
+
+ const unsigned List[] = {1, 10, 25, 99};
+ for (unsigned Num : List)
+ ToFill.set(Num);
+ unsigned i = 0;
+ for (unsigned Bit : ToFill.set_bits())
+ EXPECT_EQ(List[i++], Bit);
+}
}
#endif
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.