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