LCOV - code coverage report
Current view: top level - src - list-inl.h (source / functions) Hit Total Coverage
Test: app.info Lines: 79 79 100.0 %
Date: 2017-04-26 Functions: 577 696 82.9 %

          Line data    Source code
       1             : // Copyright 2006-2009 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_LIST_INL_H_
       6             : #define V8_LIST_INL_H_
       7             : 
       8             : #include "src/list.h"
       9             : 
      10             : #include "src/base/macros.h"
      11             : #include "src/base/platform/platform.h"
      12             : #include "src/utils.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : 
      17             : 
      18             : template<typename T, class P>
      19  1704518416 : void List<T, P>::Add(const T& element, P alloc) {
      20  1668102130 :   if (length_ < capacity_) {
      21  1610627177 :     data_[length_++] = element;
      22             :   } else {
      23             :     List<T, P>::ResizeAdd(element, alloc);
      24             :   }
      25  1668102126 : }
      26             : 
      27             : 
      28             : template<typename T, class P>
      29    17277847 : void List<T, P>::AddAll(const List<T, P>& other, P alloc) {
      30    17570007 :   AddAll(other.ToVector(), alloc);
      31             : }
      32             : 
      33             : 
      34             : template<typename T, class P>
      35   145001919 : void List<T, P>::AddAll(const Vector<T>& other, P alloc) {
      36    38736156 :   int result_length = length_ + other.length();
      37    19368078 :   if (capacity_ < result_length) Resize(result_length, alloc);
      38             :   if (std::is_fundamental<T>()) {
      39     3596054 :     memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
      40             :   } else {
      41   290828227 :     for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
      42             :   }
      43    19367948 :   length_ = result_length;
      44    19367948 : }
      45             : 
      46             : 
      47             : // Use two layers of inlining so that the non-inlined function can
      48             : // use the same implementation as the inlined version.
      49             : template<typename T, class P>
      50             : void List<T, P>::ResizeAdd(const T& element, P alloc) {
      51    57474953 :   ResizeAddInternal(element, alloc);
      52             : }
      53             : 
      54             : 
      55             : template<typename T, class P>
      56    57474948 : void List<T, P>::ResizeAddInternal(const T& element, P alloc) {
      57             :   DCHECK(length_ >= capacity_);
      58             :   // Grow the list capacity by 100%, but make sure to let it grow
      59             :   // even when the capacity is zero (possible initial case).
      60    57474948 :   int new_capacity = 1 + 2 * capacity_;
      61             :   // Since the element reference could be an element of the list, copy
      62             :   // it out of the old backing storage before resizing.
      63    57474948 :   T temp = element;
      64    57474948 :   Resize(new_capacity, alloc);
      65    57474951 :   data_[length_++] = temp;
      66    57474951 : }
      67             : 
      68             : 
      69             : template<typename T, class P>
      70    71433103 : void List<T, P>::Resize(int new_capacity, P alloc) {
      71             :   DCHECK_LE(length_, new_capacity);
      72             :   T* new_data = NewData(new_capacity, alloc);
      73    71433064 :   MemCopy(new_data, data_, length_ * sizeof(T));
      74    31890042 :   List<T, P>::DeleteData(data_);
      75    71433065 :   data_ = new_data;
      76    71433065 :   capacity_ = new_capacity;
      77    71433065 : }
      78             : 
      79             : 
      80             : template<typename T, class P>
      81             : Vector<T> List<T, P>::AddBlock(T value, int count, P alloc) {
      82    12191913 :   int start = length_;
      83   114838206 :   for (int i = 0; i < count; i++) Add(value, alloc);
      84    12191940 :   return Vector<T>(&data_[start], count);
      85             : }
      86             : 
      87             : 
      88             : template<typename T, class P>
      89             : void List<T, P>::Set(int index, const T& elm) {
      90             :   DCHECK(index >= 0 && index <= length_);
      91    24730695 :   data_[index] = elm;
      92             : }
      93             : 
      94             : 
      95             : template<typename T, class P>
      96     6575672 : void List<T, P>::InsertAt(int index, const T& elm, P alloc) {
      97             :   DCHECK(index >= 0 && index <= length_);
      98     6575672 :   Add(elm, alloc);
      99    24050994 :   for (int i = length_ - 1; i > index; --i) {
     100    17475319 :     data_[i] = data_[i - 1];
     101             :   }
     102     6575675 :   data_[index] = elm;
     103     6575675 : }
     104             : 
     105             : 
     106             : template<typename T, class P>
     107   234089023 : T List<T, P>::Remove(int i) {
     108   234089023 :   T element = at(i);
     109   234089023 :   length_--;
     110   610696519 :   while (i < length_) {
     111   142518473 :     data_[i] = data_[i + 1];
     112   142518473 :     i++;
     113             :   }
     114   234089023 :   return element;
     115             : }
     116             : 
     117             : 
     118             : template<typename T, class P>
     119    30217682 : bool List<T, P>::RemoveElement(const T& elm) {
     120    79879053 :   for (int i = 0; i < length_; i++) {
     121    79878716 :     if (data_[i] == elm) {
     122    30217345 :       Remove(i);
     123    30217971 :       return true;
     124             :     }
     125             :   }
     126             :   return false;
     127             : }
     128             : 
     129             : template <typename T, class P>
     130             : void List<T, P>::Swap(List<T, P>* list) {
     131      862979 :   std::swap(data_, list->data_);
     132      862979 :   std::swap(length_, list->length_);
     133      862979 :   std::swap(capacity_, list->capacity_);
     134             : }
     135             : 
     136             : template<typename T, class P>
     137             : void List<T, P>::Allocate(int length, P allocator) {
     138          18 :   DeleteData(data_);
     139             :   Initialize(length, allocator);
     140          18 :   length_ = length;
     141             : }
     142             : 
     143             : 
     144             : template<typename T, class P>
     145             : void List<T, P>::Clear() {
     146     5267525 :   DeleteData(data_);
     147             :   // We don't call Initialize(0) since that requires passing a Zone,
     148             :   // which we don't really need.
     149    37490373 :   data_ = NULL;
     150    37490373 :   capacity_ = 0;
     151    37490373 :   length_ = 0;
     152             : }
     153             : 
     154             : 
     155             : template<typename T, class P>
     156             : void List<T, P>::Rewind(int pos) {
     157             :   DCHECK(0 <= pos && pos <= length_);
     158   996455536 :   length_ = pos;
     159             : }
     160             : 
     161             : 
     162             : template<typename T, class P>
     163             : void List<T, P>::Trim(P alloc) {
     164      229227 :   if (length_ < capacity_ / 4) {
     165       12529 :     Resize(capacity_ / 2, alloc);
     166             :   }
     167             : }
     168             : 
     169             : 
     170             : template<typename T, class P>
     171             : void List<T, P>::Iterate(void (*callback)(T* x)) {
     172         468 :   for (int i = 0; i < length_; i++) callback(&data_[i]);
     173             : }
     174             : 
     175             : 
     176             : template<typename T, class P>
     177             : template<class Visitor>
     178             : void List<T, P>::Iterate(Visitor* visitor) {
     179             :   for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
     180             : }
     181             : 
     182             : 
     183             : template<typename T, class P>
     184             : bool List<T, P>::Contains(const T& elm) const {
     185 18573255680 :   for (int i = 0; i < length_; i++) {
     186 18573756111 :     if (data_[i] == elm)
     187             :       return true;
     188             :   }
     189             :   return false;
     190             : }
     191             : 
     192             : 
     193             : template<typename T, class P>
     194             : int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
     195             :   int result = 0;
     196             :   for (int i = start; i <= end; i++) {
     197             :     if (data_[i] == elm) ++result;
     198             :   }
     199             :   return result;
     200             : }
     201             : 
     202             : 
     203             : template <typename T, class P>
     204             : template <typename CompareFunction>
     205             : void List<T, P>::Sort(CompareFunction cmp) {
     206      568305 :   Sort(cmp, 0, length_);
     207             : }
     208             : 
     209             : 
     210             : template <typename T, class P>
     211             : template <typename CompareFunction>
     212      568305 : void List<T, P>::Sort(CompareFunction cmp, size_t s, size_t l) {
     213      568305 :   ToVector().Sort(cmp, s, l);
     214             : #ifdef DEBUG
     215             :   for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
     216             : #endif
     217             : }
     218             : 
     219             : 
     220             : template<typename T, class P>
     221             : void List<T, P>::Sort() {
     222             :   ToVector().Sort();
     223             : }
     224             : 
     225             : 
     226             : template <typename T, class P>
     227             : template <typename CompareFunction>
     228             : void List<T, P>::StableSort(CompareFunction cmp) {
     229             :   StableSort(cmp, 0, length_);
     230             : }
     231             : 
     232             : 
     233             : template <typename T, class P>
     234             : template <typename CompareFunction>
     235       11407 : void List<T, P>::StableSort(CompareFunction cmp, size_t s, size_t l) {
     236       11407 :   ToVector().StableSort(cmp, s, l);
     237             : #ifdef DEBUG
     238             :   for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
     239             : #endif
     240             : }
     241             : 
     242             : 
     243             : template <typename T, class P>
     244             : void List<T, P>::StableSort() {
     245             :   ToVector().StableSort();
     246             : }
     247             : 
     248             : 
     249             : template <typename T, typename P>
     250     3311668 : int SortedListBSearch(const List<T>& list, P cmp) {
     251             :   int low = 0;
     252      248130 :   int high = list.length() - 1;
     253     3311680 :   while (low <= high) {
     254     3063538 :     int mid = low + (high - low) / 2;
     255     3063538 :     T mid_elem = list[mid];
     256             : 
     257     3063538 :     if (cmp(&mid_elem) > 0) {
     258     1338756 :       high = mid - 1;
     259     1338756 :       continue;
     260             :     }
     261     1724782 :     if (cmp(&mid_elem) < 0) {
     262     1476664 :       low = mid + 1;
     263     1476664 :       continue;
     264             :     }
     265             :     // Found the element.
     266             :     return mid;
     267             :   }
     268             :   return -1;
     269             : }
     270             : 
     271             : 
     272             : template<typename T>
     273             : class ElementCmp {
     274             :  public:
     275             :   explicit ElementCmp(T e) : elem_(e) {}
     276             :   int operator()(const T* other) {
     277             :     return PointerValueCompare(other, &elem_);
     278             :   }
     279             :  private:
     280             :   T elem_;
     281             : };
     282             : 
     283             : 
     284             : template <typename T>
     285             : int SortedListBSearch(const List<T>& list, T elem) {
     286             :   return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem));
     287             : }
     288             : 
     289             : 
     290             : }  // namespace internal
     291             : }  // namespace v8
     292             : 
     293             : #endif  // V8_LIST_INL_H_

Generated by: LCOV version 1.10