Line data Source code
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 :
11 : namespace v8 {
12 : namespace internal {
13 :
14 : class 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 61837709 : DataStorage(uintptr_t value) : inline_(value) {}
21 : };
22 :
23 : // Iterator for the elements of this BitVector.
24 : class Iterator {
25 : public:
26 64856314 : explicit Iterator(BitVector* target)
27 : : target_(target),
28 : current_index_(0),
29 : current_value_(target->is_inline() ? target->data_.inline_
30 18229856 : : target->data_.ptr_[0]),
31 83086170 : current_(-1) {
32 32428157 : Advance();
33 32427661 : }
34 : ~Iterator() = default;
35 :
36 539075156 : bool Done() const { return current_index_ >= target_->data_length_; }
37 : 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 332047540 : while ((val & 0xFF) == 0) {
47 116277456 : val >>= 8;
48 116277456 : current_ += 8;
49 : }
50 : return val;
51 : }
52 : uintptr_t SkipZeroBits(uintptr_t val) {
53 675801779 : while ((val & 0x1) == 0) {
54 460031695 : val >>= 1;
55 460031695 : 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 61837704 : BitVector(int length, Zone* zone)
76 123675408 : : length_(length), data_length_(SizeFor(length)), data_(0) {
77 : DCHECK_LE(0, length);
78 61837704 : if (!is_inline()) {
79 27551168 : data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
80 : Clear();
81 : }
82 : // Otherwise, clearing is implicit
83 61837668 : }
84 :
85 5 : BitVector(const BitVector& other, Zone* zone)
86 : : length_(other.length_),
87 : data_length_(other.data_length_),
88 5 : data_(other.data_.inline_) {
89 5 : if (!is_inline()) {
90 0 : data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
91 0 : for (int i = 0; i < other.data_length_; i++) {
92 0 : data_.ptr_[i] = other.data_.ptr_[i];
93 : }
94 : }
95 5 : }
96 :
97 : static int SizeFor(int length) {
98 61837715 : if (length <= kDataBits) {
99 : return kDataLengthForInline;
100 : }
101 :
102 13775606 : 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 17796670 : CopyFrom(other.data_, other.data_length_);
110 : }
111 :
112 11 : void Resize(int new_length, Zone* zone) {
113 : DCHECK_GT(new_length, length());
114 : int new_data_length = SizeFor(new_length);
115 11 : if (new_data_length > data_length_) {
116 5 : 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 10 : data_.ptr_ = zone->NewArray<uintptr_t>(new_data_length);
122 5 : data_length_ = new_data_length;
123 5 : CopyFrom(old_data, old_data_length);
124 : }
125 11 : length_ = new_length;
126 11 : }
127 :
128 424691903 : bool Contains(int i) const {
129 : DCHECK(i >= 0 && i < length());
130 424691998 : uintptr_t block = is_inline() ? data_.inline_ : data_.ptr_[i / kDataBits];
131 424691998 : return (block & (kOne << (i % kDataBits))) != 0;
132 : }
133 :
134 198260327 : void Add(int i) {
135 : DCHECK(i >= 0 && i < length());
136 208328187 : if (is_inline()) {
137 144509814 : data_.inline_ |= (kOne << i);
138 : } else {
139 63818373 : 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 52559706 : void Remove(int i) {
155 : DCHECK(i >= 0 && i < length());
156 52559706 : if (is_inline()) {
157 31672831 : data_.inline_ &= ~(kOne << i);
158 : } else {
159 20886875 : data_.ptr_[i / kDataBits] &= ~(kOne << (i % kDataBits));
160 : }
161 52559706 : }
162 :
163 45380050 : void Union(const BitVector& other) {
164 : DCHECK(other.length() == length());
165 45380050 : if (is_inline()) {
166 : DCHECK(other.is_inline());
167 25904486 : data_.inline_ |= other.data_.inline_;
168 : } else {
169 371045602 : for (int i = 0; i < data_length_; i++) {
170 371045602 : data_.ptr_[i] |= other.data_.ptr_[i];
171 : }
172 : }
173 45380050 : }
174 :
175 65638 : bool UnionIsChanged(const BitVector& other) {
176 : DCHECK(other.length() == length());
177 65638 : if (is_inline()) {
178 : DCHECK(other.is_inline());
179 65629 : uintptr_t old_data = data_.inline_;
180 65629 : data_.inline_ |= other.data_.inline_;
181 65629 : return data_.inline_ != old_data;
182 : } else {
183 : bool changed = false;
184 24 : for (int i = 0; i < data_length_; i++) {
185 24 : uintptr_t old_data = data_.ptr_[i];
186 24 : data_.ptr_[i] |= other.data_.ptr_[i];
187 24 : if (data_.ptr_[i] != old_data) changed = true;
188 : }
189 : return changed;
190 : }
191 : }
192 :
193 10 : void Intersect(const BitVector& other) {
194 : DCHECK(other.length() == length());
195 10 : if (is_inline()) {
196 : DCHECK(other.is_inline());
197 10 : data_.inline_ &= other.data_.inline_;
198 : } else {
199 0 : for (int i = 0; i < data_length_; i++) {
200 0 : data_.ptr_[i] &= other.data_.ptr_[i];
201 : }
202 : }
203 10 : }
204 :
205 501 : bool IntersectIsChanged(const BitVector& other) {
206 : DCHECK(other.length() == length());
207 501 : if (is_inline()) {
208 : DCHECK(other.is_inline());
209 501 : uintptr_t old_data = data_.inline_;
210 501 : data_.inline_ &= other.data_.inline_;
211 501 : return data_.inline_ != old_data;
212 : } else {
213 : bool changed = false;
214 0 : for (int i = 0; i < data_length_; i++) {
215 0 : uintptr_t old_data = data_.ptr_[i];
216 0 : data_.ptr_[i] &= other.data_.ptr_[i];
217 0 : 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 13775566 : void Clear() {
236 13775566 : if (is_inline()) {
237 0 : data_.inline_ = 0;
238 : } else {
239 402612631 : for (int i = 0; i < data_length_; i++) {
240 402612631 : data_.ptr_[i] = 0;
241 : }
242 : }
243 : }
244 :
245 325633 : bool IsEmpty() const {
246 325633 : if (is_inline()) {
247 325633 : return data_.inline_ == 0;
248 : } else {
249 0 : for (int i = 0; i < data_length_; i++) {
250 0 : 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 17796674 : void CopyFrom(DataStorage other_data, int other_data_length) {
285 : DCHECK_LE(other_data_length, data_length_);
286 :
287 17796674 : if (is_inline()) {
288 : DCHECK_EQ(other_data_length, kDataLengthForInline);
289 16790017 : data_.inline_ = other_data.inline_;
290 1006657 : } else if (other_data_length == kDataLengthForInline) {
291 5 : data_.ptr_[0] = other_data.inline_;
292 25 : for (int i = 1; i < data_length_; i++) {
293 20 : data_.ptr_[i] = 0;
294 : }
295 : } else {
296 114315843 : for (int i = 0; i < other_data_length; i++) {
297 114315843 : data_.ptr_[i] = other_data.ptr_[i];
298 : }
299 0 : for (int i = other_data_length; i < data_length_; i++) {
300 0 : data_.ptr_[i] = 0;
301 : }
302 : }
303 17796674 : }
304 :
305 : DISALLOW_COPY_AND_ASSIGN(BitVector);
306 : };
307 :
308 : class 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_
|
