1 //===- llvm/unittest/ADT/SparseBitVectorTest.cpp - SparseBitVector tests --===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/ADT/SparseBitVector.h" 10 #include "gtest/gtest.h" 11 12 using namespace llvm; 13 14 namespace { 15 16 TEST(SparseBitVectorTest, TrivialOperation) { 17 SparseBitVector<> Vec; 18 EXPECT_EQ(0U, Vec.count()); 19 EXPECT_FALSE(Vec.test(17)); 20 Vec.set(5); 21 EXPECT_TRUE(Vec.test(5)); 22 EXPECT_FALSE(Vec.test(17)); 23 Vec.reset(6); 24 EXPECT_TRUE(Vec.test(5)); 25 EXPECT_FALSE(Vec.test(6)); 26 Vec.reset(5); 27 EXPECT_FALSE(Vec.test(5)); 28 EXPECT_TRUE(Vec.test_and_set(17)); 29 EXPECT_FALSE(Vec.test_and_set(17)); 30 EXPECT_TRUE(Vec.test(17)); 31 Vec.clear(); 32 EXPECT_FALSE(Vec.test(17)); 33 34 Vec.set(5); 35 const SparseBitVector<> ConstVec = Vec; 36 EXPECT_TRUE(ConstVec.test(5)); 37 EXPECT_FALSE(ConstVec.test(17)); 38 39 Vec.set(1337); 40 EXPECT_TRUE(Vec.test(1337)); 41 Vec = ConstVec; 42 EXPECT_FALSE(Vec.test(1337)); 43 44 Vec.set(1337); 45 EXPECT_FALSE(Vec.empty()); 46 SparseBitVector<> MovedVec(std::move(Vec)); 47 EXPECT_TRUE(Vec.empty()); 48 EXPECT_TRUE(MovedVec.test(5)); 49 EXPECT_TRUE(MovedVec.test(1337)); 50 51 Vec = std::move(MovedVec); 52 EXPECT_TRUE(MovedVec.empty()); 53 EXPECT_FALSE(Vec.empty()); 54 } 55 56 TEST(SparseBitVectorTest, IntersectWith) { 57 SparseBitVector<> Vec, Other; 58 59 Vec.set(1); 60 Other.set(1); 61 EXPECT_FALSE(Vec &= Other); 62 EXPECT_TRUE(Vec.test(1)); 63 64 Vec.clear(); 65 Vec.set(5); 66 Other.clear(); 67 Other.set(6); 68 EXPECT_TRUE(Vec &= Other); 69 EXPECT_TRUE(Vec.empty()); 70 71 Vec.clear(); 72 Vec.set(5); 73 Other.clear(); 74 Other.set(225); 75 EXPECT_TRUE(Vec &= Other); 76 EXPECT_TRUE(Vec.empty()); 77 78 Vec.clear(); 79 Vec.set(225); 80 Other.clear(); 81 Other.set(5); 82 EXPECT_TRUE(Vec &= Other); 83 EXPECT_TRUE(Vec.empty()); 84 } 85 86 TEST(SparseBitVectorTest, SelfAssignment) { 87 SparseBitVector<> Vec, Other; 88 89 Vec.set(23); 90 Vec.set(234); 91 Vec = static_cast<SparseBitVector<> &>(Vec); 92 EXPECT_TRUE(Vec.test(23)); 93 EXPECT_TRUE(Vec.test(234)); 94 95 Vec.clear(); 96 Vec.set(17); 97 Vec.set(256); 98 EXPECT_FALSE(Vec |= Vec); 99 EXPECT_TRUE(Vec.test(17)); 100 EXPECT_TRUE(Vec.test(256)); 101 102 Vec.clear(); 103 Vec.set(56); 104 Vec.set(517); 105 EXPECT_FALSE(Vec &= Vec); 106 EXPECT_TRUE(Vec.test(56)); 107 EXPECT_TRUE(Vec.test(517)); 108 109 Vec.clear(); 110 Vec.set(99); 111 Vec.set(333); 112 EXPECT_TRUE(Vec.intersectWithComplement(Vec)); 113 EXPECT_TRUE(Vec.empty()); 114 EXPECT_FALSE(Vec.intersectWithComplement(Vec)); 115 116 Vec.clear(); 117 Vec.set(28); 118 Vec.set(43); 119 Vec.intersectWithComplement(Vec, Vec); 120 EXPECT_TRUE(Vec.empty()); 121 122 Vec.clear(); 123 Vec.set(42); 124 Vec.set(567); 125 Other.set(55); 126 Other.set(567); 127 Vec.intersectWithComplement(Vec, Other); 128 EXPECT_TRUE(Vec.test(42)); 129 EXPECT_FALSE(Vec.test(567)); 130 131 Vec.clear(); 132 Vec.set(19); 133 Vec.set(21); 134 Other.clear(); 135 Other.set(19); 136 Other.set(31); 137 Vec.intersectWithComplement(Other, Vec); 138 EXPECT_FALSE(Vec.test(19)); 139 EXPECT_TRUE(Vec.test(31)); 140 141 Vec.clear(); 142 Vec.set(1); 143 Other.clear(); 144 Other.set(59); 145 Other.set(75); 146 Vec.intersectWithComplement(Other, Other); 147 EXPECT_TRUE(Vec.empty()); 148 } 149 150 TEST(SparseBitVectorTest, Find) { 151 SparseBitVector<> Vec; 152 Vec.set(1); 153 EXPECT_EQ(1, Vec.find_first()); 154 EXPECT_EQ(1, Vec.find_last()); 155 156 Vec.set(2); 157 EXPECT_EQ(1, Vec.find_first()); 158 EXPECT_EQ(2, Vec.find_last()); 159 160 Vec.set(0); 161 Vec.set(3); 162 EXPECT_EQ(0, Vec.find_first()); 163 EXPECT_EQ(3, Vec.find_last()); 164 165 Vec.reset(1); 166 Vec.reset(0); 167 Vec.reset(3); 168 EXPECT_EQ(2, Vec.find_first()); 169 EXPECT_EQ(2, Vec.find_last()); 170 171 // Set some large bits to ensure we are pulling bits from more than just a 172 // single bitword. 173 Vec.set(500); 174 Vec.set(2000); 175 Vec.set(3000); 176 Vec.set(4000); 177 Vec.reset(2); 178 EXPECT_EQ(500, Vec.find_first()); 179 EXPECT_EQ(4000, Vec.find_last()); 180 181 Vec.reset(500); 182 Vec.reset(3000); 183 Vec.reset(4000); 184 EXPECT_EQ(2000, Vec.find_first()); 185 EXPECT_EQ(2000, Vec.find_last()); 186 187 Vec.clear(); 188 } 189 } 190