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 <stddef.h>
22 
23 #include "allocator.h"
24 #include "base/logging.h"
25 #include "utils.h"
26 
27 namespace art {
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           DCHECK(bit_storage_ == other.bit_storage_);
53           DCHECK_EQ(storage_size_, other.storage_size_);
54           return bit_index_ == other.bit_index_;
55         }
56 
57         bool operator!=(const IndexIterator& other) const {
58           return !(*this == other);
59         }
60 
61         int operator*() const {
62           DCHECK_LT(bit_index_, BitSize());
63           return bit_index_;
64         }
65 
66         IndexIterator& operator++() {
67           DCHECK_LT(bit_index_, BitSize());
68           bit_index_ = FindIndex(bit_index_ + 1u);
69           return *this;
70         }
71 
72         IndexIterator operator++(int) {
73           IndexIterator result(*this);
74           ++*this;
75           return result;
76         }
77 
78         // Helper function to check for end without comparing with bit_vector.Indexes().end().
Done()79         bool Done() const {
80           return bit_index_ == BitSize();
81         }
82 
83       private:
84         struct begin_tag { };
85         struct end_tag { };
86 
IndexIterator(const BitVector * bit_vector,begin_tag)87         IndexIterator(const BitVector* bit_vector, begin_tag)
88           : bit_storage_(bit_vector->GetRawStorage()),
89             storage_size_(bit_vector->storage_size_),
90             bit_index_(FindIndex(0u)) { }
91 
IndexIterator(const BitVector * bit_vector,end_tag)92         IndexIterator(const BitVector* bit_vector, end_tag)
93           : bit_storage_(bit_vector->GetRawStorage()),
94             storage_size_(bit_vector->storage_size_),
95             bit_index_(BitSize()) { }
96 
BitSize()97         uint32_t BitSize() const {
98           return storage_size_ * kWordBits;
99         }
100 
FindIndex(uint32_t start_index)101         uint32_t FindIndex(uint32_t start_index) const {
102           DCHECK_LE(start_index, BitSize());
103           uint32_t word_index = start_index / kWordBits;
104           if (UNLIKELY(word_index == storage_size_)) {
105             return start_index;
106           }
107           uint32_t word = bit_storage_[word_index];
108           // Mask out any bits in the first word we've already considered.
109           word &= static_cast<uint32_t>(-1) << (start_index & 0x1f);
110           while (word == 0u) {
111             ++word_index;
112             if (UNLIKELY(word_index == storage_size_)) {
113               return BitSize();
114             }
115             word = bit_storage_[word_index];
116           }
117           return word_index * 32u + CTZ(word);
118         }
119 
120         const uint32_t* const bit_storage_;
121         const uint32_t storage_size_;  // Size of vector in words.
122         uint32_t bit_index_;           // Current index (size in bits).
123 
124         friend class BitVector::IndexContainer;
125     };
126 
127     /**
128      * @brief BitVector wrapper class for iteration across indexes of set bits.
129      */
130     class IndexContainer {
131      public:
IndexContainer(const BitVector * bit_vector)132       explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { }
133 
begin()134       IndexIterator begin() const {
135         return IndexIterator(bit_vector_, IndexIterator::begin_tag());
136       }
137 
end()138       IndexIterator end() const {
139         return IndexIterator(bit_vector_, IndexIterator::end_tag());
140       }
141 
142      private:
143       const BitVector* const bit_vector_;
144     };
145 
146     BitVector(uint32_t start_bits,
147               bool expandable,
148               Allocator* allocator,
149               uint32_t storage_size = 0,
150               uint32_t* storage = nullptr);
151 
152     virtual ~BitVector();
153 
154     void SetBit(uint32_t num);
155     void ClearBit(uint32_t num);
156     bool IsBitSet(uint32_t num) const;
157     void ClearAllBits();
158     void SetInitialBits(uint32_t num_bits);
159 
160     void Copy(const BitVector* src);
161     void Intersect(const BitVector* src2);
162     bool Union(const BitVector* src);
163 
164     // Set bits of union_with that are not in not_in.
165     bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in);
166 
167     void Subtract(const BitVector* src);
168     // Are we equal to another bit vector?  Note: expandability attributes must also match.
Equal(const BitVector * src)169     bool Equal(const BitVector* src) {
170       return (storage_size_ == src->GetStorageSize()) &&
171         (expandable_ == src->IsExpandable()) &&
172         (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0);
173     }
174 
175     /**
176      * @brief Are all the bits set the same?
177      * @details expandability and size can differ as long as the same bits are set.
178      */
179     bool SameBitsSet(const BitVector *src);
180 
181     uint32_t NumSetBits() const;
182 
183     // Number of bits set in range [0, end).
184     uint32_t NumSetBits(uint32_t end) const;
185 
Indexes()186     IndexContainer Indexes() const {
187       return IndexContainer(this);
188     }
189 
GetStorageSize()190     uint32_t GetStorageSize() const { return storage_size_; }
IsExpandable()191     bool IsExpandable() const { return expandable_; }
GetRawStorageWord(size_t idx)192     uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; }
GetRawStorage()193     uint32_t* GetRawStorage() { return storage_; }
GetRawStorage()194     const uint32_t* GetRawStorage() const { return storage_; }
GetSizeOf()195     size_t GetSizeOf() const { return storage_size_ * kWordBytes; }
196 
197     /**
198      * @return the highest bit set, -1 if none are set
199      */
200     int GetHighestBitSet() const;
201 
202     // Is bit set in storage. (No range check.)
203     static bool IsBitSet(const uint32_t* storage, uint32_t num);
204     // Number of bits set in range [0, end) in storage. (No range check.)
205     static uint32_t NumSetBits(const uint32_t* storage, uint32_t end);
206 
207     bool EnsureSizeAndClear(unsigned int num);
208 
209     void Dump(std::ostream& os, const char* prefix) const;
210 
211     /**
212      * @brief last_entry is this the last entry for the dot dumping
213      * @details if not, a "|" is appended to the dump.
214      */
215     void DumpDot(FILE* file, const char* prefix, bool last_entry = false) const;
216 
217     /**
218      * @brief last_entry is this the last entry for the dot dumping
219      * @details if not, a "|" is appended to the dump.
220      */
221     void DumpIndicesDot(FILE* file, const char* prefix, bool last_entry = false) const;
222 
223   protected:
224     /**
225      * @brief Dump the bitvector into buffer in a 00101..01 format.
226      * @param buffer the ostringstream used to dump the bitvector into.
227      */
228     void DumpHelper(const char* prefix, std::ostringstream& buffer) const;
229 
230     /**
231      * @brief Dump the bitvector in a 1 2 5 8 format, where the numbers are the bit set.
232      * @param buffer the ostringstream used to dump the bitvector into.
233      */
234     void DumpIndicesHelper(const char* prefix, std::ostringstream& buffer) const;
235 
236     /**
237      * @brief Wrapper to perform the bitvector dumping with the .dot format.
238      * @param buffer the ostringstream used to dump the bitvector into.
239      */
240     void DumpDotHelper(bool last_entry, FILE* file, std::ostringstream& buffer) const;
241 
242   private:
243     static constexpr uint32_t kWordBytes = sizeof(uint32_t);
244     static constexpr uint32_t kWordBits = kWordBytes * 8;
245 
246     Allocator* const allocator_;
247     const bool expandable_;         // expand bitmap if we run out?
248     uint32_t   storage_size_;       // current size, in 32-bit words.
249     uint32_t*  storage_;
250 };
251 
252 
253 }  // namespace art
254 
255 #endif  // ART_RUNTIME_BASE_BIT_VECTOR_H_
256