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/zone/zone.h"
9 
10 #ifndef V8_SRC_ZONE_ZONE_CHUNK_LIST_H_
11 #define V8_SRC_ZONE_ZONE_CHUNK_LIST_H_
12 
13 namespace v8 {
14 namespace internal {
15 
16 template <typename T>
17 class ZoneChunkListIterator;
18 template <typename T>
19 class ForwardZoneChunkListIterator;
20 template <typename T>
21 class ReverseZoneChunkListIterator;
22 
23 // A zone-backed hybrid of a vector and a linked list. Use it if you need a
24 // collection that
25 // * needs to grow indefinitely,
26 // * will mostly grow at the back, but may sometimes grow in front as well
27 // (preferrably in batches),
28 // * needs to have very low overhead,
29 // * offers forward- and backwards-iteration,
30 // * offers relatively fast seeking,
31 // * offers bidirectional iterators,
32 // * can be rewound without freeing the backing store.
33 // This list will maintain a doubly-linked list of chunks. When a chunk is
34 // filled up, a new one gets appended. New chunks appended at the end will
35 // grow in size up to a certain limit to avoid over-allocation and to keep
36 // the zone clean.
37 template <typename T>
38 class ZoneChunkList : public ZoneObject {
39  public:
40   enum class StartMode {
41     // The list will not allocate a starting chunk. Use if you expect your
42     // list to remain empty in many cases.
43     kEmpty = 0,
44     // The list will start with a small initial chunk. Subsequent chunks will
45     // get bigger over time.
46     kSmall = 8,
47     // The list will start with one chunk at maximum size. Use this if you
48     // expect your list to contain many items to avoid growing chunks.
49     kBig = 256
50   };
51 
52   explicit ZoneChunkList(Zone* zone, StartMode start_mode = StartMode::kEmpty)
zone_(zone)53       : zone_(zone) {
54     if (start_mode != StartMode::kEmpty) {
55       front_ = NewChunk(static_cast<uint32_t>(start_mode));
56       back_ = front_;
57     }
58   }
59 
60   size_t size() const;
61 
62   T& front() const;
63   T& back() const;
64 
65   void push_back(const T& item);
66   void pop_back();
67 
68   // Will push a separate chunk to the front of the chunk-list.
69   // Very memory-inefficient. Do only use sparsely! If you have many items to
70   // add in front, consider using 'push_front_many'.
71   void push_front(const T& item);
72   // TODO(heimbuef): Add 'push_front_many'.
73 
74   // Cuts the last list elements so at most 'limit' many remain. Does not
75   // free the actual memory, since it is zone allocated.
76   void Rewind(const size_t limit = 0);
77 
78   // Quickly scans the list to retrieve the element at the given index. Will
79   // *not* check bounds.
80   ForwardZoneChunkListIterator<T> Find(const size_t index);
81   ForwardZoneChunkListIterator<const T> Find(const size_t index) const;
82   // TODO(heimbuef): Add 'rFind', seeking from the end and returning a
83   // reverse iterator.
84 
85   void CopyTo(T* ptr);
86 
87   ForwardZoneChunkListIterator<T> begin();
88   ForwardZoneChunkListIterator<T> end();
89   ReverseZoneChunkListIterator<T> rbegin();
90   ReverseZoneChunkListIterator<T> rend();
91   ForwardZoneChunkListIterator<const T> begin() const;
92   ForwardZoneChunkListIterator<const T> end() const;
93   ReverseZoneChunkListIterator<const T> rbegin() const;
94   ReverseZoneChunkListIterator<const T> rend() const;
95 
96  private:
97   friend class ZoneChunkListIterator<T>;
98   friend class ForwardZoneChunkListIterator<T>;
99   friend class ReverseZoneChunkListIterator<T>;
100   static const uint32_t kMaxChunkCapacity = 256u;
101 
102   STATIC_ASSERT(kMaxChunkCapacity == static_cast<uint32_t>(StartMode::kBig));
103 
104   struct Chunk {
105     uint32_t capacity_ = 0;
106     uint32_t position_ = 0;
107     Chunk* next_ = nullptr;
108     Chunk* previous_ = nullptr;
itemsChunk109     T* items() { return reinterpret_cast<T*>(this + 1); }
110   };
111 
NewChunk(const uint32_t capacity)112   Chunk* NewChunk(const uint32_t capacity) {
113     Chunk* chunk =
114         new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk();
115     chunk->capacity_ = capacity;
116     return chunk;
117   }
118 
119   struct SeekResult {
120     Chunk* chunk_;
121     uint32_t chunk_index_;
122   };
123 
124   // Returns the chunk and relative index of the element at the given global
125   // index. Will skip entire chunks and is therefore faster than iterating.
126   SeekResult SeekIndex(size_t index) const;
127 
128   Zone* zone_;
129 
130   size_t size_ = 0;
131   Chunk* front_ = nullptr;
132   Chunk* back_ = nullptr;
133 
134   DISALLOW_COPY_AND_ASSIGN(ZoneChunkList);
135 };
136 
137 template <typename T>
138 class ZoneChunkListIterator {
139  public:
140   T& operator*() { return current_->items()[position_]; }
141   bool operator==(const ZoneChunkListIterator& other) {
142     return other.current_ == current_ && other.position_ == position_;
143   }
144   bool operator!=(const ZoneChunkListIterator& other) {
145     return !operator==(other);
146   }
147 
148  protected:
ZoneChunkListIterator(typename ZoneChunkList<T>::Chunk * current,size_t position)149   ZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current,
150                         size_t position)
151       : current_(current), position_(position) {}
152 
MoveNext()153   void MoveNext() {
154     ++position_;
155     if (position_ >= current_->capacity_) {
156       current_ = current_->next_;
157       position_ = 0;
158     }
159   }
160 
MoveRNext()161   void MoveRNext() {
162     if (position_ == 0) {
163       current_ = current_->previous_;
164       position_ = current_ ? current_->capacity_ - 1 : 0;
165     } else {
166       --position_;
167     }
168   }
169 
170   typename ZoneChunkList<T>::Chunk* current_;
171   size_t position_;
172 };
173 
174 template <typename T>
175 class ForwardZoneChunkListIterator : public ZoneChunkListIterator<T> {
176   using ZoneChunkListIterator<T>::current_;
177   using ZoneChunkListIterator<T>::position_;
178   using ZoneChunkListIterator<T>::MoveNext;
179   using ZoneChunkListIterator<T>::MoveRNext;
180 
181  public:
ForwardZoneChunkListIterator(typename ZoneChunkList<T>::Chunk * current,size_t position)182   ForwardZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current,
183                                size_t position)
184       : ZoneChunkListIterator<T>(current, position) {}
185 
186   ForwardZoneChunkListIterator& operator++() {
187     MoveNext();
188     return *this;
189   }
190 
191   ForwardZoneChunkListIterator operator++(int) {
192     ForwardZoneChunkListIterator<T> clone(*this);
193     MoveNext();
194     return clone;
195   }
196 
197   ForwardZoneChunkListIterator& operator--() {
198     MoveRNext();
199     return *this;
200   }
201 
202   ForwardZoneChunkListIterator operator--(int) {
203     ForwardZoneChunkListIterator<T> clone(*this);
204     MoveRNext();
205     return clone;
206   }
207 
208  private:
209   friend class ZoneChunkList<T>;
Begin(ZoneChunkList<T> * list)210   static ForwardZoneChunkListIterator<T> Begin(ZoneChunkList<T>* list) {
211     return ForwardZoneChunkListIterator<T>(list->front_, 0);
212   }
End(ZoneChunkList<T> * list)213   static ForwardZoneChunkListIterator<T> End(ZoneChunkList<T>* list) {
214     if (list->back_ == nullptr) return Begin(list);
215 
216     DCHECK_LE(list->back_->position_, list->back_->capacity_);
217     if (list->back_->position_ == list->back_->capacity_) {
218       return ForwardZoneChunkListIterator<T>(nullptr, 0);
219     }
220 
221     return ForwardZoneChunkListIterator<T>(list->back_, list->back_->position_);
222   }
223 };
224 
225 template <typename T>
226 class ReverseZoneChunkListIterator : public ZoneChunkListIterator<T> {
227   using ZoneChunkListIterator<T>::current_;
228   using ZoneChunkListIterator<T>::position_;
229   using ZoneChunkListIterator<T>::MoveNext;
230   using ZoneChunkListIterator<T>::MoveRNext;
231 
232  public:
ReverseZoneChunkListIterator(typename ZoneChunkList<T>::Chunk * current,size_t position)233   ReverseZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current,
234                                size_t position)
235       : ZoneChunkListIterator<T>(current, position) {}
236 
237   ReverseZoneChunkListIterator& operator++() {
238     MoveRNext();
239     return *this;
240   }
241 
242   ReverseZoneChunkListIterator operator++(int) {
243     ReverseZoneChunkListIterator<T> clone(*this);
244     MoveRNext();
245     return clone;
246   }
247 
248   ReverseZoneChunkListIterator& operator--() {
249     MoveNext();
250     return *this;
251   }
252 
253   ReverseZoneChunkListIterator operator--(int) {
254     ForwardZoneChunkListIterator<T> clone(*this);
255     MoveNext();
256     return clone;
257   }
258 
259  private:
260   friend class ZoneChunkList<T>;
Begin(ZoneChunkList<T> * list)261   static ReverseZoneChunkListIterator<T> Begin(ZoneChunkList<T>* list) {
262     if (list->back_ == nullptr) return End(list);
263     if (list->back_->position_ == 0) {
264       if (list->back_->previous_ != nullptr) {
265         return ReverseZoneChunkListIterator<T>(
266             list->back_->previous_, list->back_->previous_->capacity_ - 1);
267       } else {
268         return End(list);
269       }
270     }
271     return ReverseZoneChunkListIterator<T>(list->back_,
272                                            list->back_->position_ - 1);
273   }
End(ZoneChunkList<T> * list)274   static ReverseZoneChunkListIterator<T> End(ZoneChunkList<T>* list) {
275     return ReverseZoneChunkListIterator<T>(nullptr, 0);
276   }
277 };
278 
279 template <typename T>
size()280 size_t ZoneChunkList<T>::size() const {
281   return size_;
282 }
283 
284 template <typename T>
front()285 T& ZoneChunkList<T>::front() const {
286   DCHECK_LT(size_t(0), size());
287   return front_->items()[0];
288 }
289 
290 template <typename T>
back()291 T& ZoneChunkList<T>::back() const {
292   DCHECK_LT(size_t(0), size());
293 
294   if (back_->position_ == 0) {
295     return back_->previous_->items()[back_->previous_->position_ - 1];
296   } else {
297     return back_->items()[back_->position_ - 1];
298   }
299 }
300 
301 template <typename T>
push_back(const T & item)302 void ZoneChunkList<T>::push_back(const T& item) {
303   if (back_ == nullptr) {
304     front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall));
305     back_ = front_;
306   }
307 
308   DCHECK_LE(back_->position_, back_->capacity_);
309   if (back_->position_ == back_->capacity_) {
310     if (back_->next_ == nullptr) {
311       Chunk* chunk = NewChunk(Min(back_->capacity_ << 1, kMaxChunkCapacity));
312       back_->next_ = chunk;
313       chunk->previous_ = back_;
314     }
315     back_ = back_->next_;
316   }
317   back_->items()[back_->position_] = item;
318   ++back_->position_;
319   ++size_;
320 }
321 
322 template <typename T>
pop_back()323 void ZoneChunkList<T>::pop_back() {
324   DCHECK_LT(size_t(0), size());
325   if (back_->position_ == 0) {
326     back_ = back_->previous_;
327   }
328   --back_->position_;
329 }
330 
331 template <typename T>
push_front(const T & item)332 void ZoneChunkList<T>::push_front(const T& item) {
333   Chunk* chunk = NewChunk(1);  // Yes, this gets really inefficient.
334   chunk->next_ = front_;
335   if (front_) {
336     front_->previous_ = chunk;
337   } else {
338     back_ = chunk;
339   }
340   front_ = chunk;
341 
342   chunk->items()[0] = item;
343   chunk->position_ = 1;
344   ++size_;
345 }
346 
347 template <typename T>
SeekIndex(size_t index)348 typename ZoneChunkList<T>::SeekResult ZoneChunkList<T>::SeekIndex(
349     size_t index) const {
350   DCHECK_LT(index, size());
351   Chunk* current = front_;
352   while (index > current->capacity_) {
353     index -= current->capacity_;
354     current = current->next_;
355   }
356   return {current, static_cast<uint32_t>(index)};
357 }
358 
359 template <typename T>
Rewind(const size_t limit)360 void ZoneChunkList<T>::Rewind(const size_t limit) {
361   if (limit >= size()) return;
362 
363   SeekResult seek_result = SeekIndex(limit);
364   DCHECK_NOT_NULL(seek_result.chunk_);
365 
366   // Do a partial rewind of the chunk containing the index.
367   seek_result.chunk_->position_ = seek_result.chunk_index_;
368 
369   // Set back_ so iterators will work correctly.
370   back_ = seek_result.chunk_;
371 
372   // Do full rewind of all subsequent chunks.
373   for (Chunk* current = seek_result.chunk_->next_; current != nullptr;
374        current = current->next_) {
375     current->position_ = 0;
376   }
377 
378   size_ = limit;
379 }
380 
381 template <typename T>
Find(const size_t index)382 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::Find(const size_t index) {
383   SeekResult seek_result = SeekIndex(index);
384   return ForwardZoneChunkListIterator<T>(seek_result.chunk_,
385                                          seek_result.chunk_index_);
386 }
387 
388 template <typename T>
Find(const size_t index)389 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::Find(
390     const size_t index) const {
391   SeekResult seek_result = SeekIndex(index);
392   return ForwardZoneChunkListIterator<const T>(seek_result.chunk_,
393                                                seek_result.chunk_index_);
394 }
395 
396 template <typename T>
CopyTo(T * ptr)397 void ZoneChunkList<T>::CopyTo(T* ptr) {
398   for (Chunk* current = front_; current != nullptr; current = current->next_) {
399     void* start = current->items();
400     void* end = current->items() + current->position_;
401     size_t bytes = static_cast<size_t>(reinterpret_cast<uintptr_t>(end) -
402                                        reinterpret_cast<uintptr_t>(start));
403 
404     MemCopy(ptr, current->items(), bytes);
405     ptr += current->position_;
406   }
407 }
408 
409 template <typename T>
begin()410 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::begin() {
411   return ForwardZoneChunkListIterator<T>::Begin(this);
412 }
413 
414 template <typename T>
end()415 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::end() {
416   return ForwardZoneChunkListIterator<T>::End(this);
417 }
418 
419 template <typename T>
rbegin()420 ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rbegin() {
421   return ReverseZoneChunkListIterator<T>::Begin(this);
422 }
423 
424 template <typename T>
rend()425 ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rend() {
426   return ReverseZoneChunkListIterator<T>::End(this);
427 }
428 
429 template <typename T>
begin()430 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::begin() const {
431   return ForwardZoneChunkListIterator<const T>::Begin(this);
432 }
433 
434 template <typename T>
end()435 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::end() const {
436   return ForwardZoneChunkListIterator<const T>::End(this);
437 }
438 
439 template <typename T>
rbegin()440 ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rbegin() const {
441   return ReverseZoneChunkListIterator<const T>::Begin(this);
442 }
443 
444 template <typename T>
rend()445 ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rend() const {
446   return ReverseZoneChunkListIterator<const T>::End(this);
447 }
448 
449 }  // namespace internal
450 }  // namespace v8
451 
452 #endif  // V8_SRC_ZONE_ZONE_CHUNK_LIST_H_
453