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_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() const39 ArenaAllocator *GetAllocator() const
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<2U, TestAccessor> {
163 public:
164 using Base = BitTableRow<2U, TestAccessor>;
165 using Base::Base;
166
167 static_assert(Base::NUM_COLUMNS == 2U);
168
GetField0() const169 uint32_t GetField0() const
170 {
171 return Base::Get(0);
172 }
GetField1() const173 uint32_t GetField1() const
174 {
175 return Base::Get(1);
176 }
GetName(size_t index) const177 const char *GetName(size_t index) const
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
TEST_F(BitTableTest,Ranges)229 TEST_F(BitTableTest, Ranges)
230 {
231 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
232 data.reserve(1_KB);
233
234 std::array<std::array<uint32_t, 2>, 10> values = {
235 {{0U, 10U}, {1U, 11U}, {2U, 12U}, {3U, 13U}, {4U, 14U}, {5U, 15U}, {6U, 16U}, {7U, 17U}, {8U, 18U}, {9U, 19U}}};
236
237 BitTableBuilder<TestAccessor> builder(GetAllocator());
238 for (auto &v : values) {
239 builder.Emplace(CreateEntry<decltype(builder)>(v));
240 }
241
242 BitMemoryStreamOut out(&data);
243 builder.Encode(out);
244
245 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
246 BitTable<TestAccessor> table;
247 table.Decode(&in);
248
249 ASSERT_EQ(table.GetRowsCount(), 10);
250 ASSERT_EQ(table.GetColumnsCount(), 2);
251
252 {
253 auto range = table.GetRange(0, 6);
254 auto it = range.begin();
255 ASSERT_EQ(range[0].GetField0(), values[0][0]);
256 ASSERT_EQ(range[0].GetField1(), values[0][1]);
257 ASSERT_EQ(range[1].GetField0(), values[1][0]);
258 ASSERT_EQ(range[1].GetField1(), values[1][1]);
259 ASSERT_EQ(range[2].GetField0(), values[2][0]);
260 ASSERT_EQ(range[2].GetField1(), values[2][1]);
261 ASSERT_EQ(range[3].GetField0(), values[3][0]);
262 ASSERT_EQ(range[3].GetField1(), values[3][1]);
263 ASSERT_EQ(range[4].GetField0(), values[4][0]);
264 ASSERT_EQ(range[4].GetField1(), values[4][1]);
265 ASSERT_EQ(range[5].GetField0(), values[5][0]);
266 ASSERT_EQ(range[5].GetField1(), values[5][1]);
267
268 size_t i = 0;
269 for (auto &v : table.GetRange(0, 6)) {
270 ASSERT_EQ(v.GetField0(), values[i][0]);
271 ASSERT_EQ(v.GetField1(), values[i][1]);
272 i++;
273 }
274 ASSERT_EQ(i, 6);
275
276 i = 0;
277 for (auto &v : table) {
278 ASSERT_EQ(v.GetField0(), values[i][0]);
279 ASSERT_EQ(v.GetField1(), values[i][1]);
280 i++;
281 }
282 ASSERT_EQ(i, 10);
283 }
284
285 {
286 auto range = table.GetRangeReversed(4, 10);
287 auto it = range.begin();
288 ASSERT_EQ(range[0].GetField0(), values[9][0]);
289 ASSERT_EQ(range[0].GetField1(), values[9][1]);
290 ASSERT_EQ(range[1].GetField0(), values[8][0]);
291 ASSERT_EQ(range[1].GetField1(), values[8][1]);
292 ASSERT_EQ(range[2].GetField0(), values[7][0]);
293 ASSERT_EQ(range[2].GetField1(), values[7][1]);
294 ASSERT_EQ(range[3].GetField0(), values[6][0]);
295 ASSERT_EQ(range[3].GetField1(), values[6][1]);
296 ASSERT_EQ(range[4].GetField0(), values[5][0]);
297 ASSERT_EQ(range[4].GetField1(), values[5][1]);
298
299 int i = 10;
300 for (auto &v : table.GetRangeReversed(4, 10)) {
301 ASSERT_EQ(v.GetField0(), values[i - 1][0]);
302 ASSERT_EQ(v.GetField1(), values[i - 1][1]);
303 i--;
304 }
305 ASSERT_EQ(i, 4);
306
307 i = 10;
308 for (auto &v : table.GetRangeReversed()) {
309 ASSERT_EQ(v.GetField0(), values[i - 1][0]);
310 ASSERT_EQ(v.GetField1(), values[i - 1][1]);
311 i--;
312 }
313 ASSERT_EQ(i, 0);
314 }
315
316 {
317 auto range = table.GetRange(0, 0);
318 ASSERT_EQ(range.begin(), range.end());
319
320 size_t i = 0;
321 for (auto &v : range) {
322 i++;
323 }
324 ASSERT_EQ(i, 0);
325 }
326
327 {
328 auto range = table.GetRangeReversed(0, 0);
329 ASSERT_EQ(range.begin(), range.end());
330
331 size_t i = 0;
332 for (auto &v : range) {
333 i++;
334 }
335 ASSERT_EQ(i, 0);
336 }
337 }
338
TEST_F(BitTableTest,Deduplication)339 TEST_F(BitTableTest, Deduplication)
340 {
341 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
342 data.reserve(1_KB);
343
344 using Builder = BitTableBuilder<TestAccessor>;
345 using Entry = Builder::Entry;
346
347 Builder builder(GetAllocator());
348
349 std::array<Entry, 3> values = {Entry {1}, Entry {2}, Entry {3}};
350
351 ASSERT_EQ(0U, builder.Add(values[0]));
352 ASSERT_EQ(1U, builder.Add(values[1]));
353 ASSERT_EQ(0U, builder.Add(values[0]));
354 ASSERT_EQ(2U, builder.Add(values[2]));
355 ASSERT_EQ(1U, builder.Add(values[1]));
356 ASSERT_EQ(2U, builder.Add(values[2]));
357
358 ASSERT_EQ(3U, builder.AddArray(Span<Entry>(values.begin(), 2)));
359 ASSERT_EQ(1U, builder.AddArray(Span<Entry>(values.begin() + 1, 1)));
360 ASSERT_EQ(5U, builder.AddArray(Span<Entry>(values.begin() + 1, 2)));
361 ASSERT_EQ(3U, builder.AddArray(Span<Entry>(values.begin(), 2)));
362 ASSERT_EQ(5U, builder.AddArray(Span<Entry>(values.begin() + 1, 2)));
363 }
364
TEST_F(BitTableTest,Bitmap)365 TEST_F(BitTableTest, Bitmap)
366 {
367 uint64_t pattern = 0xBADDCAFEDEADF00DULL;
368
369 BitmapTableBuilder builder(GetAllocator());
370
371 ArenaVector<std::pair<uint32_t, uint64_t>> values(GetAllocator()->Adapter());
372 for (size_t i = 0; i <= 64; i++) {
373 uint64_t mask = (i == 64) ? std::numeric_limits<uint64_t>::max() : ((1ULL << i) - 1);
374 uint64_t value = pattern & mask;
375 BitVector<ArenaAllocator> vec(MinimumBitsToStore(value), GetAllocator());
376 vec.Reset();
377 for (size_t j = 0; j < i; j++) {
378 if ((value & (1ULL << j)) != 0) {
379 vec.SetBit(j);
380 }
381 }
382 auto fixed_vec = vec.GetFixed();
383 values.push_back({builder.Add(fixed_vec), value});
384 }
385
386 // Zero value also occupies row in the table
387 ASSERT_EQ(Popcount(pattern), builder.GetRowsCount());
388
389 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
390 data.reserve(10_KB);
391 BitMemoryStreamOut out(&data);
392 builder.Encode(out);
393
394 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
395 BitTable<BitTableDefault<1>> table;
396 table.Decode(&in);
397
398 ASSERT_EQ(table.GetRowSizeInBits(), MinimumBitsToStore(pattern));
399
400 for (auto &[index, value] : values) {
401 if (index != BitTableDefault<1>::NO_VALUE) {
402 ASSERT_EQ(table.GetBitMemoryRegion(index).Read<uint64_t>(0, table.GetRowSizeInBits()), value);
403 }
404 }
405 }
406
407 template <typename T>
FillVector(T & vector,uint32_t value)408 void FillVector(T &vector, uint32_t value)
409 {
410 auto sp = vector.GetDataSpan();
411 std::fill(sp.begin(), sp.end(), value);
412 }
413
TEST_F(BitTableTest,BitmapDeduplication)414 TEST_F(BitTableTest, BitmapDeduplication)
415 {
416 BitmapTableBuilder builder(GetAllocator());
417 std::array<uint32_t, 128> buff;
418 std::array fixed_vectors = {ArenaBitVectorSpan(&buff[0], 23), ArenaBitVectorSpan(&buff[1], 48),
419 ArenaBitVectorSpan(&buff[3], 0), ArenaBitVectorSpan(&buff[4], 123),
420 ArenaBitVectorSpan(&buff[8], 48)};
421 std::array vectors = {ArenaBitVector(GetAllocator()), ArenaBitVector(GetAllocator()),
422 ArenaBitVector(GetAllocator()), ArenaBitVector(GetAllocator()),
423 ArenaBitVector(GetAllocator())};
424 FillVector(fixed_vectors[0], 0x23232323);
425 FillVector(fixed_vectors[1], 0x48484848);
426 FillVector(fixed_vectors[2], 0);
427 FillVector(fixed_vectors[3], 0x23123123);
428 FillVector(fixed_vectors[4], 0x48484848);
429 ASSERT_EQ(fixed_vectors[1], fixed_vectors[4]);
430 vectors[0].resize(1);
431 vectors[1].resize(23);
432 vectors[2].resize(123);
433 vectors[3].resize(234);
434 vectors[4].resize(0);
435 FillVector(vectors[0], 0x1);
436 FillVector(vectors[1], 0x11111111);
437 FillVector(vectors[2], 0x23123123);
438 FillVector(vectors[3], 0x34234234);
439 ASSERT_EQ(builder.Add(fixed_vectors[0].GetFixed()), 0);
440 ASSERT_EQ(builder.Add(fixed_vectors[1].GetFixed()), 1);
441 ASSERT_EQ(builder.Add(fixed_vectors[2].GetFixed()), BitTableDefault<1>::NO_VALUE);
442 ASSERT_EQ(builder.Add(fixed_vectors[3].GetFixed()), 2);
443 ASSERT_EQ(builder.Add(fixed_vectors[4].GetFixed()), 1);
444 ASSERT_EQ(builder.Add(vectors[0].GetFixed()), 3);
445 ASSERT_EQ(builder.Add(vectors[1].GetFixed()), 4);
446 ASSERT_EQ(builder.Add(vectors[2].GetFixed()), 2);
447 ASSERT_EQ(builder.Add(vectors[3].GetFixed()), 5);
448 ASSERT_EQ(builder.Add(vectors[4].GetFixed()), BitTableDefault<1>::NO_VALUE);
449
450 ArenaVector<uint8_t> data(GetAllocator()->Adapter());
451 data.reserve(10_KB);
452 BitMemoryStreamOut out(&data);
453 builder.Encode(out);
454
455 BitMemoryStreamIn in(data.data(), 0, data.size() * BITS_PER_BYTE);
456 BitTable<BitTableDefault<1>> table;
457 table.Decode(&in);
458
459 ASSERT_EQ(table.GetRowsCount(), 6);
460 ASSERT_EQ(table.GetRowSizeInBits(), 234);
461 }
462
463 } // namespace panda::test
464