LCOV - code coverage report
Current view: top level - src/zone - zone-handle-set.h (source / functions) Hit Total Coverage
Test: app.info Lines: 71 79 89.9 %
Date: 2019-04-19 Functions: 6 8 75.0 %

          Line data    Source code
       1             : // Copyright 2016 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_ZONE_ZONE_HANDLE_SET_H_
       6             : #define V8_ZONE_ZONE_HANDLE_SET_H_
       7             : 
       8             : #include "src/handles.h"
       9             : #include "src/zone/zone-containers.h"
      10             : #include "src/zone/zone.h"
      11             : 
      12             : namespace v8 {
      13             : namespace internal {
      14             : 
      15             : template <typename T>
      16             : class ZoneHandleSet final {
      17             :  public:
      18      761406 :   ZoneHandleSet() : data_(kEmptyTag) {}
      19             :   explicit ZoneHandleSet(Handle<T> handle)
      20      177329 :       : data_(handle.address() | kSingletonTag) {
      21             :     DCHECK(IsAligned(handle.address(), kPointerAlignment));
      22             :   }
      23             : 
      24             :   bool is_empty() const { return data_ == kEmptyTag; }
      25             : 
      26             :   size_t size() const {
      27      471785 :     if ((data_ & kTagMask) == kEmptyTag) return 0;
      28      471785 :     if ((data_ & kTagMask) == kSingletonTag) return 1;
      29             :     return list()->size();
      30             :   }
      31             : 
      32      350498 :   Handle<T> at(size_t i) const {
      33             :     DCHECK_NE(kEmptyTag, data_ & kTagMask);
      34      350498 :     if ((data_ & kTagMask) == kSingletonTag) {
      35             :       DCHECK_EQ(0u, i);
      36      316716 :       return Handle<T>(singleton());
      37             :     }
      38       67564 :     return Handle<T>(list()->at(static_cast<int>(i)));
      39             :   }
      40             : 
      41      349510 :   Handle<T> operator[](size_t i) const { return at(i); }
      42             : 
      43      108372 :   void insert(Handle<T> handle, Zone* zone) {
      44      108372 :     Address* const value = reinterpret_cast<Address*>(handle.address());
      45             :     DCHECK(IsAligned(reinterpret_cast<Address>(value), kPointerAlignment));
      46      108372 :     if ((data_ & kTagMask) == kEmptyTag) {
      47       97573 :       data_ = reinterpret_cast<Address>(value) | kSingletonTag;
      48       10799 :     } else if ((data_ & kTagMask) == kSingletonTag) {
      49        9596 :       if (singleton() == value) return;
      50        9572 :       List* list = new (zone->New(sizeof(List))) List(zone);
      51        9572 :       if (singleton() < value) {
      52        9424 :         list->push_back(singleton());
      53        4712 :         list->push_back(value);
      54             :       } else {
      55        4860 :         list->push_back(value);
      56        9720 :         list->push_back(singleton());
      57             :       }
      58             :       DCHECK(IsAligned(reinterpret_cast<Address>(list), kPointerAlignment));
      59        9572 :       data_ = reinterpret_cast<Address>(list) | kListTag;
      60             :     } else {
      61             :       DCHECK_EQ(kListTag, data_ & kTagMask);
      62             :       List const* const old_list = list();
      63        1510 :       for (size_t i = 0; i < old_list->size(); ++i) {
      64        1331 :         if (old_list->at(i) == value) return;
      65        1313 :         if (old_list->at(i) > value) break;
      66             :       }
      67        1206 :       List* new_list = new (zone->New(sizeof(List))) List(zone);
      68        1206 :       new_list->reserve(old_list->size() + 1);
      69             :       size_t i = 0;
      70        1492 :       for (; i < old_list->size(); ++i) {
      71        1313 :         if (old_list->at(i) > value) break;
      72         143 :         new_list->push_back(old_list->at(i));
      73             :       }
      74        1206 :       new_list->push_back(value);
      75        6194 :       for (; i < old_list->size(); ++i) {
      76        2494 :         new_list->push_back(old_list->at(i));
      77             :       }
      78             :       DCHECK_EQ(old_list->size() + 1, new_list->size());
      79             :       DCHECK(IsAligned(reinterpret_cast<Address>(new_list), kPointerAlignment));
      80        1206 :       data_ = reinterpret_cast<Address>(new_list) | kListTag;
      81             :     }
      82             :   }
      83             : 
      84       45265 :   bool contains(ZoneHandleSet<T> const& other) const {
      85       45265 :     if (data_ == other.data_) return true;
      86        3944 :     if (data_ == kEmptyTag) return false;
      87        3944 :     if (other.data_ == kEmptyTag) return true;
      88        3944 :     if ((data_ & kTagMask) == kSingletonTag) return false;
      89             :     DCHECK_EQ(kListTag, data_ & kTagMask);
      90             :     List const* cached_list = list();
      91        2070 :     if ((other.data_ & kTagMask) == kSingletonTag) {
      92         294 :       return std::find(cached_list->begin(), cached_list->end(),
      93         294 :                        other.singleton()) != cached_list->end();
      94             :     }
      95             :     DCHECK_EQ(kListTag, other.data_ & kTagMask);
      96             :     // TODO(bmeurer): Optimize this case.
      97        9931 :     for (size_t i = 0; i < other.list()->size(); ++i) {
      98        4004 :       if (std::find(cached_list->begin(), cached_list->end(),
      99        8008 :                     other.list()->at(i)) == cached_list->end()) {
     100             :         return false;
     101             :       }
     102             :     }
     103             :     return true;
     104             :   }
     105             : 
     106        4368 :   bool contains(Handle<T> other) const {
     107        4368 :     if (data_ == kEmptyTag) return false;
     108        4368 :     Address* other_address = reinterpret_cast<Address*>(other.address());
     109        4368 :     if ((data_ & kTagMask) == kSingletonTag) {
     110        4368 :       return singleton() == other_address;
     111             :     }
     112             :     DCHECK_EQ(kListTag, data_ & kTagMask);
     113           0 :     return std::find(list()->begin(), list()->end(), other_address) !=
     114             :            list()->end();
     115             :   }
     116             : 
     117         106 :   void remove(Handle<T> handle, Zone* zone) {
     118             :     // TODO(bmeurer): Optimize this case.
     119             :     ZoneHandleSet<T> that;
     120         396 :     for (size_t i = 0; i < size(); ++i) {
     121         145 :       Handle<T> value = at(i);
     122         145 :       if (value.address() != handle.address()) {
     123          39 :         that.insert(value, zone);
     124             :       }
     125             :     }
     126             :     std::swap(*this, that);
     127         106 :   }
     128             : 
     129       25330 :   friend bool operator==(ZoneHandleSet<T> const& lhs,
     130             :                          ZoneHandleSet<T> const& rhs) {
     131       25330 :     if (lhs.data_ == rhs.data_) return true;
     132       12567 :     if ((lhs.data_ & kTagMask) == kListTag &&
     133             :         (rhs.data_ & kTagMask) == kListTag) {
     134             :       List const* const lhs_list = lhs.list();
     135             :       List const* const rhs_list = rhs.list();
     136         535 :       if (lhs_list->size() == rhs_list->size()) {
     137        2901 :         for (size_t i = 0; i < lhs_list->size(); ++i) {
     138        2366 :           if (lhs_list->at(i) != rhs_list->at(i)) return false;
     139             :         }
     140             :         return true;
     141             :       }
     142             :     }
     143             :     return false;
     144             :   }
     145             : 
     146             :   friend bool operator!=(ZoneHandleSet<T> const& lhs,
     147             :                          ZoneHandleSet<T> const& rhs) {
     148          36 :     return !(lhs == rhs);
     149             :   }
     150             : 
     151           0 :   friend size_t hash_value(ZoneHandleSet<T> const& set) {
     152           0 :     return static_cast<size_t>(set.data_);
     153             :   }
     154             : 
     155             :   class const_iterator;
     156             :   inline const_iterator begin() const;
     157             :   inline const_iterator end() const;
     158             : 
     159             :  private:
     160             :   typedef ZoneVector<Address*> List;
     161             : 
     162             :   List const* list() const {
     163             :     DCHECK_EQ(kListTag, data_ & kTagMask);
     164       64522 :     return reinterpret_cast<List const*>(data_ - kListTag);
     165             :   }
     166             : 
     167             :   Address* singleton() const {
     168             :     DCHECK_EQ(kSingletonTag, data_ & kTagMask);
     169      345238 :     return reinterpret_cast<Address*>(data_ - kSingletonTag);
     170             :   }
     171             : 
     172             :   enum Tag : Address {
     173             :     kSingletonTag = 0,
     174             :     kEmptyTag = 1,
     175             :     kListTag = 2,
     176             :     kTagMask = 3
     177             :   };
     178             : 
     179             :   STATIC_ASSERT(kTagMask < kPointerAlignment);
     180             : 
     181             :   Address data_;
     182             : };
     183             : 
     184             : template <typename T>
     185           0 : std::ostream& operator<<(std::ostream& os, ZoneHandleSet<T> set) {
     186           0 :   for (size_t i = 0; i < set.size(); ++i) {
     187           0 :     if (i > 0) os << ", ";
     188           0 :     os << set.at(i);
     189             :   }
     190           0 :   return os;
     191             : }
     192             : 
     193             : template <typename T>
     194             : class ZoneHandleSet<T>::const_iterator {
     195             :  public:
     196             :   typedef std::forward_iterator_tag iterator_category;
     197             :   typedef std::ptrdiff_t difference_type;
     198             :   typedef Handle<T> value_type;
     199             :   typedef value_type reference;
     200             :   typedef value_type* pointer;
     201             : 
     202             :   const_iterator(const const_iterator& other)
     203        3651 :       : set_(other.set_), current_(other.current_) {}
     204             : 
     205        1217 :   reference operator*() const { return (*set_)[current_]; }
     206             :   bool operator==(const const_iterator& other) const {
     207      240137 :     return set_ == other.set_ && current_ == other.current_;
     208             :   }
     209             :   bool operator!=(const const_iterator& other) const {
     210      237703 :     return !(*this == other);
     211             :   }
     212             :   const_iterator& operator++() {
     213             :     DCHECK(current_ < set_->size());
     214      123667 :     current_ += 1;
     215             :     return *this;
     216             :   }
     217             :   const_iterator operator++(int);
     218             : 
     219             :  private:
     220             :   friend class ZoneHandleSet<T>;
     221             : 
     222             :   explicit const_iterator(const ZoneHandleSet<T>* set, size_t current)
     223        1217 :       : set_(set), current_(current) {}
     224             : 
     225             :   const ZoneHandleSet<T>* set_;
     226             :   size_t current_;
     227             : };
     228             : 
     229             : template <typename T>
     230             : typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::begin() const {
     231             :   return ZoneHandleSet<T>::const_iterator(this, 0);
     232             : }
     233             : 
     234             : template <typename T>
     235             : typename ZoneHandleSet<T>::const_iterator ZoneHandleSet<T>::end() const {
     236             :   return ZoneHandleSet<T>::const_iterator(this, size());
     237             : }
     238             : 
     239             : }  // namespace internal
     240             : }  // namespace v8
     241             : 
     242             : #endif  // V8_ZONE_ZONE_HANDLE_SET_H_

Generated by: LCOV version 1.10