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/base/iterator.h"
8 : #include "src/globals.h"
9 : #include "src/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)
56 15258414 : : zone_(zone) {
57 : if (start_mode != StartMode::kEmpty) {
58 5991421 : front_ = NewChunk(static_cast<uint32_t>(start_mode));
59 5991252 : back_ = front_;
60 : }
61 : }
62 :
63 : size_t size() const { return size_; }
64 636033 : 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 13908078 : iterator begin() { return iterator::Begin(this); }
92 : iterator end() { return iterator::End(this); }
93 1 : reverse_iterator rbegin() { return reverse_iterator::Begin(this); }
94 : reverse_iterator rend() { return reverse_iterator::End(this); }
95 1 : 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 10267430 : Chunk* NewChunk(const uint32_t capacity) {
122 : Chunk* chunk =
123 10267430 : new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk();
124 10267542 : chunk->capacity_ = capacity;
125 10267542 : 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 26525672 : maybe_const<T>& operator*() const { return current_->items()[position_]; }
159 7533737 : maybe_const<T>* operator->() const { return ¤t_->items()[position_]; }
160 3 : bool operator==(const ZoneChunkListIterator& other) const {
161 49932761 : 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 2 : position_ += amount;
200 17 : while (position_ > 0 && position_ >= current_->capacity_) {
201 14 : auto overshoot = position_ - current_->capacity_;
202 14 : current_ = current_->next_;
203 14 : 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 1 : static ZoneChunkListIterator Begin(ChunkList* list) {
217 : // Forward iterator:
218 : if (!backwards) return ZoneChunkListIterator(list->front_, 0);
219 :
220 : // Backward iterator:
221 1 : if (list->back_ == nullptr) return End(list);
222 1 : if (list->back_->position_ == 0) {
223 0 : if (list->back_->previous_ != nullptr) {
224 : return ZoneChunkListIterator(list->back_->previous_,
225 0 : list->back_->previous_->capacity_ - 1);
226 : } else {
227 : return End(list);
228 : }
229 : }
230 1 : return ZoneChunkListIterator(list->back_, list->back_->position_ - 1);
231 : }
232 :
233 4 : static ZoneChunkListIterator End(ChunkList* list) {
234 : // Backward iterator:
235 : if (backwards) return ZoneChunkListIterator(nullptr, 0);
236 :
237 : // Forward iterator:
238 24683908 : if (list->back_ == nullptr) return Begin(list);
239 :
240 : DCHECK_LE(list->back_->position_, list->back_->capacity_);
241 21289878 : if (list->back_->position_ == list->back_->capacity_) {
242 391843 : return ZoneChunkListIterator(list->back_->next_, 0);
243 : }
244 :
245 20898035 : 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 1024 : if (position_ == 0) {
258 9 : current_ = current_->previous_;
259 9 : position_ = current_ ? current_->capacity_ - 1 : 0;
260 : } else {
261 1015 : --position_;
262 : }
263 : } else {
264 : // Move forwards.
265 31260557 : ++position_;
266 31260557 : if (position_ >= current_->capacity_) {
267 596790 : current_ = current_->next_;
268 6 : 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 5991325 : if (back_->position_ == 0) {
288 0 : return back_->previous_->items()[back_->previous_->position_ - 1];
289 : } else {
290 5991325 : return back_->items()[back_->position_ - 1];
291 : }
292 : }
293 :
294 : template <typename T>
295 145763686 : void ZoneChunkList<T>::push_back(const T& item) {
296 141488520 : if (back_ == nullptr) {
297 2583485 : front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall));
298 2583520 : back_ = front_;
299 : }
300 :
301 : DCHECK_LE(back_->position_, back_->capacity_);
302 141488555 : if (back_->position_ == back_->capacity_) {
303 1691684 : if (back_->next_ == nullptr) {
304 3383362 : Chunk* chunk = NewChunk(Min(back_->capacity_ << 1, kMaxChunkCapacity));
305 1691661 : back_->next_ = chunk;
306 1691661 : chunk->previous_ = back_;
307 : }
308 1691664 : back_ = back_->next_;
309 : }
310 141488535 : back_->items()[back_->position_] = item;
311 141488535 : ++back_->position_;
312 141488535 : ++size_;
313 : DCHECK_LE(back_->position_, back_->capacity_);
314 141488535 : }
315 :
316 : template <typename T>
317 : void ZoneChunkList<T>::pop_back() {
318 : DCHECK_LT(size_t(0), size());
319 1 : if (back_->position_ == 0) {
320 0 : back_ = back_->previous_;
321 : }
322 1 : --back_->position_;
323 1 : --size_;
324 : }
325 :
326 : template <typename T>
327 1024 : void ZoneChunkList<T>::push_front(const T& item) {
328 1024 : Chunk* chunk = NewChunk(1); // Yes, this gets really inefficient.
329 1024 : chunk->next_ = front_;
330 1024 : if (front_) {
331 1023 : front_->previous_ = chunk;
332 : } else {
333 1 : back_ = chunk;
334 : }
335 1024 : front_ = chunk;
336 :
337 1024 : chunk->items()[0] = item;
338 1024 : chunk->position_ = 1;
339 1024 : ++size_;
340 1024 : }
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 33702420 : while (index >= current->capacity_) {
348 27826999 : index -= current->capacity_;
349 27826999 : current = current->next_;
350 : }
351 : DCHECK_LT(index, current->capacity_);
352 280130 : return {current, static_cast<uint32_t>(index)};
353 : }
354 :
355 : template <typename T>
356 560291 : void ZoneChunkList<T>::Rewind(const size_t limit) {
357 560322 : 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 280130 : seek_result.chunk_->position_ = seek_result.chunk_index_;
364 :
365 : // Set back_ so iterators will work correctly.
366 280130 : back_ = seek_result.chunk_;
367 :
368 : // Do full rewind of all subsequent chunks.
369 285862 : for (Chunk* current = seek_result.chunk_->next_; current != nullptr;
370 : current = current->next_) {
371 5732 : current->position_ = 0;
372 : }
373 :
374 280130 : size_ = limit;
375 : }
376 :
377 : template <typename T>
378 4959674 : 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 5595291 : 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 455988 : void ZoneChunkList<T>::CopyTo(T* ptr) {
394 2313192 : for (Chunk* current = front_; current != nullptr; current = current->next_) {
395 1857204 : void* start = current->items();
396 1857204 : void* end = current->items() + current->position_;
397 : size_t bytes = static_cast<size_t>(reinterpret_cast<uintptr_t>(end) -
398 1857204 : reinterpret_cast<uintptr_t>(start));
399 :
400 : MemCopy(ptr, current->items(), bytes);
401 1857204 : ptr += current->position_;
402 : }
403 455988 : }
404 :
405 : } // namespace internal
406 : } // namespace v8
407 :
408 : #endif // V8_ZONE_ZONE_CHUNK_LIST_H_
|
