7 #include "src/base/iterator.h" 8 #include "src/globals.h" 10 #include "src/zone/zone.h" 12 #ifndef V8_ZONE_ZONE_CHUNK_LIST_H_ 13 #define V8_ZONE_ZONE_CHUNK_LIST_H_ 18 template <
typename T,
bool backwards,
bool modifiable>
43 enum class StartMode {
57 if (start_mode != StartMode::kEmpty) {
58 front_ = NewChunk(static_cast<uint32_t>(start_mode));
63 size_t size()
const {
return size_; }
64 bool is_empty()
const {
return size() == 0; }
69 void push_back(
const T& item);
75 void push_front(
const T& item);
80 void Rewind(
const size_t limit = 0);
91 iterator begin() {
return iterator::Begin(
this); }
92 iterator end() {
return iterator::End(
this); }
95 const_iterator begin()
const {
return const_iterator::Begin(
this); }
98 return const_reverse_iterator::Begin(
this);
101 return const_reverse_iterator::End(
this);
105 template <
typename S,
bool backwards,
bool modifiable>
108 static constexpr
uint32_t kMaxChunkCapacity = 256u;
110 STATIC_ASSERT(kMaxChunkCapacity == static_cast<uint32_t>(StartMode::kBig));
115 Chunk* next_ =
nullptr;
116 Chunk* previous_ =
nullptr;
117 T* items() {
return reinterpret_cast<T*
>(
this + 1); }
118 const T* items()
const {
return reinterpret_cast<const T*
>(
this + 1); }
121 Chunk* NewChunk(
const uint32_t capacity) {
123 new (zone_->New(
sizeof(Chunk) + capacity *
sizeof(
T))) Chunk();
124 chunk->capacity_ = capacity;
135 SeekResult SeekIndex(
size_t index)
const;
140 Chunk* front_ =
nullptr;
141 Chunk* back_ =
nullptr;
146 template <
typename T,
bool backwards,
bool modifiable>
150 template <
typename S>
152 typename std::conditional<modifiable, S,
153 typename std::add_const<S>::type>
::type;
154 using Chunk = maybe_const<typename ZoneChunkList<T>::Chunk>;
155 using ChunkList = maybe_const<ZoneChunkList<T>>;
158 maybe_const<T>& operator*()
const {
return current_->items()[position_]; }
159 maybe_const<T>* operator->()
const {
return ¤t_->items()[position_]; }
160 bool operator==(
const ZoneChunkListIterator& other)
const {
161 return other.current_ == current_ && other.position_ == position_;
163 bool operator!=(
const ZoneChunkListIterator& other)
const {
164 return !operator==(other);
167 ZoneChunkListIterator& operator++() {
172 ZoneChunkListIterator operator++(
int) {
173 ZoneChunkListIterator clone(*
this);
178 ZoneChunkListIterator& operator--() {
183 ZoneChunkListIterator operator--(
int) {
184 ZoneChunkListIterator clone(*
this);
189 void Advance(
int amount) {
191 DCHECK_GE(amount, 0);
193 ZoneChunkListIterator clone(*
this);
194 for (
int i = 0;
i < amount; ++
i) {
200 while (position_ > 0 && position_ >= current_->capacity_) {
201 auto overshoot = position_ - current_->capacity_;
202 current_ = current_->next_;
203 position_ = overshoot;
205 DCHECK(position_ == 0 || current_);
209 DCHECK_EQ(clone, *
this);
214 friend class ZoneChunkList<T>;
216 static ZoneChunkListIterator Begin(ChunkList* list) {
218 if (!backwards)
return ZoneChunkListIterator(list->front_, 0);
221 if (list->back_ ==
nullptr)
return End(list);
222 if (list->back_->position_ == 0) {
223 if (list->back_->previous_ !=
nullptr) {
224 return ZoneChunkListIterator(list->back_->previous_,
225 list->back_->previous_->capacity_ - 1);
230 return ZoneChunkListIterator(list->back_, list->back_->position_ - 1);
233 static ZoneChunkListIterator End(ChunkList* list) {
235 if (backwards)
return ZoneChunkListIterator(
nullptr, 0);
238 if (list->back_ ==
nullptr)
return Begin(list);
240 DCHECK_LE(list->back_->position_, list->back_->capacity_);
241 if (list->back_->position_ == list->back_->capacity_) {
242 return ZoneChunkListIterator(list->back_->next_, 0);
245 return ZoneChunkListIterator(list->back_, list->back_->position_);
248 ZoneChunkListIterator(Chunk* current,
size_t position)
249 : current_(current), position_(position) {
250 DCHECK(current ==
nullptr || position < current->capacity_);
253 template <
bool move_backward>
257 if (position_ == 0) {
258 current_ = current_->previous_;
259 position_ = current_ ? current_->capacity_ - 1 : 0;
266 if (position_ >= current_->capacity_) {
267 current_ = current_->next_;
277 template <
typename T>
278 T& ZoneChunkList<T>::front()
const {
279 DCHECK_LT(
size_t(0), size());
280 return front_->items()[0];
283 template <
typename T>
284 T& ZoneChunkList<T>::back()
const {
285 DCHECK_LT(
size_t(0), size());
287 if (back_->position_ == 0) {
288 return back_->previous_->items()[back_->previous_->position_ - 1];
290 return back_->items()[back_->position_ - 1];
294 template <
typename T>
295 void ZoneChunkList<T>::push_back(
const T& item) {
296 if (back_ ==
nullptr) {
297 front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall));
301 DCHECK_LE(back_->position_, back_->capacity_);
302 if (back_->position_ == back_->capacity_) {
303 if (back_->next_ ==
nullptr) {
304 Chunk* chunk = NewChunk(Min(back_->capacity_ << 1, kMaxChunkCapacity));
305 back_->next_ = chunk;
306 chunk->previous_ = back_;
308 back_ = back_->next_;
310 back_->items()[back_->position_] = item;
313 DCHECK_LE(back_->position_, back_->capacity_);
316 template <
typename T>
317 void ZoneChunkList<T>::pop_back() {
318 DCHECK_LT(
size_t(0), size());
319 if (back_->position_ == 0) {
320 back_ = back_->previous_;
326 template <
typename T>
327 void ZoneChunkList<T>::push_front(
const T& item) {
328 Chunk* chunk = NewChunk(1);
329 chunk->next_ = front_;
331 front_->previous_ = chunk;
337 chunk->items()[0] = item;
338 chunk->position_ = 1;
342 template <
typename T>
343 typename ZoneChunkList<T>::SeekResult ZoneChunkList<T>::SeekIndex(
344 size_t index)
const {
345 DCHECK_LT(index, size());
346 Chunk* current = front_;
347 while (index >= current->capacity_) {
348 index -= current->capacity_;
349 current = current->next_;
351 DCHECK_LT(index, current->capacity_);
352 return {current,
static_cast<uint32_t>(index)};
355 template <
typename T>
356 void ZoneChunkList<T>::Rewind(
const size_t limit) {
357 if (limit >= size())
return;
359 SeekResult seek_result = SeekIndex(limit);
360 DCHECK_NOT_NULL(seek_result.chunk_);
363 seek_result.chunk_->position_ = seek_result.chunk_index_;
366 back_ = seek_result.chunk_;
369 for (Chunk* current = seek_result.chunk_->next_; current !=
nullptr;
370 current = current->next_) {
371 current->position_ = 0;
377 template <
typename T>
378 typename ZoneChunkList<T>::iterator ZoneChunkList<T>::Find(
const size_t index) {
379 SeekResult seek_result = SeekIndex(index);
380 return typename ZoneChunkList<T>::iterator(seek_result.chunk_,
381 seek_result.chunk_index_);
384 template <
typename T>
385 typename ZoneChunkList<T>::const_iterator ZoneChunkList<T>::Find(
386 const size_t index)
const {
387 SeekResult seek_result = SeekIndex(index);
388 return typename ZoneChunkList<T>::const_iterator(seek_result.chunk_,
389 seek_result.chunk_index_);
392 template <
typename T>
393 void ZoneChunkList<T>::CopyTo(T* ptr) {
394 for (Chunk* current = front_; current !=
nullptr; current = current->next_) {
395 void* start = current->items();
396 void* end = current->items() + current->position_;
397 size_t bytes =
static_cast<size_t>(
reinterpret_cast<uintptr_t>(end) -
398 reinterpret_cast<uintptr_t>(start));
400 MemCopy(ptr, current->items(), bytes);
401 ptr += current->position_;
408 #endif // V8_ZONE_ZONE_CHUNK_LIST_H_