1 //===- llvm/unittest/ADT/SparseBitVectorTest.cpp - SparseBitVector 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 #include "llvm/ADT/SparseBitVector.h"
11 #include "gtest/gtest.h"
12 
13 using namespace llvm;
14 
15 namespace {
16 
17 TEST(SparseBitVectorTest, TrivialOperation) {
18   SparseBitVector<> Vec;
19   EXPECT_EQ(0U, Vec.count());
20   EXPECT_FALSE(Vec.test(17));
21   Vec.set(5);
22   EXPECT_TRUE(Vec.test(5));
23   EXPECT_FALSE(Vec.test(17));
24   Vec.reset(6);
25   EXPECT_TRUE(Vec.test(5));
26   EXPECT_FALSE(Vec.test(6));
27   Vec.reset(5);
28   EXPECT_FALSE(Vec.test(5));
29   EXPECT_TRUE(Vec.test_and_set(17));
30   EXPECT_FALSE(Vec.test_and_set(17));
31   EXPECT_TRUE(Vec.test(17));
32   Vec.clear();
33   EXPECT_FALSE(Vec.test(17));
34 
35   Vec.set(5);
36   const SparseBitVector<> ConstVec = Vec;
37   EXPECT_TRUE(ConstVec.test(5));
38   EXPECT_FALSE(ConstVec.test(17));
39 
40   Vec.set(1337);
41   EXPECT_TRUE(Vec.test(1337));
42   Vec = ConstVec;
43   EXPECT_FALSE(Vec.test(1337));
44 
45   Vec.set(1337);
46   EXPECT_FALSE(Vec.empty());
47   SparseBitVector<> MovedVec(std::move(Vec));
48   EXPECT_TRUE(Vec.empty());
49   EXPECT_TRUE(MovedVec.test(5));
50   EXPECT_TRUE(MovedVec.test(1337));
51 
52   Vec = std::move(MovedVec);
53   EXPECT_TRUE(MovedVec.empty());
54   EXPECT_FALSE(Vec.empty());
55 }
56 
57 TEST(SparseBitVectorTest, IntersectWith) {
58   SparseBitVector<> Vec, Other;
59 
60   Vec.set(1);
61   Other.set(1);
62   EXPECT_FALSE(Vec &= Other);
63   EXPECT_TRUE(Vec.test(1));
64 
65   Vec.clear();
66   Vec.set(5);
67   Other.clear();
68   Other.set(6);
69   EXPECT_TRUE(Vec &= Other);
70   EXPECT_TRUE(Vec.empty());
71 
72   Vec.clear();
73   Vec.set(5);
74   Other.clear();
75   Other.set(225);
76   EXPECT_TRUE(Vec &= Other);
77   EXPECT_TRUE(Vec.empty());
78 
79   Vec.clear();
80   Vec.set(225);
81   Other.clear();
82   Other.set(5);
83   EXPECT_TRUE(Vec &= Other);
84   EXPECT_TRUE(Vec.empty());
85 }
86 
87 TEST(SparseBitVectorTest, SelfAssignment) {
88   SparseBitVector<> Vec, Other;
89 
90   Vec.set(23);
91   Vec.set(234);
92   Vec = static_cast<SparseBitVector<> &>(Vec);
93   EXPECT_TRUE(Vec.test(23));
94   EXPECT_TRUE(Vec.test(234));
95 
96   Vec.clear();
97   Vec.set(17);
98   Vec.set(256);
99   EXPECT_FALSE(Vec |= Vec);
100   EXPECT_TRUE(Vec.test(17));
101   EXPECT_TRUE(Vec.test(256));
102 
103   Vec.clear();
104   Vec.set(56);
105   Vec.set(517);
106   EXPECT_FALSE(Vec &= Vec);
107   EXPECT_TRUE(Vec.test(56));
108   EXPECT_TRUE(Vec.test(517));
109 
110   Vec.clear();
111   Vec.set(99);
112   Vec.set(333);
113   EXPECT_TRUE(Vec.intersectWithComplement(Vec));
114   EXPECT_TRUE(Vec.empty());
115   EXPECT_FALSE(Vec.intersectWithComplement(Vec));
116 
117   Vec.clear();
118   Vec.set(28);
119   Vec.set(43);
120   Vec.intersectWithComplement(Vec, Vec);
121   EXPECT_TRUE(Vec.empty());
122 
123   Vec.clear();
124   Vec.set(42);
125   Vec.set(567);
126   Other.set(55);
127   Other.set(567);
128   Vec.intersectWithComplement(Vec, Other);
129   EXPECT_TRUE(Vec.test(42));
130   EXPECT_FALSE(Vec.test(567));
131 
132   Vec.clear();
133   Vec.set(19);
134   Vec.set(21);
135   Other.clear();
136   Other.set(19);
137   Other.set(31);
138   Vec.intersectWithComplement(Other, Vec);
139   EXPECT_FALSE(Vec.test(19));
140   EXPECT_TRUE(Vec.test(31));
141 
142   Vec.clear();
143   Vec.set(1);
144   Other.clear();
145   Other.set(59);
146   Other.set(75);
147   Vec.intersectWithComplement(Other, Other);
148   EXPECT_TRUE(Vec.empty());
149 }
150 
151 TEST(SparseBitVectorTest, Find) {
152   SparseBitVector<> Vec;
153   Vec.set(1);
154   EXPECT_EQ(1, Vec.find_first());
155   EXPECT_EQ(1, Vec.find_last());
156 
157   Vec.set(2);
158   EXPECT_EQ(1, Vec.find_first());
159   EXPECT_EQ(2, Vec.find_last());
160 
161   Vec.set(0);
162   Vec.set(3);
163   EXPECT_EQ(0, Vec.find_first());
164   EXPECT_EQ(3, Vec.find_last());
165 
166   Vec.reset(1);
167   Vec.reset(0);
168   Vec.reset(3);
169   EXPECT_EQ(2, Vec.find_first());
170   EXPECT_EQ(2, Vec.find_last());
171 
172   // Set some large bits to ensure we are pulling bits from more than just a
173   // single bitword.
174   Vec.set(500);
175   Vec.set(2000);
176   Vec.set(3000);
177   Vec.set(4000);
178   Vec.reset(2);
179   EXPECT_EQ(500, Vec.find_first());
180   EXPECT_EQ(4000, Vec.find_last());
181 
182   Vec.reset(500);
183   Vec.reset(3000);
184   Vec.reset(4000);
185   EXPECT_EQ(2000, Vec.find_first());
186   EXPECT_EQ(2000, Vec.find_last());
187 
188   Vec.clear();
189 }
190 }
191