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