1 // Copyright 2017 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_INL_H_
6 #define V8_ZONE_ZONE_LIST_INL_H_
7
8 #include "src/zone/zone.h"
9
10 #include "src/base/macros.h"
11 #include "src/base/platform/platform.h"
12 #include "src/utils.h"
13
14 namespace v8 {
15 namespace internal {
16
17 template <typename T>
Add(const T & element,Zone * zone)18 void ZoneList<T>::Add(const T& element, Zone* zone) {
19 if (length_ < capacity_) {
20 data_[length_++] = element;
21 } else {
22 ZoneList<T>::ResizeAdd(element, ZoneAllocationPolicy(zone));
23 }
24 }
25
26 template <typename T>
AddAll(const ZoneList<T> & other,Zone * zone)27 void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) {
28 AddAll(other.ToVector(), zone);
29 }
30
31 template <typename T>
AddAll(const Vector<T> & other,Zone * zone)32 void ZoneList<T>::AddAll(const Vector<T>& other, Zone* zone) {
33 int result_length = length_ + other.length();
34 if (capacity_ < result_length)
35 Resize(result_length, ZoneAllocationPolicy(zone));
36 if (std::is_fundamental<T>()) {
37 memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
38 } else {
39 for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
40 }
41 length_ = result_length;
42 }
43
44 // Use two layers of inlining so that the non-inlined function can
45 // use the same implementation as the inlined version.
46 template <typename T>
ResizeAdd(const T & element,ZoneAllocationPolicy alloc)47 void ZoneList<T>::ResizeAdd(const T& element, ZoneAllocationPolicy alloc) {
48 ResizeAddInternal(element, alloc);
49 }
50
51 template <typename T>
ResizeAddInternal(const T & element,ZoneAllocationPolicy alloc)52 void ZoneList<T>::ResizeAddInternal(const T& element,
53 ZoneAllocationPolicy alloc) {
54 DCHECK(length_ >= capacity_);
55 // Grow the list capacity by 100%, but make sure to let it grow
56 // even when the capacity is zero (possible initial case).
57 int new_capacity = 1 + 2 * capacity_;
58 // Since the element reference could be an element of the list, copy
59 // it out of the old backing storage before resizing.
60 T temp = element;
61 Resize(new_capacity, alloc);
62 data_[length_++] = temp;
63 }
64
65 template <typename T>
Resize(int new_capacity,ZoneAllocationPolicy alloc)66 void ZoneList<T>::Resize(int new_capacity, ZoneAllocationPolicy alloc) {
67 DCHECK_LE(length_, new_capacity);
68 T* new_data = NewData(new_capacity, alloc);
69 MemCopy(new_data, data_, length_ * sizeof(T));
70 ZoneList<T>::DeleteData(data_);
71 data_ = new_data;
72 capacity_ = new_capacity;
73 }
74
75 template <typename T>
AddBlock(T value,int count,Zone * zone)76 Vector<T> ZoneList<T>::AddBlock(T value, int count, Zone* zone) {
77 int start = length_;
78 for (int i = 0; i < count; i++) Add(value, zone);
79 return Vector<T>(&data_[start], count);
80 }
81
82 template <typename T>
Set(int index,const T & elm)83 void ZoneList<T>::Set(int index, const T& elm) {
84 DCHECK(index >= 0 && index <= length_);
85 data_[index] = elm;
86 }
87
88 template <typename T>
InsertAt(int index,const T & elm,Zone * zone)89 void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) {
90 DCHECK(index >= 0 && index <= length_);
91 Add(elm, zone);
92 for (int i = length_ - 1; i > index; --i) {
93 data_[i] = data_[i - 1];
94 }
95 data_[index] = elm;
96 }
97
98 template <typename T>
Remove(int i)99 T ZoneList<T>::Remove(int i) {
100 T element = at(i);
101 length_--;
102 while (i < length_) {
103 data_[i] = data_[i + 1];
104 i++;
105 }
106 return element;
107 }
108
109 template <typename T>
Clear()110 void ZoneList<T>::Clear() {
111 DeleteData(data_);
112 // We don't call Initialize(0) since that requires passing a Zone,
113 // which we don't really need.
114 data_ = nullptr;
115 capacity_ = 0;
116 length_ = 0;
117 }
118
119 template <typename T>
Rewind(int pos)120 void ZoneList<T>::Rewind(int pos) {
121 DCHECK(0 <= pos && pos <= length_);
122 length_ = pos;
123 }
124
125 template <typename T>
126 template <class Visitor>
Iterate(Visitor * visitor)127 void ZoneList<T>::Iterate(Visitor* visitor) {
128 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
129 }
130
131 template <typename T>
Contains(const T & elm)132 bool ZoneList<T>::Contains(const T& elm) const {
133 for (int i = 0; i < length_; i++) {
134 if (data_[i] == elm) return true;
135 }
136 return false;
137 }
138
139 template <typename T>
140 template <typename CompareFunction>
Sort(CompareFunction cmp)141 void ZoneList<T>::Sort(CompareFunction cmp) {
142 ToVector().Sort(cmp, 0, length_);
143 #ifdef DEBUG
144 for (int i = 1; i < length_; i++) {
145 DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
146 }
147 #endif
148 }
149
150 template <typename T>
151 template <typename CompareFunction>
StableSort(CompareFunction cmp,size_t s,size_t l)152 void ZoneList<T>::StableSort(CompareFunction cmp, size_t s, size_t l) {
153 ToVector().StableSort(cmp, s, l);
154 #ifdef DEBUG
155 for (size_t i = s + 1; i < l; i++) {
156 DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
157 }
158 #endif
159 }
160
161 } // namespace internal
162 } // namespace v8
163
164 #endif // V8_ZONE_ZONE_LIST_INL_H_
165