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/memcopy.h" |
13 | |
14 | namespace v8 { |
15 | namespace internal { |
16 | |
17 | template <typename T> |
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> |
27 | void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) { |
28 | AddAll(other.ToVector(), zone); |
29 | } |
30 | |
31 | template <typename T> |
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> |
47 | void ZoneList<T>::ResizeAdd(const T& element, ZoneAllocationPolicy alloc) { |
48 | ResizeAddInternal(element, alloc); |
49 | } |
50 | |
51 | template <typename T> |
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> |
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 | if (length_ > 0) { |
70 | MemCopy(new_data, data_, length_ * sizeof(T)); |
71 | } |
72 | ZoneList<T>::DeleteData(data_); |
73 | data_ = new_data; |
74 | capacity_ = new_capacity; |
75 | } |
76 | |
77 | template <typename T> |
78 | Vector<T> ZoneList<T>::AddBlock(T value, int count, Zone* zone) { |
79 | int start = length_; |
80 | for (int i = 0; i < count; i++) Add(value, zone); |
81 | return Vector<T>(&data_[start], count); |
82 | } |
83 | |
84 | template <typename T> |
85 | void ZoneList<T>::Set(int index, const T& elm) { |
86 | DCHECK(index >= 0 && index <= length_); |
87 | data_[index] = elm; |
88 | } |
89 | |
90 | template <typename T> |
91 | void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) { |
92 | DCHECK(index >= 0 && index <= length_); |
93 | Add(elm, zone); |
94 | for (int i = length_ - 1; i > index; --i) { |
95 | data_[i] = data_[i - 1]; |
96 | } |
97 | data_[index] = elm; |
98 | } |
99 | |
100 | template <typename T> |
101 | T ZoneList<T>::Remove(int i) { |
102 | T element = at(i); |
103 | length_--; |
104 | while (i < length_) { |
105 | data_[i] = data_[i + 1]; |
106 | i++; |
107 | } |
108 | return element; |
109 | } |
110 | |
111 | template <typename T> |
112 | void ZoneList<T>::Clear() { |
113 | DeleteData(data_); |
114 | // We don't call Initialize(0) since that requires passing a Zone, |
115 | // which we don't really need. |
116 | data_ = nullptr; |
117 | capacity_ = 0; |
118 | length_ = 0; |
119 | } |
120 | |
121 | template <typename T> |
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> |
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> |
135 | void ZoneList<T>::Sort(CompareFunction cmp) { |
136 | ToVector().Sort(cmp, 0, length_); |
137 | #ifdef DEBUG |
138 | for (int i = 1; i < length_; i++) { |
139 | DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0); |
140 | } |
141 | #endif |
142 | } |
143 | |
144 | template <typename T> |
145 | template <typename CompareFunction> |
146 | void ZoneList<T>::StableSort(CompareFunction cmp, size_t s, size_t l) { |
147 | ToVector().StableSort(cmp, s, l); |
148 | #ifdef DEBUG |
149 | for (size_t i = s + 1; i < l; i++) { |
150 | DCHECK_LE(cmp(&data_[i - 1], &data_[i]), 0); |
151 | } |
152 | #endif |
153 | } |
154 | |
155 | } // namespace internal |
156 | } // namespace v8 |
157 | |
158 | #endif // V8_ZONE_ZONE_LIST_INL_H_ |
159 | |