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 412435654 : void ZoneList<T>::Add(const T& element, Zone* zone) {
19 412435654 : if (length_ < capacity_) {
20 410266127 : data_[length_++] = element;
21 : } else {
22 0 : ZoneList<T>::ResizeAdd(element, ZoneAllocationPolicy(zone));
23 : }
24 412435657 : }
25 :
26 : template <typename T>
27 : void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) {
28 806 : AddAll(other.ToVector(), zone);
29 : }
30 :
31 : template <typename T>
32 16208247 : void ZoneList<T>::AddAll(const Vector<T>& other, Zone* zone) {
33 32416494 : int result_length = length_ + other.length();
34 16208247 : 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 112863065 : for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
40 : }
41 16208247 : length_ = result_length;
42 16208247 : }
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 0 : void ZoneList<T>::ResizeAdd(const T& element, ZoneAllocationPolicy alloc) {
48 2169527 : ResizeAddInternal(element, alloc);
49 0 : }
50 :
51 : template <typename T>
52 2169528 : 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 2169528 : 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 2169528 : T temp = element;
61 2169528 : Resize(new_capacity, alloc);
62 2169530 : data_[length_++] = temp;
63 2169530 : }
64 :
65 : template <typename T>
66 2169767 : void ZoneList<T>::Resize(int new_capacity, ZoneAllocationPolicy alloc) {
67 : DCHECK_LE(length_, new_capacity);
68 : T* new_data = NewData(new_capacity, alloc);
69 2169768 : if (length_ > 0) {
70 2040215 : MemCopy(new_data, data_, length_ * sizeof(T));
71 : }
72 : ZoneList<T>::DeleteData(data_);
73 2169768 : data_ = new_data;
74 2169768 : capacity_ = new_capacity;
75 2169768 : }
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 2606021 : data_[index] = elm;
88 : }
89 :
90 : template <typename T>
91 961 : void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) {
92 : DCHECK(index >= 0 && index <= length_);
93 961 : Add(elm, zone);
94 2856 : for (int i = length_ - 1; i > index; --i) {
95 1895 : data_[i] = data_[i - 1];
96 : }
97 961 : data_[index] = elm;
98 961 : }
99 :
100 : template <typename T>
101 14373 : T ZoneList<T>::Remove(int i) {
102 14373 : T element = at(i);
103 14373 : length_--;
104 14433 : while (i < length_) {
105 30 : data_[i] = data_[i + 1];
106 30 : i++;
107 : }
108 14373 : 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 2616676 : data_ = nullptr;
117 2616676 : capacity_ = 0;
118 2616676 : length_ = 0;
119 : }
120 :
121 : template <typename T>
122 : void ZoneList<T>::Rewind(int pos) {
123 : DCHECK(0 <= pos && pos <= length_);
124 26889 : 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 55 : 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_
|
