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
14 namespace v8 {
15 namespace internal {
16
17 template <typename T>
18 class ZoneChunkListIterator;
19 template <typename T>
20 class ForwardZoneChunkListIterator;
21 template <typename T>
22 class 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.
38 template <typename T>
39 class 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)
zone_(zone)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;
itemsChunk110 T* items() { return reinterpret_cast<T*>(this + 1); }
111 };
112
NewChunk(const uint32_t capacity)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
138 template <typename T>
139 class 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:
ZoneChunkListIterator(typename ZoneChunkList<T>::Chunk * current,size_t position)150 ZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current,
151 size_t position)
152 : current_(current), position_(position) {}
153
MoveNext()154 void MoveNext() {
155 ++position_;
156 if (position_ >= current_->capacity_) {
157 current_ = current_->next_;
158 position_ = 0;
159 }
160 }
161
MoveRNext()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
175 template <typename T>
176 class 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:
ForwardZoneChunkListIterator(typename ZoneChunkList<T>::Chunk * current,size_t position)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>;
Begin(ZoneChunkList<T> * list)211 static ForwardZoneChunkListIterator<T> Begin(ZoneChunkList<T>* list) {
212 return ForwardZoneChunkListIterator<T>(list->front_, 0);
213 }
End(ZoneChunkList<T> * list)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
226 template <typename T>
227 class 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:
ReverseZoneChunkListIterator(typename ZoneChunkList<T>::Chunk * current,size_t position)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>;
Begin(ZoneChunkList<T> * list)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 }
End(ZoneChunkList<T> * list)275 static ReverseZoneChunkListIterator<T> End(ZoneChunkList<T>* list) {
276 return ReverseZoneChunkListIterator<T>(nullptr, 0);
277 }
278 };
279
280 template <typename T>
size()281 size_t ZoneChunkList<T>::size() const {
282 return size_;
283 }
284
285 template <typename T>
front()286 T& ZoneChunkList<T>::front() const {
287 DCHECK_LT(size_t(0), size());
288 return front_->items()[0];
289 }
290
291 template <typename T>
back()292 T& 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
302 template <typename T>
push_back(const T & item)303 void 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
323 template <typename T>
pop_back()324 void 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
332 template <typename T>
push_front(const T & item)333 void 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
348 template <typename T>
SeekIndex(size_t index)349 typename 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
360 template <typename T>
Rewind(const size_t limit)361 void 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
382 template <typename T>
Find(const size_t index)383 ForwardZoneChunkListIterator<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
389 template <typename T>
Find(const size_t index)390 ForwardZoneChunkListIterator<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
397 template <typename T>
CopyTo(T * ptr)398 void 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
410 template <typename T>
begin()411 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::begin() {
412 return ForwardZoneChunkListIterator<T>::Begin(this);
413 }
414
415 template <typename T>
end()416 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::end() {
417 return ForwardZoneChunkListIterator<T>::End(this);
418 }
419
420 template <typename T>
rbegin()421 ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rbegin() {
422 return ReverseZoneChunkListIterator<T>::Begin(this);
423 }
424
425 template <typename T>
rend()426 ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rend() {
427 return ReverseZoneChunkListIterator<T>::End(this);
428 }
429
430 template <typename T>
begin()431 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::begin() const {
432 return ForwardZoneChunkListIterator<const T>::Begin(this);
433 }
434
435 template <typename T>
end()436 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::end() const {
437 return ForwardZoneChunkListIterator<const T>::End(this);
438 }
439
440 template <typename T>
rbegin()441 ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rbegin() const {
442 return ReverseZoneChunkListIterator<const T>::Begin(this);
443 }
444
445 template <typename T>
rend()446 ReverseZoneChunkListIterator<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