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