1 /* 2 * Copyright (C) 2018 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_FILTERED_ROW_INDEX_H_ 18 #define SRC_TRACE_PROCESSOR_FILTERED_ROW_INDEX_H_ 19 20 #include <stdint.h> 21 #include <algorithm> 22 #include <memory> 23 #include <string> 24 #include <vector> 25 26 #include "perfetto/base/logging.h" 27 #include "src/trace_processor/row_iterators.h" 28 29 namespace perfetto { 30 namespace trace_processor { 31 32 // Storage for information about the rows to be returned by a filter operation. 33 // 34 // There are two users of FilteredRowIndex: 35 // 1. The filter classes which get told to filter all their rows on a certain 36 // constraint, returning their result in an instance of this class. They will 37 // have to call one of the three functions described below to restrict the rows 38 // returned. 39 // 2. The coordiator which has access to all the constraints. They pass an 40 // instance of this class and the constraint to filter on to each filter 41 // class. Once all the constraints are filtered, the coordinator will extract 42 // the underlying row representation from the instance of this class and use 43 // that to read rows from the storage. 44 class FilteredRowIndex { 45 public: 46 FilteredRowIndex(uint32_t start_row, uint32_t end_row); 47 48 // One of the following three functions can be called by the filter classes 49 // to restrict which rows should be returned. 50 51 // Interesects the rows specified by |rows| with the already filtered rows 52 // and updates the index to the intersection. 53 void IntersectRows(std::vector<uint32_t> rows); 54 55 // Calls |fn| on each row index which is currently to be returned and retains 56 // row index if |fn| returns true or discards the row otherwise. 57 template <typename RowPredicate /* (uint32_t) -> bool */> FilterRows(RowPredicate fn)58 void FilterRows(RowPredicate fn) { 59 PERFETTO_DCHECK(error_.empty()); 60 61 switch (mode_) { 62 case Mode::kAllRows: 63 FilterAllRows(fn); 64 break; 65 case Mode::kBitVector: 66 FilterBitVector(fn); 67 break; 68 case Mode::kRowVector: 69 FilterRowVector(fn); 70 break; 71 } 72 } 73 74 // Called when there is some error in the filter operation requested. The 75 // error string is used by the coordinator to report the error to SQLite. set_error(std::string error)76 void set_error(std::string error) { error_ = std::move(error); } 77 78 // The following functions should only be called by the coordinator classes. 79 80 // Converts this index into a vector of row indicies. 81 // Note: this function leaves the index in a freshly constructed state. 82 std::vector<uint32_t> ToRowVector(); 83 84 // Converts this index into a row iterator. 85 // Note: this function leaves the index in a freshly constructed state. 86 std::unique_ptr<RowIterator> ToRowIterator(bool desc); 87 88 // Returns the error from the filter operation invoked. May be empty if no 89 // error occurred. error()90 const std::string& error() const { return error_; } 91 92 private: 93 enum Mode { 94 kAllRows = 1, 95 kBitVector = 2, 96 kRowVector = 3, 97 }; 98 99 template <typename Predicate> FilterAllRows(Predicate fn)100 void FilterAllRows(Predicate fn) { 101 mode_ = Mode::kBitVector; 102 row_filter_.resize(end_row_ - start_row_, false); 103 104 for (auto i = start_row_; i < end_row_; i++) { 105 if (fn(i)) 106 row_filter_[i - start_row_] = true; 107 } 108 } 109 110 template <typename Predicate> FilterBitVector(Predicate fn)111 void FilterBitVector(Predicate fn) { 112 auto b = row_filter_.begin(); 113 auto e = row_filter_.end(); 114 115 using std::find; 116 for (auto it = find(b, e, true); it != e; it = find(it + 1, e, true)) { 117 auto filter_idx = static_cast<uint32_t>(std::distance(b, it)); 118 auto value_it = start_row_ + filter_idx; 119 *it = fn(value_it); 120 } 121 } 122 123 template <typename Predicate> FilterRowVector(Predicate fn)124 void FilterRowVector(Predicate fn) { 125 size_t rows_size = rows_.size(); 126 for (size_t i = 0; i < rows_size;) { 127 if (fn(rows_[i])) { 128 i++; 129 } else { 130 std::swap(rows_[i], rows_[rows_size - 1]); 131 rows_size--; 132 } 133 } 134 rows_.resize(rows_size); 135 } 136 137 void ConvertBitVectorToRowVector(); 138 139 std::vector<uint32_t> TakeRowVector(); 140 141 std::vector<bool> TakeBitVector(); 142 143 Mode mode_; 144 uint32_t start_row_; 145 uint32_t end_row_; 146 147 // Only non-empty when |mode_| == Mode::kBitVector. 148 std::vector<bool> row_filter_; 149 150 // Only non-empty when |mode_| == Mode::kRowVector. 151 // This vector is sorted. 152 std::vector<uint32_t> rows_; 153 154 std::string error_; 155 }; 156 157 } // namespace trace_processor 158 } // namespace perfetto 159 160 #endif // SRC_TRACE_PROCESSOR_FILTERED_ROW_INDEX_H_ 161