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 | |
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(Idx: 6); |
24 | EXPECT_TRUE(Vec.test(5)); |
25 | EXPECT_FALSE(Vec.test(6)); |
26 | Vec.reset(Idx: 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 | |
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 | |
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(RHS1: Vec, RHS2: 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(RHS1: Vec, RHS2: 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(RHS1: Other, RHS2: 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(RHS1: Other, RHS2: Other); |
147 | EXPECT_TRUE(Vec.empty()); |
148 | } |
149 | |
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(Idx: 1); |
166 | Vec.reset(Idx: 0); |
167 | Vec.reset(Idx: 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(Idx: 2); |
178 | EXPECT_EQ(500, Vec.find_first()); |
179 | EXPECT_EQ(4000, Vec.find_last()); |
180 | |
181 | Vec.reset(Idx: 500); |
182 | Vec.reset(Idx: 3000); |
183 | Vec.reset(Idx: 4000); |
184 | EXPECT_EQ(2000, Vec.find_first()); |
185 | EXPECT_EQ(2000, Vec.find_last()); |
186 | |
187 | Vec.clear(); |
188 | } |
189 | } |
190 | |