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_table.h"
17 #include "mem/pool_manager.h"
18
19 #include <gtest/gtest.h>
20
21 namespace panda::test {
22
23 class BitTableTest : public ::testing::Test {
24 public:
BitTableTest()25 BitTableTest()
26 {
27 panda::mem::MemConfig::Initialize(0, 64_MB, 256_MB, 32_MB);
28 PoolManager::Initialize();
29 allocator_ = new ArenaAllocator(SpaceType::SPACE_TYPE_COMPILER);
30 }
31
~BitTableTest()32 virtual ~BitTableTest()
33 {
34 delete allocator_;
35 PoolManager::Finalize();
36 panda::mem::MemConfig::Finalize();
37 }
38
GetAllocator()39 ArenaAllocator *GetAllocator()
40 {
41 return allocator_;
42 }
43
44 private:
45 ArenaAllocator *allocator_ {nullptr};
46 };
47
48 template <typename C, size_t N>
CreateEntry(std::array<uint32_t,N> data)49 typename C::Entry CreateEntry(std::array<uint32_t, N> data)
50 {
51 typename C::Entry entry;
52 static_assert(N == C::NUM_COLUMNS);
53 for (size_t i = 0; i < N; i++) {
54 entry[i] = data[i];
55 }
56 return entry;
57 }
58
TEST_F(BitTableTest,EmptyTable)59 TEST_F(BitTableTest, EmptyTable)
60 {
61 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
62 data.reserve(1_KB);
63
64 BitTableBuilder<BitTableDefault<1>> builder(GetAllocator());
65 using Builder = decltype(builder);
66 BitMemoryStreamOut out(&data);
67 builder.Encode(out);
68
69 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
70 BitTable<BitTableDefault<1>> table;
71 table.Decode(&in);
72
73 ASSERT_EQ(table.GetRowsCount(), 0);
74 ASSERT_EQ(table.begin(), table.end());
75 }
76
TEST_F(BitTableTest,SingleNoValue)77 TEST_F(BitTableTest, SingleNoValue)
78 {
79 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
80 data.reserve(1_KB);
81
82 BitTableBuilder<BitTableDefault<1>> builder(GetAllocator());
83 using Builder = decltype(builder);
84 builder.Emplace(Builder::Entry({Builder::NO_VALUE}));
85 BitMemoryStreamOut out(&data);
86 builder.Encode(out);
87
88 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
89 BitTable<BitTableDefault<1>> table;
90 table.Decode(&in);
91
92 ASSERT_EQ(table.GetRowsCount(), 1);
93 ASSERT_FALSE(table.GetRow(0).Has(0));
94 ASSERT_EQ(table.GetRow(0).Get(0), Builder::NO_VALUE);
95 ASSERT_TRUE(
96 std::all_of(table.begin(), table.end(), [](const auto &row) { return row.Get(0) == Builder::NO_VALUE; }));
97 }
98
TEST_F(BitTableTest,SingleColumn)99 TEST_F(BitTableTest, SingleColumn)
100 {
101 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
102 data.reserve(1_KB);
103
104 BitTableBuilder<BitTableDefault<1>> builder(GetAllocator());
105 using Builder = decltype(builder);
106 builder.Emplace(Builder::Entry({9}));
107 builder.Emplace(Builder::Entry({Builder::NO_VALUE}));
108 builder.Emplace(Builder::Entry({19}));
109 builder.Emplace(Builder::Entry({29}));
110
111 BitMemoryStreamOut out(&data);
112 builder.Encode(out);
113
114 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
115 BitTable<BitTableDefault<1>> table;
116 table.Decode(&in);
117
118 ASSERT_EQ(table.GetRowsCount(), 4);
119 ASSERT_EQ(table.GetRow(0).Get(0), 9);
120 ASSERT_FALSE(table.GetRow(1).Has(0));
121 ASSERT_EQ(table.GetRow(2).Get(0), 19);
122 ASSERT_EQ(table.GetRow(3).Get(0), 29);
123 }
124
TEST_F(BitTableTest,MultipleColumns)125 TEST_F(BitTableTest, MultipleColumns)
126 {
127 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
128 data.reserve(1_KB);
129
130 std::array<std::array<uint32_t, 10>, 5> values = {
131 {{0U, 1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U, 9U},
132 {10U, 11U, 12U, 13U, 14U, 15U, 16U, 17U, 18U, 19U},
133 {0_KB, 1_KB + 1, 1_KB + 2, 1_KB + 3, 1_KB + 4, 1_KB + 5, 1_KB + 6, 1_KB + 7, 1_KB + 8, 1_KB + 9},
134 {0_MB, 0_MB + 1, 1_MB + 2, 1_MB + 3, 1_MB + 4, 1_MB + 5, 1_MB + 6, 1_MB + 7, 1_MB + 8, 1_MB + 9},
135 {0_GB, 0_GB + 1, 0_GB + 2, 1_GB + 3, 1_GB + 4, 1_GB + 5, 1_GB + 6, 1_GB + 7, 1_GB + 8, 1_GB + 9}}};
136
137 BitTableBuilder<BitTableDefault<10>> builder(GetAllocator());
138 builder.Emplace(CreateEntry<decltype(builder)>(values[0]));
139 builder.Emplace(CreateEntry<decltype(builder)>(values[1]));
140 builder.Emplace(CreateEntry<decltype(builder)>(values[2]));
141 builder.Emplace(CreateEntry<decltype(builder)>(values[3]));
142 builder.Emplace(CreateEntry<decltype(builder)>(values[4]));
143
144 BitMemoryStreamOut out(&data);
145 builder.Encode(out);
146
147 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
148 BitTable<BitTableDefault<10>> table;
149 table.Decode(&in);
150
151 ASSERT_EQ(table.GetRowsCount(), 5);
152
153 size_t row_index = 0;
154 for (auto row : table) {
155 for (size_t i = 0; i < row.ColumnsCount(); i++) {
156 ASSERT_EQ(row.Get(i), values[row_index][i]);
157 }
158 row_index++;
159 }
160 }
161
162 class TestAccessor : public BitTableRow<2, TestAccessor> {
163 public:
164 using Base = BitTableRow<2, TestAccessor>;
165 using Base::Base;
166
167 static_assert(Base::NUM_COLUMNS == 2);
168
GetField0()169 uint32_t GetField0()
170 {
171 return Base::Get(0);
172 }
GetField1()173 uint32_t GetField1()
174 {
175 return Base::Get(1);
176 }
GetName(size_t index)177 const char *GetName(size_t index)
178 {
179 ASSERT(index < Base::ColumnsCount());
180 static constexpr const char *names[] = {"field0", "field1"};
181 return names[index];
182 }
183
184 enum { FIELD0, FIELD1 };
185 };
186
TEST_F(BitTableTest,CustomAccessor)187 TEST_F(BitTableTest, CustomAccessor)
188 {
189 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
190 data.reserve(1_KB);
191
192 using Builder = BitTableBuilder<TestAccessor>;
193
194 Builder builder(GetAllocator());
195 {
196 Builder::Entry entry;
197 entry[TestAccessor::FIELD0] = 1;
198 entry[TestAccessor::FIELD1] = 2;
199 builder.Emplace(entry);
200 }
201 {
202 Builder::Entry entry;
203 entry[TestAccessor::FIELD0] = 3;
204 entry[TestAccessor::FIELD1] = 4;
205 builder.Emplace(entry);
206 }
207
208 BitMemoryStreamOut out(&data);
209 builder.Encode(out);
210
211 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
212 BitTable<TestAccessor> table;
213 table.Decode(&in);
214
215 ASSERT_EQ(table.GetRowsCount(), 2);
216 ASSERT_EQ(table.GetRow(0).GetField0(), 1);
217 ASSERT_EQ(table.GetRow(0).GetField1(), 2);
218 ASSERT_EQ(table.GetRow(1).GetField0(), 3);
219 ASSERT_EQ(table.GetRow(1).GetField1(), 4);
220
221 int idx = 1;
222 for (auto &row : table) {
223 for (size_t i = 0; i < row.ColumnsCount(); i++) {
224 ASSERT_EQ(row.Get(i), idx++);
225 }
226 }
227 }
228
InitRangesTest(std::array<std::array<uint32_t,2>,10> & values,BitTable<TestAccessor> & table)229 void InitRangesTest(std::array<std::array<uint32_t, 2>, 10> &values, BitTable<TestAccessor> &table)
230 {
231 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
232 data.reserve(1_KB);
233
234 BitTableBuilder<TestAccessor> builder(GetAllocator());
235 for (auto &v : values) {
236 builder.Emplace(CreateEntry<decltype(builder)>(v));
237 }
238
239 BitMemoryStreamOut out(&data);
240 builder.Encode(out);
241
242 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
243 BitTable<TestAccessor> table;
244 table.Decode(&in);
245
246 ASSERT_EQ(table.GetRowsCount(), 10);
247 ASSERT_EQ(table.GetColumnsCount(), 2);
248 }
249
TEST_F(BitTableTest,RangesTest1)250 TEST_F(BitTableTest, RangesTest1)
251 {
252 std::array<std::array<uint32_t, 2>, 10> values = {
253 {{0U, 10U}, {1U, 11U}, {2U, 12U}, {3U, 13U}, {4U, 14U}, {5U, 15U}, {6U, 16U}, {7U, 17U}, {8U, 18U}, {9U, 19U}}};
254 BitTable<TestAccessor> table;
255 InitRangesTest(values, table);
256
257 {
258 auto range = table.GetRange(0, 6);
259 auto it = range.begin();
260 ASSERT_EQ(range[0].GetField0(), values[0][0]);
261 ASSERT_EQ(range[0].GetField1(), values[0][1]);
262 ASSERT_EQ(range[1].GetField0(), values[1][0]);
263 ASSERT_EQ(range[1].GetField1(), values[1][1]);
264 ASSERT_EQ(range[2].GetField0(), values[2][0]);
265 ASSERT_EQ(range[2].GetField1(), values[2][1]);
266 ASSERT_EQ(range[3].GetField0(), values[3][0]);
267 ASSERT_EQ(range[3].GetField1(), values[3][1]);
268 ASSERT_EQ(range[4].GetField0(), values[4][0]);
269 ASSERT_EQ(range[4].GetField1(), values[4][1]);
270 ASSERT_EQ(range[5].GetField0(), values[5][0]);
271 ASSERT_EQ(range[5].GetField1(), values[5][1]);
272
273 size_t i = 0;
274 for (auto &v : table.GetRange(0, 6)) {
275 ASSERT_EQ(v.GetField0(), values[i][0]);
276 ASSERT_EQ(v.GetField1(), values[i][1]);
277 i++;
278 }
279 ASSERT_EQ(i, 6);
280
281 i = 0;
282 for (auto &v : table) {
283 ASSERT_EQ(v.GetField0(), values[i][0]);
284 ASSERT_EQ(v.GetField1(), values[i][1]);
285 i++;
286 }
287 ASSERT_EQ(i, 10);
288 }
289 }
290
TEST_F(BitTableTest,RangesTest2)291 TEST_F(BitTableTest, RangesTest2)
292 {
293 std::array<std::array<uint32_t, 2>, 10> values = {
294 {{0U, 10U}, {1U, 11U}, {2U, 12U}, {3U, 13U}, {4U, 14U}, {5U, 15U}, {6U, 16U}, {7U, 17U}, {8U, 18U}, {9U, 19U}}};
295 BitTable<TestAccessor> table;
296
297 InitRangesTest(values, table);
298
299 {
300 auto range = table.GetRangeReversed(4, 10);
301 auto it = range.begin();
302 ASSERT_EQ(range[0].GetField0(), values[9][0]);
303 ASSERT_EQ(range[0].GetField1(), values[9][1]);
304 ASSERT_EQ(range[1].GetField0(), values[8][0]);
305 ASSERT_EQ(range[1].GetField1(), values[8][1]);
306 ASSERT_EQ(range[2].GetField0(), values[7][0]);
307 ASSERT_EQ(range[2].GetField1(), values[7][1]);
308 ASSERT_EQ(range[3].GetField0(), values[6][0]);
309 ASSERT_EQ(range[3].GetField1(), values[6][1]);
310 ASSERT_EQ(range[4].GetField0(), values[5][0]);
311 ASSERT_EQ(range[4].GetField1(), values[5][1]);
312
313 int i = 10;
314 for (auto &v : table.GetRangeReversed(4, 10)) {
315 ASSERT_EQ(v.GetField0(), values[i - 1][0]);
316 ASSERT_EQ(v.GetField1(), values[i - 1][1]);
317 i--;
318 }
319 ASSERT_EQ(i, 4);
320
321 i = 10;
322 for (auto &v : table.GetRangeReversed()) {
323 ASSERT_EQ(v.GetField0(), values[i - 1][0]);
324 ASSERT_EQ(v.GetField1(), values[i - 1][1]);
325 i--;
326 }
327 ASSERT_EQ(i, 0);
328 }
329 }
330
TEST_F(BitTableTest,RangesTest3)331 TEST_F(BitTableTest, RangesTest3)
332 {
333 std::array<std::array<uint32_t, 2>, 10> values = {
334 {{0U, 10U}, {1U, 11U}, {2U, 12U}, {3U, 13U}, {4U, 14U}, {5U, 15U}, {6U, 16U}, {7U, 17U}, {8U, 18U}, {9U, 19U}}};
335 BitTable<TestAccessor> table;
336
337 InitRangesTest(values, table);
338
339 {
340 auto range = table.GetRange(0, 0);
341 ASSERT_EQ(range.begin(), range.end());
342
343 size_t i = 0;
344 for (auto &v : range) {
345 i++;
346 }
347 ASSERT_EQ(i, 0);
348 }
349
350 {
351 auto range = table.GetRangeReversed(0, 0);
352 ASSERT_EQ(range.begin(), range.end());
353
354 size_t i = 0;
355 for (auto &v : range) {
356 i++;
357 }
358 ASSERT_EQ(i, 0);
359 }
360 }
361
TEST_F(BitTableTest,Deduplication)362 TEST_F(BitTableTest, Deduplication)
363 {
364 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
365 data.reserve(1_KB);
366
367 using Builder = BitTableBuilder<TestAccessor>;
368 using Entry = Builder::Entry;
369
370 Builder builder(GetAllocator());
371
372 std::array<Entry, 3> values = {Entry {1}, Entry {2}, Entry {3}};
373
374 ASSERT_EQ(0U, builder.Add(values[0]));
375 ASSERT_EQ(1U, builder.Add(values[1]));
376 ASSERT_EQ(0U, builder.Add(values[0]));
377 ASSERT_EQ(2U, builder.Add(values[2]));
378 ASSERT_EQ(1U, builder.Add(values[1]));
379 ASSERT_EQ(2U, builder.Add(values[2]));
380
381 ASSERT_EQ(3U, builder.AddArray(Span<Entry>(values.begin(), 2)));
382 ASSERT_EQ(1U, builder.AddArray(Span<Entry>(values.begin() + 1, 1)));
383 ASSERT_EQ(5U, builder.AddArray(Span<Entry>(values.begin() + 1, 2)));
384 ASSERT_EQ(3U, builder.AddArray(Span<Entry>(values.begin(), 2)));
385 ASSERT_EQ(5U, builder.AddArray(Span<Entry>(values.begin() + 1, 2)));
386 }
387
TEST_F(BitTableTest,Bitmap)388 TEST_F(BitTableTest, Bitmap)
389 {
390 uint64_t pattern = 0xBADDCAFEDEADF00DULL;
391
392 BitmapTableBuilder builder(GetAllocator());
393
394 ArenaVector<std::pair<uint32_t, uint64_t>> values(GetAllocator()->Adapter());
395 for (size_t i = 0; i <= 64; i++) {
396 uint64_t mask = (i == 64) ? std::numeric_limits<uint64_t>::max() : ((1ULL << i) - 1);
397 uint64_t value = pattern & mask;
398 BitVector<ArenaAllocator> vec(MinimumBitsToStore(value), GetAllocator());
399 vec.Reset();
400 for (size_t j = 0; j < i; j++) {
401 if ((value & (1ULL << j)) != 0) {
402 vec.SetBit(j);
403 }
404 }
405 auto fixed_vec = vec.GetFixed();
406 values.push_back({builder.Add(fixed_vec), value});
407 }
408
409 // Zero value also occupies row in the table
410 ASSERT_EQ(Popcount(pattern), builder.GetRowsCount());
411
412 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
413 data.reserve(10_KB);
414 BitMemoryStreamOut out(&data);
415 builder.Encode(out);
416
417 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
418 BitTable<BitTableDefault<1>> table;
419 table.Decode(&in);
420
421 ASSERT_EQ(table.GetRowSizeInBits(), MinimumBitsToStore(pattern));
422
423 for (auto &[index, value] : values) {
424 if (index != BitTableDefault<1>::NO_VALUE) {
425 ASSERT_EQ(table.GetBitMemoryRegion(index).Read<uint64_t>(0, table.GetRowSizeInBits()), value);
426 }
427 }
428 }
429
430 template <typename T>
FillVector(T & vector,uint32_t value)431 void FillVector(T &vector, uint32_t value)
432 {
433 auto sp = vector.GetDataSpan();
434 std::fill(sp.begin(), sp.end(), value);
435 }
436
TEST_F(BitTableTest,BitmapDeduplication)437 TEST_F(BitTableTest, BitmapDeduplication)
438 {
439 BitmapTableBuilder builder(GetAllocator());
440 std::array<uint32_t, 128> buff;
441 std::array fixed_vectors = {ArenaBitVectorSpan(&buff[0], 23), ArenaBitVectorSpan(&buff[1], 48),
442 ArenaBitVectorSpan(&buff[3], 0), ArenaBitVectorSpan(&buff[4], 123),
443 ArenaBitVectorSpan(&buff[8], 48)};
444 std::array vectors = {ArenaBitVector(GetAllocator()), ArenaBitVector(GetAllocator()),
445 ArenaBitVector(GetAllocator()), ArenaBitVector(GetAllocator()),
446 ArenaBitVector(GetAllocator())};
447 FillVector(fixed_vectors[0], 0x23232323);
448 FillVector(fixed_vectors[1], 0x48484848);
449 FillVector(fixed_vectors[2], 0);
450 FillVector(fixed_vectors[3], 0x23123123);
451 FillVector(fixed_vectors[4], 0x48484848);
452 ASSERT_EQ(fixed_vectors[1], fixed_vectors[4]);
453 vectors[0].resize(1);
454 vectors[1].resize(23);
455 vectors[2].resize(123);
456 vectors[3].resize(234);
457 vectors[4].resize(0);
458 FillVector(vectors[0], 0x1);
459 FillVector(vectors[1], 0x11111111);
460 FillVector(vectors[2], 0x23123123);
461 FillVector(vectors[3], 0x34234234);
462 ASSERT_EQ(builder.Add(fixed_vectors[0].GetFixed()), 0);
463 ASSERT_EQ(builder.Add(fixed_vectors[1].GetFixed()), 1);
464 ASSERT_EQ(builder.Add(fixed_vectors[2].GetFixed()), BitTableDefault<1>::NO_VALUE);
465 ASSERT_EQ(builder.Add(fixed_vectors[3].GetFixed()), 2);
466 ASSERT_EQ(builder.Add(fixed_vectors[4].GetFixed()), 1);
467 ASSERT_EQ(builder.Add(vectors[0].GetFixed()), 3);
468 ASSERT_EQ(builder.Add(vectors[1].GetFixed()), 4);
469 ASSERT_EQ(builder.Add(vectors[2].GetFixed()), 2);
470 ASSERT_EQ(builder.Add(vectors[3].GetFixed()), 5);
471 ASSERT_EQ(builder.Add(vectors[4].GetFixed()), BitTableDefault<1>::NO_VALUE);
472
473 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
474 data.reserve(10_KB);
475 BitMemoryStreamOut out(&data);
476 builder.Encode(out);
477
478 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
479 BitTable<BitTableDefault<1>> table;
480 table.Decode(&in);
481
482 ASSERT_EQ(table.GetRowsCount(), 6);
483 ASSERT_EQ(table.GetRowSizeInBits(), 234);
484 }
485
486 } // namespace panda::test
487