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
TYPED_TEST(BitVectorTest,TrivialOperation)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
TYPED_TEST(BitVectorTest,Equality)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
TYPED_TEST(BitVectorTest,SimpleFindOpsMultiWord)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.
TYPED_TEST(BitVectorTest,SimpleFindOps64Bit)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.
SmallBitVectorIsSmallMode(const SmallBitVector & bv)283 static bool SmallBitVectorIsSmallMode(const SmallBitVector &bv) {
284 return bv.isSmall();
285 }
SmallBitVectorIsSmallMode(const BitVector &)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.
TYPED_TEST(BitVectorTest,SimpleFindOpsSingleWord)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
TEST(BitVectorTest,FindInRangeMultiWord)349 TEST(BitVectorTest, FindInRangeMultiWord) {
350 BitVector Vec;
351
352 Vec.resize(200);
353 Vec.set(3, 7);
354 Vec.set(24, 35);
355 Vec.set(50, 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(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(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
TEST(BitVectorTest,FindInRangeSingleWord)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(25);
431 Vec.set(2, 4);
432 Vec.set(6, 9);
433 Vec.set(12, 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
TYPED_TEST(BitVectorTest,CompoundAssignment)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
TYPED_TEST(BitVectorTest,MixedBigSmall)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
TYPED_TEST(BitVectorTest,ProxyIndex)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
TYPED_TEST(BitVectorTest,PortableBitMask)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
TYPED_TEST(BitVectorTest,BinOps)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>
createBitVector(uint32_t Size,const RangeList & setRanges)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
TYPED_TEST(BitVectorTest,ShiftOpsSingleWord)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
TYPED_TEST(BitVectorTest,ShiftOpsMultiWord)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
TYPED_TEST(BitVectorTest,RangeOps)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
TYPED_TEST(BitVectorTest,CompoundTestReset)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
TYPED_TEST(BitVectorTest,MoveConstructor)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
TYPED_TEST(BitVectorTest,MoveAssignment)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>
testEmpty(const TypeParam & A)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
TYPED_TEST(BitVectorTest,EmptyVector)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
TYPED_TEST(BitVectorTest,EmptyVectorGetData)1138 TYPED_TEST(BitVectorTest, EmptyVectorGetData) {
1139 BitVector A;
1140 testEmpty(A);
1141 auto B = A.getData();
1142 EXPECT_TRUE(B.empty());
1143 }
1144
TYPED_TEST(BitVectorTest,Iterators)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
TYPED_TEST(BitVectorTest,PushBack)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
TYPED_TEST(BitVectorTest,PopBack)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
TYPED_TEST(BitVectorTest,DenseSet)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.
TYPED_TEST(BitVectorTest,DenseMapHashing)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
TEST(BitVectoryTest,Apply)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>(j + 5, {{i, i + 1}, {j - 1, j}});
1308 const BitVector y = createBitVector<BitVector>(j + 5, {{i, j}});
1309 const BitVector z =
1310 createBitVector<BitVector>(j + 5, {{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(op0, out0, x);
1317 EXPECT_EQ(out0, expected0);
1318
1319 auto op1 = [](auto x, auto y) { return x & ~y; };
1320 BitVector expected1 = x;
1321 expected1.reset(y);
1322 BitVector out1;
1323 BitVector::apply(op1, out1, x, 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(op2, out2, x, y, z);
1333 EXPECT_EQ(out2, expected2);
1334 }
1335 }
1336
1337
1338 } // namespace
1339