V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
bit-vector.h
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  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  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 = kPointerSize * 8;
70  static const int kDataBitShift = kPointerSize == 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 
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:
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_
Definition: libplatform.h:13