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