Line data Source code
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)
54 1191477 : : 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 3331102 : Chunk* NewChunk(const uint32_t capacity) {
114 : Chunk* chunk =
115 3331102 : new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk();
116 3331103 : chunk->capacity_ = capacity;
117 3331103 : 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:
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 :
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:
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 :
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:
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 :
280 : template <typename T>
281 : size_t ZoneChunkList<T>::size() const {
282 : return size_;
283 : }
284 :
285 : template <typename T>
286 : T& ZoneChunkList<T>::front() const {
287 : DCHECK_LT(size_t(0), size());
288 : return front_->items()[0];
289 : }
290 :
291 : template <typename T>
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>
303 287162386 : void ZoneChunkList<T>::push_back(const T& item) {
304 283831284 : if (back_ == nullptr) {
305 670891 : front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall));
306 670891 : back_ = front_;
307 : }
308 :
309 : DCHECK_LE(back_->position_, back_->capacity_);
310 283831284 : if (back_->position_ == back_->capacity_) {
311 2660211 : if (back_->next_ == nullptr) {
312 5320422 : Chunk* chunk = NewChunk(Min(back_->capacity_ << 1, kMaxChunkCapacity));
313 2660212 : back_->next_ = chunk;
314 2660212 : chunk->previous_ = back_;
315 : }
316 2660212 : back_ = back_->next_;
317 : }
318 283831285 : back_->items()[back_->position_] = item;
319 283831285 : ++back_->position_;
320 283831285 : ++size_;
321 283831285 : }
322 :
323 : template <typename T>
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>
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>
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>
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>
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>
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>
398 670855 : void ZoneChunkList<T>::CopyTo(T* ptr) {
399 4001756 : for (Chunk* current = front_; current != nullptr; current = current->next_) {
400 3330901 : void* start = current->items();
401 3330901 : void* end = current->items() + current->position_;
402 : size_t bytes = static_cast<size_t>(reinterpret_cast<uintptr_t>(end) -
403 3330901 : reinterpret_cast<uintptr_t>(start));
404 :
405 : MemCopy(ptr, current->items(), bytes);
406 3330901 : ptr += current->position_;
407 : }
408 670855 : }
409 :
410 : template <typename T>
411 : ForwardZoneChunkListIterator<T> ZoneChunkList<T>::begin() {
412 : return ForwardZoneChunkListIterator<T>::Begin(this);
413 : }
414 :
415 : template <typename T>
416 : ForwardZoneChunkListIterator<T> ZoneChunkList<T>::end() {
417 : return ForwardZoneChunkListIterator<T>::End(this);
418 : }
419 :
420 : template <typename T>
421 : ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rbegin() {
422 : return ReverseZoneChunkListIterator<T>::Begin(this);
423 : }
424 :
425 : template <typename T>
426 : ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rend() {
427 : return ReverseZoneChunkListIterator<T>::End(this);
428 : }
429 :
430 : template <typename T>
431 : ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::begin() const {
432 : return ForwardZoneChunkListIterator<const T>::Begin(this);
433 : }
434 :
435 : template <typename T>
436 : ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::end() const {
437 : return ForwardZoneChunkListIterator<const T>::End(this);
438 : }
439 :
440 : template <typename T>
441 : ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rbegin() const {
442 : return ReverseZoneChunkListIterator<const T>::Begin(this);
443 : }
444 :
445 : template <typename T>
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_
|
