1 /*
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "utils/bit_vector.h"
17 #include "mem/pool_manager.h"
18 #include "utils/arena_containers.h"
19
20 #include <gtest/gtest.h>
21
22 namespace panda::test {
23
24 class BitVectorTest : public ::testing::Test {
25 public:
BitVectorTest()26 BitVectorTest()
27 {
28 panda::mem::MemConfig::Initialize(0, 64_MB, 256_MB, 32_MB);
29 PoolManager::Initialize();
30 allocator_ = new ArenaAllocator(SpaceType::SPACE_TYPE_COMPILER);
31 }
32
~BitVectorTest()33 virtual ~BitVectorTest()
34 {
35 delete allocator_;
36 PoolManager::Finalize();
37 panda::mem::MemConfig::Finalize();
38 }
39
GetAllocator()40 ArenaAllocator *GetAllocator()
41 {
42 return allocator_;
43 }
44
45 private:
46 ArenaAllocator *allocator_ {nullptr};
47 };
48
49 HWTEST_F(BitVectorTest, Basics, testing::ext::TestSize.Level0)
50 {
51 BitVector<> vector;
52 const BitVector<> &cvector = vector;
53 ASSERT_EQ(vector.capacity(), 0U);
54
55 // Index iterators for empty vector
56 for (uint32_t i : cvector.GetSetBitsIndices()) {
57 ADD_FAILURE() << i;
58 }
59 for (uint32_t i : cvector.GetZeroBitsIndices()) {
60 ADD_FAILURE() << i;
61 }
62
63 vector.push_back(true);
64 vector.push_back(false);
65 ASSERT_NE(vector.capacity(), 0U);
66
67 // Check `GetDataSpan`
68 ASSERT_NE(vector.GetDataSpan().size(), 0U);
69 uint32_t value = 1;
70 ASSERT_EQ(std::memcmp(vector.GetDataSpan().data(), &value, 1), 0);
71
72 // Constant operator[]
73 ASSERT_EQ(cvector[0], vector[0]);
74
75 // Constant versions of begin and end
76 ASSERT_EQ(cvector.begin(), vector.begin());
77 ASSERT_EQ(cvector.end(), vector.end());
78
79 vector.resize(20);
80 std::fill(vector.begin(), vector.end(), false);
81 ASSERT_EQ(vector.PopCount(), 0U);
82 std::fill(vector.begin() + 2, vector.begin() + 15, true);
83 ASSERT_EQ(vector.PopCount(), 13U);
84 for (size_t i = 0; i < 15; i++) {
85 if (i > 2) {
86 ASSERT_EQ(vector.PopCount(i), i - 2);
87 } else {
88 ASSERT_EQ(vector.PopCount(i), 0U);
89 }
90 }
91 ASSERT_EQ(vector.GetHighestBitSet(), 14);
92 ASSERT_EQ(vector[0], false);
93 ASSERT_EQ(vector[1], false);
94 ASSERT_EQ(vector[2], true);
95
96 ASSERT_EQ(vector, vector.GetFixed());
97 ASSERT_FALSE(vector.GetContainerDataSpan().empty());
98 }
99
100 HWTEST_F(BitVectorTest, Comparison, testing::ext::TestSize.Level0)
101 {
102 std::vector<bool> values = {false, true, false, true, false, true, false, true, false, true};
103 BitVector<> vec1;
104 std::copy(values.begin(), values.end(), std::back_inserter(vec1));
105 BitVector<ArenaAllocator> vec2(GetAllocator());
106 std::copy(values.begin(), values.end(), std::back_inserter(vec2));
107 ASSERT_EQ(vec1, vec2);
108 vec2[0] = true;
109 ASSERT_NE(vec1, vec2);
110 }
111
112 template <typename T>
TestIteration1(T & vector,size_t bits)113 void TestIteration1(T &vector, size_t bits)
114 {
115 uint32_t index = 0;
116
117 ASSERT_FALSE(vector.empty());
118 ASSERT_EQ(vector.size(), bits);
119
120 std::fill(vector.begin(), vector.end(), true);
121 for (uint32_t i : vector.GetZeroBitsIndices()) {
122 ADD_FAILURE() << i;
123 }
124 index = 0;
125 for (uint32_t i : vector.GetSetBitsIndices()) {
126 ASSERT_EQ(i, index++);
127 }
128
129 std::fill(vector.begin(), vector.end(), false);
130 for (uint32_t i : vector.GetSetBitsIndices()) {
131 ADD_FAILURE() << i;
132 }
133 index = 0;
134 for (uint32_t i : vector.GetZeroBitsIndices()) {
135 ASSERT_EQ(i, index++);
136 }
137
138 index = 0;
139 for (auto v : vector) {
140 v = (index++ % 2) != 0;
141 }
142 index = 0;
143 for (auto v : vector) {
144 ASSERT_EQ(v, index++ % 2);
145 }
146 index = vector.size() - 1;
147 for (auto it = vector.end() - 1;; --it) {
148 ASSERT_EQ(*it, index-- % 2);
149 if (it == vector.begin()) {
150 break;
151 }
152 }
153 index = 1;
154 for (uint32_t i : vector.GetSetBitsIndices()) {
155 ASSERT_EQ(i, index);
156 index += 2;
157 }
158 index = 0;
159 for (uint32_t i : vector.GetZeroBitsIndices()) {
160 ASSERT_EQ(i, index);
161 index += 2;
162 }
163 }
164
165 template <typename T>
TestIteration2(T & vector,size_t bits)166 void TestIteration2(T &vector, size_t bits)
167 {
168 auto it = vector.begin();
169 ASSERT_EQ(*it, false);
170 ++it;
171 ASSERT_EQ(*it, true);
172 auto it1 = it++;
173 ASSERT_EQ(*it, false);
174 ASSERT_EQ(*it1, true);
175 ASSERT_TRUE(it1 < it);
176 it += 3;
177 ASSERT_EQ(*it, true);
178 it -= 5;
179 ASSERT_EQ(*it, false);
180 ASSERT_EQ(it, vector.begin());
181
182 it = it + 6;
183 ASSERT_EQ(*it, false);
184 ASSERT_EQ(std::distance(vector.begin(), it), 6);
185 ASSERT_EQ(it[1], true);
186 it = it - 3;
187 ASSERT_EQ(*it, true);
188 ASSERT_EQ(std::distance(vector.begin(), it), 3);
189 --it;
190 ASSERT_EQ(*it, false);
191 it1 = it--;
192 ASSERT_EQ(*it, true);
193 ASSERT_EQ(*it1, false);
194 ASSERT_TRUE(it1 > it);
195 it = vector.begin() + 100;
196 ASSERT_EQ(std::distance(vector.begin(), it), 100);
197 ASSERT_TRUE(it + 2 > it);
198 ASSERT_TRUE(it + 2 >= it);
199 ASSERT_TRUE(it + 0 >= it);
200 ASSERT_TRUE(it - 2 < it);
201 ASSERT_TRUE(it - 2 <= it);
202
203 auto cit = vector.cbegin();
204 ASSERT_EQ(cit, vector.begin());
205 ASSERT_EQ(++cit, ++vector.begin());
206 ASSERT_EQ(vector.cend(), vector.end());
207 }
208
209 HWTEST_F(BitVectorTest, Iteration, testing::ext::TestSize.Level0)
210 {
211 std::array<uint32_t, 10> data {};
212 size_t bits_num = data.size() * BitsNumInValue(data[0]);
213
214 BitVector<> vec1;
215 vec1.resize(bits_num);
216 TestIteration1(vec1, bits_num);
217 TestIteration2(vec1, bits_num);
218
219 BitVector<ArenaAllocator> vec2(GetAllocator());
220 vec2.resize(bits_num);
221 TestIteration1(vec2, bits_num);
222 TestIteration2(vec2, bits_num);
223
224 BitVector<ArenaAllocator> vec3(bits_num, GetAllocator());
225 TestIteration1(vec3, bits_num);
226 TestIteration2(vec2, bits_num);
227
228 BitVectorSpan vec4(Span<uint32_t>(data.data(), data.size()));
229 TestIteration1(vec4, bits_num);
230 TestIteration2(vec4, bits_num);
231
232 data.fill(0);
233 BitVectorSpan vec5(data.data(), bits_num);
234 TestIteration1(vec5, bits_num);
235 TestIteration2(vec5, bits_num);
236 }
237
238 template <typename T>
TestModification(T & vector)239 void TestModification(T &vector)
240 {
241 std::vector<bool> values = {false, true, false, true, false, true, false, true, false, true};
242 ASSERT_TRUE(vector.empty());
243 ASSERT_EQ(vector.size(), 0U);
244 ASSERT_EQ(vector.PopCount(), 0U);
245 ASSERT_EQ(vector.GetHighestBitSet(), -1);
246
247 vector.push_back(true);
248 ASSERT_FALSE(vector.empty());
249 ASSERT_EQ(vector.size(), 1U);
250 ASSERT_EQ(vector.PopCount(), 1U);
251 ASSERT_EQ(vector.GetHighestBitSet(), 0);
252
253 std::copy(values.begin(), values.end(), std::back_inserter(vector));
254 ASSERT_EQ(vector.size(), 11U);
255 ASSERT_EQ(vector[1], false);
256 ASSERT_EQ(vector.PopCount(), 6U);
257 ASSERT_EQ(vector.GetHighestBitSet(), 10);
258
259 vector[1] = true;
260 ASSERT_EQ(vector[1], true);
261
262 uint32_t value = 0b10101010111;
263 ASSERT_EQ(std::memcmp(vector.data(), &value, vector.GetSizeInBytes()), 0);
264
265 vector.resize(3);
266 ASSERT_EQ(vector.size(), 3U);
267 ASSERT_EQ(vector.PopCount(), 3U);
268
269 vector.resize(10);
270 ASSERT_EQ(vector.PopCount(), 3U);
271
272 vector.clear();
273 ASSERT_TRUE(vector.empty());
274 ASSERT_EQ(vector.size(), 0U);
275
276 // Push 1000 values with `true` in odd and `false` in even indexes
277 for (int i = 0; i < 100; i++) {
278 std::copy(values.begin(), values.end(), std::back_inserter(vector));
279 }
280 ASSERT_EQ(vector.size(), 1000U);
281 ASSERT_EQ(vector.PopCount(), 500U);
282 for (int i = 0; i < 1000; i++) {
283 vector.push_back(false);
284 }
285 ASSERT_EQ(vector.size(), 2000U);
286 ASSERT_EQ(vector.PopCount(), 500U);
287 ASSERT_EQ(vector.GetHighestBitSet(), 999);
288
289 vector.ClearBit(3000);
290 ASSERT_EQ(vector.size(), 3001U);
291 ASSERT_EQ(vector.PopCount(), 500U);
292 ASSERT_EQ(vector.GetHighestBitSet(), 999);
293
294 vector.SetBit(4000);
295 ASSERT_EQ(vector.size(), 4001U);
296 ASSERT_EQ(vector.PopCount(), 501U);
297 ASSERT_EQ(vector.GetHighestBitSet(), 4000);
298 }
299
300 HWTEST_F(BitVectorTest, Modification, testing::ext::TestSize.Level0)
301 {
302 BitVector<> vec1;
303 TestModification(vec1);
304 BitVector<ArenaAllocator> vec2(GetAllocator());
305 TestModification(vec2);
306 }
307
308 HWTEST_F(BitVectorTest, SetClearBit, testing::ext::TestSize.Level0)
309 {
310 BitVector<> vector;
311
312 vector.SetBit(55);
313 ASSERT_EQ(vector.size(), 56U);
314
315 vector.SetBit(45);
316 ASSERT_EQ(vector.size(), 56U);
317 ASSERT_EQ(vector.PopCount(), 2U);
318
319 vector.ClearBit(105);
320 ASSERT_EQ(vector.size(), 106U);
321 ASSERT_EQ(vector.PopCount(), 2U);
322 ASSERT_EQ(vector.GetHighestBitSet(), 55);
323
324 vector.ClearBit(45);
325 ASSERT_EQ(vector.size(), 106U);
326 ASSERT_EQ(vector.PopCount(), 1U);
327 }
328
329 } // namespace panda::test
330