1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/bit_vector.h"
6#include "vm/log.h"
7#include "vm/os.h"
8
9namespace dart {
10
11void BitVector::Iterator::Advance() {
12 ++bit_index_;
13 // Skip zero words.
14 if (current_word_ == 0) {
15 do {
16 ++word_index_;
17 if (Done()) return;
18 current_word_ = target_->data_[word_index_];
19 } while (current_word_ == 0);
20 bit_index_ = word_index_ * kBitsPerWord;
21 }
22 // Skip zero bytes.
23 while ((current_word_ & 0xff) == 0) {
24 current_word_ >>= 8;
25 bit_index_ += 8;
26 }
27 // Skip zero bits.
28 while ((current_word_ & 0x1) == 0) {
29 current_word_ >>= 1;
30 ++bit_index_;
31 }
32 current_word_ = current_word_ >> 1;
33}
34
35bool BitVector::Equals(const BitVector& other) const {
36 if (length_ != other.length_) return false;
37 intptr_t i = 0;
38 for (; i < data_length_ - 1; i++) {
39 if (data_[i] != other.data_[i]) return false;
40 }
41 if (i < data_length_) {
42 if (length_ % kBitsPerWord == 0) return data_[i] == other.data_[i];
43
44 // Don't compare bits beyond length_.
45 const intptr_t shift_size = kBitsPerWord - (length_ % kBitsPerWord);
46 const uword mask = static_cast<uword>(-1) >> shift_size;
47 if ((data_[i] & mask) != (other.data_[i] & mask)) return false;
48 }
49 return true;
50}
51
52bool BitVector::AddAll(const BitVector* from) {
53 ASSERT(data_length_ == from->data_length_);
54 bool changed = false;
55 for (intptr_t i = 0; i < data_length_; i++) {
56 const uword before = data_[i];
57 const uword after = data_[i] | from->data_[i];
58 if (before != after) {
59 changed = true;
60 data_[i] = after;
61 }
62 }
63 return changed;
64}
65
66bool BitVector::RemoveAll(const BitVector* from) {
67 ASSERT(data_length_ == from->data_length_);
68 bool changed = false;
69 for (intptr_t i = 0; i < data_length_; i++) {
70 const uword before = data_[i];
71 const uword after = data_[i] & ~from->data_[i];
72 if (before != after) {
73 changed = true;
74 data_[i] = after;
75 }
76 }
77 return changed;
78}
79
80bool BitVector::KillAndAdd(BitVector* kill, BitVector* gen) {
81 ASSERT(data_length_ == kill->data_length_);
82 ASSERT(data_length_ == gen->data_length_);
83 bool changed = false;
84 for (intptr_t i = 0; i < data_length_; i++) {
85 const uword before = data_[i];
86 const uword after = data_[i] | (gen->data_[i] & ~kill->data_[i]);
87 if (before != after) changed = true;
88 data_[i] = after;
89 }
90 return changed;
91}
92
93void BitVector::Intersect(const BitVector* other) {
94 ASSERT(other->length() == length());
95 for (intptr_t i = 0; i < data_length_; i++) {
96 data_[i] = data_[i] & other->data_[i];
97 }
98}
99
100bool BitVector::IsEmpty() const {
101 for (intptr_t i = 0; i < data_length_; i++) {
102 if (data_[i] != 0) {
103 return false;
104 }
105 }
106 return true;
107}
108
109void BitVector::Print() const {
110 THR_Print("[");
111 for (intptr_t i = 0; i < length_; i++) {
112 THR_Print(Contains(i) ? "1" : "0");
113 }
114 THR_Print("]");
115}
116
117} // namespace dart
118