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 562