1 /*
2 * Copyright (c) 2021 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() const40 ArenaAllocator *GetAllocator() const
41 {
42 return allocator_;
43 }
44
45 private:
46 ArenaAllocator *allocator_ {nullptr};
47 };
48
TEST_F(BitVectorTest,Basics)49 TEST_F(BitVectorTest, Basics)
50 {
51 BitVector<> vector;
52 const BitVector<> &cvector = vector;
53 ASSERT_EQ(vector.capacity(), 0);
54
55 // Index iterators for empty vector
56 for (uint32_t i : cvector.GetSetBitsIndices()) {
57 ADD_FAILURE();
58 }
59 for (uint32_t i : cvector.GetZeroBitsIndices()) {
60 ADD_FAILURE();
61 }
62
63 vector.push_back(true);
64 vector.push_back(false);
65 ASSERT_NE(vector.capacity(), 0);
66
67 // Check `GetDataSpan`
68 ASSERT_NE(vector.GetDataSpan().size(), 0);
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(), 0);
82 std::fill(vector.begin() + 2, vector.begin() + 15, true);
83 ASSERT_EQ(vector.PopCount(), 13);
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), 0);
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
TEST_F(BitVectorTest,Comparison)100 TEST_F(BitVectorTest, Comparison)
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 ASSERT_FALSE(vector.empty());
116 ASSERT_EQ(vector.size(), bits);
117
118 std::fill(vector.begin(), vector.end(), true);
119 for (uint32_t i : vector.GetZeroBitsIndices()) {
120 ADD_FAILURE();
121 }
122 int index = 0;
123 for (uint32_t i : vector.GetSetBitsIndices()) {
124 ASSERT_EQ(i, index++);
125 }
126
127 std::fill(vector.begin(), vector.end(), false);
128 for (uint32_t i : vector.GetSetBitsIndices()) {
129 ADD_FAILURE();
130 }
131 index = 0;
132 for (uint32_t i : vector.GetZeroBitsIndices()) {
133 ASSERT_EQ(i, index++);
134 }
135
136 index = 0;
137 for (auto v : vector) {
138 v = (index++ % 2U) != 0;
139 }
140 index = 0;
141 for (auto v : vector) {
142 ASSERT_EQ(v, index++ % 2U);
143 }
144 index = vector.size() - 1;
145 for (auto it = vector.end() - 1;; --it) {
146 ASSERT_EQ(*it, index-- % 2U);
147 if (it == vector.begin()) {
148 break;
149 }
150 }
151 index = 1;
152 for (uint32_t i : vector.GetSetBitsIndices()) {
153 ASSERT_EQ(i, index);
154 index += 2U;
155 }
156 index = 0;
157 for (uint32_t i : vector.GetZeroBitsIndices()) {
158 ASSERT_EQ(i, index);
159 index += 2U;
160 }
161
162 auto it = vector.begin();
163 ASSERT_EQ(*it, false);
164 ++it;
165 ASSERT_EQ(*it, true);
166 auto it1 = it++;
167 ASSERT_EQ(*it, false);
168 ASSERT_EQ(*it1, true);
169 ASSERT_TRUE(it1 < it);
170 it += 3U;
171 ASSERT_EQ(*it, true);
172 it -= 5U;
173 ASSERT_EQ(*it, false);
174 ASSERT_EQ(it, vector.begin());
175
176 it = it + 6U;
177 ASSERT_EQ(*it, false);
178 ASSERT_EQ(std::distance(vector.begin(), it), 6U);
179 ASSERT_EQ(it[1], true);
180 it = it - 3U;
181 ASSERT_EQ(*it, true);
182 ASSERT_EQ(std::distance(vector.begin(), it), 3U);
183 --it;
184 ASSERT_EQ(*it, false);
185 it1 = it--;
186 ASSERT_EQ(*it, true);
187 ASSERT_EQ(*it1, false);
188 ASSERT_TRUE(it1 > it);
189 it = vector.begin() + 100U;
190 ASSERT_EQ(std::distance(vector.begin(), it), 100U);
191 ASSERT_TRUE(it + 2U > it);
192 ASSERT_TRUE(it + 2U >= it);
193 ASSERT_TRUE(it + 0 >= it);
194 ASSERT_TRUE(it - 2U < it);
195 ASSERT_TRUE(it - 2U <= it);
196
197 auto cit = vector.cbegin();
198 ASSERT_EQ(cit, vector.begin());
199 ASSERT_EQ(++cit, ++vector.begin());
200 ASSERT_EQ(vector.cend(), vector.end());
201 }
202
TEST_F(BitVectorTest,Iteration)203 TEST_F(BitVectorTest, Iteration)
204 {
205 std::array<uint32_t, 10U> data {};
206 size_t bits_num = data.size() * BitsNumInValue(data[0]);
207
208 BitVector<> vec1;
209 vec1.resize(bits_num);
210 TestIteration(vec1, bits_num);
211
212 BitVector<ArenaAllocator> vec2(GetAllocator());
213 vec2.resize(bits_num);
214 TestIteration(vec2, bits_num);
215
216 BitVector<ArenaAllocator> vec3(bits_num, GetAllocator());
217 TestIteration(vec3, bits_num);
218
219 BitVectorSpan vec4(Span<uint32_t>(data.data(), data.size()));
220 TestIteration(vec4, bits_num);
221
222 data.fill(0);
223 BitVectorSpan vec5(data.data(), bits_num);
224 TestIteration(vec5, bits_num);
225 }
226
227 template <typename T>
TestModification(T & vector)228 void TestModification(T &vector)
229 {
230 std::vector<bool> values = {false, true, false, true, false, true, false, true, false, true};
231 ASSERT_TRUE(vector.empty());
232 ASSERT_EQ(vector.size(), 0);
233 ASSERT_EQ(vector.PopCount(), 0);
234 ASSERT_EQ(vector.GetHighestBitSet(), -1);
235
236 vector.push_back(true);
237 ASSERT_FALSE(vector.empty());
238 ASSERT_EQ(vector.size(), 1);
239 ASSERT_EQ(vector.PopCount(), 1);
240 ASSERT_EQ(vector.GetHighestBitSet(), 0);
241
242 std::copy(values.begin(), values.end(), std::back_inserter(vector));
243 ASSERT_EQ(vector.size(), 11U);
244 ASSERT_EQ(vector[1], false);
245 ASSERT_EQ(vector.PopCount(), 6U);
246 ASSERT_EQ(vector.GetHighestBitSet(), 10U);
247
248 vector[1] = true;
249 ASSERT_EQ(vector[1], true);
250
251 uint32_t value = 0b10101010111;
252 ASSERT_EQ(std::memcmp(vector.data(), &value, vector.GetSizeInBytes()), 0);
253
254 vector.resize(3U);
255 ASSERT_EQ(vector.size(), 3U);
256 ASSERT_EQ(vector.PopCount(), 3U);
257
258 vector.resize(10U);
259 ASSERT_EQ(vector.PopCount(), 3U);
260
261 vector.clear();
262 ASSERT_TRUE(vector.empty());
263 ASSERT_EQ(vector.size(), 0);
264
265 // Push 1000 values with `true` in odd and `false` in even indexes
266 for (int i = 0; i < 100; i++) {
267 std::copy(values.begin(), values.end(), std::back_inserter(vector));
268 }
269 ASSERT_EQ(vector.size(), 1000U);
270 ASSERT_EQ(vector.PopCount(), 500U);
271 for (size_t i = 0; i < 1000U; i++) {
272 vector.push_back(false);
273 }
274 ASSERT_EQ(vector.size(), 2000U);
275 ASSERT_EQ(vector.PopCount(), 500U);
276 ASSERT_EQ(vector.GetHighestBitSet(), 999U);
277
278 vector.ClearBit(3000U);
279 ASSERT_EQ(vector.size(), 3001U);
280 ASSERT_EQ(vector.PopCount(), 500U);
281 ASSERT_EQ(vector.GetHighestBitSet(), 999U);
282
283 vector.SetBit(4000U);
284 ASSERT_EQ(vector.size(), 4001U);
285 ASSERT_EQ(vector.PopCount(), 501U);
286 ASSERT_EQ(vector.GetHighestBitSet(), 4000U);
287 }
288
TEST_F(BitVectorTest,Modification)289 TEST_F(BitVectorTest, Modification)
290 {
291 BitVector<> vec1;
292 TestModification(vec1);
293 BitVector<ArenaAllocator> vec2(GetAllocator());
294 TestModification(vec2);
295 }
296
TEST_F(BitVectorTest,SetClearBit)297 TEST_F(BitVectorTest, SetClearBit)
298 {
299 BitVector<> vector;
300
301 vector.SetBit(55);
302 ASSERT_EQ(vector.size(), 56);
303
304 vector.SetBit(45);
305 ASSERT_EQ(vector.size(), 56);
306 ASSERT_EQ(vector.PopCount(), 2);
307
308 vector.ClearBit(105);
309 ASSERT_EQ(vector.size(), 106);
310 ASSERT_EQ(vector.PopCount(), 2);
311 ASSERT_EQ(vector.GetHighestBitSet(), 55);
312
313 vector.ClearBit(45);
314 ASSERT_EQ(vector.size(), 106);
315 ASSERT_EQ(vector.PopCount(), 1);
316 }
317
318 } // namespace panda::test
319