| /* |
| * Copyright (C) 2022 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #ifndef SRC_TRACE_PROCESSOR_CONTAINERS_ROW_MAP_ALGORITHMS_H_ |
| #define SRC_TRACE_PROCESSOR_CONTAINERS_ROW_MAP_ALGORITHMS_H_ |
| |
| #include <vector> |
| |
| #include "perfetto/base/logging.h" |
| #include "src/trace_processor/containers/bit_vector.h" |
| #include "src/trace_processor/containers/bit_vector_iterators.h" |
| |
| // This file contains fundamental algorithms used by RowMap. |
| // |
| // This file is structured in a way to make benchmarking easy. The intention is |
| // to use this to decide which heurustics to use and the value of magic |
| // constants in RowMap algorithms. |
| |
| namespace perfetto { |
| namespace trace_processor { |
| namespace row_map_algorithms { |
| |
| // Returns a vector containing elements from |iv| selected by indices from |
| // |selector|. |
| inline std::vector<uint32_t> SelectIvWithIv( |
| const std::vector<uint32_t>& iv, |
| const std::vector<uint32_t>& selector) { |
| std::vector<uint32_t> ret(selector.size()); |
| for (uint32_t i = 0; i < selector.size(); ++i) { |
| PERFETTO_DCHECK(selector[i] < iv.size()); |
| ret[i] = iv[selector[i]]; |
| } |
| return ret; |
| } |
| |
| // Returns a vector containing elements from |bv| by first converting to an |
| // index vector and then selecting indices from |selector|. |
| inline std::vector<uint32_t> SelectBvWithIvByConvertToIv( |
| const BitVector& bv, |
| const std::vector<uint32_t>& selector) { |
| std::vector<uint32_t> bv_conv(bv.CountSetBits()); |
| for (auto it = bv.IterateSetBits(); it; it.Next()) { |
| bv_conv[it.ordinal()] = it.index(); |
| } |
| return SelectIvWithIv(bv_conv, selector); |
| } |
| |
| // Returns a vector containing elements from |bv| by selecting indices from |
| // |selector| using IndexOfNthSet calls. |
| inline std::vector<uint32_t> SelectBvWithIvByIndexOfNthSet( |
| const BitVector& bv, |
| const std::vector<uint32_t>& selector) { |
| std::vector<uint32_t> iv(selector.size()); |
| for (uint32_t i = 0; i < selector.size(); ++i) { |
| iv[i] = bv.IndexOfNthSet(selector[i]); |
| } |
| return iv; |
| } |
| |
| } // namespace row_map_algorithms |
| } // namespace trace_processor |
| } // namespace perfetto |
| |
| #endif // SRC_TRACE_PROCESSOR_CONTAINERS_ROW_MAP_ALGORITHMS_H_ |