• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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