562 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/CoalescingBitVector.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16using UBitVec = CoalescingBitVector<unsigned>;17using U64BitVec = CoalescingBitVector<uint64_t>;18 19bool 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 34bool 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 39TEST(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 52TEST(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 62TEST(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 72TEST(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 85TEST(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 134TEST(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 159TEST(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 human190// "expected" answer.191void 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 199TEST(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/after236 // 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 an244 // interval (and possibly both do). For ease of understanding, fix LHS to be245 // {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 the283// human "expected" answer.284void 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 291TEST(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/after327 // 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 an336 // interval (and possibly both do). For ease of understanding, fix LHS to be337 // {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 to361// double-check the human "expected" answer.362void 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 369TEST(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/after398 // 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 be409 // {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 432TEST(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 456TEST(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 494TEST(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) > Start502 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) == End532 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) > End540 EXPECT_TRUE(rangesMatch(BV.half_open_range(3, 4), {}));541 }542}543 544TEST(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} // namespace562