LCOV - code coverage report
Current view: top level - src - bit-vector.h (source / functions) Hit Total Coverage
Test: app.info Lines: 69 69 100.0 %
Date: 2017-04-26 Functions: 9 9 100.0 %

          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_DATAFLOW_H_
       6             : #define V8_DATAFLOW_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             :   // Iterator for the elements of this BitVector.
      17             :   class Iterator BASE_EMBEDDED {
      18             :    public:
      19             :     explicit Iterator(BitVector* target)
      20             :         : target_(target),
      21             :           current_index_(0),
      22    45284944 :           current_value_(target->data_[0]),
      23    90569888 :           current_(-1) {
      24             :       DCHECK(target->data_length_ > 0);
      25    45284944 :       Advance();
      26             :     }
      27             :     ~Iterator() {}
      28             : 
      29   226430033 :     bool Done() const { return current_index_ >= target_->data_length_; }
      30             :     void Advance();
      31             : 
      32             :     int Current() const {
      33             :       DCHECK(!Done());
      34             :       return current_;
      35             :     }
      36             : 
      37             :    private:
      38             :     uintptr_t SkipZeroBytes(uintptr_t val) {
      39   288174265 :       while ((val & 0xFF) == 0) {
      40   107067646 :         val >>= 8;
      41   107067646 :         current_ += 8;
      42             :       }
      43             :       return val;
      44             :     }
      45             :     uintptr_t SkipZeroBits(uintptr_t val) {
      46   525486354 :       while ((val & 0x1) == 0) {
      47   344379735 :         val >>= 1;
      48   344379735 :         current_++;
      49             :       }
      50             :       return val;
      51             :     }
      52             : 
      53             :     BitVector* target_;
      54             :     int current_index_;
      55             :     uintptr_t current_value_;
      56             :     int current_;
      57             : 
      58             :     friend class BitVector;
      59             :   };
      60             : 
      61             :   static const int kDataBits = kPointerSize * 8;
      62             :   static const int kDataBitShift = kPointerSize == 8 ? 6 : 5;
      63             :   static const uintptr_t kOne = 1;  // This saves some static_casts.
      64             : 
      65   177609650 :   BitVector(int length, Zone* zone)
      66             :       : length_(length),
      67             :         data_length_(SizeFor(length)),
      68   266414341 :         data_(zone->NewArray<uintptr_t>(data_length_)) {
      69             :     DCHECK_LE(0, length);
      70             :     Clear();
      71    88804959 :   }
      72             : 
      73             :   BitVector(const BitVector& other, Zone* zone)
      74             :       : length_(other.length()),
      75             :         data_length_(SizeFor(length_)),
      76             :         data_(zone->NewArray<uintptr_t>(data_length_)) {
      77             :     CopyFrom(other);
      78             :   }
      79             : 
      80             :   static int SizeFor(int length) {
      81    88804691 :     if (length == 0) return 1;
      82    88803242 :     return 1 + ((length - 1) / kDataBits);
      83             :   }
      84             : 
      85             :   void CopyFrom(const BitVector& other) {
      86             :     DCHECK(other.length() <= length());
      87   303010238 :     for (int i = 0; i < other.data_length_; i++) {
      88   303010238 :       data_[i] = other.data_[i];
      89             :     }
      90        5024 :     for (int i = other.data_length_; i < data_length_; i++) {
      91        5024 :       data_[i] = 0;
      92             :     }
      93             :   }
      94             : 
      95             :   bool Contains(int i) const {
      96             :     DCHECK(i >= 0 && i < length());
      97   217059159 :     uintptr_t block = data_[i / kDataBits];
      98   217059159 :     return (block & (kOne << (i % kDataBits))) != 0;
      99             :   }
     100             : 
     101             :   void Add(int i) {
     102             :     DCHECK(i >= 0 && i < length());
     103   230175291 :     data_[i / kDataBits] |= (kOne << (i % kDataBits));
     104             :   }
     105             : 
     106       11626 :   void AddAll() { memset(data_, -1, sizeof(uintptr_t) * data_length_); }
     107             : 
     108             :   void Remove(int i) {
     109             :     DCHECK(i >= 0 && i < length());
     110    52322939 :     data_[i / kDataBits] &= ~(kOne << (i % kDataBits));
     111             :   }
     112             : 
     113             :   void Union(const BitVector& other) {
     114             :     DCHECK(other.length() == length());
     115   928048652 :     for (int i = 0; i < data_length_; i++) {
     116   928048652 :       data_[i] |= other.data_[i];
     117             :     }
     118             :   }
     119             : 
     120             :   bool UnionIsChanged(const BitVector& other) {
     121             :     DCHECK(other.length() == length());
     122             :     bool changed = false;
     123     6199899 :     for (int i = 0; i < data_length_; i++) {
     124     6199899 :       uintptr_t old_data = data_[i];
     125     6199899 :       data_[i] |= other.data_[i];
     126     6199899 :       if (data_[i] != old_data) changed = true;
     127             :     }
     128             :     return changed;
     129             :   }
     130             : 
     131             :   void Intersect(const BitVector& other) {
     132             :     DCHECK(other.length() == length());
     133             :     for (int i = 0; i < data_length_; i++) {
     134             :       data_[i] &= other.data_[i];
     135             :     }
     136             :   }
     137             : 
     138             :   bool IntersectIsChanged(const BitVector& other) {
     139             :     DCHECK(other.length() == length());
     140             :     bool changed = false;
     141          68 :     for (int i = 0; i < data_length_; i++) {
     142          68 :       uintptr_t old_data = data_[i];
     143          68 :       data_[i] &= other.data_[i];
     144          68 :       if (data_[i] != old_data) changed = true;
     145             :     }
     146             :     return changed;
     147             :   }
     148             : 
     149             :   void Subtract(const BitVector& other) {
     150             :     DCHECK(other.length() == length());
     151             :     for (int i = 0; i < data_length_; i++) {
     152             :       data_[i] &= ~other.data_[i];
     153             :     }
     154             :   }
     155             : 
     156             :   void Clear() {
     157  1169432575 :     for (int i = 0; i < data_length_; i++) {
     158  1169432575 :       data_[i] = 0;
     159             :     }
     160             :   }
     161             : 
     162             :   bool IsEmpty() const {
     163      325280 :     for (int i = 0; i < data_length_; i++) {
     164      972644 :       if (data_[i] != 0) return false;
     165             :     }
     166             :     return true;
     167             :   }
     168             : 
     169             :   bool Equals(const BitVector& other) const {
     170     4627875 :     for (int i = 0; i < data_length_; i++) {
     171     4876377 :       if (data_[i] != other.data_[i]) return false;
     172             :     }
     173             :     return true;
     174             :   }
     175             : 
     176             :   int Count() const;
     177             : 
     178             :   int length() const { return length_; }
     179             : 
     180             : #ifdef DEBUG
     181             :   void Print();
     182             : #endif
     183             : 
     184             :  private:
     185             :   const int length_;
     186             :   const int data_length_;
     187             :   uintptr_t* const data_;
     188             : 
     189             :   DISALLOW_COPY_AND_ASSIGN(BitVector);
     190             : };
     191             : 
     192             : 
     193             : class GrowableBitVector BASE_EMBEDDED {
     194             :  public:
     195             :   class Iterator BASE_EMBEDDED {
     196             :    public:
     197    18903558 :     Iterator(const GrowableBitVector* target, Zone* zone)
     198    33673796 :         : it_(target->bits_ == NULL ? new (zone) BitVector(1, zone)
     199    56710850 :                                     : target->bits_) {}
     200    24834730 :     bool Done() const { return it_.Done(); }
     201     5930698 :     void Advance() { it_.Advance(); }
     202     5930684 :     int Current() const { return it_.Current(); }
     203             : 
     204             :    private:
     205             :     BitVector::Iterator it_;
     206             :   };
     207             : 
     208    14800255 :   GrowableBitVector() : bits_(NULL) {}
     209    11649257 :   GrowableBitVector(int length, Zone* zone)
     210    11649255 :       : bits_(new (zone) BitVector(length, zone)) {}
     211             : 
     212    58211909 :   bool Contains(int value) const {
     213    58211909 :     if (!InBitsRange(value)) return false;
     214   115801076 :     return bits_->Contains(value);
     215             :   }
     216             : 
     217    42215558 :   void Add(int value, Zone* zone) {
     218    42215558 :     EnsureCapacity(value, zone);
     219    42215629 :     bits_->Add(value);
     220    42215629 :   }
     221             : 
     222    13938985 :   void Union(const GrowableBitVector& other, Zone* zone) {
     223    32849775 :     for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
     224     4971635 :       Add(it.Current(), zone);
     225             :     }
     226    13939155 :   }
     227             : 
     228             :   void Clear() {
     229     5844364 :     if (bits_ != NULL) bits_->Clear();
     230             :   }
     231             : 
     232             :  private:
     233             :   static const int kInitialLength = 1024;
     234             : 
     235             :   bool InBitsRange(int value) const {
     236   100427480 :     return bits_ != NULL && bits_->length() > value;
     237             :   }
     238             : 
     239    42215571 :   void EnsureCapacity(int value, Zone* zone) {
     240    84431159 :     if (InBitsRange(value)) return;
     241     2512956 :     int new_length = bits_ == NULL ? kInitialLength : bits_->length();
     242     2491253 :     while (new_length <= value) new_length *= 2;
     243     2512964 :     BitVector* new_bits = new (zone) BitVector(new_length, zone);
     244     2491270 :     if (bits_ != NULL) new_bits->CopyFrom(*bits_);
     245     2491270 :     bits_ = new_bits;
     246             :   }
     247             : 
     248             :   BitVector* bits_;
     249             : };
     250             : 
     251             : }  // namespace internal
     252             : }  // namespace v8
     253             : 
     254             : #endif  // V8_DATAFLOW_H_

Generated by: LCOV version 1.10