1 /*
2 * Copyright (c) 2021-2024 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 ark::test {
23
24 // NOLINTBEGIN(readability-magic-numbers)
25
26 class BitVectorTest : public ::testing::Test {
27 public:
28 NO_MOVE_SEMANTIC(BitVectorTest);
29 NO_COPY_SEMANTIC(BitVectorTest);
30
BitVectorTest()31 BitVectorTest()
32 {
33 ark::mem::MemConfig::Initialize(0, 64_MB, 256_MB, 32_MB, 0, 0);
34 PoolManager::Initialize();
35 allocator_ = new ArenaAllocator(SpaceType::SPACE_TYPE_COMPILER);
36 }
37
~BitVectorTest()38 ~BitVectorTest() override
39 {
40 delete allocator_;
41 PoolManager::Finalize();
42 ark::mem::MemConfig::Finalize();
43 }
44
GetAllocator()45 ArenaAllocator *GetAllocator()
46 {
47 return allocator_;
48 }
49
50 private:
51 ArenaAllocator *allocator_ {nullptr};
52 };
53
TEST_F(BitVectorTest,Basics)54 TEST_F(BitVectorTest, Basics)
55 {
56 BitVector<> vector;
57 const BitVector<> &cvector = vector;
58 ASSERT_EQ(vector.capacity(), 0U);
59
60 // Index iterators for empty vector
61 for (uint32_t i : cvector.GetSetBitsIndices()) {
62 (void)i;
63 ADD_FAILURE();
64 }
65 for (uint32_t i : cvector.GetZeroBitsIndices()) {
66 (void)i;
67 ADD_FAILURE();
68 }
69
70 vector.push_back(true);
71 vector.push_back(false);
72 ASSERT_NE(vector.capacity(), 0U);
73
74 // Check `GetDataSpan`
75 ASSERT_NE(vector.GetDataSpan().size(), 0U);
76 uint32_t value = 1;
77 ASSERT_EQ(std::memcmp(vector.GetDataSpan().data(), &value, 1U), 0U);
78
79 // Constant operator[]
80 ASSERT_EQ(cvector[0U], vector[0U]);
81
82 // Constant versions of begin and end
83 ASSERT_EQ(cvector.begin(), vector.begin());
84 ASSERT_EQ(cvector.end(), vector.end());
85
86 vector.resize(20U);
87 std::fill(vector.begin(), vector.end(), false);
88 ASSERT_EQ(vector.PopCount(), 0U);
89 std::fill(vector.begin() + 2U, vector.begin() + 15U, true);
90 ASSERT_EQ(vector.PopCount(), 13U);
91 for (size_t i = 0; i < 15U; i++) {
92 if (i > 2U) {
93 ASSERT_EQ(vector.PopCount(i), i - 2L);
94 } else {
95 ASSERT_EQ(vector.PopCount(i), 0U);
96 }
97 }
98 ASSERT_EQ(vector.GetHighestBitSet(), 14U);
99 ASSERT_EQ(vector[0U], false);
100 ASSERT_EQ(vector[1U], false);
101 ASSERT_EQ(vector[2U], true);
102
103 ASSERT_EQ(vector, vector.GetFixed());
104 ASSERT_FALSE(vector.GetContainerDataSpan().empty());
105 }
106
TEST_F(BitVectorTest,Comparison)107 TEST_F(BitVectorTest, Comparison)
108 {
109 std::vector<bool> values = {false, true, false, true, false, true, false, true, false, true};
110 BitVector<> vec1;
111 std::copy(values.begin(), values.end(), std::back_inserter(vec1));
112 BitVector<ArenaAllocator> vec2(GetAllocator());
113 std::copy(values.begin(), values.end(), std::back_inserter(vec2));
114 ASSERT_EQ(vec1, vec2);
115 vec2[0U] = true;
116 ASSERT_NE(vec1, vec2);
117 }
118
119 template <typename T>
CheckIterator(T & vector)120 void CheckIterator(T &vector)
121 {
122 auto it = vector.begin();
123 ASSERT_EQ(*it, false);
124 ++it;
125 ASSERT_EQ(*it, true);
126 auto it1 = it++;
127 ASSERT_EQ(*it, false);
128 ASSERT_EQ(*it1, true);
129 ASSERT_TRUE(it1 < it);
130 it += 3U;
131 ASSERT_EQ(*it, true);
132 it -= 5U;
133 ASSERT_EQ(*it, false);
134 ASSERT_EQ(it, vector.begin());
135
136 it = it + 6U;
137 ASSERT_EQ(*it, false);
138 ASSERT_EQ(std::distance(vector.begin(), it), 6U);
139 ASSERT_EQ(it[1U], true);
140 it = it - 3L;
141 ASSERT_EQ(*it, true);
142 ASSERT_EQ(std::distance(vector.begin(), it), 3U);
143 --it;
144 ASSERT_EQ(*it, false);
145 it1 = it--;
146 ASSERT_EQ(*it, true);
147 ASSERT_EQ(*it1, false);
148 ASSERT_TRUE(it1 > it);
149 it = vector.begin() + 100U;
150 ASSERT_EQ(std::distance(vector.begin(), it), 100U);
151 ASSERT_TRUE(it + 2U > it);
152 ASSERT_TRUE(it + 2U >= it);
153 ASSERT_TRUE(it + 0U >= it);
154 ASSERT_TRUE(it - 2L < it);
155 ASSERT_TRUE(it - 2L <= it);
156
157 auto cit = vector.cbegin();
158 ASSERT_EQ(cit, vector.begin());
159 ASSERT_EQ(++cit, ++vector.begin());
160 ASSERT_EQ(vector.cend(), vector.end());
161 }
162
163 template <typename T>
TestIteration(T & vector,size_t bits)164 void TestIteration(T &vector, size_t bits)
165 {
166 int index = 0;
167
168 ASSERT_FALSE(vector.empty());
169 ASSERT_EQ(vector.size(), bits);
170
171 std::fill(vector.begin(), vector.end(), true);
172 for (uint32_t i : vector.GetZeroBitsIndices()) {
173 ADD_FAILURE();
174 }
175 index = 0;
176 for (uint32_t i : vector.GetSetBitsIndices()) {
177 ASSERT_EQ(i, index++);
178 }
179
180 std::fill(vector.begin(), vector.end(), false);
181 for (uint32_t i : vector.GetSetBitsIndices()) {
182 ADD_FAILURE();
183 }
184 index = 0;
185 for (uint32_t i : vector.GetZeroBitsIndices()) {
186 ASSERT_EQ(i, index++);
187 }
188
189 index = 0;
190 for (auto v : vector) {
191 v = (index++ % 2U) != 0;
192 }
193 index = 0;
194 for (auto v : vector) {
195 ASSERT_EQ(v, index++ % 2U);
196 }
197 index = vector.size() - 1U;
198 for (auto it = vector.end() - 1U;; --it) {
199 ASSERT_EQ(*it, index-- % 2U);
200 if (it == vector.begin()) {
201 break;
202 }
203 }
204 index = 1;
205 for (uint32_t i : vector.GetSetBitsIndices()) {
206 ASSERT_EQ(i, index);
207 index += 2U;
208 }
209 index = 0;
210 for (uint32_t i : vector.GetZeroBitsIndices()) {
211 ASSERT_EQ(i, index);
212 index += 2U;
213 }
214
215 CheckIterator(vector);
216 }
217
TEST_F(BitVectorTest,Iteration)218 TEST_F(BitVectorTest, Iteration)
219 {
220 std::array<uint32_t, 10U> data {};
221 size_t bitsNum = data.size() * BitsNumInValue(data[0U]);
222
223 BitVector<> vec1;
224 vec1.resize(bitsNum);
225 TestIteration(vec1, bitsNum);
226
227 BitVector<ArenaAllocator> vec2(GetAllocator());
228 vec2.resize(bitsNum);
229 TestIteration(vec2, bitsNum);
230
231 BitVector<ArenaAllocator> vec3(bitsNum, GetAllocator());
232 TestIteration(vec3, bitsNum);
233
234 BitVectorSpan vec4(Span<uint32_t>(data.data(), data.size()));
235 TestIteration(vec4, bitsNum);
236
237 data.fill(0U);
238 BitVectorSpan vec5(data.data(), bitsNum);
239 TestIteration(vec5, bitsNum);
240 }
241
242 template <typename T>
TestModification(T & vector)243 void TestModification(T &vector)
244 {
245 std::vector<bool> values = {false, true, false, true, false, true, false, true, false, true};
246 ASSERT_TRUE(vector.empty());
247 ASSERT_EQ(vector.size(), 0U);
248 ASSERT_EQ(vector.PopCount(), 0U);
249 ASSERT_EQ(vector.GetHighestBitSet(), -1L);
250
251 vector.push_back(true);
252 ASSERT_FALSE(vector.empty());
253 ASSERT_EQ(vector.size(), 1U);
254 ASSERT_EQ(vector.PopCount(), 1U);
255 ASSERT_EQ(vector.GetHighestBitSet(), 0U);
256
257 std::copy(values.begin(), values.end(), std::back_inserter(vector));
258 ASSERT_EQ(vector.size(), 11U);
259 ASSERT_EQ(vector[1U], false);
260 ASSERT_EQ(vector.PopCount(), 6U);
261 ASSERT_EQ(vector.GetHighestBitSet(), 10U);
262
263 vector[1U] = true;
264 ASSERT_EQ(vector[1U], true);
265
266 uint32_t value = 0b10101010111;
267 ASSERT_EQ(std::memcmp(vector.data(), &value, vector.GetSizeInBytes()), 0U);
268
269 vector.resize(3U);
270 ASSERT_EQ(vector.size(), 3U);
271 ASSERT_EQ(vector.PopCount(), 3U);
272
273 vector.resize(10U);
274 ASSERT_EQ(vector.PopCount(), 3U);
275
276 vector.clear();
277 ASSERT_TRUE(vector.empty());
278 ASSERT_EQ(vector.size(), 0U);
279
280 // Push 1000 values with `true` in odd and `false` in even indexes
281 for (size_t i = 0; i < 100U; i++) {
282 std::copy(values.begin(), values.end(), std::back_inserter(vector));
283 }
284 ASSERT_EQ(vector.size(), 1000U);
285 ASSERT_EQ(vector.PopCount(), 500U);
286 for (size_t i = 0; i < 1000U; i++) {
287 vector.push_back(false);
288 }
289 ASSERT_EQ(vector.size(), 2000U);
290 ASSERT_EQ(vector.PopCount(), 500U);
291 ASSERT_EQ(vector.GetHighestBitSet(), 999U);
292
293 vector.ClearBit(3000U);
294 ASSERT_EQ(vector.size(), 3001U);
295 ASSERT_EQ(vector.PopCount(), 500U);
296 ASSERT_EQ(vector.GetHighestBitSet(), 999U);
297
298 vector.SetBit(4000U);
299 ASSERT_EQ(vector.size(), 4001U);
300 ASSERT_EQ(vector.PopCount(), 501U);
301 ASSERT_EQ(vector.GetHighestBitSet(), 4000U);
302 }
303
TEST_F(BitVectorTest,Modification)304 TEST_F(BitVectorTest, Modification)
305 {
306 BitVector<> vec1;
307 TestModification(vec1);
308 BitVector<ArenaAllocator> vec2(GetAllocator());
309 TestModification(vec2);
310 }
311
TEST_F(BitVectorTest,SetClearBit)312 TEST_F(BitVectorTest, SetClearBit)
313 {
314 BitVector<> vector;
315
316 vector.SetBit(55U);
317 ASSERT_EQ(vector.size(), 56U);
318
319 vector.SetBit(45U);
320 ASSERT_EQ(vector.size(), 56U);
321 ASSERT_EQ(vector.PopCount(), 2U);
322
323 vector.ClearBit(105U);
324 ASSERT_EQ(vector.size(), 106U);
325 ASSERT_EQ(vector.PopCount(), 2U);
326 ASSERT_EQ(vector.GetHighestBitSet(), 55U);
327
328 vector.ClearBit(45U);
329 ASSERT_EQ(vector.size(), 106U);
330 ASSERT_EQ(vector.PopCount(), 1U);
331 }
332
TEST_F(BitVectorTest,TestUnion)333 TEST_F(BitVectorTest, TestUnion)
334 {
335 {
336 BitVector<> vector0;
337 BitVector<> vector1;
338
339 vector0 |= vector1;
340 ASSERT_TRUE(vector0.empty());
341 }
342
343 {
344 BitVector<> vector0;
345 vector0.SetBit(13U);
346 vector0.SetBit(71U);
347
348 BitVector<> vector1;
349 vector1.SetBit(10U);
350 vector1.SetBit(13U);
351 vector1.SetBit(42U);
352 vector1.SetBit(77U);
353
354 vector0 |= vector1;
355 ASSERT_EQ(vector0.size(), 78U);
356 ASSERT_EQ(vector0.PopCount(), 5U);
357 ASSERT_TRUE(vector0.GetBit(10U));
358 ASSERT_TRUE(vector0.GetBit(13U));
359 ASSERT_TRUE(vector0.GetBit(42U));
360 ASSERT_TRUE(vector0.GetBit(71U));
361 ASSERT_TRUE(vector0.GetBit(77U));
362
363 ASSERT_EQ(vector1.PopCount(), 4U);
364 }
365
366 {
367 BitVector<> vector0;
368 vector0.SetBit(1U);
369
370 BitVector<> vector1;
371 vector1.SetBit(128U);
372
373 vector0 |= vector1;
374
375 ASSERT_EQ(vector0.size(), 129U);
376 ASSERT_EQ(vector0.PopCount(), 2U);
377 ASSERT_TRUE(vector0.GetBit(1U));
378 ASSERT_TRUE(vector0.GetBit(128U));
379 }
380
381 {
382 BitVector<> vector0;
383 vector0.SetBit(128U);
384
385 BitVector<> vector1;
386 vector1.SetBit(1U);
387
388 vector0 |= vector1;
389
390 ASSERT_EQ(vector0.size(), 129U);
391 ASSERT_EQ(vector0.PopCount(), 2U);
392 ASSERT_TRUE(vector0.GetBit(1U));
393 ASSERT_TRUE(vector0.GetBit(128U));
394 }
395 }
396
397 // NOLINTEND(readability-magic-numbers)
398
399 } // namespace ark::test
400