5 #ifndef V8_BIT_VECTOR_H_ 6 #define V8_BIT_VECTOR_H_ 8 #include "src/allocation.h" 9 #include "src/zone/zone.h" 29 current_value_(target->is_inline() ? target->data_.inline_
30 : target->data_.ptr_[0]),
36 bool Done()
const {
return current_index_ >= target_->data_length_; }
46 while ((val & 0xFF) == 0) {
53 while ((val & 0x1) == 0) {
68 static const int kDataLengthForInline = 1;
69 static const int kDataBits = kPointerSize * 8;
70 static const int kDataBitShift = kPointerSize == 8 ? 6 : 5;
73 BitVector() : length_(0), data_length_(kDataLengthForInline), data_(0) {}
76 : length_(length), data_length_(SizeFor(length)), data_(0) {
79 data_.ptr_ = zone->NewArray<
uintptr_t>(data_length_);
85 BitVector(
const BitVector& other, Zone* zone)
86 : length_(other.length_),
87 data_length_(other.data_length_),
88 data_(other.data_.inline_) {
90 data_.ptr_ = zone->NewArray<
uintptr_t>(data_length_);
91 for (
int i = 0;
i < other.data_length_;
i++) {
92 data_.ptr_[
i] = other.data_.ptr_[
i];
97 static int SizeFor(
int length) {
98 if (length <= kDataBits) {
99 return kDataLengthForInline;
102 int data_length = 1 + ((length - 1) / kDataBits);
103 DCHECK_GT(data_length, kDataLengthForInline);
107 void CopyFrom(
const BitVector& other) {
108 DCHECK_LE(other.length(), length());
109 CopyFrom(other.data_, other.data_length_);
112 void Resize(
int new_length, Zone* zone) {
113 DCHECK_GT(new_length, length());
114 int new_data_length = SizeFor(new_length);
115 if (new_data_length > data_length_) {
116 DataStorage old_data = data_;
117 int old_data_length = data_length_;
120 DCHECK_GT(new_data_length, kDataLengthForInline);
121 data_.ptr_ = zone->NewArray<
uintptr_t>(new_data_length);
122 data_length_ = new_data_length;
123 CopyFrom(old_data, old_data_length);
125 length_ = new_length;
128 bool Contains(
int i)
const {
129 DCHECK(
i >= 0 &&
i < length());
130 uintptr_t block = is_inline() ? data_.inline_ : data_.ptr_[
i / kDataBits];
131 return (block & (kOne << (
i % kDataBits))) != 0;
135 DCHECK(
i >= 0 &&
i < length());
137 data_.inline_ |= (kOne <<
i);
139 data_.ptr_[
i / kDataBits] |= (kOne << (
i % kDataBits));
150 memset(data_.ptr_, -1,
sizeof(
uintptr_t) * data_length_);
155 DCHECK(
i >= 0 &&
i < length());
157 data_.inline_ &= ~(kOne <<
i);
159 data_.ptr_[
i / kDataBits] &= ~(kOne << (
i % kDataBits));
163 void Union(
const BitVector& other) {
164 DCHECK(other.length() == length());
166 DCHECK(other.is_inline());
167 data_.inline_ |= other.data_.inline_;
169 for (
int i = 0;
i < data_length_;
i++) {
170 data_.ptr_[
i] |= other.data_.ptr_[
i];
175 bool UnionIsChanged(
const BitVector& other) {
176 DCHECK(other.length() == length());
178 DCHECK(other.is_inline());
180 data_.inline_ |= other.data_.inline_;
181 return data_.inline_ != old_data;
183 bool changed =
false;
184 for (
int i = 0;
i < data_length_;
i++) {
186 data_.ptr_[
i] |= other.data_.ptr_[
i];
187 if (data_.ptr_[
i] != old_data) changed =
true;
193 void Intersect(
const BitVector& other) {
194 DCHECK(other.length() == length());
196 DCHECK(other.is_inline());
197 data_.inline_ &= other.data_.inline_;
199 for (
int i = 0;
i < data_length_;
i++) {
200 data_.ptr_[
i] &= other.data_.ptr_[
i];
205 bool IntersectIsChanged(
const BitVector& other) {
206 DCHECK(other.length() == length());
208 DCHECK(other.is_inline());
210 data_.inline_ &= other.data_.inline_;
211 return data_.inline_ != old_data;
213 bool changed =
false;
214 for (
int i = 0;
i < data_length_;
i++) {
216 data_.ptr_[
i] &= other.data_.ptr_[
i];
217 if (data_.ptr_[
i] != old_data) changed =
true;
223 void Subtract(
const BitVector& other) {
224 DCHECK(other.length() == length());
226 DCHECK(other.is_inline());
227 data_.inline_ &= ~other.data_.inline_;
229 for (
int i = 0;
i < data_length_;
i++) {
230 data_.ptr_[
i] &= ~other.data_.ptr_[
i];
239 for (
int i = 0;
i < data_length_;
i++) {
245 bool IsEmpty()
const {
247 return data_.inline_ == 0;
249 for (
int i = 0;
i < data_length_;
i++) {
250 if (data_.ptr_[
i] != 0)
return false;
256 bool Equals(
const BitVector& other)
const {
257 DCHECK(other.length() == length());
259 DCHECK(other.is_inline());
260 return data_.inline_ == other.data_.inline_;
262 for (
int i = 0;
i < data_length_;
i++) {
263 if (data_.ptr_[
i] != other.data_.ptr_[
i])
return false;
271 int length()
const {
return length_; }
282 bool is_inline()
const {
return data_length_ == kDataLengthForInline; }
284 void CopyFrom(DataStorage other_data,
int other_data_length) {
285 DCHECK_LE(other_data_length, data_length_);
288 DCHECK_EQ(other_data_length, kDataLengthForInline);
289 data_.inline_ = other_data.inline_;
290 }
else if (other_data_length == kDataLengthForInline) {
291 data_.ptr_[0] = other_data.inline_;
292 for (
int i = 1;
i < data_length_;
i++) {
296 for (
int i = 0;
i < other_data_length;
i++) {
297 data_.ptr_[
i] = other_data.ptr_[
i];
299 for (
int i = other_data_length;
i < data_length_;
i++) {
305 DISALLOW_COPY_AND_ASSIGN(BitVector);
313 : it_(target->bits_ ==
nullptr ? new (zone)
BitVector(1, zone)
315 bool Done()
const {
return it_.Done(); }
316 void Advance() { it_.Advance(); }
317 int Current()
const {
return it_.Current(); }
325 : bits_(new (zone)
BitVector(length, zone)) {}
327 bool Contains(
int value)
const {
328 if (!InBitsRange(value))
return false;
329 return bits_->Contains(value);
332 void Add(
int value, Zone* zone) {
333 EnsureCapacity(value, zone);
337 void Union(
const GrowableBitVector& other, Zone* zone) {
338 for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
339 Add(it.Current(), zone);
344 if (bits_ !=
nullptr) bits_->Clear();
348 static const int kInitialLength = 1024;
350 bool InBitsRange(
int value)
const {
351 return bits_ !=
nullptr && bits_->length() > value;
354 void EnsureCapacity(
int value, Zone* zone) {
355 if (InBitsRange(value))
return;
356 int new_length = bits_ ==
nullptr ? kInitialLength : bits_->length();
357 while (new_length <= value) new_length *= 2;
359 if (bits_ ==
nullptr) {
360 bits_ =
new (zone) BitVector(new_length, zone);
362 bits_->Resize(new_length, zone);
372 #endif // V8_BIT_VECTOR_H_