LCOV - code coverage report
Current view: top level - src/zone - zone-chunk-list.h (source / functions) Hit Total Coverage
Test: app.info Lines: 26 26 100.0 %
Date: 2017-04-26 Functions: 3 3 100.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             : #include <stdlib.h>
       6             : 
       7             : #include "src/globals.h"
       8             : #include "src/utils.h"
       9             : #include "src/zone/zone.h"
      10             : 
      11             : #ifndef V8_SRC_ZONE_ZONE_CHUNK_LIST_H_
      12             : #define V8_SRC_ZONE_ZONE_CHUNK_LIST_H_
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : 
      17             : template <typename T>
      18             : class ZoneChunkListIterator;
      19             : template <typename T>
      20             : class ForwardZoneChunkListIterator;
      21             : template <typename T>
      22             : class ReverseZoneChunkListIterator;
      23             : 
      24             : // A zone-backed hybrid of a vector and a linked list. Use it if you need a
      25             : // collection that
      26             : // * needs to grow indefinitely,
      27             : // * will mostly grow at the back, but may sometimes grow in front as well
      28             : // (preferrably in batches),
      29             : // * needs to have very low overhead,
      30             : // * offers forward- and backwards-iteration,
      31             : // * offers relatively fast seeking,
      32             : // * offers bidirectional iterators,
      33             : // * can be rewound without freeing the backing store.
      34             : // This list will maintain a doubly-linked list of chunks. When a chunk is
      35             : // filled up, a new one gets appended. New chunks appended at the end will
      36             : // grow in size up to a certain limit to avoid over-allocation and to keep
      37             : // the zone clean.
      38             : template <typename T>
      39             : class ZoneChunkList : public ZoneObject {
      40             :  public:
      41             :   enum class StartMode {
      42             :     // The list will not allocate a starting chunk. Use if you expect your
      43             :     // list to remain empty in many cases.
      44             :     kEmpty = 0,
      45             :     // The list will start with a small initial chunk. Subsequent chunks will
      46             :     // get bigger over time.
      47             :     kSmall = 8,
      48             :     // The list will start with one chunk at maximum size. Use this if you
      49             :     // expect your list to contain many items to avoid growing chunks.
      50             :     kBig = 256
      51             :   };
      52             : 
      53             :   explicit ZoneChunkList(Zone* zone, StartMode start_mode = StartMode::kEmpty)
      54     1191477 :       : zone_(zone) {
      55             :     if (start_mode != StartMode::kEmpty) {
      56             :       front_ = NewChunk(static_cast<uint32_t>(start_mode));
      57             :       back_ = front_;
      58             :     }
      59             :   }
      60             : 
      61             :   size_t size() const;
      62             : 
      63             :   T& front() const;
      64             :   T& back() const;
      65             : 
      66             :   void push_back(const T& item);
      67             :   void pop_back();
      68             : 
      69             :   // Will push a separate chunk to the front of the chunk-list.
      70             :   // Very memory-inefficient. Do only use sparsely! If you have many items to
      71             :   // add in front, consider using 'push_front_many'.
      72             :   void push_front(const T& item);
      73             :   // TODO(heimbuef): Add 'push_front_many'.
      74             : 
      75             :   // Cuts the last list elements so at most 'limit' many remain. Does not
      76             :   // free the actual memory, since it is zone allocated.
      77             :   void Rewind(const size_t limit = 0);
      78             : 
      79             :   // Quickly scans the list to retrieve the element at the given index. Will
      80             :   // *not* check bounds.
      81             :   ForwardZoneChunkListIterator<T> Find(const size_t index);
      82             :   ForwardZoneChunkListIterator<const T> Find(const size_t index) const;
      83             :   // TODO(heimbuef): Add 'rFind', seeking from the end and returning a
      84             :   // reverse iterator.
      85             : 
      86             :   void CopyTo(T* ptr);
      87             : 
      88             :   ForwardZoneChunkListIterator<T> begin();
      89             :   ForwardZoneChunkListIterator<T> end();
      90             :   ReverseZoneChunkListIterator<T> rbegin();
      91             :   ReverseZoneChunkListIterator<T> rend();
      92             :   ForwardZoneChunkListIterator<const T> begin() const;
      93             :   ForwardZoneChunkListIterator<const T> end() const;
      94             :   ReverseZoneChunkListIterator<const T> rbegin() const;
      95             :   ReverseZoneChunkListIterator<const T> rend() const;
      96             : 
      97             :  private:
      98             :   friend class ZoneChunkListIterator<T>;
      99             :   friend class ForwardZoneChunkListIterator<T>;
     100             :   friend class ReverseZoneChunkListIterator<T>;
     101             :   static const uint32_t kMaxChunkCapacity = 256u;
     102             : 
     103             :   STATIC_ASSERT(kMaxChunkCapacity == static_cast<uint32_t>(StartMode::kBig));
     104             : 
     105             :   struct Chunk {
     106             :     uint32_t capacity_ = 0;
     107             :     uint32_t position_ = 0;
     108             :     Chunk* next_ = nullptr;
     109             :     Chunk* previous_ = nullptr;
     110             :     T* items() { return reinterpret_cast<T*>(this + 1); }
     111             :   };
     112             : 
     113     3331102 :   Chunk* NewChunk(const uint32_t capacity) {
     114             :     Chunk* chunk =
     115     3331102 :         new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk();
     116     3331103 :     chunk->capacity_ = capacity;
     117     3331103 :     return chunk;
     118             :   }
     119             : 
     120             :   struct SeekResult {
     121             :     Chunk* chunk_;
     122             :     uint32_t chunk_index_;
     123             :   };
     124             : 
     125             :   // Returns the chunk and relative index of the element at the given global
     126             :   // index. Will skip entire chunks and is therefore faster than iterating.
     127             :   SeekResult SeekIndex(size_t index) const;
     128             : 
     129             :   Zone* zone_;
     130             : 
     131             :   size_t size_ = 0;
     132             :   Chunk* front_ = nullptr;
     133             :   Chunk* back_ = nullptr;
     134             : 
     135             :   DISALLOW_COPY_AND_ASSIGN(ZoneChunkList);
     136             : };
     137             : 
     138             : template <typename T>
     139             : class ZoneChunkListIterator {
     140             :  public:
     141             :   T& operator*() { return current_->items()[position_]; }
     142             :   bool operator==(const ZoneChunkListIterator& other) {
     143             :     return other.current_ == current_ && other.position_ == position_;
     144             :   }
     145             :   bool operator!=(const ZoneChunkListIterator& other) {
     146             :     return !operator==(other);
     147             :   }
     148             : 
     149             :  protected:
     150             :   ZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current,
     151             :                         size_t position)
     152             :       : current_(current), position_(position) {}
     153             : 
     154             :   void MoveNext() {
     155             :     ++position_;
     156             :     if (position_ >= current_->capacity_) {
     157             :       current_ = current_->next_;
     158             :       position_ = 0;
     159             :     }
     160             :   }
     161             : 
     162             :   void MoveRNext() {
     163             :     if (position_ == 0) {
     164             :       current_ = current_->previous_;
     165             :       position_ = current_ ? current_->capacity_ - 1 : 0;
     166             :     } else {
     167             :       --position_;
     168             :     }
     169             :   }
     170             : 
     171             :   typename ZoneChunkList<T>::Chunk* current_;
     172             :   size_t position_;
     173             : };
     174             : 
     175             : template <typename T>
     176             : class ForwardZoneChunkListIterator : public ZoneChunkListIterator<T> {
     177             :   using ZoneChunkListIterator<T>::current_;
     178             :   using ZoneChunkListIterator<T>::position_;
     179             :   using ZoneChunkListIterator<T>::MoveNext;
     180             :   using ZoneChunkListIterator<T>::MoveRNext;
     181             : 
     182             :  public:
     183             :   ForwardZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current,
     184             :                                size_t position)
     185             :       : ZoneChunkListIterator<T>(current, position) {}
     186             : 
     187             :   ForwardZoneChunkListIterator& operator++() {
     188             :     MoveNext();
     189             :     return *this;
     190             :   }
     191             : 
     192             :   ForwardZoneChunkListIterator operator++(int) {
     193             :     ForwardZoneChunkListIterator<T> clone(*this);
     194             :     MoveNext();
     195             :     return clone;
     196             :   }
     197             : 
     198             :   ForwardZoneChunkListIterator& operator--() {
     199             :     MoveRNext();
     200             :     return *this;
     201             :   }
     202             : 
     203             :   ForwardZoneChunkListIterator operator--(int) {
     204             :     ForwardZoneChunkListIterator<T> clone(*this);
     205             :     MoveRNext();
     206             :     return clone;
     207             :   }
     208             : 
     209             :  private:
     210             :   friend class ZoneChunkList<T>;
     211             :   static ForwardZoneChunkListIterator<T> Begin(ZoneChunkList<T>* list) {
     212             :     return ForwardZoneChunkListIterator<T>(list->front_, 0);
     213             :   }
     214             :   static ForwardZoneChunkListIterator<T> End(ZoneChunkList<T>* list) {
     215             :     if (list->back_ == nullptr) return Begin(list);
     216             : 
     217             :     DCHECK_LE(list->back_->position_, list->back_->capacity_);
     218             :     if (list->back_->position_ == list->back_->capacity_) {
     219             :       return ForwardZoneChunkListIterator<T>(nullptr, 0);
     220             :     }
     221             : 
     222             :     return ForwardZoneChunkListIterator<T>(list->back_, list->back_->position_);
     223             :   }
     224             : };
     225             : 
     226             : template <typename T>
     227             : class ReverseZoneChunkListIterator : public ZoneChunkListIterator<T> {
     228             :   using ZoneChunkListIterator<T>::current_;
     229             :   using ZoneChunkListIterator<T>::position_;
     230             :   using ZoneChunkListIterator<T>::MoveNext;
     231             :   using ZoneChunkListIterator<T>::MoveRNext;
     232             : 
     233             :  public:
     234             :   ReverseZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current,
     235             :                                size_t position)
     236             :       : ZoneChunkListIterator<T>(current, position) {}
     237             : 
     238             :   ReverseZoneChunkListIterator& operator++() {
     239             :     MoveRNext();
     240             :     return *this;
     241             :   }
     242             : 
     243             :   ReverseZoneChunkListIterator operator++(int) {
     244             :     ReverseZoneChunkListIterator<T> clone(*this);
     245             :     MoveRNext();
     246             :     return clone;
     247             :   }
     248             : 
     249             :   ReverseZoneChunkListIterator& operator--() {
     250             :     MoveNext();
     251             :     return *this;
     252             :   }
     253             : 
     254             :   ReverseZoneChunkListIterator operator--(int) {
     255             :     ForwardZoneChunkListIterator<T> clone(*this);
     256             :     MoveNext();
     257             :     return clone;
     258             :   }
     259             : 
     260             :  private:
     261             :   friend class ZoneChunkList<T>;
     262             :   static ReverseZoneChunkListIterator<T> Begin(ZoneChunkList<T>* list) {
     263             :     if (list->back_ == nullptr) return End(list);
     264             :     if (list->back_->position_ == 0) {
     265             :       if (list->back_->previous_ != nullptr) {
     266             :         return ReverseZoneChunkListIterator<T>(
     267             :             list->back_->previous_, list->back_->previous_->capacity_ - 1);
     268             :       } else {
     269             :         return End(list);
     270             :       }
     271             :     }
     272             :     return ReverseZoneChunkListIterator<T>(list->back_,
     273             :                                            list->back_->position_ - 1);
     274             :   }
     275             :   static ReverseZoneChunkListIterator<T> End(ZoneChunkList<T>* list) {
     276             :     return ReverseZoneChunkListIterator<T>(nullptr, 0);
     277             :   }
     278             : };
     279             : 
     280             : template <typename T>
     281             : size_t ZoneChunkList<T>::size() const {
     282             :   return size_;
     283             : }
     284             : 
     285             : template <typename T>
     286             : T& ZoneChunkList<T>::front() const {
     287             :   DCHECK_LT(size_t(0), size());
     288             :   return front_->items()[0];
     289             : }
     290             : 
     291             : template <typename T>
     292             : T& ZoneChunkList<T>::back() const {
     293             :   DCHECK_LT(size_t(0), size());
     294             : 
     295             :   if (back_->position_ == 0) {
     296             :     return back_->previous_->items()[back_->previous_->position_ - 1];
     297             :   } else {
     298             :     return back_->items()[back_->position_ - 1];
     299             :   }
     300             : }
     301             : 
     302             : template <typename T>
     303   287162386 : void ZoneChunkList<T>::push_back(const T& item) {
     304   283831284 :   if (back_ == nullptr) {
     305      670891 :     front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall));
     306      670891 :     back_ = front_;
     307             :   }
     308             : 
     309             :   DCHECK_LE(back_->position_, back_->capacity_);
     310   283831284 :   if (back_->position_ == back_->capacity_) {
     311     2660211 :     if (back_->next_ == nullptr) {
     312     5320422 :       Chunk* chunk = NewChunk(Min(back_->capacity_ << 1, kMaxChunkCapacity));
     313     2660212 :       back_->next_ = chunk;
     314     2660212 :       chunk->previous_ = back_;
     315             :     }
     316     2660212 :     back_ = back_->next_;
     317             :   }
     318   283831285 :   back_->items()[back_->position_] = item;
     319   283831285 :   ++back_->position_;
     320   283831285 :   ++size_;
     321   283831285 : }
     322             : 
     323             : template <typename T>
     324             : void ZoneChunkList<T>::pop_back() {
     325             :   DCHECK_LT(size_t(0), size());
     326             :   if (back_->position_ == 0) {
     327             :     back_ = back_->previous_;
     328             :   }
     329             :   --back_->position_;
     330             : }
     331             : 
     332             : template <typename T>
     333             : void ZoneChunkList<T>::push_front(const T& item) {
     334             :   Chunk* chunk = NewChunk(1);  // Yes, this gets really inefficient.
     335             :   chunk->next_ = front_;
     336             :   if (front_) {
     337             :     front_->previous_ = chunk;
     338             :   } else {
     339             :     back_ = chunk;
     340             :   }
     341             :   front_ = chunk;
     342             : 
     343             :   chunk->items()[0] = item;
     344             :   chunk->position_ = 1;
     345             :   ++size_;
     346             : }
     347             : 
     348             : template <typename T>
     349             : typename ZoneChunkList<T>::SeekResult ZoneChunkList<T>::SeekIndex(
     350             :     size_t index) const {
     351             :   DCHECK_LT(index, size());
     352             :   Chunk* current = front_;
     353             :   while (index > current->capacity_) {
     354             :     index -= current->capacity_;
     355             :     current = current->next_;
     356             :   }
     357             :   return {current, static_cast<uint32_t>(index)};
     358             : }
     359             : 
     360             : template <typename T>
     361             : void ZoneChunkList<T>::Rewind(const size_t limit) {
     362             :   if (limit >= size()) return;
     363             : 
     364             :   SeekResult seek_result = SeekIndex(limit);
     365             :   DCHECK_NOT_NULL(seek_result.chunk_);
     366             : 
     367             :   // Do a partial rewind of the chunk containing the index.
     368             :   seek_result.chunk_->position_ = seek_result.chunk_index_;
     369             : 
     370             :   // Set back_ so iterators will work correctly.
     371             :   back_ = seek_result.chunk_;
     372             : 
     373             :   // Do full rewind of all subsequent chunks.
     374             :   for (Chunk* current = seek_result.chunk_->next_; current != nullptr;
     375             :        current = current->next_) {
     376             :     current->position_ = 0;
     377             :   }
     378             : 
     379             :   size_ = limit;
     380             : }
     381             : 
     382             : template <typename T>
     383             : ForwardZoneChunkListIterator<T> ZoneChunkList<T>::Find(const size_t index) {
     384             :   SeekResult seek_result = SeekIndex(index);
     385             :   return ForwardZoneChunkListIterator<T>(seek_result.chunk_,
     386             :                                          seek_result.chunk_index_);
     387             : }
     388             : 
     389             : template <typename T>
     390             : ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::Find(
     391             :     const size_t index) const {
     392             :   SeekResult seek_result = SeekIndex(index);
     393             :   return ForwardZoneChunkListIterator<const T>(seek_result.chunk_,
     394             :                                                seek_result.chunk_index_);
     395             : }
     396             : 
     397             : template <typename T>
     398      670855 : void ZoneChunkList<T>::CopyTo(T* ptr) {
     399     4001756 :   for (Chunk* current = front_; current != nullptr; current = current->next_) {
     400     3330901 :     void* start = current->items();
     401     3330901 :     void* end = current->items() + current->position_;
     402             :     size_t bytes = static_cast<size_t>(reinterpret_cast<uintptr_t>(end) -
     403     3330901 :                                        reinterpret_cast<uintptr_t>(start));
     404             : 
     405             :     MemCopy(ptr, current->items(), bytes);
     406     3330901 :     ptr += current->position_;
     407             :   }
     408      670855 : }
     409             : 
     410             : template <typename T>
     411             : ForwardZoneChunkListIterator<T> ZoneChunkList<T>::begin() {
     412             :   return ForwardZoneChunkListIterator<T>::Begin(this);
     413             : }
     414             : 
     415             : template <typename T>
     416             : ForwardZoneChunkListIterator<T> ZoneChunkList<T>::end() {
     417             :   return ForwardZoneChunkListIterator<T>::End(this);
     418             : }
     419             : 
     420             : template <typename T>
     421             : ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rbegin() {
     422             :   return ReverseZoneChunkListIterator<T>::Begin(this);
     423             : }
     424             : 
     425             : template <typename T>
     426             : ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rend() {
     427             :   return ReverseZoneChunkListIterator<T>::End(this);
     428             : }
     429             : 
     430             : template <typename T>
     431             : ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::begin() const {
     432             :   return ForwardZoneChunkListIterator<const T>::Begin(this);
     433             : }
     434             : 
     435             : template <typename T>
     436             : ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::end() const {
     437             :   return ForwardZoneChunkListIterator<const T>::End(this);
     438             : }
     439             : 
     440             : template <typename T>
     441             : ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rbegin() const {
     442             :   return ReverseZoneChunkListIterator<const T>::Begin(this);
     443             : }
     444             : 
     445             : template <typename T>
     446             : ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rend() const {
     447             :   return ReverseZoneChunkListIterator<const T>::End(this);
     448             : }
     449             : 
     450             : }  // namespace internal
     451             : }  // namespace v8
     452             : 
     453             : #endif  // V8_SRC_ZONE_ZONE_CHUNK_LIST_H_

Generated by: LCOV version 1.10