1432 lines · cpp
1//===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/BitVector.h"10#include "llvm/ADT/DenseSet.h"11#include "llvm/ADT/STLExtras.h"12#include "llvm/ADT/SmallBitVector.h"13#include "gtest/gtest.h"14 15using namespace llvm;16 17namespace {18 19// Test fixture20template <typename T>21class BitVectorTest : public ::testing::Test { };22 23// Test both BitVector and SmallBitVector with the same suite of tests.24using BitVectorTestTypes = ::testing::Types<BitVector, SmallBitVector>;25TYPED_TEST_SUITE(BitVectorTest, BitVectorTestTypes, );26 27TYPED_TEST(BitVectorTest, TrivialOperation) {28 TypeParam Vec;29 EXPECT_EQ(0U, Vec.count());30 EXPECT_EQ(0U, Vec.size());31 EXPECT_FALSE(Vec.any());32 EXPECT_TRUE(Vec.all());33 EXPECT_TRUE(Vec.none());34 EXPECT_TRUE(Vec.empty());35 36 Vec.resize(5, true);37 EXPECT_EQ(5U, Vec.count());38 EXPECT_EQ(5U, Vec.size());39 EXPECT_TRUE(Vec.any());40 EXPECT_TRUE(Vec.all());41 EXPECT_FALSE(Vec.none());42 EXPECT_FALSE(Vec.empty());43 44 Vec.resize(11);45 EXPECT_EQ(5U, Vec.count());46 EXPECT_EQ(11U, Vec.size());47 EXPECT_TRUE(Vec.any());48 EXPECT_FALSE(Vec.all());49 EXPECT_FALSE(Vec.none());50 EXPECT_FALSE(Vec.empty());51 52 TypeParam Inv = Vec;53 Inv.flip();54 EXPECT_EQ(6U, Inv.count());55 EXPECT_EQ(11U, Inv.size());56 EXPECT_TRUE(Inv.any());57 EXPECT_FALSE(Inv.all());58 EXPECT_FALSE(Inv.none());59 EXPECT_FALSE(Inv.empty());60 61 EXPECT_FALSE(Inv == Vec);62 EXPECT_TRUE(Inv != Vec);63 Vec.flip();64 EXPECT_TRUE(Inv == Vec);65 EXPECT_FALSE(Inv != Vec);66 67 // Add some "interesting" data to Vec.68 Vec.resize(23, true);69 Vec.resize(25, false);70 Vec.resize(26, true);71 Vec.resize(29, false);72 Vec.resize(33, true);73 Vec.resize(57, false);74 unsigned Count = 0;75 for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {76 ++Count;77 EXPECT_TRUE(Vec[i]);78 EXPECT_TRUE(Vec.test(i));79 }80 EXPECT_EQ(Count, Vec.count());81 EXPECT_EQ(Count, 23u);82 EXPECT_FALSE(Vec[0]);83 EXPECT_TRUE(Vec[32]);84 EXPECT_FALSE(Vec[56]);85 Vec.resize(61, false);86 87 TypeParam Copy = Vec;88 TypeParam Alt(3, false);89 Alt.resize(6, true);90 std::swap(Alt, Vec);91 EXPECT_TRUE(Copy == Alt);92 EXPECT_TRUE(Vec.size() == 6);93 EXPECT_TRUE(Vec.count() == 3);94 EXPECT_TRUE(Vec.find_first() == 3);95 std::swap(Copy, Vec);96 97 // Add some more "interesting" data.98 Vec.resize(68, true);99 Vec.resize(78, false);100 Vec.resize(89, true);101 Vec.resize(90, false);102 Vec.resize(91, true);103 Vec.resize(130, false);104 Count = 0;105 for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {106 ++Count;107 EXPECT_TRUE(Vec[i]);108 EXPECT_TRUE(Vec.test(i));109 }110 EXPECT_EQ(Count, Vec.count());111 EXPECT_EQ(Count, 42u);112 EXPECT_FALSE(Vec[0]);113 EXPECT_TRUE(Vec[32]);114 EXPECT_FALSE(Vec[60]);115 EXPECT_FALSE(Vec[129]);116 117 Vec.flip(60);118 EXPECT_TRUE(Vec[60]);119 EXPECT_EQ(Count + 1, Vec.count());120 Vec.flip(60);121 EXPECT_FALSE(Vec[60]);122 EXPECT_EQ(Count, Vec.count());123 124 Vec.reset(32);125 EXPECT_FALSE(Vec[32]);126 EXPECT_EQ(Count - 1, Vec.count());127 Vec.set(32);128 EXPECT_TRUE(Vec[32]);129 EXPECT_EQ(Count, Vec.count());130 131 Vec.flip();132 EXPECT_EQ(Vec.size() - Count, Vec.count());133 134 Vec.reset();135 EXPECT_EQ(0U, Vec.count());136 EXPECT_EQ(130U, Vec.size());137 EXPECT_FALSE(Vec.any());138 EXPECT_FALSE(Vec.all());139 EXPECT_TRUE(Vec.none());140 EXPECT_FALSE(Vec.empty());141 142 Vec.flip();143 EXPECT_EQ(130U, Vec.count());144 EXPECT_EQ(130U, Vec.size());145 EXPECT_TRUE(Vec.any());146 EXPECT_TRUE(Vec.all());147 EXPECT_FALSE(Vec.none());148 EXPECT_FALSE(Vec.empty());149 150 Vec.resize(64);151 EXPECT_EQ(64U, Vec.count());152 EXPECT_EQ(64U, Vec.size());153 EXPECT_TRUE(Vec.any());154 EXPECT_TRUE(Vec.all());155 EXPECT_FALSE(Vec.none());156 EXPECT_FALSE(Vec.empty());157 158 Vec.flip();159 EXPECT_EQ(0U, Vec.count());160 EXPECT_EQ(64U, Vec.size());161 EXPECT_FALSE(Vec.any());162 EXPECT_FALSE(Vec.all());163 EXPECT_TRUE(Vec.none());164 EXPECT_FALSE(Vec.empty());165 166 Inv = TypeParam().flip();167 EXPECT_EQ(0U, Inv.count());168 EXPECT_EQ(0U, Inv.size());169 EXPECT_FALSE(Inv.any());170 EXPECT_TRUE(Inv.all());171 EXPECT_TRUE(Inv.none());172 EXPECT_TRUE(Inv.empty());173 174 Vec.clear();175 EXPECT_EQ(0U, Vec.count());176 EXPECT_EQ(0U, Vec.size());177 EXPECT_FALSE(Vec.any());178 EXPECT_TRUE(Vec.all());179 EXPECT_TRUE(Vec.none());180 EXPECT_TRUE(Vec.empty());181}182 183TYPED_TEST(BitVectorTest, Equality) {184 TypeParam A;185 TypeParam B;186 EXPECT_TRUE(A == B);187 A.resize(10);188 EXPECT_FALSE(A == B);189 B.resize(10);190 EXPECT_TRUE(A == B);191 A.set(5);192 EXPECT_FALSE(A == B);193 B.set(5);194 EXPECT_TRUE(A == B);195 A.resize(20);196 EXPECT_FALSE(A == B);197 B.resize(20);198 EXPECT_TRUE(A == B);199}200 201TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) {202 TypeParam A;203 204 // Test finding next set and unset bits in a BitVector with multiple words205 A.resize(100);206 A.set(12);207 A.set(13);208 A.set(75);209 210 EXPECT_EQ(75, A.find_last());211 EXPECT_EQ(12, A.find_first());212 EXPECT_EQ(13, A.find_next(12));213 EXPECT_EQ(75, A.find_next(13));214 EXPECT_EQ(-1, A.find_next(75));215 216 EXPECT_EQ(-1, A.find_prev(12));217 EXPECT_EQ(12, A.find_prev(13));218 EXPECT_EQ(13, A.find_prev(75));219 EXPECT_EQ(75, A.find_prev(90));220 221 EXPECT_EQ(0, A.find_first_unset());222 EXPECT_EQ(99, A.find_last_unset());223 EXPECT_EQ(14, A.find_next_unset(11));224 EXPECT_EQ(14, A.find_next_unset(12));225 EXPECT_EQ(14, A.find_next_unset(13));226 EXPECT_EQ(16, A.find_next_unset(15));227 EXPECT_EQ(76, A.find_next_unset(74));228 EXPECT_EQ(76, A.find_next_unset(75));229 EXPECT_EQ(-1, A.find_next_unset(99));230 231 A.set(0, 100);232 EXPECT_EQ(100U, A.count());233 EXPECT_EQ(0, A.find_first());234 EXPECT_EQ(-1, A.find_first_unset());235 EXPECT_EQ(-1, A.find_last_unset());236 EXPECT_EQ(99, A.find_last());237 EXPECT_EQ(99, A.find_next(98));238 239 A.reset(0, 100);240 EXPECT_EQ(0U, A.count());241 EXPECT_EQ(-1, A.find_first());242 EXPECT_EQ(-1, A.find_last());243 EXPECT_EQ(0, A.find_first_unset());244 EXPECT_EQ(99, A.find_last_unset());245 EXPECT_EQ(99, A.find_next_unset(98));246}247 248// Test finding next set and unset bits in a BitVector/SmallBitVector within a249// uintptr_t - check both 32-bit (Multi) and 64-bit (Small) targets.250TYPED_TEST(BitVectorTest, SimpleFindOps64Bit) {251 TypeParam A;252 253 A.resize(57);254 A.set(12);255 A.set(13);256 A.set(47);257 258 EXPECT_EQ(47, A.find_last());259 EXPECT_EQ(12, A.find_first());260 EXPECT_EQ(13, A.find_next(12));261 EXPECT_EQ(47, A.find_next(13));262 EXPECT_EQ(-1, A.find_next(47));263 264 EXPECT_EQ(-1, A.find_prev(12));265 EXPECT_EQ(12, A.find_prev(13));266 EXPECT_EQ(13, A.find_prev(47));267 EXPECT_EQ(47, A.find_prev(56));268 269 EXPECT_EQ(0, A.find_first_unset());270 EXPECT_EQ(56, A.find_last_unset());271 EXPECT_EQ(14, A.find_next_unset(11));272 EXPECT_EQ(14, A.find_next_unset(12));273 EXPECT_EQ(14, A.find_next_unset(13));274 EXPECT_EQ(16, A.find_next_unset(15));275 EXPECT_EQ(48, A.find_next_unset(46));276 EXPECT_EQ(48, A.find_next_unset(47));277 EXPECT_EQ(-1, A.find_next_unset(56));278}279 280// Check if a SmallBitVector is in small mode. This check is used in tests281// that run for both SmallBitVector and BitVector. This check doesn't apply282// to BitVector so we provide an overload that returns true to get the tests283// to compile.284static bool SmallBitVectorIsSmallMode(const SmallBitVector &bv) {285 return bv.isSmall();286}287static bool SmallBitVectorIsSmallMode(const BitVector &) { return true; }288 289// These tests are intended to exercise the single-word case of BitVector290// and the small-mode case of SmallBitVector.291TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) {292 // Test finding in an empty BitVector.293 TypeParam A;294 ASSERT_TRUE(SmallBitVectorIsSmallMode(A));295 EXPECT_EQ(-1, A.find_first());296 EXPECT_EQ(-1, A.find_last());297 EXPECT_EQ(-1, A.find_first_unset());298 EXPECT_EQ(-1, A.find_last_unset());299 300 A.resize(20);301 ASSERT_TRUE(SmallBitVectorIsSmallMode(A));302 EXPECT_EQ(-1, A.find_first());303 EXPECT_EQ(-1, A.find_last());304 EXPECT_EQ(-1, A.find_next(5));305 EXPECT_EQ(-1, A.find_next(19));306 EXPECT_EQ(-1, A.find_prev(5));307 EXPECT_EQ(-1, A.find_prev(20));308 EXPECT_EQ(0, A.find_first_unset());309 EXPECT_EQ(19, A.find_last_unset());310 EXPECT_EQ(6, A.find_next_unset(5));311 EXPECT_EQ(-1, A.find_next_unset(19));312 313 A.set(3);314 A.set(4);315 A.set(16);316 ASSERT_TRUE(SmallBitVectorIsSmallMode(A));317 EXPECT_EQ(16, A.find_last());318 EXPECT_EQ(3, A.find_first());319 EXPECT_EQ(3, A.find_next(1));320 EXPECT_EQ(4, A.find_next(3));321 EXPECT_EQ(16, A.find_next(4));322 EXPECT_EQ(-1, A.find_next(16));323 324 EXPECT_EQ(-1, A.find_prev(3));325 EXPECT_EQ(3, A.find_prev(4));326 EXPECT_EQ(4, A.find_prev(16));327 EXPECT_EQ(16, A.find_prev(18));328 329 EXPECT_EQ(0, A.find_first_unset());330 EXPECT_EQ(19, A.find_last_unset());331 EXPECT_EQ(5, A.find_next_unset(3));332 EXPECT_EQ(5, A.find_next_unset(4));333 EXPECT_EQ(13, A.find_next_unset(12));334 EXPECT_EQ(17, A.find_next_unset(15));335 336 A.set();337 ASSERT_TRUE(SmallBitVectorIsSmallMode(A));338 EXPECT_EQ(0, A.find_first());339 EXPECT_EQ(19, A.find_last());340 EXPECT_EQ(6, A.find_next(5));341 EXPECT_EQ(-1, A.find_next(19));342 EXPECT_EQ(4, A.find_prev(5));343 EXPECT_EQ(19, A.find_prev(20));344 EXPECT_EQ(-1, A.find_first_unset());345 EXPECT_EQ(-1, A.find_last_unset());346 EXPECT_EQ(-1, A.find_next_unset(5));347 EXPECT_EQ(-1, A.find_next_unset(19));348}349 350TEST(BitVectorTest, FindInRangeMultiWord) {351 BitVector Vec;352 353 Vec.resize(200);354 Vec.set(3, 7);355 Vec.set(24, 35);356 Vec.set(50, 70);357 Vec.set(150);358 Vec.set(152);359 Vec.set(154);360 361 // find first362 EXPECT_EQ(-1, Vec.find_first_in(0, 0));363 EXPECT_EQ(-1, Vec.find_first_in(24, 24));364 EXPECT_EQ(-1, Vec.find_first_in(7, 24));365 366 EXPECT_EQ(3, Vec.find_first_in(0, 10));367 EXPECT_EQ(4, Vec.find_first_in(4, 10));368 EXPECT_EQ(150, Vec.find_first_in(100, 200));369 EXPECT_EQ(152, Vec.find_first_in(151, 200));370 EXPECT_EQ(154, Vec.find_first_in(153, 200));371 372 EXPECT_EQ(-1, Vec.find_first_in(155, 200));373 Vec.set(199);374 EXPECT_EQ(199, Vec.find_first_in(199, 200));375 Vec.reset(199);376 377 // find last378 EXPECT_EQ(-1, Vec.find_last_in(0, 0));379 EXPECT_EQ(-1, Vec.find_last_in(24, 24));380 EXPECT_EQ(-1, Vec.find_last_in(7, 24));381 382 EXPECT_EQ(6, Vec.find_last_in(0, 10));383 EXPECT_EQ(5, Vec.find_last_in(0, 6));384 EXPECT_EQ(154, Vec.find_last_in(100, 155));385 EXPECT_EQ(152, Vec.find_last_in(100, 154));386 EXPECT_EQ(150, Vec.find_last_in(100, 152));387 EXPECT_EQ(-1, Vec.find_last_in(100, 150));388 Vec.set(199);389 EXPECT_EQ(199, Vec.find_last_in(199, 200));390 Vec.reset(199);391 392 // find first unset393 EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));394 EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));395 EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35));396 397 EXPECT_EQ(0, Vec.find_first_unset_in(0, 10));398 EXPECT_EQ(1, Vec.find_first_unset_in(1, 10));399 EXPECT_EQ(7, Vec.find_first_unset_in(5, 25));400 EXPECT_EQ(151, Vec.find_first_unset_in(150, 200));401 EXPECT_EQ(151, Vec.find_first_unset_in(151, 200));402 EXPECT_EQ(153, Vec.find_first_unset_in(152, 200));403 EXPECT_EQ(153, Vec.find_first_unset_in(153, 200));404 EXPECT_EQ(155, Vec.find_first_unset_in(154, 200));405 EXPECT_EQ(155, Vec.find_first_unset_in(155, 200));406 EXPECT_EQ(199, Vec.find_first_unset_in(199, 200));407 408 // find last unset409 EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));410 EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));411 EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35));412 413 EXPECT_EQ(9, Vec.find_last_unset_in(0, 10));414 EXPECT_EQ(8, Vec.find_last_unset_in(0, 9));415 EXPECT_EQ(2, Vec.find_last_unset_in(0, 7));416 EXPECT_EQ(149, Vec.find_last_unset_in(100, 151));417 EXPECT_EQ(151, Vec.find_last_unset_in(100, 152));418 EXPECT_EQ(151, Vec.find_last_unset_in(100, 153));419 EXPECT_EQ(153, Vec.find_last_unset_in(100, 154));420 EXPECT_EQ(153, Vec.find_last_unset_in(100, 155));421 EXPECT_EQ(155, Vec.find_last_unset_in(100, 156));422 EXPECT_EQ(199, Vec.find_last_unset_in(199, 200));423}424 425TEST(BitVectorTest, FindInRangeSingleWord) {426 // When the bit vector contains only a single word, this is slightly different427 // than when the bit vector contains multiple words, because masks are applied428 // to the front and back of the same word. So make sure this works.429 BitVector Vec;430 431 Vec.resize(25);432 Vec.set(2, 4);433 Vec.set(6, 9);434 Vec.set(12, 15);435 Vec.set(19);436 Vec.set(21);437 Vec.set(23);438 439 // find first440 EXPECT_EQ(-1, Vec.find_first_in(0, 0));441 EXPECT_EQ(-1, Vec.find_first_in(24, 24));442 EXPECT_EQ(-1, Vec.find_first_in(9, 12));443 444 EXPECT_EQ(2, Vec.find_first_in(0, 10));445 EXPECT_EQ(6, Vec.find_first_in(4, 10));446 EXPECT_EQ(19, Vec.find_first_in(18, 25));447 EXPECT_EQ(21, Vec.find_first_in(20, 25));448 EXPECT_EQ(23, Vec.find_first_in(22, 25));449 EXPECT_EQ(-1, Vec.find_first_in(24, 25));450 451 // find last452 EXPECT_EQ(-1, Vec.find_last_in(0, 0));453 EXPECT_EQ(-1, Vec.find_last_in(24, 24));454 EXPECT_EQ(-1, Vec.find_last_in(9, 12));455 456 EXPECT_EQ(8, Vec.find_last_in(0, 10));457 EXPECT_EQ(3, Vec.find_last_in(0, 6));458 EXPECT_EQ(23, Vec.find_last_in(18, 25));459 EXPECT_EQ(21, Vec.find_last_in(18, 23));460 EXPECT_EQ(19, Vec.find_last_in(18, 21));461 EXPECT_EQ(-1, Vec.find_last_in(18, 19));462 463 // find first unset464 EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));465 EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));466 EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9));467 468 EXPECT_EQ(0, Vec.find_first_unset_in(0, 6));469 EXPECT_EQ(1, Vec.find_first_unset_in(1, 6));470 EXPECT_EQ(9, Vec.find_first_unset_in(7, 13));471 EXPECT_EQ(18, Vec.find_first_unset_in(18, 25));472 EXPECT_EQ(20, Vec.find_first_unset_in(19, 25));473 EXPECT_EQ(20, Vec.find_first_unset_in(20, 25));474 EXPECT_EQ(22, Vec.find_first_unset_in(21, 25));475 EXPECT_EQ(22, Vec.find_first_unset_in(22, 25));476 EXPECT_EQ(24, Vec.find_first_unset_in(23, 25));477 EXPECT_EQ(24, Vec.find_first_unset_in(24, 25));478 479 // find last unset480 EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));481 EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));482 EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9));483 484 EXPECT_EQ(5, Vec.find_last_unset_in(0, 6));485 EXPECT_EQ(4, Vec.find_last_unset_in(0, 5));486 EXPECT_EQ(1, Vec.find_last_unset_in(0, 4));487 EXPECT_EQ(11, Vec.find_last_unset_in(7, 13));488 EXPECT_EQ(24, Vec.find_last_unset_in(18, 25));489 EXPECT_EQ(22, Vec.find_last_unset_in(18, 24));490 EXPECT_EQ(22, Vec.find_last_unset_in(18, 23));491 EXPECT_EQ(20, Vec.find_last_unset_in(18, 22));492 EXPECT_EQ(20, Vec.find_last_unset_in(18, 21));493 EXPECT_EQ(18, Vec.find_last_unset_in(18, 20));494 EXPECT_EQ(18, Vec.find_last_unset_in(18, 19));495}496 497TYPED_TEST(BitVectorTest, CompoundAssignment) {498 TypeParam A;499 A.resize(10);500 A.set(4);501 A.set(7);502 503 TypeParam B;504 B.resize(50);505 B.set(5);506 B.set(18);507 508 A |= B;509 EXPECT_TRUE(A.test(4));510 EXPECT_TRUE(A.test(5));511 EXPECT_TRUE(A.test(7));512 EXPECT_TRUE(A.test(18));513 EXPECT_EQ(4U, A.count());514 EXPECT_EQ(50U, A.size());515 516 B.resize(10);517 B.set();518 B.reset(2);519 B.reset(7);520 A &= B;521 EXPECT_FALSE(A.test(2));522 EXPECT_FALSE(A.test(7));523 EXPECT_TRUE(A.test(4));524 EXPECT_TRUE(A.test(5));525 EXPECT_EQ(2U, A.count());526 EXPECT_EQ(50U, A.size());527 528 B.resize(100);529 B.set();530 531 A ^= B;532 EXPECT_TRUE(A.test(2));533 EXPECT_TRUE(A.test(7));534 EXPECT_EQ(98U, A.count());535 EXPECT_EQ(100U, A.size());536}537 538// Test SmallBitVector operations with mixed big/small representations539TYPED_TEST(BitVectorTest, MixedBigSmall) {540 {541 TypeParam Big;542 TypeParam Small;543 544 Big.reserve(100);545 Big.resize(20);546 Small.resize(10);547 548 Small.set(0);549 Small.set(1);550 Big.set(0);551 Big.set(2);552 Big.set(16);553 554 Small &= Big;555 EXPECT_TRUE(Small.test(0));556 EXPECT_EQ(1u, Small.count());557 // FIXME BitVector and SmallBitVector behave differently here.558 // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())559 // but BitVector does not.560 // EXPECT_EQ(20u, Small.size());561 }562 563 {564 TypeParam Big;565 TypeParam Small;566 567 Big.reserve(100);568 Big.resize(20);569 Small.resize(10);570 571 Small.set(0);572 Small.set(1);573 Big.set(0);574 Big.set(2);575 Big.set(16);576 577 Big &= Small;578 EXPECT_TRUE(Big.test(0));579 EXPECT_EQ(1u, Big.count());580 // FIXME BitVector and SmallBitVector behave differently here.581 // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())582 // but BitVector does not.583 // EXPECT_EQ(20u, Big.size());584 }585 586 {587 TypeParam Big;588 TypeParam Small;589 590 Big.reserve(100);591 Big.resize(20);592 Small.resize(10);593 594 Small.set(0);595 Small.set(1);596 Big.set(0);597 Big.set(2);598 Big.set(16);599 600 Small |= Big;601 EXPECT_TRUE(Small.test(0));602 EXPECT_TRUE(Small.test(1));603 EXPECT_TRUE(Small.test(2));604 EXPECT_TRUE(Small.test(16));605 EXPECT_EQ(4u, Small.count());606 EXPECT_EQ(20u, Small.size());607 }608 609 {610 TypeParam Big;611 TypeParam Small;612 613 Big.reserve(100);614 Big.resize(20);615 Small.resize(10);616 617 Small.set(0);618 Small.set(1);619 Big.set(0);620 Big.set(2);621 Big.set(16);622 623 Big |= Small;624 EXPECT_TRUE(Big.test(0));625 EXPECT_TRUE(Big.test(1));626 EXPECT_TRUE(Big.test(2));627 EXPECT_TRUE(Big.test(16));628 EXPECT_EQ(4u, Big.count());629 EXPECT_EQ(20u, Big.size());630 }631 632 {633 TypeParam Big;634 TypeParam Small;635 636 Big.reserve(100);637 Big.resize(20);638 Small.resize(10);639 640 Small.set(0);641 Small.set(1);642 Big.set(0);643 Big.set(2);644 Big.set(16);645 646 Small ^= Big;647 EXPECT_TRUE(Small.test(1));648 EXPECT_TRUE(Small.test(2));649 EXPECT_TRUE(Small.test(16));650 EXPECT_EQ(3u, Small.count());651 EXPECT_EQ(20u, Small.size());652 }653 654 {655 TypeParam Big;656 TypeParam Small;657 658 Big.reserve(100);659 Big.resize(20);660 Small.resize(10);661 662 Small.set(0);663 Small.set(1);664 Big.set(0);665 Big.set(2);666 Big.set(16);667 668 Big ^= Small;669 EXPECT_TRUE(Big.test(1));670 EXPECT_TRUE(Big.test(2));671 EXPECT_TRUE(Big.test(16));672 EXPECT_EQ(3u, Big.count());673 EXPECT_EQ(20u, Big.size());674 }675 676 {677 TypeParam Big;678 TypeParam Small;679 680 Big.reserve(100);681 Big.resize(20);682 Small.resize(10);683 684 Small.set(0);685 Small.set(1);686 Big.set(0);687 Big.set(2);688 Big.set(16);689 690 Small.reset(Big);691 EXPECT_TRUE(Small.test(1));692 EXPECT_EQ(1u, Small.count());693 EXPECT_EQ(10u, Small.size());694 }695 696 {697 TypeParam Big;698 TypeParam Small;699 700 Big.reserve(100);701 Big.resize(20);702 Small.resize(10);703 704 Small.set(0);705 Small.set(1);706 Big.set(0);707 Big.set(2);708 Big.set(16);709 710 Big.reset(Small);711 EXPECT_TRUE(Big.test(2));712 EXPECT_TRUE(Big.test(16));713 EXPECT_EQ(2u, Big.count());714 EXPECT_EQ(20u, Big.size());715 }716 717 {718 TypeParam Big;719 TypeParam Small;720 721 Big.reserve(100);722 Big.resize(10);723 Small.resize(10);724 725 Small.set(0);726 Small.set(1);727 Big.set(0);728 729 EXPECT_FALSE(Big == Small);730 EXPECT_FALSE(Small == Big);731 Big.set(1);732 EXPECT_TRUE(Big == Small);733 EXPECT_TRUE(Small == Big);734 }735 736 {737 TypeParam Big;738 TypeParam Small;739 740 Big.reserve(100);741 Big.resize(20);742 Small.resize(10);743 744 Small.set(0);745 Big.set(1);746 747 EXPECT_FALSE(Small.anyCommon(Big));748 EXPECT_FALSE(Big.anyCommon(Small));749 Big.set(0);750 EXPECT_TRUE(Small.anyCommon(Big));751 EXPECT_TRUE(Big.anyCommon(Small));752 }753 754 {755 TypeParam Big;756 TypeParam Small;757 758 Big.reserve(100);759 Big.resize(10);760 Small.resize(10);761 762 Small.set(0);763 Small.set(1);764 Big.set(0);765 766 EXPECT_TRUE(Small.test(Big));767 EXPECT_FALSE(Big.test(Small));768 Big.set(1);769 EXPECT_FALSE(Small.test(Big));770 EXPECT_FALSE(Big.test(Small));771 }772}773 774TYPED_TEST(BitVectorTest, ProxyIndex) {775 TypeParam Vec(3);776 EXPECT_TRUE(Vec.none());777 Vec[0] = Vec[1] = Vec[2] = true;778 EXPECT_EQ(Vec.size(), Vec.count());779 Vec[2] = Vec[1] = Vec[0] = false;780 EXPECT_TRUE(Vec.none());781}782 783 784TYPED_TEST(BitVectorTest, PortableBitMask) {785 TypeParam A;786 const uint32_t Mask1[] = { 0x80000000, 6, 5 };787 788 A.resize(10);789 A.setBitsInMask(Mask1, 1);790 EXPECT_EQ(10u, A.size());791 EXPECT_FALSE(A.test(0));792 793 A.resize(32);794 A.setBitsInMask(Mask1, 1);795 EXPECT_FALSE(A.test(0));796 EXPECT_TRUE(A.test(31));797 EXPECT_EQ(1u, A.count());798 799 A.resize(33);800 A.setBitsInMask(Mask1, 1);801 EXPECT_EQ(1u, A.count());802 A.setBitsInMask(Mask1, 2);803 EXPECT_EQ(1u, A.count());804 805 A.resize(34);806 A.setBitsInMask(Mask1, 2);807 EXPECT_EQ(2u, A.count());808 809 A.resize(65);810 A.setBitsInMask(Mask1, 3);811 EXPECT_EQ(4u, A.count());812 813 A.setBitsNotInMask(Mask1, 1);814 EXPECT_EQ(32u+3u, A.count());815 816 A.setBitsNotInMask(Mask1, 3);817 EXPECT_EQ(65u, A.count());818 819 A.resize(96);820 EXPECT_EQ(65u, A.count());821 822 A.clear();823 A.resize(128);824 A.setBitsNotInMask(Mask1, 3);825 EXPECT_EQ(96u-5u, A.count());826 827 A.clearBitsNotInMask(Mask1, 1);828 EXPECT_EQ(64-4u, A.count());829}830 831TYPED_TEST(BitVectorTest, BinOps) {832 TypeParam A;833 TypeParam B;834 835 A.resize(65);836 EXPECT_FALSE(A.anyCommon(B));837 EXPECT_FALSE(B.anyCommon(B));838 839 B.resize(64);840 A.set(64);841 EXPECT_FALSE(A.anyCommon(B));842 EXPECT_FALSE(B.anyCommon(A));843 844 B.set(63);845 EXPECT_FALSE(A.anyCommon(B));846 EXPECT_FALSE(B.anyCommon(A));847 848 A.set(63);849 EXPECT_TRUE(A.anyCommon(B));850 EXPECT_TRUE(B.anyCommon(A));851 852 B.resize(70);853 B.set(64);854 B.reset(63);855 A.resize(64);856 EXPECT_FALSE(A.anyCommon(B));857 EXPECT_FALSE(B.anyCommon(A));858}859 860using RangeList = std::vector<std::pair<int, int>>;861 862template <typename VecType>863static inline VecType createBitVector(uint32_t Size,864 const RangeList &setRanges) {865 VecType V;866 V.resize(Size);867 for (auto &R : setRanges)868 V.set(R.first, R.second);869 return V;870}871 872TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) {873 // Test that shift ops work when the desired shift amount is less874 // than one word.875 876 // 1. Case where the number of bits in the BitVector also fit into a single877 // word.878 TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}});879 TypeParam B = A;880 881 EXPECT_EQ(4U, A.count());882 EXPECT_TRUE(A.test(2));883 EXPECT_TRUE(A.test(3));884 EXPECT_TRUE(A.test(8));885 EXPECT_TRUE(A.test(9));886 887 A >>= 1;888 EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A);889 890 A <<= 1;891 EXPECT_EQ(B, A);892 893 A >>= 10;894 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);895 896 A = B;897 A <<= 10;898 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);899 900 // 2. Case where the number of bits in the BitVector do not fit into a single901 // word.902 903 // 31----------------------------------------------------------------------0904 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111905 A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}});906 EXPECT_EQ(40U, A.size());907 EXPECT_EQ(22U, A.count());908 909 // 2a. Make sure that left shifting some 1 bits out of the vector works.910 // 31----------------------------------------------------------------------0911 // Before:912 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111913 // After:914 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000915 A <<= 9;916 EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A);917 918 // 2b. Make sure that keeping the number of one bits unchanged works.919 // 31----------------------------------------------------------------------0920 // Before:921 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000922 // After:923 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000924 A >>= 6;925 EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A);926 927 // 2c. Make sure that right shifting some 1 bits out of the vector works.928 // 31----------------------------------------------------------------------0929 // Before:930 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000931 // After:932 // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111933 A >>= 10;934 EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A);935 936 // 3. Big test.937 A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});938 A <<= 29;939 EXPECT_EQ(createBitVector<TypeParam>(940 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}),941 A);942}943 944TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) {945 // Test that shift ops work when the desired shift amount is greater than or946 // equal to the size of a single word.947 auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});948 949 // Make a copy so we can re-use it later.950 auto B = A;951 952 // 1. Shift left by an exact multiple of the word size. This should invoke953 // only a memmove and no per-word bit operations.954 A <<= 64;955 auto Expected = createBitVector<TypeParam>(956 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}});957 EXPECT_EQ(Expected, A);958 959 // 2. Shift left by a non multiple of the word size. This should invoke both960 // a memmove and per-word bit operations.961 A = B;962 A <<= 93;963 EXPECT_EQ(createBitVector<TypeParam>(964 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}),965 A);966 967 // 1. Shift right by an exact multiple of the word size. This should invoke968 // only a memmove and no per-word bit operations.969 A = B;970 A >>= 64;971 EXPECT_EQ(972 createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A);973 974 // 2. Shift left by a non multiple of the word size. This should invoke both975 // a memmove and per-word bit operations.976 A = B;977 A >>= 93;978 EXPECT_EQ(979 createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A);980}981 982TYPED_TEST(BitVectorTest, RangeOps) {983 TypeParam A;984 A.resize(256);985 A.reset();986 A.set(1, 255);987 988 EXPECT_FALSE(A.test(0));989 EXPECT_TRUE( A.test(1));990 EXPECT_TRUE( A.test(23));991 EXPECT_TRUE( A.test(254));992 EXPECT_FALSE(A.test(255));993 994 TypeParam B;995 B.resize(256);996 B.set();997 B.reset(1, 255);998 999 EXPECT_TRUE( B.test(0));1000 EXPECT_FALSE(B.test(1));1001 EXPECT_FALSE(B.test(23));1002 EXPECT_FALSE(B.test(254));1003 EXPECT_TRUE( B.test(255));1004 1005 TypeParam C;1006 C.resize(3);1007 C.reset();1008 C.set(0, 1);1009 1010 EXPECT_TRUE(C.test(0));1011 EXPECT_FALSE( C.test(1));1012 EXPECT_FALSE( C.test(2));1013 1014 TypeParam D;1015 D.resize(3);1016 D.set();1017 D.reset(0, 1);1018 1019 EXPECT_FALSE(D.test(0));1020 EXPECT_TRUE( D.test(1));1021 EXPECT_TRUE( D.test(2));1022 1023 TypeParam E;1024 E.resize(128);1025 E.reset();1026 E.set(1, 33);1027 1028 EXPECT_FALSE(E.test(0));1029 EXPECT_TRUE( E.test(1));1030 EXPECT_TRUE( E.test(32));1031 EXPECT_FALSE(E.test(33));1032 1033 TypeParam BufferOverrun;1034 unsigned size = sizeof(unsigned long) * 8;1035 BufferOverrun.resize(size);1036 BufferOverrun.reset(0, size);1037 BufferOverrun.set(0, size);1038}1039 1040TYPED_TEST(BitVectorTest, CompoundTestReset) {1041 TypeParam A(50, true);1042 TypeParam B(50, false);1043 1044 TypeParam C(100, true);1045 TypeParam D(100, false);1046 1047 EXPECT_FALSE(A.test(A));1048 EXPECT_TRUE(A.test(B));1049 EXPECT_FALSE(A.test(C));1050 EXPECT_TRUE(A.test(D));1051 EXPECT_FALSE(B.test(A));1052 EXPECT_FALSE(B.test(B));1053 EXPECT_FALSE(B.test(C));1054 EXPECT_FALSE(B.test(D));1055 EXPECT_TRUE(C.test(A));1056 EXPECT_TRUE(C.test(B));1057 EXPECT_FALSE(C.test(C));1058 EXPECT_TRUE(C.test(D));1059 1060 A.reset(B);1061 A.reset(D);1062 EXPECT_TRUE(A.all());1063 A.reset(A);1064 EXPECT_TRUE(A.none());1065 A.set();1066 A.reset(C);1067 EXPECT_TRUE(A.none());1068 A.set();1069 1070 C.reset(A);1071 EXPECT_EQ(50, C.find_first());1072 C.reset(C);1073 EXPECT_TRUE(C.none());1074}1075 1076TYPED_TEST(BitVectorTest, MoveConstructor) {1077 TypeParam A(10, true);1078 TypeParam B(std::move(A));1079 // Check that the move ctor leaves the moved-from object in a valid state.1080 // The following line used to crash.1081 A = B;1082 1083 TypeParam C(10, true);1084 EXPECT_EQ(C, A);1085 EXPECT_EQ(C, B);1086}1087 1088TYPED_TEST(BitVectorTest, MoveAssignment) {1089 TypeParam A(10, true);1090 TypeParam B;1091 B = std::move(A);1092 // Check that move assignment leaves the moved-from object in a valid state.1093 // The following line used to crash.1094 A = B;1095 1096 TypeParam C(10, true);1097 EXPECT_EQ(C, A);1098 EXPECT_EQ(C, B);1099}1100 1101template<class TypeParam>1102static void testEmpty(const TypeParam &A) {1103 EXPECT_TRUE(A.empty());1104 EXPECT_EQ((size_t)0, A.size());1105 EXPECT_EQ((size_t)0, A.count());1106 EXPECT_FALSE(A.any());1107 EXPECT_TRUE(A.all());1108 EXPECT_TRUE(A.none());1109 EXPECT_EQ(-1, A.find_first());1110 EXPECT_EQ(A, TypeParam());1111}1112 1113/// Tests whether BitVector behaves well with Bits==nullptr, Capacity==01114TYPED_TEST(BitVectorTest, EmptyVector) {1115 TypeParam A;1116 testEmpty(A);1117 1118 TypeParam B;1119 B.reset();1120 testEmpty(B);1121 1122 TypeParam C;1123 C.clear();1124 testEmpty(C);1125 1126 TypeParam D(A);1127 testEmpty(D);1128 1129 TypeParam E;1130 E = A;1131 testEmpty(E);1132 1133 TypeParam F;1134 E.reset(A);1135 testEmpty(E);1136}1137 1138/// Make sure calling getData() is legal even on an empty BitVector1139TYPED_TEST(BitVectorTest, EmptyVectorGetData) {1140 BitVector A;1141 testEmpty(A);1142 auto B = A.getData();1143 EXPECT_TRUE(B.empty());1144}1145 1146TYPED_TEST(BitVectorTest, Iterators) {1147 TypeParam Singleton(1, true);1148 EXPECT_EQ(std::next(Singleton.set_bits_begin()), Singleton.set_bits_end());1149 1150 TypeParam Filled(10, true);1151 EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end());1152 unsigned Counter = 0;1153 for (unsigned Bit : Filled.set_bits())1154 EXPECT_EQ(Bit, Counter++);1155 1156 TypeParam Empty;1157 EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end());1158 int BitCount = 0;1159 for (unsigned Bit : Empty.set_bits()) {1160 (void)Bit;1161 BitCount++;1162 }1163 ASSERT_EQ(BitCount, 0);1164 1165 TypeParam ToFill(100, false);1166 ToFill.set(0);1167 EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end());1168 EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end());1169 EXPECT_EQ(*ToFill.set_bits_begin(), 0U);1170 ToFill.reset(0);1171 EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end());1172 1173 const unsigned List[] = {1, 10, 25, 99};1174 for (unsigned Num : List)1175 ToFill.set(Num);1176 unsigned i = 0;1177 for (unsigned Bit : ToFill.set_bits())1178 EXPECT_EQ(List[i++], Bit);1179}1180 1181TYPED_TEST(BitVectorTest, BidirectionalIterator) {1182 // Test decrement operators.1183 TypeParam Vec(100, false);1184 Vec.set(10);1185 Vec.set(20);1186 Vec.set(30);1187 Vec.set(40);1188 1189 // Test that we can decrement from end().1190 auto EndIt = Vec.set_bits_end();1191 auto LastIt = EndIt;1192 --LastIt;1193 EXPECT_EQ(*LastIt, 40U);1194 1195 // Test post-decrement.1196 auto It = Vec.set_bits_end();1197 auto PrevIt = It--;1198 EXPECT_EQ(PrevIt, Vec.set_bits_end());1199 EXPECT_EQ(*It, 40U);1200 1201 // Test pre-decrement.1202 --It;1203 EXPECT_EQ(*It, 30U);1204 1205 // Test full backward iteration.1206 std::vector<unsigned> BackwardBits;1207 for (auto RIt = Vec.set_bits_end(); RIt != Vec.set_bits_begin();) {1208 --RIt;1209 BackwardBits.push_back(*RIt);1210 }1211 EXPECT_EQ(BackwardBits.size(), 4U);1212 EXPECT_EQ(BackwardBits[0], 40U);1213 EXPECT_EQ(BackwardBits[1], 30U);1214 EXPECT_EQ(BackwardBits[2], 20U);1215 EXPECT_EQ(BackwardBits[3], 10U);1216}1217 1218TYPED_TEST(BitVectorTest, ReverseIteration) {1219 // Test using llvm::reverse.1220 TypeParam Vec(100, false);1221 Vec.set(5);1222 Vec.set(15);1223 Vec.set(25);1224 Vec.set(35);1225 Vec.set(45);1226 1227 std::vector<unsigned> ReversedBits;1228 for (unsigned Bit : llvm::reverse(Vec.set_bits())) {1229 ReversedBits.push_back(Bit);1230 }1231 1232 EXPECT_EQ(ReversedBits.size(), 5U);1233 EXPECT_EQ(ReversedBits[0], 45U);1234 EXPECT_EQ(ReversedBits[1], 35U);1235 EXPECT_EQ(ReversedBits[2], 25U);1236 EXPECT_EQ(ReversedBits[3], 15U);1237 EXPECT_EQ(ReversedBits[4], 5U);1238}1239 1240TYPED_TEST(BitVectorTest, BidirectionalIteratorEdgeCases) {1241 // Test empty BitVector.1242 TypeParam Empty;1243 EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end());1244 1245 // Decrementing end() on empty should give -1 (no bits set).1246 auto EmptyEndIt = Empty.set_bits_end();1247 --EmptyEndIt;1248 // After decrement on empty, iterator should still be at "no bit" position.1249 EXPECT_EQ(*EmptyEndIt, static_cast<unsigned>(-1));1250 1251 // Test single bit.1252 TypeParam Single(10, false);1253 Single.set(5);1254 1255 auto SingleIt = Single.set_bits_end();1256 --SingleIt;1257 EXPECT_EQ(*SingleIt, 5U);1258 // After decrementing past the first element, the iterator is in an1259 // undefined state (before begin), so we don't test this case.1260 1261 // Test all bits set.1262 TypeParam AllSet(10, true);1263 std::vector<unsigned> AllBitsReverse;1264 for (unsigned Bit : llvm::reverse(AllSet.set_bits())) {1265 AllBitsReverse.push_back(Bit);1266 }1267 EXPECT_EQ(AllBitsReverse.size(), 10U);1268 for (unsigned i = 0; i < 10; ++i) {1269 EXPECT_EQ(AllBitsReverse[i], 9 - i);1270 }1271}1272 1273TYPED_TEST(BitVectorTest, PushBack) {1274 TypeParam Vec(10, false);1275 EXPECT_EQ(-1, Vec.find_first());1276 EXPECT_EQ(10U, Vec.size());1277 EXPECT_EQ(0U, Vec.count());1278 EXPECT_EQ(false, Vec.back());1279 1280 Vec.push_back(true);1281 EXPECT_EQ(10, Vec.find_first());1282 EXPECT_EQ(11U, Vec.size());1283 EXPECT_EQ(1U, Vec.count());1284 EXPECT_EQ(true, Vec.back());1285 1286 Vec.push_back(false);1287 EXPECT_EQ(10, Vec.find_first());1288 EXPECT_EQ(12U, Vec.size());1289 EXPECT_EQ(1U, Vec.count());1290 EXPECT_EQ(false, Vec.back());1291 1292 Vec.push_back(true);1293 EXPECT_EQ(10, Vec.find_first());1294 EXPECT_EQ(13U, Vec.size());1295 EXPECT_EQ(2U, Vec.count());1296 EXPECT_EQ(true, Vec.back());1297 1298 // Add a lot of values to cause reallocation.1299 for (int i = 0; i != 100; ++i) {1300 Vec.push_back(true);1301 Vec.push_back(false);1302 }1303 EXPECT_EQ(10, Vec.find_first());1304 EXPECT_EQ(213U, Vec.size());1305 EXPECT_EQ(102U, Vec.count());1306}1307 1308TYPED_TEST(BitVectorTest, PopBack) {1309 TypeParam Vec(10, true);1310 EXPECT_EQ(10U, Vec.size());1311 EXPECT_EQ(10U, Vec.count());1312 EXPECT_EQ(true, Vec.back());1313 1314 Vec.pop_back();1315 EXPECT_EQ(9U, Vec.size());1316 EXPECT_EQ(9U, Vec.count());1317 EXPECT_EQ(true, Vec.back());1318 1319 Vec.push_back(false);1320 EXPECT_EQ(10U, Vec.size());1321 EXPECT_EQ(9U, Vec.count());1322 EXPECT_EQ(false, Vec.back());1323 1324 Vec.pop_back();1325 EXPECT_EQ(9U, Vec.size());1326 EXPECT_EQ(9U, Vec.count());1327 EXPECT_EQ(true, Vec.back());1328}1329 1330TYPED_TEST(BitVectorTest, DenseSet) {1331 DenseSet<TypeParam> Set;1332 TypeParam A(10, true);1333 auto I = Set.insert(A);1334 EXPECT_EQ(true, I.second);1335 1336 TypeParam B(5, true);1337 I = Set.insert(B);1338 EXPECT_EQ(true, I.second);1339 1340 TypeParam C(20, false);1341 C.set(19);1342 I = Set.insert(C);1343 EXPECT_EQ(true, I.second);1344 1345#if LLVM_ENABLE_ABI_BREAKING_CHECKS1346 TypeParam D;1347 EXPECT_DEATH(Set.insert(D),1348 "Empty/Tombstone value shouldn't be inserted into map!");1349#endif1350 1351 EXPECT_EQ(3U, Set.size());1352 EXPECT_EQ(1U, Set.count(A));1353 EXPECT_EQ(1U, Set.count(B));1354 EXPECT_EQ(1U, Set.count(C));1355 1356 EXPECT_EQ(true, Set.erase(B));1357 EXPECT_EQ(2U, Set.size());1358 1359 EXPECT_EQ(true, Set.erase(C));1360 EXPECT_EQ(1U, Set.size());1361 1362 EXPECT_EQ(true, Set.erase(A));1363 EXPECT_EQ(0U, Set.size());1364}1365 1366/// Test that capacity doesn't affect hashing.1367TYPED_TEST(BitVectorTest, DenseMapHashing) {1368 using DMI = DenseMapInfo<TypeParam>;1369 {1370 TypeParam A;1371 A.resize(200);1372 A.set(100);1373 1374 TypeParam B;1375 B.resize(200);1376 B.set(100);1377 B.reserve(1000);1378 1379 EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B));1380 }1381 {1382 TypeParam A;1383 A.resize(20);1384 A.set(10);1385 1386 TypeParam B;1387 B.resize(20);1388 B.set(10);1389 B.reserve(1000);1390 1391 EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B));1392 }1393}1394 1395TEST(BitVectoryTest, Apply) {1396 for (int i = 0; i < 2; ++i) {1397 int j = i * 100 + 3;1398 1399 const BitVector x =1400 createBitVector<BitVector>(j + 5, {{i, i + 1}, {j - 1, j}});1401 const BitVector y = createBitVector<BitVector>(j + 5, {{i, j}});1402 const BitVector z =1403 createBitVector<BitVector>(j + 5, {{i + 1, i + 2}, {j, j + 1}});1404 1405 auto op0 = [](auto x) { return ~x; };1406 BitVector expected0 = x;1407 expected0.flip();1408 BitVector out0(j - 2);1409 BitVector::apply(op0, out0, x);1410 EXPECT_EQ(out0, expected0);1411 1412 auto op1 = [](auto x, auto y) { return x & ~y; };1413 BitVector expected1 = x;1414 expected1.reset(y);1415 BitVector out1;1416 BitVector::apply(op1, out1, x, y);1417 EXPECT_EQ(out1, expected1);1418 1419 auto op2 = [](auto x, auto y, auto z) { return (x ^ ~y) | z; };1420 BitVector expected2 = y;1421 expected2.flip();1422 expected2 ^= x;1423 expected2 |= z;1424 BitVector out2(j + 5);1425 BitVector::apply(op2, out2, x, y, z);1426 EXPECT_EQ(out2, expected2);1427 }1428}1429 1430 1431} // namespace1432