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_last()); 190 EXPECT_EQ(-1, A.find_first_unset()); 191 EXPECT_EQ(-1, A.find_last_unset()); 192 EXPECT_EQ(-1, A.find_next(0)); 193 EXPECT_EQ(-1, A.find_next_unset(0)); 194 195 // Test finding next set and unset bits in a BitVector with multiple words 196 A.resize(100); 197 A.set(12); 198 A.set(13); 199 A.set(75); 200 201 EXPECT_EQ(75, A.find_last()); 202 EXPECT_EQ(12, A.find_first()); 203 EXPECT_EQ(13, A.find_next(12)); 204 EXPECT_EQ(75, A.find_next(13)); 205 EXPECT_EQ(-1, A.find_next(75)); 206 207 EXPECT_EQ(-1, A.find_prev(12)); 208 EXPECT_EQ(12, A.find_prev(13)); 209 EXPECT_EQ(13, A.find_prev(75)); 210 EXPECT_EQ(75, A.find_prev(90)); 211 212 EXPECT_EQ(0, A.find_first_unset()); 213 EXPECT_EQ(99, A.find_last_unset()); 214 EXPECT_EQ(14, A.find_next_unset(11)); 215 EXPECT_EQ(14, A.find_next_unset(12)); 216 EXPECT_EQ(14, A.find_next_unset(13)); 217 EXPECT_EQ(16, A.find_next_unset(15)); 218 EXPECT_EQ(76, A.find_next_unset(74)); 219 EXPECT_EQ(76, A.find_next_unset(75)); 220 EXPECT_EQ(-1, A.find_next_unset(99)); 221 222 A.set(0, 100); 223 EXPECT_EQ(100U, A.count()); 224 EXPECT_EQ(0, A.find_first()); 225 EXPECT_EQ(99, A.find_last()); 226 EXPECT_EQ(-1, A.find_first_unset()); 227 EXPECT_EQ(-1, A.find_last_unset()); 228 229 A.reset(0, 100); 230 EXPECT_EQ(0U, A.count()); 231 EXPECT_EQ(-1, A.find_first()); 232 EXPECT_EQ(-1, A.find_last()); 233 EXPECT_EQ(0, A.find_first_unset()); 234 EXPECT_EQ(99, A.find_last_unset()); 235 236 // Also test with a vector that is small enough to fit in 1 word. 237 A.resize(20); 238 A.set(3); 239 A.set(4); 240 A.set(16); 241 EXPECT_EQ(16, A.find_last()); 242 EXPECT_EQ(3, A.find_first()); 243 EXPECT_EQ(3, A.find_next(1)); 244 EXPECT_EQ(4, A.find_next(3)); 245 EXPECT_EQ(16, A.find_next(4)); 246 EXPECT_EQ(-1, A.find_next(16)); 247 248 EXPECT_EQ(-1, A.find_prev(3)); 249 EXPECT_EQ(3, A.find_prev(4)); 250 EXPECT_EQ(4, A.find_prev(16)); 251 EXPECT_EQ(16, A.find_prev(18)); 252 253 EXPECT_EQ(0, A.find_first_unset()); 254 EXPECT_EQ(19, A.find_last_unset()); 255 EXPECT_EQ(5, A.find_next_unset(3)); 256 EXPECT_EQ(5, A.find_next_unset(4)); 257 EXPECT_EQ(13, A.find_next_unset(12)); 258 EXPECT_EQ(17, A.find_next_unset(15)); 259 } 260 261 TYPED_TEST(BitVectorTest, CompoundAssignment) { 262 TypeParam A; 263 A.resize(10); 264 A.set(4); 265 A.set(7); 266 267 TypeParam B; 268 B.resize(50); 269 B.set(5); 270 B.set(18); 271 272 A |= B; 273 EXPECT_TRUE(A.test(4)); 274 EXPECT_TRUE(A.test(5)); 275 EXPECT_TRUE(A.test(7)); 276 EXPECT_TRUE(A.test(18)); 277 EXPECT_EQ(4U, A.count()); 278 EXPECT_EQ(50U, A.size()); 279 280 B.resize(10); 281 B.set(); 282 B.reset(2); 283 B.reset(7); 284 A &= B; 285 EXPECT_FALSE(A.test(2)); 286 EXPECT_FALSE(A.test(7)); 287 EXPECT_EQ(2U, A.count()); 288 EXPECT_EQ(50U, A.size()); 289 290 B.resize(100); 291 B.set(); 292 293 A ^= B; 294 EXPECT_TRUE(A.test(2)); 295 EXPECT_TRUE(A.test(7)); 296 EXPECT_EQ(98U, A.count()); 297 EXPECT_EQ(100U, A.size()); 298 } 299 300 TYPED_TEST(BitVectorTest, ProxyIndex) { 301 TypeParam Vec(3); 302 EXPECT_TRUE(Vec.none()); 303 Vec[0] = Vec[1] = Vec[2] = true; 304 EXPECT_EQ(Vec.size(), Vec.count()); 305 Vec[2] = Vec[1] = Vec[0] = false; 306 EXPECT_TRUE(Vec.none()); 307 } 308 309 TYPED_TEST(BitVectorTest, PortableBitMask) { 310 TypeParam A; 311 const uint32_t Mask1[] = { 0x80000000, 6, 5 }; 312 313 A.resize(10); 314 A.setBitsInMask(Mask1, 1); 315 EXPECT_EQ(10u, A.size()); 316 EXPECT_FALSE(A.test(0)); 317 318 A.resize(32); 319 A.setBitsInMask(Mask1, 1); 320 EXPECT_FALSE(A.test(0)); 321 EXPECT_TRUE(A.test(31)); 322 EXPECT_EQ(1u, A.count()); 323 324 A.resize(33); 325 A.setBitsInMask(Mask1, 1); 326 EXPECT_EQ(1u, A.count()); 327 A.setBitsInMask(Mask1, 2); 328 EXPECT_EQ(1u, A.count()); 329 330 A.resize(34); 331 A.setBitsInMask(Mask1, 2); 332 EXPECT_EQ(2u, A.count()); 333 334 A.resize(65); 335 A.setBitsInMask(Mask1, 3); 336 EXPECT_EQ(4u, A.count()); 337 338 A.setBitsNotInMask(Mask1, 1); 339 EXPECT_EQ(32u+3u, A.count()); 340 341 A.setBitsNotInMask(Mask1, 3); 342 EXPECT_EQ(65u, A.count()); 343 344 A.resize(96); 345 EXPECT_EQ(65u, A.count()); 346 347 A.clear(); 348 A.resize(128); 349 A.setBitsNotInMask(Mask1, 3); 350 EXPECT_EQ(96u-5u, A.count()); 351 352 A.clearBitsNotInMask(Mask1, 1); 353 EXPECT_EQ(64-4u, A.count()); 354 } 355 356 TYPED_TEST(BitVectorTest, BinOps) { 357 TypeParam A; 358 TypeParam B; 359 360 A.resize(65); 361 EXPECT_FALSE(A.anyCommon(B)); 362 EXPECT_FALSE(B.anyCommon(B)); 363 364 B.resize(64); 365 A.set(64); 366 EXPECT_FALSE(A.anyCommon(B)); 367 EXPECT_FALSE(B.anyCommon(A)); 368 369 B.set(63); 370 EXPECT_FALSE(A.anyCommon(B)); 371 EXPECT_FALSE(B.anyCommon(A)); 372 373 A.set(63); 374 EXPECT_TRUE(A.anyCommon(B)); 375 EXPECT_TRUE(B.anyCommon(A)); 376 377 B.resize(70); 378 B.set(64); 379 B.reset(63); 380 A.resize(64); 381 EXPECT_FALSE(A.anyCommon(B)); 382 EXPECT_FALSE(B.anyCommon(A)); 383 } 384 385 typedef std::vector<std::pair<int, int>> RangeList; 386 387 template <typename VecType> 388 static inline VecType createBitVector(uint32_t Size, 389 const RangeList &setRanges) { 390 VecType V; 391 V.resize(Size); 392 for (auto &R : setRanges) 393 V.set(R.first, R.second); 394 return V; 395 } 396 397 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) { 398 // Test that shift ops work when the desired shift amount is less 399 // than one word. 400 401 // 1. Case where the number of bits in the BitVector also fit into a single 402 // word. 403 TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}}); 404 TypeParam B = A; 405 406 EXPECT_EQ(4U, A.count()); 407 EXPECT_TRUE(A.test(2)); 408 EXPECT_TRUE(A.test(3)); 409 EXPECT_TRUE(A.test(8)); 410 EXPECT_TRUE(A.test(9)); 411 412 A >>= 1; 413 EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A); 414 415 A <<= 1; 416 EXPECT_EQ(B, A); 417 418 A >>= 10; 419 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 420 421 A = B; 422 A <<= 10; 423 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 424 425 // 2. Case where the number of bits in the BitVector do not fit into a single 426 // word. 427 428 // 31----------------------------------------------------------------------0 429 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 430 A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}}); 431 EXPECT_EQ(40U, A.size()); 432 EXPECT_EQ(22U, A.count()); 433 434 // 2a. Make sure that left shifting some 1 bits out of the vector works. 435 // 31----------------------------------------------------------------------0 436 // Before: 437 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 438 // After: 439 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 440 A <<= 9; 441 EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A); 442 443 // 2b. Make sure that keeping the number of one bits unchanged works. 444 // 31----------------------------------------------------------------------0 445 // Before: 446 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 447 // After: 448 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 449 A >>= 6; 450 EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A); 451 452 // 2c. Make sure that right shifting some 1 bits out of the vector works. 453 // 31----------------------------------------------------------------------0 454 // Before: 455 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 456 // After: 457 // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111 458 A >>= 10; 459 EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A); 460 461 // 3. Big test. 462 A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 463 A <<= 29; 464 EXPECT_EQ(createBitVector<TypeParam>( 465 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}), 466 A); 467 } 468 469 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) { 470 // Test that shift ops work when the desired shift amount is greater than or 471 // equal to the size of a single word. 472 auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 473 474 // Make a copy so we can re-use it later. 475 auto B = A; 476 477 // 1. Shift left by an exact multiple of the word size. This should invoke 478 // only a memmove and no per-word bit operations. 479 A <<= 64; 480 auto Expected = createBitVector<TypeParam>( 481 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}}); 482 EXPECT_EQ(Expected, A); 483 484 // 2. Shift left by a non multiple of the word size. This should invoke both 485 // a memmove and per-word bit operations. 486 A = B; 487 A <<= 93; 488 EXPECT_EQ(createBitVector<TypeParam>( 489 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}), 490 A); 491 492 // 1. Shift right by an exact multiple of the word size. This should invoke 493 // only a memmove and no per-word bit operations. 494 A = B; 495 A >>= 64; 496 EXPECT_EQ( 497 createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A); 498 499 // 2. Shift left by a non multiple of the word size. This should invoke both 500 // a memmove and per-word bit operations. 501 A = B; 502 A >>= 93; 503 EXPECT_EQ( 504 createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A); 505 } 506 507 TYPED_TEST(BitVectorTest, RangeOps) { 508 TypeParam A; 509 A.resize(256); 510 A.reset(); 511 A.set(1, 255); 512 513 EXPECT_FALSE(A.test(0)); 514 EXPECT_TRUE( A.test(1)); 515 EXPECT_TRUE( A.test(23)); 516 EXPECT_TRUE( A.test(254)); 517 EXPECT_FALSE(A.test(255)); 518 519 TypeParam B; 520 B.resize(256); 521 B.set(); 522 B.reset(1, 255); 523 524 EXPECT_TRUE( B.test(0)); 525 EXPECT_FALSE(B.test(1)); 526 EXPECT_FALSE(B.test(23)); 527 EXPECT_FALSE(B.test(254)); 528 EXPECT_TRUE( B.test(255)); 529 530 TypeParam C; 531 C.resize(3); 532 C.reset(); 533 C.set(0, 1); 534 535 EXPECT_TRUE(C.test(0)); 536 EXPECT_FALSE( C.test(1)); 537 EXPECT_FALSE( C.test(2)); 538 539 TypeParam D; 540 D.resize(3); 541 D.set(); 542 D.reset(0, 1); 543 544 EXPECT_FALSE(D.test(0)); 545 EXPECT_TRUE( D.test(1)); 546 EXPECT_TRUE( D.test(2)); 547 548 TypeParam E; 549 E.resize(128); 550 E.reset(); 551 E.set(1, 33); 552 553 EXPECT_FALSE(E.test(0)); 554 EXPECT_TRUE( E.test(1)); 555 EXPECT_TRUE( E.test(32)); 556 EXPECT_FALSE(E.test(33)); 557 558 TypeParam BufferOverrun; 559 unsigned size = sizeof(unsigned long) * 8; 560 BufferOverrun.resize(size); 561 BufferOverrun.reset(0, size); 562 BufferOverrun.set(0, size); 563 } 564 565 TYPED_TEST(BitVectorTest, CompoundTestReset) { 566 TypeParam A(50, true); 567 TypeParam B(50, false); 568 569 TypeParam C(100, true); 570 TypeParam D(100, false); 571 572 EXPECT_FALSE(A.test(A)); 573 EXPECT_TRUE(A.test(B)); 574 EXPECT_FALSE(A.test(C)); 575 EXPECT_TRUE(A.test(D)); 576 EXPECT_FALSE(B.test(A)); 577 EXPECT_FALSE(B.test(B)); 578 EXPECT_FALSE(B.test(C)); 579 EXPECT_FALSE(B.test(D)); 580 EXPECT_TRUE(C.test(A)); 581 EXPECT_TRUE(C.test(B)); 582 EXPECT_FALSE(C.test(C)); 583 EXPECT_TRUE(C.test(D)); 584 585 A.reset(B); 586 A.reset(D); 587 EXPECT_TRUE(A.all()); 588 A.reset(A); 589 EXPECT_TRUE(A.none()); 590 A.set(); 591 A.reset(C); 592 EXPECT_TRUE(A.none()); 593 A.set(); 594 595 C.reset(A); 596 EXPECT_EQ(50, C.find_first()); 597 C.reset(C); 598 EXPECT_TRUE(C.none()); 599 } 600 601 TYPED_TEST(BitVectorTest, MoveConstructor) { 602 TypeParam A(10, true); 603 TypeParam B(std::move(A)); 604 // Check that the move ctor leaves the moved-from object in a valid state. 605 // The following line used to crash. 606 A = B; 607 608 TypeParam C(10, true); 609 EXPECT_EQ(C, A); 610 EXPECT_EQ(C, B); 611 } 612 613 TYPED_TEST(BitVectorTest, MoveAssignment) { 614 TypeParam A(10, true); 615 TypeParam B; 616 B = std::move(A); 617 // Check that move assignment leaves the moved-from object in a valid state. 618 // The following line used to crash. 619 A = B; 620 621 TypeParam C(10, true); 622 EXPECT_EQ(C, A); 623 EXPECT_EQ(C, B); 624 } 625 626 template<class TypeParam> 627 static void testEmpty(const TypeParam &A) { 628 EXPECT_TRUE(A.empty()); 629 EXPECT_EQ((size_t)0, A.size()); 630 EXPECT_EQ((size_t)0, A.count()); 631 EXPECT_FALSE(A.any()); 632 EXPECT_TRUE(A.all()); 633 EXPECT_TRUE(A.none()); 634 EXPECT_EQ(-1, A.find_first()); 635 EXPECT_EQ(A, TypeParam()); 636 } 637 638 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0 639 TYPED_TEST(BitVectorTest, EmptyVector) { 640 TypeParam A; 641 testEmpty(A); 642 643 TypeParam B; 644 B.reset(); 645 testEmpty(B); 646 647 TypeParam C; 648 C.clear(); 649 testEmpty(C); 650 651 TypeParam D(A); 652 testEmpty(D); 653 654 TypeParam E; 655 E = A; 656 testEmpty(E); 657 658 TypeParam F; 659 E.reset(A); 660 testEmpty(E); 661 } 662 663 TYPED_TEST(BitVectorTest, Iterators) { 664 TypeParam Filled(10, true); 665 EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end()); 666 unsigned Counter = 0; 667 for (unsigned Bit : Filled.set_bits()) 668 EXPECT_EQ(Bit, Counter++); 669 670 TypeParam Empty; 671 EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end()); 672 for (unsigned Bit : Empty.set_bits()) { 673 (void)Bit; 674 EXPECT_TRUE(false); 675 } 676 677 TypeParam ToFill(100, false); 678 ToFill.set(0); 679 EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end()); 680 EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end()); 681 EXPECT_EQ(*ToFill.set_bits_begin(), 0U); 682 ToFill.reset(0); 683 EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end()); 684 685 const unsigned List[] = {1, 10, 25, 99}; 686 for (unsigned Num : List) 687 ToFill.set(Num); 688 unsigned i = 0; 689 for (unsigned Bit : ToFill.set_bits()) 690 EXPECT_EQ(List[i++], Bit); 691 } 692 } 693 #endif 694