Line data Source code
1 : // Copyright 2006-2009 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_LIST_INL_H_
6 : #define V8_LIST_INL_H_
7 :
8 : #include "src/list.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 :
18 : template<typename T, class P>
19 1704518416 : void List<T, P>::Add(const T& element, P alloc) {
20 1668102130 : if (length_ < capacity_) {
21 1610627177 : data_[length_++] = element;
22 : } else {
23 : List<T, P>::ResizeAdd(element, alloc);
24 : }
25 1668102126 : }
26 :
27 :
28 : template<typename T, class P>
29 17277847 : void List<T, P>::AddAll(const List<T, P>& other, P alloc) {
30 17570007 : AddAll(other.ToVector(), alloc);
31 : }
32 :
33 :
34 : template<typename T, class P>
35 145001919 : void List<T, P>::AddAll(const Vector<T>& other, P alloc) {
36 38736156 : int result_length = length_ + other.length();
37 19368078 : if (capacity_ < result_length) Resize(result_length, alloc);
38 : if (std::is_fundamental<T>()) {
39 3596054 : memcpy(data_ + length_, other.start(), sizeof(*data_) * other.length());
40 : } else {
41 290828227 : for (int i = 0; i < other.length(); i++) data_[length_ + i] = other.at(i);
42 : }
43 19367948 : length_ = result_length;
44 19367948 : }
45 :
46 :
47 : // Use two layers of inlining so that the non-inlined function can
48 : // use the same implementation as the inlined version.
49 : template<typename T, class P>
50 : void List<T, P>::ResizeAdd(const T& element, P alloc) {
51 57474953 : ResizeAddInternal(element, alloc);
52 : }
53 :
54 :
55 : template<typename T, class P>
56 57474948 : void List<T, P>::ResizeAddInternal(const T& element, P alloc) {
57 : DCHECK(length_ >= capacity_);
58 : // Grow the list capacity by 100%, but make sure to let it grow
59 : // even when the capacity is zero (possible initial case).
60 57474948 : int new_capacity = 1 + 2 * capacity_;
61 : // Since the element reference could be an element of the list, copy
62 : // it out of the old backing storage before resizing.
63 57474948 : T temp = element;
64 57474948 : Resize(new_capacity, alloc);
65 57474951 : data_[length_++] = temp;
66 57474951 : }
67 :
68 :
69 : template<typename T, class P>
70 71433103 : void List<T, P>::Resize(int new_capacity, P alloc) {
71 : DCHECK_LE(length_, new_capacity);
72 : T* new_data = NewData(new_capacity, alloc);
73 71433064 : MemCopy(new_data, data_, length_ * sizeof(T));
74 31890042 : List<T, P>::DeleteData(data_);
75 71433065 : data_ = new_data;
76 71433065 : capacity_ = new_capacity;
77 71433065 : }
78 :
79 :
80 : template<typename T, class P>
81 : Vector<T> List<T, P>::AddBlock(T value, int count, P alloc) {
82 12191913 : int start = length_;
83 114838206 : for (int i = 0; i < count; i++) Add(value, alloc);
84 12191940 : return Vector<T>(&data_[start], count);
85 : }
86 :
87 :
88 : template<typename T, class P>
89 : void List<T, P>::Set(int index, const T& elm) {
90 : DCHECK(index >= 0 && index <= length_);
91 24730695 : data_[index] = elm;
92 : }
93 :
94 :
95 : template<typename T, class P>
96 6575672 : void List<T, P>::InsertAt(int index, const T& elm, P alloc) {
97 : DCHECK(index >= 0 && index <= length_);
98 6575672 : Add(elm, alloc);
99 24050994 : for (int i = length_ - 1; i > index; --i) {
100 17475319 : data_[i] = data_[i - 1];
101 : }
102 6575675 : data_[index] = elm;
103 6575675 : }
104 :
105 :
106 : template<typename T, class P>
107 234089023 : T List<T, P>::Remove(int i) {
108 234089023 : T element = at(i);
109 234089023 : length_--;
110 610696519 : while (i < length_) {
111 142518473 : data_[i] = data_[i + 1];
112 142518473 : i++;
113 : }
114 234089023 : return element;
115 : }
116 :
117 :
118 : template<typename T, class P>
119 30217682 : bool List<T, P>::RemoveElement(const T& elm) {
120 79879053 : for (int i = 0; i < length_; i++) {
121 79878716 : if (data_[i] == elm) {
122 30217345 : Remove(i);
123 30217971 : return true;
124 : }
125 : }
126 : return false;
127 : }
128 :
129 : template <typename T, class P>
130 : void List<T, P>::Swap(List<T, P>* list) {
131 862979 : std::swap(data_, list->data_);
132 862979 : std::swap(length_, list->length_);
133 862979 : std::swap(capacity_, list->capacity_);
134 : }
135 :
136 : template<typename T, class P>
137 : void List<T, P>::Allocate(int length, P allocator) {
138 18 : DeleteData(data_);
139 : Initialize(length, allocator);
140 18 : length_ = length;
141 : }
142 :
143 :
144 : template<typename T, class P>
145 : void List<T, P>::Clear() {
146 5267525 : DeleteData(data_);
147 : // We don't call Initialize(0) since that requires passing a Zone,
148 : // which we don't really need.
149 37490373 : data_ = NULL;
150 37490373 : capacity_ = 0;
151 37490373 : length_ = 0;
152 : }
153 :
154 :
155 : template<typename T, class P>
156 : void List<T, P>::Rewind(int pos) {
157 : DCHECK(0 <= pos && pos <= length_);
158 996455536 : length_ = pos;
159 : }
160 :
161 :
162 : template<typename T, class P>
163 : void List<T, P>::Trim(P alloc) {
164 229227 : if (length_ < capacity_ / 4) {
165 12529 : Resize(capacity_ / 2, alloc);
166 : }
167 : }
168 :
169 :
170 : template<typename T, class P>
171 : void List<T, P>::Iterate(void (*callback)(T* x)) {
172 468 : for (int i = 0; i < length_; i++) callback(&data_[i]);
173 : }
174 :
175 :
176 : template<typename T, class P>
177 : template<class Visitor>
178 : void List<T, P>::Iterate(Visitor* visitor) {
179 : for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
180 : }
181 :
182 :
183 : template<typename T, class P>
184 : bool List<T, P>::Contains(const T& elm) const {
185 18573255680 : for (int i = 0; i < length_; i++) {
186 18573756111 : if (data_[i] == elm)
187 : return true;
188 : }
189 : return false;
190 : }
191 :
192 :
193 : template<typename T, class P>
194 : int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
195 : int result = 0;
196 : for (int i = start; i <= end; i++) {
197 : if (data_[i] == elm) ++result;
198 : }
199 : return result;
200 : }
201 :
202 :
203 : template <typename T, class P>
204 : template <typename CompareFunction>
205 : void List<T, P>::Sort(CompareFunction cmp) {
206 568305 : Sort(cmp, 0, length_);
207 : }
208 :
209 :
210 : template <typename T, class P>
211 : template <typename CompareFunction>
212 568305 : void List<T, P>::Sort(CompareFunction cmp, size_t s, size_t l) {
213 568305 : ToVector().Sort(cmp, s, l);
214 : #ifdef DEBUG
215 : for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
216 : #endif
217 : }
218 :
219 :
220 : template<typename T, class P>
221 : void List<T, P>::Sort() {
222 : ToVector().Sort();
223 : }
224 :
225 :
226 : template <typename T, class P>
227 : template <typename CompareFunction>
228 : void List<T, P>::StableSort(CompareFunction cmp) {
229 : StableSort(cmp, 0, length_);
230 : }
231 :
232 :
233 : template <typename T, class P>
234 : template <typename CompareFunction>
235 11407 : void List<T, P>::StableSort(CompareFunction cmp, size_t s, size_t l) {
236 11407 : ToVector().StableSort(cmp, s, l);
237 : #ifdef DEBUG
238 : for (size_t i = s + 1; i < l; i++) DCHECK(cmp(&data_[i - 1], &data_[i]) <= 0);
239 : #endif
240 : }
241 :
242 :
243 : template <typename T, class P>
244 : void List<T, P>::StableSort() {
245 : ToVector().StableSort();
246 : }
247 :
248 :
249 : template <typename T, typename P>
250 3311668 : int SortedListBSearch(const List<T>& list, P cmp) {
251 : int low = 0;
252 248130 : int high = list.length() - 1;
253 3311680 : while (low <= high) {
254 3063538 : int mid = low + (high - low) / 2;
255 3063538 : T mid_elem = list[mid];
256 :
257 3063538 : if (cmp(&mid_elem) > 0) {
258 1338756 : high = mid - 1;
259 1338756 : continue;
260 : }
261 1724782 : if (cmp(&mid_elem) < 0) {
262 1476664 : low = mid + 1;
263 1476664 : continue;
264 : }
265 : // Found the element.
266 : return mid;
267 : }
268 : return -1;
269 : }
270 :
271 :
272 : template<typename T>
273 : class ElementCmp {
274 : public:
275 : explicit ElementCmp(T e) : elem_(e) {}
276 : int operator()(const T* other) {
277 : return PointerValueCompare(other, &elem_);
278 : }
279 : private:
280 : T elem_;
281 : };
282 :
283 :
284 : template <typename T>
285 : int SortedListBSearch(const List<T>& list, T elem) {
286 : return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem));
287 : }
288 :
289 :
290 : } // namespace internal
291 : } // namespace v8
292 :
293 : #endif // V8_LIST_INL_H_
|
