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/utils.h"
13 :
14 : namespace v8 {
15 : namespace internal {
16 :
17 : template <typename T>
18 989388422 : void ZoneList<T>::Add(const T& element, Zone* zone) {
19 977225259 : if (length_ < capacity_) {
20 962659328 : data_[length_++] = element;
21 : } else {
22 : ZoneList<T>::ResizeAdd(element, ZoneAllocationPolicy(zone));
23 : }
24 977225235 : }
25 :
26 : template <typename T>
27 : void ZoneList<T>::AddAll(const ZoneList<T>& other, Zone* zone) {
28 24721 : AddAll(other.ToVector(), zone);
29 : }
30 :
31 : template <typename T>
32 24721 : void ZoneList<T>::AddAll(const Vector<T>& other, Zone* zone) {
33 49442 : int result_length = length_ + other.length();
34 24721 : if (capacity_ < result_length)
35 92 : Resize(result_length, ZoneAllocationPolicy(zone));
36 : if (std::is_fundamental<T>()) {
37 : memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
38 : } else {
39 75802 : for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
40 : }
41 24721 : length_ = result_length;
42 24721 : }
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 14565931 : ResizeAddInternal(element, alloc);
49 : }
50 :
51 : template <typename T>
52 14565914 : 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 14565914 : 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 14565914 : T temp = element;
61 14565914 : Resize(new_capacity, alloc);
62 14565990 : data_[length_++] = temp;
63 14565990 : }
64 :
65 : template <typename T>
66 14566003 : void ZoneList<T>::Resize(int new_capacity, ZoneAllocationPolicy alloc) {
67 : DCHECK_LE(length_, new_capacity);
68 : T* new_data = NewData(new_capacity, alloc);
69 14566069 : MemCopy(new_data, data_, length_ * sizeof(T));
70 : ZoneList<T>::DeleteData(data_);
71 14566069 : data_ = new_data;
72 14566069 : capacity_ = new_capacity;
73 14566069 : }
74 :
75 : template <typename T>
76 : Vector<T> ZoneList<T>::AddBlock(T value, int count, Zone* zone) {
77 : int start = length_;
78 14717147 : 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 2332616 : data_[index] = elm;
86 : }
87 :
88 : template <typename T>
89 2068 : void ZoneList<T>::InsertAt(int index, const T& elm, Zone* zone) {
90 : DCHECK(index >= 0 && index <= length_);
91 2068 : Add(elm, zone);
92 4994 : for (int i = length_ - 1; i > index; --i) {
93 2926 : data_[i] = data_[i - 1];
94 : }
95 2068 : data_[index] = elm;
96 2068 : }
97 :
98 : template <typename T>
99 74888488 : T ZoneList<T>::Remove(int i) {
100 74888488 : T element = at(i);
101 74888488 : length_--;
102 149777042 : while (i < length_) {
103 66 : data_[i] = data_[i + 1];
104 66 : i++;
105 : }
106 74888488 : 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 21543685 : data_ = nullptr;
115 21543685 : capacity_ = 0;
116 21543685 : length_ = 0;
117 : }
118 :
119 : template <typename T>
120 : void ZoneList<T>::Rewind(int pos) {
121 : DCHECK(0 <= pos && pos <= length_);
122 656436447 : 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 81474087 : for (int i = 0; i < length_; i++) {
134 81902686 : if (data_[i] == elm) return true;
135 : }
136 : return false;
137 : }
138 :
139 : template <typename T>
140 : template <typename CompareFunction>
141 66 : void ZoneList<T>::Sort(CompareFunction cmp) {
142 132 : 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 9695 : void ZoneList<T>::StableSort(CompareFunction cmp, size_t s, size_t l) {
153 9695 : 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_
|
