1 files changed, 155 insertions, 0 deletions
diff --git a/compiler/utils/bit_vector.cc b/compiler/utils/bit_vector.cc
new file mode 100644
index 0000000000..81a639a050
--- /dev/null
+++ b/compiler/utils/bit_vector.cc
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "bit_vector.h"
+
+namespace art {
+
+// TODO: profile to make sure this is still a win relative to just using shifted masks.
+static uint32_t check_masks[32] = {
+  0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010,
+  0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200,
+  0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
+  0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000,
+  0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000,
+  0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
+  0x40000000, 0x80000000 };
+
+static inline uint32_t BitsToWords(unsigned int bits) {
+  return (bits + 31) >> 5;
+}
+
+// TODO: replace excessive argument defaulting when we are at gcc 4.7
+// or later on host with delegating constructor support. Specifically,
+// starts_bits and storage_size/storage are mutually exclusive.
+BitVector::BitVector(unsigned int start_bits,
+                     bool expandable,
+                     Allocator* allocator,
+                     uint32_t storage_size,
+                     uint32_t* storage)
+  : allocator_(allocator),
+    expandable_(expandable),
+    storage_size_(storage_size),
+    storage_(storage) {
+  DCHECK_EQ(sizeof(storage_[0]), 4U);  // Assuming 32-bit units.
+  if (storage_ == NULL) {
+    storage_size_ = BitsToWords(start_bits);
+    storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * sizeof(uint32_t)));
+  }
+}
+
+BitVector::~BitVector() {
+  allocator_->Free(storage_);
+}
+
+/*
+ * Determine whether or not the specified bit is set.
+ */
+bool BitVector::IsBitSet(unsigned int num) {
+  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
+
+  unsigned int val = storage_[num >> 5] & check_masks[num & 0x1f];
+  return (val != 0);
+}
+
+// Mark all bits bit as "clear".
+void BitVector::ClearAllBits() {
+  memset(storage_, 0, storage_size_ * sizeof(uint32_t));
+}
+
+// Mark the specified bit as "set".
+/*
+ * TUNING: this could have pathologically bad growth/expand behavior.  Make sure we're
+ * not using it badly or change resize mechanism.
+ */
+void BitVector::SetBit(unsigned int num) {
+  if (num >= storage_size_ * sizeof(uint32_t) * 8) {
+    DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
+
+    /* Round up to word boundaries for "num+1" bits */
+    unsigned int new_size = BitsToWords(num + 1);
+    DCHECK_GT(new_size, storage_size_);
+    uint32_t *new_storage =
+        static_cast<uint32_t*>(allocator_->Alloc(new_size * sizeof(uint32_t)));
+    memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t));
+    // Zero out the new storage words.
+    memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(uint32_t));
+    // TOTO: collect stats on space wasted because of resize.
+    storage_ = new_storage;
+    storage_size_ = new_size;
+  }
+
+  storage_[num >> 5] |= check_masks[num & 0x1f];
+}
+
+// Mark the specified bit as "unset".
+void BitVector::ClearBit(unsigned int num) {
+  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
+  storage_[num >> 5] &= ~check_masks[num & 0x1f];
+}
+
+// Intersect with another bit vector.  Sizes and expandability must be the same.
+void BitVector::Intersect(const BitVector* src) {
+  DCHECK_EQ(storage_size_, src->GetStorageSize());
+  DCHECK_EQ(expandable_, src->IsExpandable());
+  for (unsigned int idx = 0; idx < storage_size_; idx++) {
+    storage_[idx] &= src->GetRawStorageWord(idx);
+  }
+}
+
+/*
+ * Union with another bit vector.  Sizes and expandability must be the same.
+ */
+void BitVector::Union(const BitVector* src) {
+  DCHECK_EQ(storage_size_, src->GetStorageSize());
+  DCHECK_EQ(expandable_, src->IsExpandable());
+  for (unsigned int idx = 0; idx < storage_size_; idx++) {
+    storage_[idx] |= src->GetRawStorageWord(idx);
+  }
+}
+
+// Count the number of bits that are set.
+int BitVector::NumSetBits() {
+  unsigned int count = 0;
+
+  for (unsigned int word = 0; word < storage_size_; word++) {
+    count += __builtin_popcount(storage_[word]);
+  }
+  return count;
+}
+
+BitVector::Iterator* BitVector::GetIterator() {
+  return new (allocator_) Iterator(this);
+}
+
+/*
+ * Mark specified number of bits as "set". Cannot set all bits like ClearAll
+ * since there might be unused bits - setting those to one will confuse the
+ * iterator.
+ */
+void BitVector::SetInitialBits(unsigned int num_bits) {
+  DCHECK_LE(BitsToWords(num_bits), storage_size_);
+  unsigned int idx;
+  for (idx = 0; idx < (num_bits >> 5); idx++) {
+    storage_[idx] = -1;
+  }
+  unsigned int rem_num_bits = num_bits & 0x1f;
+  if (rem_num_bits) {
+    storage_[idx] = (1 << rem_num_bits) - 1;
+  }
+}
+
+}  // namespace art