1 // Copyright 2020 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 #ifndef V8_UTILS_SCOPED_LIST_H_ 6 #define V8_UTILS_SCOPED_LIST_H_ 7 8 #include <type_traits> 9 #include <vector> 10 11 #include "src/base/logging.h" 12 13 namespace v8 { 14 namespace internal { 15 16 template <typename T> 17 class Vector; 18 19 template <typename T> 20 class ZoneList; 21 22 // ScopedList is a scope-lifetime list with a std::vector backing that can be 23 // re-used between ScopedLists. Note that a ScopedList in an outer scope cannot 24 // add any entries if there is a ScopedList with the same backing in an inner 25 // scope. 26 template <typename T, typename TBacking = T> 27 class ScopedList final { 28 // The backing can either be the same type as the list type, or, for pointers, 29 // we additionally allow a void* backing store. 30 static_assert((std::is_same<TBacking, T>::value) || 31 (std::is_same<TBacking, void*>::value && 32 std::is_pointer<T>::value), 33 "Incompatible combination of T and TBacking types"); 34 35 public: ScopedList(std::vector<TBacking> * buffer)36 explicit ScopedList(std::vector<TBacking>* buffer) 37 : buffer_(*buffer), start_(buffer->size()), end_(buffer->size()) {} 38 ~ScopedList()39 ~ScopedList() { Rewind(); } 40 Rewind()41 void Rewind() { 42 DCHECK_EQ(buffer_.size(), end_); 43 buffer_.resize(start_); 44 end_ = start_; 45 } 46 MergeInto(ScopedList * parent)47 void MergeInto(ScopedList* parent) { 48 DCHECK_EQ(parent->end_, start_); 49 parent->end_ = end_; 50 start_ = end_; 51 DCHECK_EQ(0, length()); 52 } 53 length()54 int length() const { return static_cast<int>(end_ - start_); } 55 at(int i)56 const T& at(int i) const { 57 size_t index = start_ + i; 58 DCHECK_LE(start_, index); 59 DCHECK_LT(index, buffer_.size()); 60 return *reinterpret_cast<T*>(&buffer_[index]); 61 } 62 at(int i)63 T& at(int i) { 64 size_t index = start_ + i; 65 DCHECK_LE(start_, index); 66 DCHECK_LT(index, buffer_.size()); 67 return *reinterpret_cast<T*>(&buffer_[index]); 68 } 69 ToConstVector()70 Vector<const T> ToConstVector() const { 71 T* data = reinterpret_cast<T*>(buffer_.data() + start_); 72 return Vector<const T>(data, length()); 73 } 74 Add(const T & value)75 void Add(const T& value) { 76 DCHECK_EQ(buffer_.size(), end_); 77 buffer_.push_back(value); 78 ++end_; 79 } 80 AddAll(const Vector<const T> & list)81 void AddAll(const Vector<const T>& list) { 82 DCHECK_EQ(buffer_.size(), end_); 83 buffer_.reserve(buffer_.size() + list.length()); 84 for (int i = 0; i < list.length(); i++) { 85 buffer_.push_back(list.at(i)); 86 } 87 end_ += list.length(); 88 } 89 90 using iterator = T*; 91 using const_iterator = const T*; 92 begin()93 inline iterator begin() { 94 return reinterpret_cast<T*>(buffer_.data() + start_); 95 } begin()96 inline const_iterator begin() const { 97 return reinterpret_cast<T*>(buffer_.data() + start_); 98 } 99 end()100 inline iterator end() { return reinterpret_cast<T*>(buffer_.data() + end_); } end()101 inline const_iterator end() const { 102 return reinterpret_cast<T*>(buffer_.data() + end_); 103 } 104 105 private: 106 std::vector<TBacking>& buffer_; 107 size_t start_; 108 size_t end_; 109 }; 110 111 template <typename T> 112 using ScopedPtrList = ScopedList<T*, void*>; 113 114 } // namespace internal 115 } // namespace v8 116 117 #endif // V8_UTILS_SCOPED_LIST_H_ 118