Line data Source code
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 413603266 : void ZoneList<T>::Add(const T& element, Zone* zone) {
19 412619405 : if (length_ < capacity_) {
20 410382058 : data_[length_++] = element;
21 : } else {
22 : ZoneList<T>::ResizeAdd(element, ZoneAllocationPolicy(zone));
23 : }
24 412619413 : }
25 :
26 : template <typename T>
27 0 : void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) {
28 806 : AddAll(other.ToVector(), zone);
29 : }
30 :
31 : template <typename T>
32 16302352 : void ZoneList<T>::AddAll(const Vector<T>& other, Zone* zone) {
33 32604704 : int result_length = length_ + other.length();
34 16302352 : if (capacity_ < result_length)
35 240 : Resize(result_length, ZoneAllocationPolicy(zone));
36 : if (std::is_fundamental<T>()) {
37 : memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
38 : } else {
39 164385235 : for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
40 : }
41 16302352 : length_ = result_length;
42 16302352 : }
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 2237347 : ResizeAddInternal(element, alloc);
49 : }
50 :
51 : template <typename T>
52 2237350 : 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 2237350 : 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 2237350 : T temp = element;
61 2237350 : Resize(new_capacity, alloc);
62 2237355 : data_[length_++] = temp;
63 2237355 : }
64 :
65 : template <typename T>
66 2237585 : void ZoneList<T>::Resize(int new_capacity, ZoneAllocationPolicy alloc) {
67 : DCHECK_LE(length_, new_capacity);
68 : T* new_data = NewData(new_capacity, alloc);
69 2237596 : MemCopy(new_data, data_, length_ * sizeof(T));
70 : ZoneList<T>::DeleteData(data_);
71 2237596 : data_ = new_data;
72 2237596 : capacity_ = new_capacity;
73 2237596 : }
74 :
75 : template <typename T>
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>
83 : void ZoneList<T>::Set(int index, const T& elm) {
84 : DCHECK(index >= 0 && index <= length_);
85 2581442 : data_[index] = elm;
86 : }
87 :
88 : template <typename T>
89 961 : void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) {
90 : DCHECK(index >= 0 && index <= length_);
91 961 : Add(elm, zone);
92 2856 : for (int i = length_ - 1; i > index; --i) {
93 1895 : data_[i] = data_[i - 1];
94 : }
95 961 : data_[index] = elm;
96 961 : }
97 :
98 : template <typename T>
99 14385 : T ZoneList<T>::Remove(int i) {
100 14385 : T element = at(i);
101 14385 : length_--;
102 28825 : while (i < length_) {
103 55 : data_[i] = data_[i + 1];
104 55 : i++;
105 : }
106 14385 : return element;
107 : }
108 :
109 : template <typename T>
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 2498605 : data_ = nullptr;
115 2498605 : capacity_ = 0;
116 2498605 : length_ = 0;
117 : }
118 :
119 : template <typename T>
120 : void ZoneList<T>::Rewind(int pos) {
121 : DCHECK(0 <= pos && pos <= length_);
122 26812 : length_ = pos;
123 : }
124 :
125 : template <typename T>
126 : template <class 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>
132 : bool ZoneList<T>::Contains(const T& elm) const {
133 67492268 : for (int i = 0; i < length_; i++) {
134 67817028 : if (data_[i] == elm) return true;
135 : }
136 : return false;
137 : }
138 :
139 : template <typename T>
140 : template <typename CompareFunction>
141 55 : void ZoneList<T>::Sort(CompareFunction cmp) {
142 110 : 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>
152 8627 : void ZoneList<T>::StableSort(CompareFunction cmp, size_t s, size_t l) {
153 8627 : 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_
|
