OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/bit_vector.h" | 5 #include "vm/bit_vector.h" |
6 | 6 |
7 #include "vm/os.h" | 7 #include "vm/os.h" |
8 | 8 |
9 namespace dart { | 9 namespace dart { |
10 | 10 |
(...skipping 14 matching lines...) Expand all Loading... |
25 bit_index_ += 8; | 25 bit_index_ += 8; |
26 } | 26 } |
27 // Skip zero bits. | 27 // Skip zero bits. |
28 while ((current_word_ & 0x1) == 0) { | 28 while ((current_word_ & 0x1) == 0) { |
29 current_word_ >>= 1; | 29 current_word_ >>= 1; |
30 ++bit_index_; | 30 ++bit_index_; |
31 } | 31 } |
32 current_word_ = current_word_ >> 1; | 32 current_word_ = current_word_ >> 1; |
33 } | 33 } |
34 | 34 |
35 | |
36 bool BitVector::Equals(const BitVector& other) const { | 35 bool BitVector::Equals(const BitVector& other) const { |
37 if (length_ != other.length_) return false; | 36 if (length_ != other.length_) return false; |
38 intptr_t i = 0; | 37 intptr_t i = 0; |
39 for (; i < data_length_ - 1; i++) { | 38 for (; i < data_length_ - 1; i++) { |
40 if (data_[i] != other.data_[i]) return false; | 39 if (data_[i] != other.data_[i]) return false; |
41 } | 40 } |
42 if (i < data_length_) { | 41 if (i < data_length_) { |
43 // Don't compare bits beyond length_. | 42 // Don't compare bits beyond length_. |
44 const intptr_t shift_size = (kBitsPerWord - length_) & (kBitsPerWord - 1); | 43 const intptr_t shift_size = (kBitsPerWord - length_) & (kBitsPerWord - 1); |
45 const uword mask = static_cast<uword>(-1) >> shift_size; | 44 const uword mask = static_cast<uword>(-1) >> shift_size; |
46 if ((data_[i] & mask) != (other.data_[i] & mask)) return false; | 45 if ((data_[i] & mask) != (other.data_[i] & mask)) return false; |
47 } | 46 } |
48 return true; | 47 return true; |
49 } | 48 } |
50 | 49 |
51 | |
52 bool BitVector::AddAll(const BitVector* from) { | 50 bool BitVector::AddAll(const BitVector* from) { |
53 ASSERT(data_length_ == from->data_length_); | 51 ASSERT(data_length_ == from->data_length_); |
54 bool changed = false; | 52 bool changed = false; |
55 for (intptr_t i = 0; i < data_length_; i++) { | 53 for (intptr_t i = 0; i < data_length_; i++) { |
56 const uword before = data_[i]; | 54 const uword before = data_[i]; |
57 const uword after = data_[i] | from->data_[i]; | 55 const uword after = data_[i] | from->data_[i]; |
58 if (before != after) { | 56 if (before != after) { |
59 changed = true; | 57 changed = true; |
60 data_[i] = after; | 58 data_[i] = after; |
61 } | 59 } |
62 } | 60 } |
63 return changed; | 61 return changed; |
64 } | 62 } |
65 | 63 |
66 | |
67 bool BitVector::RemoveAll(const BitVector* from) { | 64 bool BitVector::RemoveAll(const BitVector* from) { |
68 ASSERT(data_length_ == from->data_length_); | 65 ASSERT(data_length_ == from->data_length_); |
69 bool changed = false; | 66 bool changed = false; |
70 for (intptr_t i = 0; i < data_length_; i++) { | 67 for (intptr_t i = 0; i < data_length_; i++) { |
71 const uword before = data_[i]; | 68 const uword before = data_[i]; |
72 const uword after = data_[i] & ~from->data_[i]; | 69 const uword after = data_[i] & ~from->data_[i]; |
73 if (before != after) { | 70 if (before != after) { |
74 changed = true; | 71 changed = true; |
75 data_[i] = after; | 72 data_[i] = after; |
76 } | 73 } |
77 } | 74 } |
78 return changed; | 75 return changed; |
79 } | 76 } |
80 | 77 |
81 bool BitVector::KillAndAdd(BitVector* kill, BitVector* gen) { | 78 bool BitVector::KillAndAdd(BitVector* kill, BitVector* gen) { |
82 ASSERT(data_length_ == kill->data_length_); | 79 ASSERT(data_length_ == kill->data_length_); |
83 ASSERT(data_length_ == gen->data_length_); | 80 ASSERT(data_length_ == gen->data_length_); |
84 bool changed = false; | 81 bool changed = false; |
85 for (intptr_t i = 0; i < data_length_; i++) { | 82 for (intptr_t i = 0; i < data_length_; i++) { |
86 const uword before = data_[i]; | 83 const uword before = data_[i]; |
87 const uword after = data_[i] | (gen->data_[i] & ~kill->data_[i]); | 84 const uword after = data_[i] | (gen->data_[i] & ~kill->data_[i]); |
88 if (before != after) changed = true; | 85 if (before != after) changed = true; |
89 data_[i] = after; | 86 data_[i] = after; |
90 } | 87 } |
91 return changed; | 88 return changed; |
92 } | 89 } |
93 | 90 |
94 | |
95 void BitVector::Intersect(const BitVector* other) { | 91 void BitVector::Intersect(const BitVector* other) { |
96 ASSERT(other->length() == length()); | 92 ASSERT(other->length() == length()); |
97 for (intptr_t i = 0; i < data_length_; i++) { | 93 for (intptr_t i = 0; i < data_length_; i++) { |
98 data_[i] = data_[i] & other->data_[i]; | 94 data_[i] = data_[i] & other->data_[i]; |
99 } | 95 } |
100 } | 96 } |
101 | 97 |
102 | |
103 bool BitVector::IsEmpty() const { | 98 bool BitVector::IsEmpty() const { |
104 for (intptr_t i = 0; i < data_length_; i++) { | 99 for (intptr_t i = 0; i < data_length_; i++) { |
105 if (data_[i] != 0) { | 100 if (data_[i] != 0) { |
106 return false; | 101 return false; |
107 } | 102 } |
108 } | 103 } |
109 return true; | 104 return true; |
110 } | 105 } |
111 | 106 |
112 | |
113 void BitVector::Print() const { | 107 void BitVector::Print() const { |
114 OS::Print("["); | 108 OS::Print("["); |
115 for (intptr_t i = 0; i < length_; i++) { | 109 for (intptr_t i = 0; i < length_; i++) { |
116 OS::Print(Contains(i) ? "1" : "0"); | 110 OS::Print(Contains(i) ? "1" : "0"); |
117 } | 111 } |
118 OS::Print("]"); | 112 OS::Print("]"); |
119 } | 113 } |
120 | 114 |
121 } // namespace dart | 115 } // namespace dart |
OLD | NEW |