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