• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (C) 2011 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 "bit_vector.h"
18 
19 #include <limits>
20 #include <sstream>
21 
22 #include "allocator.h"
23 #include "bit_vector-inl.h"
24 
25 namespace art {
26 
BitVector(bool expandable,Allocator * allocator,uint32_t storage_size,uint32_t * storage)27 BitVector::BitVector(bool expandable,
28                      Allocator* allocator,
29                      uint32_t storage_size,
30                      uint32_t* storage)
31   : storage_(storage),
32     storage_size_(storage_size),
33     allocator_(allocator),
34     expandable_(expandable) {
35   DCHECK(storage_ != nullptr);
36 
37   static_assert(sizeof(*storage_) == kWordBytes, "word bytes");
38   static_assert(sizeof(*storage_) * 8u == kWordBits, "word bits");
39 }
40 
BitVector(uint32_t start_bits,bool expandable,Allocator * allocator)41 BitVector::BitVector(uint32_t start_bits,
42                      bool expandable,
43                      Allocator* allocator)
44   : BitVector(expandable,
45               allocator,
46               BitsToWords(start_bits),
47               static_cast<uint32_t*>(allocator->Alloc(BitsToWords(start_bits) * kWordBytes))) {
48   // We don't know if the allocator cleared things.
49   ClearAllBits();
50 }
51 
BitVector(const BitVector & src,bool expandable,Allocator * allocator)52 BitVector::BitVector(const BitVector& src,
53                      bool expandable,
54                      Allocator* allocator)
55   : BitVector(expandable,
56               allocator,
57               src.storage_size_,
58               static_cast<uint32_t*>(allocator->Alloc(src.storage_size_ * kWordBytes))) {
59   // Direct memcpy would be faster, but this should be fine too and is cleaner.
60   Copy(&src);
61 }
62 
~BitVector()63 BitVector::~BitVector() {
64   if (storage_ != nullptr) {
65     // Only free if we haven't been moved out of.
66     allocator_->Free(storage_);
67   }
68 }
69 
SameBitsSet(const BitVector * src) const70 bool BitVector::SameBitsSet(const BitVector *src) const {
71   int our_highest = GetHighestBitSet();
72   int src_highest = src->GetHighestBitSet();
73 
74   // If the highest bit set is different, we are different.
75   if (our_highest != src_highest) {
76     return false;
77   }
78 
79   // If the highest bit set is -1, both are cleared, we are the same.
80   // If the highest bit set is 0, both have a unique bit set, we are the same.
81   if (our_highest <= 0) {
82     return true;
83   }
84 
85   // Get the highest bit set's cell's index
86   // No need of highest + 1 here because it can't be 0 so BitsToWords will work here.
87   int our_highest_index = BitsToWords(our_highest);
88 
89   // This memcmp is enough: we know that the highest bit set is the same for both:
90   //   - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less.
91   //      ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index,
92   //          they are automatically at 0.
93   return (memcmp(storage_, src->GetRawStorage(), our_highest_index * kWordBytes) == 0);
94 }
95 
IsSubsetOf(const BitVector * other) const96 bool BitVector::IsSubsetOf(const BitVector *other) const {
97   int this_highest = GetHighestBitSet();
98   int other_highest = other->GetHighestBitSet();
99 
100   // If the highest bit set is -1, this is empty and a trivial subset.
101   if (this_highest < 0) {
102     return true;
103   }
104 
105   // If the highest bit set is higher, this cannot be a subset.
106   if (this_highest > other_highest) {
107     return false;
108   }
109 
110   // Compare each 32-bit word.
111   size_t this_highest_index = BitsToWords(this_highest + 1);
112   for (size_t i = 0; i < this_highest_index; ++i) {
113     uint32_t this_storage = storage_[i];
114     uint32_t other_storage = other->storage_[i];
115     if ((this_storage | other_storage) != other_storage) {
116       return false;
117     }
118   }
119   return true;
120 }
121 
Intersect(const BitVector * src)122 void BitVector::Intersect(const BitVector* src) {
123   uint32_t src_storage_size = src->storage_size_;
124 
125   // Get the minimum size between us and source.
126   uint32_t min_size = (storage_size_ < src_storage_size) ? storage_size_ : src_storage_size;
127 
128   uint32_t idx;
129   for (idx = 0; idx < min_size; idx++) {
130     storage_[idx] &= src->GetRawStorageWord(idx);
131   }
132 
133   // Now, due to this being an intersection, there are two possibilities:
134   //   - Either src was larger than us: we don't care, all upper bits would thus be 0.
135   //   - Either we are larger than src: we don't care, all upper bits would have been 0 too.
136   // So all we need to do is set all remaining bits to 0.
137   for (; idx < storage_size_; idx++) {
138     storage_[idx] = 0;
139   }
140 }
141 
Union(const BitVector * src)142 bool BitVector::Union(const BitVector* src) {
143   // Get the highest bit to determine how much we need to expand.
144   int highest_bit = src->GetHighestBitSet();
145   bool changed = false;
146 
147   // If src has no bit set, we are done: there is no need for a union with src.
148   if (highest_bit == -1) {
149     return changed;
150   }
151 
152   // Update src_size to how many cells we actually care about: where the bit is + 1.
153   uint32_t src_size = BitsToWords(highest_bit + 1);
154 
155   // Is the storage size smaller than src's?
156   if (storage_size_ < src_size) {
157     changed = true;
158 
159     EnsureSize(highest_bit);
160 
161     // Check: storage size should be big enough to hold this bit now.
162     DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
163   }
164 
165   for (uint32_t idx = 0; idx < src_size; idx++) {
166     uint32_t existing = storage_[idx];
167     uint32_t update = existing | src->GetRawStorageWord(idx);
168     if (existing != update) {
169       changed = true;
170       storage_[idx] = update;
171     }
172   }
173   return changed;
174 }
175 
UnionIfNotIn(const BitVector * union_with,const BitVector * not_in)176 bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) {
177   // Get the highest bit to determine how much we need to expand.
178   int highest_bit = union_with->GetHighestBitSet();
179   bool changed = false;
180 
181   // If src has no bit set, we are done: there is no need for a union with src.
182   if (highest_bit == -1) {
183     return changed;
184   }
185 
186   // Update union_with_size to how many cells we actually care about: where the bit is + 1.
187   uint32_t union_with_size = BitsToWords(highest_bit + 1);
188 
189   // Is the storage size smaller than src's?
190   if (storage_size_ < union_with_size) {
191     EnsureSize(highest_bit);
192 
193     // Check: storage size should be big enough to hold this bit now.
194     DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
195   }
196 
197   uint32_t not_in_size = not_in->GetStorageSize();
198 
199   uint32_t idx = 0;
200   for (; idx < std::min(not_in_size, union_with_size); idx++) {
201     uint32_t existing = storage_[idx];
202     uint32_t update = existing |
203         (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx));
204     if (existing != update) {
205       changed = true;
206       storage_[idx] = update;
207     }
208   }
209 
210   for (; idx < union_with_size; idx++) {
211     uint32_t existing = storage_[idx];
212     uint32_t update = existing | union_with->GetRawStorageWord(idx);
213     if (existing != update) {
214       changed = true;
215       storage_[idx] = update;
216     }
217   }
218   return changed;
219 }
220 
Subtract(const BitVector * src)221 void BitVector::Subtract(const BitVector *src) {
222   uint32_t src_size = src->storage_size_;
223 
224   // We only need to operate on bytes up to the smaller of the sizes of the two operands.
225   unsigned int min_size = (storage_size_ > src_size) ? src_size : storage_size_;
226 
227   // Difference until max, we know both accept it:
228   //   There is no need to do more:
229   //     If we are bigger than src, the upper bits are unchanged.
230   //     If we are smaller than src, the nonexistent upper bits are 0 and thus can't get subtracted.
231   for (uint32_t idx = 0; idx < min_size; idx++) {
232     storage_[idx] &= (~(src->GetRawStorageWord(idx)));
233   }
234 }
235 
NumSetBits() const236 uint32_t BitVector::NumSetBits() const {
237   uint32_t count = 0;
238   for (uint32_t word = 0; word < storage_size_; word++) {
239     count += POPCOUNT(storage_[word]);
240   }
241   return count;
242 }
243 
NumSetBits(uint32_t end) const244 uint32_t BitVector::NumSetBits(uint32_t end) const {
245   DCHECK_LE(end, storage_size_ * kWordBits);
246   return NumSetBits(storage_, end);
247 }
248 
SetInitialBits(uint32_t num_bits)249 void BitVector::SetInitialBits(uint32_t num_bits) {
250   // If num_bits is 0, clear everything.
251   if (num_bits == 0) {
252     ClearAllBits();
253     return;
254   }
255 
256   // Set the highest bit we want to set to get the BitVector allocated if need be.
257   SetBit(num_bits - 1);
258 
259   uint32_t idx;
260   // We can set every storage element with -1.
261   for (idx = 0; idx < WordIndex(num_bits); idx++) {
262     storage_[idx] = std::numeric_limits<uint32_t>::max();
263   }
264 
265   // Handle the potentially last few bits.
266   uint32_t rem_num_bits = num_bits & 0x1f;
267   if (rem_num_bits != 0) {
268     storage_[idx] = (1U << rem_num_bits) - 1;
269     ++idx;
270   }
271 
272   // Now set the upper ones to 0.
273   for (; idx < storage_size_; idx++) {
274     storage_[idx] = 0;
275   }
276 }
277 
GetHighestBitSet() const278 int BitVector::GetHighestBitSet() const {
279   unsigned int max = storage_size_;
280   for (int idx = max - 1; idx >= 0; idx--) {
281     // If not 0, we have more work: check the bits.
282     uint32_t value = storage_[idx];
283 
284     if (value != 0) {
285       // Return highest bit set in value plus bits from previous storage indexes.
286       return 31 - CLZ(value) + (idx * kWordBits);
287     }
288   }
289 
290   // All zero, therefore return -1.
291   return -1;
292 }
293 
Copy(const BitVector * src)294 void BitVector::Copy(const BitVector *src) {
295   // Get highest bit set, we only need to copy till then.
296   int highest_bit = src->GetHighestBitSet();
297 
298   // If nothing is set, clear everything.
299   if (highest_bit == -1) {
300     ClearAllBits();
301     return;
302   }
303 
304   // Set upper bit to ensure right size before copy.
305   SetBit(highest_bit);
306 
307   // Now set until highest bit's storage.
308   uint32_t size = 1 + (highest_bit / kWordBits);
309   memcpy(storage_, src->GetRawStorage(), kWordBytes * size);
310 
311   // Set upper bits to 0.
312   uint32_t left = storage_size_ - size;
313 
314   if (left > 0) {
315     memset(storage_ + size, 0, kWordBytes * left);
316   }
317 }
318 
NumSetBits(const uint32_t * storage,uint32_t end)319 uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) {
320   uint32_t word_end = WordIndex(end);
321   uint32_t partial_word_bits = end & 0x1f;
322 
323   uint32_t count = 0u;
324   for (uint32_t word = 0u; word < word_end; word++) {
325     count += POPCOUNT(storage[word]);
326   }
327   if (partial_word_bits != 0u) {
328     count += POPCOUNT(storage[word_end] & ~(0xffffffffu << partial_word_bits));
329   }
330   return count;
331 }
332 
Dump(std::ostream & os,const char * prefix) const333 void BitVector::Dump(std::ostream& os, const char *prefix) const {
334   std::ostringstream buffer;
335   DumpHelper(prefix, buffer);
336   os << buffer.str() << std::endl;
337 }
338 
DumpHelper(const char * prefix,std::ostringstream & buffer) const339 void BitVector::DumpHelper(const char* prefix, std::ostringstream& buffer) const {
340   // Initialize it.
341   if (prefix != nullptr) {
342     buffer << prefix;
343   }
344 
345   buffer << '(';
346   for (size_t i = 0; i < storage_size_ * kWordBits; i++) {
347     buffer << IsBitSet(i);
348   }
349   buffer << ')';
350 }
351 
EnsureSize(uint32_t idx)352 void BitVector::EnsureSize(uint32_t idx) {
353   if (idx >= storage_size_ * kWordBits) {
354     DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << idx;
355 
356     /* Round up to word boundaries for "idx+1" bits */
357     uint32_t new_size = BitsToWords(idx + 1);
358     DCHECK_GT(new_size, storage_size_);
359     uint32_t *new_storage =
360         static_cast<uint32_t*>(allocator_->Alloc(new_size * kWordBytes));
361     memcpy(new_storage, storage_, storage_size_ * kWordBytes);
362     // Zero out the new storage words.
363     memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * kWordBytes);
364     // TODO: collect stats on space wasted because of resize.
365 
366     // Free old storage.
367     allocator_->Free(storage_);
368 
369     // Set fields.
370     storage_ = new_storage;
371     storage_size_ = new_size;
372   }
373 }
374 
GetAllocator() const375 Allocator* BitVector::GetAllocator() const {
376   return allocator_;
377 }
378 
Resize(size_t rows,size_t cols,bool clear)379 void BaseBitVectorArray::Resize(size_t rows, size_t cols, bool clear) {
380   DCHECK(IsExpandable());
381   if (clear) {
382     Clear();
383   }
384   cols = RoundUp(cols, BitVector::kWordBits);
385   num_columns_ = cols;
386   num_rows_ = rows;
387   // Ensure size
388   GetRawData().SetBit(num_rows_ * num_columns_ - 1);
389   GetRawData().ClearBit(num_rows_ * num_columns_ - 1);
390 }
391 
392 // In order to improve performance we do this in 4-byte blocks. Clang should be
393 // able to optimize this to larger blocks if possible.
UnionRows(size_t dest_row,size_t other)394 void BaseBitVectorArray::UnionRows(size_t dest_row, size_t other) {
395   DCHECK_LT(dest_row, num_rows_);
396   DCHECK_LT(other, num_rows_);
397   size_t block_words = num_columns_ / BitVector::kWordBits;
398   uint32_t* dest =
399       GetRawData().GetRawStorage() + ((dest_row * num_columns_) / BitVector::kWordBits);
400   uint32_t* source = GetRawData().GetRawStorage() + ((other * num_columns_) / BitVector::kWordBits);
401   for (uint32_t i = 0; i < block_words; ++i, ++dest, ++source) {
402     *dest = (*dest) | (*source);
403   }
404 }
405 
406 }  // namespace art
407