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 <algorithm>
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 12279314 : : zone_(zone) {
57 : if (start_mode != StartMode::kEmpty) {
58 6450044 : front_ = NewChunk(static_cast<uint32_t>(start_mode));
59 6450190 : 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 163994342 : T* items() { return reinterpret_cast<T*>(this + 1); }
118 : const T* items() const { return reinterpret_cast<const T*>(this + 1); }
119 : };
120 :
121 8315827 : Chunk* NewChunk(const uint32_t capacity) {
122 : Chunk* chunk =
123 10930034 : new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk();
124 10930368 : chunk->capacity_ = capacity;
125 8316017 : 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 29765125 : maybe_const<T>& operator*() const { return current_->items()[position_]; }
159 9125741 : maybe_const<T>* operator->() const { return ¤t_->items()[position_]; }
160 : bool operator==(const ZoneChunkListIterator& other) const {
161 54640698 : return other.current_ == current_ && other.position_ == position_;
162 : }
163 : bool operator!=(const ZoneChunkListIterator& other) const {
164 54640695 : 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 17 : while (position_ > 0 && position_ >= current_->capacity_) {
201 14 : auto overshoot = position_ - current_->capacity_;
202 14 : 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 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 : static ZoneChunkListIterator End(ChunkList* list) {
234 : // Backward iterator:
235 : if (backwards) return ZoneChunkListIterator(nullptr, 0);
236 :
237 : // Forward iterator:
238 26105637 : if (list->back_ == nullptr) return Begin(list);
239 :
240 : DCHECK_LE(list->back_->position_, list->back_->capacity_);
241 24072077 : if (list->back_->position_ == list->back_->capacity_) {
242 523238 : return ZoneChunkListIterator(list->back_->next_, 0);
243 : }
244 :
245 23548839 : 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 35477501 : ++position_;
266 35477501 : if (position_ >= current_->capacity_) {
267 760791 : 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 6450579 : if (back_->position_ == 0) {
288 0 : return back_->previous_->items()[back_->previous_->position_ - 1];
289 : } else {
290 6450579 : return back_->items()[back_->position_ - 1];
291 : }
292 : }
293 :
294 : template <typename T>
295 161329354 : void ZoneChunkList<T>::push_back(const T& item) {
296 161329354 : if (back_ == nullptr) {
297 2613327 : front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall));
298 2613327 : back_ = front_;
299 : }
300 :
301 : DCHECK_LE(back_->position_, back_->capacity_);
302 161329498 : if (back_->position_ == back_->capacity_) {
303 1865779 : if (back_->next_ == nullptr) {
304 1865777 : constexpr auto max_capacity = kMaxChunkCapacity;
305 3731554 : Chunk* chunk = NewChunk(std::min(back_->capacity_ << 1, max_capacity));
306 1865771 : back_->next_ = chunk;
307 1865771 : chunk->previous_ = back_;
308 : }
309 1865773 : back_ = back_->next_;
310 : }
311 322658984 : back_->items()[back_->position_] = item;
312 161329492 : ++back_->position_;
313 161329492 : ++size_;
314 : DCHECK_LE(back_->position_, back_->capacity_);
315 161329492 : }
316 :
317 : template <typename T>
318 : void ZoneChunkList<T>::pop_back() {
319 : DCHECK_LT(size_t(0), size());
320 1 : if (back_->position_ == 0) {
321 0 : back_ = back_->previous_;
322 : }
323 1 : --back_->position_;
324 1 : --size_;
325 : }
326 :
327 : template <typename T>
328 1024 : void ZoneChunkList<T>::push_front(const T& item) {
329 : Chunk* chunk = NewChunk(1); // Yes, this gets really inefficient.
330 1024 : chunk->next_ = front_;
331 1024 : if (front_) {
332 1023 : front_->previous_ = chunk;
333 : } else {
334 1 : back_ = chunk;
335 : }
336 1024 : front_ = chunk;
337 :
338 1024 : chunk->items()[0] = item;
339 1024 : chunk->position_ = 1;
340 1024 : ++size_;
341 1024 : }
342 :
343 : template <typename T>
344 : typename ZoneChunkList<T>::SeekResult ZoneChunkList<T>::SeekIndex(
345 : size_t index) const {
346 : DCHECK_LT(index, size());
347 : Chunk* current = front_;
348 16041101 : while (index >= current->capacity_) {
349 9189712 : index -= current->capacity_;
350 9189712 : current = current->next_;
351 : }
352 : DCHECK_LT(index, current->capacity_);
353 287053 : return {current, static_cast<uint32_t>(index)};
354 : }
355 :
356 : template <typename T>
357 : void ZoneChunkList<T>::Rewind(const size_t limit) {
358 287174 : 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 287053 : seek_result.chunk_->position_ = seek_result.chunk_index_;
365 :
366 : // Set back_ so iterators will work correctly.
367 287053 : back_ = seek_result.chunk_;
368 :
369 : // Do full rewind of all subsequent chunks.
370 291820 : for (Chunk* current = seek_result.chunk_->next_; current != nullptr;
371 : current = current->next_) {
372 4767 : current->position_ = 0;
373 : }
374 :
375 287053 : size_ = limit;
376 : }
377 :
378 : template <typename T>
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>
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>
394 463914 : void ZoneChunkList<T>::CopyTo(T* ptr) {
395 2474686 : for (Chunk* current = front_; current != nullptr; current = current->next_) {
396 : void* start = current->items();
397 2010772 : 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 2010772 : ptr += current->position_;
403 : }
404 463914 : }
405 :
406 : } // namespace internal
407 : } // namespace v8
408 :
409 : #endif // V8_ZONE_ZONE_CHUNK_LIST_H_
|
