Merge "tp: introduces SqliteEngine to broker all interactions with SQLite"
diff --git a/gn/BUILD.gn b/gn/BUILD.gn
index 192ede8..6edf379 100644
--- a/gn/BUILD.gn
+++ b/gn/BUILD.gn
@@ -275,7 +275,7 @@
"GOOGLE_PROTOBUF_NO_STATIC_INITIALIZER",
]
cflags = []
- if (!is_clang || !is_win) {
+ if (!is_clang && !is_win) {
cflags += [ "-Wno-deprecated-declarations" ]
}
if (is_clang && is_win) {
diff --git a/gn/standalone/BUILD.gn b/gn/standalone/BUILD.gn
index d000f53..0af6551 100644
--- a/gn/standalone/BUILD.gn
+++ b/gn/standalone/BUILD.gn
@@ -100,6 +100,18 @@
# TODO(lalitm): remove this when we upgrade to a GCC version which is good
# enough to handle this.
cflags_cc += [ "-Wno-maybe-uninitialized" ]
+
+ # GCC's handling of detecting infinite recursion is flaky at best and
+ # causes some false positives.
+ # TODO(lalitm): remove this when we upgrade to a GCC version which is good
+ # enough to handle this.
+ cflags_cc += [ "-Wno-infinite-recursion" ]
+
+ # GCC's handling of detecting non null arguments is flaky at best and
+ # causes some false positives.
+ # TODO(lalitm): remove this when we upgrade to a GCC version which is good
+ # enough to handle this.
+ cflags_cc += [ "-Wno-nonnull" ]
}
}
diff --git a/gn/standalone/toolchain/win_find_msvc.py b/gn/standalone/toolchain/win_find_msvc.py
index 1628c07..6f7eb86 100644
--- a/gn/standalone/toolchain/win_find_msvc.py
+++ b/gn/standalone/toolchain/win_find_msvc.py
@@ -27,6 +27,7 @@
"""
import os
+import itertools
import subprocess
import sys
@@ -62,19 +63,19 @@
filt = lambda x: os.path.exists(os.path.join(x, 'ucrt', 'x64', 'ucrt.lib'))
out[1] = find_max_subdir(lib_base, filt)
- for year in ['2022', '2021', '2020', '2019']:
- for version in [
- 'BuildTools', 'Community', 'Professional', 'Enterprise', 'Preview'
- ]:
- msvc_base = ('C:\\Program Files (x86)\\Microsoft Visual Studio\\'
- f'{year}\\{version}\\VC\\Tools\\MSVC')
- if os.path.exists(msvc_base):
- filt = lambda x: os.path.exists(
- os.path.join(x, 'lib', 'x64', 'libcmt.lib'))
- max_msvc = find_max_subdir(msvc_base, filt)
- if max_msvc is not None:
- out[2] = os.path.join(msvc_base, max_msvc)
- break
+ for try_dir in itertools.product(
+ ['2022', '2021', '2020', '2019'],
+ ['BuildTools', 'Community', 'Professional', 'Enterprise', 'Preview'],
+ ['Program Files', 'Program Files (x86)']):
+ msvc_base = (f'C:\\{try_dir[2]}\\Microsoft Visual Studio\\'
+ f'{try_dir[0]}\\{try_dir[1]}\\VC\\Tools\\MSVC')
+ if os.path.exists(msvc_base):
+ filt = lambda x: os.path.exists(
+ os.path.join(x, 'lib', 'x64', 'libcmt.lib'))
+ max_msvc = find_max_subdir(msvc_base, filt)
+ if max_msvc is not None:
+ out[2] = os.path.join(msvc_base, max_msvc)
+ break
# Don't error in case of failure, GN scripts are supposed to deal with
# failures and allow the user to override the dirs.
diff --git a/protos/perfetto/metrics/webview/webview_jank_approximation.proto b/protos/perfetto/metrics/webview/webview_jank_approximation.proto
index 0d01a77..cdf7299 100644
--- a/protos/perfetto/metrics/webview/webview_jank_approximation.proto
+++ b/protos/perfetto/metrics/webview/webview_jank_approximation.proto
@@ -19,9 +19,9 @@
package perfetto.protos;
message WebViewJankApproximation {
- required int32 webview_janks = 1;
- required int32 webview_janks_without_startup = 2;
- required int32 webview_app_janks = 3;
- required int32 webview_total_janks = 4;
- required int32 total_janks = 5;
+ optional int32 webview_janks = 1;
+ optional int32 webview_janks_without_startup = 2;
+ optional int32 webview_app_janks = 3;
+ optional int32 webview_total_janks = 4;
+ optional int32 total_janks = 5;
}
diff --git a/src/trace_processor/containers/row_map.cc b/src/trace_processor/containers/row_map.cc
index b3d1d59..d00d487 100644
--- a/src/trace_processor/containers/row_map.cc
+++ b/src/trace_processor/containers/row_map.cc
@@ -15,6 +15,7 @@
*/
#include "src/trace_processor/containers/row_map.h"
+#include <unordered_set>
#include "src/trace_processor/containers/row_map_algorithms.h"
@@ -23,22 +24,19 @@
namespace {
-RowMap SelectRangeWithRange(uint32_t start,
- uint32_t end,
- uint32_t selector_start,
- uint32_t selector_end) {
- PERFETTO_DCHECK(start <= end);
- PERFETTO_DCHECK(selector_start <= selector_end);
- PERFETTO_DCHECK(selector_end <= end - start);
+using Range = RowMap::Range;
+using OutputIndex = RowMap::OutputIndex;
+using Variant = std::variant<Range, BitVector, std::vector<OutputIndex>>;
- return RowMap(start + selector_start, start + selector_end);
+RowMap Select(Range range, Range selector) {
+ PERFETTO_DCHECK(selector.start <= selector.end);
+ PERFETTO_DCHECK(selector.end <= range.size());
+
+ return RowMap(range.start + selector.start, range.start + selector.end);
}
-RowMap SelectRangeWithBv(uint32_t start,
- uint32_t end,
- const BitVector& selector) {
- PERFETTO_DCHECK(start <= end);
- PERFETTO_DCHECK(selector.size() <= end - start);
+RowMap Select(Range range, const BitVector& selector) {
+ PERFETTO_DCHECK(selector.size() <= range.size());
// If |start| == 0 and |selector.size()| <= |end - start| (which is a
// precondition for this function), the BitVector we generate is going to be
@@ -48,60 +46,52 @@
// SelectRows is called on all the table RowMaps with a BitVector. The self
// RowMap will always be a range so we expect this case to be hit at least
// once every filter operation.
- if (start == 0u)
+ if (range.start == 0u)
return RowMap(selector.Copy());
// We only need to resize to |start| + |selector.size()| as we know any rows
// not covered by |selector| are going to be removed below.
- BitVector bv(start, false);
- bv.Resize(start + selector.size(), true);
+ BitVector bv(range.start, false);
+ bv.Resize(range.start + selector.size(), true);
bv.UpdateSetBits(selector);
return RowMap(std::move(bv));
}
-RowMap SelectRangeWithIv(uint32_t start,
- uint32_t end,
- const std::vector<uint32_t>& selector) {
- PERFETTO_DCHECK(start <= end);
-
+RowMap Select(Range range, const std::vector<OutputIndex>& selector) {
std::vector<uint32_t> iv(selector.size());
for (uint32_t i = 0; i < selector.size(); ++i) {
- PERFETTO_DCHECK(selector[i] < end - start);
- iv[i] = selector[i] + start;
+ PERFETTO_DCHECK(selector[i] < range.size());
+ iv[i] = selector[i] + range.start;
}
return RowMap(std::move(iv));
}
-RowMap SelectBvWithRange(const BitVector& bv,
- uint32_t selector_start,
- uint32_t selector_end) {
- PERFETTO_DCHECK(selector_start <= selector_end);
- PERFETTO_DCHECK(selector_end <= bv.CountSetBits());
+RowMap Select(const BitVector& bv, Range selector) {
+ PERFETTO_DCHECK(selector.end <= bv.CountSetBits());
// If we're simply selecting every element in the bitvector, just
// return a copy of the BitVector without iterating.
BitVector ret = bv.Copy();
- if (selector_start == 0 && selector_end == bv.CountSetBits()) {
+ if (selector.start == 0 && selector.end == bv.CountSetBits()) {
return RowMap(std::move(ret));
}
for (auto it = ret.IterateSetBits(); it; it.Next()) {
auto set_idx = it.ordinal();
- if (set_idx < selector_start || set_idx >= selector_end)
+ if (set_idx < selector.start || set_idx >= selector.end)
it.Clear();
}
return RowMap(std::move(ret));
}
-RowMap SelectBvWithBv(const BitVector& bv, const BitVector& selector) {
+RowMap Select(const BitVector& bv, const BitVector& selector) {
BitVector ret = bv.Copy();
ret.UpdateSetBits(selector);
return RowMap(std::move(ret));
}
-RowMap SelectBvWithIv(const BitVector& bv,
- const std::vector<uint32_t>& selector) {
+RowMap Select(const BitVector& bv, const std::vector<uint32_t>& selector) {
// The value of this constant was found by considering the benchmarks
// |BM_SelectBvWithIvByConvertToIv| and |BM_SelectBvWithIvByIndexOfNthSet|.
//
@@ -130,21 +120,17 @@
row_map_algorithms::SelectBvWithIvByIndexOfNthSet(bv, selector));
}
-RowMap SelectIvWithRange(const std::vector<uint32_t>& iv,
- uint32_t selector_start,
- uint32_t selector_end) {
- PERFETTO_DCHECK(selector_start <= selector_end);
- PERFETTO_DCHECK(selector_end <= iv.size());
+RowMap Select(const std::vector<uint32_t>& iv, Range selector) {
+ PERFETTO_DCHECK(selector.end <= iv.size());
- std::vector<uint32_t> ret(selector_end - selector_start);
- for (uint32_t i = selector_start; i < selector_end; ++i) {
- ret[i - selector_start] = iv[i];
+ std::vector<uint32_t> ret(selector.size());
+ for (uint32_t i = selector.start; i < selector.end; ++i) {
+ ret[i - selector.start] = iv[i];
}
return RowMap(std::move(ret));
}
-RowMap SelectIvWithBv(const std::vector<uint32_t>& iv,
- const BitVector& selector) {
+RowMap Select(const std::vector<uint32_t>& iv, const BitVector& selector) {
PERFETTO_DCHECK(selector.size() <= iv.size());
std::vector<uint32_t> copy = iv;
@@ -158,83 +144,133 @@
return RowMap(std::move(copy));
}
-RowMap SelectIvWithIv(const std::vector<uint32_t>& iv,
- const std::vector<uint32_t>& selector) {
+RowMap Select(const std::vector<uint32_t>& iv,
+ const std::vector<uint32_t>& selector) {
return RowMap(row_map_algorithms::SelectIvWithIv(iv, selector));
}
+Variant IntersectInternal(BitVector& first, const BitVector& second) {
+ for (auto set_bit = first.IterateSetBits(); set_bit; set_bit.Next()) {
+ if (!second.IsSet(set_bit.index()))
+ set_bit.Clear();
+ }
+ return std::move(first);
+}
+
+Variant IntersectInternal(Range first, Range second) {
+ // If both RowMaps have ranges, we can just take the smallest intersection
+ // of them as the new RowMap.
+ // We have this as an explicit fast path as this is very common for
+ // constraints on id and sorted columns to satisfy this condition.
+ OutputIndex start = std::max(first.start, second.start);
+ OutputIndex end = std::max(start, std::min(first.end, second.end));
+ return Range{start, end};
+}
+
+Variant IntersectInternal(std::vector<OutputIndex>& first,
+ const std::vector<OutputIndex>& second) {
+ std::unordered_set<OutputIndex> lookup(second.begin(), second.end());
+ first.erase(std::remove_if(first.begin(), first.end(),
+ [lookup](OutputIndex ind) {
+ return lookup.find(ind) == lookup.end();
+ }),
+ first.end());
+ return std::move(first);
+}
+
+Variant IntersectInternal(Range range, const BitVector& bv) {
+ return bv.IntersectRange(range.start, range.end);
+}
+
+Variant IntersectInternal(BitVector& bv, Range range) {
+ return IntersectInternal(range, bv);
+}
+
+Variant IntersectInternal(const std::vector<OutputIndex>& index_vec,
+ const BitVector& bv) {
+ std::vector<OutputIndex> new_vec(index_vec.begin(), index_vec.end());
+ new_vec.erase(std::remove_if(new_vec.begin(), new_vec.end(),
+ [&bv](uint32_t i) { return !bv.IsSet(i); }),
+ new_vec.end());
+ return std::move(new_vec);
+}
+
+Variant IntersectInternal(const BitVector& bv,
+ const std::vector<OutputIndex>& index_vec) {
+ return IntersectInternal(index_vec, bv);
+}
+
+Variant IntersectInternal(Range range,
+ const std::vector<OutputIndex>& index_vec) {
+ std::vector<OutputIndex> new_vec(index_vec.begin(), index_vec.end());
+ new_vec.erase(std::remove_if(new_vec.begin(), new_vec.end(),
+ [range](uint32_t i) {
+ return i < range.start || i >= range.end;
+ }),
+ new_vec.end());
+ return std::move(new_vec);
+}
+
+Variant IntersectInternal(const std::vector<OutputIndex>& index_vec,
+ Range range) {
+ return IntersectInternal(range, index_vec);
+}
+
} // namespace
-RowMap::RowMap() : RowMap(0, 0) {}
+RowMap::RowMap() : RowMap(Range()) {}
RowMap::RowMap(uint32_t start, uint32_t end, OptimizeFor optimize_for)
- : mode_(Mode::kRange),
- start_index_(start),
- end_index_(end),
- optimize_for_(optimize_for) {}
+ : data_(Range{start, end}), optimize_for_(optimize_for) {}
-RowMap::RowMap(BitVector bit_vector)
- : mode_(Mode::kBitVector), bit_vector_(std::move(bit_vector)) {}
+RowMap::RowMap(Variant def) : data_(std::move(def)) {}
-RowMap::RowMap(std::vector<uint32_t> vec)
- : mode_(Mode::kIndexVector), index_vector_(std::move(vec)) {}
+RowMap::RowMap(Range r) : data_(r) {}
+
+// Creates a RowMap backed by a BitVector.
+RowMap::RowMap(BitVector bit_vector) : data_(std::move(bit_vector)) {}
+
+// Creates a RowMap backed by an std::vector<uint32_t>.
+RowMap::RowMap(IndexVector vec) : data_(vec) {}
RowMap RowMap::Copy() const {
- switch (mode_) {
- case Mode::kRange:
- return RowMap(start_index_, end_index_);
- case Mode::kBitVector:
- return RowMap(bit_vector_.Copy());
- case Mode::kIndexVector:
- return RowMap(index_vector_);
+ if (auto* range = std::get_if<Range>(&data_)) {
+ return RowMap(*range);
}
- PERFETTO_FATAL("For GCC");
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ return RowMap(bv->Copy());
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ return RowMap(*vec);
+ }
+ NoVariantMatched();
}
RowMap RowMap::SelectRowsSlow(const RowMap& selector) const {
- // Pick the strategy based on the selector as there is more common code
- // between selectors of the same mode than between the RowMaps being
- // selected of the same mode.
- switch (selector.mode_) {
- case Mode::kRange:
- switch (mode_) {
- case Mode::kRange:
- return SelectRangeWithRange(start_index_, end_index_,
- selector.start_index_,
- selector.end_index_);
- case Mode::kBitVector:
- return SelectBvWithRange(bit_vector_, selector.start_index_,
- selector.end_index_);
- case Mode::kIndexVector:
- return SelectIvWithRange(index_vector_, selector.start_index_,
- selector.end_index_);
- }
- break;
- case Mode::kBitVector:
- switch (mode_) {
- case Mode::kRange:
- return SelectRangeWithBv(start_index_, end_index_,
- selector.bit_vector_);
- case Mode::kBitVector:
- return SelectBvWithBv(bit_vector_, selector.bit_vector_);
- case Mode::kIndexVector:
- return SelectIvWithBv(index_vector_, selector.bit_vector_);
- }
- break;
- case Mode::kIndexVector:
- switch (mode_) {
- case Mode::kRange:
- return SelectRangeWithIv(start_index_, end_index_,
- selector.index_vector_);
- case Mode::kBitVector:
- return SelectBvWithIv(bit_vector_, selector.index_vector_);
- case Mode::kIndexVector:
- return SelectIvWithIv(index_vector_, selector.index_vector_);
- }
- break;
- }
- PERFETTO_FATAL("For GCC");
+ return std::visit(
+ [](const auto& def, const auto& selector_def) {
+ return Select(def, selector_def);
+ },
+ data_, selector.data_);
}
+void RowMap::Intersect(const RowMap& second) {
+ data_ = std::visit(
+ [](auto& def, auto& selector_def) {
+ return IntersectInternal(def, selector_def);
+ },
+ data_, second.data_);
+}
+
+RowMap::Iterator::Iterator(const RowMap* rm) : rm_(rm) {
+ if (auto* range = std::get_if<Range>(&rm_->data_)) {
+ ordinal_ = range->start;
+ return;
+ }
+ if (auto* bv = std::get_if<BitVector>(&rm_->data_)) {
+ set_bits_it_.reset(new BitVector::SetBitsIterator(bv->IterateSetBits()));
+ return;
+ }
+}
} // namespace trace_processor
} // namespace perfetto
diff --git a/src/trace_processor/containers/row_map.h b/src/trace_processor/containers/row_map.h
index 8ab3915..283455c 100644
--- a/src/trace_processor/containers/row_map.h
+++ b/src/trace_processor/containers/row_map.h
@@ -21,6 +21,7 @@
#include <memory>
#include <optional>
+#include <variant>
#include <vector>
#include "perfetto/base/logging.h"
@@ -73,55 +74,24 @@
// more efficient than a BitVector; in this case, we will make a best effort
// switch to it but the cases where this happens is not precisely defined.
class RowMap {
- private:
- // We need to declare these iterator classes before RowMap::Iterator as it
- // depends on them. However, we don't want to make these public so keep them
- // under a special private section.
-
- // Iterator for ranged mode of RowMap.
- // This class should act as a drop-in replacement for
- // BitVector::SetBitsIterator.
- class RangeIterator {
- public:
- RangeIterator(const RowMap* rm) : rm_(rm), index_(rm->start_index_) {}
-
- void Next() { ++index_; }
-
- operator bool() const { return index_ < rm_->end_index_; }
-
- uint32_t index() const { return index_; }
-
- uint32_t ordinal() const { return index_ - rm_->start_index_; }
-
- private:
- const RowMap* rm_ = nullptr;
- uint32_t index_ = 0;
- };
-
- // Iterator for index vector mode of RowMap.
- // This class should act as a drop-in replacement for
- // BitVector::SetBitsIterator.
- class IndexVectorIterator {
- public:
- IndexVectorIterator(const RowMap* rm) : rm_(rm) {}
-
- void Next() { ++ordinal_; }
-
- operator bool() const { return ordinal_ < rm_->index_vector_.size(); }
-
- uint32_t index() const { return rm_->index_vector_[ordinal_]; }
-
- uint32_t ordinal() const { return ordinal_; }
-
- private:
- const RowMap* rm_ = nullptr;
- uint32_t ordinal_ = 0;
- };
-
public:
- // Input type.
using InputRow = uint32_t;
using OutputIndex = uint32_t;
+ using IndexVector = std::vector<OutputIndex>;
+
+ struct Range {
+ Range(OutputIndex start_index, OutputIndex end_index)
+ : start(start_index), end(end_index) {}
+ Range() : start(0), end(0) {}
+
+ OutputIndex start = 0; // This is an inclusive index.
+ OutputIndex end = 0; // This is an exclusive index.
+
+ uint32_t size() const {
+ PERFETTO_DCHECK(end >= start);
+ return end - start;
+ }
+ };
// Allows efficient iteration over the rows of a RowMap.
//
@@ -130,87 +100,72 @@
// of the RowMap on every method call.
class Iterator {
public:
- Iterator(const RowMap* rm) : rm_(rm) {
- switch (rm->mode_) {
- case Mode::kRange:
- range_it_.reset(new RangeIterator(rm));
- break;
- case Mode::kBitVector:
- set_bits_it_.reset(
- new BitVector::SetBitsIterator(rm->bit_vector_.IterateSetBits()));
- break;
- case Mode::kIndexVector:
- iv_it_.reset(new IndexVectorIterator(rm));
- break;
- }
- }
+ explicit Iterator(const RowMap* rm);
Iterator(Iterator&&) noexcept = default;
Iterator& operator=(Iterator&&) = default;
// Forwards the iterator to the next row of the RowMap.
void Next() {
- switch (rm_->mode_) {
- case Mode::kRange:
- range_it_->Next();
- break;
- case Mode::kBitVector:
- set_bits_it_->Next();
- break;
- case Mode::kIndexVector:
- iv_it_->Next();
- break;
+ if (std::get_if<Range>(&rm_->data_)) {
+ ++ordinal_;
+ } else if (std::get_if<BitVector>(&rm_->data_)) {
+ set_bits_it_->Next();
+ } else if (std::get_if<IndexVector>(&rm_->data_)) {
+ ++ordinal_;
}
}
// Returns if the iterator is still valid.
operator bool() const {
- switch (rm_->mode_) {
- case Mode::kRange:
- return *range_it_;
- case Mode::kBitVector:
- return *set_bits_it_;
- case Mode::kIndexVector:
- return *iv_it_;
+ if (auto* range = std::get_if<Range>(&rm_->data_)) {
+ return ordinal_ < range->end;
}
- PERFETTO_FATAL("For GCC");
+ if (std::get_if<BitVector>(&rm_->data_)) {
+ return bool(*set_bits_it_);
+ }
+ if (auto* vec = std::get_if<IndexVector>(&rm_->data_)) {
+ return ordinal_ < vec->size();
+ }
+ PERFETTO_FATAL("Didn't match any variant type.");
}
// Returns the index pointed to by this iterator.
OutputIndex index() const {
- switch (rm_->mode_) {
- case Mode::kRange:
- return range_it_->index();
- case Mode::kBitVector:
- return set_bits_it_->index();
- case Mode::kIndexVector:
- return iv_it_->index();
+ if (std::get_if<Range>(&rm_->data_)) {
+ return ordinal_;
}
- PERFETTO_FATAL("For GCC");
+ if (std::get_if<BitVector>(&rm_->data_)) {
+ return set_bits_it_->index();
+ }
+ if (auto* vec = std::get_if<IndexVector>(&rm_->data_)) {
+ return (*vec)[ordinal_];
+ }
+ PERFETTO_FATAL("Didn't match any variant type.");
}
// Returns the row of the index the iterator points to.
InputRow row() const {
- switch (rm_->mode_) {
- case Mode::kRange:
- return range_it_->ordinal();
- case Mode::kBitVector:
- return set_bits_it_->ordinal();
- case Mode::kIndexVector:
- return iv_it_->ordinal();
+ if (auto* range = std::get_if<Range>(&rm_->data_)) {
+ return ordinal_ - range->start;
}
- PERFETTO_FATAL("For GCC");
+ if (std::get_if<BitVector>(&rm_->data_)) {
+ return set_bits_it_->ordinal();
+ }
+ if (std::get_if<IndexVector>(&rm_->data_)) {
+ return ordinal_;
+ }
+ PERFETTO_FATAL("Didn't match any variant type.");
}
private:
Iterator(const Iterator&) = delete;
Iterator& operator=(const Iterator&) = delete;
- // Only one of the below will be non-null depending on the mode of the
- // RowMap.
- std::unique_ptr<RangeIterator> range_it_;
+ // Ordinal will not be used for BitVector based RowMap.
+ uint32_t ordinal_ = 0;
+ // Not nullptr for BitVector based RowMap.
std::unique_ptr<BitVector::SetBitsIterator> set_bits_it_;
- std::unique_ptr<IndexVectorIterator> iv_it_;
const RowMap* rm_ = nullptr;
};
@@ -228,15 +183,15 @@
// Creates a RowMap containing the range of indices between |start| and |end|
// i.e. all indices between |start| (inclusive) and |end| (exclusive).
- explicit RowMap(OutputIndex start,
- OutputIndex end,
- OptimizeFor optimize_for = OptimizeFor::kMemory);
+ RowMap(OutputIndex start,
+ OutputIndex end,
+ OptimizeFor optimize_for = OptimizeFor::kMemory);
// Creates a RowMap backed by a BitVector.
- explicit RowMap(BitVector bit_vector);
+ explicit RowMap(BitVector);
// Creates a RowMap backed by an std::vector<uint32_t>.
- explicit RowMap(std::vector<OutputIndex> vec);
+ explicit RowMap(IndexVector);
RowMap(const RowMap&) noexcept = delete;
RowMap& operator=(const RowMap&) = delete;
@@ -259,15 +214,16 @@
// Returns the size of the RowMap; that is the number of indices in the
// RowMap.
uint32_t size() const {
- switch (mode_) {
- case Mode::kRange:
- return end_index_ - start_index_;
- case Mode::kBitVector:
- return bit_vector_.CountSetBits();
- case Mode::kIndexVector:
- return static_cast<uint32_t>(index_vector_.size());
+ if (auto* range = std::get_if<Range>(&data_)) {
+ return range->size();
}
- PERFETTO_FATAL("For GCC");
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ return bv->CountSetBits();
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ return static_cast<uint32_t>(vec->size());
+ }
+ NoVariantMatched();
}
// Returns whether this rowmap is empty.
@@ -275,57 +231,51 @@
// Returns the index at the given |row|.
OutputIndex Get(InputRow row) const {
- PERFETTO_DCHECK(row < size());
- switch (mode_) {
- case Mode::kRange:
- return GetRange(row);
- case Mode::kBitVector:
- return GetBitVector(row);
- case Mode::kIndexVector:
- return GetIndexVector(row);
+ if (auto* range = std::get_if<Range>(&data_)) {
+ return GetRange(*range, row);
}
- PERFETTO_FATAL("For GCC");
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ return GetBitVector(*bv, row);
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ return GetIndexVector(*vec, row);
+ }
+ NoVariantMatched();
}
// Returns whether the RowMap contains the given index.
bool Contains(OutputIndex index) const {
- switch (mode_) {
- case Mode::kRange: {
- return index >= start_index_ && index < end_index_;
- }
- case Mode::kBitVector: {
- return index < bit_vector_.size() && bit_vector_.IsSet(index);
- }
- case Mode::kIndexVector: {
- auto it = std::find(index_vector_.begin(), index_vector_.end(), index);
- return it != index_vector_.end();
- }
+ if (auto* range = std::get_if<Range>(&data_)) {
+ return index >= range->start && index < range->end;
}
- PERFETTO_FATAL("For GCC");
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ return index < bv->size() && bv->IsSet(index);
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ return std::find(vec->begin(), vec->end(), index) != vec->end();
+ }
+ NoVariantMatched();
}
// Returns the first row of the given |index| in the RowMap.
std::optional<InputRow> RowOf(OutputIndex index) const {
- switch (mode_) {
- case Mode::kRange: {
- if (index < start_index_ || index >= end_index_)
- return std::nullopt;
- return index - start_index_;
- }
- case Mode::kBitVector: {
- return index < bit_vector_.size() && bit_vector_.IsSet(index)
- ? std::make_optional(bit_vector_.CountSetBits(index))
- : std::nullopt;
- }
- case Mode::kIndexVector: {
- auto it = std::find(index_vector_.begin(), index_vector_.end(), index);
- return it != index_vector_.end()
- ? std::make_optional(static_cast<InputRow>(
- std::distance(index_vector_.begin(), it)))
- : std::nullopt;
- }
+ if (auto* range = std::get_if<Range>(&data_)) {
+ if (index < range->start || index >= range->end)
+ return std::nullopt;
+ return index - range->start;
}
- PERFETTO_FATAL("For GCC");
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ return index < bv->size() && bv->IsSet(index)
+ ? std::make_optional(bv->CountSetBits(index))
+ : std::nullopt;
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ auto it = std::find(vec->begin(), vec->end(), index);
+ return it != vec->end() ? std::make_optional(static_cast<InputRow>(
+ std::distance(vec->begin(), it)))
+ : std::nullopt;
+ }
+ NoVariantMatched();
}
// Performs an ordered insert of the index into the current RowMap
@@ -343,34 +293,36 @@
// the RowMap is in range or BitVector mode but is a required condition for
// IndexVector mode.
void Insert(OutputIndex index) {
- switch (mode_) {
- case Mode::kRange:
- if (index == end_index_) {
- // Fast path: if we're just appending to the end of the range, we can
- // stay in range mode and just bump the end index.
- end_index_++;
- } else {
- // Slow path: the insert is somewhere else other than the end. This
- // means we need to switch to using a BitVector instead.
- bit_vector_.Resize(start_index_, false);
- bit_vector_.Resize(end_index_, true);
- *this = RowMap(std::move(bit_vector_));
-
- InsertIntoBitVector(index);
- }
- break;
- case Mode::kBitVector:
- InsertIntoBitVector(index);
- break;
- case Mode::kIndexVector: {
- PERFETTO_DCHECK(
- std::is_sorted(index_vector_.begin(), index_vector_.end()));
- auto it =
- std::upper_bound(index_vector_.begin(), index_vector_.end(), index);
- index_vector_.insert(it, index);
- break;
+ if (auto* range = std::get_if<Range>(&data_)) {
+ if (index == range->end) {
+ // Fast path: if we're just appending to the end
+ // of the range, we can stay in range mode and
+ // just bump the end index.
+ range->end++;
+ return;
}
+
+ // Slow path: the insert is somewhere else other
+ // than the end. This means we need to switch to
+ // using a BitVector instead.
+ BitVector bv;
+ bv.Resize(range->start, false);
+ bv.Resize(range->end, true);
+ InsertIntoBitVector(bv, index);
+ data_ = std::move(bv);
+ return;
}
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ InsertIntoBitVector(*bv, index);
+ return;
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ PERFETTO_DCHECK(std::is_sorted(vec->begin(), vec->end()));
+ auto it = std::upper_bound(vec->begin(), vec->end(), index);
+ vec->insert(it, index);
+ return;
+ }
+ NoVariantMatched();
}
// Updates this RowMap by 'picking' the indices given by |picker|.
@@ -413,22 +365,7 @@
// if (start_index <= idx && idx < end_index)
// continue;
// Remove(idx)
- void Intersect(uint32_t start_index, uint32_t end_index) {
- if (mode_ == Mode::kRange) {
- // If both RowMaps have ranges, we can just take the smallest intersection
- // of them as the new RowMap.
- // We have this as an explicit fast path as this is very common for
- // constraints on id and sorted columns to satisfy this condition.
- start_index_ = std::max(start_index_, start_index);
- end_index_ = std::max(start_index_, std::min(end_index_, end_index));
- return;
- }
-
- // TODO(lalitm): improve efficiency of this if we end up needing it.
- Filter([start_index, end_index](OutputIndex index) {
- return index >= start_index && index < end_index;
- });
- }
+ void Intersect(const RowMap& second);
// Intersects this RowMap with |index|. If this RowMap contained |index|, then
// it will *only* contain |index|. Otherwise, it will be empty.
@@ -444,71 +381,82 @@
void Clear() { *this = RowMap(); }
template <typename Comparator = bool(uint32_t, uint32_t)>
- void StableSort(std::vector<uint32_t>* out, Comparator c) const {
- switch (mode_) {
- case Mode::kRange:
- std::stable_sort(out->begin(), out->end(),
- [this, c](uint32_t a, uint32_t b) {
- return c(GetRange(a), GetRange(b));
- });
- break;
- case Mode::kBitVector:
- std::stable_sort(out->begin(), out->end(),
- [this, c](uint32_t a, uint32_t b) {
- return c(GetBitVector(a), GetBitVector(b));
- });
- break;
- case Mode::kIndexVector:
- std::stable_sort(out->begin(), out->end(),
- [this, c](uint32_t a, uint32_t b) {
- return c(GetIndexVector(a), GetIndexVector(b));
- });
- break;
+ void StableSort(IndexVector* out, Comparator c) const {
+ if (auto* range = std::get_if<Range>(&data_)) {
+ std::stable_sort(out->begin(), out->end(),
+ [range, c](uint32_t a, uint32_t b) {
+ return c(GetRange(*range, a), GetRange(*range, b));
+ });
+ return;
}
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ std::stable_sort(out->begin(), out->end(),
+ [&bv, c](uint32_t a, uint32_t b) {
+ return c(GetBitVector(*bv, a), GetBitVector(*bv, b));
+ });
+ return;
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ std::stable_sort(
+ out->begin(), out->end(), [vec, c](uint32_t a, uint32_t b) {
+ return c(GetIndexVector(*vec, a), GetIndexVector(*vec, b));
+ });
+ return;
+ }
+ NoVariantMatched();
}
// Filters the indices in |out| by keeping those which meet |p|.
template <typename Predicate = bool(OutputIndex)>
void Filter(Predicate p) {
- switch (mode_) {
- case Mode::kRange:
- FilterRange(p);
- break;
- case Mode::kBitVector: {
- for (auto it = bit_vector_.IterateSetBits(); it; it.Next()) {
- if (!p(it.index()))
- it.Clear();
- }
- break;
- }
- case Mode::kIndexVector: {
- auto ret = std::remove_if(index_vector_.begin(), index_vector_.end(),
- [p](uint32_t i) { return !p(i); });
- index_vector_.erase(ret, index_vector_.end());
- break;
- }
+ if (auto* range = std::get_if<Range>(&data_)) {
+ data_ = FilterRange(p, *range);
+ return;
}
+ if (auto* bv = std::get_if<BitVector>(&data_)) {
+ for (auto it = bv->IterateSetBits(); it; it.Next()) {
+ if (!p(it.index()))
+ it.Clear();
+ }
+ return;
+ }
+ if (auto* vec = std::get_if<IndexVector>(&data_)) {
+ auto ret = std::remove_if(vec->begin(), vec->end(),
+ [p](uint32_t i) { return !p(i); });
+ vec->erase(ret, vec->end());
+ return;
+ }
+ NoVariantMatched();
}
// Returns the iterator over the rows in this RowMap.
Iterator IterateRows() const { return Iterator(this); }
// Returns if the RowMap is internally represented using a range.
- bool IsRange() const { return mode_ == Mode::kRange; }
+ bool IsRange() const { return std::holds_alternative<Range>(data_); }
+
+ // Returns if the RowMap is internally represented using a BitVector.
+ bool IsBitVector() const { return std::holds_alternative<BitVector>(data_); }
+
+ // Returns if the RowMap is internally represented using an index vector.
+ bool IsIndexVector() const {
+ return std::holds_alternative<IndexVector>(data_);
+ }
private:
- enum class Mode {
- kRange,
- kBitVector,
- kIndexVector,
- };
+ using Variant = std::variant<Range, BitVector, IndexVector>;
+
+ explicit RowMap(Range);
+
+ explicit RowMap(Variant);
+
// TODO(lalitm): remove this when the coupling between RowMap and
// ColumnStorage Selector is broken (after filtering is moved out of here).
friend class ColumnStorageOverlay;
template <typename Predicate>
- void FilterRange(Predicate p) {
- uint32_t count = end_index_ - start_index_;
+ Variant FilterRange(Predicate p, Range r) {
+ uint32_t count = r.size();
// Optimization: if we are only going to scan a few indices, it's not
// worth the haslle of working with a BitVector.
@@ -517,7 +465,7 @@
// Optimization: weif the cost of a BitVector is more than the highest
// possible cost an index vector could have, use the index vector.
- uint32_t bit_vector_cost = BitVector::ApproxBytesCost(end_index_);
+ uint32_t bit_vector_cost = BitVector::ApproxBytesCost(r.end);
uint32_t index_vector_cost_ub = sizeof(uint32_t) * count;
// If either of the conditions hold which make it better to use an
@@ -527,7 +475,7 @@
optimize_for_ == OptimizeFor::kLookupSpeed) {
// Try and strike a good balance between not making the vector too
// big and good performance.
- std::vector<uint32_t> iv(std::min(kSmallRangeLimit, count));
+ IndexVector iv(std::min(kSmallRangeLimit, count));
uint32_t out_i = 0;
for (uint32_t i = 0; i < count; ++i) {
@@ -537,8 +485,8 @@
// We keep this branch free by always writing the index but only
// incrementing the out index if the return value is true.
- bool value = p(i + start_index_);
- iv[out_i] = i + start_index_;
+ bool value = p(i + r.start);
+ iv[out_i] = i + r.start;
out_i += value;
}
@@ -546,58 +494,44 @@
iv.resize(out_i);
iv.shrink_to_fit();
- *this = RowMap(std::move(iv));
- return;
+ return std::move(iv);
}
// Otherwise, create a bitvector which spans the full range using
// |p| as the filler for the bits between start and end.
- *this = RowMap(BitVector::Range(start_index_, end_index_, p));
+ return BitVector::Range(r.start, r.end, p);
}
- void InsertIntoBitVector(uint32_t row) {
- PERFETTO_DCHECK(mode_ == Mode::kBitVector);
-
- // If we're adding a row to precisely the end of the BitVector, just append
- // true instead of resizing and then setting.
- if (row == bit_vector_.size()) {
- bit_vector_.AppendTrue();
- return;
- }
-
- if (row > bit_vector_.size()) {
- bit_vector_.Resize(row + 1, false);
- }
- bit_vector_.Set(row);
+ PERFETTO_ALWAYS_INLINE static OutputIndex GetRange(Range r, InputRow row) {
+ return r.start + row;
}
-
- PERFETTO_ALWAYS_INLINE OutputIndex GetRange(InputRow row) const {
- PERFETTO_DCHECK(mode_ == Mode::kRange);
- return start_index_ + row;
+ PERFETTO_ALWAYS_INLINE static OutputIndex GetBitVector(const BitVector& bv,
+ uint32_t row) {
+ return bv.IndexOfNthSet(row);
}
- PERFETTO_ALWAYS_INLINE OutputIndex GetBitVector(uint32_t row) const {
- PERFETTO_DCHECK(mode_ == Mode::kBitVector);
- return bit_vector_.IndexOfNthSet(row);
- }
- PERFETTO_ALWAYS_INLINE OutputIndex GetIndexVector(uint32_t row) const {
- PERFETTO_DCHECK(mode_ == Mode::kIndexVector);
- return index_vector_[row];
+ PERFETTO_ALWAYS_INLINE static OutputIndex GetIndexVector(
+ const IndexVector& vec,
+ uint32_t row) {
+ return vec[row];
}
RowMap SelectRowsSlow(const RowMap& selector) const;
- Mode mode_ = Mode::kRange;
+ static void InsertIntoBitVector(BitVector& bv, OutputIndex row) {
+ if (row == bv.size()) {
+ bv.AppendTrue();
+ return;
+ }
+ if (row > bv.size())
+ bv.Resize(row + 1, false);
+ bv.Set(row);
+ }
- // Only valid when |mode_| == Mode::kRange.
- OutputIndex start_index_ = 0; // This is an inclusive index.
- OutputIndex end_index_ = 0; // This is an exclusive index.
+ PERFETTO_NORETURN void NoVariantMatched() const {
+ PERFETTO_FATAL("Didn't match any variant type.");
+ }
- // Only valid when |mode_| == Mode::kBitVector.
- BitVector bit_vector_;
-
- // Only valid when |mode_| == Mode::kIndexVector.
- std::vector<OutputIndex> index_vector_;
-
+ Variant data_;
OptimizeFor optimize_for_ = OptimizeFor::kMemory;
};
diff --git a/src/trace_processor/containers/row_map_unittest.cc b/src/trace_processor/containers/row_map_unittest.cc
index 6e1ca11..7f919bd 100644
--- a/src/trace_processor/containers/row_map_unittest.cc
+++ b/src/trace_processor/containers/row_map_unittest.cc
@@ -25,6 +25,191 @@
namespace trace_processor {
namespace {
+TEST(RowMapUnittest, SingleRow) {
+ RowMap rm(10, 20);
+ RowMap rm_row = rm.SingleRow(15u);
+ ASSERT_EQ(rm_row.size(), 1u);
+ ASSERT_TRUE(rm_row.Contains(15));
+ ASSERT_FALSE(rm_row.Contains(11));
+}
+
+TEST(RowMapUnittest, CopyRange) {
+ RowMap rm(10, 20);
+ RowMap rm_copy = rm.Copy();
+ ASSERT_EQ(rm_copy.size(), 10u);
+}
+
+TEST(RowMapUnittest, CopyBitVector) {
+ RowMap rm(BitVector{true, false, false, false, true, true});
+ RowMap rm_copy = rm.Copy();
+ ASSERT_EQ(rm_copy.size(), 3u);
+}
+
+TEST(RowMapUnittest, CopyIndexVector) {
+ RowMap rm(std::vector<uint32_t>{10, 17, 20, 21});
+ RowMap rm_copy = rm.Copy();
+ ASSERT_EQ(rm_copy.size(), 4u);
+}
+
+TEST(RowMapUnittest, GetFromRange) {
+ RowMap rm(10, 20);
+ ASSERT_EQ(rm.Get(5), 15u);
+}
+
+TEST(RowMapUnittest, GetFromBitVector) {
+ RowMap rm(BitVector{true, false, false, false, true, true});
+ ASSERT_EQ(rm.Get(1), 4u);
+}
+
+TEST(RowMapUnittest, GetFromIndexVector) {
+ RowMap rm(std::vector<uint32_t>{10, 17, 20, 21});
+ ASSERT_EQ(rm.Get(1), 17u);
+}
+
+TEST(RowMapUnittest, ContainsFromRange) {
+ RowMap rm(10, 20);
+ ASSERT_FALSE(rm.Contains(5));
+ ASSERT_TRUE(rm.Contains(15));
+}
+
+TEST(RowMapUnittest, ContainsFromBitVector) {
+ RowMap rm(BitVector{true, false, false, false, true, true});
+ ASSERT_FALSE(rm.Contains(3));
+ ASSERT_TRUE(rm.Contains(5));
+}
+
+TEST(RowMapUnittest, ContainsFromIndexVector) {
+ RowMap rm(std::vector<uint32_t>{10, 17, 20, 21});
+ ASSERT_FALSE(rm.Contains(5));
+ ASSERT_TRUE(rm.Contains(10));
+}
+
+TEST(RowMapUnittest, RowOfRange) {
+ RowMap rm(10, 20);
+ ASSERT_EQ(rm.RowOf(15).value(), 5u);
+ ASSERT_EQ(rm.RowOf(5), std::nullopt);
+}
+
+TEST(RowMapUnittest, RowOfBitVector) {
+ RowMap rm(BitVector{true, false, false, false, true, true});
+ ASSERT_EQ(rm.RowOf(4), 1u);
+ ASSERT_EQ(rm.RowOf(1), std::nullopt);
+}
+
+TEST(RowMapUnittest, RowOfIndexVector) {
+ RowMap rm(std::vector<uint32_t>{10, 17, 20, 21});
+ ASSERT_EQ(rm.RowOf(17), 1u);
+ ASSERT_EQ(rm.RowOf(5), std::nullopt);
+}
+
+TEST(RowMapUnittest, InsertIntoRangeAtTheEnd) {
+ RowMap rm(10, 20);
+ rm.Insert(21);
+ ASSERT_EQ(rm.size(), 11u);
+ ASSERT_TRUE(rm.Contains(21));
+}
+
+TEST(RowMapUnittest, InsertIntoRange) {
+ RowMap rm(10, 20);
+ rm.Insert(25);
+ ASSERT_EQ(rm.size(), 11u);
+ ASSERT_TRUE(rm.Contains(25));
+}
+
+TEST(RowMapUnittest, InsertIntoBitVector) {
+ RowMap rm(BitVector{true, false, false, false, true, true});
+ rm.Insert(25);
+ ASSERT_EQ(rm.size(), 4u);
+ ASSERT_TRUE(rm.Contains(25));
+}
+
+TEST(RowMapUnittest, InsertIntoIndexVector) {
+ RowMap rm(std::vector<uint32_t>{10, 17, 20, 21});
+ rm.Insert(25);
+ ASSERT_EQ(rm.size(), 5u);
+ ASSERT_TRUE(rm.Contains(25));
+}
+
+TEST(RowMapUnittest, SelectRowsFromRangeWithRange) {
+ RowMap rm(10, 20);
+
+ RowMap selector(4, 8);
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 4u);
+ ASSERT_EQ(selected.Get(0), 14u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromRangeWithBV) {
+ RowMap rm(10, 20);
+ // BitVector with values at 16, 18, 20 and so on.
+ RowMap selector(
+ BitVector::Range(4, 8, [](uint32_t x) { return x % 2 == 0; }));
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 2u);
+ ASSERT_EQ(selected.Get(0), 14u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromRangeWithIV) {
+ RowMap rm(10, 20);
+ RowMap selector(std::vector<uint32_t>{4, 6});
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 2u);
+ ASSERT_EQ(selected.Get(0), 14u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromBVWithRange) {
+ RowMap rm(BitVector::Range(10, 50, [](uint32_t x) { return x % 2 == 0; }));
+
+ RowMap selector(4, 8);
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 4u);
+ ASSERT_EQ(selected.Get(0), 18u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromBVWithBV) {
+ RowMap rm(BitVector::Range(10, 50, [](uint32_t x) { return x % 2 == 0; }));
+ // BitVector with values at 16, 18, 20 and so on.
+ RowMap selector(
+ BitVector::Range(4, 8, [](uint32_t x) { return x % 2 == 0; }));
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 2u);
+ ASSERT_EQ(selected.Get(0), 18u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromBVWithIV) {
+ RowMap rm(BitVector::Range(10, 50, [](uint32_t x) { return x % 2 == 0; }));
+ RowMap selector(std::vector<uint32_t>{4, 6});
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 2u);
+ ASSERT_EQ(selected.Get(0), 18u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromIVWithRange) {
+ RowMap rm(std::vector<uint32_t>{10, 12, 14, 16, 18, 20, 22, 24});
+
+ RowMap selector(4, 8);
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 4u);
+ ASSERT_EQ(selected.Get(0), 18u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromIVWithBV) {
+ RowMap rm(std::vector<uint32_t>{10, 12, 14, 16, 18, 20, 22, 24});
+ RowMap selector(
+ BitVector::Range(4, 8, [](uint32_t x) { return x % 2 == 0; }));
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 2u);
+ ASSERT_EQ(selected.Get(0), 18u);
+}
+
+TEST(RowMapUnittest, SelectRowsFromIVWithIV) {
+ RowMap rm(std::vector<uint32_t>{10, 12, 14, 16, 18, 20, 22, 24});
+ RowMap selector(std::vector<uint32_t>{4, 6});
+ RowMap selected = rm.SelectRows(selector);
+ ASSERT_EQ(selected.size(), 2u);
+ ASSERT_EQ(selected.Get(0), 18u);
+}
+
TEST(RowMapUnittest, SmokeRange) {
RowMap rm(30, 47);
@@ -327,22 +512,86 @@
ASSERT_EQ(rm.size(), 0u);
}
-TEST(RowMapUnittest, IntersectManyRange) {
+TEST(RowMapUnittest, IntersectRangeWithRange) {
RowMap rm(3, 7);
- rm.Intersect(2, 4);
+ RowMap sec(2, 4);
+ rm.Intersect(sec);
ASSERT_EQ(rm.size(), 1u);
ASSERT_EQ(rm.Get(0u), 3u);
}
-TEST(RowMapUnittest, IntersectManyIv) {
- RowMap rm(std::vector<uint32_t>{3u, 2u, 0u, 1u, 1u, 3u});
- rm.Intersect(2, 4);
+TEST(RowMapUnittest, IntersectRangeWithBV) {
+ RowMap rm(2, 4);
+ RowMap sec(BitVector{true, false, true, true, false, true});
+ rm.Intersect(sec);
+
+ ASSERT_EQ(rm.size(), 2u);
+ ASSERT_EQ(rm.Get(0), 2u);
+}
+
+TEST(RowMapUnittest, IntersectRangeWithIV) {
+ RowMap rm(2, 10);
+ RowMap sec(std::vector<uint32_t>{0, 2, 5});
+ rm.Intersect(sec);
+
+ ASSERT_EQ(rm.size(), 2u);
+ ASSERT_EQ(rm.Get(0u), 2u);
+}
+
+TEST(RowMapUnittest, IntersectBVWithRange) {
+ RowMap rm(BitVector{true, false, true, true, false, true});
+ RowMap sec(2, 4);
+ rm.Intersect(sec);
+
+ ASSERT_EQ(rm.size(), 2u);
+ ASSERT_EQ(rm.Get(0), 2u);
+}
+
+TEST(RowMapUnittest, IntersectBVWithBV) {
+ RowMap rm(BitVector{true, false, true, true, false, true});
+ RowMap sec(BitVector{false, true, true, false, false, true, true});
+ rm.Intersect(sec);
+
+ ASSERT_EQ(rm.size(), 2u);
+ ASSERT_EQ(rm.Get(0), 2u);
+}
+
+TEST(RowMapUnittest, IntersectBVWithIV) {
+ RowMap rm(BitVector{true, false, true, true, false, true});
+ RowMap sec(std::vector<uint32_t>{0, 2, 5});
+ rm.Intersect(sec);
ASSERT_EQ(rm.size(), 3u);
- ASSERT_EQ(rm.Get(0u), 3u);
- ASSERT_EQ(rm.Get(1u), 2u);
- ASSERT_EQ(rm.Get(2u), 3u);
+ ASSERT_EQ(rm.Get(0), 0u);
+}
+
+TEST(RowMapUnittest, IntersectIVWithRange) {
+ RowMap rm(std::vector<uint32_t>{0, 2, 5});
+ RowMap sec(2, 10);
+ rm.Intersect(sec);
+
+ ASSERT_EQ(rm.size(), 2u);
+ ASSERT_EQ(rm.Get(0u), 2u);
+}
+
+TEST(RowMapUnittest, IntersectIVWithBV) {
+ RowMap rm(std::vector<uint32_t>{0, 2, 5});
+ RowMap sec(BitVector{true, false, true, true, false, true});
+ rm.Intersect(sec);
+
+ ASSERT_EQ(rm.size(), 3u);
+ ASSERT_EQ(rm.Get(0), 0u);
+}
+
+TEST(RowMapUnittest, IntersectIVWithIV) {
+ RowMap rm(std::vector<uint32_t>{0, 2, 5});
+ RowMap sec(std::vector<uint32_t>{1, 2, 6});
+
+ rm.Intersect(sec);
+
+ ASSERT_EQ(rm.size(), 1u);
+ ASSERT_EQ(rm.Get(0u), 2u);
}
} // namespace
diff --git a/src/trace_processor/db/column.h b/src/trace_processor/db/column.h
index 04425b9..a97d6e4 100644
--- a/src/trace_processor/db/column.h
+++ b/src/trace_processor/db/column.h
@@ -545,31 +545,31 @@
b, std::lower_bound(b, e, value, &compare::SqlValueComparator));
uint32_t end = std::distance(
b, std::upper_bound(b, e, value, &compare::SqlValueComparator));
- rm->Intersect(beg, end);
+ rm->Intersect({beg, end});
return true;
}
case FilterOp::kLe: {
uint32_t end = std::distance(
b, std::upper_bound(b, e, value, &compare::SqlValueComparator));
- rm->Intersect(0, end);
+ rm->Intersect({0, end});
return true;
}
case FilterOp::kLt: {
uint32_t end = std::distance(
b, std::lower_bound(b, e, value, &compare::SqlValueComparator));
- rm->Intersect(0, end);
+ rm->Intersect({0, end});
return true;
}
case FilterOp::kGe: {
uint32_t beg = std::distance(
b, std::lower_bound(b, e, value, &compare::SqlValueComparator));
- rm->Intersect(beg, overlay().size());
+ rm->Intersect({beg, overlay().size()});
return true;
}
case FilterOp::kGt: {
uint32_t beg = std::distance(
b, std::upper_bound(b, e, value, &compare::SqlValueComparator));
- rm->Intersect(beg, overlay().size());
+ rm->Intersect({beg, overlay().size()});
return true;
}
case FilterOp::kNe:
@@ -608,11 +608,13 @@
// Otherwise, find the end of the set and return the intersection for this.
for (uint32_t i = set_id + 1; i < ov.size(); ++i) {
if (st.Get(ov.Get(i)) != filter_set_id) {
- rm->Intersect(set_id, i);
+ RowMap r(set_id, i);
+ rm->Intersect(r);
return;
}
}
- rm->Intersect(set_id, ov.size());
+ RowMap r(set_id, ov.size());
+ rm->Intersect(r);
}
// Slow path filter method which will perform a full table scan.
diff --git a/src/trace_processor/db/column_storage_overlay.h b/src/trace_processor/db/column_storage_overlay.h
index 108dccd..997d4be 100644
--- a/src/trace_processor/db/column_storage_overlay.h
+++ b/src/trace_processor/db/column_storage_overlay.h
@@ -183,24 +183,12 @@
// meet |p|. However, if |this| is a BitVector, we end up needing expensive
// |IndexOfNthSet| calls (as we need to convert the row to an index before
// passing it to |p|).
- switch (row_map_.mode_) {
- case RowMap::Mode::kRange: {
- auto ip = [this, p](uint32_t row) { return p(row_map_.GetRange(row)); };
- out->Filter(ip);
- break;
- }
- case RowMap::Mode::kBitVector: {
- FilterIntoScanSelfBv(out, p);
- break;
- }
- case RowMap::Mode::kIndexVector: {
- auto ip = [this, p](uint32_t row) {
- return p(row_map_.GetIndexVector(row));
- };
- out->Filter(ip);
- break;
- }
+ if (row_map_.IsBitVector()) {
+ FilterIntoScanSelfBv(out, p);
+ return;
}
+ auto ip = [this, p](uint32_t row) { return p(row_map_.Get(row)); };
+ out->Filter(ip);
}
template <typename Comparator = bool(uint32_t, uint32_t)>
@@ -217,54 +205,57 @@
// Filters the current ColumnStorageOverlay into |out| by performing a full
// scan on |row_map.bit_vector_|. See |FilterInto| for a full breakdown of the
// semantics of this function.
- template <typename Predicate>
- void FilterIntoScanSelfBv(RowMap* out, Predicate p) const {
- auto it = row_map_.bit_vector_.IterateSetBits();
- switch (out->mode_) {
- case RowMap::Mode::kRange: {
- // TODO(lalitm): investigate whether we can reuse the data inside
- // out->bit_vector_ at some point.
- BitVector bv(out->end_index_, false);
- for (auto out_it = bv.IterateAllBits(); it; it.Next(), out_it.Next()) {
- uint32_t ordinal = it.ordinal();
- if (ordinal < out->start_index_)
- continue;
- if (ordinal >= out->end_index_)
- break;
- if (p(it.index())) {
- out_it.Set();
- }
+ template <typename Predicate>
+ struct FilterIntoScanSelfBvVisitor {
+ void operator()(RowMap::Range out_r) {
+ BitVector bv(out_r.end, false);
+ for (auto out_it = bv.IterateAllBits(); bv_iter;
+ bv_iter.Next(), out_it.Next()) {
+ uint32_t ordinal = bv_iter.ordinal();
+ if (ordinal < out_r.start)
+ continue;
+ if (ordinal >= out_r.end)
+ break;
+
+ if (p(bv_iter.index())) {
+ out_it.Set();
}
- *out = RowMap(std::move(bv));
- break;
}
- case RowMap::Mode::kBitVector: {
- auto out_it = out->bit_vector_.IterateAllBits();
- for (; out_it; it.Next(), out_it.Next()) {
- PERFETTO_DCHECK(it);
- if (out_it.IsSet() && !p(it.index()))
- out_it.Clear();
- }
- break;
- }
- case RowMap::Mode::kIndexVector: {
- PERFETTO_DCHECK(std::is_sorted(out->index_vector_.begin(),
- out->index_vector_.end()));
- auto fn = [&p, &it](uint32_t i) {
- while (it.ordinal() < i) {
- it.Next();
- PERFETTO_DCHECK(it);
- }
- PERFETTO_DCHECK(it.ordinal() == i);
- return !p(it.index());
- };
- auto iv_it = std::remove_if(out->index_vector_.begin(),
- out->index_vector_.end(), fn);
- out->index_vector_.erase(iv_it, out->index_vector_.end());
- break;
+ *out = RowMap(std::move(bv));
+ }
+ void operator()(const BitVector& out_bv) {
+ auto out_it = out_bv.IterateAllBits();
+ for (; out_it; bv_iter.Next(), out_it.Next()) {
+ PERFETTO_DCHECK(bv_iter);
+ if (out_it.IsSet() && !p(bv_iter.index()))
+ out_it.Clear();
}
}
+ void operator()(std::vector<OutputIndex>& out_vec) {
+ PERFETTO_DCHECK(std::is_sorted(out_vec.begin(), out_vec.end()));
+ auto fn = [this](uint32_t i) {
+ while (bv_iter.ordinal() < i) {
+ bv_iter.Next();
+ PERFETTO_DCHECK(bv_iter);
+ }
+ PERFETTO_DCHECK(bv_iter.ordinal() == i);
+ return !p(bv_iter.index());
+ };
+ auto iv_it = std::remove_if(out_vec.begin(), out_vec.end(), fn);
+ out_vec.erase(iv_it, out_vec.end());
+ }
+ RowMap* out;
+ Predicate p;
+ internal::SetBitsIterator bv_iter;
+ };
+
+ template <typename Predicate>
+ void FilterIntoScanSelfBv(RowMap* out, Predicate p) const {
+ const BitVector* bv = std::get_if<BitVector>(&row_map_.data_);
+ auto it = bv->IterateSetBits();
+ std::visit(FilterIntoScanSelfBvVisitor<Predicate>{out, p, std::move(it)},
+ out->data_);
}
RowMap row_map_;
