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(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 | |
34 | bool 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 | |
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(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 | |
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(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 | |
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(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. |
191 | void 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 | |
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(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. |
284 | void 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 | |
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(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. |
362 | void 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 | |
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(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 | |
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(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 | |
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(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 | |
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 | |