bit-vector.h 9.56 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5 6
#ifndef V8_BIT_VECTOR_H_
#define V8_BIT_VECTOR_H_
7

8
#include "src/allocation.h"
9
#include "src/zone/zone.h"
10 11 12 13

namespace v8 {
namespace internal {

14
class BitVector : public ZoneObject {
15
 public:
16 17 18 19 20 21 22
  union DataStorage {
    uintptr_t* ptr_;    // valid if data_length_ > 1
    uintptr_t inline_;  // valid if data_length_ == 1

    DataStorage(uintptr_t value) : inline_(value) {}
  };

23 24 25 26 27 28
  // Iterator for the elements of this BitVector.
  class Iterator BASE_EMBEDDED {
   public:
    explicit Iterator(BitVector* target)
        : target_(target),
          current_index_(0),
29 30
          current_value_(target->is_inline() ? target->data_.inline_
                                             : target->data_.ptr_[0]),
31 32 33
          current_(-1) {
      Advance();
    }
34
    ~Iterator() {}
35 36 37 38 39

    bool Done() const { return current_index_ >= target_->data_length_; }
    void Advance();

    int Current() const {
40
      DCHECK(!Done());
41 42 43 44
      return current_;
    }

   private:
45
    uintptr_t SkipZeroBytes(uintptr_t val) {
46 47 48 49 50 51
      while ((val & 0xFF) == 0) {
        val >>= 8;
        current_ += 8;
      }
      return val;
    }
52
    uintptr_t SkipZeroBits(uintptr_t val) {
53 54 55 56 57 58
      while ((val & 0x1) == 0) {
        val >>= 1;
        current_++;
      }
      return val;
    }
59

60 61
    BitVector* target_;
    int current_index_;
62
    uintptr_t current_value_;
63 64 65 66 67
    int current_;

    friend class BitVector;
  };

68
  static const int kDataLengthForInline = 1;
69 70 71 72
  static const int kDataBits = kPointerSize * 8;
  static const int kDataBitShift = kPointerSize == 8 ? 6 : 5;
  static const uintptr_t kOne = 1;  // This saves some static_casts.

73 74
  BitVector() : length_(0), data_length_(kDataLengthForInline), data_(0) {}

75
  BitVector(int length, Zone* zone)
76
      : length_(length), data_length_(SizeFor(length)), data_(0) {
77
    DCHECK_LE(0, length);
78 79 80 81 82
    if (!is_inline()) {
      data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
      Clear();
    }
    // Otherwise, clearing is implicit
83 84
  }

85
  BitVector(const BitVector& other, Zone* zone)
86 87 88 89 90 91 92 93 94
      : length_(other.length_),
        data_length_(other.data_length_),
        data_(other.data_.inline_) {
    if (!is_inline()) {
      data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
      for (int i = 0; i < other.data_length_; i++) {
        data_.ptr_[i] = other.data_.ptr_[i];
      }
    }
95 96
  }

97
  static int SizeFor(int length) {
98 99 100 101 102 103 104
    if (length <= kDataBits) {
      return kDataLengthForInline;
    }

    int data_length = 1 + ((length - 1) / kDataBits);
    DCHECK_GT(data_length, kDataLengthForInline);
    return data_length;
105
  }
106

107
  void CopyFrom(const BitVector& other) {
108 109 110 111 112 113 114 115
    DCHECK_LE(other.length(), length());
    CopyFrom(other.data_, other.data_length_);
  }

  void Resize(int new_length, Zone* zone) {
    DCHECK_GT(new_length, length());
    int new_data_length = SizeFor(new_length);
    if (new_data_length > data_length_) {
116
      DataStorage old_data = data_;
117 118
      int old_data_length = data_length_;

119 120 121
      // Make sure the new data length is large enough to need allocation.
      DCHECK_GT(new_data_length, kDataLengthForInline);
      data_.ptr_ = zone->NewArray<uintptr_t>(new_data_length);
122 123
      data_length_ = new_data_length;
      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 137 138 139 140
    if (is_inline()) {
      data_.inline_ |= (kOne << i);
    } else {
      data_.ptr_[i / kDataBits] |= (kOne << (i % kDataBits));
    }
141 142
  }

143 144 145 146 147 148 149 150 151 152
  void AddAll() {
    // TODO(leszeks): This sets bits outside of the length of this bit-vector,
    // which is observable if we resize it or copy from it. If this is a
    // problem, we should clear the high bits either on add, or on resize/copy.
    if (is_inline()) {
      data_.inline_ = -1;
    } else {
      memset(data_.ptr_, -1, sizeof(uintptr_t) * data_length_);
    }
  }
153

154
  void Remove(int i) {
155
    DCHECK(i >= 0 && i < length());
156 157 158 159 160
    if (is_inline()) {
      data_.inline_ &= ~(kOne << i);
    } else {
      data_.ptr_[i / kDataBits] &= ~(kOne << (i % kDataBits));
    }
161 162 163
  }

  void Union(const BitVector& other) {
164
    DCHECK(other.length() == length());
165 166 167 168 169 170 171
    if (is_inline()) {
      DCHECK(other.is_inline());
      data_.inline_ |= other.data_.inline_;
    } else {
      for (int i = 0; i < data_length_; i++) {
        data_.ptr_[i] |= other.data_.ptr_[i];
      }
172 173 174
    }
  }

175
  bool UnionIsChanged(const BitVector& other) {
176
    DCHECK(other.length() == length());
177 178 179 180 181 182 183 184 185 186 187 188 189
    if (is_inline()) {
      DCHECK(other.is_inline());
      uintptr_t old_data = data_.inline_;
      data_.inline_ |= other.data_.inline_;
      return data_.inline_ != old_data;
    } else {
      bool changed = false;
      for (int i = 0; i < data_length_; i++) {
        uintptr_t old_data = data_.ptr_[i];
        data_.ptr_[i] |= other.data_.ptr_[i];
        if (data_.ptr_[i] != old_data) changed = true;
      }
      return changed;
190 191 192
    }
  }

193
  void Intersect(const BitVector& other) {
194
    DCHECK(other.length() == length());
195 196 197 198 199 200 201
    if (is_inline()) {
      DCHECK(other.is_inline());
      data_.inline_ &= other.data_.inline_;
    } else {
      for (int i = 0; i < data_length_; i++) {
        data_.ptr_[i] &= other.data_.ptr_[i];
      }
202 203 204
    }
  }

205 206
  bool IntersectIsChanged(const BitVector& other) {
    DCHECK(other.length() == length());
207 208 209 210 211 212 213 214 215 216 217 218 219
    if (is_inline()) {
      DCHECK(other.is_inline());
      uintptr_t old_data = data_.inline_;
      data_.inline_ &= other.data_.inline_;
      return data_.inline_ != old_data;
    } else {
      bool changed = false;
      for (int i = 0; i < data_length_; i++) {
        uintptr_t old_data = data_.ptr_[i];
        data_.ptr_[i] &= other.data_.ptr_[i];
        if (data_.ptr_[i] != old_data) changed = true;
      }
      return changed;
220 221 222
    }
  }

223
  void Subtract(const BitVector& other) {
224
    DCHECK(other.length() == length());
225 226 227 228 229 230 231
    if (is_inline()) {
      DCHECK(other.is_inline());
      data_.inline_ &= ~other.data_.inline_;
    } else {
      for (int i = 0; i < data_length_; i++) {
        data_.ptr_[i] &= ~other.data_.ptr_[i];
      }
232 233 234
    }
  }

235
  void Clear() {
236 237 238 239 240 241
    if (is_inline()) {
      data_.inline_ = 0;
    } else {
      for (int i = 0; i < data_length_; i++) {
        data_.ptr_[i] = 0;
      }
242 243 244
    }
  }

245
  bool IsEmpty() const {
246 247 248 249 250 251 252
    if (is_inline()) {
      return data_.inline_ == 0;
    } else {
      for (int i = 0; i < data_length_; i++) {
        if (data_.ptr_[i] != 0) return false;
      }
      return true;
253 254 255
    }
  }

256
  bool Equals(const BitVector& other) const {
257 258 259 260 261 262 263 264 265
    DCHECK(other.length() == length());
    if (is_inline()) {
      DCHECK(other.is_inline());
      return data_.inline_ == other.data_.inline_;
    } else {
      for (int i = 0; i < data_length_; i++) {
        if (data_.ptr_[i] != other.data_.ptr_[i]) return false;
      }
      return true;
266 267 268
    }
  }

269
  int Count() const;
270

271 272
  int length() const { return length_; }

273 274 275 276
#ifdef DEBUG
  void Print();
#endif

277
 private:
278 279
  int length_;
  int data_length_;
280 281 282
  DataStorage data_;

  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 288 289 290 291 292 293 294 295 296 297 298 299 300 301

    if (is_inline()) {
      DCHECK_EQ(other_data_length, kDataLengthForInline);
      data_.inline_ = other_data.inline_;
    } else if (other_data_length == kDataLengthForInline) {
      data_.ptr_[0] = other_data.inline_;
      for (int i = 1; i < data_length_; i++) {
        data_.ptr_[i] = 0;
      }
    } else {
      for (int i = 0; i < other_data_length; i++) {
        data_.ptr_[i] = other_data.ptr_[i];
      }
      for (int i = other_data_length; i < data_length_; i++) {
        data_.ptr_[i] = 0;
      }
302 303
    }
  }
304 305

  DISALLOW_COPY_AND_ASSIGN(BitVector);
306 307
};

308

309 310
class GrowableBitVector BASE_EMBEDDED {
 public:
311 312 313
  class Iterator BASE_EMBEDDED {
   public:
    Iterator(const GrowableBitVector* target, Zone* zone)
314 315
        : it_(target->bits_ == nullptr ? new (zone) BitVector(1, zone)
                                       : target->bits_) {}
316 317 318
    bool Done() const { return it_.Done(); }
    void Advance() { it_.Advance(); }
    int Current() const { return it_.Current(); }
319

320 321 322 323
   private:
    BitVector::Iterator it_;
  };

324
  GrowableBitVector() : bits_(nullptr) {}
325
  GrowableBitVector(int length, Zone* zone)
326
      : bits_(new (zone) BitVector(length, zone)) {}
327 328 329 330 331 332 333 334 335 336 337

  bool Contains(int value) const {
    if (!InBitsRange(value)) return false;
    return bits_->Contains(value);
  }

  void Add(int value, Zone* zone) {
    EnsureCapacity(value, zone);
    bits_->Add(value);
  }

338 339 340 341 342 343
  void Union(const GrowableBitVector& other, Zone* zone) {
    for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
      Add(it.Current(), zone);
    }
  }

344
  void Clear() {
345
    if (bits_ != nullptr) bits_->Clear();
346
  }
347

348 349 350 351
 private:
  static const int kInitialLength = 1024;

  bool InBitsRange(int value) const {
352
    return bits_ != nullptr && bits_->length() > value;
353 354 355 356
  }

  void EnsureCapacity(int value, Zone* zone) {
    if (InBitsRange(value)) return;
357
    int new_length = bits_ == nullptr ? kInitialLength : bits_->length();
358
    while (new_length <= value) new_length *= 2;
359 360 361 362 363 364

    if (bits_ == nullptr) {
      bits_ = new (zone) BitVector(new_length, zone);
    } else {
      bits_->Resize(new_length, zone);
    }
365 366 367 368 369
  }

  BitVector* bits_;
};

370 371
}  // namespace internal
}  // namespace v8
372

373
#endif  // V8_BIT_VECTOR_H_