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 <algorithm>
6
7 #include "src/base/iterator.h"
8 #include "src/common/globals.h"
9 #include "src/utils/memcopy.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>
19 class ZoneChunkListIterator;
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:
38 using iterator = ZoneChunkListIterator<T, false, true>;
39 using const_iterator = ZoneChunkListIterator<T, false, false>;
40 using reverse_iterator = ZoneChunkListIterator<T, true, true>;
41 using const_reverse_iterator = ZoneChunkListIterator<T, true, false>;
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)
zone_(zone)56 : zone_(zone) {
57 if (start_mode != StartMode::kEmpty) {
58 front_ = NewChunk(static_cast<uint32_t>(start_mode));
59 back_ = front_;
60 }
61 }
62
size()63 size_t size() const { return size_; }
is_empty()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
begin()91 iterator begin() { return iterator::Begin(this); }
end()92 iterator end() { return iterator::End(this); }
rbegin()93 reverse_iterator rbegin() { return reverse_iterator::Begin(this); }
rend()94 reverse_iterator rend() { return reverse_iterator::End(this); }
begin()95 const_iterator begin() const { return const_iterator::Begin(this); }
end()96 const_iterator end() const { return const_iterator::End(this); }
rbegin()97 const_reverse_iterator rbegin() const {
98 return const_reverse_iterator::Begin(this);
99 }
rend()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;
itemsChunk117 T* items() { return reinterpret_cast<T*>(this + 1); }
itemsChunk118 const T* items() const { return reinterpret_cast<const T*>(this + 1); }
119 };
120
NewChunk(const uint32_t capacity)121 Chunk* NewChunk(const uint32_t capacity) {
122 void* memory = zone_->Allocate<Chunk>(sizeof(Chunk) + capacity * sizeof(T));
123 Chunk* chunk = new (memory) 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>
147 class ZoneChunkListIterator
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 ¤t_->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
Advance(int amount)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
Begin(ChunkList * list)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
End(ChunkList * list)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
ZoneChunkListIterator(Chunk * current,size_t position)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>
Move()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>
front()278 T& ZoneChunkList<T>::front() const {
279 DCHECK_LT(size_t(0), size());
280 return front_->items()[0];
281 }
282
283 template <typename T>
back()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>
push_back(const T & item)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 constexpr auto max_capacity = kMaxChunkCapacity;
305 Chunk* chunk = NewChunk(std::min(back_->capacity_ << 1, max_capacity));
306 back_->next_ = chunk;
307 chunk->previous_ = back_;
308 }
309 back_ = back_->next_;
310 }
311 back_->items()[back_->position_] = item;
312 ++back_->position_;
313 ++size_;
314 DCHECK_LE(back_->position_, back_->capacity_);
315 }
316
317 template <typename T>
pop_back()318 void ZoneChunkList<T>::pop_back() {
319 DCHECK_LT(size_t(0), size());
320 if (back_->position_ == 0) {
321 back_ = back_->previous_;
322 }
323 --back_->position_;
324 --size_;
325 }
326
327 template <typename T>
push_front(const T & item)328 void ZoneChunkList<T>::push_front(const T& item) {
329 Chunk* chunk = NewChunk(1); // Yes, this gets really inefficient.
330 chunk->next_ = front_;
331 if (front_) {
332 front_->previous_ = chunk;
333 } else {
334 back_ = chunk;
335 }
336 front_ = chunk;
337
338 chunk->items()[0] = item;
339 chunk->position_ = 1;
340 ++size_;
341 }
342
343 template <typename T>
SeekIndex(size_t index)344 typename ZoneChunkList<T>::SeekResult ZoneChunkList<T>::SeekIndex(
345 size_t index) const {
346 DCHECK_LT(index, size());
347 Chunk* current = front_;
348 while (index >= current->capacity_) {
349 index -= current->capacity_;
350 current = current->next_;
351 }
352 DCHECK_LT(index, current->capacity_);
353 return {current, static_cast<uint32_t>(index)};
354 }
355
356 template <typename T>
Rewind(const size_t limit)357 void ZoneChunkList<T>::Rewind(const size_t limit) {
358 if (limit >= size()) return;
359
360 SeekResult seek_result = SeekIndex(limit);
361 DCHECK_NOT_NULL(seek_result.chunk_);
362
363 // Do a partial rewind of the chunk containing the index.
364 seek_result.chunk_->position_ = seek_result.chunk_index_;
365
366 // Set back_ so iterators will work correctly.
367 back_ = seek_result.chunk_;
368
369 // Do full rewind of all subsequent chunks.
370 for (Chunk* current = seek_result.chunk_->next_; current != nullptr;
371 current = current->next_) {
372 current->position_ = 0;
373 }
374
375 size_ = limit;
376 }
377
378 template <typename T>
Find(const size_t index)379 typename ZoneChunkList<T>::iterator ZoneChunkList<T>::Find(const size_t index) {
380 SeekResult seek_result = SeekIndex(index);
381 return typename ZoneChunkList<T>::iterator(seek_result.chunk_,
382 seek_result.chunk_index_);
383 }
384
385 template <typename T>
Find(const size_t index)386 typename ZoneChunkList<T>::const_iterator ZoneChunkList<T>::Find(
387 const size_t index) const {
388 SeekResult seek_result = SeekIndex(index);
389 return typename ZoneChunkList<T>::const_iterator(seek_result.chunk_,
390 seek_result.chunk_index_);
391 }
392
393 template <typename T>
CopyTo(T * ptr)394 void ZoneChunkList<T>::CopyTo(T* ptr) {
395 for (Chunk* current = front_; current != nullptr; current = current->next_) {
396 void* start = current->items();
397 void* end = current->items() + current->position_;
398 size_t bytes = static_cast<size_t>(reinterpret_cast<uintptr_t>(end) -
399 reinterpret_cast<uintptr_t>(start));
400
401 MemCopy(ptr, current->items(), bytes);
402 ptr += current->position_;
403 }
404 }
405
406 } // namespace internal
407 } // namespace v8
408
409 #endif // V8_ZONE_ZONE_CHUNK_LIST_H_
410