1 /*
2 * Copyright (C) 2022 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 #ifndef SRC_TRACE_PROCESSOR_CONTAINERS_ROW_MAP_ALGORITHMS_H_
18 #define SRC_TRACE_PROCESSOR_CONTAINERS_ROW_MAP_ALGORITHMS_H_
19
20 #include <vector>
21
22 #include "perfetto/base/logging.h"
23 #include "src/trace_processor/containers/bit_vector.h"
24 #include "src/trace_processor/containers/bit_vector_iterators.h"
25
26 // This file contains fundamental algorithms used by RowMap.
27 //
28 // This file is structured in a way to make benchmarking easy. The intention is
29 // to use this to decide which heurustics to use and the value of magic
30 // constants in RowMap algorithms.
31
32 namespace perfetto {
33 namespace trace_processor {
34 namespace row_map_algorithms {
35
36 // Returns a vector containing elements from |iv| selected by indices from
37 // |selector|.
SelectIvWithIv(const std::vector<uint32_t> & iv,const std::vector<uint32_t> & selector)38 inline std::vector<uint32_t> SelectIvWithIv(
39 const std::vector<uint32_t>& iv,
40 const std::vector<uint32_t>& selector) {
41 std::vector<uint32_t> ret(selector.size());
42 for (uint32_t i = 0; i < selector.size(); ++i) {
43 PERFETTO_DCHECK(selector[i] < iv.size());
44 ret[i] = iv[selector[i]];
45 }
46 return ret;
47 }
48
49 // Returns a vector containing elements from |bv| by first converting to an
50 // index vector and then selecting indices from |selector|.
SelectBvWithIvByConvertToIv(const BitVector & bv,const std::vector<uint32_t> & selector)51 inline std::vector<uint32_t> SelectBvWithIvByConvertToIv(
52 const BitVector& bv,
53 const std::vector<uint32_t>& selector) {
54 std::vector<uint32_t> bv_conv(bv.CountSetBits());
55 for (auto it = bv.IterateSetBits(); it; it.Next()) {
56 bv_conv[it.ordinal()] = it.index();
57 }
58 return SelectIvWithIv(bv_conv, selector);
59 }
60
61 // Returns a vector containing elements from |bv| by selecting indices from
62 // |selector| using IndexOfNthSet calls.
SelectBvWithIvByIndexOfNthSet(const BitVector & bv,const std::vector<uint32_t> & selector)63 inline std::vector<uint32_t> SelectBvWithIvByIndexOfNthSet(
64 const BitVector& bv,
65 const std::vector<uint32_t>& selector) {
66 std::vector<uint32_t> iv(selector.size());
67 for (uint32_t i = 0; i < selector.size(); ++i) {
68 iv[i] = bv.IndexOfNthSet(selector[i]);
69 }
70 return iv;
71 }
72
73 } // namespace row_map_algorithms
74 } // namespace trace_processor
75 } // namespace perfetto
76
77 #endif // SRC_TRACE_PROCESSOR_CONTAINERS_ROW_MAP_ALGORITHMS_H_
78