1 /*
2 * Copyright (C) 2019 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/containers/bit_vector_iterators.h"
18
19 namespace perfetto {
20 namespace trace_processor {
21 namespace internal {
22
BaseIterator(BitVector * bv)23 BaseIterator::BaseIterator(BitVector* bv) : bv_(bv) {
24 size_ = bv->size();
25
26 if (size_ > 0) {
27 block_ = bv_->blocks_[0];
28 }
29 }
30
~BaseIterator()31 BaseIterator::~BaseIterator() {
32 if (size_ > 0) {
33 uint32_t block_idx = index_ / BitVector::Block::kBits;
34 uint32_t last_block_idx = static_cast<uint32_t>(bv_->blocks_.size()) - 1;
35
36 // If |index_| == |size_| and the last index was on a block boundary, we
37 // can end up one block past the end of the bitvector. Take the
38 // min of the block index and the last block
39 OnBlockChange(std::min(block_idx, last_block_idx), last_block_idx);
40 }
41 }
42
OnBlockChange(uint32_t old_block,uint32_t new_block)43 void BaseIterator::OnBlockChange(uint32_t old_block, uint32_t new_block) {
44 // If we touched the current block, flush the block to the bitvector.
45 if (is_block_changed_) {
46 bv_->blocks_[old_block] = block_;
47 }
48
49 if (set_bit_count_diff_ != 0) {
50 // If the count of set bits has changed, go through all the counts between
51 // the old and new blocks and modify them.
52 // We only need to go to new_block and not to the end of the bitvector as
53 // the blocks after new_block will either be updated in a future call to
54 // OnBlockChange or in the destructor.
55 for (uint32_t i = old_block + 1; i <= new_block; ++i) {
56 int32_t new_count =
57 static_cast<int32_t>(bv_->counts_[i]) + set_bit_count_diff_;
58 PERFETTO_DCHECK(new_count >= 0);
59
60 bv_->counts_[i] = static_cast<uint32_t>(new_count);
61 }
62 }
63
64 // Reset the changed flag and cache the new block.
65 is_block_changed_ = false;
66 block_ = bv_->blocks_[new_block];
67 }
68
AllBitsIterator(const BitVector * bv)69 AllBitsIterator::AllBitsIterator(const BitVector* bv)
70 : BaseIterator(const_cast<BitVector*>(bv)) {}
71
SetBitsIterator(const BitVector * bv)72 SetBitsIterator::SetBitsIterator(const BitVector* bv)
73 : BaseIterator(const_cast<BitVector*>(bv)) {
74 set_bit_count_ = bv->GetNumBitsSet();
75
76 if (set_bit_count_ > 0) {
77 // Read a batch of set bit indices starting at index 0.
78 ReadSetBitBatch(0);
79
80 // Fast forward the iterator to the first index in the freshly read
81 // batch of set bots.
82 SetIndex(batch_[0]);
83 }
84 }
85
ReadSetBitBatch(uint32_t start_idx)86 void SetBitsIterator::ReadSetBitBatch(uint32_t start_idx) {
87 PERFETTO_DCHECK(set_bit_index_ % kBatchSize == 0);
88
89 uint32_t set_bit_count_until_i = set_bit_index_;
90 for (uint32_t i = start_idx; i < size(); ++i) {
91 auto addr = BitVector::IndexToAddress(i);
92
93 // Compute the count to the end of the block noting that the last block
94 // needs to use |set_bit_count_| and not the next count in the vector
95 // because that is OOB.
96 uint32_t set_bits_to_end_of_block =
97 addr.block_idx == bv().counts_.size() - 1
98 ? set_bit_count_
99 : bv().counts_[addr.block_idx + 1];
100
101 // Optimization: If the count of set bits to the end of the block is the
102 // same as the count to the current index, we can just skip the whole
103 // block without iterating through the bits inside.
104 if (set_bits_to_end_of_block == set_bit_count_until_i) {
105 static constexpr BitVector::BlockOffset kLastBlockOffset = {
106 BitVector::Block::kWords - 1, BitVector::BitWord::kBits - 1};
107
108 i = BitVector::AddressToIndex({addr.block_idx, kLastBlockOffset});
109 continue;
110 }
111
112 // If the bit is not set, just bail out.
113 const auto& block = bv().blocks_[addr.block_idx];
114 if (!block.IsSet(addr.block_offset))
115 continue;
116
117 // Update |batch_| with the index of the current bit.
118 uint32_t batch_idx = set_bit_count_until_i++ % kBatchSize;
119 batch_[batch_idx] = i;
120
121 // If we've reached as many indicies as the batch can store, just
122 // return.
123 if (PERFETTO_UNLIKELY(batch_idx == kBatchSize - 1))
124 return;
125 }
126
127 // We should only get here when we've managed to read all the set bits.
128 // End of batch should return from the body of the loop.
129 PERFETTO_DCHECK(set_bit_count_until_i == set_bit_count_);
130 }
131
132 } // namespace internal
133 } // namespace trace_processor
134 } // namespace perfetto
135