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