/*
|
* Copyright (C) 2018 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.
|
*/
|
|
#include "src/trace_processor/filtered_row_index.h"
|
|
#include <numeric>
|
|
namespace perfetto {
|
namespace trace_processor {
|
|
FilteredRowIndex::FilteredRowIndex(uint32_t start_row, uint32_t end_row)
|
: mode_(Mode::kAllRows), start_row_(start_row), end_row_(end_row) {}
|
|
void FilteredRowIndex::IntersectRows(std::vector<uint32_t> rows) {
|
PERFETTO_DCHECK(error_.empty());
|
|
// Sort the rows so all branches below make sense.
|
std::sort(rows.begin(), rows.end());
|
|
if (mode_ == kAllRows) {
|
mode_ = Mode::kRowVector;
|
// Yes you're reading this code correctly. We use lower_bound in both cases.
|
// Yes this is very intentional and has to do with |end_row_| already being
|
// one greater than the value we are searching for so we need the first
|
// iterator which is *geq* the |end_row_|.
|
auto begin = std::lower_bound(rows.begin(), rows.end(), start_row_);
|
auto end = std::lower_bound(begin, rows.end(), end_row_);
|
rows_.insert(rows_.end(), begin, end);
|
return;
|
} else if (mode_ == kRowVector) {
|
std::vector<uint32_t> intersected;
|
std::set_intersection(rows_.begin(), rows_.end(), rows.begin(), rows.end(),
|
std::back_inserter(intersected));
|
rows_ = std::move(intersected);
|
return;
|
}
|
|
// Initialise start to the beginning of the vector.
|
auto start = row_filter_.begin();
|
|
// Skip directly to the rows in range of start and end.
|
size_t i = 0;
|
for (; i < rows.size() && rows[i] < start_row_; i++) {
|
}
|
for (; i < rows.size() && rows[i] < end_row_; i++) {
|
// Unset all bits between the start iterator and the iterator pointing
|
// to the current row. That is, this loop sets all elements not pointed
|
// to by rows to false. It does not touch the rows themselves which
|
// means if they were already false (i.e. not returned) then they won't
|
// be returned now and if they were true (i.e. returned) they will still
|
// be returned.
|
auto row = rows[i];
|
auto end = row_filter_.begin() + static_cast<ptrdiff_t>(row - start_row_);
|
std::fill(start, end, false);
|
start = end + 1;
|
}
|
std::fill(start, row_filter_.end(), false);
|
}
|
|
std::vector<uint32_t> FilteredRowIndex::ToRowVector() {
|
PERFETTO_DCHECK(error_.empty());
|
|
switch (mode_) {
|
case Mode::kAllRows:
|
mode_ = Mode::kRowVector;
|
rows_.resize(end_row_ - start_row_);
|
std::iota(rows_.begin(), rows_.end(), start_row_);
|
break;
|
case Mode::kBitVector:
|
ConvertBitVectorToRowVector();
|
break;
|
case Mode::kRowVector:
|
// Nothing to do.
|
break;
|
}
|
return TakeRowVector();
|
}
|
|
void FilteredRowIndex::ConvertBitVectorToRowVector() {
|
PERFETTO_DCHECK(error_.empty());
|
|
mode_ = Mode::kRowVector;
|
|
auto b = row_filter_.begin();
|
auto e = row_filter_.end();
|
using std::find;
|
for (auto it = find(b, e, true); it != e; it = find(it + 1, e, true)) {
|
auto filter_idx = static_cast<uint32_t>(std::distance(b, it));
|
rows_.emplace_back(filter_idx + start_row_);
|
}
|
row_filter_.clear();
|
}
|
|
std::unique_ptr<RowIterator> FilteredRowIndex::ToRowIterator(bool desc) {
|
PERFETTO_DCHECK(error_.empty());
|
|
switch (mode_) {
|
case Mode::kAllRows:
|
return std::unique_ptr<RangeRowIterator>(
|
new RangeRowIterator(start_row_, end_row_, desc));
|
case Mode::kBitVector: {
|
return std::unique_ptr<RangeRowIterator>(
|
new RangeRowIterator(start_row_, desc, TakeBitVector()));
|
}
|
case Mode::kRowVector: {
|
auto vector = TakeRowVector();
|
if (desc)
|
std::reverse(vector.begin(), vector.end());
|
return std::unique_ptr<VectorRowIterator>(
|
new VectorRowIterator(std::move(vector)));
|
}
|
}
|
PERFETTO_FATAL("For GCC");
|
}
|
|
std::vector<uint32_t> FilteredRowIndex::TakeRowVector() {
|
PERFETTO_DCHECK(error_.empty());
|
|
PERFETTO_DCHECK(mode_ == Mode::kRowVector);
|
auto vector = std::move(rows_);
|
rows_.clear();
|
mode_ = Mode::kAllRows;
|
return vector;
|
}
|
|
std::vector<bool> FilteredRowIndex::TakeBitVector() {
|
PERFETTO_DCHECK(error_.empty());
|
|
PERFETTO_DCHECK(mode_ == Mode::kBitVector);
|
auto filter = std::move(row_filter_);
|
row_filter_.clear();
|
mode_ = Mode::kAllRows;
|
return filter;
|
}
|
|
} // namespace trace_processor
|
} // namespace perfetto
|
