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
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(first1: BV.begin(), last1: BV.end(), first2: List.begin(), last2: List.end())) {
21 UBitVec::Allocator Alloc;
22 UBitVec Expected(Alloc);
23 Expected.set(List);
24 dbgs() << "elementsMatch:\n"
25 << " Expected: ";
26 Expected.print(OS&: dbgs());
27 dbgs() << " Got: ";
28 BV.print(OS&: 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(first1: R.begin(), last1: R.end(), first2: List.begin(), last2: 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(Index: 3);
122 BV.reset(Index: 3);
123 BV.reset(Index: 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(Index: 0);
141 EXPECT_FALSE(BV.test(0));
142
143 BV.clear();
144 BV.set({1, 2, 3});
145 BV.reset(Index: 1);
146 EXPECT_TRUE(elementsMatch(BV, {2, 3}));
147
148 BV.clear();
149 BV.set({1, 2, 3});
150 BV.reset(Index: 2);
151 EXPECT_TRUE(elementsMatch(BV, {1, 3}));
152
153 BV.clear();
154 BV.set({1, 2, 3});
155 BV.reset(Index: 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(Index: 1);
183 EXPECT_NE(BV1, BV2);
184 BV2.set(1);
185 BV2.reset(Index: 11);
186 EXPECT_NE(BV1, BV2);
187}
188
189// A simple implementation of set union, used to double-check the human
190// "expected" answer.
191void simpleUnion(UBitVec &Union, const UBitVec &LHS,
192 const UBitVec &RHS) {
193 for (unsigned Bit : LHS)
194 Union.test_and_set(Index: Bit);
195 for (unsigned Bit : RHS)
196 Union.test_and_set(Index: 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(Union&: DoubleCheckedExpected, LHS: BV1, RHS: 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.
284void simpleIntersection(UBitVec &Intersection, const UBitVec &LHS,
285 const UBitVec &RHS) {
286 for (unsigned Bit : LHS)
287 if (RHS.test(Index: 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(Intersection&: DoubleCheckedExpected, LHS: BV1, RHS: 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.
362void simpleIntersectionWithComplement(UBitVec &Intersection, const UBitVec &LHS,
363 const UBitVec &RHS) {
364 for (unsigned Bit : LHS)
365 if (!RHS.test(Index: 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(Intersection&: DoubleCheckedExpected, LHS: BV1, RHS: BV2);
383 ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
384 BV1.intersectWithComplement(Other: 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
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(Index: BigNum1);
440 EXPECT_EQ(*Find1, BigNum1);
441 BV.set(BigNum2);
442 auto Find2 = BV.find(Index: BigNum1);
443 EXPECT_EQ(*Find2, BigNum1);
444 auto Find3 = BV.find(Index: BigNum2);
445 EXPECT_EQ(*Find3, BigNum2);
446 BV.reset(Index: BigNum1);
447 auto Find4 = BV.find(Index: 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(Index: 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(Index: 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(Index: 0);
487 EXPECT_EQ(*It, 1u);
488 It.advanceToLowerBound(Index: 100);
489 EXPECT_TRUE(It == BV.end());
490 It.advanceToLowerBound(Index: 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) > 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
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} // namespace
562

source code of llvm/unittests/ADT/CoalescingBitVectorTest.cpp