diff options
author | Jean Christophe Beyler <jean.christophe.beyler@intel.com> | 2014-04-15 15:54:35 -0700 |
---|---|---|
committer | Jean Christophe Beyler <jean.christophe.beyler@intel.com> | 2014-04-24 12:20:40 -0700 |
commit | 5afa08f95d43dd24fb4b3d7a08aa1ec23386ad54 (patch) | |
tree | 28d388989be9ccdfce387728f63820689c29e9ca /runtime/base | |
parent | 1c17753ca9cf125ffd1fa47f34650fb6f4005409 (diff) | |
download | art-5afa08f95d43dd24fb4b3d7a08aa1ec23386ad54.zip art-5afa08f95d43dd24fb4b3d7a08aa1ec23386ad54.tar.gz art-5afa08f95d43dd24fb4b3d7a08aa1ec23386ad54.tar.bz2 |
ART: Bitvector extensions for dumping and size handling
- Added dumping functions and the ensure size and clear function.
- Fixed a bug in union where if a bit is not set in the source, an buffer
overflow can occur later down.
Change-Id: Iff40529f3a8970a1ce2dd5c591f659f71924dea3
Signed-off-by: Jean Christophe Beyler <jean.christophe.beyler@intel.com>
Signed-off-by: Razvan A Lupusoru <razvan.a.lupusoru@intel.com>
Signed-off-by: Yixin Shou <yixin.shou@intel.com>
Signed-off-by: Chao-ying Fu <chao-ying.fu@intel.com>
Signed-off-by: Udayan Banerji <udayan.banerji@intel.com>
Diffstat (limited to 'runtime/base')
-rw-r--r-- | runtime/base/bit_vector.cc | 80 | ||||
-rw-r--r-- | runtime/base/bit_vector.h | 8 |
2 files changed, 72 insertions, 16 deletions
diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc index d8ef962..12c0352 100644 --- a/runtime/base/bit_vector.cc +++ b/runtime/base/bit_vector.cc @@ -157,33 +157,27 @@ void BitVector::Intersect(const BitVector* src) { * Union with another bit vector. */ void BitVector::Union(const BitVector* src) { - uint32_t src_size = src->storage_size_; + // Get the highest bit to determine how much we need to expand. + int highest_bit = src->GetHighestBitSet(); + + // If src has no bit set, we are done: there is no need for a union with src. + if (highest_bit == -1) { + return; + } - // Get our size, we use this variable for the last loop of the method: - // - It can change in the if block if src is of a different size. - uint32_t size = storage_size_; + // Update src_size to how many cells we actually care about: where the bit is + 1. + uint32_t src_size = BitsToWords(highest_bit + 1); // Is the storage size smaller than src's? if (storage_size_ < src_size) { - // Get the highest bit to determine how much we need to expand. - int highest_bit = src->GetHighestBitSet(); - - // If src has no bit set, we are done: there is no need for a union with src. - if (highest_bit == -1) { - return; - } - // Set it to reallocate. SetBit(highest_bit); // Paranoid: storage size should be big enough to hold this bit now. DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8); - - // Update the size, our size can now not be bigger than the src size - size = storage_size_; } - for (uint32_t idx = 0; idx < size; idx++) { + for (uint32_t idx = 0; idx < src_size; idx++) { storage_[idx] |= src->GetRawStorageWord(idx); } } @@ -284,6 +278,23 @@ int BitVector::GetHighestBitSet() const { return -1; } +bool BitVector::EnsureSizeAndClear(unsigned int num) { + // Check if the bitvector is expandable. + if (IsExpandable() == false) { + return false; + } + + if (num > 0) { + // Now try to expand by setting the last bit. + SetBit(num - 1); + } + + // We must clear all bits as per our specification. + ClearAllBits(); + + return true; +} + void BitVector::Copy(const BitVector *src) { // Get highest bit set, we only need to copy till then. int highest_bit = src->GetHighestBitSet(); @@ -328,4 +339,41 @@ uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) { return count; } +void BitVector::Dump(std::ostream& os, const char *prefix) { + std::ostringstream buffer; + DumpHelper(buffer, prefix); + os << buffer << std::endl; +} + +void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) { + std::ostringstream buffer; + Dump(buffer, prefix); + + // Now print it to the file. + fprintf(file, " {%s}", buffer.str().c_str()); + + // If it isn't the last entry, add a |. + if (last_entry == false) { + fprintf(file, "|"); + } + + // Add the \n. + fprintf(file, "\\\n"); +} + +void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) { + // Initialize it. + if (prefix != nullptr) { + buffer << prefix; + } + + int max = GetHighestBitSet(); + + for (int i = 0; i <= max; i++) { + if (IsBitSet(i)) { + buffer << i << " "; + } + } +} + } // namespace art diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h index a496dbd..db29c49 100644 --- a/runtime/base/bit_vector.h +++ b/runtime/base/bit_vector.h @@ -142,6 +142,14 @@ class BitVector { // Number of bits set in range [0, end) in storage. (No range check.) static uint32_t NumSetBits(const uint32_t* storage, uint32_t end); + bool EnsureSizeAndClear(unsigned int num); + + void Dump(std::ostream& os, const char* prefix); + void DumpDot(FILE* file, const char* prefix, bool last_entry = false); + + protected: + void DumpHelper(std::ostringstream& buffer, const char* prefix); + private: Allocator* const allocator_; const bool expandable_; // expand bitmap if we run out? |