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/base/macros.h"
9 #include "src/base/platform/platform.h"
10 #include "src/utils/memcopy.h"
11 #include "src/zone/zone-list.h"
12
13 namespace v8 {
14 namespace internal {
15
16 template <typename T>
Add(const T & element,Zone * zone)17 void ZoneList<T>::Add(const T& element, Zone* zone) {
18 if (length_ < capacity_) {
19 data_[length_++] = element;
20 } else {
21 ZoneList<T>::ResizeAdd(element, zone);
22 }
23 }
24
25 template <typename T>
AddAll(const ZoneList<T> & other,Zone * zone)26 void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) {
27 AddAll(other.ToVector(), zone);
28 }
29
30 template <typename T>
AddAll(const Vector<const T> & other,Zone * zone)31 void ZoneList<T>::AddAll(const Vector<const T>& other, Zone* zone) {
32 int length = other.length();
33 if (length == 0) return;
34
35 int result_length = length_ + length;
36 if (capacity_ < result_length) Resize(result_length, zone);
37 if (std::is_trivially_copyable<T>::value) {
38 memcpy(&data_[length_], other.begin(), sizeof(T) * length);
39 } else {
40 std::copy(other.begin(), other.end(), &data_[length_]);
41 }
42 length_ = result_length;
43 }
44
45 // Use two layers of inlining so that the non-inlined function can
46 // use the same implementation as the inlined version.
47 template <typename T>
ResizeAdd(const T & element,Zone * zone)48 void ZoneList<T>::ResizeAdd(const T& element, Zone* zone) {
49 ResizeAddInternal(element, zone);
50 }
51
52 template <typename T>
ResizeAddInternal(const T & element,Zone * zone)53 void ZoneList<T>::ResizeAddInternal(const T& element, Zone* zone) {
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, zone);
62 data_[length_++] = temp;
63 }
64
65 template <typename T>
Resize(int new_capacity,Zone * zone)66 void ZoneList<T>::Resize(int new_capacity, Zone* zone) {
67 DCHECK_LE(length_, new_capacity);
68 T* new_data = zone->NewArray<T>(new_capacity);
69 if (length_ > 0) {
70 if (std::is_trivially_copyable<T>::value) {
71 MemCopy(new_data, data_, length_ * sizeof(T));
72 } else {
73 std::copy(&data_[0], &data_[length_], &new_data[0]);
74 }
75 }
76 if (data_) zone->DeleteArray<T>(data_, capacity_);
77 data_ = new_data;
78 capacity_ = new_capacity;
79 }
80
81 template <typename T>
AddBlock(T value,int count,Zone * zone)82 Vector<T> ZoneList<T>::AddBlock(T value, int count, Zone* zone) {
83 int start = length_;
84 for (int i = 0; i < count; i++) Add(value, zone);
85 return Vector<T>(&data_[start], count);
86 }
87
88 template <typename T>
Set(int index,const T & elm)89 void ZoneList<T>::Set(int index, const T& elm) {
90 DCHECK(index >= 0 && index <= length_);
91 data_[index] = elm;
92 }
93
94 template <typename T>
InsertAt(int index,const T & elm,Zone * zone)95 void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) {
96 DCHECK(index >= 0 && index <= length_);
97 Add(elm, zone);
98 for (int i = length_ - 1; i > index; --i) {
99 data_[i] = data_[i - 1];
100 }
101 data_[index] = elm;
102 }
103
104 template <typename T>
Remove(int i)105 T ZoneList<T>::Remove(int i) {
106 T element = at(i);
107 length_--;
108 while (i < length_) {
109 data_[i] = data_[i + 1];
110 i++;
111 }
112 return element;
113 }
114
115 template <typename T>
Clear(Zone * zone)116 void ZoneList<T>::Clear(Zone* zone) {
117 if (data_) zone->DeleteArray<T>(data_, capacity_);
118 DropAndClear();
119 }
120
121 template <typename T>
Rewind(int pos)122 void ZoneList<T>::Rewind(int pos) {
123 DCHECK(0 <= pos && pos <= length_);
124 length_ = pos;
125 }
126
127 template <typename T>
128 template <class Visitor>
Iterate(Visitor * visitor)129 void ZoneList<T>::Iterate(Visitor* visitor) {
130 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
131 }
132
133 template <typename T>
134 template <typename CompareFunction>
Sort(CompareFunction cmp)135 void ZoneList<T>::Sort(CompareFunction cmp) {
136 std::sort(begin(), end(),
137 [cmp](const T& a, const T& b) { return cmp(&a, &b) < 0; });
138 #ifdef DEBUG
139 for (int i = 1; i < length_; i++) {
140 DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
141 }
142 #endif
143 }
144
145 template <typename T>
146 template <typename CompareFunction>
StableSort(CompareFunction cmp,size_t s,size_t l)147 void ZoneList<T>::StableSort(CompareFunction cmp, size_t s, size_t l) {
148 std::stable_sort(begin() + s, begin() + s + l,
149 [cmp](const T& a, const T& b) { return cmp(&a, &b) < 0; });
150 #ifdef DEBUG
151 for (size_t i = s + 1; i < l; i++) {
152 DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0);
153 }
154 #endif
155 }
156
157 } // namespace internal
158 } // namespace v8
159
160 #endif // V8_ZONE_ZONE_LIST_INL_H_
161