V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
zone-chunk-list.h
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/base/iterator.h"
8 #include "src/globals.h"
9 #include "src/utils.h"
10 #include "src/zone/zone.h"
11 
12 #ifndef V8_ZONE_ZONE_CHUNK_LIST_H_
13 #define V8_ZONE_ZONE_CHUNK_LIST_H_
14 
15 namespace v8 {
16 namespace internal {
17 
18 template <typename T, bool backwards, bool modifiable>
20 
21 // A zone-backed hybrid of a vector and a linked list. Use it if you need a
22 // collection that
23 // * needs to grow indefinitely,
24 // * will mostly grow at the back, but may sometimes grow in front as well
25 // (preferably in batches),
26 // * needs to have very low overhead,
27 // * offers forward- and backwards-iteration,
28 // * offers relatively fast seeking,
29 // * offers bidirectional iterators,
30 // * can be rewound without freeing the backing store.
31 // This list will maintain a doubly-linked list of chunks. When a chunk is
32 // filled up, a new one gets appended. New chunks appended at the end will
33 // grow in size up to a certain limit to avoid over-allocation and to keep
34 // the zone clean.
35 template <typename T>
36 class ZoneChunkList : public ZoneObject {
37  public:
42 
43  enum class StartMode {
44  // The list will not allocate a starting chunk. Use if you expect your
45  // list to remain empty in many cases.
46  kEmpty = 0,
47  // The list will start with a small initial chunk. Subsequent chunks will
48  // get bigger over time.
49  kSmall = 8,
50  // The list will start with one chunk at maximum size. Use this if you
51  // expect your list to contain many items to avoid growing chunks.
52  kBig = 256
53  };
54 
55  explicit ZoneChunkList(Zone* zone, StartMode start_mode = StartMode::kEmpty)
56  : zone_(zone) {
57  if (start_mode != StartMode::kEmpty) {
58  front_ = NewChunk(static_cast<uint32_t>(start_mode));
59  back_ = front_;
60  }
61  }
62 
63  size_t size() const { return size_; }
64  bool is_empty() const { return size() == 0; }
65 
66  T& front() const;
67  T& back() const;
68 
69  void push_back(const T& item);
70  void pop_back();
71 
72  // Will push a separate chunk to the front of the chunk-list.
73  // Very memory-inefficient. Do only use sparsely! If you have many items to
74  // add in front, consider using 'push_front_many'.
75  void push_front(const T& item);
76  // TODO(heimbuef): Add 'push_front_many'.
77 
78  // Cuts the last list elements so at most 'limit' many remain. Does not
79  // free the actual memory, since it is zone allocated.
80  void Rewind(const size_t limit = 0);
81 
82  // Quickly scans the list to retrieve the element at the given index. Will
83  // *not* check bounds.
84  iterator Find(const size_t index);
85  const_iterator Find(const size_t index) const;
86  // TODO(heimbuef): Add 'rFind', seeking from the end and returning a
87  // reverse iterator.
88 
89  void CopyTo(T* ptr);
90 
91  iterator begin() { return iterator::Begin(this); }
92  iterator end() { return iterator::End(this); }
93  reverse_iterator rbegin() { return reverse_iterator::Begin(this); }
94  reverse_iterator rend() { return reverse_iterator::End(this); }
95  const_iterator begin() const { return const_iterator::Begin(this); }
96  const_iterator end() const { return const_iterator::End(this); }
97  const_reverse_iterator rbegin() const {
98  return const_reverse_iterator::Begin(this);
99  }
100  const_reverse_iterator rend() const {
101  return const_reverse_iterator::End(this);
102  }
103 
104  private:
105  template <typename S, bool backwards, bool modifiable>
106  friend class ZoneChunkListIterator;
107 
108  static constexpr uint32_t kMaxChunkCapacity = 256u;
109 
110  STATIC_ASSERT(kMaxChunkCapacity == static_cast<uint32_t>(StartMode::kBig));
111 
112  struct Chunk {
113  uint32_t capacity_ = 0;
114  uint32_t position_ = 0;
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); }
119  };
120 
121  Chunk* NewChunk(const uint32_t capacity) {
122  Chunk* chunk =
123  new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk();
124  chunk->capacity_ = capacity;
125  return chunk;
126  }
127 
128  struct SeekResult {
129  Chunk* chunk_;
130  uint32_t chunk_index_;
131  };
132 
133  // Returns the chunk and relative index of the element at the given global
134  // index. Will skip entire chunks and is therefore faster than iterating.
135  SeekResult SeekIndex(size_t index) const;
136 
137  Zone* zone_;
138 
139  size_t size_ = 0;
140  Chunk* front_ = nullptr;
141  Chunk* back_ = nullptr;
142 
143  DISALLOW_COPY_AND_ASSIGN(ZoneChunkList);
144 };
145 
146 template <typename T, bool backwards, bool modifiable>
148  : public base::iterator<std::bidirectional_iterator_tag, T> {
149  private:
150  template <typename S>
151  using maybe_const =
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>>;
156 
157  public:
158  maybe_const<T>& operator*() const { return current_->items()[position_]; }
159  maybe_const<T>* operator->() const { return &current_->items()[position_]; }
160  bool operator==(const ZoneChunkListIterator& other) const {
161  return other.current_ == current_ && other.position_ == position_;
162  }
163  bool operator!=(const ZoneChunkListIterator& other) const {
164  return !operator==(other);
165  }
166 
167  ZoneChunkListIterator& operator++() {
168  Move<backwards>();
169  return *this;
170  }
171 
172  ZoneChunkListIterator operator++(int) {
173  ZoneChunkListIterator clone(*this);
174  Move<backwards>();
175  return clone;
176  }
177 
178  ZoneChunkListIterator& operator--() {
179  Move<!backwards>();
180  return *this;
181  }
182 
183  ZoneChunkListIterator operator--(int) {
184  ZoneChunkListIterator clone(*this);
185  Move<!backwards>();
186  return clone;
187  }
188 
189  void Advance(int amount) {
190  // Move forwards.
191  DCHECK_GE(amount, 0);
192 #if DEBUG
193  ZoneChunkListIterator clone(*this);
194  for (int i = 0; i < amount; ++i) {
195  ++clone;
196  }
197 #endif
198 
199  position_ += amount;
200  while (position_ > 0 && position_ >= current_->capacity_) {
201  auto overshoot = position_ - current_->capacity_;
202  current_ = current_->next_;
203  position_ = overshoot;
204 
205  DCHECK(position_ == 0 || current_);
206  }
207 
208 #if DEBUG
209  DCHECK_EQ(clone, *this);
210 #endif
211  }
212 
213  private:
214  friend class ZoneChunkList<T>;
215 
216  static ZoneChunkListIterator Begin(ChunkList* list) {
217  // Forward iterator:
218  if (!backwards) return ZoneChunkListIterator(list->front_, 0);
219 
220  // Backward iterator:
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);
226  } else {
227  return End(list);
228  }
229  }
230  return ZoneChunkListIterator(list->back_, list->back_->position_ - 1);
231  }
232 
233  static ZoneChunkListIterator End(ChunkList* list) {
234  // Backward iterator:
235  if (backwards) return ZoneChunkListIterator(nullptr, 0);
236 
237  // Forward iterator:
238  if (list->back_ == nullptr) return Begin(list);
239 
240  DCHECK_LE(list->back_->position_, list->back_->capacity_);
241  if (list->back_->position_ == list->back_->capacity_) {
242  return ZoneChunkListIterator(list->back_->next_, 0);
243  }
244 
245  return ZoneChunkListIterator(list->back_, list->back_->position_);
246  }
247 
248  ZoneChunkListIterator(Chunk* current, size_t position)
249  : current_(current), position_(position) {
250  DCHECK(current == nullptr || position < current->capacity_);
251  }
252 
253  template <bool move_backward>
254  void Move() {
255  if (move_backward) {
256  // Move backwards.
257  if (position_ == 0) {
258  current_ = current_->previous_;
259  position_ = current_ ? current_->capacity_ - 1 : 0;
260  } else {
261  --position_;
262  }
263  } else {
264  // Move forwards.
265  ++position_;
266  if (position_ >= current_->capacity_) {
267  current_ = current_->next_;
268  position_ = 0;
269  }
270  }
271  }
272 
273  Chunk* current_;
274  size_t position_;
275 };
276 
277 template <typename T>
278 T& ZoneChunkList<T>::front() const {
279  DCHECK_LT(size_t(0), size());
280  return front_->items()[0];
281 }
282 
283 template <typename T>
284 T& ZoneChunkList<T>::back() const {
285  DCHECK_LT(size_t(0), size());
286 
287  if (back_->position_ == 0) {
288  return back_->previous_->items()[back_->previous_->position_ - 1];
289  } else {
290  return back_->items()[back_->position_ - 1];
291  }
292 }
293 
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));
298  back_ = front_;
299  }
300 
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_;
307  }
308  back_ = back_->next_;
309  }
310  back_->items()[back_->position_] = item;
311  ++back_->position_;
312  ++size_;
313  DCHECK_LE(back_->position_, back_->capacity_);
314 }
315 
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_;
321  }
322  --back_->position_;
323  --size_;
324 }
325 
326 template <typename T>
327 void ZoneChunkList<T>::push_front(const T& item) {
328  Chunk* chunk = NewChunk(1); // Yes, this gets really inefficient.
329  chunk->next_ = front_;
330  if (front_) {
331  front_->previous_ = chunk;
332  } else {
333  back_ = chunk;
334  }
335  front_ = chunk;
336 
337  chunk->items()[0] = item;
338  chunk->position_ = 1;
339  ++size_;
340 }
341 
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_;
350  }
351  DCHECK_LT(index, current->capacity_);
352  return {current, static_cast<uint32_t>(index)};
353 }
354 
355 template <typename T>
356 void ZoneChunkList<T>::Rewind(const size_t limit) {
357  if (limit >= size()) return;
358 
359  SeekResult seek_result = SeekIndex(limit);
360  DCHECK_NOT_NULL(seek_result.chunk_);
361 
362  // Do a partial rewind of the chunk containing the index.
363  seek_result.chunk_->position_ = seek_result.chunk_index_;
364 
365  // Set back_ so iterators will work correctly.
366  back_ = seek_result.chunk_;
367 
368  // Do full rewind of all subsequent chunks.
369  for (Chunk* current = seek_result.chunk_->next_; current != nullptr;
370  current = current->next_) {
371  current->position_ = 0;
372  }
373 
374  size_ = limit;
375 }
376 
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_);
382 }
383 
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_);
390 }
391 
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));
399 
400  MemCopy(ptr, current->items(), bytes);
401  ptr += current->position_;
402  }
403 }
404 
405 } // namespace internal
406 } // namespace v8
407 
408 #endif // V8_ZONE_ZONE_CHUNK_LIST_H_
Definition: libplatform.h:13