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