1 //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 // Some of these tests fail on PowerPC for unknown reasons. 11 #ifndef __ppc__ 12 13 #include "llvm/ADT/BitVector.h" 14 #include "llvm/ADT/SmallBitVector.h" 15 #include "gtest/gtest.h" 16 17 using namespace llvm; 18 19 namespace { 20 21 // Test fixture 22 template <typename T> 23 class BitVectorTest : public ::testing::Test { }; 24 25 // Test both BitVector and SmallBitVector with the same suite of tests. 26 typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes; 27 TYPED_TEST_CASE(BitVectorTest, BitVectorTestTypes); 28 29 TYPED_TEST(BitVectorTest, TrivialOperation) { 30 TypeParam Vec; 31 EXPECT_EQ(0U, Vec.count()); 32 EXPECT_EQ(0U, Vec.size()); 33 EXPECT_FALSE(Vec.any()); 34 EXPECT_TRUE(Vec.all()); 35 EXPECT_TRUE(Vec.none()); 36 EXPECT_TRUE(Vec.empty()); 37 38 Vec.resize(5, true); 39 EXPECT_EQ(5U, Vec.count()); 40 EXPECT_EQ(5U, Vec.size()); 41 EXPECT_TRUE(Vec.any()); 42 EXPECT_TRUE(Vec.all()); 43 EXPECT_FALSE(Vec.none()); 44 EXPECT_FALSE(Vec.empty()); 45 46 Vec.resize(11); 47 EXPECT_EQ(5U, Vec.count()); 48 EXPECT_EQ(11U, Vec.size()); 49 EXPECT_TRUE(Vec.any()); 50 EXPECT_FALSE(Vec.all()); 51 EXPECT_FALSE(Vec.none()); 52 EXPECT_FALSE(Vec.empty()); 53 54 TypeParam Inv = Vec; 55 Inv.flip(); 56 EXPECT_EQ(6U, Inv.count()); 57 EXPECT_EQ(11U, Inv.size()); 58 EXPECT_TRUE(Inv.any()); 59 EXPECT_FALSE(Inv.all()); 60 EXPECT_FALSE(Inv.none()); 61 EXPECT_FALSE(Inv.empty()); 62 63 EXPECT_FALSE(Inv == Vec); 64 EXPECT_TRUE(Inv != Vec); 65 Vec.flip(); 66 EXPECT_TRUE(Inv == Vec); 67 EXPECT_FALSE(Inv != Vec); 68 69 // Add some "interesting" data to Vec. 70 Vec.resize(23, true); 71 Vec.resize(25, false); 72 Vec.resize(26, true); 73 Vec.resize(29, false); 74 Vec.resize(33, true); 75 Vec.resize(57, false); 76 unsigned Count = 0; 77 for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { 78 ++Count; 79 EXPECT_TRUE(Vec[i]); 80 EXPECT_TRUE(Vec.test(i)); 81 } 82 EXPECT_EQ(Count, Vec.count()); 83 EXPECT_EQ(Count, 23u); 84 EXPECT_FALSE(Vec[0]); 85 EXPECT_TRUE(Vec[32]); 86 EXPECT_FALSE(Vec[56]); 87 Vec.resize(61, false); 88 89 TypeParam Copy = Vec; 90 TypeParam Alt(3, false); 91 Alt.resize(6, true); 92 std::swap(Alt, Vec); 93 EXPECT_TRUE(Copy == Alt); 94 EXPECT_TRUE(Vec.size() == 6); 95 EXPECT_TRUE(Vec.count() == 3); 96 EXPECT_TRUE(Vec.find_first() == 3); 97 std::swap(Copy, Vec); 98 99 // Add some more "interesting" data. 100 Vec.resize(68, true); 101 Vec.resize(78, false); 102 Vec.resize(89, true); 103 Vec.resize(90, false); 104 Vec.resize(91, true); 105 Vec.resize(130, false); 106 Count = 0; 107 for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { 108 ++Count; 109 EXPECT_TRUE(Vec[i]); 110 EXPECT_TRUE(Vec.test(i)); 111 } 112 EXPECT_EQ(Count, Vec.count()); 113 EXPECT_EQ(Count, 42u); 114 EXPECT_FALSE(Vec[0]); 115 EXPECT_TRUE(Vec[32]); 116 EXPECT_FALSE(Vec[60]); 117 EXPECT_FALSE(Vec[129]); 118 119 Vec.flip(60); 120 EXPECT_TRUE(Vec[60]); 121 EXPECT_EQ(Count + 1, Vec.count()); 122 Vec.flip(60); 123 EXPECT_FALSE(Vec[60]); 124 EXPECT_EQ(Count, Vec.count()); 125 126 Vec.reset(32); 127 EXPECT_FALSE(Vec[32]); 128 EXPECT_EQ(Count - 1, Vec.count()); 129 Vec.set(32); 130 EXPECT_TRUE(Vec[32]); 131 EXPECT_EQ(Count, Vec.count()); 132 133 Vec.flip(); 134 EXPECT_EQ(Vec.size() - Count, Vec.count()); 135 136 Vec.reset(); 137 EXPECT_EQ(0U, Vec.count()); 138 EXPECT_EQ(130U, Vec.size()); 139 EXPECT_FALSE(Vec.any()); 140 EXPECT_FALSE(Vec.all()); 141 EXPECT_TRUE(Vec.none()); 142 EXPECT_FALSE(Vec.empty()); 143 144 Vec.flip(); 145 EXPECT_EQ(130U, Vec.count()); 146 EXPECT_EQ(130U, Vec.size()); 147 EXPECT_TRUE(Vec.any()); 148 EXPECT_TRUE(Vec.all()); 149 EXPECT_FALSE(Vec.none()); 150 EXPECT_FALSE(Vec.empty()); 151 152 Inv = TypeParam().flip(); 153 EXPECT_EQ(0U, Inv.count()); 154 EXPECT_EQ(0U, Inv.size()); 155 EXPECT_FALSE(Inv.any()); 156 EXPECT_TRUE(Inv.all()); 157 EXPECT_TRUE(Inv.none()); 158 EXPECT_TRUE(Inv.empty()); 159 160 Vec.clear(); 161 EXPECT_EQ(0U, Vec.count()); 162 EXPECT_EQ(0U, Vec.size()); 163 EXPECT_FALSE(Vec.any()); 164 EXPECT_TRUE(Vec.all()); 165 EXPECT_TRUE(Vec.none()); 166 EXPECT_TRUE(Vec.empty()); 167 } 168 169 TYPED_TEST(BitVectorTest, CompoundAssignment) { 170 TypeParam A; 171 A.resize(10); 172 A.set(4); 173 A.set(7); 174 175 TypeParam B; 176 B.resize(50); 177 B.set(5); 178 B.set(18); 179 180 A |= B; 181 EXPECT_TRUE(A.test(4)); 182 EXPECT_TRUE(A.test(5)); 183 EXPECT_TRUE(A.test(7)); 184 EXPECT_TRUE(A.test(18)); 185 EXPECT_EQ(4U, A.count()); 186 EXPECT_EQ(50U, A.size()); 187 188 B.resize(10); 189 B.set(); 190 B.reset(2); 191 B.reset(7); 192 A &= B; 193 EXPECT_FALSE(A.test(2)); 194 EXPECT_FALSE(A.test(7)); 195 EXPECT_EQ(2U, A.count()); 196 EXPECT_EQ(50U, A.size()); 197 198 B.resize(100); 199 B.set(); 200 201 A ^= B; 202 EXPECT_TRUE(A.test(2)); 203 EXPECT_TRUE(A.test(7)); 204 EXPECT_EQ(98U, A.count()); 205 EXPECT_EQ(100U, A.size()); 206 } 207 208 TYPED_TEST(BitVectorTest, ProxyIndex) { 209 TypeParam Vec(3); 210 EXPECT_TRUE(Vec.none()); 211 Vec[0] = Vec[1] = Vec[2] = true; 212 EXPECT_EQ(Vec.size(), Vec.count()); 213 Vec[2] = Vec[1] = Vec[0] = false; 214 EXPECT_TRUE(Vec.none()); 215 } 216 217 TYPED_TEST(BitVectorTest, PortableBitMask) { 218 TypeParam A; 219 const uint32_t Mask1[] = { 0x80000000, 6, 5 }; 220 221 A.resize(10); 222 A.setBitsInMask(Mask1, 3); 223 EXPECT_EQ(10u, A.size()); 224 EXPECT_FALSE(A.test(0)); 225 226 A.resize(32); 227 A.setBitsInMask(Mask1, 3); 228 EXPECT_FALSE(A.test(0)); 229 EXPECT_TRUE(A.test(31)); 230 EXPECT_EQ(1u, A.count()); 231 232 A.resize(33); 233 A.setBitsInMask(Mask1, 1); 234 EXPECT_EQ(1u, A.count()); 235 A.setBitsInMask(Mask1, 2); 236 EXPECT_EQ(1u, A.count()); 237 238 A.resize(34); 239 A.setBitsInMask(Mask1, 2); 240 EXPECT_EQ(2u, A.count()); 241 242 A.resize(65); 243 A.setBitsInMask(Mask1, 3); 244 EXPECT_EQ(4u, A.count()); 245 246 A.setBitsNotInMask(Mask1, 1); 247 EXPECT_EQ(32u+3u, A.count()); 248 249 A.setBitsNotInMask(Mask1, 3); 250 EXPECT_EQ(65u, A.count()); 251 252 A.resize(96); 253 EXPECT_EQ(65u, A.count()); 254 255 A.clear(); 256 A.resize(128); 257 A.setBitsNotInMask(Mask1, 3); 258 EXPECT_EQ(96u-5u, A.count()); 259 260 A.clearBitsNotInMask(Mask1, 1); 261 EXPECT_EQ(64-4u, A.count()); 262 } 263 264 TYPED_TEST(BitVectorTest, BinOps) { 265 TypeParam A; 266 TypeParam B; 267 268 A.resize(65); 269 EXPECT_FALSE(A.anyCommon(B)); 270 EXPECT_FALSE(B.anyCommon(B)); 271 272 B.resize(64); 273 A.set(64); 274 EXPECT_FALSE(A.anyCommon(B)); 275 EXPECT_FALSE(B.anyCommon(A)); 276 277 B.set(63); 278 EXPECT_FALSE(A.anyCommon(B)); 279 EXPECT_FALSE(B.anyCommon(A)); 280 281 A.set(63); 282 EXPECT_TRUE(A.anyCommon(B)); 283 EXPECT_TRUE(B.anyCommon(A)); 284 285 B.resize(70); 286 B.set(64); 287 B.reset(63); 288 A.resize(64); 289 EXPECT_FALSE(A.anyCommon(B)); 290 EXPECT_FALSE(B.anyCommon(A)); 291 } 292 293 TYPED_TEST(BitVectorTest, RangeOps) { 294 TypeParam A; 295 A.resize(256); 296 A.reset(); 297 A.set(1, 255); 298 299 EXPECT_FALSE(A.test(0)); 300 EXPECT_TRUE( A.test(1)); 301 EXPECT_TRUE( A.test(23)); 302 EXPECT_TRUE( A.test(254)); 303 EXPECT_FALSE(A.test(255)); 304 305 TypeParam B; 306 B.resize(256); 307 B.set(); 308 B.reset(1, 255); 309 310 EXPECT_TRUE( B.test(0)); 311 EXPECT_FALSE(B.test(1)); 312 EXPECT_FALSE(B.test(23)); 313 EXPECT_FALSE(B.test(254)); 314 EXPECT_TRUE( B.test(255)); 315 316 TypeParam C; 317 C.resize(3); 318 C.reset(); 319 C.set(0, 1); 320 321 EXPECT_TRUE(C.test(0)); 322 EXPECT_FALSE( C.test(1)); 323 EXPECT_FALSE( C.test(2)); 324 325 TypeParam D; 326 D.resize(3); 327 D.set(); 328 D.reset(0, 1); 329 330 EXPECT_FALSE(D.test(0)); 331 EXPECT_TRUE( D.test(1)); 332 EXPECT_TRUE( D.test(2)); 333 334 TypeParam E; 335 E.resize(128); 336 E.reset(); 337 E.set(1, 33); 338 339 EXPECT_FALSE(E.test(0)); 340 EXPECT_TRUE( E.test(1)); 341 EXPECT_TRUE( E.test(32)); 342 EXPECT_FALSE(E.test(33)); 343 } 344 } 345 #endif 346