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>
TestIteration(T & vector,size_t bits)113 void TestIteration(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 auto it = vector.begin();
165 ASSERT_EQ(*it, false);
166 ++it;
167 ASSERT_EQ(*it, true);
168 auto it1 = it++;
169 ASSERT_EQ(*it, false);
170 ASSERT_EQ(*it1, true);
171 ASSERT_TRUE(it1 < it);
172 it += 3;
173 ASSERT_EQ(*it, true);
174 it -= 5;
175 ASSERT_EQ(*it, false);
176 ASSERT_EQ(it, vector.begin());
177
178 it = it + 6;
179 ASSERT_EQ(*it, false);
180 ASSERT_EQ(std::distance(vector.begin(), it), 6);
181 ASSERT_EQ(it[1], true);
182 it = it - 3;
183 ASSERT_EQ(*it, true);
184 ASSERT_EQ(std::distance(vector.begin(), it), 3);
185 --it;
186 ASSERT_EQ(*it, false);
187 it1 = it--;
188 ASSERT_EQ(*it, true);
189 ASSERT_EQ(*it1, false);
190 ASSERT_TRUE(it1 > it);
191 it = vector.begin() + 100;
192 ASSERT_EQ(std::distance(vector.begin(), it), 100);
193 ASSERT_TRUE(it + 2 > it);
194 ASSERT_TRUE(it + 2 >= it);
195 ASSERT_TRUE(it + 0 >= it);
196 ASSERT_TRUE(it - 2 < it);
197 ASSERT_TRUE(it - 2 <= it);
198
199 auto cit = vector.cbegin();
200 ASSERT_EQ(cit, vector.begin());
201 ASSERT_EQ(++cit, ++vector.begin());
202 ASSERT_EQ(vector.cend(), vector.end());
203 }
204
205 HWTEST_F(BitVectorTest, Iteration, testing::ext::TestSize.Level0)
206 {
207 std::array<uint32_t, 10> data {};
208 size_t bits_num = data.size() * BitsNumInValue(data[0]);
209
210 BitVector<> vec1;
211 vec1.resize(bits_num);
212 TestIteration(vec1, bits_num);
213
214 BitVector<ArenaAllocator> vec2(GetAllocator());
215 vec2.resize(bits_num);
216 TestIteration(vec2, bits_num);
217
218 BitVector<ArenaAllocator> vec3(bits_num, GetAllocator());
219 TestIteration(vec3, bits_num);
220
221 BitVectorSpan vec4(Span<uint32_t>(data.data(), data.size()));
222 TestIteration(vec4, bits_num);
223
224 data.fill(0);
225 BitVectorSpan vec5(data.data(), bits_num);
226 TestIteration(vec5, bits_num);
227 }
228
229 template <typename T>
TestModification(T & vector)230 void TestModification(T &vector)
231 {
232 std::vector<bool> values = {false, true, false, true, false, true, false, true, false, true};
233 ASSERT_TRUE(vector.empty());
234 ASSERT_EQ(vector.size(), 0U);
235 ASSERT_EQ(vector.PopCount(), 0U);
236 ASSERT_EQ(vector.GetHighestBitSet(), -1);
237
238 vector.push_back(true);
239 ASSERT_FALSE(vector.empty());
240 ASSERT_EQ(vector.size(), 1U);
241 ASSERT_EQ(vector.PopCount(), 1U);
242 ASSERT_EQ(vector.GetHighestBitSet(), 0);
243
244 std::copy(values.begin(), values.end(), std::back_inserter(vector));
245 ASSERT_EQ(vector.size(), 11U);
246 ASSERT_EQ(vector[1], false);
247 ASSERT_EQ(vector.PopCount(), 6U);
248 ASSERT_EQ(vector.GetHighestBitSet(), 10);
249
250 vector[1] = true;
251 ASSERT_EQ(vector[1], true);
252
253 uint32_t value = 0b10101010111;
254 ASSERT_EQ(std::memcmp(vector.data(), &value, vector.GetSizeInBytes()), 0);
255
256 vector.resize(3);
257 ASSERT_EQ(vector.size(), 3U);
258 ASSERT_EQ(vector.PopCount(), 3U);
259
260 vector.resize(10);
261 ASSERT_EQ(vector.PopCount(), 3U);
262
263 vector.clear();
264 ASSERT_TRUE(vector.empty());
265 ASSERT_EQ(vector.size(), 0U);
266
267 // Push 1000 values with `true` in odd and `false` in even indexes
268 for (int i = 0; i < 100; i++) {
269 std::copy(values.begin(), values.end(), std::back_inserter(vector));
270 }
271 ASSERT_EQ(vector.size(), 1000U);
272 ASSERT_EQ(vector.PopCount(), 500U);
273 for (int i = 0; i < 1000; i++) {
274 vector.push_back(false);
275 }
276 ASSERT_EQ(vector.size(), 2000U);
277 ASSERT_EQ(vector.PopCount(), 500U);
278 ASSERT_EQ(vector.GetHighestBitSet(), 999);
279
280 vector.ClearBit(3000);
281 ASSERT_EQ(vector.size(), 3001U);
282 ASSERT_EQ(vector.PopCount(), 500U);
283 ASSERT_EQ(vector.GetHighestBitSet(), 999);
284
285 vector.SetBit(4000);
286 ASSERT_EQ(vector.size(), 4001U);
287 ASSERT_EQ(vector.PopCount(), 501U);
288 ASSERT_EQ(vector.GetHighestBitSet(), 4000);
289 }
290
291 HWTEST_F(BitVectorTest, Modification, testing::ext::TestSize.Level0)
292 {
293 BitVector<> vec1;
294 TestModification(vec1);
295 BitVector<ArenaAllocator> vec2(GetAllocator());
296 TestModification(vec2);
297 }
298
299 HWTEST_F(BitVectorTest, SetClearBit, testing::ext::TestSize.Level0)
300 {
301 BitVector<> vector;
302
303 vector.SetBit(55);
304 ASSERT_EQ(vector.size(), 56U);
305
306 vector.SetBit(45);
307 ASSERT_EQ(vector.size(), 56U);
308 ASSERT_EQ(vector.PopCount(), 2U);
309
310 vector.ClearBit(105);
311 ASSERT_EQ(vector.size(), 106U);
312 ASSERT_EQ(vector.PopCount(), 2U);
313 ASSERT_EQ(vector.GetHighestBitSet(), 55);
314
315 vector.ClearBit(45);
316 ASSERT_EQ(vector.size(), 106U);
317 ASSERT_EQ(vector.PopCount(), 1U);
318 }
319
320 } // namespace panda::test
321