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
14namespace v8 {
15namespace internal {
16
17template <typename T>
18class ZoneChunkListIterator;
19template <typename T>
20class ForwardZoneChunkListIterator;
21template <typename T>
22class 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.
38template <typename T>
39class 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      : 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  Chunk* NewChunk(const uint32_t capacity) {
114    Chunk* chunk =
115        new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk();
116    chunk->capacity_ = capacity;
117    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
138template <typename T>
139class 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
175template <typename T>
176class 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
226template <typename T>
227class 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
280template <typename T>
281size_t ZoneChunkList<T>::size() const {
282  return size_;
283}
284
285template <typename T>
286T& ZoneChunkList<T>::front() const {
287  DCHECK_LT(size_t(0), size());
288  return front_->items()[0];
289}
290
291template <typename T>
292T& 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
302template <typename T>
303void ZoneChunkList<T>::push_back(const T& item) {
304  if (back_ == nullptr) {
305    front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall));
306    back_ = front_;
307  }
308
309  DCHECK_LE(back_->position_, back_->capacity_);
310  if (back_->position_ == back_->capacity_) {
311    if (back_->next_ == nullptr) {
312      Chunk* chunk = NewChunk(Min(back_->capacity_ << 1, kMaxChunkCapacity));
313      back_->next_ = chunk;
314      chunk->previous_ = back_;
315    }
316    back_ = back_->next_;
317  }
318  back_->items()[back_->position_] = item;
319  ++back_->position_;
320  ++size_;
321}
322
323template <typename T>
324void 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
332template <typename T>
333void 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
348template <typename T>
349typename 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
360template <typename T>
361void 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
382template <typename T>
383ForwardZoneChunkListIterator<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
389template <typename T>
390ForwardZoneChunkListIterator<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
397template <typename T>
398void ZoneChunkList<T>::CopyTo(T* ptr) {
399  for (Chunk* current = front_; current != nullptr; current = current->next_) {
400    void* start = current->items();
401    void* end = current->items() + current->position_;
402    size_t bytes = static_cast<size_t>(reinterpret_cast<uintptr_t>(end) -
403                                       reinterpret_cast<uintptr_t>(start));
404
405    MemCopy(ptr, current->items(), bytes);
406    ptr += current->position_;
407  }
408}
409
410template <typename T>
411ForwardZoneChunkListIterator<T> ZoneChunkList<T>::begin() {
412  return ForwardZoneChunkListIterator<T>::Begin(this);
413}
414
415template <typename T>
416ForwardZoneChunkListIterator<T> ZoneChunkList<T>::end() {
417  return ForwardZoneChunkListIterator<T>::End(this);
418}
419
420template <typename T>
421ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rbegin() {
422  return ReverseZoneChunkListIterator<T>::Begin(this);
423}
424
425template <typename T>
426ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rend() {
427  return ReverseZoneChunkListIterator<T>::End(this);
428}
429
430template <typename T>
431ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::begin() const {
432  return ForwardZoneChunkListIterator<const T>::Begin(this);
433}
434
435template <typename T>
436ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::end() const {
437  return ForwardZoneChunkListIterator<const T>::End(this);
438}
439
440template <typename T>
441ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rbegin() const {
442  return ReverseZoneChunkListIterator<const T>::Begin(this);
443}
444
445template <typename T>
446ReverseZoneChunkListIterator<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_
454