unittests/ADT/BitVectorTest.cpp

   1 //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 // Some of these tests fail on PowerPC for unknown reasons.
  11 #ifndef __ppc__
  12
  13 #include "llvm/ADT/BitVector.h"
  14 #include "llvm/ADT/SmallBitVector.h"
  15 #include "gtest/gtest.h"
  16
  17 using namespace llvm;
  18
  19 namespace {
  20
  21 // Test fixture
  22 template <typename T>
  23 class BitVectorTest : public ::testing::Test { };
  24
  25 // Test both BitVector and SmallBitVector with the same suite of tests.
  26 typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes;
  27 TYPED_TEST_CASE(BitVectorTest, BitVectorTestTypes);
  28
  29 TYPED_TEST(BitVectorTest, TrivialOperation) {
  30   TypeParam Vec;
  31   EXPECT_EQ(0U, Vec.count());
  32   EXPECT_EQ(0U, Vec.size());
  33   EXPECT_FALSE(Vec.any());
  34   EXPECT_TRUE(Vec.all());
  35   EXPECT_TRUE(Vec.none());
  36   EXPECT_TRUE(Vec.empty());
  37
  38   Vec.resize(5, true);
  39   EXPECT_EQ(5U, Vec.count());
  40   EXPECT_EQ(5U, Vec.size());
  41   EXPECT_TRUE(Vec.any());
  42   EXPECT_TRUE(Vec.all());
  43   EXPECT_FALSE(Vec.none());
  44   EXPECT_FALSE(Vec.empty());
  45
  46   Vec.resize(11);
  47   EXPECT_EQ(5U, Vec.count());
  48   EXPECT_EQ(11U, Vec.size());
  49   EXPECT_TRUE(Vec.any());
  50   EXPECT_FALSE(Vec.all());
  51   EXPECT_FALSE(Vec.none());
  52   EXPECT_FALSE(Vec.empty());
  53
  54   TypeParam Inv = Vec;
  55   Inv.flip();
  56   EXPECT_EQ(6U, Inv.count());
  57   EXPECT_EQ(11U, Inv.size());
  58   EXPECT_TRUE(Inv.any());
  59   EXPECT_FALSE(Inv.all());
  60   EXPECT_FALSE(Inv.none());
  61   EXPECT_FALSE(Inv.empty());
  62
  63   EXPECT_FALSE(Inv == Vec);
  64   EXPECT_TRUE(Inv != Vec);
  65   Vec.flip();
  66   EXPECT_TRUE(Inv == Vec);
  67   EXPECT_FALSE(Inv != Vec);
  68
  69   // Add some "interesting" data to Vec.
  70   Vec.resize(23, true);
  71   Vec.resize(25, false);
  72   Vec.resize(26, true);
  73   Vec.resize(29, false);
  74   Vec.resize(33, true);
  75   Vec.resize(57, false);
  76   unsigned Count = 0;
  77   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
  78     ++Count;
  79     EXPECT_TRUE(Vec[i]);
  80     EXPECT_TRUE(Vec.test(i));
  81   }
  82   EXPECT_EQ(Count, Vec.count());
  83   EXPECT_EQ(Count, 23u);
  84   EXPECT_FALSE(Vec[0]);
  85   EXPECT_TRUE(Vec[32]);
  86   EXPECT_FALSE(Vec[56]);
  87   Vec.resize(61, false);
  88
  89   TypeParam Copy = Vec;
  90   TypeParam Alt(3, false);
  91   Alt.resize(6, true);
  92   std::swap(Alt, Vec);
  93   EXPECT_TRUE(Copy == Alt);
  94   EXPECT_TRUE(Vec.size() == 6);
  95   EXPECT_TRUE(Vec.count() == 3);
  96   EXPECT_TRUE(Vec.find_first() == 3);
  97   std::swap(Copy, Vec);
  98
  99   // Add some more "interesting" data.
 100   Vec.resize(68, true);
 101   Vec.resize(78, false);
 102   Vec.resize(89, true);
 103   Vec.resize(90, false);
 104   Vec.resize(91, true);
 105   Vec.resize(130, false);
 106   Count = 0;
 107   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
 108     ++Count;
 109     EXPECT_TRUE(Vec[i]);
 110     EXPECT_TRUE(Vec.test(i));
 111   }
 112   EXPECT_EQ(Count, Vec.count());
 113   EXPECT_EQ(Count, 42u);
 114   EXPECT_FALSE(Vec[0]);
 115   EXPECT_TRUE(Vec[32]);
 116   EXPECT_FALSE(Vec[60]);
 117   EXPECT_FALSE(Vec[129]);
 118
 119   Vec.flip(60);
 120   EXPECT_TRUE(Vec[60]);
 121   EXPECT_EQ(Count + 1, Vec.count());
 122   Vec.flip(60);
 123   EXPECT_FALSE(Vec[60]);
 124   EXPECT_EQ(Count, Vec.count());
 125
 126   Vec.reset(32);
 127   EXPECT_FALSE(Vec[32]);
 128   EXPECT_EQ(Count - 1, Vec.count());
 129   Vec.set(32);
 130   EXPECT_TRUE(Vec[32]);
 131   EXPECT_EQ(Count, Vec.count());
 132
 133   Vec.flip();
 134   EXPECT_EQ(Vec.size() - Count, Vec.count());
 135
 136   Vec.reset();
 137   EXPECT_EQ(0U, Vec.count());
 138   EXPECT_EQ(130U, Vec.size());
 139   EXPECT_FALSE(Vec.any());
 140   EXPECT_FALSE(Vec.all());
 141   EXPECT_TRUE(Vec.none());
 142   EXPECT_FALSE(Vec.empty());
 143
 144   Vec.flip();
 145   EXPECT_EQ(130U, Vec.count());
 146   EXPECT_EQ(130U, Vec.size());
 147   EXPECT_TRUE(Vec.any());
 148   EXPECT_TRUE(Vec.all());
 149   EXPECT_FALSE(Vec.none());
 150   EXPECT_FALSE(Vec.empty());
 151
 152   Vec.resize(64);
 153   EXPECT_EQ(64U, Vec.count());
 154   EXPECT_EQ(64U, Vec.size());
 155   EXPECT_TRUE(Vec.any());
 156   EXPECT_TRUE(Vec.all());
 157   EXPECT_FALSE(Vec.none());
 158   EXPECT_FALSE(Vec.empty());
 159
 160   Vec.flip();
 161   EXPECT_EQ(0U, Vec.count());
 162   EXPECT_EQ(64U, Vec.size());
 163   EXPECT_FALSE(Vec.any());
 164   EXPECT_FALSE(Vec.all());
 165   EXPECT_TRUE(Vec.none());
 166   EXPECT_FALSE(Vec.empty());
 167
 168   Inv = TypeParam().flip();
 169   EXPECT_EQ(0U, Inv.count());
 170   EXPECT_EQ(0U, Inv.size());
 171   EXPECT_FALSE(Inv.any());
 172   EXPECT_TRUE(Inv.all());
 173   EXPECT_TRUE(Inv.none());
 174   EXPECT_TRUE(Inv.empty());
 175
 176   Vec.clear();
 177   EXPECT_EQ(0U, Vec.count());
 178   EXPECT_EQ(0U, Vec.size());
 179   EXPECT_FALSE(Vec.any());
 180   EXPECT_TRUE(Vec.all());
 181   EXPECT_TRUE(Vec.none());
 182   EXPECT_TRUE(Vec.empty());
 183 }
 184
 185 TYPED_TEST(BitVectorTest, SimpleFindOps) {
 186   // Test finding in an empty BitVector.
 187   TypeParam A;
 188   EXPECT_EQ(-1, A.find_first());
 189   EXPECT_EQ(-1, A.find_last());
 190   EXPECT_EQ(-1, A.find_first_unset());
 191   EXPECT_EQ(-1, A.find_last_unset());
 192
 193   // Test finding next set and unset bits in a BitVector with multiple words
 194   A.resize(100);
 195   A.set(12);
 196   A.set(13);
 197   A.set(75);
 198
 199   EXPECT_EQ(75, A.find_last());
 200   EXPECT_EQ(12, A.find_first());
 201   EXPECT_EQ(13, A.find_next(12));
 202   EXPECT_EQ(75, A.find_next(13));
 203   EXPECT_EQ(-1, A.find_next(75));
 204
 205   EXPECT_EQ(-1, A.find_prev(12));
 206   EXPECT_EQ(12, A.find_prev(13));
 207   EXPECT_EQ(13, A.find_prev(75));
 208   EXPECT_EQ(75, A.find_prev(90));
 209
 210   EXPECT_EQ(0, A.find_first_unset());
 211   EXPECT_EQ(99, A.find_last_unset());
 212   EXPECT_EQ(14, A.find_next_unset(11));
 213   EXPECT_EQ(14, A.find_next_unset(12));
 214   EXPECT_EQ(14, A.find_next_unset(13));
 215   EXPECT_EQ(16, A.find_next_unset(15));
 216   EXPECT_EQ(76, A.find_next_unset(74));
 217   EXPECT_EQ(76, A.find_next_unset(75));
 218   EXPECT_EQ(-1, A.find_next_unset(99));
 219
 220   A.set(0, 100);
 221   EXPECT_EQ(100U, A.count());
 222   EXPECT_EQ(0, A.find_first());
 223   EXPECT_EQ(-1, A.find_first_unset());
 224   EXPECT_EQ(-1, A.find_last_unset());
 225   EXPECT_EQ(99, A.find_last());
 226   EXPECT_EQ(99, A.find_next(98));
 227
 228   A.reset(0, 100);
 229   EXPECT_EQ(0U, A.count());
 230   EXPECT_EQ(-1, A.find_first());
 231   EXPECT_EQ(-1, A.find_last());
 232   EXPECT_EQ(0, A.find_first_unset());
 233   EXPECT_EQ(99, A.find_last_unset());
 234   EXPECT_EQ(99, A.find_next_unset(98));
 235
 236   // Also test with a vector that is small enough to fit in 1 word.
 237   A.resize(20);
 238   A.set(3);
 239   A.set(4);
 240   A.set(16);
 241   EXPECT_EQ(16, A.find_last());
 242   EXPECT_EQ(3, A.find_first());
 243   EXPECT_EQ(3, A.find_next(1));
 244   EXPECT_EQ(4, A.find_next(3));
 245   EXPECT_EQ(16, A.find_next(4));
 246   EXPECT_EQ(-1, A.find_next(16));
 247
 248   EXPECT_EQ(-1, A.find_prev(3));
 249   EXPECT_EQ(3, A.find_prev(4));
 250   EXPECT_EQ(4, A.find_prev(16));
 251   EXPECT_EQ(16, A.find_prev(18));
 252
 253   EXPECT_EQ(0, A.find_first_unset());
 254   EXPECT_EQ(19, A.find_last_unset());
 255   EXPECT_EQ(5, A.find_next_unset(3));
 256   EXPECT_EQ(5, A.find_next_unset(4));
 257   EXPECT_EQ(13, A.find_next_unset(12));
 258   EXPECT_EQ(17, A.find_next_unset(15));
 259 }
 260
 261 TEST(BitVectorTest, FindInRangeMultiWord) {
 262   BitVector Vec;
 263
 264   Vec.resize(200);
 265   Vec.set(3, 7);
 266   Vec.set(24, 35);
 267   Vec.set(50, 70);
 268   Vec.set(150);
 269   Vec.set(152);
 270   Vec.set(154);
 271
 272   // find first
 273   EXPECT_EQ(-1, Vec.find_first_in(0, 0));
 274   EXPECT_EQ(-1, Vec.find_first_in(24, 24));
 275   EXPECT_EQ(-1, Vec.find_first_in(7, 24));
 276
 277   EXPECT_EQ(3, Vec.find_first_in(0, 10));
 278   EXPECT_EQ(4, Vec.find_first_in(4, 10));
 279   EXPECT_EQ(150, Vec.find_first_in(100, 200));
 280   EXPECT_EQ(152, Vec.find_first_in(151, 200));
 281   EXPECT_EQ(154, Vec.find_first_in(153, 200));
 282
 283   EXPECT_EQ(-1, Vec.find_first_in(155, 200));
 284   Vec.set(199);
 285   EXPECT_EQ(199, Vec.find_first_in(199, 200));
 286   Vec.reset(199);
 287
 288   // find last
 289   EXPECT_EQ(-1, Vec.find_last_in(0, 0));
 290   EXPECT_EQ(-1, Vec.find_last_in(24, 24));
 291   EXPECT_EQ(-1, Vec.find_last_in(7, 24));
 292
 293   EXPECT_EQ(6, Vec.find_last_in(0, 10));
 294   EXPECT_EQ(5, Vec.find_last_in(0, 6));
 295   EXPECT_EQ(154, Vec.find_last_in(100, 155));
 296   EXPECT_EQ(152, Vec.find_last_in(100, 154));
 297   EXPECT_EQ(150, Vec.find_last_in(100, 152));
 298   EXPECT_EQ(-1, Vec.find_last_in(100, 150));
 299   Vec.set(199);
 300   EXPECT_EQ(199, Vec.find_last_in(199, 200));
 301   Vec.reset(199);
 302
 303   // find first unset
 304   EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
 305   EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
 306   EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35));
 307
 308   EXPECT_EQ(0, Vec.find_first_unset_in(0, 10));
 309   EXPECT_EQ(1, Vec.find_first_unset_in(1, 10));
 310   EXPECT_EQ(7, Vec.find_first_unset_in(5, 25));
 311   EXPECT_EQ(151, Vec.find_first_unset_in(150, 200));
 312   EXPECT_EQ(151, Vec.find_first_unset_in(151, 200));
 313   EXPECT_EQ(153, Vec.find_first_unset_in(152, 200));
 314   EXPECT_EQ(153, Vec.find_first_unset_in(153, 200));
 315   EXPECT_EQ(155, Vec.find_first_unset_in(154, 200));
 316   EXPECT_EQ(155, Vec.find_first_unset_in(155, 200));
 317   EXPECT_EQ(199, Vec.find_first_unset_in(199, 200));
 318
 319   // find last unset
 320   EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
 321   EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
 322   EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35));
 323
 324   EXPECT_EQ(9, Vec.find_last_unset_in(0, 10));
 325   EXPECT_EQ(8, Vec.find_last_unset_in(0, 9));
 326   EXPECT_EQ(2, Vec.find_last_unset_in(0, 7));
 327   EXPECT_EQ(149, Vec.find_last_unset_in(100, 151));
 328   EXPECT_EQ(151, Vec.find_last_unset_in(100, 152));
 329   EXPECT_EQ(151, Vec.find_last_unset_in(100, 153));
 330   EXPECT_EQ(153, Vec.find_last_unset_in(100, 154));
 331   EXPECT_EQ(153, Vec.find_last_unset_in(100, 155));
 332   EXPECT_EQ(155, Vec.find_last_unset_in(100, 156));
 333   EXPECT_EQ(199, Vec.find_last_unset_in(199, 200));
 334 }
 335
 336 TEST(BitVectorTest, FindInRangeSingleWord) {
 337   // When the bit vector contains only a single word, this is slightly different
 338   // than when the bit vector contains multiple words, because masks are applied
 339   // to the front and back of the same word.  So make sure this works.
 340   BitVector Vec;
 341
 342   Vec.resize(25);
 343   Vec.set(2, 4);
 344   Vec.set(6, 9);
 345   Vec.set(12, 15);
 346   Vec.set(19);
 347   Vec.set(21);
 348   Vec.set(23);
 349
 350   // find first
 351   EXPECT_EQ(-1, Vec.find_first_in(0, 0));
 352   EXPECT_EQ(-1, Vec.find_first_in(24, 24));
 353   EXPECT_EQ(-1, Vec.find_first_in(9, 12));
 354
 355   EXPECT_EQ(2, Vec.find_first_in(0, 10));
 356   EXPECT_EQ(6, Vec.find_first_in(4, 10));
 357   EXPECT_EQ(19, Vec.find_first_in(18, 25));
 358   EXPECT_EQ(21, Vec.find_first_in(20, 25));
 359   EXPECT_EQ(23, Vec.find_first_in(22, 25));
 360   EXPECT_EQ(-1, Vec.find_first_in(24, 25));
 361
 362   // find last
 363   EXPECT_EQ(-1, Vec.find_last_in(0, 0));
 364   EXPECT_EQ(-1, Vec.find_last_in(24, 24));
 365   EXPECT_EQ(-1, Vec.find_last_in(9, 12));
 366
 367   EXPECT_EQ(8, Vec.find_last_in(0, 10));
 368   EXPECT_EQ(3, Vec.find_last_in(0, 6));
 369   EXPECT_EQ(23, Vec.find_last_in(18, 25));
 370   EXPECT_EQ(21, Vec.find_last_in(18, 23));
 371   EXPECT_EQ(19, Vec.find_last_in(18, 21));
 372   EXPECT_EQ(-1, Vec.find_last_in(18, 19));
 373
 374   // find first unset
 375   EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
 376   EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
 377   EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9));
 378
 379   EXPECT_EQ(0, Vec.find_first_unset_in(0, 6));
 380   EXPECT_EQ(1, Vec.find_first_unset_in(1, 6));
 381   EXPECT_EQ(9, Vec.find_first_unset_in(7, 13));
 382   EXPECT_EQ(18, Vec.find_first_unset_in(18, 25));
 383   EXPECT_EQ(20, Vec.find_first_unset_in(19, 25));
 384   EXPECT_EQ(20, Vec.find_first_unset_in(20, 25));
 385   EXPECT_EQ(22, Vec.find_first_unset_in(21, 25));
 386   EXPECT_EQ(22, Vec.find_first_unset_in(22, 25));
 387   EXPECT_EQ(24, Vec.find_first_unset_in(23, 25));
 388   EXPECT_EQ(24, Vec.find_first_unset_in(24, 25));
 389
 390   // find last unset
 391   EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
 392   EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
 393   EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9));
 394
 395   EXPECT_EQ(5, Vec.find_last_unset_in(0, 6));
 396   EXPECT_EQ(4, Vec.find_last_unset_in(0, 5));
 397   EXPECT_EQ(1, Vec.find_last_unset_in(0, 4));
 398   EXPECT_EQ(11, Vec.find_last_unset_in(7, 13));
 399   EXPECT_EQ(24, Vec.find_last_unset_in(18, 25));
 400   EXPECT_EQ(22, Vec.find_last_unset_in(18, 24));
 401   EXPECT_EQ(22, Vec.find_last_unset_in(18, 23));
 402   EXPECT_EQ(20, Vec.find_last_unset_in(18, 22));
 403   EXPECT_EQ(20, Vec.find_last_unset_in(18, 21));
 404   EXPECT_EQ(18, Vec.find_last_unset_in(18, 20));
 405   EXPECT_EQ(18, Vec.find_last_unset_in(18, 19));
 406 }
 407
 408 TYPED_TEST(BitVectorTest, CompoundAssignment) {
 409   TypeParam A;
 410   A.resize(10);
 411   A.set(4);
 412   A.set(7);
 413
 414   TypeParam B;
 415   B.resize(50);
 416   B.set(5);
 417   B.set(18);
 418
 419   A |= B;
 420   EXPECT_TRUE(A.test(4));
 421   EXPECT_TRUE(A.test(5));
 422   EXPECT_TRUE(A.test(7));
 423   EXPECT_TRUE(A.test(18));
 424   EXPECT_EQ(4U, A.count());
 425   EXPECT_EQ(50U, A.size());
 426
 427   B.resize(10);
 428   B.set();
 429   B.reset(2);
 430   B.reset(7);
 431   A &= B;
 432   EXPECT_FALSE(A.test(2));
 433   EXPECT_FALSE(A.test(7));
 434   EXPECT_EQ(2U, A.count());
 435   EXPECT_EQ(50U, A.size());
 436
 437   B.resize(100);
 438   B.set();
 439
 440   A ^= B;
 441   EXPECT_TRUE(A.test(2));
 442   EXPECT_TRUE(A.test(7));
 443   EXPECT_EQ(98U, A.count());
 444   EXPECT_EQ(100U, A.size());
 445 }
 446
 447 TYPED_TEST(BitVectorTest, ProxyIndex) {
 448   TypeParam Vec(3);
 449   EXPECT_TRUE(Vec.none());
 450   Vec[0] = Vec[1] = Vec[2] = true;
 451   EXPECT_EQ(Vec.size(), Vec.count());
 452   Vec[2] = Vec[1] = Vec[0] = false;
 453   EXPECT_TRUE(Vec.none());
 454 }
 455
 456 TYPED_TEST(BitVectorTest, PortableBitMask) {
 457   TypeParam A;
 458   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
 459
 460   A.resize(10);
 461   A.setBitsInMask(Mask1, 1);
 462   EXPECT_EQ(10u, A.size());
 463   EXPECT_FALSE(A.test(0));
 464
 465   A.resize(32);
 466   A.setBitsInMask(Mask1, 1);
 467   EXPECT_FALSE(A.test(0));
 468   EXPECT_TRUE(A.test(31));
 469   EXPECT_EQ(1u, A.count());
 470
 471   A.resize(33);
 472   A.setBitsInMask(Mask1, 1);
 473   EXPECT_EQ(1u, A.count());
 474   A.setBitsInMask(Mask1, 2);
 475   EXPECT_EQ(1u, A.count());
 476
 477   A.resize(34);
 478   A.setBitsInMask(Mask1, 2);
 479   EXPECT_EQ(2u, A.count());
 480
 481   A.resize(65);
 482   A.setBitsInMask(Mask1, 3);
 483   EXPECT_EQ(4u, A.count());
 484
 485   A.setBitsNotInMask(Mask1, 1);
 486   EXPECT_EQ(32u+3u, A.count());
 487
 488   A.setBitsNotInMask(Mask1, 3);
 489   EXPECT_EQ(65u, A.count());
 490
 491   A.resize(96);
 492   EXPECT_EQ(65u, A.count());
 493
 494   A.clear();
 495   A.resize(128);
 496   A.setBitsNotInMask(Mask1, 3);
 497   EXPECT_EQ(96u-5u, A.count());
 498
 499   A.clearBitsNotInMask(Mask1, 1);
 500   EXPECT_EQ(64-4u, A.count());
 501 }
 502
 503 TYPED_TEST(BitVectorTest, BinOps) {
 504   TypeParam A;
 505   TypeParam B;
 506
 507   A.resize(65);
 508   EXPECT_FALSE(A.anyCommon(B));
 509   EXPECT_FALSE(B.anyCommon(B));
 510
 511   B.resize(64);
 512   A.set(64);
 513   EXPECT_FALSE(A.anyCommon(B));
 514   EXPECT_FALSE(B.anyCommon(A));
 515
 516   B.set(63);
 517   EXPECT_FALSE(A.anyCommon(B));
 518   EXPECT_FALSE(B.anyCommon(A));
 519
 520   A.set(63);
 521   EXPECT_TRUE(A.anyCommon(B));
 522   EXPECT_TRUE(B.anyCommon(A));
 523
 524   B.resize(70);
 525   B.set(64);
 526   B.reset(63);
 527   A.resize(64);
 528   EXPECT_FALSE(A.anyCommon(B));
 529   EXPECT_FALSE(B.anyCommon(A));
 530 }
 531
 532 typedef std::vector<std::pair<int, int>> RangeList;
 533
 534 template <typename VecType>
 535 static inline VecType createBitVector(uint32_t Size,
 536                                       const RangeList &setRanges) {
 537   VecType V;
 538   V.resize(Size);
 539   for (auto &R : setRanges)
 540     V.set(R.first, R.second);
 541   return V;
 542 }
 543
 544 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) {
 545   // Test that shift ops work when the desired shift amount is less
 546   // than one word.
 547
 548   // 1. Case where the number of bits in the BitVector also fit into a single
 549   // word.
 550   TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}});
 551   TypeParam B = A;
 552
 553   EXPECT_EQ(4U, A.count());
 554   EXPECT_TRUE(A.test(2));
 555   EXPECT_TRUE(A.test(3));
 556   EXPECT_TRUE(A.test(8));
 557   EXPECT_TRUE(A.test(9));
 558
 559   A >>= 1;
 560   EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A);
 561
 562   A <<= 1;
 563   EXPECT_EQ(B, A);
 564
 565   A >>= 10;
 566   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
 567
 568   A = B;
 569   A <<= 10;
 570   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
 571
 572   // 2. Case where the number of bits in the BitVector do not fit into a single
 573   // word.
 574
 575   // 31----------------------------------------------------------------------0
 576   // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
 577   A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}});
 578   EXPECT_EQ(40U, A.size());
 579   EXPECT_EQ(22U, A.count());
 580
 581   // 2a. Make sure that left shifting some 1 bits out of the vector works.
 582   //   31----------------------------------------------------------------------0
 583   // Before:
 584   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
 585   // After:
 586   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
 587   A <<= 9;
 588   EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A);
 589
 590   // 2b. Make sure that keeping the number of one bits unchanged works.
 591   //   31----------------------------------------------------------------------0
 592   // Before:
 593   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
 594   // After:
 595   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
 596   A >>= 6;
 597   EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A);
 598
 599   // 2c. Make sure that right shifting some 1 bits out of the vector works.
 600   //   31----------------------------------------------------------------------0
 601   // Before:
 602   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
 603   // After:
 604   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111
 605   A >>= 10;
 606   EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A);
 607
 608   // 3. Big test.
 609   A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
 610   A <<= 29;
 611   EXPECT_EQ(createBitVector<TypeParam>(
 612                 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}),
 613             A);
 614 }
 615
 616 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) {
 617   // Test that shift ops work when the desired shift amount is greater than or
 618   // equal to the size of a single word.
 619   auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
 620
 621   // Make a copy so we can re-use it later.
 622   auto B = A;
 623
 624   // 1. Shift left by an exact multiple of the word size.  This should invoke
 625   // only a memmove and no per-word bit operations.
 626   A <<= 64;
 627   auto Expected = createBitVector<TypeParam>(
 628       300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}});
 629   EXPECT_EQ(Expected, A);
 630
 631   // 2. Shift left by a non multiple of the word size.  This should invoke both
 632   // a memmove and per-word bit operations.
 633   A = B;
 634   A <<= 93;
 635   EXPECT_EQ(createBitVector<TypeParam>(
 636                 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}),
 637             A);
 638
 639   // 1. Shift right by an exact multiple of the word size.  This should invoke
 640   // only a memmove and no per-word bit operations.
 641   A = B;
 642   A >>= 64;
 643   EXPECT_EQ(
 644       createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A);
 645
 646   // 2. Shift left by a non multiple of the word size.  This should invoke both
 647   // a memmove and per-word bit operations.
 648   A = B;
 649   A >>= 93;
 650   EXPECT_EQ(
 651       createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A);
 652 }
 653
 654 TYPED_TEST(BitVectorTest, RangeOps) {
 655   TypeParam A;
 656   A.resize(256);
 657   A.reset();
 658   A.set(1, 255);
 659
 660   EXPECT_FALSE(A.test(0));
 661   EXPECT_TRUE( A.test(1));
 662   EXPECT_TRUE( A.test(23));
 663   EXPECT_TRUE( A.test(254));
 664   EXPECT_FALSE(A.test(255));
 665
 666   TypeParam B;
 667   B.resize(256);
 668   B.set();
 669   B.reset(1, 255);
 670
 671   EXPECT_TRUE( B.test(0));
 672   EXPECT_FALSE(B.test(1));
 673   EXPECT_FALSE(B.test(23));
 674   EXPECT_FALSE(B.test(254));
 675   EXPECT_TRUE( B.test(255));
 676
 677   TypeParam C;
 678   C.resize(3);
 679   C.reset();
 680   C.set(0, 1);
 681
 682   EXPECT_TRUE(C.test(0));
 683   EXPECT_FALSE( C.test(1));
 684   EXPECT_FALSE( C.test(2));
 685
 686   TypeParam D;
 687   D.resize(3);
 688   D.set();
 689   D.reset(0, 1);
 690
 691   EXPECT_FALSE(D.test(0));
 692   EXPECT_TRUE( D.test(1));
 693   EXPECT_TRUE( D.test(2));
 694
 695   TypeParam E;
 696   E.resize(128);
 697   E.reset();
 698   E.set(1, 33);
 699
 700   EXPECT_FALSE(E.test(0));
 701   EXPECT_TRUE( E.test(1));
 702   EXPECT_TRUE( E.test(32));
 703   EXPECT_FALSE(E.test(33));
 704
 705   TypeParam BufferOverrun;
 706   unsigned size = sizeof(unsigned long) * 8;
 707   BufferOverrun.resize(size);
 708   BufferOverrun.reset(0, size);
 709   BufferOverrun.set(0, size);
 710 }
 711
 712 TYPED_TEST(BitVectorTest, CompoundTestReset) {
 713   TypeParam A(50, true);
 714   TypeParam B(50, false);
 715
 716   TypeParam C(100, true);
 717   TypeParam D(100, false);
 718
 719   EXPECT_FALSE(A.test(A));
 720   EXPECT_TRUE(A.test(B));
 721   EXPECT_FALSE(A.test(C));
 722   EXPECT_TRUE(A.test(D));
 723   EXPECT_FALSE(B.test(A));
 724   EXPECT_FALSE(B.test(B));
 725   EXPECT_FALSE(B.test(C));
 726   EXPECT_FALSE(B.test(D));
 727   EXPECT_TRUE(C.test(A));
 728   EXPECT_TRUE(C.test(B));
 729   EXPECT_FALSE(C.test(C));
 730   EXPECT_TRUE(C.test(D));
 731
 732   A.reset(B);
 733   A.reset(D);
 734   EXPECT_TRUE(A.all());
 735   A.reset(A);
 736   EXPECT_TRUE(A.none());
 737   A.set();
 738   A.reset(C);
 739   EXPECT_TRUE(A.none());
 740   A.set();
 741
 742   C.reset(A);
 743   EXPECT_EQ(50, C.find_first());
 744   C.reset(C);
 745   EXPECT_TRUE(C.none());
 746 }
 747
 748 TYPED_TEST(BitVectorTest, MoveConstructor) {
 749   TypeParam A(10, true);
 750   TypeParam B(std::move(A));
 751   // Check that the move ctor leaves the moved-from object in a valid state.
 752   // The following line used to crash.
 753   A = B;
 754
 755   TypeParam C(10, true);
 756   EXPECT_EQ(C, A);
 757   EXPECT_EQ(C, B);
 758 }
 759
 760 TYPED_TEST(BitVectorTest, MoveAssignment) {
 761   TypeParam A(10, true);
 762   TypeParam B;
 763   B = std::move(A);
 764   // Check that move assignment leaves the moved-from object in a valid state.
 765   // The following line used to crash.
 766   A = B;
 767
 768   TypeParam C(10, true);
 769   EXPECT_EQ(C, A);
 770   EXPECT_EQ(C, B);
 771 }
 772
 773 template<class TypeParam>
 774 static void testEmpty(const TypeParam &A) {
 775   EXPECT_TRUE(A.empty());
 776   EXPECT_EQ((size_t)0, A.size());
 777   EXPECT_EQ((size_t)0, A.count());
 778   EXPECT_FALSE(A.any());
 779   EXPECT_TRUE(A.all());
 780   EXPECT_TRUE(A.none());
 781   EXPECT_EQ(-1, A.find_first());
 782   EXPECT_EQ(A, TypeParam());
 783 }
 784
 785 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0
 786 TYPED_TEST(BitVectorTest, EmptyVector) {
 787   TypeParam A;
 788   testEmpty(A);
 789
 790   TypeParam B;
 791   B.reset();
 792   testEmpty(B);
 793
 794   TypeParam C;
 795   C.clear();
 796   testEmpty(C);
 797
 798   TypeParam D(A);
 799   testEmpty(D);
 800
 801   TypeParam E;
 802   E = A;
 803   testEmpty(E);
 804
 805   TypeParam F;
 806   E.reset(A);
 807   testEmpty(E);
 808 }
 809
 810 TYPED_TEST(BitVectorTest, Iterators) {
 811   TypeParam Filled(10, true);
 812   EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end());
 813   unsigned Counter = 0;
 814   for (unsigned Bit : Filled.set_bits())
 815     EXPECT_EQ(Bit, Counter++);
 816
 817   TypeParam Empty;
 818   EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end());
 819   for (unsigned Bit : Empty.set_bits()) {
 820     (void)Bit;
 821     EXPECT_TRUE(false);
 822   }
 823
 824   TypeParam ToFill(100, false);
 825   ToFill.set(0);
 826   EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end());
 827   EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end());
 828   EXPECT_EQ(*ToFill.set_bits_begin(), 0U);
 829   ToFill.reset(0);
 830   EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end());
 831
 832   const unsigned List[] = {1, 10, 25, 99};
 833   for (unsigned Num : List)
 834     ToFill.set(Num);
 835   unsigned i = 0;
 836   for (unsigned Bit : ToFill.set_bits())
 837     EXPECT_EQ(List[i++], Bit);
 838 }
 839
 840 TYPED_TEST(BitVectorTest, PushBack) {
 841   TypeParam Vec(10, false);
 842   EXPECT_EQ(-1, Vec.find_first());
 843   EXPECT_EQ(10U, Vec.size());
 844   EXPECT_EQ(0U, Vec.count());
 845
 846   Vec.push_back(true);
 847   EXPECT_EQ(10, Vec.find_first());
 848   EXPECT_EQ(11U, Vec.size());
 849   EXPECT_EQ(1U, Vec.count());
 850
 851   Vec.push_back(false);
 852   EXPECT_EQ(10, Vec.find_first());
 853   EXPECT_EQ(12U, Vec.size());
 854   EXPECT_EQ(1U, Vec.count());
 855
 856   Vec.push_back(true);
 857   EXPECT_EQ(10, Vec.find_first());
 858   EXPECT_EQ(13U, Vec.size());
 859   EXPECT_EQ(2U, Vec.count());
 860
 861   // Add a lot of values to cause reallocation.
 862   for (int i = 0; i != 100; ++i) {
 863     Vec.push_back(true);
 864     Vec.push_back(false);
 865   }
 866   EXPECT_EQ(10, Vec.find_first());
 867   EXPECT_EQ(213U, Vec.size());
 868   EXPECT_EQ(102U, Vec.count());
 869 }
 870 }
 871 #endif