1//===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10// Some of these tests fail on PowerPC for unknown reasons.
11#ifndef __ppc__
12
13#include "llvm/ADT/BitVector.h"
14#include "llvm/ADT/SmallBitVector.h"
15#include "gtest/gtest.h"
16
17using namespace llvm;
18
19namespace {
20
21// Test fixture
22template <typename T>
23class BitVectorTest : public ::testing::Test { };
24
25// Test both BitVector and SmallBitVector with the same suite of tests.
26typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes;
27TYPED_TEST_CASE(BitVectorTest, BitVectorTestTypes);
28
29TYPED_TEST(BitVectorTest, TrivialOperation) {
30  TypeParam Vec;
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());
37
38  Vec.resize(5, true);
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());
45
46  Vec.resize(11);
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());
53
54  TypeParam Inv = Vec;
55  Inv.flip();
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());
62
63  EXPECT_FALSE(Inv == Vec);
64  EXPECT_TRUE(Inv != Vec);
65  Vec.flip();
66  EXPECT_TRUE(Inv == Vec);
67  EXPECT_FALSE(Inv != Vec);
68
69  // Add some "interesting" data to Vec.
70  Vec.resize(23, true);
71  Vec.resize(25, false);
72  Vec.resize(26, true);
73  Vec.resize(29, false);
74  Vec.resize(33, true);
75  Vec.resize(57, false);
76  unsigned Count = 0;
77  for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
78    ++Count;
79    EXPECT_TRUE(Vec[i]);
80    EXPECT_TRUE(Vec.test(i));
81  }
82  EXPECT_EQ(Count, Vec.count());
83  EXPECT_EQ(Count, 23u);
84  EXPECT_FALSE(Vec[0]);
85  EXPECT_TRUE(Vec[32]);
86  EXPECT_FALSE(Vec[56]);
87  Vec.resize(61, false);
88
89  TypeParam Copy = Vec;
90  TypeParam Alt(3, false);
91  Alt.resize(6, true);
92  std::swap(Alt, Vec);
93  EXPECT_TRUE(Copy == Alt);
94  EXPECT_TRUE(Vec.size() == 6);
95  EXPECT_TRUE(Vec.count() == 3);
96  EXPECT_TRUE(Vec.find_first() == 3);
97  std::swap(Copy, Vec);
98
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);
106  Count = 0;
107  for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
108    ++Count;
109    EXPECT_TRUE(Vec[i]);
110    EXPECT_TRUE(Vec.test(i));
111  }
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]);
118
119  Vec.flip(60);
120  EXPECT_TRUE(Vec[60]);
121  EXPECT_EQ(Count + 1, Vec.count());
122  Vec.flip(60);
123  EXPECT_FALSE(Vec[60]);
124  EXPECT_EQ(Count, Vec.count());
125
126  Vec.reset(32);
127  EXPECT_FALSE(Vec[32]);
128  EXPECT_EQ(Count - 1, Vec.count());
129  Vec.set(32);
130  EXPECT_TRUE(Vec[32]);
131  EXPECT_EQ(Count, Vec.count());
132
133  Vec.flip();
134  EXPECT_EQ(Vec.size() - Count, Vec.count());
135
136  Vec.reset();
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());
143
144  Inv = TypeParam().flip();
145  EXPECT_EQ(0U, Inv.count());
146  EXPECT_EQ(0U, Inv.size());
147  EXPECT_FALSE(Inv.any());
148  EXPECT_TRUE(Inv.all());
149  EXPECT_TRUE(Inv.none());
150  EXPECT_TRUE(Inv.empty());
151
152  Vec.clear();
153  EXPECT_EQ(0U, Vec.count());
154  EXPECT_EQ(0U, Vec.size());
155  EXPECT_FALSE(Vec.any());
156  EXPECT_TRUE(Vec.all());
157  EXPECT_TRUE(Vec.none());
158  EXPECT_TRUE(Vec.empty());
159}
160
161TYPED_TEST(BitVectorTest, CompoundAssignment) {
162  TypeParam A;
163  A.resize(10);
164  A.set(4);
165  A.set(7);
166
167  TypeParam B;
168  B.resize(50);
169  B.set(5);
170  B.set(18);
171
172  A |= B;
173  EXPECT_TRUE(A.test(4));
174  EXPECT_TRUE(A.test(5));
175  EXPECT_TRUE(A.test(7));
176  EXPECT_TRUE(A.test(18));
177  EXPECT_EQ(4U, A.count());
178  EXPECT_EQ(50U, A.size());
179
180  B.resize(10);
181  B.set();
182  B.reset(2);
183  B.reset(7);
184  A &= B;
185  EXPECT_FALSE(A.test(2));
186  EXPECT_FALSE(A.test(7));
187  EXPECT_EQ(2U, A.count());
188  EXPECT_EQ(50U, A.size());
189
190  B.resize(100);
191  B.set();
192
193  A ^= B;
194  EXPECT_TRUE(A.test(2));
195  EXPECT_TRUE(A.test(7));
196  EXPECT_EQ(98U, A.count());
197  EXPECT_EQ(100U, A.size());
198}
199
200TYPED_TEST(BitVectorTest, ProxyIndex) {
201  TypeParam Vec(3);
202  EXPECT_TRUE(Vec.none());
203  Vec[0] = Vec[1] = Vec[2] = true;
204  EXPECT_EQ(Vec.size(), Vec.count());
205  Vec[2] = Vec[1] = Vec[0] = false;
206  EXPECT_TRUE(Vec.none());
207}
208
209TYPED_TEST(BitVectorTest, PortableBitMask) {
210  TypeParam A;
211  const uint32_t Mask1[] = { 0x80000000, 6, 5 };
212
213  A.resize(10);
214  A.setBitsInMask(Mask1, 3);
215  EXPECT_EQ(10u, A.size());
216  EXPECT_FALSE(A.test(0));
217
218  A.resize(32);
219  A.setBitsInMask(Mask1, 3);
220  EXPECT_FALSE(A.test(0));
221  EXPECT_TRUE(A.test(31));
222  EXPECT_EQ(1u, A.count());
223
224  A.resize(33);
225  A.setBitsInMask(Mask1, 1);
226  EXPECT_EQ(1u, A.count());
227  A.setBitsInMask(Mask1, 2);
228  EXPECT_EQ(1u, A.count());
229
230  A.resize(34);
231  A.setBitsInMask(Mask1, 2);
232  EXPECT_EQ(2u, A.count());
233
234  A.resize(65);
235  A.setBitsInMask(Mask1, 3);
236  EXPECT_EQ(4u, A.count());
237
238  A.setBitsNotInMask(Mask1, 1);
239  EXPECT_EQ(32u+3u, A.count());
240
241  A.setBitsNotInMask(Mask1, 3);
242  EXPECT_EQ(65u, A.count());
243
244  A.resize(96);
245  EXPECT_EQ(65u, A.count());
246
247  A.clear();
248  A.resize(128);
249  A.setBitsNotInMask(Mask1, 3);
250  EXPECT_EQ(96u-5u, A.count());
251
252  A.clearBitsNotInMask(Mask1, 1);
253  EXPECT_EQ(64-4u, A.count());
254}
255
256TYPED_TEST(BitVectorTest, BinOps) {
257  TypeParam A;
258  TypeParam B;
259
260  A.resize(65);
261  EXPECT_FALSE(A.anyCommon(B));
262  EXPECT_FALSE(B.anyCommon(B));
263
264  B.resize(64);
265  A.set(64);
266  EXPECT_FALSE(A.anyCommon(B));
267  EXPECT_FALSE(B.anyCommon(A));
268
269  B.set(63);
270  EXPECT_FALSE(A.anyCommon(B));
271  EXPECT_FALSE(B.anyCommon(A));
272
273  A.set(63);
274  EXPECT_TRUE(A.anyCommon(B));
275  EXPECT_TRUE(B.anyCommon(A));
276
277  B.resize(70);
278  B.set(64);
279  B.reset(63);
280  A.resize(64);
281  EXPECT_FALSE(A.anyCommon(B));
282  EXPECT_FALSE(B.anyCommon(A));
283}
284
285TYPED_TEST(BitVectorTest, RangeOps) {
286  TypeParam A;
287  A.resize(256);
288  A.reset();
289  A.set(1, 255);
290
291  EXPECT_FALSE(A.test(0));
292  EXPECT_TRUE( A.test(1));
293  EXPECT_TRUE( A.test(23));
294  EXPECT_TRUE( A.test(254));
295  EXPECT_FALSE(A.test(255));
296
297  TypeParam B;
298  B.resize(256);
299  B.set();
300  B.reset(1, 255);
301
302  EXPECT_TRUE( B.test(0));
303  EXPECT_FALSE(B.test(1));
304  EXPECT_FALSE(B.test(23));
305  EXPECT_FALSE(B.test(254));
306  EXPECT_TRUE( B.test(255));
307
308  TypeParam C;
309  C.resize(3);
310  C.reset();
311  C.set(0, 1);
312
313  EXPECT_TRUE(C.test(0));
314  EXPECT_FALSE( C.test(1));
315  EXPECT_FALSE( C.test(2));
316
317  TypeParam D;
318  D.resize(3);
319  D.set();
320  D.reset(0, 1);
321
322  EXPECT_FALSE(D.test(0));
323  EXPECT_TRUE( D.test(1));
324  EXPECT_TRUE( D.test(2));
325
326  TypeParam E;
327  E.resize(128);
328  E.reset();
329  E.set(1, 33);
330
331  EXPECT_FALSE(E.test(0));
332  EXPECT_TRUE( E.test(1));
333  EXPECT_TRUE( E.test(32));
334  EXPECT_FALSE(E.test(33));
335}
336}
337#endif
338