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