1// Copyright 2012 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_BIT_VECTOR_H_
6#define V8_BIT_VECTOR_H_
7
8#include "src/allocation.h"
9#include "src/zone/zone.h"
10
11namespace v8 {
12namespace internal {
13
14class V8_EXPORT_PRIVATE BitVector : public ZoneObject {
15 public:
16 union DataStorage {
17 uintptr_t* ptr_; // valid if data_length_ > 1
18 uintptr_t inline_; // valid if data_length_ == 1
19
20 DataStorage(uintptr_t value) : inline_(value) {}
21 };
22
23 // Iterator for the elements of this BitVector.
24 class Iterator {
25 public:
26 explicit Iterator(BitVector* target)
27 : target_(target),
28 current_index_(0),
29 current_value_(target->is_inline() ? target->data_.inline_
30 : target->data_.ptr_[0]),
31 current_(-1) {
32 Advance();
33 }
34 ~Iterator() = default;
35
36 bool Done() const { return current_index_ >= target_->data_length_; }
37 V8_EXPORT_PRIVATE void Advance();
38
39 int Current() const {
40 DCHECK(!Done());
41 return current_;
42 }
43
44 private:
45 uintptr_t SkipZeroBytes(uintptr_t val) {
46 while ((val & 0xFF) == 0) {
47 val >>= 8;
48 current_ += 8;
49 }
50 return val;
51 }
52 uintptr_t SkipZeroBits(uintptr_t val) {
53 while ((val & 0x1) == 0) {
54 val >>= 1;
55 current_++;
56 }
57 return val;
58 }
59
60 BitVector* target_;
61 int current_index_;
62 uintptr_t current_value_;
63 int current_;
64
65 friend class BitVector;
66 };
67
68 static const int kDataLengthForInline = 1;
69 static const int kDataBits = kSystemPointerSize * 8;
70 static const int kDataBitShift = kSystemPointerSize == 8 ? 6 : 5;
71 static const uintptr_t kOne = 1; // This saves some static_casts.
72
73 BitVector() : length_(0), data_length_(kDataLengthForInline), data_(0) {}
74
75 BitVector(int length, Zone* zone)
76 : length_(length), data_length_(SizeFor(length)), data_(0) {
77 DCHECK_LE(0, length);
78 if (!is_inline()) {
79 data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
80 Clear();
81 }
82 // Otherwise, clearing is implicit
83 }
84
85 BitVector(const BitVector& other, Zone* zone)
86 : length_(other.length_),
87 data_length_(other.data_length_),
88 data_(other.data_.inline_) {
89 if (!is_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];
93 }
94 }
95 }
96
97 static int SizeFor(int length) {
98 if (length <= kDataBits) {
99 return kDataLengthForInline;
100 }
101
102 int data_length = 1 + ((length - 1) / kDataBits);
103 DCHECK_GT(data_length, kDataLengthForInline);
104 return data_length;
105 }
106
107 void CopyFrom(const BitVector& other) {
108 DCHECK_LE(other.length(), length());
109 CopyFrom(other.data_, other.data_length_);
110 }
111
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_;
118
119 // Make sure the new data length is large enough to need allocation.
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);
124 }
125 length_ = new_length;
126 }
127
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;
132 }
133
134 void Add(int i) {
135 DCHECK(i >= 0 && i < length());
136 if (is_inline()) {
137 data_.inline_ |= (kOne << i);
138 } else {
139 data_.ptr_[i / kDataBits] |= (kOne << (i % kDataBits));
140 }
141 }
142
143 void AddAll() {
144 // TODO(leszeks): This sets bits outside of the length of this bit-vector,
145 // which is observable if we resize it or copy from it. If this is a
146 // problem, we should clear the high bits either on add, or on resize/copy.
147 if (is_inline()) {
148 data_.inline_ = -1;
149 } else {
150 memset(data_.ptr_, -1, sizeof(uintptr_t) * data_length_);
151 }
152 }
153
154 void Remove(int i) {
155 DCHECK(i >= 0 && i < length());
156 if (is_inline()) {
157 data_.inline_ &= ~(kOne << i);
158 } else {
159 data_.ptr_[i / kDataBits] &= ~(kOne << (i % kDataBits));
160 }
161 }
162
163 void Union(const BitVector& other) {
164 DCHECK(other.length() == length());
165 if (is_inline()) {
166 DCHECK(other.is_inline());
167 data_.inline_ |= other.data_.inline_;
168 } else {
169 for (int i = 0; i < data_length_; i++) {
170 data_.ptr_[i] |= other.data_.ptr_[i];
171 }
172 }
173 }
174
175 bool UnionIsChanged(const BitVector& other) {
176 DCHECK(other.length() == length());
177 if (is_inline()) {
178 DCHECK(other.is_inline());
179 uintptr_t old_data = data_.inline_;
180 data_.inline_ |= other.data_.inline_;
181 return data_.inline_ != old_data;
182 } else {
183 bool changed = false;
184 for (int i = 0; i < data_length_; i++) {
185 uintptr_t old_data = data_.ptr_[i];
186 data_.ptr_[i] |= other.data_.ptr_[i];
187 if (data_.ptr_[i] != old_data) changed = true;
188 }
189 return changed;
190 }
191 }
192
193 void Intersect(const BitVector& other) {
194 DCHECK(other.length() == length());
195 if (is_inline()) {
196 DCHECK(other.is_inline());
197 data_.inline_ &= other.data_.inline_;
198 } else {
199 for (int i = 0; i < data_length_; i++) {
200 data_.ptr_[i] &= other.data_.ptr_[i];
201 }
202 }
203 }
204
205 bool IntersectIsChanged(const BitVector& other) {
206 DCHECK(other.length() == length());
207 if (is_inline()) {
208 DCHECK(other.is_inline());
209 uintptr_t old_data = data_.inline_;
210 data_.inline_ &= other.data_.inline_;
211 return data_.inline_ != old_data;
212 } else {
213 bool changed = false;
214 for (int i = 0; i < data_length_; i++) {
215 uintptr_t old_data = data_.ptr_[i];
216 data_.ptr_[i] &= other.data_.ptr_[i];
217 if (data_.ptr_[i] != old_data) changed = true;
218 }
219 return changed;
220 }
221 }
222
223 void Subtract(const BitVector& other) {
224 DCHECK(other.length() == length());
225 if (is_inline()) {
226 DCHECK(other.is_inline());
227 data_.inline_ &= ~other.data_.inline_;
228 } else {
229 for (int i = 0; i < data_length_; i++) {
230 data_.ptr_[i] &= ~other.data_.ptr_[i];
231 }
232 }
233 }
234
235 void Clear() {
236 if (is_inline()) {
237 data_.inline_ = 0;
238 } else {
239 for (int i = 0; i < data_length_; i++) {
240 data_.ptr_[i] = 0;
241 }
242 }
243 }
244
245 bool IsEmpty() const {
246 if (is_inline()) {
247 return data_.inline_ == 0;
248 } else {
249 for (int i = 0; i < data_length_; i++) {
250 if (data_.ptr_[i] != 0) return false;
251 }
252 return true;
253 }
254 }
255
256 bool Equals(const BitVector& other) const {
257 DCHECK(other.length() == length());
258 if (is_inline()) {
259 DCHECK(other.is_inline());
260 return data_.inline_ == other.data_.inline_;
261 } else {
262 for (int i = 0; i < data_length_; i++) {
263 if (data_.ptr_[i] != other.data_.ptr_[i]) return false;
264 }
265 return true;
266 }
267 }
268
269 int Count() const;
270
271 int length() const { return length_; }
272
273#ifdef DEBUG
274 void Print();
275#endif
276
277 private:
278 int length_;
279 int data_length_;
280 DataStorage data_;
281
282 bool is_inline() const { return data_length_ == kDataLengthForInline; }
283
284 void CopyFrom(DataStorage other_data, int other_data_length) {
285 DCHECK_LE(other_data_length, data_length_);
286
287 if (is_inline()) {
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++) {
293 data_.ptr_[i] = 0;
294 }
295 } else {
296 for (int i = 0; i < other_data_length; i++) {
297 data_.ptr_[i] = other_data.ptr_[i];
298 }
299 for (int i = other_data_length; i < data_length_; i++) {
300 data_.ptr_[i] = 0;
301 }
302 }
303 }
304
305 DISALLOW_COPY_AND_ASSIGN(BitVector);
306};
307
308class GrowableBitVector {
309 public:
310 class Iterator {
311 public:
312 Iterator(const GrowableBitVector* target, Zone* zone)
313 : it_(target->bits_ == nullptr ? new (zone) BitVector(1, zone)
314 : target->bits_) {}
315 bool Done() const { return it_.Done(); }
316 void Advance() { it_.Advance(); }
317 int Current() const { return it_.Current(); }
318
319 private:
320 BitVector::Iterator it_;
321 };
322
323 GrowableBitVector() : bits_(nullptr) {}
324 GrowableBitVector(int length, Zone* zone)
325 : bits_(new (zone) BitVector(length, zone)) {}
326
327 bool Contains(int value) const {
328 if (!InBitsRange(value)) return false;
329 return bits_->Contains(value);
330 }
331
332 void Add(int value, Zone* zone) {
333 EnsureCapacity(value, zone);
334 bits_->Add(value);
335 }
336
337 void Union(const GrowableBitVector& other, Zone* zone) {
338 for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
339 Add(it.Current(), zone);
340 }
341 }
342
343 void Clear() {
344 if (bits_ != nullptr) bits_->Clear();
345 }
346
347 private:
348 static const int kInitialLength = 1024;
349
350 bool InBitsRange(int value) const {
351 return bits_ != nullptr && bits_->length() > value;
352 }
353
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;
358
359 if (bits_ == nullptr) {
360 bits_ = new (zone) BitVector(new_length, zone);
361 } else {
362 bits_->Resize(new_length, zone);
363 }
364 }
365
366 BitVector* bits_;
367};
368
369} // namespace internal
370} // namespace v8
371
372#endif // V8_BIT_VECTOR_H_
373