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 
elementsMatch(const UBitVec & BV,std::initializer_list<unsigned> List)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 
rangesMatch(iterator_range<UBitVec::const_iterator> R,std::initializer_list<unsigned> List)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 
TEST(CoalescingBitVectorTest,Set)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 
TEST(CoalescingBitVectorTest,Count)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 
TEST(CoalescingBitVectorTest,ClearAndEmpty)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 
TEST(CoalescingBitVector,Copy)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 
TEST(CoalescingBitVectorTest,Iterators)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 
TEST(CoalescingBitVectorTest,Reset)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 
TEST(CoalescingBitVectorTest,Comparison)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.
simpleUnion(UBitVec & Union,const UBitVec & LHS,const UBitVec & RHS)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 
TEST(CoalescingBitVectorTest,Union)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.
simpleIntersection(UBitVec & Intersection,const UBitVec & LHS,const UBitVec & RHS)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 
TEST(CoalescingBitVectorTest,Intersection)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.
simpleIntersectionWithComplement(UBitVec & Intersection,const UBitVec & LHS,const UBitVec & RHS)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 
TEST(CoalescingBitVectorTest,IntersectWithComplement)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 
TEST(CoalescingBitVectorTest,FindLowerBound)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 
TEST(CoalescingBitVectorTest,AdvanceToLowerBound)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 
TEST(CoalescingBitVectorTest,HalfOpenRange)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 
TEST(CoalescingBitVectorTest,Print)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