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
17 using namespace llvm;
18
19 namespace {
20
21 // Test fixture
22 template <typename T>
23 class BitVectorTest : public ::testing::Test { };
24
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);
28
TYPED_TEST(BitVectorTest,TrivialOperation)29 TYPED_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
TYPED_TEST(BitVectorTest,CompoundAssignment)185 TYPED_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
TYPED_TEST(BitVectorTest,ProxyIndex)224 TYPED_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
TYPED_TEST(BitVectorTest,PortableBitMask)233 TYPED_TEST(BitVectorTest, PortableBitMask) {
234 TypeParam A;
235 const uint32_t Mask1[] = { 0x80000000, 6, 5 };
236
237 A.resize(10);
238 A.setBitsInMask(Mask1, 1);
239 EXPECT_EQ(10u, A.size());
240 EXPECT_FALSE(A.test(0));
241
242 A.resize(32);
243 A.setBitsInMask(Mask1, 1);
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
TYPED_TEST(BitVectorTest,BinOps)280 TYPED_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
TYPED_TEST(BitVectorTest,RangeOps)309 TYPED_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
TYPED_TEST(BitVectorTest,CompoundTestReset)367 TYPED_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