1 /*
2 * Copyright (C) 2013 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 #ifndef ART_LIBARTBASE_BASE_BIT_VECTOR_INL_H_
18 #define ART_LIBARTBASE_BASE_BIT_VECTOR_INL_H_
19
20 #include "bit_vector.h"
21
22 #include <android-base/logging.h>
23 #include <cstring>
24
25 #include "bit_utils.h"
26
27 namespace art {
28
29 template <typename StorageType>
ClearAllBits()30 inline void BitVectorView<StorageType>::ClearAllBits() {
31 // Note: We do not `DCheckTrailingBitsClear()` here as this may be the initial call
32 // to clear the storage and the trailing bits may not be clear after allocation.
33 memset(storage_, 0, SizeInWords() * sizeof(WordType));
34 }
35
36 template <typename StorageType>
SetInitialBits(uint32_t num_bits)37 inline void BitVectorView<StorageType>::SetInitialBits(uint32_t num_bits) {
38 // Note: We do not `DCheckTrailingBitsClear()` here as this may be the initial call
39 // to clear the storage and the trailing bits may not be clear after allocation.
40 DCHECK_LE(num_bits, SizeInBits());
41 size_t words = WordIndex(num_bits);
42 // Set initial full words.
43 std::fill_n(storage_, words, std::numeric_limits<WordType>::max());
44 if (num_bits % kWordBits != 0) {
45 // Set all bits below the first clear bit in the boundary storage word.
46 storage_[words] = BitMask(num_bits) - static_cast<StorageType>(1u);
47 ++words;
48 }
49 // Set clear words if any.
50 std::fill_n(storage_ + words, SizeInWords() - words, static_cast<StorageType>(0));
51 }
52
53 template <typename StorageType>
Union(BitVectorView<const StorageType> union_with)54 inline bool BitVectorView<StorageType>::Union(BitVectorView<const StorageType> union_with) {
55 DCHECK_EQ(SizeInBits(), union_with.SizeInBits());
56 DCheckTrailingBitsClear();
57 union_with.DCheckTrailingBitsClear();
58 StorageType added_bits = 0u;
59 for (size_t i = 0, size = SizeInWords(); i != size; ++i) {
60 StorageType word = storage_[i];
61 StorageType union_with_word = union_with.storage_[i];
62 storage_[i] = union_with_word | word;
63 added_bits |= union_with_word & ~word;
64 }
65 return added_bits != 0u;
66 }
67
68 template <typename StorageType>
UnionIfNotIn(BitVectorView<const StorageType> union_with,BitVectorView<const StorageType> not_in)69 inline bool BitVectorView<StorageType>::UnionIfNotIn(BitVectorView<const StorageType> union_with,
70 BitVectorView<const StorageType> not_in) {
71 DCHECK_EQ(SizeInBits(), union_with.SizeInBits());
72 DCHECK_EQ(SizeInBits(), not_in.SizeInBits());
73 DCheckTrailingBitsClear();
74 union_with.DCheckTrailingBitsClear();
75 not_in.DCheckTrailingBitsClear();
76 StorageType added_bits = 0u;
77 for (size_t i = 0, size = SizeInWords(); i != size; ++i) {
78 StorageType word = storage_[i];
79 StorageType union_with_word = union_with.storage_[i] & ~not_in.storage_[i];
80 storage_[i] = union_with_word | word;
81 added_bits |= union_with_word & ~word;
82 }
83 return added_bits != 0u;
84 }
85
86 template <typename StorageType>
87 inline bool BitVectorIndexIterator<StorageType>::operator==(
88 const BitVectorIndexIterator<StorageType>& other) const {
89 DCHECK_EQ(bit_vector_view_.storage_, other.bit_vector_view_.storage_);
90 DCHECK_EQ(bit_vector_view_.size_in_bits_, other.bit_vector_view_.size_in_bits_);
91 return bit_index_ == other.bit_index_;
92 }
93
94 template <typename StorageType>
95 inline bool BitVectorIndexIterator<StorageType>::operator!=(
96 const BitVectorIndexIterator<StorageType>& other) const {
97 return !(*this == other);
98 }
99
100 template <typename StorageType>
101 inline size_t BitVectorIndexIterator<StorageType>::operator*() const {
102 DCHECK_LT(bit_index_, bit_vector_view_.size_in_bits_);
103 return bit_index_;
104 }
105
106 template <typename StorageType>
107 inline BitVectorIndexIterator<StorageType>& BitVectorIndexIterator<StorageType>::operator++() {
108 DCHECK_LT(bit_index_, bit_vector_view_.size_in_bits_);
109 bit_index_ = FindIndex(bit_index_ + 1u);
110 return *this;
111 }
112
113 template <typename StorageType>
114 inline BitVectorIndexIterator<StorageType> BitVectorIndexIterator<StorageType>::operator++(int) {
115 BitVectorIndexIterator result(*this);
116 ++*this;
117 return result;
118 }
119
120 template <typename StorageType>
FindIndex(size_t start_index)121 inline size_t BitVectorIndexIterator<StorageType>::FindIndex(size_t start_index) const {
122 DCHECK_LE(start_index, bit_vector_view_.size_in_bits_);
123 bit_vector_view_.DCheckTrailingBitsClear();
124 if (UNLIKELY(start_index == bit_vector_view_.size_in_bits_)) {
125 return start_index;
126 }
127 size_t word_index = start_index / kWordBits;
128 DCHECK_LT(word_index, bit_vector_view_.SizeInWords());
129 std::remove_const_t<StorageType> word = bit_vector_view_.storage_[word_index];
130 // Mask out any bits in the first word we've already considered.
131 word &= std::numeric_limits<StorageType>::max() << (start_index % kWordBits);
132 if (word == 0u) {
133 size_t size_in_words = bit_vector_view_.SizeInWords();
134 do {
135 ++word_index;
136 if (UNLIKELY(word_index == size_in_words)) {
137 return bit_vector_view_.size_in_bits_;
138 }
139 word = bit_vector_view_.storage_[word_index];
140 } while (word == 0u);
141 }
142 return word_index * kWordBits + CTZ(word);
143 }
144
145 template <typename StorageType>
BitVectorIndexIterator(BitVectorView<StorageType> bit_vector_view,begin_tag)146 inline BitVectorIndexIterator<StorageType>::BitVectorIndexIterator(
147 BitVectorView<StorageType> bit_vector_view, begin_tag)
148 : bit_vector_view_(bit_vector_view),
149 bit_index_(FindIndex(0u)) { }
150
151 template <typename StorageType>
BitVectorIndexIterator(BitVectorView<StorageType> bit_vector_view,end_tag)152 inline BitVectorIndexIterator<StorageType>::BitVectorIndexIterator(
153 BitVectorView<StorageType> bit_vector_view, end_tag)
154 : bit_vector_view_(bit_vector_view),
155 bit_index_(bit_vector_view_.size_in_bits_) { }
156
157 template <typename StorageType>
158 class BitVectorView<StorageType>::IndexContainerImpl {
159 static_assert(std::is_const_v<StorageType>);
160
161 public:
IndexContainerImpl(BitVectorView<StorageType> bit_vector_view)162 explicit IndexContainerImpl(BitVectorView<StorageType> bit_vector_view)
163 : bit_vector_view_(bit_vector_view) { }
164
begin()165 BitVectorIndexIterator<StorageType> begin() const {
166 return {bit_vector_view_, typename BitVectorIndexIterator<StorageType>::begin_tag()};
167 }
168
end()169 BitVectorIndexIterator<StorageType> end() const {
170 return {bit_vector_view_, typename BitVectorIndexIterator<StorageType>::end_tag()};
171 }
172
173 private:
174 BitVectorView<StorageType> bit_vector_view_;
175 };
176
177 template <typename StorageType>
Indexes()178 BitVectorView<StorageType>::IndexContainer BitVectorView<StorageType>::Indexes() const {
179 return BitVectorView<StorageType>::IndexContainer(*this);
180 }
181
ClearAllBits()182 inline void BitVector::ClearAllBits() {
183 AsView().ClearAllBits();
184 }
185
Equal(const BitVector * src)186 inline bool BitVector::Equal(const BitVector* src) const {
187 return (storage_size_ == src->GetStorageSize()) &&
188 (expandable_ == src->IsExpandable()) &&
189 (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0);
190 }
191
Indexes()192 inline BitVector::IndexContainer BitVector::Indexes() const {
193 return AsView().Indexes();
194 }
195
196 } // namespace art
197
198 #endif // ART_LIBARTBASE_BASE_BIT_VECTOR_INL_H_
199