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  Vec.flip();
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());
151
152  Vec.resize(64);
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());
159
160  Vec.flip();
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());
167
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());
175
176  Vec.clear();
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());
183}
184
185TYPED_TEST(BitVectorTest, CompoundAssignment) {
186  TypeParam A;
187  A.resize(10);
188  A.set(4);
189  A.set(7);
190
191  TypeParam B;
192  B.resize(50);
193  B.set(5);
194  B.set(18);
195
196  A |= B;
197  EXPECT_TRUE(A.test(4));
198  EXPECT_TRUE(A.test(5));
199  EXPECT_TRUE(A.test(7));
200  EXPECT_TRUE(A.test(18));
201  EXPECT_EQ(4U, A.count());
202  EXPECT_EQ(50U, A.size());
203
204  B.resize(10);
205  B.set();
206  B.reset(2);
207  B.reset(7);
208  A &= B;
209  EXPECT_FALSE(A.test(2));
210  EXPECT_FALSE(A.test(7));
211  EXPECT_EQ(2U, A.count());
212  EXPECT_EQ(50U, A.size());
213
214  B.resize(100);
215  B.set();
216
217  A ^= B;
218  EXPECT_TRUE(A.test(2));
219  EXPECT_TRUE(A.test(7));
220  EXPECT_EQ(98U, A.count());
221  EXPECT_EQ(100U, A.size());
222}
223
224TYPED_TEST(BitVectorTest, ProxyIndex) {
225  TypeParam Vec(3);
226  EXPECT_TRUE(Vec.none());
227  Vec[0] = Vec[1] = Vec[2] = true;
228  EXPECT_EQ(Vec.size(), Vec.count());
229  Vec[2] = Vec[1] = Vec[0] = false;
230  EXPECT_TRUE(Vec.none());
231}
232
233TYPED_TEST(BitVectorTest, PortableBitMask) {
234  TypeParam A;
235  const uint32_t Mask1[] = { 0x80000000, 6, 5 };
236
237  A.resize(10);
238  A.setBitsInMask(Mask1, 3);
239  EXPECT_EQ(10u, A.size());
240  EXPECT_FALSE(A.test(0));
241
242  A.resize(32);
243  A.setBitsInMask(Mask1, 3);
244  EXPECT_FALSE(A.test(0));
245  EXPECT_TRUE(A.test(31));
246  EXPECT_EQ(1u, A.count());
247
248  A.resize(33);
249  A.setBitsInMask(Mask1, 1);
250  EXPECT_EQ(1u, A.count());
251  A.setBitsInMask(Mask1, 2);
252  EXPECT_EQ(1u, A.count());
253
254  A.resize(34);
255  A.setBitsInMask(Mask1, 2);
256  EXPECT_EQ(2u, A.count());
257
258  A.resize(65);
259  A.setBitsInMask(Mask1, 3);
260  EXPECT_EQ(4u, A.count());
261
262  A.setBitsNotInMask(Mask1, 1);
263  EXPECT_EQ(32u+3u, A.count());
264
265  A.setBitsNotInMask(Mask1, 3);
266  EXPECT_EQ(65u, A.count());
267
268  A.resize(96);
269  EXPECT_EQ(65u, A.count());
270
271  A.clear();
272  A.resize(128);
273  A.setBitsNotInMask(Mask1, 3);
274  EXPECT_EQ(96u-5u, A.count());
275
276  A.clearBitsNotInMask(Mask1, 1);
277  EXPECT_EQ(64-4u, A.count());
278}
279
280TYPED_TEST(BitVectorTest, BinOps) {
281  TypeParam A;
282  TypeParam B;
283
284  A.resize(65);
285  EXPECT_FALSE(A.anyCommon(B));
286  EXPECT_FALSE(B.anyCommon(B));
287
288  B.resize(64);
289  A.set(64);
290  EXPECT_FALSE(A.anyCommon(B));
291  EXPECT_FALSE(B.anyCommon(A));
292
293  B.set(63);
294  EXPECT_FALSE(A.anyCommon(B));
295  EXPECT_FALSE(B.anyCommon(A));
296
297  A.set(63);
298  EXPECT_TRUE(A.anyCommon(B));
299  EXPECT_TRUE(B.anyCommon(A));
300
301  B.resize(70);
302  B.set(64);
303  B.reset(63);
304  A.resize(64);
305  EXPECT_FALSE(A.anyCommon(B));
306  EXPECT_FALSE(B.anyCommon(A));
307}
308
309TYPED_TEST(BitVectorTest, RangeOps) {
310  TypeParam A;
311  A.resize(256);
312  A.reset();
313  A.set(1, 255);
314
315  EXPECT_FALSE(A.test(0));
316  EXPECT_TRUE( A.test(1));
317  EXPECT_TRUE( A.test(23));
318  EXPECT_TRUE( A.test(254));
319  EXPECT_FALSE(A.test(255));
320
321  TypeParam B;
322  B.resize(256);
323  B.set();
324  B.reset(1, 255);
325
326  EXPECT_TRUE( B.test(0));
327  EXPECT_FALSE(B.test(1));
328  EXPECT_FALSE(B.test(23));
329  EXPECT_FALSE(B.test(254));
330  EXPECT_TRUE( B.test(255));
331
332  TypeParam C;
333  C.resize(3);
334  C.reset();
335  C.set(0, 1);
336
337  EXPECT_TRUE(C.test(0));
338  EXPECT_FALSE( C.test(1));
339  EXPECT_FALSE( C.test(2));
340
341  TypeParam D;
342  D.resize(3);
343  D.set();
344  D.reset(0, 1);
345
346  EXPECT_FALSE(D.test(0));
347  EXPECT_TRUE( D.test(1));
348  EXPECT_TRUE( D.test(2));
349
350  TypeParam E;
351  E.resize(128);
352  E.reset();
353  E.set(1, 33);
354
355  EXPECT_FALSE(E.test(0));
356  EXPECT_TRUE( E.test(1));
357  EXPECT_TRUE( E.test(32));
358  EXPECT_FALSE(E.test(33));
359
360  TypeParam BufferOverrun;
361  unsigned size = sizeof(unsigned long) * 8;
362  BufferOverrun.resize(size);
363  BufferOverrun.reset(0, size);
364  BufferOverrun.set(0, size);
365}
366
367TYPED_TEST(BitVectorTest, CompoundTestReset) {
368  TypeParam A(50, true);
369  TypeParam B(50, false);
370
371  TypeParam C(100, true);
372  TypeParam D(100, false);
373
374  EXPECT_FALSE(A.test(A));
375  EXPECT_TRUE(A.test(B));
376  EXPECT_FALSE(A.test(C));
377  EXPECT_TRUE(A.test(D));
378  EXPECT_FALSE(B.test(A));
379  EXPECT_FALSE(B.test(B));
380  EXPECT_FALSE(B.test(C));
381  EXPECT_FALSE(B.test(D));
382  EXPECT_TRUE(C.test(A));
383  EXPECT_TRUE(C.test(B));
384  EXPECT_FALSE(C.test(C));
385  EXPECT_TRUE(C.test(D));
386
387  A.reset(B);
388  A.reset(D);
389  EXPECT_TRUE(A.all());
390  A.reset(A);
391  EXPECT_TRUE(A.none());
392  A.set();
393  A.reset(C);
394  EXPECT_TRUE(A.none());
395  A.set();
396
397  C.reset(A);
398  EXPECT_EQ(50, C.find_first());
399  C.reset(C);
400  EXPECT_TRUE(C.none());
401}
402}
403#endif
404