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_ZONE_ZONE_LIST_H_ 6 #define V8_ZONE_ZONE_LIST_H_ 7 8 #include "src/base/logging.h" 9 #include "src/zone/zone.h" 10 11 namespace v8 { 12 13 namespace base { 14 template <typename T> 15 class Vector; 16 } // namespace base 17 18 namespace internal { 19 20 // ZoneLists are growable lists with constant-time access to the elements. 21 // The list itself and all its elements are supposed to be allocated in zone 22 // memory. Unlike ZoneVector container, the ZoneList instance has minimal 23 // possible size which makes it a good candidate for embedding into other 24 // often-allocated zone objects. 25 // 26 // Note, ZoneLists' elements cannot be deleted individually and the destructor 27 // intentionally does not free the backing store. Because of the latter, the 28 // ZoneList must not be used outsize of zone memory. Consider using ZoneVector 29 // or other containers instead. 30 template <typename T> 31 class ZoneList final : public ZoneObject { 32 public: 33 // Construct a new ZoneList with the given capacity; the length is 34 // always zero. The capacity must be non-negative. ZoneList(int capacity,Zone * zone)35 ZoneList(int capacity, Zone* zone) : capacity_(capacity) { 36 DCHECK_GE(capacity, 0); 37 data_ = (capacity_ > 0) ? zone->NewArray<T>(capacity_) : nullptr; 38 } 39 40 // Construct a new ZoneList by copying the elements of the given ZoneList. ZoneList(const ZoneList<T> & other,Zone * zone)41 ZoneList(const ZoneList<T>& other, Zone* zone) 42 : ZoneList(other.length(), zone) { 43 AddAll(other, zone); 44 } 45 46 // Construct a new ZoneList by copying the elements of the given vector. ZoneList(const base::Vector<const T> & other,Zone * zone)47 ZoneList(const base::Vector<const T>& other, Zone* zone) 48 : ZoneList(other.length(), zone) { 49 AddAll(other, zone); 50 } 51 ZoneList(ZoneList<T> && other)52 ZoneList(ZoneList<T>&& other) V8_NOEXCEPT { *this = std::move(other); } 53 54 ZoneList(const ZoneList&) = delete; 55 ZoneList& operator=(const ZoneList&) = delete; 56 57 // The ZoneList objects are usually allocated as a fields in other 58 // zone-allocated objects for which destructors are not called anyway, so 59 // we are not going to clear the memory here as well. 60 ~ZoneList() = default; 61 62 ZoneList& operator=(ZoneList&& other) V8_NOEXCEPT { 63 // We don't have a Zone object, so we'll have to drop the data_ array. 64 // If this assert ever fails, consider calling Clear(Zone*) or 65 // DropAndClear() before the move assignment to make it explicit what's 66 // happenning with the lvalue. 67 DCHECK_NULL(data_); 68 data_ = other.data_; 69 capacity_ = other.capacity_; 70 length_ = other.length_; 71 other.DropAndClear(); 72 return *this; 73 } 74 75 // Returns a reference to the element at index i. This reference is not safe 76 // to use after operations that can change the list's backing store 77 // (e.g. Add). 78 inline T& operator[](int i) const { 79 DCHECK_LE(0, i); 80 DCHECK_GT(static_cast<unsigned>(length_), static_cast<unsigned>(i)); 81 return data_[i]; 82 } at(int i)83 inline T& at(int i) const { return operator[](i); } last()84 inline T& last() const { return at(length_ - 1); } first()85 inline T& first() const { return at(0); } 86 87 using iterator = T*; begin()88 inline iterator begin() { return &data_[0]; } end()89 inline iterator end() { return &data_[length_]; } 90 91 using const_iterator = const T*; begin()92 inline const_iterator begin() const { return &data_[0]; } end()93 inline const_iterator end() const { return &data_[length_]; } 94 is_empty()95 V8_INLINE bool is_empty() const { return length_ == 0; } length()96 V8_INLINE int length() const { return length_; } capacity()97 V8_INLINE int capacity() const { return capacity_; } 98 ToVector()99 base::Vector<T> ToVector() const { return base::Vector<T>(data_, length_); } ToVector(int start,int length)100 base::Vector<T> ToVector(int start, int length) const { 101 DCHECK_LE(start, length_); 102 return base::Vector<T>(&data_[start], std::min(length_ - start, length)); 103 } 104 ToConstVector()105 base::Vector<const T> ToConstVector() const { 106 return base::Vector<const T>(data_, length_); 107 } 108 109 // Adds a copy of the given 'element' to the end of the list, 110 // expanding the list if necessary. 111 void Add(const T& element, Zone* zone); 112 // Add all the elements from the argument list to this list. 113 void AddAll(const ZoneList<T>& other, Zone* zone); 114 // Add all the elements from the vector to this list. 115 void AddAll(const base::Vector<const T>& other, Zone* zone); 116 // Inserts the element at the specific index. 117 void InsertAt(int index, const T& element, Zone* zone); 118 119 // Added 'count' elements with the value 'value' and returns a 120 // vector that allows access to the elements. The vector is valid 121 // until the next change is made to this list. 122 base::Vector<T> AddBlock(T value, int count, Zone* zone); 123 124 // Overwrites the element at the specific index. 125 void Set(int index, const T& element); 126 127 // Removes the i'th element without deleting it even if T is a 128 // pointer type; moves all elements above i "down". Returns the 129 // removed element. This function's complexity is linear in the 130 // size of the list. 131 T Remove(int i); 132 133 // Removes the last element without deleting it even if T is a 134 // pointer type. Returns the removed element. RemoveLast()135 V8_INLINE T RemoveLast() { return Remove(length_ - 1); } 136 137 // Clears the list by freeing the storage memory. If you want to keep the 138 // memory, use Rewind(0) instead. Be aware, that even if T is a 139 // pointer type, clearing the list doesn't delete the entries. 140 V8_INLINE void Clear(Zone* zone); 141 142 // Clears the list but unlike Clear(), it doesn't free the storage memory. 143 // It's useful when the whole zone containing the backing store will be 144 // released but the list will be used further. DropAndClear()145 V8_INLINE void DropAndClear() { 146 data_ = nullptr; 147 capacity_ = 0; 148 length_ = 0; 149 } 150 151 // Drops all but the first 'pos' elements from the list. 152 V8_INLINE void Rewind(int pos); 153 Contains(const T & elm)154 inline bool Contains(const T& elm) const { 155 for (int i = 0; i < length_; i++) { 156 if (data_[i] == elm) return true; 157 } 158 return false; 159 } 160 161 // Iterate through all list entries, starting at index 0. 162 template <class Visitor> 163 void Iterate(Visitor* visitor); 164 165 // Sort all list entries (using QuickSort) 166 template <typename CompareFunction> 167 void Sort(CompareFunction cmp); 168 template <typename CompareFunction> 169 void StableSort(CompareFunction cmp, size_t start, size_t length); 170 171 private: 172 T* data_ = nullptr; 173 int capacity_ = 0; 174 int length_ = 0; 175 176 // Increase the capacity of a full list, and add an element. 177 // List must be full already. 178 void ResizeAdd(const T& element, Zone* zone); 179 180 // Inlined implementation of ResizeAdd, shared by inlined and 181 // non-inlined versions of ResizeAdd. 182 void ResizeAddInternal(const T& element, Zone* zone); 183 184 // Resize the list. 185 void Resize(int new_capacity, Zone* zone); 186 }; 187 188 } // namespace internal 189 } // namespace v8 190 191 #endif // V8_ZONE_ZONE_LIST_H_ 192