1 /*
2  * Copyright (C) 2019 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "src/trace_processor/containers/row_map.h"
18 
19 #include <memory>
20 
21 #include "src/base/test/gtest_test_suite.h"
22 #include "test/gtest_and_gmock.h"
23 
24 namespace perfetto {
25 namespace trace_processor {
26 namespace {
27 
TEST(RowMapUnittest,SmokeRange)28 TEST(RowMapUnittest, SmokeRange) {
29   RowMap rm(30, 47);
30 
31   ASSERT_EQ(rm.size(), 17u);
32 
33   ASSERT_EQ(rm.Get(0), 30u);
34   ASSERT_EQ(rm.Get(1), 31u);
35   ASSERT_EQ(rm.Get(16), 46u);
36 
37   ASSERT_EQ(rm.IndexOf(29), base::nullopt);
38   ASSERT_EQ(rm.IndexOf(30), 0u);
39   ASSERT_EQ(rm.IndexOf(37), 7u);
40   ASSERT_EQ(rm.IndexOf(46), 16u);
41   ASSERT_EQ(rm.IndexOf(47), base::nullopt);
42 }
43 
TEST(RowMapUnittest,SmokeBitVector)44 TEST(RowMapUnittest, SmokeBitVector) {
45   RowMap rm(BitVector{true, false, false, false, true, true});
46 
47   ASSERT_EQ(rm.size(), 3u);
48 
49   ASSERT_EQ(rm.Get(0u), 0u);
50   ASSERT_EQ(rm.Get(1u), 4u);
51   ASSERT_EQ(rm.Get(2u), 5u);
52 
53   ASSERT_EQ(rm.IndexOf(0u), 0u);
54   ASSERT_EQ(rm.IndexOf(4u), 1u);
55   ASSERT_EQ(rm.IndexOf(5u), 2u);
56 
57   ASSERT_EQ(rm.IndexOf(1u), base::nullopt);
58   ASSERT_EQ(rm.IndexOf(100u), base::nullopt);
59 }
60 
TEST(RowMapUnittest,SmokeIndexVector)61 TEST(RowMapUnittest, SmokeIndexVector) {
62   RowMap rm(std::vector<uint32_t>{32u, 56u, 24u, 0u, 100u, 1u});
63 
64   ASSERT_EQ(rm.size(), 6u);
65 
66   ASSERT_EQ(rm.Get(0u), 32u);
67   ASSERT_EQ(rm.Get(1u), 56u);
68   ASSERT_EQ(rm.Get(2u), 24u);
69   ASSERT_EQ(rm.Get(3u), 0u);
70   ASSERT_EQ(rm.Get(4u), 100u);
71   ASSERT_EQ(rm.Get(5u), 1u);
72 
73   ASSERT_EQ(rm.IndexOf(32u), 0u);
74   ASSERT_EQ(rm.IndexOf(56u), 1u);
75   ASSERT_EQ(rm.IndexOf(24u), 2u);
76   ASSERT_EQ(rm.IndexOf(0u), 3u);
77   ASSERT_EQ(rm.IndexOf(100u), 4u);
78   ASSERT_EQ(rm.IndexOf(1u), 5u);
79 }
80 
TEST(RowMapUnittest,InsertToRangeAfter)81 TEST(RowMapUnittest, InsertToRangeAfter) {
82   RowMap rm(3u, 7u);
83   rm.Insert(10u);
84 
85   ASSERT_EQ(rm.size(), 5u);
86   ASSERT_EQ(rm.Get(4u), 10u);
87   ASSERT_EQ(rm.IndexOf(10u), 4u);
88 }
89 
TEST(RowMapUnittest,InsertToBitVectorBefore)90 TEST(RowMapUnittest, InsertToBitVectorBefore) {
91   RowMap rm(BitVector{true, false, true, true, false, true});
92   rm.Insert(1u);
93 
94   ASSERT_EQ(rm.size(), 5u);
95   ASSERT_EQ(rm.Get(0u), 0u);
96   ASSERT_EQ(rm.Get(1u), 1u);
97   ASSERT_EQ(rm.Get(2u), 2u);
98   ASSERT_EQ(rm.Get(3u), 3u);
99   ASSERT_EQ(rm.Get(4u), 5u);
100 }
101 
TEST(RowMapUnittest,InsertToBitVectorAfter)102 TEST(RowMapUnittest, InsertToBitVectorAfter) {
103   RowMap rm(BitVector{true, false, true, true, false, true});
104   rm.Insert(10u);
105 
106   ASSERT_EQ(rm.size(), 5u);
107   ASSERT_EQ(rm.Get(4u), 10u);
108   ASSERT_EQ(rm.IndexOf(10u), 4u);
109 }
110 
TEST(RowMapUnittest,InsertToIndexVectorAfter)111 TEST(RowMapUnittest, InsertToIndexVectorAfter) {
112   RowMap rm(std::vector<uint32_t>{0u, 2u, 3u, 5u});
113   rm.Insert(10u);
114 
115   ASSERT_EQ(rm.size(), 5u);
116   ASSERT_EQ(rm.Get(4u), 10u);
117   ASSERT_EQ(rm.IndexOf(10u), 4u);
118 }
119 
TEST(RowMapUnittest,ContainsRange)120 TEST(RowMapUnittest, ContainsRange) {
121   RowMap rm(93, 157);
122 
123   ASSERT_TRUE(rm.Contains(93));
124   ASSERT_TRUE(rm.Contains(105));
125   ASSERT_TRUE(rm.Contains(156));
126 
127   ASSERT_FALSE(rm.Contains(0));
128   ASSERT_FALSE(rm.Contains(92));
129   ASSERT_FALSE(rm.Contains(157));
130 }
131 
TEST(RowMapUnittest,ContainsBitVector)132 TEST(RowMapUnittest, ContainsBitVector) {
133   RowMap rm(BitVector{true, false, true, true, false, true});
134 
135   ASSERT_TRUE(rm.Contains(0));
136   ASSERT_TRUE(rm.Contains(2));
137   ASSERT_TRUE(rm.Contains(3));
138 
139   ASSERT_FALSE(rm.Contains(1));
140   ASSERT_FALSE(rm.Contains(4));
141   ASSERT_FALSE(rm.Contains(6));
142 }
143 
TEST(RowMapUnittest,ContainsIndexVector)144 TEST(RowMapUnittest, ContainsIndexVector) {
145   RowMap rm(std::vector<uint32_t>{0u, 2u, 3u, 5u});
146 
147   ASSERT_TRUE(rm.Contains(0));
148   ASSERT_TRUE(rm.Contains(2));
149   ASSERT_TRUE(rm.Contains(3));
150 
151   ASSERT_FALSE(rm.Contains(1));
152   ASSERT_FALSE(rm.Contains(4));
153   ASSERT_FALSE(rm.Contains(6));
154 }
155 
TEST(RowMapUnittest,SelectRangeWithRange)156 TEST(RowMapUnittest, SelectRangeWithRange) {
157   RowMap rm(93, 157);
158   RowMap picker(4, 7);
159   auto res = rm.SelectRows(picker);
160 
161   ASSERT_EQ(res.size(), 3u);
162   ASSERT_EQ(res.Get(0u), 97u);
163   ASSERT_EQ(res.Get(1u), 98u);
164   ASSERT_EQ(res.Get(2u), 99u);
165 }
166 
TEST(RowMapUnittest,SelectBitVectorWithRange)167 TEST(RowMapUnittest, SelectBitVectorWithRange) {
168   RowMap rm(BitVector{true, false, false, true, false, true, false});
169   RowMap picker(1u, 3u);
170   auto res = rm.SelectRows(picker);
171 
172   ASSERT_EQ(res.size(), 2u);
173   ASSERT_EQ(res.Get(0u), 3u);
174   ASSERT_EQ(res.Get(1u), 5u);
175 }
176 
TEST(RowMapUnittest,SelectIndexVectorWithRange)177 TEST(RowMapUnittest, SelectIndexVectorWithRange) {
178   RowMap rm(std::vector<uint32_t>{33, 2u, 45u, 7u, 8u, 9u});
179   RowMap picker(2, 5);
180   auto res = rm.SelectRows(picker);
181 
182   ASSERT_EQ(res.size(), 3u);
183   ASSERT_EQ(res.Get(0u), 45u);
184   ASSERT_EQ(res.Get(1u), 7u);
185   ASSERT_EQ(res.Get(2u), 8u);
186 }
187 
TEST(RowMapUnittest,SelectRangeWithBitVector)188 TEST(RowMapUnittest, SelectRangeWithBitVector) {
189   RowMap rm(27, 31);
190   RowMap picker(BitVector{true, false, false, true});
191   auto res = rm.SelectRows(picker);
192 
193   ASSERT_EQ(res.size(), 2u);
194   ASSERT_EQ(res.Get(0u), 27u);
195   ASSERT_EQ(res.Get(1u), 30u);
196 }
197 
TEST(RowMapUnittest,SelectRangeWithSmallBitVector)198 TEST(RowMapUnittest, SelectRangeWithSmallBitVector) {
199   RowMap rm(27, 31);
200   RowMap picker(BitVector{false, true});
201   auto res = rm.SelectRows(picker);
202 
203   ASSERT_EQ(res.size(), 1u);
204   ASSERT_EQ(res.Get(0u), 28u);
205 }
206 
TEST(RowMapUnittest,SelectBitVectorWithBitVector)207 TEST(RowMapUnittest, SelectBitVectorWithBitVector) {
208   RowMap rm(BitVector{true, false, true, true, false, true});
209   RowMap picker(BitVector{true, false, false, true});
210   auto res = rm.SelectRows(picker);
211 
212   ASSERT_EQ(res.size(), 2u);
213   ASSERT_EQ(res.Get(0u), 0u);
214   ASSERT_EQ(res.Get(1u), 5u);
215 }
216 
TEST(RowMapUnittest,SelectBitVectorWithSmallBitVector)217 TEST(RowMapUnittest, SelectBitVectorWithSmallBitVector) {
218   RowMap rm(BitVector{true, false, true, true, false, true});
219   RowMap picker(BitVector{false, true});
220   auto res = rm.SelectRows(picker);
221 
222   ASSERT_EQ(res.size(), 1u);
223   ASSERT_EQ(res.Get(0u), 2u);
224 }
225 
TEST(RowMapUnittest,SelectIndexVectorWithBitVector)226 TEST(RowMapUnittest, SelectIndexVectorWithBitVector) {
227   RowMap rm(std::vector<uint32_t>{0u, 2u, 3u, 5u});
228   RowMap picker(BitVector{true, false, false, true});
229   auto res = rm.SelectRows(picker);
230 
231   ASSERT_EQ(res.size(), 2u);
232   ASSERT_EQ(res.Get(0u), 0u);
233   ASSERT_EQ(res.Get(1u), 5u);
234 }
235 
TEST(RowMapUnittest,SelectRangeWithIndexVector)236 TEST(RowMapUnittest, SelectRangeWithIndexVector) {
237   RowMap rm(27, 31);
238   RowMap picker(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
239   auto res = rm.SelectRows(picker);
240 
241   ASSERT_EQ(res.size(), 6u);
242   ASSERT_EQ(res.Get(0u), 30u);
243   ASSERT_EQ(res.Get(1u), 29u);
244   ASSERT_EQ(res.Get(2u), 27u);
245   ASSERT_EQ(res.Get(3u), 28u);
246   ASSERT_EQ(res.Get(4u), 28u);
247   ASSERT_EQ(res.Get(5u), 30u);
248 }
249 
TEST(RowMapUnittest,SelectBitVectorWithIndexVector)250 TEST(RowMapUnittest, SelectBitVectorWithIndexVector) {
251   RowMap rm(BitVector{true, false, true, true, false, true});
252   RowMap picker(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
253   auto res = rm.SelectRows(picker);
254 
255   ASSERT_EQ(res.size(), 6u);
256   ASSERT_EQ(res.Get(0u), 5u);
257   ASSERT_EQ(res.Get(1u), 3u);
258   ASSERT_EQ(res.Get(2u), 0u);
259   ASSERT_EQ(res.Get(3u), 2u);
260   ASSERT_EQ(res.Get(4u), 2u);
261   ASSERT_EQ(res.Get(5u), 5u);
262 }
263 
TEST(RowMapUnittest,SelectIndexVectorWithIndexVector)264 TEST(RowMapUnittest, SelectIndexVectorWithIndexVector) {
265   RowMap rm(std::vector<uint32_t>{33u, 2u, 45u, 7u, 8u, 9u});
266   RowMap picker(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
267   auto res = rm.SelectRows(picker);
268 
269   ASSERT_EQ(res.size(), 6u);
270   ASSERT_EQ(res.Get(0u), 7u);
271   ASSERT_EQ(res.Get(1u), 45u);
272   ASSERT_EQ(res.Get(2u), 33u);
273   ASSERT_EQ(res.Get(3u), 2u);
274   ASSERT_EQ(res.Get(4u), 2u);
275   ASSERT_EQ(res.Get(5u), 7u);
276 }
277 
TEST(RowMapUnittest,IntersectNone)278 TEST(RowMapUnittest, IntersectNone) {
279   RowMap rm(BitVector{true, false, true, true, false, true});
280   rm.Intersect(RowMap());
281 
282   ASSERT_EQ(rm.size(), 0u);
283 }
284 
TEST(RowMapUnittest,IntersectSinglePresent)285 TEST(RowMapUnittest, IntersectSinglePresent) {
286   RowMap rm(BitVector{true, false, true, true, false, true});
287   rm.Intersect(RowMap::SingleRow(2u));
288 
289   ASSERT_EQ(rm.size(), 1u);
290   ASSERT_EQ(rm.Get(0u), 2u);
291 }
292 
TEST(RowMapUnittest,IntersectSingleAbsent)293 TEST(RowMapUnittest, IntersectSingleAbsent) {
294   RowMap rm(BitVector{true, false, true, true, false, true});
295   rm.Intersect(RowMap::SingleRow(1u));
296 
297   ASSERT_EQ(rm.size(), 0u);
298 }
299 
TEST(RowMapUnittest,IntersectMany)300 TEST(RowMapUnittest, IntersectMany) {
301   RowMap rm(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
302   rm.Intersect(RowMap(BitVector{false, false, true, true}));
303 
304   ASSERT_EQ(rm.size(), 3u);
305   ASSERT_EQ(rm.Get(0u), 3u);
306   ASSERT_EQ(rm.Get(1u), 2u);
307   ASSERT_EQ(rm.Get(2u), 3u);
308 }
309 
TEST(RowMapUnittest,FilterIntoEmptyOutput)310 TEST(RowMapUnittest, FilterIntoEmptyOutput) {
311   RowMap rm(0, 10000);
312   RowMap filter(4, 4);
313   rm.FilterInto(&filter, [](uint32_t) -> bool {
314     ADD_FAILURE() << "Should not have called lambda";
315     return true;
316   });
317 
318   ASSERT_EQ(filter.size(), 0u);
319 }
320 
TEST(RowMapUnittest,FilterIntoSingleRowTrue)321 TEST(RowMapUnittest, FilterIntoSingleRowTrue) {
322   RowMap rm(100, 10000);
323   RowMap filter(6, 7);
324   rm.FilterInto(&filter, [](uint32_t row) { return row == 106u; });
325 
326   ASSERT_EQ(filter.size(), 1u);
327   ASSERT_EQ(filter.Get(0u), 6u);
328 }
329 
TEST(RowMapUnittest,FilterIntoSingleRowFalse)330 TEST(RowMapUnittest, FilterIntoSingleRowFalse) {
331   RowMap rm(100, 10000);
332   RowMap filter(6, 7);
333   rm.FilterInto(&filter, [](uint32_t row) {
334     EXPECT_EQ(row, 106u);
335     return row != 106u;
336   });
337 
338   ASSERT_EQ(filter.size(), 0u);
339 }
340 
TEST(RowMapUnittest,FilterIntoRangeWithRange)341 TEST(RowMapUnittest, FilterIntoRangeWithRange) {
342   RowMap rm(93, 157);
343   RowMap filter(4, 7);
344   rm.FilterInto(&filter, [](uint32_t row) { return row == 97u || row == 98u; });
345 
346   ASSERT_EQ(filter.size(), 2u);
347   ASSERT_EQ(filter.Get(0u), 4u);
348   ASSERT_EQ(filter.Get(1u), 5u);
349 }
350 
TEST(RowMapUnittest,FilterIntoOffsetRangeWithRange)351 TEST(RowMapUnittest, FilterIntoOffsetRangeWithRange) {
352   RowMap rm(100000, 100010);
353   RowMap filter(4, 7);
354   rm.FilterInto(&filter, [](uint32_t row) { return row == 100004u; });
355 
356   ASSERT_EQ(filter.size(), 1u);
357   ASSERT_EQ(filter.Get(0u), 4u);
358 }
359 
TEST(RowMapUnittest,FilterIntoLargeRangeWithRange)360 TEST(RowMapUnittest, FilterIntoLargeRangeWithRange) {
361   RowMap rm(0, 100000);
362   RowMap filter(0, 100000);
363   rm.FilterInto(&filter, [](uint32_t row) { return row % 2 == 0; });
364 
365   ASSERT_EQ(filter.size(), 100000u / 2);
366   for (uint32_t i = 0; i < 100000 / 2; ++i) {
367     ASSERT_EQ(filter.Get(i), i * 2);
368   }
369 }
370 
TEST(RowMapUnittest,FilterIntoBitVectorWithRange)371 TEST(RowMapUnittest, FilterIntoBitVectorWithRange) {
372   RowMap rm(
373       BitVector{true, false, false, true, false, true, false, true, true});
374   RowMap filter(1u, 5u);
375   rm.FilterInto(&filter, [](uint32_t row) { return row == 3u || row == 7u; });
376 
377   ASSERT_EQ(filter.size(), 2u);
378   ASSERT_EQ(filter.Get(0u), 1u);
379   ASSERT_EQ(filter.Get(1u), 3u);
380 }
381 
TEST(RowMapUnittest,FilterIntoIndexVectorWithRange)382 TEST(RowMapUnittest, FilterIntoIndexVectorWithRange) {
383   RowMap rm(std::vector<uint32_t>{33, 2u, 45u, 7u, 8u, 9u});
384   RowMap filter(2, 5);
385   rm.FilterInto(&filter, [](uint32_t row) { return row == 45u || row == 8u; });
386 
387   ASSERT_EQ(filter.size(), 2u);
388   ASSERT_EQ(filter.Get(0u), 2u);
389   ASSERT_EQ(filter.Get(1u), 4u);
390 }
391 
TEST(RowMapUnittest,FilterIntoRangeWithBitVector)392 TEST(RowMapUnittest, FilterIntoRangeWithBitVector) {
393   RowMap rm(27, 31);
394   RowMap filter(BitVector{true, false, true, true});
395   rm.FilterInto(&filter, [](uint32_t row) { return row == 29u || row == 30u; });
396 
397   ASSERT_EQ(filter.size(), 2u);
398   ASSERT_EQ(filter.Get(0u), 2u);
399   ASSERT_EQ(filter.Get(1u), 3u);
400 }
401 
TEST(RowMapUnittest,FilterIntoBitVectorWithBitVector)402 TEST(RowMapUnittest, FilterIntoBitVectorWithBitVector) {
403   RowMap rm(BitVector{true, false, true, true, false, true});
404   RowMap filter(BitVector{true, true, false, true});
405   rm.FilterInto(&filter, [](uint32_t row) { return row == 2u || row == 5u; });
406 
407   ASSERT_EQ(filter.size(), 2u);
408   ASSERT_EQ(filter.Get(0u), 1u);
409   ASSERT_EQ(filter.Get(1u), 3u);
410 }
411 
TEST(RowMapUnittest,FilterIntoIndexVectorWithBitVector)412 TEST(RowMapUnittest, FilterIntoIndexVectorWithBitVector) {
413   RowMap rm(std::vector<uint32_t>{0u, 2u, 3u, 5u});
414   RowMap filter(BitVector{true, true, false, true});
415   rm.FilterInto(&filter, [](uint32_t row) { return row == 2u || row == 5u; });
416 
417   ASSERT_EQ(filter.size(), 2u);
418   ASSERT_EQ(filter.Get(0u), 1u);
419   ASSERT_EQ(filter.Get(1u), 3u);
420 }
421 
TEST(RowMapUnittest,FilterIntoRangeWithIndexVector)422 TEST(RowMapUnittest, FilterIntoRangeWithIndexVector) {
423   RowMap rm(27, 41);
424   RowMap filter(std::vector<uint32_t>{3u, 5u, 9u, 10u, 12u});
425   rm.FilterInto(&filter, [](uint32_t row) { return row == 32u || row == 39u; });
426 
427   ASSERT_EQ(filter.size(), 2u);
428   ASSERT_EQ(filter.Get(0u), 5u);
429   ASSERT_EQ(filter.Get(1u), 12u);
430 }
431 
TEST(RowMapUnittest,FilterIntoBitVectorWithIndexVector)432 TEST(RowMapUnittest, FilterIntoBitVectorWithIndexVector) {
433   RowMap rm(BitVector{false, true, false, true, true, false, true});
434   RowMap filter(std::vector<uint32_t>{1u, 2u, 3u});
435   rm.FilterInto(&filter, [](uint32_t row) { return row == 3u || row == 4u; });
436 
437   ASSERT_EQ(filter.size(), 2u);
438   ASSERT_EQ(filter.Get(0u), 1u);
439   ASSERT_EQ(filter.Get(1u), 2u);
440 }
441 
TEST(RowMapUnittest,FilterIntoIndexVectorWithIndexVector)442 TEST(RowMapUnittest, FilterIntoIndexVectorWithIndexVector) {
443   RowMap rm(std::vector<uint32_t>{33u, 2u, 45u, 7u, 8u, 9u});
444   RowMap filter(std::vector<uint32_t>{1u, 2u, 3u});
445   rm.FilterInto(&filter, [](uint32_t row) { return row == 2u || row == 7u; });
446 
447   ASSERT_EQ(filter.size(), 2u);
448   ASSERT_EQ(filter.Get(0u), 1u);
449   ASSERT_EQ(filter.Get(1u), 3u);
450 }
451 
452 }  // namespace
453 }  // namespace trace_processor
454 }  // namespace perfetto
455