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