blob: 564092a1a2667f7d5440018372f7edebe953b2f7 [file] [log] [blame]
Brian Carlstrom413e89f2013-10-21 23:53:49 -07001/*
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
Brian Carlstromba150c32013-08-27 17:31:03 -070017#ifndef ART_RUNTIME_BASE_BIT_VECTOR_H_
18#define ART_RUNTIME_BASE_BIT_VECTOR_H_
Brian Carlstrom413e89f2013-10-21 23:53:49 -070019
20#include <stdint.h>
Ian Rogerse77493c2014-08-20 15:08:45 -070021#include <iterator>
Brian Carlstrom413e89f2013-10-21 23:53:49 -070022
Vladimir Marko80afd022015-05-19 18:08:00 +010023#include "base/bit_utils.h"
David Brazdilf10a25f2015-06-02 14:29:52 +010024#include "globals.h"
Vladimir Marko83d46ef2015-05-12 18:27:20 +010025
Brian Carlstrom413e89f2013-10-21 23:53:49 -070026namespace art {
27
Ian Rogerse77493c2014-08-20 15:08:45 -070028class Allocator;
29
Brian Carlstrom413e89f2013-10-21 23:53:49 -070030/*
31 * Expanding bitmap, used for tracking resources. Bits are numbered starting
32 * from zero. All operations on a BitVector are unsynchronized.
33 */
34class BitVector {
Ian Rogerse77493c2014-08-20 15:08:45 -070035 public:
36 class IndexContainer;
Vladimir Markoa5b8fde2014-05-23 15:16:44 +010037
Ian Rogerse77493c2014-08-20 15:08:45 -070038 /**
39 * @brief Convenient iterator across the indexes of the BitVector's set bits.
40 *
41 * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest
42 * to the highest index of the BitVector's set bits. Instances can be retrieved
43 * only through BitVector::Indexes() which returns an IndexContainer wrapper
44 * object with begin() and end() suitable for range-based loops:
45 * for (uint32_t idx : bit_vector.Indexes()) {
46 * // Use idx.
47 * }
48 */
49 class IndexIterator :
50 std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> {
51 public:
52 bool operator==(const IndexIterator& other) const;
Brian Carlstrom413e89f2013-10-21 23:53:49 -070053
Ian Rogerse77493c2014-08-20 15:08:45 -070054 bool operator!=(const IndexIterator& other) const {
55 return !(*this == other);
Brian Carlstrom413e89f2013-10-21 23:53:49 -070056 }
Jean Christophe Beylerad0d30a2014-01-16 09:00:18 -080057
Vladimir Marko04071962015-01-02 17:00:44 +000058 uint32_t operator*() const;
Jean Christophe Beylerad0d30a2014-01-16 09:00:18 -080059
Ian Rogerse77493c2014-08-20 15:08:45 -070060 IndexIterator& operator++();
Vladimir Markod3c5beb2014-04-11 16:32:51 +010061
Ian Rogerse77493c2014-08-20 15:08:45 -070062 IndexIterator operator++(int);
Brian Carlstrom413e89f2013-10-21 23:53:49 -070063
Ian Rogerse77493c2014-08-20 15:08:45 -070064 // Helper function to check for end without comparing with bit_vector.Indexes().end().
65 bool Done() const {
66 return bit_index_ == BitSize();
Vladimir Markoa5b8fde2014-05-23 15:16:44 +010067 }
Brian Carlstrom413e89f2013-10-21 23:53:49 -070068
Ian Rogerse77493c2014-08-20 15:08:45 -070069 private:
70 struct begin_tag { };
71 struct end_tag { };
Brian Carlstrom413e89f2013-10-21 23:53:49 -070072
Vladimir Marko174b2e22017-10-12 13:34:49 +010073 IndexIterator(const BitVector* bit_vector, begin_tag);
74 IndexIterator(const BitVector* bit_vector, end_tag);
Ian Rogerse77493c2014-08-20 15:08:45 -070075
76 uint32_t BitSize() const {
77 return storage_size_ * kWordBits;
78 }
79
80 uint32_t FindIndex(uint32_t start_index) const;
81 const uint32_t* const bit_storage_;
82 const uint32_t storage_size_; // Size of vector in words.
83 uint32_t bit_index_; // Current index (size in bits).
84
85 friend class BitVector::IndexContainer;
86 };
87
88 /**
89 * @brief BitVector wrapper class for iteration across indexes of set bits.
90 */
91 class IndexContainer {
92 public:
93 explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { }
94
Vladimir Marko174b2e22017-10-12 13:34:49 +010095 IndexIterator begin() const;
96 IndexIterator end() const;
Ian Rogerse77493c2014-08-20 15:08:45 -070097
98 private:
99 const BitVector* const bit_vector_;
100 };
101
Vladimir Marko492a7fa2016-06-01 18:38:43 +0100102 // MoveConstructible but not MoveAssignable, CopyConstructible or CopyAssignable.
103
104 BitVector(const BitVector& other) = delete;
105 BitVector& operator=(const BitVector& other) = delete;
106
107 BitVector(BitVector&& other)
108 : storage_(other.storage_),
109 storage_size_(other.storage_size_),
110 allocator_(other.allocator_),
111 expandable_(other.expandable_) {
112 other.storage_ = nullptr;
113 other.storage_size_ = 0u;
114 }
115
Ian Rogerse77493c2014-08-20 15:08:45 -0700116 BitVector(uint32_t start_bits,
117 bool expandable,
Andreas Gampe067f1ed2015-08-07 08:29:13 -0700118 Allocator* allocator);
119
120 BitVector(bool expandable,
Ian Rogerse77493c2014-08-20 15:08:45 -0700121 Allocator* allocator,
Andreas Gampe067f1ed2015-08-07 08:29:13 -0700122 uint32_t storage_size,
123 uint32_t* storage);
124
125 BitVector(const BitVector& src,
126 bool expandable,
127 Allocator* allocator);
Ian Rogerse77493c2014-08-20 15:08:45 -0700128
129 virtual ~BitVector();
130
Vladimir Marko83d46ef2015-05-12 18:27:20 +0100131 // The number of words necessary to encode bits.
132 static constexpr uint32_t BitsToWords(uint32_t bits) {
133 return RoundUp(bits, kWordBits) / kWordBits;
134 }
135
Ian Rogerse77493c2014-08-20 15:08:45 -0700136 // Mark the specified bit as "set".
137 void SetBit(uint32_t idx) {
138 /*
139 * TUNING: this could have pathologically bad growth/expand behavior. Make sure we're
140 * not using it badly or change resize mechanism.
Jean Christophe Beylerad0d30a2014-01-16 09:00:18 -0800141 */
Ian Rogerse77493c2014-08-20 15:08:45 -0700142 if (idx >= storage_size_ * kWordBits) {
143 EnsureSize(idx);
144 }
145 storage_[WordIndex(idx)] |= BitMask(idx);
146 }
Jean Christophe Beylerad0d30a2014-01-16 09:00:18 -0800147
Ian Rogerse77493c2014-08-20 15:08:45 -0700148 // Mark the specified bit as "unset".
149 void ClearBit(uint32_t idx) {
150 // If the index is over the size, we don't have to do anything, it is cleared.
151 if (idx < storage_size_ * kWordBits) {
152 // Otherwise, go ahead and clear it.
153 storage_[WordIndex(idx)] &= ~BitMask(idx);
154 }
155 }
Vladimir Markod3c5beb2014-04-11 16:32:51 +0100156
Ian Rogerse77493c2014-08-20 15:08:45 -0700157 // Determine whether or not the specified bit is set.
158 bool IsBitSet(uint32_t idx) const {
159 // If the index is over the size, whether it is expandable or not, this bit does not exist:
160 // thus it is not set.
161 return (idx < (storage_size_ * kWordBits)) && IsBitSet(storage_, idx);
162 }
Jean Christophe Beyler5afa08f2014-04-15 15:54:35 -0700163
Ian Rogerse77493c2014-08-20 15:08:45 -0700164 // Mark all bits bit as "clear".
165 void ClearAllBits();
Jean Christophe Beyler520f37b2014-05-22 15:43:50 -0700166
Ian Rogerse77493c2014-08-20 15:08:45 -0700167 // Mark specified number of bits as "set". Cannot set all bits like ClearAll since there might
168 // be unused bits - setting those to one will confuse the iterator.
169 void SetInitialBits(uint32_t num_bits);
Jean Christophe Beyler5afa08f2014-04-15 15:54:35 -0700170
Ian Rogerse77493c2014-08-20 15:08:45 -0700171 void Copy(const BitVector* src);
Jean Christophe Beyler520f37b2014-05-22 15:43:50 -0700172
Ian Rogerse77493c2014-08-20 15:08:45 -0700173 // Intersect with another bit vector.
174 void Intersect(const BitVector* src2);
Jean Christophe Beyler520f37b2014-05-22 15:43:50 -0700175
Ian Rogerse77493c2014-08-20 15:08:45 -0700176 // Union with another bit vector.
177 bool Union(const BitVector* src);
Jean Christophe Beyler520f37b2014-05-22 15:43:50 -0700178
Ian Rogerse77493c2014-08-20 15:08:45 -0700179 // Set bits of union_with that are not in not_in.
180 bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in);
Jean Christophe Beyler5afa08f2014-04-15 15:54:35 -0700181
Ian Rogerse77493c2014-08-20 15:08:45 -0700182 void Subtract(const BitVector* src);
Vladimir Markoa5b8fde2014-05-23 15:16:44 +0100183
Ian Rogerse77493c2014-08-20 15:08:45 -0700184 // Are we equal to another bit vector? Note: expandability attributes must also match.
185 bool Equal(const BitVector* src) const;
186
187 /**
188 * @brief Are all the bits set the same?
189 * @details expandability and size can differ as long as the same bits are set.
190 */
191 bool SameBitsSet(const BitVector *src) const;
192
David Brazdil7d275372015-04-21 16:36:35 +0100193 bool IsSubsetOf(const BitVector *other) const;
194
Ian Rogerse77493c2014-08-20 15:08:45 -0700195 // Count the number of bits that are set.
196 uint32_t NumSetBits() const;
197
198 // Count the number of bits that are set in range [0, end).
199 uint32_t NumSetBits(uint32_t end) const;
200
201 IndexContainer Indexes() const {
202 return IndexContainer(this);
203 }
204
205 uint32_t GetStorageSize() const {
206 return storage_size_;
207 }
208
209 bool IsExpandable() const {
210 return expandable_;
211 }
212
213 uint32_t GetRawStorageWord(size_t idx) const {
214 return storage_[idx];
215 }
216
217 uint32_t* GetRawStorage() {
218 return storage_;
219 }
220
221 const uint32_t* GetRawStorage() const {
222 return storage_;
223 }
224
225 size_t GetSizeOf() const {
226 return storage_size_ * kWordBytes;
227 }
228
229 /**
230 * @return the highest bit set, -1 if none are set
231 */
232 int GetHighestBitSet() const;
233
David Srbecky1bbdfd72016-02-24 16:39:26 +0000234 // Minimum number of bits required to store this vector, 0 if none are set.
235 size_t GetNumberOfBits() const {
236 return GetHighestBitSet() + 1;
237 }
238
Ian Rogerse77493c2014-08-20 15:08:45 -0700239 // Is bit set in storage. (No range check.)
240 static bool IsBitSet(const uint32_t* storage, uint32_t idx) {
241 return (storage[WordIndex(idx)] & BitMask(idx)) != 0;
242 }
243
244 // Number of bits set in range [0, end) in storage. (No range check.)
245 static uint32_t NumSetBits(const uint32_t* storage, uint32_t end);
246
David Brazdilf10a25f2015-06-02 14:29:52 +0100247 // Fill given memory region with the contents of the vector and zero padding.
248 void CopyTo(void* dst, size_t len) const {
249 DCHECK_LE(static_cast<size_t>(GetHighestBitSet() + 1), len * kBitsPerByte);
250 size_t vec_len = GetSizeOf();
251 if (vec_len < len) {
252 void* dst_padding = reinterpret_cast<uint8_t*>(dst) + vec_len;
253 memcpy(dst, storage_, vec_len);
254 memset(dst_padding, 0, len - vec_len);
255 } else {
256 memcpy(dst, storage_, len);
257 }
258 }
259
Ian Rogerse77493c2014-08-20 15:08:45 -0700260 void Dump(std::ostream& os, const char* prefix) const;
261
Andreas Gampe067f1ed2015-08-07 08:29:13 -0700262 Allocator* GetAllocator() const;
263
Ian Rogerse77493c2014-08-20 15:08:45 -0700264 private:
265 /**
266 * @brief Dump the bitvector into buffer in a 00101..01 format.
267 * @param buffer the ostringstream used to dump the bitvector into.
268 */
269 void DumpHelper(const char* prefix, std::ostringstream& buffer) const;
270
271 // Ensure there is space for a bit at idx.
272 void EnsureSize(uint32_t idx);
273
274 // The index of the word within storage.
275 static constexpr uint32_t WordIndex(uint32_t idx) {
276 return idx >> 5;
277 }
278
279 // A bit mask to extract the bit for the given index.
280 static constexpr uint32_t BitMask(uint32_t idx) {
281 return 1 << (idx & 0x1f);
282 }
283
284 static constexpr uint32_t kWordBytes = sizeof(uint32_t);
285 static constexpr uint32_t kWordBits = kWordBytes * 8;
286
287 uint32_t* storage_; // The storage for the bit vector.
288 uint32_t storage_size_; // Current size, in 32-bit words.
289 Allocator* const allocator_; // Allocator if expandable.
290 const bool expandable_; // Should the bitmap expand if too small?
Brian Carlstrom413e89f2013-10-21 23:53:49 -0700291};
292
293
294} // namespace art
295
Brian Carlstromba150c32013-08-27 17:31:03 -0700296#endif // ART_RUNTIME_BASE_BIT_VECTOR_H_