LCOV - code coverage report
Current view: top level - src - list.h (source / functions) Hit Total Coverage
Test: app.info Lines: 20 22 90.9 %
Date: 2017-04-26 Functions: 25 28 89.3 %

          Line data    Source code
       1             : // Copyright 2011 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_H_
       6             : #define V8_LIST_H_
       7             : 
       8             : #include <algorithm>
       9             : 
      10             : #include "src/checks.h"
      11             : #include "src/vector.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : 
      16             : template<typename T> class Vector;
      17             : 
      18             : // ----------------------------------------------------------------------------
      19             : // The list is a template for very light-weight lists. We are not
      20             : // using the STL because we want full control over space and speed of
      21             : // the code. This implementation is based on code by Robert Griesemer
      22             : // and Rob Pike.
      23             : //
      24             : // The list is parameterized by the type of its elements (T) and by an
      25             : // allocation policy (P). The policy is used for allocating lists in
      26             : // the C free store or the zone; see zone.h.
      27             : 
      28             : // Forward defined as
      29             : // template <typename T,
      30             : //           class AllocationPolicy = FreeStoreAllocationPolicy> class List;
      31             : template <typename T, class AllocationPolicy>
      32             : class List {
      33             :  public:
      34      229995 :   explicit List(AllocationPolicy allocator = AllocationPolicy()) {
      35             :     Initialize(0, allocator);
      36      229995 :   }
      37             :   INLINE(explicit List(int capacity,
      38             :                        AllocationPolicy allocator = AllocationPolicy())) {
      39             :     Initialize(capacity, allocator);
      40             :   }
      41   101130364 :   INLINE(~List()) { DeleteData(data_); }
      42             : 
      43             :   // Deallocates memory used by the list and leaves the list in a consistent
      44             :   // empty state.
      45             :   void Free() {
      46      266213 :     DeleteData(data_);
      47             :     Initialize(0);
      48             :   }
      49             : 
      50             :   INLINE(void* operator new(size_t size,
      51             :                             AllocationPolicy allocator = AllocationPolicy())) {
      52             :     return allocator.New(static_cast<int>(size));
      53             :   }
      54             :   INLINE(void operator delete(void* p)) {
      55             :     AllocationPolicy::Delete(p);
      56             :   }
      57             : 
      58             :   // Please the MSVC compiler.  We should never have to execute this.
      59             :   INLINE(void operator delete(void* p, AllocationPolicy allocator)) {
      60             :     UNREACHABLE();
      61             :   }
      62             : 
      63             :   // Returns a reference to the element at index i.  This reference is
      64             :   // not safe to use after operations that can change the list's
      65             :   // backing store (e.g. Add).
      66    22191512 :   inline T& operator[](int i) const {
      67             :     DCHECK_LE(0, i);
      68             :     DCHECK_GT(static_cast<unsigned>(length_), static_cast<unsigned>(i));
      69  5910267210 :     return data_[i];
      70             :   }
      71  3562718164 :   inline T& at(int i) const { return operator[](i); }
      72   301713969 :   inline T& last() const { return at(length_ - 1); }
      73    96084808 :   inline T& first() const { return at(0); }
      74             : 
      75             :   typedef T* iterator;
      76     1758539 :   inline iterator begin() const { return &data_[0]; }
      77     6408421 :   inline iterator end() const { return &data_[length_]; }
      78             : 
      79             :   INLINE(bool is_empty() const) { return length_ == 0; }
      80             :   INLINE(int length() const) { return length_; }
      81             :   INLINE(int capacity() const) { return capacity_; }
      82             : 
      83             :   Vector<T> ToVector() const { return Vector<T>(data_, length_); }
      84             : 
      85             :   Vector<const T> ToConstVector() const {
      86             :     return Vector<const T>(data_, length_);
      87             :   }
      88             : 
      89             :   // Adds a copy of the given 'element' to the end of the list,
      90             :   // expanding the list if necessary.
      91     5394221 :   void Add(const T& element, AllocationPolicy allocator = AllocationPolicy());
      92             : 
      93             :   // Add all the elements from the argument list to this list.
      94      292160 :   void AddAll(const List<T, AllocationPolicy>& other,
      95             :               AllocationPolicy allocator = AllocationPolicy());
      96             : 
      97             :   // Add all the elements from the vector to this list.
      98     5986314 :   void AddAll(const Vector<T>& other,
      99             :               AllocationPolicy allocator = AllocationPolicy());
     100             : 
     101             :   // Inserts the element at the specific index.
     102        2699 :   void InsertAt(int index, const T& element,
     103             :                 AllocationPolicy allocator = AllocationPolicy());
     104             : 
     105             :   // Overwrites the element at the specific index.
     106             :   void Set(int index, const T& element);
     107             : 
     108             :   // Added 'count' elements with the value 'value' and returns a
     109             :   // vector that allows access to the elements.  The vector is valid
     110             :   // until the next change is made to this list.
     111             :   Vector<T> AddBlock(T value, int count,
     112             :                      AllocationPolicy allocator = AllocationPolicy());
     113             : 
     114             :   // Removes the i'th element without deleting it even if T is a
     115             :   // pointer type; moves all elements above i "down". Returns the
     116             :   // removed element.  This function's complexity is linear in the
     117             :   // size of the list.
     118             :   T Remove(int i);
     119             : 
     120             :   // Remove the given element from the list. Returns whether or not
     121             :   // the input is included in the list in the first place.
     122             :   bool RemoveElement(const T& elm);
     123             : 
     124             :   // Removes the last element without deleting it even if T is a
     125             :   // pointer type. Returns the removed element.
     126   203849142 :   INLINE(T RemoveLast()) { return Remove(length_ - 1); }
     127             : 
     128             :   // Deletes current list contents and allocates space for 'length' elements.
     129             :   INLINE(void Allocate(int length,
     130             :                        AllocationPolicy allocator = AllocationPolicy()));
     131             : 
     132             :   // Clears the list by freeing the storage memory. If you want to keep the
     133             :   // memory, use Rewind(0) instead. Be aware, that even if T is a
     134             :   // pointer type, clearing the list doesn't delete the entries.
     135             :   INLINE(void Clear());
     136             : 
     137             :   // Drops all but the first 'pos' elements from the list.
     138             :   INLINE(void Rewind(int pos));
     139             : 
     140             :   // Drop the last 'count' elements from the list.
     141             :   INLINE(void RewindBy(int count)) { Rewind(length_ - count); }
     142             : 
     143             :   // Swaps the contents of the two lists.
     144             :   INLINE(void Swap(List<T, AllocationPolicy>* list));
     145             : 
     146             :   // Halve the capacity if fill level is less than a quarter.
     147             :   INLINE(void Trim(AllocationPolicy allocator = AllocationPolicy()));
     148             : 
     149             :   bool Contains(const T& elm) const;
     150             :   int CountOccurrences(const T& elm, int start, int end) const;
     151             : 
     152             :   // Iterate through all list entries, starting at index 0.
     153             :   void Iterate(void (*callback)(T* x));
     154             :   template<class Visitor>
     155             :   void Iterate(Visitor* visitor);
     156             : 
     157             :   // Sort all list entries (using QuickSort)
     158             :   template <typename CompareFunction>
     159             :   void Sort(CompareFunction cmp, size_t start, size_t length);
     160             :   template <typename CompareFunction>
     161             :   void Sort(CompareFunction cmp);
     162             :   void Sort();
     163             :   template <typename CompareFunction>
     164             :   void StableSort(CompareFunction cmp, size_t start, size_t length);
     165             :   template <typename CompareFunction>
     166             :   void StableSort(CompareFunction cmp);
     167             :   void StableSort();
     168             : 
     169             :   INLINE(void Initialize(int capacity,
     170             :                          AllocationPolicy allocator = AllocationPolicy())) {
     171             :     DCHECK(capacity >= 0);
     172   800094421 :     data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL;
     173   431665703 :     capacity_ = capacity;
     174   431665703 :     length_ = 0;
     175             :   }
     176             : 
     177             :  private:
     178             :   T* data_;
     179             :   int capacity_;
     180             :   int length_;
     181             : 
     182             :   INLINE(T* NewData(int n, AllocationPolicy allocator))  {
     183   381362930 :     return static_cast<T*>(allocator.New(n * sizeof(T)));
     184             :   }
     185             :   INLINE(void DeleteData(T* data))  {
     186             :     AllocationPolicy::Delete(data);
     187             :   }
     188             : 
     189             :   // Increase the capacity of a full list, and add an element.
     190             :   // List must be full already.
     191             :   void ResizeAdd(const T& element, AllocationPolicy allocator);
     192             : 
     193             :   // Inlined implementation of ResizeAdd, shared by inlined and
     194             :   // non-inlined versions of ResizeAdd.
     195             :   void ResizeAddInternal(const T& element, AllocationPolicy allocator);
     196             : 
     197             :   // Resize the list.
     198             :   void Resize(int new_capacity, AllocationPolicy allocator);
     199             : 
     200             :   DISALLOW_COPY_AND_ASSIGN(List);
     201             : };
     202             : 
     203             : 
     204             : template<typename T, class P>
     205           0 : size_t GetMemoryUsedByList(const List<T, P>& list) {
     206           0 :   return list.length() * sizeof(T) + sizeof(list);
     207             : }
     208             : 
     209             : 
     210             : class Map;
     211             : class FieldType;
     212             : class Code;
     213             : template<typename T> class Handle;
     214             : typedef List<Map*> MapList;
     215             : typedef List<Code*> CodeList;
     216             : typedef List<Handle<Map> > MapHandleList;
     217             : typedef List<Handle<FieldType> > TypeHandleList;
     218             : typedef List<Handle<Code> > CodeHandleList;
     219             : 
     220             : // Perform binary search for an element in an already sorted
     221             : // list. Returns the index of the element of -1 if it was not found.
     222             : // |cmp| is a predicate that takes a pointer to an element of the List
     223             : // and returns +1 if it is greater, -1 if it is less than the element
     224             : // being searched.
     225             : template <typename T, class P>
     226             : int SortedListBSearch(const List<T>& list, P cmp);
     227             : template <typename T>
     228             : int SortedListBSearch(const List<T>& list, T elem);
     229             : 
     230             : 
     231             : }  // namespace internal
     232             : }  // namespace v8
     233             : 
     234             : 
     235             : #endif  // V8_LIST_H_

Generated by: LCOV version 1.10