• 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 #include "src/trace_processor/filtered_row_index.h"
18 
19 #include <numeric>
20 
21 namespace perfetto {
22 namespace trace_processor {
23 
FilteredRowIndex(uint32_t start_row,uint32_t end_row)24 FilteredRowIndex::FilteredRowIndex(uint32_t start_row, uint32_t end_row)
25     : mode_(Mode::kAllRows), start_row_(start_row), end_row_(end_row) {}
26 
IntersectRows(std::vector<uint32_t> rows)27 void FilteredRowIndex::IntersectRows(std::vector<uint32_t> rows) {
28   PERFETTO_DCHECK(error_.empty());
29 
30   // Sort the rows so all branches below make sense.
31   std::sort(rows.begin(), rows.end());
32 
33   if (mode_ == kAllRows) {
34     mode_ = Mode::kRowVector;
35     // Yes you're reading this code correctly. We use lower_bound in both cases.
36     // Yes this is very intentional and has to do with |end_row_| already being
37     // one greater than the value we are searching for so we need the first
38     // iterator which is *geq* the |end_row_|.
39     auto begin = std::lower_bound(rows.begin(), rows.end(), start_row_);
40     auto end = std::lower_bound(begin, rows.end(), end_row_);
41     rows_.insert(rows_.end(), begin, end);
42     return;
43   } else if (mode_ == kRowVector) {
44     std::vector<uint32_t> intersected;
45     std::set_intersection(rows_.begin(), rows_.end(), rows.begin(), rows.end(),
46                           std::back_inserter(intersected));
47     rows_ = std::move(intersected);
48     return;
49   }
50 
51   // Initialise start to the beginning of the vector.
52   auto start = row_filter_.begin();
53 
54   // Skip directly to the rows in range of start and end.
55   size_t i = 0;
56   for (; i < rows.size() && rows[i] < start_row_; i++) {
57   }
58   for (; i < rows.size() && rows[i] < end_row_; i++) {
59     // Unset all bits between the start iterator and the iterator pointing
60     // to the current row. That is, this loop sets all elements not pointed
61     // to by rows to false. It does not touch the rows themselves which
62     // means if they were already false (i.e. not returned) then they won't
63     // be returned now and if they were true (i.e. returned) they will still
64     // be returned.
65     auto row = rows[i];
66     auto end = row_filter_.begin() + static_cast<ptrdiff_t>(row - start_row_);
67     std::fill(start, end, false);
68     start = end + 1;
69   }
70   std::fill(start, row_filter_.end(), false);
71 }
72 
ToRowVector()73 std::vector<uint32_t> FilteredRowIndex::ToRowVector() {
74   PERFETTO_DCHECK(error_.empty());
75 
76   switch (mode_) {
77     case Mode::kAllRows:
78       mode_ = Mode::kRowVector;
79       rows_.resize(end_row_ - start_row_);
80       std::iota(rows_.begin(), rows_.end(), start_row_);
81       break;
82     case Mode::kBitVector:
83       ConvertBitVectorToRowVector();
84       break;
85     case Mode::kRowVector:
86       // Nothing to do.
87       break;
88   }
89   return TakeRowVector();
90 }
91 
ConvertBitVectorToRowVector()92 void FilteredRowIndex::ConvertBitVectorToRowVector() {
93   PERFETTO_DCHECK(error_.empty());
94 
95   mode_ = Mode::kRowVector;
96 
97   auto b = row_filter_.begin();
98   auto e = row_filter_.end();
99   using std::find;
100   for (auto it = find(b, e, true); it != e; it = find(it + 1, e, true)) {
101     auto filter_idx = static_cast<uint32_t>(std::distance(b, it));
102     rows_.emplace_back(filter_idx + start_row_);
103   }
104   row_filter_.clear();
105 }
106 
ToRowIterator(bool desc)107 std::unique_ptr<RowIterator> FilteredRowIndex::ToRowIterator(bool desc) {
108   PERFETTO_DCHECK(error_.empty());
109 
110   switch (mode_) {
111     case Mode::kAllRows:
112       return std::unique_ptr<RangeRowIterator>(
113           new RangeRowIterator(start_row_, end_row_, desc));
114     case Mode::kBitVector: {
115       return std::unique_ptr<RangeRowIterator>(
116           new RangeRowIterator(start_row_, desc, TakeBitVector()));
117     }
118     case Mode::kRowVector: {
119       auto vector = TakeRowVector();
120       if (desc)
121         std::reverse(vector.begin(), vector.end());
122       return std::unique_ptr<VectorRowIterator>(
123           new VectorRowIterator(std::move(vector)));
124     }
125   }
126   PERFETTO_FATAL("For GCC");
127 }
128 
TakeRowVector()129 std::vector<uint32_t> FilteredRowIndex::TakeRowVector() {
130   PERFETTO_DCHECK(error_.empty());
131 
132   PERFETTO_DCHECK(mode_ == Mode::kRowVector);
133   auto vector = std::move(rows_);
134   rows_.clear();
135   mode_ = Mode::kAllRows;
136   return vector;
137 }
138 
TakeBitVector()139 std::vector<bool> FilteredRowIndex::TakeBitVector() {
140   PERFETTO_DCHECK(error_.empty());
141 
142   PERFETTO_DCHECK(mode_ == Mode::kBitVector);
143   auto filter = std::move(row_filter_);
144   row_filter_.clear();
145   mode_ = Mode::kAllRows;
146   return filter;
147 }
148 
149 }  // namespace trace_processor
150 }  // namespace perfetto
151