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