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