Home | History | Annotate | Download | only in base
      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 
     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 
     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 }
     49 
     50 
     51 BitVector::BitVector(const BitVector& src,
     52                      bool expandable,
     53                      Allocator* allocator)
     54   : BitVector(expandable,
     55               allocator,
     56               src.storage_size_,
     57               static_cast<uint32_t*>(allocator->Alloc(src.storage_size_ * kWordBytes))) {
     58   // Direct memcpy would be faster, but this should be fine too and is cleaner.
     59   Copy(&src);
     60 }
     61 
     62 BitVector::~BitVector() {
     63   allocator_->Free(storage_);
     64 }
     65 
     66 bool BitVector::SameBitsSet(const BitVector *src) const {
     67   int our_highest = GetHighestBitSet();
     68   int src_highest = src->GetHighestBitSet();
     69 
     70   // If the highest bit set is different, we are different.
     71   if (our_highest != src_highest) {
     72     return false;
     73   }
     74 
     75   // If the highest bit set is -1, both are cleared, we are the same.
     76   // If the highest bit set is 0, both have a unique bit set, we are the same.
     77   if (our_highest <= 0) {
     78     return true;
     79   }
     80 
     81   // Get the highest bit set's cell's index
     82   // No need of highest + 1 here because it can't be 0 so BitsToWords will work here.
     83   int our_highest_index = BitsToWords(our_highest);
     84 
     85   // This memcmp is enough: we know that the highest bit set is the same for both:
     86   //   - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less.
     87   //      ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index,
     88   //          they are automatically at 0.
     89   return (memcmp(storage_, src->GetRawStorage(), our_highest_index * kWordBytes) == 0);
     90 }
     91 
     92 bool BitVector::IsSubsetOf(const BitVector *other) const {
     93   int this_highest = GetHighestBitSet();
     94   int other_highest = other->GetHighestBitSet();
     95 
     96   // If the highest bit set is -1, this is empty and a trivial subset.
     97   if (this_highest < 0) {
     98     return true;
     99   }
    100 
    101   // If the highest bit set is higher, this cannot be a subset.
    102   if (this_highest > other_highest) {
    103     return false;
    104   }
    105 
    106   // Compare each 32-bit word.
    107   size_t this_highest_index = BitsToWords(this_highest + 1);
    108   for (size_t i = 0; i < this_highest_index; ++i) {
    109     uint32_t this_storage = storage_[i];
    110     uint32_t other_storage = other->storage_[i];
    111     if ((this_storage | other_storage) != other_storage) {
    112       return false;
    113     }
    114   }
    115   return true;
    116 }
    117 
    118 void BitVector::Intersect(const BitVector* src) {
    119   uint32_t src_storage_size = src->storage_size_;
    120 
    121   // Get the minimum size between us and source.
    122   uint32_t min_size = (storage_size_ < src_storage_size) ? storage_size_ : src_storage_size;
    123 
    124   uint32_t idx;
    125   for (idx = 0; idx < min_size; idx++) {
    126     storage_[idx] &= src->GetRawStorageWord(idx);
    127   }
    128 
    129   // Now, due to this being an intersection, there are two possibilities:
    130   //   - Either src was larger than us: we don't care, all upper bits would thus be 0.
    131   //   - Either we are larger than src: we don't care, all upper bits would have been 0 too.
    132   // So all we need to do is set all remaining bits to 0.
    133   for (; idx < storage_size_; idx++) {
    134     storage_[idx] = 0;
    135   }
    136 }
    137 
    138 bool BitVector::Union(const BitVector* src) {
    139   // Get the highest bit to determine how much we need to expand.
    140   int highest_bit = src->GetHighestBitSet();
    141   bool changed = false;
    142 
    143   // If src has no bit set, we are done: there is no need for a union with src.
    144   if (highest_bit == -1) {
    145     return changed;
    146   }
    147 
    148   // Update src_size to how many cells we actually care about: where the bit is + 1.
    149   uint32_t src_size = BitsToWords(highest_bit + 1);
    150 
    151   // Is the storage size smaller than src's?
    152   if (storage_size_ < src_size) {
    153     changed = true;
    154 
    155     EnsureSize(highest_bit);
    156 
    157     // Paranoid: storage size should be big enough to hold this bit now.
    158     DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
    159   }
    160 
    161   for (uint32_t idx = 0; idx < src_size; idx++) {
    162     uint32_t existing = storage_[idx];
    163     uint32_t update = existing | src->GetRawStorageWord(idx);
    164     if (existing != update) {
    165       changed = true;
    166       storage_[idx] = update;
    167     }
    168   }
    169   return changed;
    170 }
    171 
    172 bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) {
    173   // Get the highest bit to determine how much we need to expand.
    174   int highest_bit = union_with->GetHighestBitSet();
    175   bool changed = false;
    176 
    177   // If src has no bit set, we are done: there is no need for a union with src.
    178   if (highest_bit == -1) {
    179     return changed;
    180   }
    181 
    182   // Update union_with_size to how many cells we actually care about: where the bit is + 1.
    183   uint32_t union_with_size = BitsToWords(highest_bit + 1);
    184 
    185   // Is the storage size smaller than src's?
    186   if (storage_size_ < union_with_size) {
    187     EnsureSize(highest_bit);
    188 
    189     // Paranoid: storage size should be big enough to hold this bit now.
    190     DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
    191   }
    192 
    193   uint32_t not_in_size = not_in->GetStorageSize();
    194 
    195   uint32_t idx = 0;
    196   for (; idx < std::min(not_in_size, union_with_size); idx++) {
    197     uint32_t existing = storage_[idx];
    198     uint32_t update = existing |
    199         (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx));
    200     if (existing != update) {
    201       changed = true;
    202       storage_[idx] = update;
    203     }
    204   }
    205 
    206   for (; idx < union_with_size; idx++) {
    207     uint32_t existing = storage_[idx];
    208     uint32_t update = existing | union_with->GetRawStorageWord(idx);
    209     if (existing != update) {
    210       changed = true;
    211       storage_[idx] = update;
    212     }
    213   }
    214   return changed;
    215 }
    216 
    217 void BitVector::Subtract(const BitVector *src) {
    218   uint32_t src_size = src->storage_size_;
    219 
    220   // We only need to operate on bytes up to the smaller of the sizes of the two operands.
    221   unsigned int min_size = (storage_size_ > src_size) ? src_size : storage_size_;
    222 
    223   // Difference until max, we know both accept it:
    224   //   There is no need to do more:
    225   //     If we are bigger than src, the upper bits are unchanged.
    226   //     If we are smaller than src, the non-existant upper bits are 0 and thus can't get subtracted.
    227   for (uint32_t idx = 0; idx < min_size; idx++) {
    228     storage_[idx] &= (~(src->GetRawStorageWord(idx)));
    229   }
    230 }
    231 
    232 uint32_t BitVector::NumSetBits() const {
    233   uint32_t count = 0;
    234   for (uint32_t word = 0; word < storage_size_; word++) {
    235     count += POPCOUNT(storage_[word]);
    236   }
    237   return count;
    238 }
    239 
    240 uint32_t BitVector::NumSetBits(uint32_t end) const {
    241   DCHECK_LE(end, storage_size_ * kWordBits);
    242   return NumSetBits(storage_, end);
    243 }
    244 
    245 void BitVector::SetInitialBits(uint32_t num_bits) {
    246   // If num_bits is 0, clear everything.
    247   if (num_bits == 0) {
    248     ClearAllBits();
    249     return;
    250   }
    251 
    252   // Set the highest bit we want to set to get the BitVector allocated if need be.
    253   SetBit(num_bits - 1);
    254 
    255   uint32_t idx;
    256   // We can set every storage element with -1.
    257   for (idx = 0; idx < WordIndex(num_bits); idx++) {
    258     storage_[idx] = std::numeric_limits<uint32_t>::max();
    259   }
    260 
    261   // Handle the potentially last few bits.
    262   uint32_t rem_num_bits = num_bits & 0x1f;
    263   if (rem_num_bits != 0) {
    264     storage_[idx] = (1U << rem_num_bits) - 1;
    265     ++idx;
    266   }
    267 
    268   // Now set the upper ones to 0.
    269   for (; idx < storage_size_; idx++) {
    270     storage_[idx] = 0;
    271   }
    272 }
    273 
    274 int BitVector::GetHighestBitSet() const {
    275   unsigned int max = storage_size_;
    276   for (int idx = max - 1; idx >= 0; idx--) {
    277     // If not 0, we have more work: check the bits.
    278     uint32_t value = storage_[idx];
    279 
    280     if (value != 0) {
    281       // Return highest bit set in value plus bits from previous storage indexes.
    282       return 31 - CLZ(value) + (idx * kWordBits);
    283     }
    284   }
    285 
    286   // All zero, therefore return -1.
    287   return -1;
    288 }
    289 
    290 void BitVector::Copy(const BitVector *src) {
    291   // Get highest bit set, we only need to copy till then.
    292   int highest_bit = src->GetHighestBitSet();
    293 
    294   // If nothing is set, clear everything.
    295   if (highest_bit == -1) {
    296     ClearAllBits();
    297     return;
    298   }
    299 
    300   // Set upper bit to ensure right size before copy.
    301   SetBit(highest_bit);
    302 
    303   // Now set until highest bit's storage.
    304   uint32_t size = 1 + (highest_bit / kWordBits);
    305   memcpy(storage_, src->GetRawStorage(), kWordBytes * size);
    306 
    307   // Set upper bits to 0.
    308   uint32_t left = storage_size_ - size;
    309 
    310   if (left > 0) {
    311     memset(storage_ + size, 0, kWordBytes * left);
    312   }
    313 }
    314 
    315 #if defined(__clang__) && defined(__ARM_64BIT_STATE)
    316 // b/19180814 When POPCOUNT is inlined, boot up failed on arm64 devices.
    317 __attribute__((optnone))
    318 #endif
    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 
    333 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 
    339 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 
    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 
    375 Allocator* BitVector::GetAllocator() const {
    376   return allocator_;
    377 }
    378 
    379 }  // namespace art
    380