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 Vec.resize(64); 153 EXPECT_EQ(64U, Vec.count()); 154 EXPECT_EQ(64U, Vec.size()); 155 EXPECT_TRUE(Vec.any()); 156 EXPECT_TRUE(Vec.all()); 157 EXPECT_FALSE(Vec.none()); 158 EXPECT_FALSE(Vec.empty()); 159 160 Vec.flip(); 161 EXPECT_EQ(0U, Vec.count()); 162 EXPECT_EQ(64U, Vec.size()); 163 EXPECT_FALSE(Vec.any()); 164 EXPECT_FALSE(Vec.all()); 165 EXPECT_TRUE(Vec.none()); 166 EXPECT_FALSE(Vec.empty()); 167 168 Inv = TypeParam().flip(); 169 EXPECT_EQ(0U, Inv.count()); 170 EXPECT_EQ(0U, Inv.size()); 171 EXPECT_FALSE(Inv.any()); 172 EXPECT_TRUE(Inv.all()); 173 EXPECT_TRUE(Inv.none()); 174 EXPECT_TRUE(Inv.empty()); 175 176 Vec.clear(); 177 EXPECT_EQ(0U, Vec.count()); 178 EXPECT_EQ(0U, Vec.size()); 179 EXPECT_FALSE(Vec.any()); 180 EXPECT_TRUE(Vec.all()); 181 EXPECT_TRUE(Vec.none()); 182 EXPECT_TRUE(Vec.empty()); 183 } 184 185 TYPED_TEST(BitVectorTest, FindOperations) { 186 // Test finding in an empty BitVector. 187 TypeParam A; 188 EXPECT_EQ(-1, A.find_first()); 189 EXPECT_EQ(-1, A.find_first_unset()); 190 EXPECT_EQ(-1, A.find_next(0)); 191 EXPECT_EQ(-1, A.find_next_unset(0)); 192 193 // Test finding next set and unset bits in a BitVector with multiple words 194 A.resize(100); 195 A.set(12); 196 A.set(13); 197 A.set(75); 198 199 EXPECT_EQ(12, A.find_first()); 200 EXPECT_EQ(13, A.find_next(12)); 201 EXPECT_EQ(75, A.find_next(13)); 202 EXPECT_EQ(-1, A.find_next(75)); 203 204 EXPECT_EQ(0, A.find_first_unset()); 205 EXPECT_EQ(14, A.find_next_unset(11)); 206 EXPECT_EQ(14, A.find_next_unset(12)); 207 EXPECT_EQ(14, A.find_next_unset(13)); 208 EXPECT_EQ(16, A.find_next_unset(15)); 209 EXPECT_EQ(76, A.find_next_unset(74)); 210 EXPECT_EQ(76, A.find_next_unset(75)); 211 EXPECT_EQ(-1, A.find_next_unset(99)); 212 213 A.set(0, 100); 214 EXPECT_EQ(100U, A.count()); 215 EXPECT_EQ(0, A.find_first()); 216 EXPECT_EQ(-1, A.find_first_unset()); 217 218 A.reset(0, 100); 219 EXPECT_EQ(0U, A.count()); 220 EXPECT_EQ(-1, A.find_first()); 221 EXPECT_EQ(0, A.find_first_unset()); 222 } 223 224 TYPED_TEST(BitVectorTest, CompoundAssignment) { 225 TypeParam A; 226 A.resize(10); 227 A.set(4); 228 A.set(7); 229 230 TypeParam B; 231 B.resize(50); 232 B.set(5); 233 B.set(18); 234 235 A |= B; 236 EXPECT_TRUE(A.test(4)); 237 EXPECT_TRUE(A.test(5)); 238 EXPECT_TRUE(A.test(7)); 239 EXPECT_TRUE(A.test(18)); 240 EXPECT_EQ(4U, A.count()); 241 EXPECT_EQ(50U, A.size()); 242 243 B.resize(10); 244 B.set(); 245 B.reset(2); 246 B.reset(7); 247 A &= B; 248 EXPECT_FALSE(A.test(2)); 249 EXPECT_FALSE(A.test(7)); 250 EXPECT_EQ(2U, A.count()); 251 EXPECT_EQ(50U, A.size()); 252 253 B.resize(100); 254 B.set(); 255 256 A ^= B; 257 EXPECT_TRUE(A.test(2)); 258 EXPECT_TRUE(A.test(7)); 259 EXPECT_EQ(98U, A.count()); 260 EXPECT_EQ(100U, A.size()); 261 } 262 263 TYPED_TEST(BitVectorTest, ProxyIndex) { 264 TypeParam Vec(3); 265 EXPECT_TRUE(Vec.none()); 266 Vec[0] = Vec[1] = Vec[2] = true; 267 EXPECT_EQ(Vec.size(), Vec.count()); 268 Vec[2] = Vec[1] = Vec[0] = false; 269 EXPECT_TRUE(Vec.none()); 270 } 271 272 TYPED_TEST(BitVectorTest, PortableBitMask) { 273 TypeParam A; 274 const uint32_t Mask1[] = { 0x80000000, 6, 5 }; 275 276 A.resize(10); 277 A.setBitsInMask(Mask1, 1); 278 EXPECT_EQ(10u, A.size()); 279 EXPECT_FALSE(A.test(0)); 280 281 A.resize(32); 282 A.setBitsInMask(Mask1, 1); 283 EXPECT_FALSE(A.test(0)); 284 EXPECT_TRUE(A.test(31)); 285 EXPECT_EQ(1u, A.count()); 286 287 A.resize(33); 288 A.setBitsInMask(Mask1, 1); 289 EXPECT_EQ(1u, A.count()); 290 A.setBitsInMask(Mask1, 2); 291 EXPECT_EQ(1u, A.count()); 292 293 A.resize(34); 294 A.setBitsInMask(Mask1, 2); 295 EXPECT_EQ(2u, A.count()); 296 297 A.resize(65); 298 A.setBitsInMask(Mask1, 3); 299 EXPECT_EQ(4u, A.count()); 300 301 A.setBitsNotInMask(Mask1, 1); 302 EXPECT_EQ(32u+3u, A.count()); 303 304 A.setBitsNotInMask(Mask1, 3); 305 EXPECT_EQ(65u, A.count()); 306 307 A.resize(96); 308 EXPECT_EQ(65u, A.count()); 309 310 A.clear(); 311 A.resize(128); 312 A.setBitsNotInMask(Mask1, 3); 313 EXPECT_EQ(96u-5u, A.count()); 314 315 A.clearBitsNotInMask(Mask1, 1); 316 EXPECT_EQ(64-4u, A.count()); 317 } 318 319 TYPED_TEST(BitVectorTest, BinOps) { 320 TypeParam A; 321 TypeParam B; 322 323 A.resize(65); 324 EXPECT_FALSE(A.anyCommon(B)); 325 EXPECT_FALSE(B.anyCommon(B)); 326 327 B.resize(64); 328 A.set(64); 329 EXPECT_FALSE(A.anyCommon(B)); 330 EXPECT_FALSE(B.anyCommon(A)); 331 332 B.set(63); 333 EXPECT_FALSE(A.anyCommon(B)); 334 EXPECT_FALSE(B.anyCommon(A)); 335 336 A.set(63); 337 EXPECT_TRUE(A.anyCommon(B)); 338 EXPECT_TRUE(B.anyCommon(A)); 339 340 B.resize(70); 341 B.set(64); 342 B.reset(63); 343 A.resize(64); 344 EXPECT_FALSE(A.anyCommon(B)); 345 EXPECT_FALSE(B.anyCommon(A)); 346 } 347 348 TYPED_TEST(BitVectorTest, RangeOps) { 349 TypeParam A; 350 A.resize(256); 351 A.reset(); 352 A.set(1, 255); 353 354 EXPECT_FALSE(A.test(0)); 355 EXPECT_TRUE( A.test(1)); 356 EXPECT_TRUE( A.test(23)); 357 EXPECT_TRUE( A.test(254)); 358 EXPECT_FALSE(A.test(255)); 359 360 TypeParam B; 361 B.resize(256); 362 B.set(); 363 B.reset(1, 255); 364 365 EXPECT_TRUE( B.test(0)); 366 EXPECT_FALSE(B.test(1)); 367 EXPECT_FALSE(B.test(23)); 368 EXPECT_FALSE(B.test(254)); 369 EXPECT_TRUE( B.test(255)); 370 371 TypeParam C; 372 C.resize(3); 373 C.reset(); 374 C.set(0, 1); 375 376 EXPECT_TRUE(C.test(0)); 377 EXPECT_FALSE( C.test(1)); 378 EXPECT_FALSE( C.test(2)); 379 380 TypeParam D; 381 D.resize(3); 382 D.set(); 383 D.reset(0, 1); 384 385 EXPECT_FALSE(D.test(0)); 386 EXPECT_TRUE( D.test(1)); 387 EXPECT_TRUE( D.test(2)); 388 389 TypeParam E; 390 E.resize(128); 391 E.reset(); 392 E.set(1, 33); 393 394 EXPECT_FALSE(E.test(0)); 395 EXPECT_TRUE( E.test(1)); 396 EXPECT_TRUE( E.test(32)); 397 EXPECT_FALSE(E.test(33)); 398 399 TypeParam BufferOverrun; 400 unsigned size = sizeof(unsigned long) * 8; 401 BufferOverrun.resize(size); 402 BufferOverrun.reset(0, size); 403 BufferOverrun.set(0, size); 404 } 405 406 TYPED_TEST(BitVectorTest, CompoundTestReset) { 407 TypeParam A(50, true); 408 TypeParam B(50, false); 409 410 TypeParam C(100, true); 411 TypeParam D(100, false); 412 413 EXPECT_FALSE(A.test(A)); 414 EXPECT_TRUE(A.test(B)); 415 EXPECT_FALSE(A.test(C)); 416 EXPECT_TRUE(A.test(D)); 417 EXPECT_FALSE(B.test(A)); 418 EXPECT_FALSE(B.test(B)); 419 EXPECT_FALSE(B.test(C)); 420 EXPECT_FALSE(B.test(D)); 421 EXPECT_TRUE(C.test(A)); 422 EXPECT_TRUE(C.test(B)); 423 EXPECT_FALSE(C.test(C)); 424 EXPECT_TRUE(C.test(D)); 425 426 A.reset(B); 427 A.reset(D); 428 EXPECT_TRUE(A.all()); 429 A.reset(A); 430 EXPECT_TRUE(A.none()); 431 A.set(); 432 A.reset(C); 433 EXPECT_TRUE(A.none()); 434 A.set(); 435 436 C.reset(A); 437 EXPECT_EQ(50, C.find_first()); 438 C.reset(C); 439 EXPECT_TRUE(C.none()); 440 } 441 442 TYPED_TEST(BitVectorTest, MoveConstructor) { 443 TypeParam A(10, true); 444 TypeParam B(std::move(A)); 445 // Check that the move ctor leaves the moved-from object in a valid state. 446 // The following line used to crash. 447 A = B; 448 449 TypeParam C(10, true); 450 EXPECT_EQ(C, A); 451 EXPECT_EQ(C, B); 452 } 453 454 TYPED_TEST(BitVectorTest, MoveAssignment) { 455 TypeParam A(10, true); 456 TypeParam B; 457 B = std::move(A); 458 // Check that move assignment leaves the moved-from object in a valid state. 459 // The following line used to crash. 460 A = B; 461 462 TypeParam C(10, true); 463 EXPECT_EQ(C, A); 464 EXPECT_EQ(C, B); 465 } 466 467 template<class TypeParam> 468 static void testEmpty(const TypeParam &A) { 469 EXPECT_TRUE(A.empty()); 470 EXPECT_EQ((size_t)0, A.size()); 471 EXPECT_EQ((size_t)0, A.count()); 472 EXPECT_FALSE(A.any()); 473 EXPECT_TRUE(A.all()); 474 EXPECT_TRUE(A.none()); 475 EXPECT_EQ(-1, A.find_first()); 476 EXPECT_EQ(A, TypeParam()); 477 } 478 479 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0 480 TYPED_TEST(BitVectorTest, EmptyVector) { 481 TypeParam A; 482 testEmpty(A); 483 484 TypeParam B; 485 B.reset(); 486 testEmpty(B); 487 488 TypeParam C; 489 C.clear(); 490 testEmpty(C); 491 492 TypeParam D(A); 493 testEmpty(D); 494 495 TypeParam E; 496 E = A; 497 testEmpty(E); 498 499 TypeParam F; 500 E.reset(A); 501 testEmpty(E); 502 } 503 504 } 505 #endif 506