1 //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Some of these tests fail on PowerPC for unknown reasons.
13 #include "llvm/ADT/BitVector.h"
14 #include "llvm/ADT/SmallBitVector.h"
15 #include "gtest/gtest.h"
23 class BitVectorTest
: public ::testing::Test
{ };
25 // Test both BitVector and SmallBitVector with the same suite of tests.
26 typedef ::testing::Types
<BitVector
, SmallBitVector
> BitVectorTestTypes
;
27 TYPED_TEST_CASE(BitVectorTest
, BitVectorTestTypes
);
29 TYPED_TEST(BitVectorTest
, TrivialOperation
) {
31 EXPECT_EQ(0U, Vec
.count());
32 EXPECT_EQ(0U, Vec
.size());
33 EXPECT_FALSE(Vec
.any());
34 EXPECT_TRUE(Vec
.all());
35 EXPECT_TRUE(Vec
.none());
36 EXPECT_TRUE(Vec
.empty());
39 EXPECT_EQ(5U, Vec
.count());
40 EXPECT_EQ(5U, Vec
.size());
41 EXPECT_TRUE(Vec
.any());
42 EXPECT_TRUE(Vec
.all());
43 EXPECT_FALSE(Vec
.none());
44 EXPECT_FALSE(Vec
.empty());
47 EXPECT_EQ(5U, Vec
.count());
48 EXPECT_EQ(11U, Vec
.size());
49 EXPECT_TRUE(Vec
.any());
50 EXPECT_FALSE(Vec
.all());
51 EXPECT_FALSE(Vec
.none());
52 EXPECT_FALSE(Vec
.empty());
56 EXPECT_EQ(6U, Inv
.count());
57 EXPECT_EQ(11U, Inv
.size());
58 EXPECT_TRUE(Inv
.any());
59 EXPECT_FALSE(Inv
.all());
60 EXPECT_FALSE(Inv
.none());
61 EXPECT_FALSE(Inv
.empty());
63 EXPECT_FALSE(Inv
== Vec
);
64 EXPECT_TRUE(Inv
!= Vec
);
66 EXPECT_TRUE(Inv
== Vec
);
67 EXPECT_FALSE(Inv
!= Vec
);
69 // Add some "interesting" data to Vec.
71 Vec
.resize(25, false);
73 Vec
.resize(29, false);
75 Vec
.resize(57, false);
77 for (unsigned i
= Vec
.find_first(); i
!= -1u; i
= Vec
.find_next(i
)) {
80 EXPECT_TRUE(Vec
.test(i
));
82 EXPECT_EQ(Count
, Vec
.count());
83 EXPECT_EQ(Count
, 23u);
86 EXPECT_FALSE(Vec
[56]);
87 Vec
.resize(61, false);
90 TypeParam
Alt(3, false);
93 EXPECT_TRUE(Copy
== Alt
);
94 EXPECT_TRUE(Vec
.size() == 6);
95 EXPECT_TRUE(Vec
.count() == 3);
96 EXPECT_TRUE(Vec
.find_first() == 3);
99 // Add some more "interesting" data.
100 Vec
.resize(68, true);
101 Vec
.resize(78, false);
102 Vec
.resize(89, true);
103 Vec
.resize(90, false);
104 Vec
.resize(91, true);
105 Vec
.resize(130, false);
107 for (unsigned i
= Vec
.find_first(); i
!= -1u; i
= Vec
.find_next(i
)) {
110 EXPECT_TRUE(Vec
.test(i
));
112 EXPECT_EQ(Count
, Vec
.count());
113 EXPECT_EQ(Count
, 42u);
114 EXPECT_FALSE(Vec
[0]);
115 EXPECT_TRUE(Vec
[32]);
116 EXPECT_FALSE(Vec
[60]);
117 EXPECT_FALSE(Vec
[129]);
120 EXPECT_TRUE(Vec
[60]);
121 EXPECT_EQ(Count
+ 1, Vec
.count());
123 EXPECT_FALSE(Vec
[60]);
124 EXPECT_EQ(Count
, Vec
.count());
127 EXPECT_FALSE(Vec
[32]);
128 EXPECT_EQ(Count
- 1, Vec
.count());
130 EXPECT_TRUE(Vec
[32]);
131 EXPECT_EQ(Count
, Vec
.count());
134 EXPECT_EQ(Vec
.size() - Count
, Vec
.count());
137 EXPECT_EQ(0U, Vec
.count());
138 EXPECT_EQ(130U, Vec
.size());
139 EXPECT_FALSE(Vec
.any());
140 EXPECT_FALSE(Vec
.all());
141 EXPECT_TRUE(Vec
.none());
142 EXPECT_FALSE(Vec
.empty());
145 EXPECT_EQ(130U, Vec
.count());
146 EXPECT_EQ(130U, Vec
.size());
147 EXPECT_TRUE(Vec
.any());
148 EXPECT_TRUE(Vec
.all());
149 EXPECT_FALSE(Vec
.none());
150 EXPECT_FALSE(Vec
.empty());
153 EXPECT_EQ(64U, Vec
.count());
154 EXPECT_EQ(64U, Vec
.size());
155 EXPECT_TRUE(Vec
.any());
156 EXPECT_TRUE(Vec
.all());
157 EXPECT_FALSE(Vec
.none());
158 EXPECT_FALSE(Vec
.empty());
161 EXPECT_EQ(0U, Vec
.count());
162 EXPECT_EQ(64U, Vec
.size());
163 EXPECT_FALSE(Vec
.any());
164 EXPECT_FALSE(Vec
.all());
165 EXPECT_TRUE(Vec
.none());
166 EXPECT_FALSE(Vec
.empty());
168 Inv
= TypeParam().flip();
169 EXPECT_EQ(0U, Inv
.count());
170 EXPECT_EQ(0U, Inv
.size());
171 EXPECT_FALSE(Inv
.any());
172 EXPECT_TRUE(Inv
.all());
173 EXPECT_TRUE(Inv
.none());
174 EXPECT_TRUE(Inv
.empty());
177 EXPECT_EQ(0U, Vec
.count());
178 EXPECT_EQ(0U, Vec
.size());
179 EXPECT_FALSE(Vec
.any());
180 EXPECT_TRUE(Vec
.all());
181 EXPECT_TRUE(Vec
.none());
182 EXPECT_TRUE(Vec
.empty());
185 TYPED_TEST(BitVectorTest
, SimpleFindOps
) {
186 // Test finding in an empty BitVector.
188 EXPECT_EQ(-1, A
.find_first());
189 EXPECT_EQ(-1, A
.find_last());
190 EXPECT_EQ(-1, A
.find_first_unset());
191 EXPECT_EQ(-1, A
.find_last_unset());
193 // Test finding next set and unset bits in a BitVector with multiple words
199 EXPECT_EQ(75, A
.find_last());
200 EXPECT_EQ(12, A
.find_first());
201 EXPECT_EQ(13, A
.find_next(12));
202 EXPECT_EQ(75, A
.find_next(13));
203 EXPECT_EQ(-1, A
.find_next(75));
205 EXPECT_EQ(-1, A
.find_prev(12));
206 EXPECT_EQ(12, A
.find_prev(13));
207 EXPECT_EQ(13, A
.find_prev(75));
208 EXPECT_EQ(75, A
.find_prev(90));
210 EXPECT_EQ(0, A
.find_first_unset());
211 EXPECT_EQ(99, A
.find_last_unset());
212 EXPECT_EQ(14, A
.find_next_unset(11));
213 EXPECT_EQ(14, A
.find_next_unset(12));
214 EXPECT_EQ(14, A
.find_next_unset(13));
215 EXPECT_EQ(16, A
.find_next_unset(15));
216 EXPECT_EQ(76, A
.find_next_unset(74));
217 EXPECT_EQ(76, A
.find_next_unset(75));
218 EXPECT_EQ(-1, A
.find_next_unset(99));
221 EXPECT_EQ(100U, A
.count());
222 EXPECT_EQ(0, A
.find_first());
223 EXPECT_EQ(-1, A
.find_first_unset());
224 EXPECT_EQ(-1, A
.find_last_unset());
225 EXPECT_EQ(99, A
.find_last());
226 EXPECT_EQ(99, A
.find_next(98));
229 EXPECT_EQ(0U, A
.count());
230 EXPECT_EQ(-1, A
.find_first());
231 EXPECT_EQ(-1, A
.find_last());
232 EXPECT_EQ(0, A
.find_first_unset());
233 EXPECT_EQ(99, A
.find_last_unset());
234 EXPECT_EQ(99, A
.find_next_unset(98));
236 // Also test with a vector that is small enough to fit in 1 word.
241 EXPECT_EQ(16, A
.find_last());
242 EXPECT_EQ(3, A
.find_first());
243 EXPECT_EQ(3, A
.find_next(1));
244 EXPECT_EQ(4, A
.find_next(3));
245 EXPECT_EQ(16, A
.find_next(4));
246 EXPECT_EQ(-1, A
.find_next(16));
248 EXPECT_EQ(-1, A
.find_prev(3));
249 EXPECT_EQ(3, A
.find_prev(4));
250 EXPECT_EQ(4, A
.find_prev(16));
251 EXPECT_EQ(16, A
.find_prev(18));
253 EXPECT_EQ(0, A
.find_first_unset());
254 EXPECT_EQ(19, A
.find_last_unset());
255 EXPECT_EQ(5, A
.find_next_unset(3));
256 EXPECT_EQ(5, A
.find_next_unset(4));
257 EXPECT_EQ(13, A
.find_next_unset(12));
258 EXPECT_EQ(17, A
.find_next_unset(15));
261 TEST(BitVectorTest
, FindInRangeMultiWord
) {
273 EXPECT_EQ(-1, Vec
.find_first_in(0, 0));
274 EXPECT_EQ(-1, Vec
.find_first_in(24, 24));
275 EXPECT_EQ(-1, Vec
.find_first_in(7, 24));
277 EXPECT_EQ(3, Vec
.find_first_in(0, 10));
278 EXPECT_EQ(4, Vec
.find_first_in(4, 10));
279 EXPECT_EQ(150, Vec
.find_first_in(100, 200));
280 EXPECT_EQ(152, Vec
.find_first_in(151, 200));
281 EXPECT_EQ(154, Vec
.find_first_in(153, 200));
283 EXPECT_EQ(-1, Vec
.find_first_in(155, 200));
285 EXPECT_EQ(199, Vec
.find_first_in(199, 200));
289 EXPECT_EQ(-1, Vec
.find_last_in(0, 0));
290 EXPECT_EQ(-1, Vec
.find_last_in(24, 24));
291 EXPECT_EQ(-1, Vec
.find_last_in(7, 24));
293 EXPECT_EQ(6, Vec
.find_last_in(0, 10));
294 EXPECT_EQ(5, Vec
.find_last_in(0, 6));
295 EXPECT_EQ(154, Vec
.find_last_in(100, 155));
296 EXPECT_EQ(152, Vec
.find_last_in(100, 154));
297 EXPECT_EQ(150, Vec
.find_last_in(100, 152));
298 EXPECT_EQ(-1, Vec
.find_last_in(100, 150));
300 EXPECT_EQ(199, Vec
.find_last_in(199, 200));
304 EXPECT_EQ(-1, Vec
.find_first_unset_in(0, 0));
305 EXPECT_EQ(-1, Vec
.find_first_unset_in(23, 23));
306 EXPECT_EQ(-1, Vec
.find_first_unset_in(24, 35));
308 EXPECT_EQ(0, Vec
.find_first_unset_in(0, 10));
309 EXPECT_EQ(1, Vec
.find_first_unset_in(1, 10));
310 EXPECT_EQ(7, Vec
.find_first_unset_in(5, 25));
311 EXPECT_EQ(151, Vec
.find_first_unset_in(150, 200));
312 EXPECT_EQ(151, Vec
.find_first_unset_in(151, 200));
313 EXPECT_EQ(153, Vec
.find_first_unset_in(152, 200));
314 EXPECT_EQ(153, Vec
.find_first_unset_in(153, 200));
315 EXPECT_EQ(155, Vec
.find_first_unset_in(154, 200));
316 EXPECT_EQ(155, Vec
.find_first_unset_in(155, 200));
317 EXPECT_EQ(199, Vec
.find_first_unset_in(199, 200));
320 EXPECT_EQ(-1, Vec
.find_last_unset_in(0, 0));
321 EXPECT_EQ(-1, Vec
.find_last_unset_in(23, 23));
322 EXPECT_EQ(-1, Vec
.find_last_unset_in(24, 35));
324 EXPECT_EQ(9, Vec
.find_last_unset_in(0, 10));
325 EXPECT_EQ(8, Vec
.find_last_unset_in(0, 9));
326 EXPECT_EQ(2, Vec
.find_last_unset_in(0, 7));
327 EXPECT_EQ(149, Vec
.find_last_unset_in(100, 151));
328 EXPECT_EQ(151, Vec
.find_last_unset_in(100, 152));
329 EXPECT_EQ(151, Vec
.find_last_unset_in(100, 153));
330 EXPECT_EQ(153, Vec
.find_last_unset_in(100, 154));
331 EXPECT_EQ(153, Vec
.find_last_unset_in(100, 155));
332 EXPECT_EQ(155, Vec
.find_last_unset_in(100, 156));
333 EXPECT_EQ(199, Vec
.find_last_unset_in(199, 200));
336 TEST(BitVectorTest
, FindInRangeSingleWord
) {
337 // When the bit vector contains only a single word, this is slightly different
338 // than when the bit vector contains multiple words, because masks are applied
339 // to the front and back of the same word. So make sure this works.
351 EXPECT_EQ(-1, Vec
.find_first_in(0, 0));
352 EXPECT_EQ(-1, Vec
.find_first_in(24, 24));
353 EXPECT_EQ(-1, Vec
.find_first_in(9, 12));
355 EXPECT_EQ(2, Vec
.find_first_in(0, 10));
356 EXPECT_EQ(6, Vec
.find_first_in(4, 10));
357 EXPECT_EQ(19, Vec
.find_first_in(18, 25));
358 EXPECT_EQ(21, Vec
.find_first_in(20, 25));
359 EXPECT_EQ(23, Vec
.find_first_in(22, 25));
360 EXPECT_EQ(-1, Vec
.find_first_in(24, 25));
363 EXPECT_EQ(-1, Vec
.find_last_in(0, 0));
364 EXPECT_EQ(-1, Vec
.find_last_in(24, 24));
365 EXPECT_EQ(-1, Vec
.find_last_in(9, 12));
367 EXPECT_EQ(8, Vec
.find_last_in(0, 10));
368 EXPECT_EQ(3, Vec
.find_last_in(0, 6));
369 EXPECT_EQ(23, Vec
.find_last_in(18, 25));
370 EXPECT_EQ(21, Vec
.find_last_in(18, 23));
371 EXPECT_EQ(19, Vec
.find_last_in(18, 21));
372 EXPECT_EQ(-1, Vec
.find_last_in(18, 19));
375 EXPECT_EQ(-1, Vec
.find_first_unset_in(0, 0));
376 EXPECT_EQ(-1, Vec
.find_first_unset_in(23, 23));
377 EXPECT_EQ(-1, Vec
.find_first_unset_in(6, 9));
379 EXPECT_EQ(0, Vec
.find_first_unset_in(0, 6));
380 EXPECT_EQ(1, Vec
.find_first_unset_in(1, 6));
381 EXPECT_EQ(9, Vec
.find_first_unset_in(7, 13));
382 EXPECT_EQ(18, Vec
.find_first_unset_in(18, 25));
383 EXPECT_EQ(20, Vec
.find_first_unset_in(19, 25));
384 EXPECT_EQ(20, Vec
.find_first_unset_in(20, 25));
385 EXPECT_EQ(22, Vec
.find_first_unset_in(21, 25));
386 EXPECT_EQ(22, Vec
.find_first_unset_in(22, 25));
387 EXPECT_EQ(24, Vec
.find_first_unset_in(23, 25));
388 EXPECT_EQ(24, Vec
.find_first_unset_in(24, 25));
391 EXPECT_EQ(-1, Vec
.find_last_unset_in(0, 0));
392 EXPECT_EQ(-1, Vec
.find_last_unset_in(23, 23));
393 EXPECT_EQ(-1, Vec
.find_last_unset_in(6, 9));
395 EXPECT_EQ(5, Vec
.find_last_unset_in(0, 6));
396 EXPECT_EQ(4, Vec
.find_last_unset_in(0, 5));
397 EXPECT_EQ(1, Vec
.find_last_unset_in(0, 4));
398 EXPECT_EQ(11, Vec
.find_last_unset_in(7, 13));
399 EXPECT_EQ(24, Vec
.find_last_unset_in(18, 25));
400 EXPECT_EQ(22, Vec
.find_last_unset_in(18, 24));
401 EXPECT_EQ(22, Vec
.find_last_unset_in(18, 23));
402 EXPECT_EQ(20, Vec
.find_last_unset_in(18, 22));
403 EXPECT_EQ(20, Vec
.find_last_unset_in(18, 21));
404 EXPECT_EQ(18, Vec
.find_last_unset_in(18, 20));
405 EXPECT_EQ(18, Vec
.find_last_unset_in(18, 19));
408 TYPED_TEST(BitVectorTest
, CompoundAssignment
) {
420 EXPECT_TRUE(A
.test(4));
421 EXPECT_TRUE(A
.test(5));
422 EXPECT_TRUE(A
.test(7));
423 EXPECT_TRUE(A
.test(18));
424 EXPECT_EQ(4U, A
.count());
425 EXPECT_EQ(50U, A
.size());
432 EXPECT_FALSE(A
.test(2));
433 EXPECT_FALSE(A
.test(7));
434 EXPECT_EQ(2U, A
.count());
435 EXPECT_EQ(50U, A
.size());
441 EXPECT_TRUE(A
.test(2));
442 EXPECT_TRUE(A
.test(7));
443 EXPECT_EQ(98U, A
.count());
444 EXPECT_EQ(100U, A
.size());
447 TYPED_TEST(BitVectorTest
, ProxyIndex
) {
449 EXPECT_TRUE(Vec
.none());
450 Vec
[0] = Vec
[1] = Vec
[2] = true;
451 EXPECT_EQ(Vec
.size(), Vec
.count());
452 Vec
[2] = Vec
[1] = Vec
[0] = false;
453 EXPECT_TRUE(Vec
.none());
456 TYPED_TEST(BitVectorTest
, PortableBitMask
) {
458 const uint32_t Mask1
[] = { 0x80000000, 6, 5 };
461 A
.setBitsInMask(Mask1
, 1);
462 EXPECT_EQ(10u, A
.size());
463 EXPECT_FALSE(A
.test(0));
466 A
.setBitsInMask(Mask1
, 1);
467 EXPECT_FALSE(A
.test(0));
468 EXPECT_TRUE(A
.test(31));
469 EXPECT_EQ(1u, A
.count());
472 A
.setBitsInMask(Mask1
, 1);
473 EXPECT_EQ(1u, A
.count());
474 A
.setBitsInMask(Mask1
, 2);
475 EXPECT_EQ(1u, A
.count());
478 A
.setBitsInMask(Mask1
, 2);
479 EXPECT_EQ(2u, A
.count());
482 A
.setBitsInMask(Mask1
, 3);
483 EXPECT_EQ(4u, A
.count());
485 A
.setBitsNotInMask(Mask1
, 1);
486 EXPECT_EQ(32u+3u, A
.count());
488 A
.setBitsNotInMask(Mask1
, 3);
489 EXPECT_EQ(65u, A
.count());
492 EXPECT_EQ(65u, A
.count());
496 A
.setBitsNotInMask(Mask1
, 3);
497 EXPECT_EQ(96u-5u, A
.count());
499 A
.clearBitsNotInMask(Mask1
, 1);
500 EXPECT_EQ(64-4u, A
.count());
503 TYPED_TEST(BitVectorTest
, BinOps
) {
508 EXPECT_FALSE(A
.anyCommon(B
));
509 EXPECT_FALSE(B
.anyCommon(B
));
513 EXPECT_FALSE(A
.anyCommon(B
));
514 EXPECT_FALSE(B
.anyCommon(A
));
517 EXPECT_FALSE(A
.anyCommon(B
));
518 EXPECT_FALSE(B
.anyCommon(A
));
521 EXPECT_TRUE(A
.anyCommon(B
));
522 EXPECT_TRUE(B
.anyCommon(A
));
528 EXPECT_FALSE(A
.anyCommon(B
));
529 EXPECT_FALSE(B
.anyCommon(A
));
532 typedef std::vector
<std::pair
<int, int>> RangeList
;
534 template <typename VecType
>
535 static inline VecType
createBitVector(uint32_t Size
,
536 const RangeList
&setRanges
) {
539 for (auto &R
: setRanges
)
540 V
.set(R
.first
, R
.second
);
544 TYPED_TEST(BitVectorTest
, ShiftOpsSingleWord
) {
545 // Test that shift ops work when the desired shift amount is less
548 // 1. Case where the number of bits in the BitVector also fit into a single
550 TypeParam A
= createBitVector
<TypeParam
>(12, {{2, 4}, {8, 10}});
553 EXPECT_EQ(4U, A
.count());
554 EXPECT_TRUE(A
.test(2));
555 EXPECT_TRUE(A
.test(3));
556 EXPECT_TRUE(A
.test(8));
557 EXPECT_TRUE(A
.test(9));
560 EXPECT_EQ(createBitVector
<TypeParam
>(12, {{1, 3}, {7, 9}}), A
);
566 EXPECT_EQ(createBitVector
<TypeParam
>(12, {}), A
);
570 EXPECT_EQ(createBitVector
<TypeParam
>(12, {}), A
);
572 // 2. Case where the number of bits in the BitVector do not fit into a single
575 // 31----------------------------------------------------------------------0
576 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
577 A
= createBitVector
<TypeParam
>(40, {{0, 12}, {25, 35}});
578 EXPECT_EQ(40U, A
.size());
579 EXPECT_EQ(22U, A
.count());
581 // 2a. Make sure that left shifting some 1 bits out of the vector works.
582 // 31----------------------------------------------------------------------0
584 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
586 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
588 EXPECT_EQ(createBitVector
<TypeParam
>(40, {{9, 21}, {34, 40}}), A
);
590 // 2b. Make sure that keeping the number of one bits unchanged works.
591 // 31----------------------------------------------------------------------0
593 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
595 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
597 EXPECT_EQ(createBitVector
<TypeParam
>(40, {{3, 15}, {28, 34}}), A
);
599 // 2c. Make sure that right shifting some 1 bits out of the vector works.
600 // 31----------------------------------------------------------------------0
602 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
604 // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111
606 EXPECT_EQ(createBitVector
<TypeParam
>(40, {{0, 5}, {18, 24}}), A
);
609 A
= createBitVector
<TypeParam
>(300, {{1, 30}, {60, 95}, {200, 275}});
611 EXPECT_EQ(createBitVector
<TypeParam
>(
612 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}),
616 TYPED_TEST(BitVectorTest
, ShiftOpsMultiWord
) {
617 // Test that shift ops work when the desired shift amount is greater than or
618 // equal to the size of a single word.
619 auto A
= createBitVector
<TypeParam
>(300, {{1, 30}, {60, 95}, {200, 275}});
621 // Make a copy so we can re-use it later.
624 // 1. Shift left by an exact multiple of the word size. This should invoke
625 // only a memmove and no per-word bit operations.
627 auto Expected
= createBitVector
<TypeParam
>(
628 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}});
629 EXPECT_EQ(Expected
, A
);
631 // 2. Shift left by a non multiple of the word size. This should invoke both
632 // a memmove and per-word bit operations.
635 EXPECT_EQ(createBitVector
<TypeParam
>(
636 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}),
639 // 1. Shift right by an exact multiple of the word size. This should invoke
640 // only a memmove and no per-word bit operations.
644 createBitVector
<TypeParam
>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A
);
646 // 2. Shift left by a non multiple of the word size. This should invoke both
647 // a memmove and per-word bit operations.
651 createBitVector
<TypeParam
>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A
);
654 TYPED_TEST(BitVectorTest
, RangeOps
) {
660 EXPECT_FALSE(A
.test(0));
661 EXPECT_TRUE( A
.test(1));
662 EXPECT_TRUE( A
.test(23));
663 EXPECT_TRUE( A
.test(254));
664 EXPECT_FALSE(A
.test(255));
671 EXPECT_TRUE( B
.test(0));
672 EXPECT_FALSE(B
.test(1));
673 EXPECT_FALSE(B
.test(23));
674 EXPECT_FALSE(B
.test(254));
675 EXPECT_TRUE( B
.test(255));
682 EXPECT_TRUE(C
.test(0));
683 EXPECT_FALSE( C
.test(1));
684 EXPECT_FALSE( C
.test(2));
691 EXPECT_FALSE(D
.test(0));
692 EXPECT_TRUE( D
.test(1));
693 EXPECT_TRUE( D
.test(2));
700 EXPECT_FALSE(E
.test(0));
701 EXPECT_TRUE( E
.test(1));
702 EXPECT_TRUE( E
.test(32));
703 EXPECT_FALSE(E
.test(33));
705 TypeParam BufferOverrun
;
706 unsigned size
= sizeof(unsigned long) * 8;
707 BufferOverrun
.resize(size
);
708 BufferOverrun
.reset(0, size
);
709 BufferOverrun
.set(0, size
);
712 TYPED_TEST(BitVectorTest
, CompoundTestReset
) {
713 TypeParam
A(50, true);
714 TypeParam
B(50, false);
716 TypeParam
C(100, true);
717 TypeParam
D(100, false);
719 EXPECT_FALSE(A
.test(A
));
720 EXPECT_TRUE(A
.test(B
));
721 EXPECT_FALSE(A
.test(C
));
722 EXPECT_TRUE(A
.test(D
));
723 EXPECT_FALSE(B
.test(A
));
724 EXPECT_FALSE(B
.test(B
));
725 EXPECT_FALSE(B
.test(C
));
726 EXPECT_FALSE(B
.test(D
));
727 EXPECT_TRUE(C
.test(A
));
728 EXPECT_TRUE(C
.test(B
));
729 EXPECT_FALSE(C
.test(C
));
730 EXPECT_TRUE(C
.test(D
));
734 EXPECT_TRUE(A
.all());
736 EXPECT_TRUE(A
.none());
739 EXPECT_TRUE(A
.none());
743 EXPECT_EQ(50, C
.find_first());
745 EXPECT_TRUE(C
.none());
748 TYPED_TEST(BitVectorTest
, MoveConstructor
) {
749 TypeParam
A(10, true);
750 TypeParam
B(std::move(A
));
751 // Check that the move ctor leaves the moved-from object in a valid state.
752 // The following line used to crash.
755 TypeParam
C(10, true);
760 TYPED_TEST(BitVectorTest
, MoveAssignment
) {
761 TypeParam
A(10, true);
764 // Check that move assignment leaves the moved-from object in a valid state.
765 // The following line used to crash.
768 TypeParam
C(10, true);
773 template<class TypeParam
>
774 static void testEmpty(const TypeParam
&A
) {
775 EXPECT_TRUE(A
.empty());
776 EXPECT_EQ((size_t)0, A
.size());
777 EXPECT_EQ((size_t)0, A
.count());
778 EXPECT_FALSE(A
.any());
779 EXPECT_TRUE(A
.all());
780 EXPECT_TRUE(A
.none());
781 EXPECT_EQ(-1, A
.find_first());
782 EXPECT_EQ(A
, TypeParam());
785 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0
786 TYPED_TEST(BitVectorTest
, EmptyVector
) {
810 TYPED_TEST(BitVectorTest
, Iterators
) {
811 TypeParam
Filled(10, true);
812 EXPECT_NE(Filled
.set_bits_begin(), Filled
.set_bits_end());
813 unsigned Counter
= 0;
814 for (unsigned Bit
: Filled
.set_bits())
815 EXPECT_EQ(Bit
, Counter
++);
818 EXPECT_EQ(Empty
.set_bits_begin(), Empty
.set_bits_end());
819 for (unsigned Bit
: Empty
.set_bits()) {
824 TypeParam
ToFill(100, false);
826 EXPECT_NE(ToFill
.set_bits_begin(), ToFill
.set_bits_end());
827 EXPECT_EQ(++ToFill
.set_bits_begin(), ToFill
.set_bits_end());
828 EXPECT_EQ(*ToFill
.set_bits_begin(), 0U);
830 EXPECT_EQ(ToFill
.set_bits_begin(), ToFill
.set_bits_end());
832 const unsigned List
[] = {1, 10, 25, 99};
833 for (unsigned Num
: List
)
836 for (unsigned Bit
: ToFill
.set_bits())
837 EXPECT_EQ(List
[i
++], Bit
);
840 TYPED_TEST(BitVectorTest
, PushBack
) {
841 TypeParam
Vec(10, false);
842 EXPECT_EQ(-1, Vec
.find_first());
843 EXPECT_EQ(10U, Vec
.size());
844 EXPECT_EQ(0U, Vec
.count());
847 EXPECT_EQ(10, Vec
.find_first());
848 EXPECT_EQ(11U, Vec
.size());
849 EXPECT_EQ(1U, Vec
.count());
851 Vec
.push_back(false);
852 EXPECT_EQ(10, Vec
.find_first());
853 EXPECT_EQ(12U, Vec
.size());
854 EXPECT_EQ(1U, Vec
.count());
857 EXPECT_EQ(10, Vec
.find_first());
858 EXPECT_EQ(13U, Vec
.size());
859 EXPECT_EQ(2U, Vec
.count());
861 // Add a lot of values to cause reallocation.
862 for (int i
= 0; i
!= 100; ++i
) {
864 Vec
.push_back(false);
866 EXPECT_EQ(10, Vec
.find_first());
867 EXPECT_EQ(213U, Vec
.size());
868 EXPECT_EQ(102U, Vec
.count());