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