Merge "trace_processor: optimize filtering for sched slice and generify"
diff --git a/src/trace_processor/sched_slice_table.cc b/src/trace_processor/sched_slice_table.cc
index 8915c65..079168f 100644
--- a/src/trace_processor/sched_slice_table.cc
+++ b/src/trace_processor/sched_slice_table.cc
@@ -34,49 +34,6 @@
constexpr uint64_t kUint64Max = std::numeric_limits<uint64_t>::max();
-template <size_t N = base::kMaxCpus>
-bool PopulateFilterBitmap(int op,
- sqlite3_value* value,
- std::bitset<N>* filter) {
- bool constraint_implemented = true;
- int64_t int_value = sqlite3_value_int64(value);
- if (IsOpGe(op) || IsOpGt(op)) {
- // If the operator is gt, then add one to the upper bound.
- int_value = IsOpGt(op) ? int_value + 1 : int_value;
-
- // Set to false all values less than |int_value|.
- size_t ub = static_cast<size_t>(std::max<int64_t>(0, int_value));
- ub = std::min(ub, filter->size());
- for (size_t i = 0; i < ub; i++) {
- filter->set(i, false);
- }
- } else if (IsOpLe(op) || IsOpLt(op)) {
- // If the operator is lt, then minus one to the lower bound.
- int_value = IsOpLt(op) ? int_value - 1 : int_value;
-
- // Set to false all values greater than |int_value|.
- size_t lb = static_cast<size_t>(std::max<int64_t>(0, int_value));
- lb = std::min(lb, filter->size());
- for (size_t i = lb; i < filter->size(); i++) {
- filter->set(i, false);
- }
- } else if (IsOpEq(op)) {
- if (int_value >= 0 && static_cast<size_t>(int_value) < filter->size()) {
- // If the value is in bounds, set all bits to false and restore the value
- // of the bit at the specified index.
- bool existing = filter->test(static_cast<size_t>(int_value));
- filter->reset();
- filter->set(static_cast<size_t>(int_value), existing);
- } else {
- // If the index is out of bounds, nothing should match.
- filter->reset();
- }
- } else {
- constraint_implemented = false;
- }
- return constraint_implemented;
-}
-
template <class T>
inline int Compare(T first, T second, bool desc) {
if (first < second) {
@@ -87,6 +44,137 @@
return 0;
}
+// Compares the slice at index |f| with the slice at index |s| on the
+// criteria in |order_by|.
+// Returns -1 if the first slice is before the second in the ordering, 1 if
+// the first slice is after the second and 0 if they are equal.
+PERFETTO_ALWAYS_INLINE int CompareSlicesOnColumn(
+ const TraceStorage* storage,
+ size_t f_idx,
+ size_t s_idx,
+ const QueryConstraints::OrderBy& ob) {
+ const auto& sl = storage->slices();
+ switch (ob.iColumn) {
+ case SchedSliceTable::Column::kTimestamp:
+ return Compare(sl.start_ns()[f_idx], sl.start_ns()[s_idx], ob.desc);
+ case SchedSliceTable::Column::kDuration:
+ return Compare(sl.durations()[f_idx], sl.durations()[s_idx], ob.desc);
+ case SchedSliceTable::Column::kCpu:
+ return Compare(sl.cpus()[f_idx], sl.cpus()[s_idx], ob.desc);
+ case SchedSliceTable::Column::kUtid:
+ return Compare(sl.utids()[f_idx], sl.utids()[s_idx], ob.desc);
+ default:
+ PERFETTO_FATAL("Unexpected column %d", ob.iColumn);
+ }
+}
+
+// Compares the slice at index |f| with the slice at index |s|on all
+// columns.
+// Returns -1 if the first slice is before the second in the ordering, 1 if
+// the first slice is after the second and 0 if they are equal.
+PERFETTO_ALWAYS_INLINE int CompareSlices(
+ const TraceStorage* storage,
+ size_t f_idx,
+ size_t s_idx,
+ const std::vector<QueryConstraints::OrderBy>& order_by) {
+ for (const auto& ob : order_by) {
+ int c = CompareSlicesOnColumn(storage, f_idx, s_idx, ob);
+ if (c != 0)
+ return c;
+ }
+ return 0;
+}
+
+std::pair<uint64_t, uint64_t> GetTsBounds(const QueryConstraints& qc,
+ sqlite3_value** argv) {
+ uint64_t min_ts = 0;
+ uint64_t max_ts = kUint64Max;
+ for (size_t i = 0; i < qc.constraints().size(); i++) {
+ const auto& cs = qc.constraints()[i];
+ switch (cs.iColumn) {
+ case SchedSliceTable::Column::kTimestamp:
+ auto ts = static_cast<uint64_t>(sqlite3_value_int64(argv[i]));
+ if (IsOpGe(cs.op) || IsOpGt(cs.op)) {
+ min_ts = IsOpGe(cs.op) ? ts : ts + 1;
+ } else if (IsOpLe(cs.op) || IsOpLt(cs.op)) {
+ max_ts = IsOpLe(cs.op) ? ts : ts - 1;
+ } else if (IsOpEq(cs.op)) {
+ min_ts = ts;
+ max_ts = ts;
+ } else {
+ // We can't handle any other constraints on ts.
+ PERFETTO_CHECK(false);
+ }
+ break;
+ }
+ }
+ return std::make_pair(min_ts, max_ts);
+}
+
+std::pair<uint32_t, uint32_t> FindTsIndices(
+ const TraceStorage* storage,
+ std::pair<uint64_t, uint64_t> ts_bounds) {
+ const auto& slices = storage->slices();
+ const auto& ts = slices.start_ns();
+ PERFETTO_CHECK(slices.slice_count() <= std::numeric_limits<uint32_t>::max());
+
+ auto min_it = std::lower_bound(ts.begin(), ts.end(), ts_bounds.first);
+ auto min_idx = static_cast<uint32_t>(std::distance(ts.begin(), min_it));
+
+ auto max_it = std::upper_bound(min_it, ts.end(), ts_bounds.second);
+ auto max_idx = static_cast<uint32_t>(std::distance(ts.begin(), max_it));
+
+ return std::make_pair(min_idx, max_idx);
+}
+
+std::vector<bool> FilterNonTsColumns(const TraceStorage* storage,
+ const QueryConstraints& qc,
+ sqlite3_value** argv,
+ uint32_t min_idx,
+ uint32_t max_idx) {
+ const auto& slices = storage->slices();
+ ptrdiff_t min_idx_ptr = static_cast<ptrdiff_t>(min_idx);
+ ptrdiff_t max_idx_ptr = static_cast<ptrdiff_t>(max_idx);
+
+ auto dist = static_cast<size_t>(max_idx - min_idx);
+ std::vector<bool> filter(dist, true);
+ for (size_t i = 0; i < qc.constraints().size(); i++) {
+ const auto& cs = qc.constraints()[i];
+ auto* v = argv[i];
+ switch (cs.iColumn) {
+ case SchedSliceTable::Column::kCpu: {
+ auto it = slices.cpus().begin();
+ FilterColumn(it + min_idx_ptr, it + max_idx_ptr, cs, v, &filter);
+ break;
+ }
+ case SchedSliceTable::Column::kDuration: {
+ auto it = slices.durations().begin();
+ FilterColumn(it + min_idx_ptr, it + max_idx_ptr, cs, v, &filter);
+ break;
+ }
+ case SchedSliceTable::Column::kUtid: {
+ auto it = slices.utids().begin();
+ FilterColumn(it + min_idx_ptr, it + max_idx_ptr, cs, v, &filter);
+ break;
+ }
+ }
+ }
+ return filter;
+}
+
+bool HasOnlyTsConstraints(const QueryConstraints& qc) {
+ auto fn = [](const QueryConstraints::Constraint& c) {
+ return c.iColumn == SchedSliceTable::Column::kTimestamp;
+ };
+ return std::all_of(qc.constraints().begin(), qc.constraints().end(), fn);
+}
+
+bool IsTsOrdered(const QueryConstraints& qc) {
+ return qc.order_by().size() == 0 ||
+ (qc.order_by().size() == 1 &&
+ qc.order_by()[0].iColumn == SchedSliceTable::Column::kTimestamp);
+}
+
} // namespace
SchedSliceTable::SchedSliceTable(sqlite3*, const TraceStorage* storage)
@@ -110,85 +198,50 @@
std::unique_ptr<Table::Cursor> SchedSliceTable::CreateCursor(
const QueryConstraints& qc,
sqlite3_value** argv) {
- return std::unique_ptr<Table::Cursor>(new Cursor(storage_, qc, argv));
+ auto ts_indices = FindTsIndices(storage_, GetTsBounds(qc, argv));
+ auto min_idx = ts_indices.first;
+ auto max_idx = ts_indices.second;
+
+ if (HasOnlyTsConstraints(qc)) {
+ if (IsTsOrdered(qc)) {
+ bool desc = qc.order_by().size() == 1 && qc.order_by()[0].desc;
+ return std::unique_ptr<Table::Cursor>(
+ new IncrementCursor(storage_, min_idx, max_idx, desc));
+ }
+ return std::unique_ptr<Table::Cursor>(
+ new SortedCursor(storage_, min_idx, max_idx, qc.order_by()));
+ }
+
+ std::vector<bool> filter =
+ FilterNonTsColumns(storage_, qc, argv, min_idx, max_idx);
+ if (IsTsOrdered(qc)) {
+ bool desc = qc.order_by().size() == 1 && qc.order_by()[0].desc;
+ return std::unique_ptr<Table::Cursor>(
+ new FilterCursor(storage_, min_idx, max_idx, std::move(filter), desc));
+ }
+ return std::unique_ptr<Table::Cursor>(new SortedCursor(
+ storage_, min_idx, max_idx, qc.order_by(), std::move(filter)));
}
int SchedSliceTable::BestIndex(const QueryConstraints& qc,
BestIndexInfo* info) {
- bool is_time_constrained = false;
- for (size_t i = 0; i < qc.constraints().size(); i++) {
- const auto& cs = qc.constraints()[i];
- if (cs.iColumn == Column::kTimestamp)
- is_time_constrained = true;
- }
-
+ bool is_time_constrained =
+ !qc.constraints().empty() && HasOnlyTsConstraints(qc);
info->estimated_cost = is_time_constrained ? 10 : 10000;
info->order_by_consumed = true;
+ // We should be able to handle any constraint thrown at us.
+ std::fill(info->omit.begin(), info->omit.end(), true);
+
return SQLITE_OK;
}
-SchedSliceTable::Cursor::Cursor(const TraceStorage* storage,
- const QueryConstraints& query_constraints,
- sqlite3_value** argv)
- : order_by_(query_constraints.order_by()), storage_(storage) {
- // Remove ordering on timestamp if it is the only ordering as we are already
- // sorted on TS. This makes span joining significantly faster.
- if (order_by_.size() == 1 && order_by_[0].iColumn == Column::kTimestamp &&
- !order_by_[0].desc) {
- order_by_.clear();
- }
+SchedSliceTable::BaseCursor::BaseCursor(const TraceStorage* storage)
+ : storage_(storage) {}
+SchedSliceTable::BaseCursor::~BaseCursor() = default;
- std::bitset<base::kMaxCpus> cpu_filter;
- cpu_filter.set();
-
- uint64_t min_ts = 0;
- uint64_t max_ts = kUint64Max;
-
- for (size_t i = 0; i < query_constraints.constraints().size(); i++) {
- const auto& cs = query_constraints.constraints()[i];
- switch (cs.iColumn) {
- case Column::kCpu:
- PopulateFilterBitmap(cs.op, argv[i], &cpu_filter);
- break;
- case Column::kTimestamp: {
- auto ts = static_cast<uint64_t>(sqlite3_value_int64(argv[i]));
- if (IsOpGe(cs.op) || IsOpGt(cs.op)) {
- min_ts = IsOpGe(cs.op) ? ts : ts + 1;
- } else if (IsOpLe(cs.op) || IsOpLt(cs.op)) {
- max_ts = IsOpLe(cs.op) ? ts : ts - 1;
- }
- break;
- }
- }
- }
- SetupSortedRowIds(min_ts, max_ts);
-
- // Filter rows on CPUs if any CPUs need to be excluded.
- const auto& slices = storage_->slices();
- row_filter_.resize(sorted_row_ids_.size(), true);
- if (cpu_filter.count() < cpu_filter.size()) {
- for (size_t i = 0; i < sorted_row_ids_.size(); i++) {
- row_filter_[i] = cpu_filter.test(slices.cpus()[sorted_row_ids_[i]]);
- }
- }
- FindNextRowAndTimestamp();
-}
-
-int SchedSliceTable::Cursor::Next() {
- next_row_id_index_++;
- FindNextRowAndTimestamp();
- return SQLITE_OK;
-}
-
-int SchedSliceTable::Cursor::Eof() {
- return !IsNextRowIdIndexValid();
-}
-
-int SchedSliceTable::Cursor::Column(sqlite3_context* context, int N) {
- PERFETTO_DCHECK(IsNextRowIdIndexValid());
-
- size_t row = next_row_id();
+int SchedSliceTable::BaseCursor::Column(sqlite3_context* context, int N) {
+ size_t row = RowIndex();
const auto& slices = storage_->slices();
switch (N) {
case Column::kTimestamp: {
@@ -213,64 +266,116 @@
return SQLITE_OK;
}
-void SchedSliceTable::Cursor::SetupSortedRowIds(uint64_t min_ts,
- uint64_t max_ts) {
- const auto& slices = storage_->slices();
- const auto& start_ns = slices.start_ns();
- PERFETTO_CHECK(slices.slice_count() <= std::numeric_limits<uint32_t>::max());
+SchedSliceTable::IncrementCursor::IncrementCursor(const TraceStorage* storage,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ bool desc)
+ : BaseCursor(storage), min_idx_(min_idx), max_idx_(max_idx), desc_(desc) {}
- auto min_it = std::lower_bound(start_ns.begin(), start_ns.end(), min_ts);
- auto max_it = std::upper_bound(min_it, start_ns.end(), max_ts);
- ptrdiff_t dist = std::distance(min_it, max_it);
- PERFETTO_CHECK(dist >= 0 && static_cast<size_t>(dist) <= start_ns.size());
+int SchedSliceTable::IncrementCursor::Next() {
+ offset_++;
+ return SQLITE_OK;
+}
- // Fill |indices| with the consecutive row numbers affected by the filtering.
- sorted_row_ids_.resize(static_cast<size_t>(dist));
- std::iota(sorted_row_ids_.begin(), sorted_row_ids_.end(),
- std::distance(start_ns.begin(), min_it));
+uint32_t SchedSliceTable::IncrementCursor::RowIndex() {
+ return desc_ ? max_idx_ - 1 - offset_ : min_idx_ + offset_;
+}
- // Sort if there is any order by constraints.
- if (!order_by_.empty()) {
- std::sort(
- sorted_row_ids_.begin(), sorted_row_ids_.end(),
- [this](uint32_t f, uint32_t s) { return CompareSlices(f, s) < 0; });
+int SchedSliceTable::IncrementCursor::Eof() {
+ return offset_ >= (max_idx_ - min_idx_);
+}
+
+SchedSliceTable::FilterCursor::FilterCursor(const TraceStorage* storage,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ std::vector<bool> filter,
+ bool desc)
+ : BaseCursor(storage),
+ min_idx_(min_idx),
+ max_idx_(max_idx),
+ filter_(std::move(filter)),
+ desc_(desc) {
+ PERFETTO_CHECK(max_idx - min_idx == filter_.size());
+ FindNext();
+}
+
+int SchedSliceTable::FilterCursor::Next() {
+ offset_++;
+ FindNext();
+ return SQLITE_OK;
+}
+
+void SchedSliceTable::FilterCursor::FindNext() {
+ ptrdiff_t offset = static_cast<ptrdiff_t>(offset_);
+ if (desc_) {
+ auto it = std::find(filter_.rbegin() + offset, filter_.rend(), true);
+ offset_ = static_cast<uint32_t>(std::distance(filter_.rbegin(), it));
+ } else {
+ auto it = std::find(filter_.begin() + offset, filter_.end(), true);
+ offset_ = static_cast<uint32_t>(std::distance(filter_.begin(), it));
}
}
-int SchedSliceTable::Cursor::CompareSlices(size_t f_idx, size_t s_idx) {
- for (const auto& ob : order_by_) {
- int c = CompareSlicesOnColumn(f_idx, s_idx, ob);
- if (c != 0)
- return c;
- }
- return 0;
+uint32_t SchedSliceTable::FilterCursor::RowIndex() {
+ return desc_ ? max_idx_ - 1 - offset_ : min_idx_ + offset_;
}
-int SchedSliceTable::Cursor::CompareSlicesOnColumn(
- size_t f_idx,
- size_t s_idx,
- const QueryConstraints::OrderBy& ob) {
- const auto& sl = storage_->slices();
- switch (ob.iColumn) {
- case SchedSliceTable::Column::kTimestamp:
- return Compare(sl.start_ns()[f_idx], sl.start_ns()[s_idx], ob.desc);
- case SchedSliceTable::Column::kDuration:
- return Compare(sl.durations()[f_idx], sl.durations()[s_idx], ob.desc);
- case SchedSliceTable::Column::kCpu:
- return Compare(sl.cpus()[f_idx], sl.cpus()[s_idx], ob.desc);
- case SchedSliceTable::Column::kUtid:
- return Compare(sl.utids()[f_idx], sl.utids()[s_idx], ob.desc);
- }
- PERFETTO_FATAL("Unexpected column %d", ob.iColumn);
+int SchedSliceTable::FilterCursor::Eof() {
+ return offset_ >= (max_idx_ - min_idx_);
}
-void SchedSliceTable::Cursor::FindNextRowAndTimestamp() {
- auto start =
- row_filter_.begin() +
- static_cast<decltype(row_filter_)::difference_type>(next_row_id_index_);
- auto next_it = std::find(start, row_filter_.end(), true);
- next_row_id_index_ =
- static_cast<uint32_t>(std::distance(row_filter_.begin(), next_it));
+SchedSliceTable::SortedCursor::SortedCursor(
+ const TraceStorage* storage,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ const std::vector<QueryConstraints::OrderBy>& ob)
+ : BaseCursor(storage) {
+ auto diff = static_cast<size_t>(max_idx - min_idx);
+ sorted_rows_.resize(static_cast<size_t>(diff));
+
+ std::iota(sorted_rows_.begin(), sorted_rows_.end(), min_idx);
+ std::sort(sorted_rows_.begin(), sorted_rows_.end(),
+ [this, &ob](uint32_t f, uint32_t s) {
+ return CompareSlices(storage_, f, s, ob) < 0;
+ });
+}
+
+SchedSliceTable::SortedCursor::SortedCursor(
+ const TraceStorage* storage,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ const std::vector<QueryConstraints::OrderBy>& ob,
+ const std::vector<bool>& filter)
+ : BaseCursor(storage) {
+ auto diff = static_cast<size_t>(max_idx - min_idx);
+ PERFETTO_CHECK(diff == filter.size());
+
+ auto set_bits = std::count(filter.begin(), filter.end(), true);
+ sorted_rows_.resize(static_cast<size_t>(set_bits));
+
+ auto it = std::find(filter.begin(), filter.end(), true);
+ for (size_t i = 0; it != filter.end(); i++) {
+ auto index = static_cast<uint32_t>(std::distance(filter.begin(), it));
+ sorted_rows_[i] = min_idx + index;
+ it = std::find(it + 1, filter.end(), true);
+ }
+ std::sort(sorted_rows_.begin(), sorted_rows_.end(),
+ [this, &ob](uint32_t f, uint32_t s) {
+ return CompareSlices(storage_, f, s, ob) < 0;
+ });
+}
+
+int SchedSliceTable::SortedCursor::Next() {
+ next_row_idx_++;
+ return SQLITE_OK;
+}
+
+uint32_t SchedSliceTable::SortedCursor::RowIndex() {
+ return sorted_rows_[next_row_idx_];
+}
+
+int SchedSliceTable::SortedCursor::Eof() {
+ return next_row_idx_ >= sorted_rows_.size();
}
} // namespace trace_processor
diff --git a/src/trace_processor/sched_slice_table.h b/src/trace_processor/sched_slice_table.h
index ccd6b26..bd63df8 100644
--- a/src/trace_processor/sched_slice_table.h
+++ b/src/trace_processor/sched_slice_table.h
@@ -52,57 +52,91 @@
int BestIndex(const QueryConstraints&, BestIndexInfo*) override;
private:
- // Implementation of the Table cursor interface.
- class Cursor : public Table::Cursor {
+ // Base class for other cursors, implementing column reporting.
+ class BaseCursor : public Table::Cursor {
public:
- Cursor(const TraceStorage* storage,
- const QueryConstraints& query_constraints,
- sqlite3_value** argv);
+ BaseCursor(const TraceStorage* storage);
+ virtual ~BaseCursor() override;
+
+ virtual uint32_t RowIndex() = 0;
+ int Column(sqlite3_context*, int N) override final;
+
+ protected:
+ const TraceStorage* const storage_;
+ };
+
+ // Very fast cursor which which simply increments through indices.
+ class IncrementCursor : public BaseCursor {
+ public:
+ IncrementCursor(const TraceStorage*,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ bool desc);
int Next() override;
+ uint32_t RowIndex() override;
int Eof() override;
- int Column(sqlite3_context*, int N) override;
-
- inline bool IsNextRowIdIndexValid() const {
- return next_row_id_index_ < sorted_row_ids_.size();
- }
-
- size_t next_row_id() const { return sorted_row_ids_[next_row_id_index_]; }
private:
- // Updates |sorted_row_ids_| with the indices into the slices sorted by the
- // order by criteria.
- void SetupSortedRowIds(uint64_t min_ts, uint64_t max_ts);
+ uint32_t const min_idx_;
+ uint32_t const max_idx_;
+ bool const desc_;
- // Compares the slice at index |f| with the slice at index |s|on all
- // columns.
- // Returns -1 if the first slice is before the second in the ordering, 1 if
- // the first slice is after the second and 0 if they are equal.
- int CompareSlices(size_t f, size_t s);
+ // In non-desc mode, this is an offset from min_idx while in desc mode, this
+ // is an offset from max_idx_.
+ uint32_t offset_ = 0;
+ };
- // Compares the slice at index |f| with the slice at index |s| on the
- // criteria in |order_by|.
- // Returns -1 if the first slice is before the second in the ordering, 1 if
- // the first slice is after the second and 0 if they are equal.
- int CompareSlicesOnColumn(size_t f,
- size_t s,
- const QueryConstraints::OrderBy& order_by);
+ // Reasonably fast cursor which stores a vector of booleans about whether
+ // a row should be returned.
+ class FilterCursor : public BaseCursor {
+ public:
+ FilterCursor(const TraceStorage*,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ std::vector<bool> filter,
+ bool desc);
- void FindNextRowAndTimestamp();
+ int Next() override;
+ uint32_t RowIndex() override;
+ int Eof() override;
- // Vector of row ids sorted by the the given order by constraints.
- std::vector<uint32_t> sorted_row_ids_;
+ private:
+ void FindNext();
- // Bitset for filtering slices.
- std::vector<bool> row_filter_;
+ uint32_t const min_idx_;
+ uint32_t const max_idx_;
+ std::vector<bool> filter_;
+ bool const desc_;
+
+ // In non-desc mode, this is an offset from min_idx while in desc mode, this
+ // is an offset from max_idx_.
+ uint32_t offset_ = 0;
+ };
+
+ // Slow path cursor which stores a sorted set of indices into storage.
+ class SortedCursor : public BaseCursor {
+ public:
+ SortedCursor(const TraceStorage* storage,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ const std::vector<QueryConstraints::OrderBy>&);
+ SortedCursor(const TraceStorage* storage,
+ uint32_t min_idx,
+ uint32_t max_idx,
+ const std::vector<QueryConstraints::OrderBy>&,
+ const std::vector<bool>& filter);
+
+ int Next() override;
+ uint32_t RowIndex() override;
+ int Eof() override;
+
+ private:
+ // Vector of row ids sorted by some order by constraints.
+ std::vector<uint32_t> sorted_rows_;
// An offset into |sorted_row_ids_| indicating the next row to return.
- uint32_t next_row_id_index_ = 0;
-
- // The sorting criteria for this filter operation.
- std::vector<QueryConstraints::OrderBy> order_by_;
-
- const TraceStorage* const storage_;
+ uint32_t next_row_idx_ = 0;
};
const TraceStorage* const storage_;
diff --git a/src/trace_processor/sqlite_utils.h b/src/trace_processor/sqlite_utils.h
index b1e0499..191f316 100644
--- a/src/trace_processor/sqlite_utils.h
+++ b/src/trace_processor/sqlite_utils.h
@@ -18,6 +18,12 @@
#define SRC_TRACE_PROCESSOR_SQLITE_UTILS_H_
#include <sqlite3.h>
+#include <algorithm>
+#include <deque>
+#include <iterator>
+
+#include "perfetto/base/logging.h"
+#include "src/trace_processor/query_constraints.h"
namespace perfetto {
namespace trace_processor {
@@ -62,6 +68,57 @@
}
}
+template <typename F>
+bool Compare(uint32_t actual, sqlite3_value* value) {
+ PERFETTO_DCHECK(sqlite3_value_type(value) == SQLITE_INTEGER);
+ return F()(actual, static_cast<uint32_t>(sqlite3_value_int64(value)));
+}
+
+template <typename F>
+bool Compare(uint64_t actual, sqlite3_value* value) {
+ PERFETTO_CHECK(sqlite3_value_type(value) == SQLITE_INTEGER);
+ return F()(actual, static_cast<uint64_t>(sqlite3_value_int64(value)));
+}
+
+template <class RandomAccessIterator>
+void FilterColumn(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ const QueryConstraints::Constraint& constraint,
+ sqlite3_value* argv,
+ std::vector<bool>* row_filter) {
+ using T = typename RandomAccessIterator::value_type;
+ PERFETTO_DCHECK(static_cast<size_t>(std::distance(begin, end)) ==
+ row_filter->size());
+
+ auto it = std::find(row_filter->begin(), row_filter->end(), true);
+ while (it != row_filter->end()) {
+ auto index = std::distance(row_filter->begin(), it);
+ switch (constraint.op) {
+ case SQLITE_INDEX_CONSTRAINT_EQ:
+ *it = Compare<std::equal_to<T>>(begin[index], argv);
+ break;
+ case SQLITE_INDEX_CONSTRAINT_GE:
+ *it = Compare<std::greater_equal<T>>(begin[index], argv);
+ break;
+ case SQLITE_INDEX_CONSTRAINT_GT:
+ *it = Compare<std::greater<T>>(begin[index], argv);
+ break;
+ case SQLITE_INDEX_CONSTRAINT_LE:
+ *it = Compare<std::less_equal<T>>(begin[index], argv);
+ break;
+ case SQLITE_INDEX_CONSTRAINT_LT:
+ *it = Compare<std::less<T>>(begin[index], argv);
+ break;
+ case SQLITE_INDEX_CONSTRAINT_NE:
+ *it = Compare<std::not_equal_to<T>>(begin[index], argv);
+ break;
+ default:
+ PERFETTO_CHECK(false);
+ }
+ it = std::find(it + 1, row_filter->end(), true);
+ }
+}
+
} // namespace sqlite_utils
} // namespace trace_processor
} // namespace perfetto