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