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 <cstdint>
21 #include <vector>
22
23 #include "perfetto/base/logging.h"
24 #include "src/trace_processor/containers/bit_vector.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 return SelectIvWithIv(bv.GetSetBitIndices(), selector);
55 }
56
57 // Returns a vector containing elements from |bv| by selecting indices from
58 // |selector| using IndexOfNthSet calls.
SelectBvWithIvByIndexOfNthSet(const BitVector & bv,const std::vector<uint32_t> & selector)59 inline std::vector<uint32_t> SelectBvWithIvByIndexOfNthSet(
60 const BitVector& bv,
61 const std::vector<uint32_t>& selector) {
62 std::vector<uint32_t> iv(selector.size());
63 for (uint32_t i = 0; i < selector.size(); ++i) {
64 iv[i] = bv.IndexOfNthSet(selector[i]);
65 }
66 return iv;
67 }
68
69 } // namespace row_map_algorithms
70 } // namespace trace_processor
71 } // namespace perfetto
72
73 #endif // SRC_TRACE_PROCESSOR_CONTAINERS_ROW_MAP_ALGORITHMS_H_
74