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
13namespace v8 {
14namespace internal {
15
16
17template<typename T, class P>
18void 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
27template<typename T, class P>
28void List<T, P>::AddAll(const List<T, P>& other, P alloc) {
29  AddAll(other.ToVector(), alloc);
30}
31
32
33template<typename T, class P>
34void 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.
48template<typename T, class P>
49void List<T, P>::ResizeAdd(const T& element, P alloc) {
50  ResizeAddInternal(element, alloc);
51}
52
53
54template<typename T, class P>
55void 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
68template<typename T, class P>
69void 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
79template<typename T, class P>
80Vector<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
87template<typename T, class P>
88void List<T, P>::Set(int index, const T& elm) {
89  DCHECK(index >= 0 && index <= length_);
90  data_[index] = elm;
91}
92
93
94template<typename T, class P>
95void 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
105template<typename T, class P>
106T 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
117template<typename T, class P>
118bool 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
128template <typename T, class P>
129void 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
135template<typename T, class P>
136void List<T, P>::Allocate(int length, P allocator) {
137  DeleteData(data_);
138  Initialize(length, allocator);
139  length_ = length;
140}
141
142
143template<typename T, class P>
144void 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
154template<typename T, class P>
155void List<T, P>::Rewind(int pos) {
156  DCHECK(0 <= pos && pos <= length_);
157  length_ = pos;
158}
159
160
161template<typename T, class P>
162void List<T, P>::Trim(P alloc) {
163  if (length_ < capacity_ / 4) {
164    Resize(capacity_ / 2, alloc);
165  }
166}
167
168
169template<typename T, class P>
170void List<T, P>::Iterate(void (*callback)(T* x)) {
171  for (int i = 0; i < length_; i++) callback(&data_[i]);
172}
173
174
175template<typename T, class P>
176template<class Visitor>
177void List<T, P>::Iterate(Visitor* visitor) {
178  for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
179}
180
181
182template<typename T, class P>
183bool 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
192template<typename T, class P>
193int 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
202template <typename T, class P>
203template <typename CompareFunction>
204void List<T, P>::Sort(CompareFunction cmp) {
205  Sort(cmp, 0, length_);
206}
207
208
209template <typename T, class P>
210template <typename CompareFunction>
211void 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
219template<typename T, class P>
220void List<T, P>::Sort() {
221  ToVector().Sort();
222}
223
224
225template <typename T, class P>
226template <typename CompareFunction>
227void List<T, P>::StableSort(CompareFunction cmp) {
228  StableSort(cmp, 0, length_);
229}
230
231
232template <typename T, class P>
233template <typename CompareFunction>
234void 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
242template <typename T, class P>
243void List<T, P>::StableSort() {
244  ToVector().StableSort();
245}
246
247
248template <typename T, typename P>
249int 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
271template<typename T>
272class ElementCmp {
273 public:
274  explicit ElementCmp(T e) : elem_(e) {}
275  int operator()(const T* other) {
276    return PointerValueCompare(other, &elem_);
277  }
278 private:
279  T elem_;
280};
281
282
283template <typename T>
284int 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