llvm/unittests/ADT/CoalescingBitVectorTest.cpp

   1 //=== CoalescingBitVectorTest.cpp - CoalescingBitVector unit 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/CoalescingBitVector.h"
  10 #include "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 namespace {
  15
  16 using UBitVec = CoalescingBitVector<unsigned>;
  17 using U64BitVec = CoalescingBitVector<uint64_t>;
  18
  19 bool elementsMatch(const UBitVec &BV, std::initializer_list<unsigned> List) {
  20   if (!std::equal(BV.begin(), BV.end(), List.begin(), List.end())) {
  21     UBitVec::Allocator Alloc;
  22     UBitVec Expected(Alloc);
  23     Expected.set(List);
  24     dbgs() << "elementsMatch:\n"
  25            << "     Expected: ";
  26     Expected.print(dbgs());
  27     dbgs() << "          Got: ";
  28     BV.print(dbgs());
  29     return false;
  30   }
  31   return true;
  32 }
  33
  34 bool rangesMatch(iterator_range<UBitVec::const_iterator> R,
  35                  std::initializer_list<unsigned> List) {
  36   return std::equal(R.begin(), R.end(), List.begin(), List.end());
  37 }
  38
  39 TEST(CoalescingBitVectorTest, Set) {
  40   UBitVec::Allocator Alloc;
  41   UBitVec BV1(Alloc);
  42   UBitVec BV2(Alloc);
  43
  44   BV1.set(0);
  45   EXPECT_TRUE(BV1.test(0));
  46   EXPECT_FALSE(BV1.test(1));
  47
  48   BV2.set(BV1);
  49   EXPECT_TRUE(BV2.test(0));
  50 }
  51
  52 TEST(CoalescingBitVectorTest, Count) {
  53   UBitVec::Allocator Alloc;
  54   UBitVec BV(Alloc);
  55   EXPECT_EQ(BV.count(), 0u);
  56   BV.set(0);
  57   EXPECT_EQ(BV.count(), 1u);
  58   BV.set({11, 12, 13, 14, 15});
  59   EXPECT_EQ(BV.count(), 6u);
  60 }
  61
  62 TEST(CoalescingBitVectorTest, ClearAndEmpty) {
  63   UBitVec::Allocator Alloc;
  64   UBitVec BV(Alloc);
  65   EXPECT_TRUE(BV.empty());
  66   BV.set(1);
  67   EXPECT_FALSE(BV.empty());
  68   BV.clear();
  69   EXPECT_TRUE(BV.empty());
  70 }
  71
  72 TEST(CoalescingBitVector, Copy) {
  73   UBitVec::Allocator Alloc;
  74   UBitVec BV1(Alloc);
  75   BV1.set(0);
  76   UBitVec BV2 = BV1;
  77   EXPECT_TRUE(elementsMatch(BV1, {0}));
  78   EXPECT_TRUE(elementsMatch(BV2, {0}));
  79   BV2.set(5);
  80   BV2 = BV1;
  81   EXPECT_TRUE(elementsMatch(BV1, {0}));
  82   EXPECT_TRUE(elementsMatch(BV2, {0}));
  83 }
  84
  85 TEST(CoalescingBitVectorTest, Iterators) {
  86   UBitVec::Allocator Alloc;
  87   UBitVec BV(Alloc);
  88
  89   BV.set({0, 1, 2});
  90
  91   auto It = BV.begin();
  92   EXPECT_TRUE(It == BV.begin());
  93   EXPECT_EQ(*It, 0u);
  94   ++It;
  95   EXPECT_EQ(*It, 1u);
  96   ++It;
  97   EXPECT_EQ(*It, 2u);
  98   ++It;
  99   EXPECT_TRUE(It == BV.end());
 100   EXPECT_TRUE(BV.end() == BV.end());
 101
 102   It = BV.begin();
 103   EXPECT_TRUE(It == BV.begin());
 104   auto ItCopy = It++;
 105   EXPECT_TRUE(ItCopy == BV.begin());
 106   EXPECT_EQ(*ItCopy, 0u);
 107   EXPECT_EQ(*It, 1u);
 108
 109   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2}));
 110
 111   BV.set({4, 5, 6});
 112   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6}));
 113
 114   BV.set(3);
 115   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6}));
 116
 117   BV.set(10);
 118   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6, 10}));
 119
 120   // Should be able to reset unset bits.
 121   BV.reset(3);
 122   BV.reset(3);
 123   BV.reset(20000);
 124   BV.set({1000, 1001, 1002});
 125   EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6, 10, 1000, 1001, 1002}));
 126
 127   auto It1 = BV.begin();
 128   EXPECT_TRUE(It1 == BV.begin());
 129   EXPECT_TRUE(++It1 == ++BV.begin());
 130   EXPECT_TRUE(It1 != BV.begin());
 131   EXPECT_TRUE(It1 != BV.end());
 132 }
 133
 134 TEST(CoalescingBitVectorTest, Reset) {
 135   UBitVec::Allocator Alloc;
 136   UBitVec BV(Alloc);
 137
 138   BV.set(0);
 139   EXPECT_TRUE(BV.test(0));
 140   BV.reset(0);
 141   EXPECT_FALSE(BV.test(0));
 142
 143   BV.clear();
 144   BV.set({1, 2, 3});
 145   BV.reset(1);
 146   EXPECT_TRUE(elementsMatch(BV, {2, 3}));
 147
 148   BV.clear();
 149   BV.set({1, 2, 3});
 150   BV.reset(2);
 151   EXPECT_TRUE(elementsMatch(BV, {1, 3}));
 152
 153   BV.clear();
 154   BV.set({1, 2, 3});
 155   BV.reset(3);
 156   EXPECT_TRUE(elementsMatch(BV, {1, 2}));
 157 }
 158
 159 TEST(CoalescingBitVectorTest, Comparison) {
 160   UBitVec::Allocator Alloc;
 161   UBitVec BV1(Alloc);
 162   UBitVec BV2(Alloc);
 163
 164   // Single interval.
 165   BV1.set({1, 2, 3});
 166   BV2.set({1, 2, 3});
 167   EXPECT_EQ(BV1, BV2);
 168   EXPECT_FALSE(BV1 != BV2);
 169
 170   // Different number of intervals.
 171   BV1.clear();
 172   BV2.clear();
 173   BV1.set({1, 2, 3});
 174   EXPECT_NE(BV1, BV2);
 175
 176   // Multiple intervals.
 177   BV1.clear();
 178   BV2.clear();
 179   BV1.set({1, 2, 11, 12});
 180   BV2.set({1, 2, 11, 12});
 181   EXPECT_EQ(BV1, BV2);
 182   BV2.reset(1);
 183   EXPECT_NE(BV1, BV2);
 184   BV2.set(1);
 185   BV2.reset(11);
 186   EXPECT_NE(BV1, BV2);
 187 }
 188
 189 // A simple implementation of set union, used to double-check the human
 190 // "expected" answer.
 191 void simpleUnion(UBitVec &Union, const UBitVec &LHS,
 192                     const UBitVec &RHS) {
 193   for (unsigned Bit : LHS)
 194     Union.test_and_set(Bit);
 195   for (unsigned Bit : RHS)
 196     Union.test_and_set(Bit);
 197 }
 198
 199 TEST(CoalescingBitVectorTest, Union) {
 200   UBitVec::Allocator Alloc;
 201
 202   // Check that after doing LHS |= RHS, LHS == Expected.
 203   auto unionIs = [&](std::initializer_list<unsigned> LHS,
 204                      std::initializer_list<unsigned> RHS,
 205                      std::initializer_list<unsigned> Expected) {
 206     UBitVec BV1(Alloc);
 207     BV1.set(LHS);
 208     UBitVec BV2(Alloc);
 209     BV2.set(RHS);
 210     UBitVec DoubleCheckedExpected(Alloc);
 211     simpleUnion(DoubleCheckedExpected, BV1, BV2);
 212     ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
 213     BV1 |= BV2;
 214     ASSERT_TRUE(elementsMatch(BV1, Expected));
 215   };
 216
 217   // Check that "LHS |= RHS" and "RHS |= LHS" both produce the expected result.
 218   auto testUnionSymmetrically = [&](std::initializer_list<unsigned> LHS,
 219                      std::initializer_list<unsigned> RHS,
 220                      std::initializer_list<unsigned> Expected) {
 221     unionIs(LHS, RHS, Expected);
 222     unionIs(RHS, LHS, Expected);
 223   };
 224
 225   // Empty LHS.
 226   testUnionSymmetrically({}, {1, 2, 3}, {1, 2, 3});
 227
 228   // Empty RHS.
 229   testUnionSymmetrically({1, 2, 3}, {}, {1, 2, 3});
 230
 231   // Full overlap.
 232   testUnionSymmetrically({1}, {1}, {1});
 233   testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});
 234
 235   // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
 236   // it. Repeat this swapping LHS and RHS.
 237   testUnionSymmetrically({2, 3, 4}, {1, 2, 3}, {1, 2, 3, 4});
 238   testUnionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
 239   testUnionSymmetrically({2, 3, 4}, {3, 4, 5}, {2, 3, 4, 5});
 240   testUnionSymmetrically({1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4});
 241   testUnionSymmetrically({3, 4, 5}, {2, 3, 4}, {2, 3, 4, 5});
 242
 243   // Multiple overlaps, but at least one of the overlaps forces us to split an
 244   // interval (and possibly both do). For ease of understanding, fix LHS to be
 245   // {1, 2, 11, 12}, but vary RHS.
 246   testUnionSymmetrically({1, 2, 11, 12}, {1}, {1, 2, 11, 12});
 247   testUnionSymmetrically({1, 2, 11, 12}, {2}, {1, 2, 11, 12});
 248   testUnionSymmetrically({1, 2, 11, 12}, {11}, {1, 2, 11, 12});
 249   testUnionSymmetrically({1, 2, 11, 12}, {12}, {1, 2, 11, 12});
 250   testUnionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 2, 11, 12});
 251   testUnionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 2, 11, 12});
 252   testUnionSymmetrically({1, 2, 11, 12}, {2, 11}, {1, 2, 11, 12});
 253   testUnionSymmetrically({1, 2, 11, 12}, {2, 12}, {1, 2, 11, 12});
 254   testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11, 12});
 255   testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 11, 12});
 256   testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 2, 11, 12});
 257   testUnionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {1, 2, 11, 12});
 258   testUnionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {0, 1, 2, 11, 12});
 259   testUnionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {1, 2, 3, 11, 12});
 260   testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 2, 11, 12, 13});
 261   testUnionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 2, 10, 11, 12});
 262
 263   // Partial overlap, but the existing interval covers future overlaps.
 264   testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
 265                          {1, 2, 3, 4, 5, 6, 7, 8});
 266   testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 7, 8, 9},
 267                          {1, 2, 3, 4, 5, 6, 7, 8, 9});
 268
 269   // More partial overlaps.
 270   testUnionSymmetrically({1, 2, 3, 4, 5}, {0, 1, 2, 4, 5, 6},
 271                          {0, 1, 2, 3, 4, 5, 6});
 272   testUnionSymmetrically({2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4});
 273   testUnionSymmetrically({3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4});
 274   testUnionSymmetrically({1, 2}, {1, 2, 3, 4}, {1, 2, 3, 4});
 275   testUnionSymmetrically({0, 1}, {1, 2, 3, 4}, {0, 1, 2, 3, 4});
 276
 277   // Merge non-overlapping.
 278   testUnionSymmetrically({0, 1}, {2, 3}, {0, 1, 2, 3});
 279   testUnionSymmetrically({0, 3}, {1, 2}, {0, 1, 2, 3});
 280 }
 281
 282 // A simple implementation of set intersection, used to double-check the
 283 // human "expected" answer.
 284 void simpleIntersection(UBitVec &Intersection, const UBitVec &LHS,
 285                         const UBitVec &RHS) {
 286   for (unsigned Bit : LHS)
 287     if (RHS.test(Bit))
 288       Intersection.set(Bit);
 289 }
 290
 291 TEST(CoalescingBitVectorTest, Intersection) {
 292   UBitVec::Allocator Alloc;
 293
 294   // Check that after doing LHS &= RHS, LHS == Expected.
 295   auto intersectionIs = [&](std::initializer_list<unsigned> LHS,
 296                             std::initializer_list<unsigned> RHS,
 297                             std::initializer_list<unsigned> Expected) {
 298     UBitVec BV1(Alloc);
 299     BV1.set(LHS);
 300     UBitVec BV2(Alloc);
 301     BV2.set(RHS);
 302     UBitVec DoubleCheckedExpected(Alloc);
 303     simpleIntersection(DoubleCheckedExpected, BV1, BV2);
 304     ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
 305     BV1 &= BV2;
 306     ASSERT_TRUE(elementsMatch(BV1, Expected));
 307   };
 308
 309   // Check that "LHS &= RHS" and "RHS &= LHS" both produce the expected result.
 310   auto testIntersectionSymmetrically = [&](std::initializer_list<unsigned> LHS,
 311                      std::initializer_list<unsigned> RHS,
 312                      std::initializer_list<unsigned> Expected) {
 313     intersectionIs(LHS, RHS, Expected);
 314     intersectionIs(RHS, LHS, Expected);
 315   };
 316
 317   // Empty case, one-element case.
 318   testIntersectionSymmetrically({}, {}, {});
 319   testIntersectionSymmetrically({1}, {1}, {1});
 320   testIntersectionSymmetrically({1}, {2}, {});
 321
 322   // Exact overlaps cases: single overlap and multiple overlaps.
 323   testIntersectionSymmetrically({1, 2}, {1, 2}, {1, 2});
 324   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});
 325
 326   // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
 327   // it.
 328   testIntersectionSymmetrically({2, 3, 4}, {1, 2, 3}, {2, 3});
 329   testIntersectionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
 330   testIntersectionSymmetrically({2, 3, 4}, {3, 4, 5}, {3, 4});
 331
 332   // No overlap, but we have multiple intervals.
 333   testIntersectionSymmetrically({1, 2, 11, 12}, {3, 4, 13, 14}, {});
 334
 335   // Multiple overlaps, but at least one of the overlaps forces us to split an
 336   // interval (and possibly both do). For ease of understanding, fix LHS to be
 337   // {1, 2, 11, 12}, but vary RHS.
 338   testIntersectionSymmetrically({1, 2, 11, 12}, {1}, {1});
 339   testIntersectionSymmetrically({1, 2, 11, 12}, {2}, {2});
 340   testIntersectionSymmetrically({1, 2, 11, 12}, {11}, {11});
 341   testIntersectionSymmetrically({1, 2, 11, 12}, {12}, {12});
 342   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 11});
 343   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 12});
 344   testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11}, {2, 11});
 345   testIntersectionSymmetrically({1, 2, 11, 12}, {2, 12}, {2, 12});
 346   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11});
 347   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 12});
 348   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 11, 12});
 349   testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {2, 11, 12});
 350   testIntersectionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {11, 12});
 351   testIntersectionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {11, 12});
 352   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 11});
 353   testIntersectionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 11});
 354
 355   // Partial overlap, but the existing interval covers future overlaps.
 356   testIntersectionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
 357                                 {2, 3, 4, 6, 7});
 358 }
 359
 360 // A simple implementation of set intersection-with-complement, used to
 361 // double-check the human "expected" answer.
 362 void simpleIntersectionWithComplement(UBitVec &Intersection, const UBitVec &LHS,
 363                                       const UBitVec &RHS) {
 364   for (unsigned Bit : LHS)
 365     if (!RHS.test(Bit))
 366       Intersection.set(Bit);
 367 }
 368
 369 TEST(CoalescingBitVectorTest, IntersectWithComplement) {
 370   UBitVec::Allocator Alloc;
 371
 372   // Check that after doing LHS.intersectWithComplement(RHS), LHS == Expected.
 373   auto intersectionWithComplementIs =
 374       [&](std::initializer_list<unsigned> LHS,
 375           std::initializer_list<unsigned> RHS,
 376           std::initializer_list<unsigned> Expected) {
 377         UBitVec BV1(Alloc);
 378         BV1.set(LHS);
 379         UBitVec BV2(Alloc);
 380         BV2.set(RHS);
 381         UBitVec DoubleCheckedExpected(Alloc);
 382         simpleIntersectionWithComplement(DoubleCheckedExpected, BV1, BV2);
 383         ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
 384         BV1.intersectWithComplement(BV2);
 385         ASSERT_TRUE(elementsMatch(BV1, Expected));
 386       };
 387
 388   // Empty case, one-element case.
 389   intersectionWithComplementIs({}, {}, {});
 390   intersectionWithComplementIs({1}, {1}, {});
 391   intersectionWithComplementIs({1}, {2}, {1});
 392
 393   // Exact overlaps cases: single overlap and multiple overlaps.
 394   intersectionWithComplementIs({1, 2}, {1, 2}, {});
 395   intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11, 12}, {});
 396
 397   // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
 398   // it. Repeat this swapping LHS and RHS.
 399   intersectionWithComplementIs({2, 3, 4}, {1, 2, 3}, {4});
 400   intersectionWithComplementIs({2, 3, 4}, {2, 3, 4}, {});
 401   intersectionWithComplementIs({2, 3, 4}, {3, 4, 5}, {2});
 402   intersectionWithComplementIs({1, 2, 3}, {2, 3, 4}, {1});
 403   intersectionWithComplementIs({3, 4, 5}, {2, 3, 4}, {5});
 404
 405   // No overlap, but we have multiple intervals.
 406   intersectionWithComplementIs({1, 2, 11, 12}, {3, 4, 13, 14}, {1, 2, 11, 12});
 407
 408   // Multiple overlaps. For ease of understanding, fix LHS to be
 409   // {1, 2, 11, 12}, but vary RHS.
 410   intersectionWithComplementIs({1, 2, 11, 12}, {1}, {2, 11, 12});
 411   intersectionWithComplementIs({1, 2, 11, 12}, {2}, {1, 11, 12});
 412   intersectionWithComplementIs({1, 2, 11, 12}, {11}, {1, 2, 12});
 413   intersectionWithComplementIs({1, 2, 11, 12}, {12}, {1, 2, 11});
 414   intersectionWithComplementIs({1, 2, 11, 12}, {1, 11}, {2, 12});
 415   intersectionWithComplementIs({1, 2, 11, 12}, {1, 12}, {2, 11});
 416   intersectionWithComplementIs({1, 2, 11, 12}, {2, 11}, {1, 12});
 417   intersectionWithComplementIs({1, 2, 11, 12}, {2, 12}, {1, 11});
 418   intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11}, {12});
 419   intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 12}, {11});
 420   intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 12}, {2});
 421   intersectionWithComplementIs({1, 2, 11, 12}, {2, 11, 12}, {1});
 422   intersectionWithComplementIs({1, 2, 11, 12}, {0, 11, 12}, {1, 2});
 423   intersectionWithComplementIs({1, 2, 11, 12}, {3, 11, 12}, {1, 2});
 424   intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 13}, {2, 12});
 425   intersectionWithComplementIs({1, 2, 11, 12}, {1, 10, 11}, {2, 12});
 426
 427   // Partial overlap, but the existing interval covers future overlaps.
 428   intersectionWithComplementIs({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
 429                                {1, 5, 8});
 430 }
 431
 432 TEST(CoalescingBitVectorTest, FindLowerBound) {
 433   U64BitVec::Allocator Alloc;
 434   U64BitVec BV(Alloc);
 435   uint64_t BigNum1 = uint64_t(1) << 32;
 436   uint64_t BigNum2 = (uint64_t(1) << 33) + 1;
 437   EXPECT_TRUE(BV.find(BigNum1) == BV.end());
 438   BV.set(BigNum1);
 439   auto Find1 = BV.find(BigNum1);
 440   EXPECT_EQ(*Find1, BigNum1);
 441   BV.set(BigNum2);
 442   auto Find2 = BV.find(BigNum1);
 443   EXPECT_EQ(*Find2, BigNum1);
 444   auto Find3 = BV.find(BigNum2);
 445   EXPECT_EQ(*Find3, BigNum2);
 446   BV.reset(BigNum1);
 447   auto Find4 = BV.find(BigNum1);
 448   EXPECT_EQ(*Find4, BigNum2);
 449
 450   BV.clear();
 451   BV.set({1, 2, 3});
 452   EXPECT_EQ(*BV.find(2), 2u);
 453   EXPECT_EQ(*BV.find(3), 3u);
 454 }
 455
 456 TEST(CoalescingBitVectorTest, AdvanceToLowerBound) {
 457   U64BitVec::Allocator Alloc;
 458   U64BitVec BV(Alloc);
 459   uint64_t BigNum1 = uint64_t(1) << 32;
 460   uint64_t BigNum2 = (uint64_t(1) << 33) + 1;
 461
 462   auto advFromBegin = [&](uint64_t To) -> U64BitVec::const_iterator {
 463     auto It = BV.begin();
 464     It.advanceToLowerBound(To);
 465     return It;
 466   };
 467
 468   EXPECT_TRUE(advFromBegin(BigNum1) == BV.end());
 469   BV.set(BigNum1);
 470   auto Find1 = advFromBegin(BigNum1);
 471   EXPECT_EQ(*Find1, BigNum1);
 472   BV.set(BigNum2);
 473   auto Find2 = advFromBegin(BigNum1);
 474   EXPECT_EQ(*Find2, BigNum1);
 475   auto Find3 = advFromBegin(BigNum2);
 476   EXPECT_EQ(*Find3, BigNum2);
 477   BV.reset(BigNum1);
 478   auto Find4 = advFromBegin(BigNum1);
 479   EXPECT_EQ(*Find4, BigNum2);
 480
 481   BV.clear();
 482   BV.set({1, 2, 3});
 483   EXPECT_EQ(*advFromBegin(2), 2u);
 484   EXPECT_EQ(*advFromBegin(3), 3u);
 485   auto It = BV.begin();
 486   It.advanceToLowerBound(0);
 487   EXPECT_EQ(*It, 1u);
 488   It.advanceToLowerBound(100);
 489   EXPECT_TRUE(It == BV.end());
 490   It.advanceToLowerBound(100);
 491   EXPECT_TRUE(It == BV.end());
 492 }
 493
 494 TEST(CoalescingBitVectorTest, HalfOpenRange) {
 495   UBitVec::Allocator Alloc;
 496
 497   {
 498     UBitVec BV(Alloc);
 499     BV.set({1, 2, 3});
 500
 501     EXPECT_EQ(*BV.find(0), 1U); // find(Start) > Start
 502     EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2, 3}));
 503     EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 4), {1, 2, 3}));
 504     EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 3), {1, 2}));
 505     EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 3), {2}));
 506     EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 4), {2, 3}));
 507     EXPECT_TRUE(rangesMatch(BV.half_open_range(4, 5), {}));
 508   }
 509
 510   {
 511     UBitVec BV(Alloc);
 512     BV.set({1, 2, 11, 12});
 513
 514     EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 15), {1, 2, 11, 12}));
 515     EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 13), {1, 2, 11, 12}));
 516     EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 12), {1, 2, 11}));
 517
 518     EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2}));
 519     EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 5), {1, 2}));
 520     EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 5), {2}));
 521     EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 2), {1}));
 522     EXPECT_TRUE(rangesMatch(BV.half_open_range(13, 14), {}));
 523
 524     EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 10), {2}));
 525   }
 526
 527   {
 528     UBitVec BV(Alloc);
 529     BV.set({1});
 530
 531     EXPECT_EQ(*BV.find(0), 1U); // find(Start) == End
 532     EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 1), {}));
 533   }
 534
 535   {
 536     UBitVec BV(Alloc);
 537     BV.set({5});
 538
 539     EXPECT_EQ(*BV.find(3), 5U); // find(Start) > End
 540     EXPECT_TRUE(rangesMatch(BV.half_open_range(3, 4), {}));
 541   }
 542 }
 543
 544 TEST(CoalescingBitVectorTest, Print) {
 545   std::string S;
 546   {
 547     raw_string_ostream OS(S);
 548     UBitVec::Allocator Alloc;
 549     UBitVec BV(Alloc);
 550     BV.set({1});
 551     BV.print(OS);
 552
 553     BV.clear();
 554     BV.set({1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20});
 555     BV.print(OS);
 556   }
 557   EXPECT_EQ(S, "{[1]}"
 558                "{[1][11, 20]}");
 559 }
 560
 561 } // namespace