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,SelectRangeWithSingleBitVector)198 TEST(RowMapUnittest, SelectRangeWithSingleBitVector) {
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,SelectRangeWithSmallBitVector)207 TEST(RowMapUnittest, SelectRangeWithSmallBitVector) {
208   RowMap rm(27, 31);
209   RowMap picker(BitVector{false, true, true});
210   auto res = rm.SelectRows(picker);
211 
212   ASSERT_EQ(res.size(), 2u);
213   ASSERT_EQ(res.Get(0u), 28u);
214   ASSERT_EQ(res.Get(1u), 29u);
215 }
216 
TEST(RowMapUnittest,SelectBitVectorWithBitVector)217 TEST(RowMapUnittest, SelectBitVectorWithBitVector) {
218   RowMap rm(BitVector{true, false, true, true, false, true});
219   RowMap picker(BitVector{true, false, false, true});
220   auto res = rm.SelectRows(picker);
221 
222   ASSERT_EQ(res.size(), 2u);
223   ASSERT_EQ(res.Get(0u), 0u);
224   ASSERT_EQ(res.Get(1u), 5u);
225 }
226 
TEST(RowMapUnittest,SelectBitVectorWithSingleBitVector)227 TEST(RowMapUnittest, SelectBitVectorWithSingleBitVector) {
228   RowMap rm(BitVector{true, false, true, true, false, true});
229   RowMap picker(BitVector{false, true});
230   auto res = rm.SelectRows(picker);
231 
232   ASSERT_EQ(res.size(), 1u);
233   ASSERT_EQ(res.Get(0u), 2u);
234 }
235 
TEST(RowMapUnittest,SelectBitVectorWithSmallBitVector)236 TEST(RowMapUnittest, SelectBitVectorWithSmallBitVector) {
237   RowMap rm(BitVector{true, false, true, true, false, true});
238   RowMap picker(BitVector{false, true, true});
239   auto res = rm.SelectRows(picker);
240 
241   ASSERT_EQ(res.size(), 2u);
242   ASSERT_EQ(res.Get(0u), 2u);
243   ASSERT_EQ(res.Get(1u), 3u);
244 }
245 
TEST(RowMapUnittest,SelectIndexVectorWithBitVector)246 TEST(RowMapUnittest, SelectIndexVectorWithBitVector) {
247   RowMap rm(std::vector<uint32_t>{0u, 2u, 3u, 5u});
248   RowMap picker(BitVector{true, false, false, true});
249   auto res = rm.SelectRows(picker);
250 
251   ASSERT_EQ(res.size(), 2u);
252   ASSERT_EQ(res.Get(0u), 0u);
253   ASSERT_EQ(res.Get(1u), 5u);
254 }
255 
TEST(RowMapUnittest,SelectIndexVectorWithSmallBitVector)256 TEST(RowMapUnittest, SelectIndexVectorWithSmallBitVector) {
257   RowMap rm(std::vector<uint32_t>{0u, 2u, 3u, 5u});
258   RowMap picker(BitVector{false, true, true});
259   auto res = rm.SelectRows(picker);
260 
261   ASSERT_EQ(res.size(), 2u);
262   ASSERT_EQ(res.Get(0u), 2u);
263   ASSERT_EQ(res.Get(1u), 3u);
264 }
265 
TEST(RowMapUnittest,SelectRangeWithIndexVector)266 TEST(RowMapUnittest, SelectRangeWithIndexVector) {
267   RowMap rm(27, 31);
268   RowMap picker(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
269   auto res = rm.SelectRows(picker);
270 
271   ASSERT_EQ(res.size(), 6u);
272   ASSERT_EQ(res.Get(0u), 30u);
273   ASSERT_EQ(res.Get(1u), 29u);
274   ASSERT_EQ(res.Get(2u), 27u);
275   ASSERT_EQ(res.Get(3u), 28u);
276   ASSERT_EQ(res.Get(4u), 28u);
277   ASSERT_EQ(res.Get(5u), 30u);
278 }
279 
TEST(RowMapUnittest,SelectBitVectorWithIndexVector)280 TEST(RowMapUnittest, SelectBitVectorWithIndexVector) {
281   RowMap rm(BitVector{true, false, true, true, false, true});
282   RowMap picker(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
283   auto res = rm.SelectRows(picker);
284 
285   ASSERT_EQ(res.size(), 6u);
286   ASSERT_EQ(res.Get(0u), 5u);
287   ASSERT_EQ(res.Get(1u), 3u);
288   ASSERT_EQ(res.Get(2u), 0u);
289   ASSERT_EQ(res.Get(3u), 2u);
290   ASSERT_EQ(res.Get(4u), 2u);
291   ASSERT_EQ(res.Get(5u), 5u);
292 }
293 
TEST(RowMapUnittest,SelectIndexVectorWithIndexVector)294 TEST(RowMapUnittest, SelectIndexVectorWithIndexVector) {
295   RowMap rm(std::vector<uint32_t>{33u, 2u, 45u, 7u, 8u, 9u});
296   RowMap picker(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
297   auto res = rm.SelectRows(picker);
298 
299   ASSERT_EQ(res.size(), 6u);
300   ASSERT_EQ(res.Get(0u), 7u);
301   ASSERT_EQ(res.Get(1u), 45u);
302   ASSERT_EQ(res.Get(2u), 33u);
303   ASSERT_EQ(res.Get(3u), 2u);
304   ASSERT_EQ(res.Get(4u), 2u);
305   ASSERT_EQ(res.Get(5u), 7u);
306 }
307 
TEST(RowMapUnittest,IntersectNone)308 TEST(RowMapUnittest, IntersectNone) {
309   RowMap rm(BitVector{true, false, true, true, false, true});
310   rm.Intersect(RowMap());
311 
312   ASSERT_EQ(rm.size(), 0u);
313 }
314 
TEST(RowMapUnittest,IntersectSinglePresent)315 TEST(RowMapUnittest, IntersectSinglePresent) {
316   RowMap rm(BitVector{true, false, true, true, false, true});
317   rm.Intersect(RowMap::SingleRow(2u));
318 
319   ASSERT_EQ(rm.size(), 1u);
320   ASSERT_EQ(rm.Get(0u), 2u);
321 }
322 
TEST(RowMapUnittest,IntersectSingleAbsent)323 TEST(RowMapUnittest, IntersectSingleAbsent) {
324   RowMap rm(BitVector{true, false, true, true, false, true});
325   rm.Intersect(RowMap::SingleRow(1u));
326 
327   ASSERT_EQ(rm.size(), 0u);
328 }
329 
TEST(RowMapUnittest,IntersectMany)330 TEST(RowMapUnittest, IntersectMany) {
331   RowMap rm(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
332   rm.Intersect(RowMap(BitVector{false, false, true, true}));
333 
334   ASSERT_EQ(rm.size(), 3u);
335   ASSERT_EQ(rm.Get(0u), 3u);
336   ASSERT_EQ(rm.Get(1u), 2u);
337   ASSERT_EQ(rm.Get(2u), 3u);
338 }
339 
TEST(RowMapUnittest,FilterIntoEmptyOutput)340 TEST(RowMapUnittest, FilterIntoEmptyOutput) {
341   RowMap rm(0, 10000);
342   RowMap filter(4, 4);
343   rm.FilterInto(&filter, [](uint32_t) -> bool {
344     ADD_FAILURE() << "Should not have called lambda";
345     return true;
346   });
347 
348   ASSERT_EQ(filter.size(), 0u);
349 }
350 
TEST(RowMapUnittest,FilterIntoSingleRowTrue)351 TEST(RowMapUnittest, FilterIntoSingleRowTrue) {
352   RowMap rm(100, 10000);
353   RowMap filter(6, 7);
354   rm.FilterInto(&filter, [](uint32_t row) { return row == 106u; });
355 
356   ASSERT_EQ(filter.size(), 1u);
357   ASSERT_EQ(filter.Get(0u), 6u);
358 }
359 
TEST(RowMapUnittest,FilterIntoSingleRowFalse)360 TEST(RowMapUnittest, FilterIntoSingleRowFalse) {
361   RowMap rm(100, 10000);
362   RowMap filter(6, 7);
363   rm.FilterInto(&filter, [](uint32_t row) {
364     EXPECT_EQ(row, 106u);
365     return row != 106u;
366   });
367 
368   ASSERT_EQ(filter.size(), 0u);
369 }
370 
TEST(RowMapUnittest,FilterIntoRangeWithRange)371 TEST(RowMapUnittest, FilterIntoRangeWithRange) {
372   RowMap rm(93, 157);
373   RowMap filter(4, 7);
374   rm.FilterInto(&filter, [](uint32_t row) { return row == 97u || row == 98u; });
375 
376   ASSERT_EQ(filter.size(), 2u);
377   ASSERT_EQ(filter.Get(0u), 4u);
378   ASSERT_EQ(filter.Get(1u), 5u);
379 }
380 
TEST(RowMapUnittest,FilterIntoOffsetRangeWithRange)381 TEST(RowMapUnittest, FilterIntoOffsetRangeWithRange) {
382   RowMap rm(100000, 100010);
383   RowMap filter(4, 7);
384   rm.FilterInto(&filter, [](uint32_t row) { return row == 100004u; });
385 
386   ASSERT_EQ(filter.size(), 1u);
387   ASSERT_EQ(filter.Get(0u), 4u);
388 }
389 
TEST(RowMapUnittest,FilterIntoLargeRangeWithRange)390 TEST(RowMapUnittest, FilterIntoLargeRangeWithRange) {
391   RowMap rm(0, 100000);
392   RowMap filter(0, 100000);
393   rm.FilterInto(&filter, [](uint32_t row) { return row % 2 == 0; });
394 
395   ASSERT_EQ(filter.size(), 100000u / 2);
396   for (uint32_t i = 0; i < 100000 / 2; ++i) {
397     ASSERT_EQ(filter.Get(i), i * 2);
398   }
399 }
400 
TEST(RowMapUnittest,FilterIntoBitVectorWithRange)401 TEST(RowMapUnittest, FilterIntoBitVectorWithRange) {
402   RowMap rm(
403       BitVector{true, false, false, true, false, true, false, true, true});
404   RowMap filter(1u, 5u);
405   rm.FilterInto(&filter, [](uint32_t row) { return row == 3u || row == 7u; });
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,FilterIntoIndexVectorWithRange)412 TEST(RowMapUnittest, FilterIntoIndexVectorWithRange) {
413   RowMap rm(std::vector<uint32_t>{33, 2u, 45u, 7u, 8u, 9u});
414   RowMap filter(2, 5);
415   rm.FilterInto(&filter, [](uint32_t row) { return row == 45u || row == 8u; });
416 
417   ASSERT_EQ(filter.size(), 2u);
418   ASSERT_EQ(filter.Get(0u), 2u);
419   ASSERT_EQ(filter.Get(1u), 4u);
420 }
421 
TEST(RowMapUnittest,FilterIntoRangeWithBitVector)422 TEST(RowMapUnittest, FilterIntoRangeWithBitVector) {
423   RowMap rm(27, 31);
424   RowMap filter(BitVector{true, false, true, true});
425   rm.FilterInto(&filter, [](uint32_t row) { return row == 29u || row == 30u; });
426 
427   ASSERT_EQ(filter.size(), 2u);
428   ASSERT_EQ(filter.Get(0u), 2u);
429   ASSERT_EQ(filter.Get(1u), 3u);
430 }
431 
TEST(RowMapUnittest,FilterIntoBitVectorWithBitVector)432 TEST(RowMapUnittest, FilterIntoBitVectorWithBitVector) {
433   RowMap rm(BitVector{true, false, true, true, false, true});
434   RowMap filter(BitVector{true, true, false, true});
435   rm.FilterInto(&filter, [](uint32_t row) { return row == 2u || row == 5u; });
436 
437   ASSERT_EQ(filter.size(), 2u);
438   ASSERT_EQ(filter.Get(0u), 1u);
439   ASSERT_EQ(filter.Get(1u), 3u);
440 }
441 
TEST(RowMapUnittest,FilterIntoIndexVectorWithBitVector)442 TEST(RowMapUnittest, FilterIntoIndexVectorWithBitVector) {
443   RowMap rm(std::vector<uint32_t>{0u, 2u, 3u, 5u});
444   RowMap filter(BitVector{true, true, false, true});
445   rm.FilterInto(&filter, [](uint32_t row) { return row == 2u || row == 5u; });
446 
447   ASSERT_EQ(filter.size(), 2u);
448   ASSERT_EQ(filter.Get(0u), 1u);
449   ASSERT_EQ(filter.Get(1u), 3u);
450 }
451 
TEST(RowMapUnittest,FilterIntoRangeWithIndexVector)452 TEST(RowMapUnittest, FilterIntoRangeWithIndexVector) {
453   RowMap rm(27, 41);
454   RowMap filter(std::vector<uint32_t>{3u, 5u, 9u, 10u, 12u});
455   rm.FilterInto(&filter, [](uint32_t row) { return row == 32u || row == 39u; });
456 
457   ASSERT_EQ(filter.size(), 2u);
458   ASSERT_EQ(filter.Get(0u), 5u);
459   ASSERT_EQ(filter.Get(1u), 12u);
460 }
461 
TEST(RowMapUnittest,FilterIntoBitVectorWithIndexVector)462 TEST(RowMapUnittest, FilterIntoBitVectorWithIndexVector) {
463   RowMap rm(BitVector{false, true, false, true, true, false, true});
464   RowMap filter(std::vector<uint32_t>{1u, 2u, 3u});
465   rm.FilterInto(&filter, [](uint32_t row) { return row == 3u || row == 4u; });
466 
467   ASSERT_EQ(filter.size(), 2u);
468   ASSERT_EQ(filter.Get(0u), 1u);
469   ASSERT_EQ(filter.Get(1u), 2u);
470 }
471 
TEST(RowMapUnittest,FilterIntoIndexVectorWithIndexVector)472 TEST(RowMapUnittest, FilterIntoIndexVectorWithIndexVector) {
473   RowMap rm(std::vector<uint32_t>{33u, 2u, 45u, 7u, 8u, 9u});
474   RowMap filter(std::vector<uint32_t>{1u, 2u, 3u});
475   rm.FilterInto(&filter, [](uint32_t row) { return row == 2u || row == 7u; });
476 
477   ASSERT_EQ(filter.size(), 2u);
478   ASSERT_EQ(filter.Get(0u), 1u);
479   ASSERT_EQ(filter.Get(1u), 3u);
480 }
481 
482 }  // namespace
483 }  // namespace trace_processor
484 }  // namespace perfetto
485