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_RUNTIME_BASE_BIT_VECTOR_H_
18 #define ART_RUNTIME_BASE_BIT_VECTOR_H_
19 
20 #include <stdint.h>
21 #include <iterator>
22 
23 #include "base/bit_utils.h"
24 
25 namespace art {
26 
27 class Allocator;
28 
29 /*
30  * Expanding bitmap, used for tracking resources.  Bits are numbered starting
31  * from zero.  All operations on a BitVector are unsynchronized.
32  */
33 class BitVector {
34  public:
35   class IndexContainer;
36 
37   /**
38    * @brief Convenient iterator across the indexes of the BitVector's set bits.
39    *
40    * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest
41    * to the highest index of the BitVector's set bits. Instances can be retrieved
42    * only through BitVector::Indexes() which returns an IndexContainer wrapper
43    * object with begin() and end() suitable for range-based loops:
44    *   for (uint32_t idx : bit_vector.Indexes()) {
45    *     // Use idx.
46    *   }
47    */
48   class IndexIterator :
49       std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> {
50    public:
51     bool operator==(const IndexIterator& other) const;
52 
53     bool operator!=(const IndexIterator& other) const {
54       return !(*this == other);
55     }
56 
57     uint32_t operator*() const;
58 
59     IndexIterator& operator++();
60 
61     IndexIterator operator++(int);
62 
63     // Helper function to check for end without comparing with bit_vector.Indexes().end().
Done()64     bool Done() const {
65       return bit_index_ == BitSize();
66     }
67 
68    private:
69     struct begin_tag { };
70     struct end_tag { };
71 
IndexIterator(const BitVector * bit_vector,begin_tag)72     IndexIterator(const BitVector* bit_vector, begin_tag)
73       : bit_storage_(bit_vector->GetRawStorage()),
74         storage_size_(bit_vector->storage_size_),
75         bit_index_(FindIndex(0u)) { }
76 
IndexIterator(const BitVector * bit_vector,end_tag)77     IndexIterator(const BitVector* bit_vector, end_tag)
78       : bit_storage_(bit_vector->GetRawStorage()),
79         storage_size_(bit_vector->storage_size_),
80         bit_index_(BitSize()) { }
81 
BitSize()82     uint32_t BitSize() const {
83       return storage_size_ * kWordBits;
84     }
85 
86     uint32_t FindIndex(uint32_t start_index) const;
87     const uint32_t* const bit_storage_;
88     const uint32_t storage_size_;  // Size of vector in words.
89     uint32_t bit_index_;           // Current index (size in bits).
90 
91     friend class BitVector::IndexContainer;
92   };
93 
94   /**
95    * @brief BitVector wrapper class for iteration across indexes of set bits.
96    */
97   class IndexContainer {
98    public:
IndexContainer(const BitVector * bit_vector)99     explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { }
100 
begin()101     IndexIterator begin() const {
102       return IndexIterator(bit_vector_, IndexIterator::begin_tag());
103     }
104 
end()105     IndexIterator end() const {
106       return IndexIterator(bit_vector_, IndexIterator::end_tag());
107     }
108 
109    private:
110     const BitVector* const bit_vector_;
111   };
112 
113   BitVector(uint32_t start_bits,
114             bool expandable,
115             Allocator* allocator);
116 
117   BitVector(bool expandable,
118             Allocator* allocator,
119             uint32_t storage_size,
120             uint32_t* storage);
121 
122   BitVector(const BitVector& src,
123             bool expandable,
124             Allocator* allocator);
125 
126   virtual ~BitVector();
127 
128   // The number of words necessary to encode bits.
BitsToWords(uint32_t bits)129   static constexpr uint32_t BitsToWords(uint32_t bits) {
130     return RoundUp(bits, kWordBits) / kWordBits;
131   }
132 
133   // Mark the specified bit as "set".
SetBit(uint32_t idx)134   void SetBit(uint32_t idx) {
135     /*
136      * TUNING: this could have pathologically bad growth/expand behavior.  Make sure we're
137      * not using it badly or change resize mechanism.
138      */
139     if (idx >= storage_size_ * kWordBits) {
140       EnsureSize(idx);
141     }
142     storage_[WordIndex(idx)] |= BitMask(idx);
143   }
144 
145   // Mark the specified bit as "unset".
ClearBit(uint32_t idx)146   void ClearBit(uint32_t idx) {
147     // If the index is over the size, we don't have to do anything, it is cleared.
148     if (idx < storage_size_ * kWordBits) {
149       // Otherwise, go ahead and clear it.
150       storage_[WordIndex(idx)] &= ~BitMask(idx);
151     }
152   }
153 
154   // Determine whether or not the specified bit is set.
IsBitSet(uint32_t idx)155   bool IsBitSet(uint32_t idx) const {
156     // If the index is over the size, whether it is expandable or not, this bit does not exist:
157     // thus it is not set.
158     return (idx < (storage_size_ * kWordBits)) && IsBitSet(storage_, idx);
159   }
160 
161   // Mark all bits bit as "clear".
162   void ClearAllBits();
163 
164   // Mark specified number of bits as "set". Cannot set all bits like ClearAll since there might
165   // be unused bits - setting those to one will confuse the iterator.
166   void SetInitialBits(uint32_t num_bits);
167 
168   void Copy(const BitVector* src);
169 
170   // Intersect with another bit vector.
171   void Intersect(const BitVector* src2);
172 
173   // Union with another bit vector.
174   bool Union(const BitVector* src);
175 
176   // Set bits of union_with that are not in not_in.
177   bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in);
178 
179   void Subtract(const BitVector* src);
180 
181   // Are we equal to another bit vector?  Note: expandability attributes must also match.
182   bool Equal(const BitVector* src) const;
183 
184   /**
185    * @brief Are all the bits set the same?
186    * @details expandability and size can differ as long as the same bits are set.
187    */
188   bool SameBitsSet(const BitVector *src) const;
189 
190   bool IsSubsetOf(const BitVector *other) const;
191 
192   // Count the number of bits that are set.
193   uint32_t NumSetBits() const;
194 
195   // Count the number of bits that are set in range [0, end).
196   uint32_t NumSetBits(uint32_t end) const;
197 
Indexes()198   IndexContainer Indexes() const {
199     return IndexContainer(this);
200   }
201 
GetStorageSize()202   uint32_t GetStorageSize() const {
203     return storage_size_;
204   }
205 
IsExpandable()206   bool IsExpandable() const {
207     return expandable_;
208   }
209 
GetRawStorageWord(size_t idx)210   uint32_t GetRawStorageWord(size_t idx) const {
211     return storage_[idx];
212   }
213 
GetRawStorage()214   uint32_t* GetRawStorage() {
215     return storage_;
216   }
217 
GetRawStorage()218   const uint32_t* GetRawStorage() const {
219     return storage_;
220   }
221 
GetSizeOf()222   size_t GetSizeOf() const {
223     return storage_size_ * kWordBytes;
224   }
225 
226   /**
227    * @return the highest bit set, -1 if none are set
228    */
229   int GetHighestBitSet() const;
230 
231   // Is bit set in storage. (No range check.)
IsBitSet(const uint32_t * storage,uint32_t idx)232   static bool IsBitSet(const uint32_t* storage, uint32_t idx) {
233     return (storage[WordIndex(idx)] & BitMask(idx)) != 0;
234   }
235 
236   // Number of bits set in range [0, end) in storage. (No range check.)
237   static uint32_t NumSetBits(const uint32_t* storage, uint32_t end);
238 
239   void Dump(std::ostream& os, const char* prefix) const;
240 
241   Allocator* GetAllocator() const;
242 
243  private:
244   /**
245    * @brief Dump the bitvector into buffer in a 00101..01 format.
246    * @param buffer the ostringstream used to dump the bitvector into.
247    */
248   void DumpHelper(const char* prefix, std::ostringstream& buffer) const;
249 
250   // Ensure there is space for a bit at idx.
251   void EnsureSize(uint32_t idx);
252 
253   // The index of the word within storage.
WordIndex(uint32_t idx)254   static constexpr uint32_t WordIndex(uint32_t idx) {
255     return idx >> 5;
256   }
257 
258   // A bit mask to extract the bit for the given index.
BitMask(uint32_t idx)259   static constexpr uint32_t BitMask(uint32_t idx) {
260     return 1 << (idx & 0x1f);
261   }
262 
263   static constexpr uint32_t kWordBytes = sizeof(uint32_t);
264   static constexpr uint32_t kWordBits = kWordBytes * 8;
265 
266   uint32_t*  storage_;            // The storage for the bit vector.
267   uint32_t   storage_size_;       // Current size, in 32-bit words.
268   Allocator* const allocator_;    // Allocator if expandable.
269   const bool expandable_;         // Should the bitmap expand if too small?
270 };
271 
272 
273 }  // namespace art
274 
275 #endif  // ART_RUNTIME_BASE_BIT_VECTOR_H_
276