bit_vector.h

Go to the documentation of this file.

// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
 
#ifndef RUNTIME_VM_BIT_VECTOR_H_
#define RUNTIME_VM_BIT_VECTOR_H_
 
#include "vm/allocation.h"
#include "vm/isolate.h"
#include "vm/zone.h"
 
namespace dart {
 
// Bit vector implementation.
class BitVector : public ZoneAllocated {
 public:
  // Iterator for the elements of this BitVector.
  class Iterator : public ValueObject {
   public:
    explicit Iterator(BitVector* target)
        : target_(target),
          bit_index_(-1),
          word_index_(0),
          current_word_(target->data_[0]) {
      ASSERT(target->data_length_ > 0);
      Advance();
    }
    ~Iterator() {}
 
    bool Done() const { return word_index_ >= target_->data_length_; }
    void Advance();
 
    intptr_t Current() const {
      ASSERT(!Done());
      return bit_index_;
    }
 
   private:
    BitVector* target_;
    intptr_t bit_index_;
    intptr_t word_index_;
    uword current_word_;
 
    friend class BitVector;
  };
 
  BitVector(Zone* zone, intptr_t length)
      : length_(length),
        data_length_(SizeFor(length)),
        data_(zone->Alloc<uword>(data_length_)) {
    Clear();
  }
 
  void CopyFrom(const BitVector* other) {
    Clear();
    AddAll(other);
  }
 
  static intptr_t SizeFor(intptr_t length) {
    return 1 + ((length - 1) / kBitsPerWord);
  }
 
  void Add(intptr_t i) {
    ASSERT(i >= 0 && i < length());
    data_[i / kBitsPerWord] |= (static_cast<uword>(1) << (i % kBitsPerWord));
  }
 
  void Remove(intptr_t i) {
    ASSERT(i >= 0 && i < length());
    data_[i / kBitsPerWord] &= ~(static_cast<uword>(1) << (i % kBitsPerWord));
  }
 
  void Set(intptr_t i, bool value) { value ? Add(i) : Remove(i); }
 
  bool Equals(const BitVector& other) const;
 
  // Add all elements that are in the bitvector from.
  bool AddAll(const BitVector* from);
 
  // Remove all elements that are in the bitvector from.
  bool RemoveAll(const BitVector* from);
 
  // From the bitvector gen add those elements that are not in the
  // bitvector kill.
  bool KillAndAdd(BitVector* kill, BitVector* gen);
 
  void Intersect(const BitVector* other);
 
  bool IsEmpty() const;
 
  bool Contains(intptr_t i) const {
    ASSERT(i >= 0 && i < length());
    uword block = data_[i / kBitsPerWord];
    return (block & (static_cast<uword>(1) << (i % kBitsPerWord))) != 0;
  }
 
  bool SubsetOf(const BitVector& other) {
    ASSERT(length_ == other.length_);
    for (intptr_t i = 0; i < data_length_; ++i) {
      if ((data_[i] & other.data_[i]) != data_[i]) return false;
    }
    return true;
  }
 
  void Clear() {
    for (intptr_t i = 0; i < data_length_; i++) {
      data_[i] = 0;
    }
  }
 
  void SetAll() {
    for (intptr_t i = 0; i < data_length_; i++) {
      data_[i] = static_cast<uword>(-1);
    }
  }
 
  intptr_t length() const { return length_; }
 
  void Print() const;
 
 private:
  intptr_t length_;
  intptr_t data_length_;
  uword* data_;
 
  DISALLOW_COPY_AND_ASSIGN(BitVector);
};
 
}  // namespace dart
 
#endif  // RUNTIME_VM_BIT_VECTOR_H_