1 | //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector 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/BitVector.h" |
10 | #include "llvm/ADT/DenseSet.h" |
11 | #include "llvm/ADT/SmallBitVector.h" |
12 | #include "gtest/gtest.h" |
13 | |
14 | using namespace llvm; |
15 | |
16 | namespace { |
17 | |
18 | // Test fixture |
19 | template <typename T> |
20 | class BitVectorTest : public ::testing::Test { }; |
21 | |
22 | // Test both BitVector and SmallBitVector with the same suite of tests. |
23 | typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes; |
24 | TYPED_TEST_SUITE(BitVectorTest, BitVectorTestTypes, ); |
25 | |
26 | TYPED_TEST(BitVectorTest, TrivialOperation) { |
27 | TypeParam Vec; |
28 | EXPECT_EQ(0U, Vec.count()); |
29 | EXPECT_EQ(0U, Vec.size()); |
30 | EXPECT_FALSE(Vec.any()); |
31 | EXPECT_TRUE(Vec.all()); |
32 | EXPECT_TRUE(Vec.none()); |
33 | EXPECT_TRUE(Vec.empty()); |
34 | |
35 | Vec.resize(5, true); |
36 | EXPECT_EQ(5U, Vec.count()); |
37 | EXPECT_EQ(5U, Vec.size()); |
38 | EXPECT_TRUE(Vec.any()); |
39 | EXPECT_TRUE(Vec.all()); |
40 | EXPECT_FALSE(Vec.none()); |
41 | EXPECT_FALSE(Vec.empty()); |
42 | |
43 | Vec.resize(11); |
44 | EXPECT_EQ(5U, Vec.count()); |
45 | EXPECT_EQ(11U, Vec.size()); |
46 | EXPECT_TRUE(Vec.any()); |
47 | EXPECT_FALSE(Vec.all()); |
48 | EXPECT_FALSE(Vec.none()); |
49 | EXPECT_FALSE(Vec.empty()); |
50 | |
51 | TypeParam Inv = Vec; |
52 | Inv.flip(); |
53 | EXPECT_EQ(6U, Inv.count()); |
54 | EXPECT_EQ(11U, Inv.size()); |
55 | EXPECT_TRUE(Inv.any()); |
56 | EXPECT_FALSE(Inv.all()); |
57 | EXPECT_FALSE(Inv.none()); |
58 | EXPECT_FALSE(Inv.empty()); |
59 | |
60 | EXPECT_FALSE(Inv == Vec); |
61 | EXPECT_TRUE(Inv != Vec); |
62 | Vec.flip(); |
63 | EXPECT_TRUE(Inv == Vec); |
64 | EXPECT_FALSE(Inv != Vec); |
65 | |
66 | // Add some "interesting" data to Vec. |
67 | Vec.resize(23, true); |
68 | Vec.resize(25, false); |
69 | Vec.resize(26, true); |
70 | Vec.resize(29, false); |
71 | Vec.resize(33, true); |
72 | Vec.resize(57, false); |
73 | unsigned Count = 0; |
74 | for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { |
75 | ++Count; |
76 | EXPECT_TRUE(Vec[i]); |
77 | EXPECT_TRUE(Vec.test(i)); |
78 | } |
79 | EXPECT_EQ(Count, Vec.count()); |
80 | EXPECT_EQ(Count, 23u); |
81 | EXPECT_FALSE(Vec[0]); |
82 | EXPECT_TRUE(Vec[32]); |
83 | EXPECT_FALSE(Vec[56]); |
84 | Vec.resize(61, false); |
85 | |
86 | TypeParam Copy = Vec; |
87 | TypeParam Alt(3, false); |
88 | Alt.resize(6, true); |
89 | std::swap(Alt, Vec); |
90 | EXPECT_TRUE(Copy == Alt); |
91 | EXPECT_TRUE(Vec.size() == 6); |
92 | EXPECT_TRUE(Vec.count() == 3); |
93 | EXPECT_TRUE(Vec.find_first() == 3); |
94 | std::swap(Copy, Vec); |
95 | |
96 | // Add some more "interesting" data. |
97 | Vec.resize(68, true); |
98 | Vec.resize(78, false); |
99 | Vec.resize(89, true); |
100 | Vec.resize(90, false); |
101 | Vec.resize(91, true); |
102 | Vec.resize(130, false); |
103 | Count = 0; |
104 | for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { |
105 | ++Count; |
106 | EXPECT_TRUE(Vec[i]); |
107 | EXPECT_TRUE(Vec.test(i)); |
108 | } |
109 | EXPECT_EQ(Count, Vec.count()); |
110 | EXPECT_EQ(Count, 42u); |
111 | EXPECT_FALSE(Vec[0]); |
112 | EXPECT_TRUE(Vec[32]); |
113 | EXPECT_FALSE(Vec[60]); |
114 | EXPECT_FALSE(Vec[129]); |
115 | |
116 | Vec.flip(60); |
117 | EXPECT_TRUE(Vec[60]); |
118 | EXPECT_EQ(Count + 1, Vec.count()); |
119 | Vec.flip(60); |
120 | EXPECT_FALSE(Vec[60]); |
121 | EXPECT_EQ(Count, Vec.count()); |
122 | |
123 | Vec.reset(32); |
124 | EXPECT_FALSE(Vec[32]); |
125 | EXPECT_EQ(Count - 1, Vec.count()); |
126 | Vec.set(32); |
127 | EXPECT_TRUE(Vec[32]); |
128 | EXPECT_EQ(Count, Vec.count()); |
129 | |
130 | Vec.flip(); |
131 | EXPECT_EQ(Vec.size() - Count, Vec.count()); |
132 | |
133 | Vec.reset(); |
134 | EXPECT_EQ(0U, Vec.count()); |
135 | EXPECT_EQ(130U, Vec.size()); |
136 | EXPECT_FALSE(Vec.any()); |
137 | EXPECT_FALSE(Vec.all()); |
138 | EXPECT_TRUE(Vec.none()); |
139 | EXPECT_FALSE(Vec.empty()); |
140 | |
141 | Vec.flip(); |
142 | EXPECT_EQ(130U, Vec.count()); |
143 | EXPECT_EQ(130U, Vec.size()); |
144 | EXPECT_TRUE(Vec.any()); |
145 | EXPECT_TRUE(Vec.all()); |
146 | EXPECT_FALSE(Vec.none()); |
147 | EXPECT_FALSE(Vec.empty()); |
148 | |
149 | Vec.resize(64); |
150 | EXPECT_EQ(64U, Vec.count()); |
151 | EXPECT_EQ(64U, Vec.size()); |
152 | EXPECT_TRUE(Vec.any()); |
153 | EXPECT_TRUE(Vec.all()); |
154 | EXPECT_FALSE(Vec.none()); |
155 | EXPECT_FALSE(Vec.empty()); |
156 | |
157 | Vec.flip(); |
158 | EXPECT_EQ(0U, Vec.count()); |
159 | EXPECT_EQ(64U, Vec.size()); |
160 | EXPECT_FALSE(Vec.any()); |
161 | EXPECT_FALSE(Vec.all()); |
162 | EXPECT_TRUE(Vec.none()); |
163 | EXPECT_FALSE(Vec.empty()); |
164 | |
165 | Inv = TypeParam().flip(); |
166 | EXPECT_EQ(0U, Inv.count()); |
167 | EXPECT_EQ(0U, Inv.size()); |
168 | EXPECT_FALSE(Inv.any()); |
169 | EXPECT_TRUE(Inv.all()); |
170 | EXPECT_TRUE(Inv.none()); |
171 | EXPECT_TRUE(Inv.empty()); |
172 | |
173 | Vec.clear(); |
174 | EXPECT_EQ(0U, Vec.count()); |
175 | EXPECT_EQ(0U, Vec.size()); |
176 | EXPECT_FALSE(Vec.any()); |
177 | EXPECT_TRUE(Vec.all()); |
178 | EXPECT_TRUE(Vec.none()); |
179 | EXPECT_TRUE(Vec.empty()); |
180 | } |
181 | |
182 | TYPED_TEST(BitVectorTest, Equality) { |
183 | TypeParam A; |
184 | TypeParam B; |
185 | EXPECT_TRUE(A == B); |
186 | A.resize(10); |
187 | EXPECT_FALSE(A == B); |
188 | B.resize(10); |
189 | EXPECT_TRUE(A == B); |
190 | A.set(5); |
191 | EXPECT_FALSE(A == B); |
192 | B.set(5); |
193 | EXPECT_TRUE(A == B); |
194 | A.resize(20); |
195 | EXPECT_FALSE(A == B); |
196 | B.resize(20); |
197 | EXPECT_TRUE(A == B); |
198 | } |
199 | |
200 | TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) { |
201 | TypeParam A; |
202 | |
203 | // Test finding next set and unset bits in a BitVector with multiple words |
204 | A.resize(100); |
205 | A.set(12); |
206 | A.set(13); |
207 | A.set(75); |
208 | |
209 | EXPECT_EQ(75, A.find_last()); |
210 | EXPECT_EQ(12, A.find_first()); |
211 | EXPECT_EQ(13, A.find_next(12)); |
212 | EXPECT_EQ(75, A.find_next(13)); |
213 | EXPECT_EQ(-1, A.find_next(75)); |
214 | |
215 | EXPECT_EQ(-1, A.find_prev(12)); |
216 | EXPECT_EQ(12, A.find_prev(13)); |
217 | EXPECT_EQ(13, A.find_prev(75)); |
218 | EXPECT_EQ(75, A.find_prev(90)); |
219 | |
220 | EXPECT_EQ(0, A.find_first_unset()); |
221 | EXPECT_EQ(99, A.find_last_unset()); |
222 | EXPECT_EQ(14, A.find_next_unset(11)); |
223 | EXPECT_EQ(14, A.find_next_unset(12)); |
224 | EXPECT_EQ(14, A.find_next_unset(13)); |
225 | EXPECT_EQ(16, A.find_next_unset(15)); |
226 | EXPECT_EQ(76, A.find_next_unset(74)); |
227 | EXPECT_EQ(76, A.find_next_unset(75)); |
228 | EXPECT_EQ(-1, A.find_next_unset(99)); |
229 | |
230 | A.set(0, 100); |
231 | EXPECT_EQ(100U, A.count()); |
232 | EXPECT_EQ(0, A.find_first()); |
233 | EXPECT_EQ(-1, A.find_first_unset()); |
234 | EXPECT_EQ(-1, A.find_last_unset()); |
235 | EXPECT_EQ(99, A.find_last()); |
236 | EXPECT_EQ(99, A.find_next(98)); |
237 | |
238 | A.reset(0, 100); |
239 | EXPECT_EQ(0U, A.count()); |
240 | EXPECT_EQ(-1, A.find_first()); |
241 | EXPECT_EQ(-1, A.find_last()); |
242 | EXPECT_EQ(0, A.find_first_unset()); |
243 | EXPECT_EQ(99, A.find_last_unset()); |
244 | EXPECT_EQ(99, A.find_next_unset(98)); |
245 | } |
246 | |
247 | // Test finding next set and unset bits in a BitVector/SmallBitVector within a |
248 | // uintptr_t - check both 32-bit (Multi) and 64-bit (Small) targets. |
249 | TYPED_TEST(BitVectorTest, SimpleFindOps64Bit) { |
250 | TypeParam A; |
251 | |
252 | A.resize(57); |
253 | A.set(12); |
254 | A.set(13); |
255 | A.set(47); |
256 | |
257 | EXPECT_EQ(47, A.find_last()); |
258 | EXPECT_EQ(12, A.find_first()); |
259 | EXPECT_EQ(13, A.find_next(12)); |
260 | EXPECT_EQ(47, A.find_next(13)); |
261 | EXPECT_EQ(-1, A.find_next(47)); |
262 | |
263 | EXPECT_EQ(-1, A.find_prev(12)); |
264 | EXPECT_EQ(12, A.find_prev(13)); |
265 | EXPECT_EQ(13, A.find_prev(47)); |
266 | EXPECT_EQ(47, A.find_prev(56)); |
267 | |
268 | EXPECT_EQ(0, A.find_first_unset()); |
269 | EXPECT_EQ(56, A.find_last_unset()); |
270 | EXPECT_EQ(14, A.find_next_unset(11)); |
271 | EXPECT_EQ(14, A.find_next_unset(12)); |
272 | EXPECT_EQ(14, A.find_next_unset(13)); |
273 | EXPECT_EQ(16, A.find_next_unset(15)); |
274 | EXPECT_EQ(48, A.find_next_unset(46)); |
275 | EXPECT_EQ(48, A.find_next_unset(47)); |
276 | EXPECT_EQ(-1, A.find_next_unset(56)); |
277 | } |
278 | |
279 | // Check if a SmallBitVector is in small mode. This check is used in tests |
280 | // that run for both SmallBitVector and BitVector. This check doesn't apply |
281 | // to BitVector so we provide an overload that returns true to get the tests |
282 | // to compile. |
283 | static bool SmallBitVectorIsSmallMode(const SmallBitVector &bv) { |
284 | return bv.isSmall(); |
285 | } |
286 | static bool SmallBitVectorIsSmallMode(const BitVector &) { return true; } |
287 | |
288 | // These tests are intended to exercise the single-word case of BitVector |
289 | // and the small-mode case of SmallBitVector. |
290 | TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) { |
291 | // Test finding in an empty BitVector. |
292 | TypeParam A; |
293 | ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); |
294 | EXPECT_EQ(-1, A.find_first()); |
295 | EXPECT_EQ(-1, A.find_last()); |
296 | EXPECT_EQ(-1, A.find_first_unset()); |
297 | EXPECT_EQ(-1, A.find_last_unset()); |
298 | |
299 | A.resize(20); |
300 | ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); |
301 | EXPECT_EQ(-1, A.find_first()); |
302 | EXPECT_EQ(-1, A.find_last()); |
303 | EXPECT_EQ(-1, A.find_next(5)); |
304 | EXPECT_EQ(-1, A.find_next(19)); |
305 | EXPECT_EQ(-1, A.find_prev(5)); |
306 | EXPECT_EQ(-1, A.find_prev(20)); |
307 | EXPECT_EQ(0, A.find_first_unset()); |
308 | EXPECT_EQ(19, A.find_last_unset()); |
309 | EXPECT_EQ(6, A.find_next_unset(5)); |
310 | EXPECT_EQ(-1, A.find_next_unset(19)); |
311 | |
312 | A.set(3); |
313 | A.set(4); |
314 | A.set(16); |
315 | ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); |
316 | EXPECT_EQ(16, A.find_last()); |
317 | EXPECT_EQ(3, A.find_first()); |
318 | EXPECT_EQ(3, A.find_next(1)); |
319 | EXPECT_EQ(4, A.find_next(3)); |
320 | EXPECT_EQ(16, A.find_next(4)); |
321 | EXPECT_EQ(-1, A.find_next(16)); |
322 | |
323 | EXPECT_EQ(-1, A.find_prev(3)); |
324 | EXPECT_EQ(3, A.find_prev(4)); |
325 | EXPECT_EQ(4, A.find_prev(16)); |
326 | EXPECT_EQ(16, A.find_prev(18)); |
327 | |
328 | EXPECT_EQ(0, A.find_first_unset()); |
329 | EXPECT_EQ(19, A.find_last_unset()); |
330 | EXPECT_EQ(5, A.find_next_unset(3)); |
331 | EXPECT_EQ(5, A.find_next_unset(4)); |
332 | EXPECT_EQ(13, A.find_next_unset(12)); |
333 | EXPECT_EQ(17, A.find_next_unset(15)); |
334 | |
335 | A.set(); |
336 | ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); |
337 | EXPECT_EQ(0, A.find_first()); |
338 | EXPECT_EQ(19, A.find_last()); |
339 | EXPECT_EQ(6, A.find_next(5)); |
340 | EXPECT_EQ(-1, A.find_next(19)); |
341 | EXPECT_EQ(4, A.find_prev(5)); |
342 | EXPECT_EQ(19, A.find_prev(20)); |
343 | EXPECT_EQ(-1, A.find_first_unset()); |
344 | EXPECT_EQ(-1, A.find_last_unset()); |
345 | EXPECT_EQ(-1, A.find_next_unset(5)); |
346 | EXPECT_EQ(-1, A.find_next_unset(19)); |
347 | } |
348 | |
349 | TEST(BitVectorTest, FindInRangeMultiWord) { |
350 | BitVector Vec; |
351 | |
352 | Vec.resize(N: 200); |
353 | Vec.set(I: 3, E: 7); |
354 | Vec.set(I: 24, E: 35); |
355 | Vec.set(I: 50, E: 70); |
356 | Vec.set(150); |
357 | Vec.set(152); |
358 | Vec.set(154); |
359 | |
360 | // find first |
361 | EXPECT_EQ(-1, Vec.find_first_in(0, 0)); |
362 | EXPECT_EQ(-1, Vec.find_first_in(24, 24)); |
363 | EXPECT_EQ(-1, Vec.find_first_in(7, 24)); |
364 | |
365 | EXPECT_EQ(3, Vec.find_first_in(0, 10)); |
366 | EXPECT_EQ(4, Vec.find_first_in(4, 10)); |
367 | EXPECT_EQ(150, Vec.find_first_in(100, 200)); |
368 | EXPECT_EQ(152, Vec.find_first_in(151, 200)); |
369 | EXPECT_EQ(154, Vec.find_first_in(153, 200)); |
370 | |
371 | EXPECT_EQ(-1, Vec.find_first_in(155, 200)); |
372 | Vec.set(199); |
373 | EXPECT_EQ(199, Vec.find_first_in(199, 200)); |
374 | Vec.reset(Idx: 199); |
375 | |
376 | // find last |
377 | EXPECT_EQ(-1, Vec.find_last_in(0, 0)); |
378 | EXPECT_EQ(-1, Vec.find_last_in(24, 24)); |
379 | EXPECT_EQ(-1, Vec.find_last_in(7, 24)); |
380 | |
381 | EXPECT_EQ(6, Vec.find_last_in(0, 10)); |
382 | EXPECT_EQ(5, Vec.find_last_in(0, 6)); |
383 | EXPECT_EQ(154, Vec.find_last_in(100, 155)); |
384 | EXPECT_EQ(152, Vec.find_last_in(100, 154)); |
385 | EXPECT_EQ(150, Vec.find_last_in(100, 152)); |
386 | EXPECT_EQ(-1, Vec.find_last_in(100, 150)); |
387 | Vec.set(199); |
388 | EXPECT_EQ(199, Vec.find_last_in(199, 200)); |
389 | Vec.reset(Idx: 199); |
390 | |
391 | // find first unset |
392 | EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); |
393 | EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); |
394 | EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35)); |
395 | |
396 | EXPECT_EQ(0, Vec.find_first_unset_in(0, 10)); |
397 | EXPECT_EQ(1, Vec.find_first_unset_in(1, 10)); |
398 | EXPECT_EQ(7, Vec.find_first_unset_in(5, 25)); |
399 | EXPECT_EQ(151, Vec.find_first_unset_in(150, 200)); |
400 | EXPECT_EQ(151, Vec.find_first_unset_in(151, 200)); |
401 | EXPECT_EQ(153, Vec.find_first_unset_in(152, 200)); |
402 | EXPECT_EQ(153, Vec.find_first_unset_in(153, 200)); |
403 | EXPECT_EQ(155, Vec.find_first_unset_in(154, 200)); |
404 | EXPECT_EQ(155, Vec.find_first_unset_in(155, 200)); |
405 | EXPECT_EQ(199, Vec.find_first_unset_in(199, 200)); |
406 | |
407 | // find last unset |
408 | EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); |
409 | EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); |
410 | EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35)); |
411 | |
412 | EXPECT_EQ(9, Vec.find_last_unset_in(0, 10)); |
413 | EXPECT_EQ(8, Vec.find_last_unset_in(0, 9)); |
414 | EXPECT_EQ(2, Vec.find_last_unset_in(0, 7)); |
415 | EXPECT_EQ(149, Vec.find_last_unset_in(100, 151)); |
416 | EXPECT_EQ(151, Vec.find_last_unset_in(100, 152)); |
417 | EXPECT_EQ(151, Vec.find_last_unset_in(100, 153)); |
418 | EXPECT_EQ(153, Vec.find_last_unset_in(100, 154)); |
419 | EXPECT_EQ(153, Vec.find_last_unset_in(100, 155)); |
420 | EXPECT_EQ(155, Vec.find_last_unset_in(100, 156)); |
421 | EXPECT_EQ(199, Vec.find_last_unset_in(199, 200)); |
422 | } |
423 | |
424 | TEST(BitVectorTest, FindInRangeSingleWord) { |
425 | // When the bit vector contains only a single word, this is slightly different |
426 | // than when the bit vector contains multiple words, because masks are applied |
427 | // to the front and back of the same word. So make sure this works. |
428 | BitVector Vec; |
429 | |
430 | Vec.resize(N: 25); |
431 | Vec.set(I: 2, E: 4); |
432 | Vec.set(I: 6, E: 9); |
433 | Vec.set(I: 12, E: 15); |
434 | Vec.set(19); |
435 | Vec.set(21); |
436 | Vec.set(23); |
437 | |
438 | // find first |
439 | EXPECT_EQ(-1, Vec.find_first_in(0, 0)); |
440 | EXPECT_EQ(-1, Vec.find_first_in(24, 24)); |
441 | EXPECT_EQ(-1, Vec.find_first_in(9, 12)); |
442 | |
443 | EXPECT_EQ(2, Vec.find_first_in(0, 10)); |
444 | EXPECT_EQ(6, Vec.find_first_in(4, 10)); |
445 | EXPECT_EQ(19, Vec.find_first_in(18, 25)); |
446 | EXPECT_EQ(21, Vec.find_first_in(20, 25)); |
447 | EXPECT_EQ(23, Vec.find_first_in(22, 25)); |
448 | EXPECT_EQ(-1, Vec.find_first_in(24, 25)); |
449 | |
450 | // find last |
451 | EXPECT_EQ(-1, Vec.find_last_in(0, 0)); |
452 | EXPECT_EQ(-1, Vec.find_last_in(24, 24)); |
453 | EXPECT_EQ(-1, Vec.find_last_in(9, 12)); |
454 | |
455 | EXPECT_EQ(8, Vec.find_last_in(0, 10)); |
456 | EXPECT_EQ(3, Vec.find_last_in(0, 6)); |
457 | EXPECT_EQ(23, Vec.find_last_in(18, 25)); |
458 | EXPECT_EQ(21, Vec.find_last_in(18, 23)); |
459 | EXPECT_EQ(19, Vec.find_last_in(18, 21)); |
460 | EXPECT_EQ(-1, Vec.find_last_in(18, 19)); |
461 | |
462 | // find first unset |
463 | EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); |
464 | EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); |
465 | EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9)); |
466 | |
467 | EXPECT_EQ(0, Vec.find_first_unset_in(0, 6)); |
468 | EXPECT_EQ(1, Vec.find_first_unset_in(1, 6)); |
469 | EXPECT_EQ(9, Vec.find_first_unset_in(7, 13)); |
470 | EXPECT_EQ(18, Vec.find_first_unset_in(18, 25)); |
471 | EXPECT_EQ(20, Vec.find_first_unset_in(19, 25)); |
472 | EXPECT_EQ(20, Vec.find_first_unset_in(20, 25)); |
473 | EXPECT_EQ(22, Vec.find_first_unset_in(21, 25)); |
474 | EXPECT_EQ(22, Vec.find_first_unset_in(22, 25)); |
475 | EXPECT_EQ(24, Vec.find_first_unset_in(23, 25)); |
476 | EXPECT_EQ(24, Vec.find_first_unset_in(24, 25)); |
477 | |
478 | // find last unset |
479 | EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); |
480 | EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); |
481 | EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9)); |
482 | |
483 | EXPECT_EQ(5, Vec.find_last_unset_in(0, 6)); |
484 | EXPECT_EQ(4, Vec.find_last_unset_in(0, 5)); |
485 | EXPECT_EQ(1, Vec.find_last_unset_in(0, 4)); |
486 | EXPECT_EQ(11, Vec.find_last_unset_in(7, 13)); |
487 | EXPECT_EQ(24, Vec.find_last_unset_in(18, 25)); |
488 | EXPECT_EQ(22, Vec.find_last_unset_in(18, 24)); |
489 | EXPECT_EQ(22, Vec.find_last_unset_in(18, 23)); |
490 | EXPECT_EQ(20, Vec.find_last_unset_in(18, 22)); |
491 | EXPECT_EQ(20, Vec.find_last_unset_in(18, 21)); |
492 | EXPECT_EQ(18, Vec.find_last_unset_in(18, 20)); |
493 | EXPECT_EQ(18, Vec.find_last_unset_in(18, 19)); |
494 | } |
495 | |
496 | TYPED_TEST(BitVectorTest, CompoundAssignment) { |
497 | TypeParam A; |
498 | A.resize(10); |
499 | A.set(4); |
500 | A.set(7); |
501 | |
502 | TypeParam B; |
503 | B.resize(50); |
504 | B.set(5); |
505 | B.set(18); |
506 | |
507 | A |= B; |
508 | EXPECT_TRUE(A.test(4)); |
509 | EXPECT_TRUE(A.test(5)); |
510 | EXPECT_TRUE(A.test(7)); |
511 | EXPECT_TRUE(A.test(18)); |
512 | EXPECT_EQ(4U, A.count()); |
513 | EXPECT_EQ(50U, A.size()); |
514 | |
515 | B.resize(10); |
516 | B.set(); |
517 | B.reset(2); |
518 | B.reset(7); |
519 | A &= B; |
520 | EXPECT_FALSE(A.test(2)); |
521 | EXPECT_FALSE(A.test(7)); |
522 | EXPECT_TRUE(A.test(4)); |
523 | EXPECT_TRUE(A.test(5)); |
524 | EXPECT_EQ(2U, A.count()); |
525 | EXPECT_EQ(50U, A.size()); |
526 | |
527 | B.resize(100); |
528 | B.set(); |
529 | |
530 | A ^= B; |
531 | EXPECT_TRUE(A.test(2)); |
532 | EXPECT_TRUE(A.test(7)); |
533 | EXPECT_EQ(98U, A.count()); |
534 | EXPECT_EQ(100U, A.size()); |
535 | } |
536 | |
537 | // Test SmallBitVector operations with mixed big/small representations |
538 | TYPED_TEST(BitVectorTest, MixedBigSmall) { |
539 | { |
540 | TypeParam Big; |
541 | TypeParam Small; |
542 | |
543 | Big.reserve(100); |
544 | Big.resize(20); |
545 | Small.resize(10); |
546 | |
547 | Small.set(0); |
548 | Small.set(1); |
549 | Big.set(0); |
550 | Big.set(2); |
551 | Big.set(16); |
552 | |
553 | Small &= Big; |
554 | EXPECT_TRUE(Small.test(0)); |
555 | EXPECT_EQ(1u, Small.count()); |
556 | // FIXME BitVector and SmallBitVector behave differently here. |
557 | // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size()) |
558 | // but BitVector does not. |
559 | // EXPECT_EQ(20u, Small.size()); |
560 | } |
561 | |
562 | { |
563 | TypeParam Big; |
564 | TypeParam Small; |
565 | |
566 | Big.reserve(100); |
567 | Big.resize(20); |
568 | Small.resize(10); |
569 | |
570 | Small.set(0); |
571 | Small.set(1); |
572 | Big.set(0); |
573 | Big.set(2); |
574 | Big.set(16); |
575 | |
576 | Big &= Small; |
577 | EXPECT_TRUE(Big.test(0)); |
578 | EXPECT_EQ(1u, Big.count()); |
579 | // FIXME BitVector and SmallBitVector behave differently here. |
580 | // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size()) |
581 | // but BitVector does not. |
582 | // EXPECT_EQ(20u, Big.size()); |
583 | } |
584 | |
585 | { |
586 | TypeParam Big; |
587 | TypeParam Small; |
588 | |
589 | Big.reserve(100); |
590 | Big.resize(20); |
591 | Small.resize(10); |
592 | |
593 | Small.set(0); |
594 | Small.set(1); |
595 | Big.set(0); |
596 | Big.set(2); |
597 | Big.set(16); |
598 | |
599 | Small |= Big; |
600 | EXPECT_TRUE(Small.test(0)); |
601 | EXPECT_TRUE(Small.test(1)); |
602 | EXPECT_TRUE(Small.test(2)); |
603 | EXPECT_TRUE(Small.test(16)); |
604 | EXPECT_EQ(4u, Small.count()); |
605 | EXPECT_EQ(20u, Small.size()); |
606 | } |
607 | |
608 | { |
609 | TypeParam Big; |
610 | TypeParam Small; |
611 | |
612 | Big.reserve(100); |
613 | Big.resize(20); |
614 | Small.resize(10); |
615 | |
616 | Small.set(0); |
617 | Small.set(1); |
618 | Big.set(0); |
619 | Big.set(2); |
620 | Big.set(16); |
621 | |
622 | Big |= Small; |
623 | EXPECT_TRUE(Big.test(0)); |
624 | EXPECT_TRUE(Big.test(1)); |
625 | EXPECT_TRUE(Big.test(2)); |
626 | EXPECT_TRUE(Big.test(16)); |
627 | EXPECT_EQ(4u, Big.count()); |
628 | EXPECT_EQ(20u, Big.size()); |
629 | } |
630 | |
631 | { |
632 | TypeParam Big; |
633 | TypeParam Small; |
634 | |
635 | Big.reserve(100); |
636 | Big.resize(20); |
637 | Small.resize(10); |
638 | |
639 | Small.set(0); |
640 | Small.set(1); |
641 | Big.set(0); |
642 | Big.set(2); |
643 | Big.set(16); |
644 | |
645 | Small ^= Big; |
646 | EXPECT_TRUE(Small.test(1)); |
647 | EXPECT_TRUE(Small.test(2)); |
648 | EXPECT_TRUE(Small.test(16)); |
649 | EXPECT_EQ(3u, Small.count()); |
650 | EXPECT_EQ(20u, Small.size()); |
651 | } |
652 | |
653 | { |
654 | TypeParam Big; |
655 | TypeParam Small; |
656 | |
657 | Big.reserve(100); |
658 | Big.resize(20); |
659 | Small.resize(10); |
660 | |
661 | Small.set(0); |
662 | Small.set(1); |
663 | Big.set(0); |
664 | Big.set(2); |
665 | Big.set(16); |
666 | |
667 | Big ^= Small; |
668 | EXPECT_TRUE(Big.test(1)); |
669 | EXPECT_TRUE(Big.test(2)); |
670 | EXPECT_TRUE(Big.test(16)); |
671 | EXPECT_EQ(3u, Big.count()); |
672 | EXPECT_EQ(20u, Big.size()); |
673 | } |
674 | |
675 | { |
676 | TypeParam Big; |
677 | TypeParam Small; |
678 | |
679 | Big.reserve(100); |
680 | Big.resize(20); |
681 | Small.resize(10); |
682 | |
683 | Small.set(0); |
684 | Small.set(1); |
685 | Big.set(0); |
686 | Big.set(2); |
687 | Big.set(16); |
688 | |
689 | Small.reset(Big); |
690 | EXPECT_TRUE(Small.test(1)); |
691 | EXPECT_EQ(1u, Small.count()); |
692 | EXPECT_EQ(10u, Small.size()); |
693 | } |
694 | |
695 | { |
696 | TypeParam Big; |
697 | TypeParam Small; |
698 | |
699 | Big.reserve(100); |
700 | Big.resize(20); |
701 | Small.resize(10); |
702 | |
703 | Small.set(0); |
704 | Small.set(1); |
705 | Big.set(0); |
706 | Big.set(2); |
707 | Big.set(16); |
708 | |
709 | Big.reset(Small); |
710 | EXPECT_TRUE(Big.test(2)); |
711 | EXPECT_TRUE(Big.test(16)); |
712 | EXPECT_EQ(2u, Big.count()); |
713 | EXPECT_EQ(20u, Big.size()); |
714 | } |
715 | |
716 | { |
717 | TypeParam Big; |
718 | TypeParam Small; |
719 | |
720 | Big.reserve(100); |
721 | Big.resize(10); |
722 | Small.resize(10); |
723 | |
724 | Small.set(0); |
725 | Small.set(1); |
726 | Big.set(0); |
727 | |
728 | EXPECT_FALSE(Big == Small); |
729 | EXPECT_FALSE(Small == Big); |
730 | Big.set(1); |
731 | EXPECT_TRUE(Big == Small); |
732 | EXPECT_TRUE(Small == Big); |
733 | } |
734 | |
735 | { |
736 | TypeParam Big; |
737 | TypeParam Small; |
738 | |
739 | Big.reserve(100); |
740 | Big.resize(20); |
741 | Small.resize(10); |
742 | |
743 | Small.set(0); |
744 | Big.set(1); |
745 | |
746 | EXPECT_FALSE(Small.anyCommon(Big)); |
747 | EXPECT_FALSE(Big.anyCommon(Small)); |
748 | Big.set(0); |
749 | EXPECT_TRUE(Small.anyCommon(Big)); |
750 | EXPECT_TRUE(Big.anyCommon(Small)); |
751 | } |
752 | |
753 | { |
754 | TypeParam Big; |
755 | TypeParam Small; |
756 | |
757 | Big.reserve(100); |
758 | Big.resize(10); |
759 | Small.resize(10); |
760 | |
761 | Small.set(0); |
762 | Small.set(1); |
763 | Big.set(0); |
764 | |
765 | EXPECT_TRUE(Small.test(Big)); |
766 | EXPECT_FALSE(Big.test(Small)); |
767 | Big.set(1); |
768 | EXPECT_FALSE(Small.test(Big)); |
769 | EXPECT_FALSE(Big.test(Small)); |
770 | } |
771 | } |
772 | |
773 | TYPED_TEST(BitVectorTest, ProxyIndex) { |
774 | TypeParam Vec(3); |
775 | EXPECT_TRUE(Vec.none()); |
776 | Vec[0] = Vec[1] = Vec[2] = true; |
777 | EXPECT_EQ(Vec.size(), Vec.count()); |
778 | Vec[2] = Vec[1] = Vec[0] = false; |
779 | EXPECT_TRUE(Vec.none()); |
780 | } |
781 | |
782 | |
783 | TYPED_TEST(BitVectorTest, PortableBitMask) { |
784 | TypeParam A; |
785 | const uint32_t Mask1[] = { 0x80000000, 6, 5 }; |
786 | |
787 | A.resize(10); |
788 | A.setBitsInMask(Mask1, 1); |
789 | EXPECT_EQ(10u, A.size()); |
790 | EXPECT_FALSE(A.test(0)); |
791 | |
792 | A.resize(32); |
793 | A.setBitsInMask(Mask1, 1); |
794 | EXPECT_FALSE(A.test(0)); |
795 | EXPECT_TRUE(A.test(31)); |
796 | EXPECT_EQ(1u, A.count()); |
797 | |
798 | A.resize(33); |
799 | A.setBitsInMask(Mask1, 1); |
800 | EXPECT_EQ(1u, A.count()); |
801 | A.setBitsInMask(Mask1, 2); |
802 | EXPECT_EQ(1u, A.count()); |
803 | |
804 | A.resize(34); |
805 | A.setBitsInMask(Mask1, 2); |
806 | EXPECT_EQ(2u, A.count()); |
807 | |
808 | A.resize(65); |
809 | A.setBitsInMask(Mask1, 3); |
810 | EXPECT_EQ(4u, A.count()); |
811 | |
812 | A.setBitsNotInMask(Mask1, 1); |
813 | EXPECT_EQ(32u+3u, A.count()); |
814 | |
815 | A.setBitsNotInMask(Mask1, 3); |
816 | EXPECT_EQ(65u, A.count()); |
817 | |
818 | A.resize(96); |
819 | EXPECT_EQ(65u, A.count()); |
820 | |
821 | A.clear(); |
822 | A.resize(128); |
823 | A.setBitsNotInMask(Mask1, 3); |
824 | EXPECT_EQ(96u-5u, A.count()); |
825 | |
826 | A.clearBitsNotInMask(Mask1, 1); |
827 | EXPECT_EQ(64-4u, A.count()); |
828 | } |
829 | |
830 | TYPED_TEST(BitVectorTest, BinOps) { |
831 | TypeParam A; |
832 | TypeParam B; |
833 | |
834 | A.resize(65); |
835 | EXPECT_FALSE(A.anyCommon(B)); |
836 | EXPECT_FALSE(B.anyCommon(B)); |
837 | |
838 | B.resize(64); |
839 | A.set(64); |
840 | EXPECT_FALSE(A.anyCommon(B)); |
841 | EXPECT_FALSE(B.anyCommon(A)); |
842 | |
843 | B.set(63); |
844 | EXPECT_FALSE(A.anyCommon(B)); |
845 | EXPECT_FALSE(B.anyCommon(A)); |
846 | |
847 | A.set(63); |
848 | EXPECT_TRUE(A.anyCommon(B)); |
849 | EXPECT_TRUE(B.anyCommon(A)); |
850 | |
851 | B.resize(70); |
852 | B.set(64); |
853 | B.reset(63); |
854 | A.resize(64); |
855 | EXPECT_FALSE(A.anyCommon(B)); |
856 | EXPECT_FALSE(B.anyCommon(A)); |
857 | } |
858 | |
859 | typedef std::vector<std::pair<int, int>> RangeList; |
860 | |
861 | template <typename VecType> |
862 | static inline VecType createBitVector(uint32_t Size, |
863 | const RangeList &setRanges) { |
864 | VecType V; |
865 | V.resize(Size); |
866 | for (auto &R : setRanges) |
867 | V.set(R.first, R.second); |
868 | return V; |
869 | } |
870 | |
871 | TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) { |
872 | // Test that shift ops work when the desired shift amount is less |
873 | // than one word. |
874 | |
875 | // 1. Case where the number of bits in the BitVector also fit into a single |
876 | // word. |
877 | TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}}); |
878 | TypeParam B = A; |
879 | |
880 | EXPECT_EQ(4U, A.count()); |
881 | EXPECT_TRUE(A.test(2)); |
882 | EXPECT_TRUE(A.test(3)); |
883 | EXPECT_TRUE(A.test(8)); |
884 | EXPECT_TRUE(A.test(9)); |
885 | |
886 | A >>= 1; |
887 | EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A); |
888 | |
889 | A <<= 1; |
890 | EXPECT_EQ(B, A); |
891 | |
892 | A >>= 10; |
893 | EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); |
894 | |
895 | A = B; |
896 | A <<= 10; |
897 | EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); |
898 | |
899 | // 2. Case where the number of bits in the BitVector do not fit into a single |
900 | // word. |
901 | |
902 | // 31----------------------------------------------------------------------0 |
903 | // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 |
904 | A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}}); |
905 | EXPECT_EQ(40U, A.size()); |
906 | EXPECT_EQ(22U, A.count()); |
907 | |
908 | // 2a. Make sure that left shifting some 1 bits out of the vector works. |
909 | // 31----------------------------------------------------------------------0 |
910 | // Before: |
911 | // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 |
912 | // After: |
913 | // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 |
914 | A <<= 9; |
915 | EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A); |
916 | |
917 | // 2b. Make sure that keeping the number of one bits unchanged works. |
918 | // 31----------------------------------------------------------------------0 |
919 | // Before: |
920 | // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 |
921 | // After: |
922 | // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 |
923 | A >>= 6; |
924 | EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A); |
925 | |
926 | // 2c. Make sure that right shifting some 1 bits out of the vector works. |
927 | // 31----------------------------------------------------------------------0 |
928 | // Before: |
929 | // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 |
930 | // After: |
931 | // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111 |
932 | A >>= 10; |
933 | EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A); |
934 | |
935 | // 3. Big test. |
936 | A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); |
937 | A <<= 29; |
938 | EXPECT_EQ(createBitVector<TypeParam>( |
939 | 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}), |
940 | A); |
941 | } |
942 | |
943 | TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) { |
944 | // Test that shift ops work when the desired shift amount is greater than or |
945 | // equal to the size of a single word. |
946 | auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); |
947 | |
948 | // Make a copy so we can re-use it later. |
949 | auto B = A; |
950 | |
951 | // 1. Shift left by an exact multiple of the word size. This should invoke |
952 | // only a memmove and no per-word bit operations. |
953 | A <<= 64; |
954 | auto Expected = createBitVector<TypeParam>( |
955 | 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}}); |
956 | EXPECT_EQ(Expected, A); |
957 | |
958 | // 2. Shift left by a non multiple of the word size. This should invoke both |
959 | // a memmove and per-word bit operations. |
960 | A = B; |
961 | A <<= 93; |
962 | EXPECT_EQ(createBitVector<TypeParam>( |
963 | 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}), |
964 | A); |
965 | |
966 | // 1. Shift right by an exact multiple of the word size. This should invoke |
967 | // only a memmove and no per-word bit operations. |
968 | A = B; |
969 | A >>= 64; |
970 | EXPECT_EQ( |
971 | createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A); |
972 | |
973 | // 2. Shift left by a non multiple of the word size. This should invoke both |
974 | // a memmove and per-word bit operations. |
975 | A = B; |
976 | A >>= 93; |
977 | EXPECT_EQ( |
978 | createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A); |
979 | } |
980 | |
981 | TYPED_TEST(BitVectorTest, RangeOps) { |
982 | TypeParam A; |
983 | A.resize(256); |
984 | A.reset(); |
985 | A.set(1, 255); |
986 | |
987 | EXPECT_FALSE(A.test(0)); |
988 | EXPECT_TRUE( A.test(1)); |
989 | EXPECT_TRUE( A.test(23)); |
990 | EXPECT_TRUE( A.test(254)); |
991 | EXPECT_FALSE(A.test(255)); |
992 | |
993 | TypeParam B; |
994 | B.resize(256); |
995 | B.set(); |
996 | B.reset(1, 255); |
997 | |
998 | EXPECT_TRUE( B.test(0)); |
999 | EXPECT_FALSE(B.test(1)); |
1000 | EXPECT_FALSE(B.test(23)); |
1001 | EXPECT_FALSE(B.test(254)); |
1002 | EXPECT_TRUE( B.test(255)); |
1003 | |
1004 | TypeParam C; |
1005 | C.resize(3); |
1006 | C.reset(); |
1007 | C.set(0, 1); |
1008 | |
1009 | EXPECT_TRUE(C.test(0)); |
1010 | EXPECT_FALSE( C.test(1)); |
1011 | EXPECT_FALSE( C.test(2)); |
1012 | |
1013 | TypeParam D; |
1014 | D.resize(3); |
1015 | D.set(); |
1016 | D.reset(0, 1); |
1017 | |
1018 | EXPECT_FALSE(D.test(0)); |
1019 | EXPECT_TRUE( D.test(1)); |
1020 | EXPECT_TRUE( D.test(2)); |
1021 | |
1022 | TypeParam E; |
1023 | E.resize(128); |
1024 | E.reset(); |
1025 | E.set(1, 33); |
1026 | |
1027 | EXPECT_FALSE(E.test(0)); |
1028 | EXPECT_TRUE( E.test(1)); |
1029 | EXPECT_TRUE( E.test(32)); |
1030 | EXPECT_FALSE(E.test(33)); |
1031 | |
1032 | TypeParam BufferOverrun; |
1033 | unsigned size = sizeof(unsigned long) * 8; |
1034 | BufferOverrun.resize(size); |
1035 | BufferOverrun.reset(0, size); |
1036 | BufferOverrun.set(0, size); |
1037 | } |
1038 | |
1039 | TYPED_TEST(BitVectorTest, CompoundTestReset) { |
1040 | TypeParam A(50, true); |
1041 | TypeParam B(50, false); |
1042 | |
1043 | TypeParam C(100, true); |
1044 | TypeParam D(100, false); |
1045 | |
1046 | EXPECT_FALSE(A.test(A)); |
1047 | EXPECT_TRUE(A.test(B)); |
1048 | EXPECT_FALSE(A.test(C)); |
1049 | EXPECT_TRUE(A.test(D)); |
1050 | EXPECT_FALSE(B.test(A)); |
1051 | EXPECT_FALSE(B.test(B)); |
1052 | EXPECT_FALSE(B.test(C)); |
1053 | EXPECT_FALSE(B.test(D)); |
1054 | EXPECT_TRUE(C.test(A)); |
1055 | EXPECT_TRUE(C.test(B)); |
1056 | EXPECT_FALSE(C.test(C)); |
1057 | EXPECT_TRUE(C.test(D)); |
1058 | |
1059 | A.reset(B); |
1060 | A.reset(D); |
1061 | EXPECT_TRUE(A.all()); |
1062 | A.reset(A); |
1063 | EXPECT_TRUE(A.none()); |
1064 | A.set(); |
1065 | A.reset(C); |
1066 | EXPECT_TRUE(A.none()); |
1067 | A.set(); |
1068 | |
1069 | C.reset(A); |
1070 | EXPECT_EQ(50, C.find_first()); |
1071 | C.reset(C); |
1072 | EXPECT_TRUE(C.none()); |
1073 | } |
1074 | |
1075 | TYPED_TEST(BitVectorTest, MoveConstructor) { |
1076 | TypeParam A(10, true); |
1077 | TypeParam B(std::move(A)); |
1078 | // Check that the move ctor leaves the moved-from object in a valid state. |
1079 | // The following line used to crash. |
1080 | A = B; |
1081 | |
1082 | TypeParam C(10, true); |
1083 | EXPECT_EQ(C, A); |
1084 | EXPECT_EQ(C, B); |
1085 | } |
1086 | |
1087 | TYPED_TEST(BitVectorTest, MoveAssignment) { |
1088 | TypeParam A(10, true); |
1089 | TypeParam B; |
1090 | B = std::move(A); |
1091 | // Check that move assignment leaves the moved-from object in a valid state. |
1092 | // The following line used to crash. |
1093 | A = B; |
1094 | |
1095 | TypeParam C(10, true); |
1096 | EXPECT_EQ(C, A); |
1097 | EXPECT_EQ(C, B); |
1098 | } |
1099 | |
1100 | template<class TypeParam> |
1101 | static void testEmpty(const TypeParam &A) { |
1102 | EXPECT_TRUE(A.empty()); |
1103 | EXPECT_EQ((size_t)0, A.size()); |
1104 | EXPECT_EQ((size_t)0, A.count()); |
1105 | EXPECT_FALSE(A.any()); |
1106 | EXPECT_TRUE(A.all()); |
1107 | EXPECT_TRUE(A.none()); |
1108 | EXPECT_EQ(-1, A.find_first()); |
1109 | EXPECT_EQ(A, TypeParam()); |
1110 | } |
1111 | |
1112 | /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0 |
1113 | TYPED_TEST(BitVectorTest, EmptyVector) { |
1114 | TypeParam A; |
1115 | testEmpty(A); |
1116 | |
1117 | TypeParam B; |
1118 | B.reset(); |
1119 | testEmpty(B); |
1120 | |
1121 | TypeParam C; |
1122 | C.clear(); |
1123 | testEmpty(C); |
1124 | |
1125 | TypeParam D(A); |
1126 | testEmpty(D); |
1127 | |
1128 | TypeParam E; |
1129 | E = A; |
1130 | testEmpty(E); |
1131 | |
1132 | TypeParam F; |
1133 | E.reset(A); |
1134 | testEmpty(E); |
1135 | } |
1136 | |
1137 | /// Make sure calling getData() is legal even on an empty BitVector |
1138 | TYPED_TEST(BitVectorTest, EmptyVectorGetData) { |
1139 | BitVector A; |
1140 | testEmpty(A); |
1141 | auto B = A.getData(); |
1142 | EXPECT_TRUE(B.empty()); |
1143 | } |
1144 | |
1145 | TYPED_TEST(BitVectorTest, Iterators) { |
1146 | TypeParam Singleton(1, true); |
1147 | EXPECT_EQ(std::next(Singleton.set_bits_begin()), Singleton.set_bits_end()); |
1148 | |
1149 | TypeParam Filled(10, true); |
1150 | EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end()); |
1151 | unsigned Counter = 0; |
1152 | for (unsigned Bit : Filled.set_bits()) |
1153 | EXPECT_EQ(Bit, Counter++); |
1154 | |
1155 | TypeParam Empty; |
1156 | EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end()); |
1157 | int BitCount = 0; |
1158 | for (unsigned Bit : Empty.set_bits()) { |
1159 | (void)Bit; |
1160 | BitCount++; |
1161 | } |
1162 | ASSERT_EQ(BitCount, 0); |
1163 | |
1164 | TypeParam ToFill(100, false); |
1165 | ToFill.set(0); |
1166 | EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end()); |
1167 | EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end()); |
1168 | EXPECT_EQ(*ToFill.set_bits_begin(), 0U); |
1169 | ToFill.reset(0); |
1170 | EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end()); |
1171 | |
1172 | const unsigned List[] = {1, 10, 25, 99}; |
1173 | for (unsigned Num : List) |
1174 | ToFill.set(Num); |
1175 | unsigned i = 0; |
1176 | for (unsigned Bit : ToFill.set_bits()) |
1177 | EXPECT_EQ(List[i++], Bit); |
1178 | } |
1179 | |
1180 | TYPED_TEST(BitVectorTest, PushBack) { |
1181 | TypeParam Vec(10, false); |
1182 | EXPECT_EQ(-1, Vec.find_first()); |
1183 | EXPECT_EQ(10U, Vec.size()); |
1184 | EXPECT_EQ(0U, Vec.count()); |
1185 | EXPECT_EQ(false, Vec.back()); |
1186 | |
1187 | Vec.push_back(true); |
1188 | EXPECT_EQ(10, Vec.find_first()); |
1189 | EXPECT_EQ(11U, Vec.size()); |
1190 | EXPECT_EQ(1U, Vec.count()); |
1191 | EXPECT_EQ(true, Vec.back()); |
1192 | |
1193 | Vec.push_back(false); |
1194 | EXPECT_EQ(10, Vec.find_first()); |
1195 | EXPECT_EQ(12U, Vec.size()); |
1196 | EXPECT_EQ(1U, Vec.count()); |
1197 | EXPECT_EQ(false, Vec.back()); |
1198 | |
1199 | Vec.push_back(true); |
1200 | EXPECT_EQ(10, Vec.find_first()); |
1201 | EXPECT_EQ(13U, Vec.size()); |
1202 | EXPECT_EQ(2U, Vec.count()); |
1203 | EXPECT_EQ(true, Vec.back()); |
1204 | |
1205 | // Add a lot of values to cause reallocation. |
1206 | for (int i = 0; i != 100; ++i) { |
1207 | Vec.push_back(true); |
1208 | Vec.push_back(false); |
1209 | } |
1210 | EXPECT_EQ(10, Vec.find_first()); |
1211 | EXPECT_EQ(213U, Vec.size()); |
1212 | EXPECT_EQ(102U, Vec.count()); |
1213 | } |
1214 | |
1215 | TYPED_TEST(BitVectorTest, PopBack) { |
1216 | TypeParam Vec(10, true); |
1217 | EXPECT_EQ(10U, Vec.size()); |
1218 | EXPECT_EQ(10U, Vec.count()); |
1219 | EXPECT_EQ(true, Vec.back()); |
1220 | |
1221 | Vec.pop_back(); |
1222 | EXPECT_EQ(9U, Vec.size()); |
1223 | EXPECT_EQ(9U, Vec.count()); |
1224 | EXPECT_EQ(true, Vec.back()); |
1225 | |
1226 | Vec.push_back(false); |
1227 | EXPECT_EQ(10U, Vec.size()); |
1228 | EXPECT_EQ(9U, Vec.count()); |
1229 | EXPECT_EQ(false, Vec.back()); |
1230 | |
1231 | Vec.pop_back(); |
1232 | EXPECT_EQ(9U, Vec.size()); |
1233 | EXPECT_EQ(9U, Vec.count()); |
1234 | EXPECT_EQ(true, Vec.back()); |
1235 | } |
1236 | |
1237 | TYPED_TEST(BitVectorTest, DenseSet) { |
1238 | DenseSet<TypeParam> Set; |
1239 | TypeParam A(10, true); |
1240 | auto I = Set.insert(A); |
1241 | EXPECT_EQ(true, I.second); |
1242 | |
1243 | TypeParam B(5, true); |
1244 | I = Set.insert(B); |
1245 | EXPECT_EQ(true, I.second); |
1246 | |
1247 | TypeParam C(20, false); |
1248 | C.set(19); |
1249 | I = Set.insert(C); |
1250 | EXPECT_EQ(true, I.second); |
1251 | |
1252 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS |
1253 | TypeParam D; |
1254 | EXPECT_DEATH(Set.insert(D), |
1255 | "Empty/Tombstone value shouldn't be inserted into map!" ); |
1256 | #endif |
1257 | |
1258 | EXPECT_EQ(3U, Set.size()); |
1259 | EXPECT_EQ(1U, Set.count(A)); |
1260 | EXPECT_EQ(1U, Set.count(B)); |
1261 | EXPECT_EQ(1U, Set.count(C)); |
1262 | |
1263 | EXPECT_EQ(true, Set.erase(B)); |
1264 | EXPECT_EQ(2U, Set.size()); |
1265 | |
1266 | EXPECT_EQ(true, Set.erase(C)); |
1267 | EXPECT_EQ(1U, Set.size()); |
1268 | |
1269 | EXPECT_EQ(true, Set.erase(A)); |
1270 | EXPECT_EQ(0U, Set.size()); |
1271 | } |
1272 | |
1273 | /// Test that capacity doesn't affect hashing. |
1274 | TYPED_TEST(BitVectorTest, DenseMapHashing) { |
1275 | using DMI = DenseMapInfo<TypeParam>; |
1276 | { |
1277 | TypeParam A; |
1278 | A.resize(200); |
1279 | A.set(100); |
1280 | |
1281 | TypeParam B; |
1282 | B.resize(200); |
1283 | B.set(100); |
1284 | B.reserve(1000); |
1285 | |
1286 | EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); |
1287 | } |
1288 | { |
1289 | TypeParam A; |
1290 | A.resize(20); |
1291 | A.set(10); |
1292 | |
1293 | TypeParam B; |
1294 | B.resize(20); |
1295 | B.set(10); |
1296 | B.reserve(1000); |
1297 | |
1298 | EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); |
1299 | } |
1300 | } |
1301 | |
1302 | TEST(BitVectoryTest, Apply) { |
1303 | for (int i = 0; i < 2; ++i) { |
1304 | int j = i * 100 + 3; |
1305 | |
1306 | const BitVector x = |
1307 | createBitVector<BitVector>(Size: j + 5, setRanges: {{i, i + 1}, {j - 1, j}}); |
1308 | const BitVector y = createBitVector<BitVector>(Size: j + 5, setRanges: {{i, j}}); |
1309 | const BitVector z = |
1310 | createBitVector<BitVector>(Size: j + 5, setRanges: {{i + 1, i + 2}, {j, j + 1}}); |
1311 | |
1312 | auto op0 = [](auto x) { return ~x; }; |
1313 | BitVector expected0 = x; |
1314 | expected0.flip(); |
1315 | BitVector out0(j - 2); |
1316 | BitVector::apply(f&: op0, Out&: out0, Arg: x); |
1317 | EXPECT_EQ(out0, expected0); |
1318 | |
1319 | auto op1 = [](auto x, auto y) { return x & ~y; }; |
1320 | BitVector expected1 = x; |
1321 | expected1.reset(RHS: y); |
1322 | BitVector out1; |
1323 | BitVector::apply(f&: op1, Out&: out1, Arg: x, Args: y); |
1324 | EXPECT_EQ(out1, expected1); |
1325 | |
1326 | auto op2 = [](auto x, auto y, auto z) { return (x ^ ~y) | z; }; |
1327 | BitVector expected2 = y; |
1328 | expected2.flip(); |
1329 | expected2 ^= x; |
1330 | expected2 |= z; |
1331 | BitVector out2(j + 5); |
1332 | BitVector::apply(f&: op2, Out&: out2, Arg: x, Args: y, Args: z); |
1333 | EXPECT_EQ(out2, expected2); |
1334 | } |
1335 | } |
1336 | |
1337 | |
1338 | } // namespace |
1339 | |