Merge "trace_processor: add all bits iterator"
diff --git a/Android.bp b/Android.bp
index 679b438..52e65e5 100644
--- a/Android.bp
+++ b/Android.bp
@@ -4514,6 +4514,7 @@
name: "perfetto_src_trace_processor_db_lib",
srcs: [
"src/trace_processor/db/bit_vector.cc",
+ "src/trace_processor/db/bit_vector_iterators.cc",
"src/trace_processor/db/column.cc",
"src/trace_processor/db/row_map.cc",
"src/trace_processor/db/table.cc",
diff --git a/BUILD b/BUILD
index 4063dd8..74e1390 100644
--- a/BUILD
+++ b/BUILD
@@ -516,6 +516,8 @@
srcs = [
"src/trace_processor/db/bit_vector.cc",
"src/trace_processor/db/bit_vector.h",
+ "src/trace_processor/db/bit_vector_iterators.cc",
+ "src/trace_processor/db/bit_vector_iterators.h",
"src/trace_processor/db/column.cc",
"src/trace_processor/db/column.h",
"src/trace_processor/db/row_map.cc",
diff --git a/src/trace_processor/db/BUILD.gn b/src/trace_processor/db/BUILD.gn
index 7360779..57366d2 100644
--- a/src/trace_processor/db/BUILD.gn
+++ b/src/trace_processor/db/BUILD.gn
@@ -18,6 +18,8 @@
sources = [
"bit_vector.cc",
"bit_vector.h",
+ "bit_vector_iterators.cc",
+ "bit_vector_iterators.h",
"column.cc",
"column.h",
"row_map.cc",
diff --git a/src/trace_processor/db/bit_vector.cc b/src/trace_processor/db/bit_vector.cc
index edf1af6..2845a50 100644
--- a/src/trace_processor/db/bit_vector.cc
+++ b/src/trace_processor/db/bit_vector.cc
@@ -16,6 +16,8 @@
#include "src/trace_processor/db/bit_vector.h"
+#include "src/trace_processor/db/bit_vector_iterators.h"
+
namespace perfetto {
namespace trace_processor {
@@ -34,5 +36,25 @@
return BitVector(blocks_, counts_, size_);
}
+BitVector::AllBitsIterator BitVector::IterateAllBits() const {
+ return AllBitsIterator(this);
+}
+
+void BitVector::UpdateSetBits(const BitVector& other) {
+ PERFETTO_DCHECK(other.size() == GetNumBitsSet());
+
+ // Go through each set bit and if |other| has it unset, then unset the
+ // bit taking care to update the index we consider to take into account
+ // the bits we just unset.
+ // TODO(lalitm): we add a set bits iterator implementation to remove this
+ // inefficient loop.
+ uint32_t removed = 0;
+ for (auto it = other.IterateAllBits(); it; it.Next()) {
+ if (!it.IsSet()) {
+ Clear(IndexOfNthSet(it.index() - removed++));
+ }
+ }
+}
+
} // namespace trace_processor
} // namespace perfetto
diff --git a/src/trace_processor/db/bit_vector.h b/src/trace_processor/db/bit_vector.h
index df49156..8993b22 100644
--- a/src/trace_processor/db/bit_vector.h
+++ b/src/trace_processor/db/bit_vector.h
@@ -30,10 +30,19 @@
namespace perfetto {
namespace trace_processor {
+namespace internal {
+
+class BaseIterator;
+class AllBitsIterator;
+
+} // namespace internal
+
// A bitvector which compactly stores a vector of bools using a single bit
// for each bool.
class BitVector {
public:
+ using AllBitsIterator = internal::AllBitsIterator;
+
// Creates an empty bitvector.
BitVector();
@@ -265,23 +274,20 @@
// This will change this to the following:
// this: 0 1 0 0 1 0 0
// TODO(lalitm): investigate whether we should just change this to And.
- void UpdateSetBits(const BitVector& other) {
- PERFETTO_DCHECK(other.size() == GetNumBitsSet());
+ void UpdateSetBits(const BitVector& other);
- // Go through each set bit and if |other| has it unset, then unset the
- // bit taking care to update the index we consider to take into account
- // the bits we just unset.
- // TODO(lalitm): we add an iterator implementation to remove this
- // inefficient loop.
- uint32_t removed = 0;
- for (uint32_t i = 0, size = other.size(); i < size; ++i) {
- if (!other.IsSet(i)) {
- Clear(IndexOfNthSet(i - removed++));
- }
- }
- }
+ // Iterate all the bits in the BitVector.
+ //
+ // Usage:
+ // for (auto it = bv.IterateAllBits(); it; it.Next()) {
+ // ...
+ // }
+ AllBitsIterator IterateAllBits() const;
private:
+ friend class internal::BaseIterator;
+ friend class internal::AllBitsIterator;
+
// Represents the offset of a bit within a block.
struct BlockOffset {
uint16_t word_idx;
diff --git a/src/trace_processor/db/bit_vector_iterators.cc b/src/trace_processor/db/bit_vector_iterators.cc
new file mode 100644
index 0000000..29981dd
--- /dev/null
+++ b/src/trace_processor/db/bit_vector_iterators.cc
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2019 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/db/bit_vector_iterators.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace internal {
+
+BaseIterator::BaseIterator(BitVector* bv) : bv_(bv) {
+ size_ = bv->size();
+
+ if (size_ > 0) {
+ block_ = bv_->blocks_[0];
+ }
+}
+
+BaseIterator::~BaseIterator() {
+ uint32_t block = index_ / BitVector::Block::kBits;
+ OnBlockChange(block, static_cast<uint32_t>(bv_->blocks_.size()) - 1);
+}
+
+void BaseIterator::OnBlockChange(uint32_t old_block, uint32_t new_block) {
+ // If we touched the current block, flush the block to the bitvector.
+ if (is_block_changed_) {
+ bv_->blocks_[old_block] = block_;
+ }
+
+ if (set_bit_count_diff_ != 0) {
+ // If the count of set bits has changed, go through all the counts between
+ // the old and new blocks and modify them.
+ // We only need to go to new_block and not to the end of the bitvector as
+ // the blocks after new_block will either be updated in a future call to
+ // OnBlockChange or in the destructor.
+ for (uint32_t i = old_block + 1; i <= new_block; ++i) {
+ int32_t new_count =
+ static_cast<int32_t>(bv_->counts_[i]) + set_bit_count_diff_;
+ PERFETTO_DCHECK(new_count >= 0);
+
+ bv_->counts_[i] = static_cast<uint32_t>(new_count);
+ }
+ }
+
+ // Reset the changed flag and cache the new block.
+ is_block_changed_ = false;
+ block_ = bv_->blocks_[new_block];
+}
+
+AllBitsIterator::AllBitsIterator(const BitVector* bv)
+ : BaseIterator(const_cast<BitVector*>(bv)) {}
+
+} // namespace internal
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/db/bit_vector_iterators.h b/src/trace_processor/db/bit_vector_iterators.h
new file mode 100644
index 0000000..a1b98d4
--- /dev/null
+++ b/src/trace_processor/db/bit_vector_iterators.h
@@ -0,0 +1,131 @@
+/*
+ * Copyright (C) 2019 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.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_DB_BIT_VECTOR_ITERATORS_H_
+#define SRC_TRACE_PROCESSOR_DB_BIT_VECTOR_ITERATORS_H_
+
+#include "src/trace_processor/db/bit_vector.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace internal {
+
+// Base iterator class for all iterators on BitVector.
+//
+// This class implements caching of one Block at a time to reduce pointer
+// chasing. It also defers updating counts on Clear calls until the end of each
+// block.
+class BaseIterator {
+ public:
+ BaseIterator(BitVector* bv);
+ ~BaseIterator();
+
+ BaseIterator(BaseIterator&&) noexcept = default;
+ BaseIterator& operator=(BaseIterator&&) = default;
+
+ // Clears the current bit the iterator points to.
+ void Clear() {
+ if (IsSet()) {
+ block_.Clear(block_offset());
+
+ is_block_changed_ = true;
+ --set_bit_count_diff_;
+ }
+ }
+
+ // Returns whether the current bit the iterator points to is set.
+ bool IsSet() { return block_.IsSet(block_offset()); }
+
+ // Returns the index of the current bit the iterator points to.
+ uint32_t index() const { return index_; }
+
+ protected:
+ // Sets the index this iterator points to the given value.
+ //
+ // This method also performs some extra work on block boundaries
+ // as it caches the block to improve performance by reducing pointer
+ // chasing on every IsSet and Clear calls.
+ void SetIndex(uint32_t index) {
+ // We should always move the index forward.
+ PERFETTO_DCHECK(index >= index_);
+
+ uint32_t old_index = index_;
+ index_ = index;
+
+ // If we've reached the end of the iterator, just bail out.
+ if (index >= size_)
+ return;
+
+ uint32_t old_block = old_index / BitVector::Block::kBits;
+ uint32_t new_block = index / BitVector::Block::kBits;
+
+ // Fast path: we're in the same block so we don't need to do
+ // any other work.
+ if (PERFETTO_LIKELY(old_block == new_block))
+ return;
+
+ // Slow path: we have to change block so this will involve flushing the old
+ // block and counts (if necessary) and caching the new block.
+ OnBlockChange(old_block, new_block);
+ }
+
+ // Handles flushing count changes and modified blocks to the bitvector
+ // and caching the new block.
+ void OnBlockChange(uint32_t old_block, uint32_t new_block);
+
+ uint32_t size() const { return size_; }
+
+ private:
+ BaseIterator(const BaseIterator&) = delete;
+ BaseIterator& operator=(const BaseIterator&) = delete;
+
+ BitVector::BlockOffset block_offset() const {
+ uint16_t bit_idx_inside_block = index_ % BitVector::Block::kBits;
+
+ BitVector::BlockOffset bo;
+ bo.word_idx = bit_idx_inside_block / BitVector::BitWord::kBits;
+ bo.bit_idx = bit_idx_inside_block % BitVector::BitWord::kBits;
+ return bo;
+ }
+
+ uint32_t index_ = 0;
+ uint32_t size_ = 0;
+
+ bool is_block_changed_ = false;
+ int32_t set_bit_count_diff_ = 0;
+
+ BitVector* bv_ = nullptr;
+
+ BitVector::Block block_{};
+};
+
+// Iterator over all the bits in a bitvector.
+class AllBitsIterator : public BaseIterator {
+ public:
+ AllBitsIterator(const BitVector*);
+
+ // Increments the iterator to point to the next bit.
+ void Next() { SetIndex(index() + 1); }
+
+ // Returns whether the iterator is valid.
+ operator bool() const { return index() < size(); }
+};
+
+} // namespace internal
+} // namespace trace_processor
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_DB_BIT_VECTOR_ITERATORS_H_
diff --git a/src/trace_processor/db/bit_vector_unittest.cc b/src/trace_processor/db/bit_vector_unittest.cc
index feb0f6c..c61fba6 100644
--- a/src/trace_processor/db/bit_vector_unittest.cc
+++ b/src/trace_processor/db/bit_vector_unittest.cc
@@ -18,6 +18,7 @@
#include <random>
+#include "src/trace_processor/db/bit_vector_iterators.h"
#include "test/gtest_and_gmock.h"
namespace perfetto {
@@ -236,6 +237,55 @@
ASSERT_TRUE(bv.IsSet(4));
}
+TEST(BitVectorUnittest, IterateAllBitsConst) {
+ BitVector bv;
+ for (uint32_t i = 0; i < 12345; ++i) {
+ if (i % 7 == 0 || i % 13 == 0) {
+ bv.AppendTrue();
+ } else {
+ bv.AppendFalse();
+ }
+ }
+
+ uint32_t i = 0;
+ for (auto it = bv.IterateAllBits(); it; it.Next(), ++i) {
+ ASSERT_EQ(it.IsSet(), i % 7 == 0 || i % 13 == 0);
+ ASSERT_EQ(it.index(), i);
+ }
+}
+
+TEST(BitVectorUnittest, IterateAllBitsClear) {
+ BitVector bv;
+ for (uint32_t i = 0; i < 12345; ++i) {
+ if (i % 7 == 0 || i % 13 == 0) {
+ bv.AppendTrue();
+ } else {
+ bv.AppendFalse();
+ }
+ }
+
+ // Unset every 15th bit.
+ for (auto it = bv.IterateAllBits(); it; it.Next()) {
+ if (it.index() % 15 == 0) {
+ it.Clear();
+ }
+ }
+
+ // Go through the iterator manually and check it has updated
+ // to not have every 15th bit set.
+ uint32_t count = 0;
+ for (uint32_t i = 0; i < 12345; ++i) {
+ bool is_set = i % 15 != 0 && (i % 7 == 0 || i % 13 == 0);
+
+ ASSERT_EQ(bv.IsSet(i), is_set);
+ ASSERT_EQ(bv.GetNumBitsSet(i), count);
+
+ if (is_set) {
+ ASSERT_EQ(bv.IndexOfNthSet(count++), i);
+ }
+ }
+}
+
TEST(BitVectorUnittest, QueryStressTest) {
BitVector bv;
std::vector<bool> bool_vec;
@@ -255,12 +305,19 @@
int_vec.emplace_back(i);
}
+ auto it = bv.IterateAllBits();
for (uint32_t i = 0; i < kCount; ++i) {
uint32_t count = static_cast<uint32_t>(std::count(
bool_vec.begin(), bool_vec.begin() + static_cast<int32_t>(i), true));
ASSERT_EQ(bv.IsSet(i), bool_vec[i]);
ASSERT_EQ(bv.GetNumBitsSet(i), count);
+
+ ASSERT_TRUE(it);
+ ASSERT_EQ(it.IsSet(), bool_vec[i]);
+ ASSERT_EQ(it.index(), i);
+ it.Next();
}
+ ASSERT_FALSE(it);
for (uint32_t i = 0; i < int_vec.size(); ++i) {
ASSERT_EQ(bv.IndexOfNthSet(i), int_vec[i]);
