commit ad0d30a2a2141aa0e9da9e97993ce20e4d8e056e
author Jean Christophe Beyler <jean.christophe.beyler@intel.com> Thu Jan 16 09:00:18 2014 -0800
committer Jean Christophe Beyler <jean.christophe.beyler@intel.com> Fri Jan 17 13:37:14 2014 -0800
tree 90af62fbfc9a05b8d29bdf54d96f128183bce92b
parent 1776f50b5b99782278d7f3d354fa956d9066c903

Update to the BitVector Implementation

IsBitSet:
- If the index requested is above the size, return false.

ClearBit:
- If the index requested is above the size, ignore.

Added SameBitsSet:
- Check the bits set disregarding size and expandable.

Intersect and Union:
- removed the requirement of same size.
- handles case where the sizes are not the same.

Added Subtract between BitVectors.

SetInitialBits:
- Now requests expansion if above the bits available.
- Clears upper bits.

Added GetHighestBitSet.

ClearBit:
- If we clear above the size, it is fine, it has not been set yet.

Copy:
- Supposes it is well allocated.
- It used to just copy what was available in destination without checking source's size.
- Now actually allocate the destination to make sure it holds enough space.
- Set parameter to const.

General:
- Moved sizeof(uint32_t) to sizeof(*storage_) for future maintenance.

Change-Id: Iebb214632482c46807deca957f5b6dc892a61a84

runtime/base/bit_vector.h

diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 74bec08..c8f285e 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -46,7 +46,9 @@
           DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8);
           DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage());
 
-          if (UNLIKELY(bit_index_ >= bit_size_)) return -1;
+          if (UNLIKELY(bit_index_ >= bit_size_)) {
+            return -1;
+          }
 
           uint32_t word_index = bit_index_ / 32;
           uint32_t word = bit_storage_[word_index];
@@ -89,7 +91,7 @@
               bool expandable,
               Allocator* allocator,
               uint32_t storage_size = 0,
-              uint32_t* storage = NULL);
+              uint32_t* storage = nullptr);
 
     virtual ~BitVector();
 
@@ -98,17 +100,24 @@
     bool IsBitSet(uint32_t num) const;
     void ClearAllBits();
     void SetInitialBits(uint32_t num_bits);
-    void Copy(BitVector* src) {
-      memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_);
-    }
+
+    void Copy(const BitVector* src);
     void Intersect(const BitVector* src2);
     void Union(const BitVector* src);
+    void Subtract(const BitVector* src);
     // Are we equal to another bit vector?  Note: expandability attributes must also match.
     bool Equal(const BitVector* src) {
       return (storage_size_ == src->GetStorageSize()) &&
         (expandable_ == src->IsExpandable()) &&
         (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0);
     }
+
+    /**
+     * @brief Are all the bits set the same?
+     * @details expandability and size can differ as long as the same bits are set.
+     */
+    bool SameBitsSet(const BitVector *src);
+
     uint32_t NumSetBits() const;
     uint32_t NumSetBits(uint32_t num) const;
 
@@ -121,6 +130,11 @@
     const uint32_t* GetRawStorage() const { return storage_; }
     size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); }
 
+    /**
+     * @return the highest bit set, -1 if none are set
+     */
+    int GetHighestBitSet() const;
+
   private:
     Allocator* const allocator_;
     const bool expandable_;         // expand bitmap if we run out?