1// Copyright 2006-2009 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_LIST_INL_H_
29#define V8_LIST_INL_H_
30
31#include "list.h"
32
33namespace v8 {
34namespace internal {
35
36
37template<typename T, class P>
38void List<T, P>::Add(const T& element) {
39  if (length_ < capacity_) {
40    data_[length_++] = element;
41  } else {
42    List<T, P>::ResizeAdd(element);
43  }
44}
45
46
47template<typename T, class P>
48void List<T, P>::AddAll(const List<T, P>& other) {
49  AddAll(other.ToVector());
50}
51
52
53template<typename T, class P>
54void List<T, P>::AddAll(const Vector<T>& other) {
55  int result_length = length_ + other.length();
56  if (capacity_ < result_length) Resize(result_length);
57  for (int i = 0; i < other.length(); i++) {
58    data_[length_ + i] = other.at(i);
59  }
60  length_ = result_length;
61}
62
63
64// Use two layers of inlining so that the non-inlined function can
65// use the same implementation as the inlined version.
66template<typename T, class P>
67void List<T, P>::ResizeAdd(const T& element) {
68  ResizeAddInternal(element);
69}
70
71
72template<typename T, class P>
73void List<T, P>::ResizeAddInternal(const T& element) {
74  ASSERT(length_ >= capacity_);
75  // Grow the list capacity by 100%, but make sure to let it grow
76  // even when the capacity is zero (possible initial case).
77  int new_capacity = 1 + 2 * capacity_;
78  // Since the element reference could be an element of the list, copy
79  // it out of the old backing storage before resizing.
80  T temp = element;
81  Resize(new_capacity);
82  data_[length_++] = temp;
83}
84
85
86template<typename T, class P>
87void List<T, P>::Resize(int new_capacity) {
88  T* new_data = List<T, P>::NewData(new_capacity);
89  memcpy(new_data, data_, capacity_ * sizeof(T));
90  List<T, P>::DeleteData(data_);
91  data_ = new_data;
92  capacity_ = new_capacity;
93}
94
95
96template<typename T, class P>
97Vector<T> List<T, P>::AddBlock(T value, int count) {
98  int start = length_;
99  for (int i = 0; i < count; i++) Add(value);
100  return Vector<T>(&data_[start], count);
101}
102
103
104template<typename T, class P>
105void List<T, P>::InsertAt(int index, const T& elm) {
106  ASSERT(index >= 0 && index <= length_);
107  Add(elm);
108  for (int i = length_ - 1; i > index; --i) {
109    data_[i] = data_[i - 1];
110  }
111  data_[index] = elm;
112}
113
114
115template<typename T, class P>
116T List<T, P>::Remove(int i) {
117  T element = at(i);
118  length_--;
119  while (i < length_) {
120    data_[i] = data_[i + 1];
121    i++;
122  }
123  return element;
124}
125
126
127template<typename T, class P>
128bool List<T, P>::RemoveElement(const T& elm) {
129  for (int i = 0; i < length_; i++) {
130    if (data_[i] == elm) {
131      Remove(i);
132      return true;
133    }
134  }
135  return false;
136}
137
138
139template<typename T, class P>
140void List<T, P>::Clear() {
141  DeleteData(data_);
142  Initialize(0);
143}
144
145
146template<typename T, class P>
147void List<T, P>::Rewind(int pos) {
148  length_ = pos;
149}
150
151
152template<typename T, class P>
153void List<T, P>::Iterate(void (*callback)(T* x)) {
154  for (int i = 0; i < length_; i++) callback(&data_[i]);
155}
156
157
158template<typename T, class P>
159template<class Visitor>
160void List<T, P>::Iterate(Visitor* visitor) {
161  for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
162}
163
164
165template<typename T, class P>
166bool List<T, P>::Contains(const T& elm) const {
167  for (int i = 0; i < length_; i++) {
168    if (data_[i] == elm)
169      return true;
170  }
171  return false;
172}
173
174
175template<typename T, class P>
176int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
177  int result = 0;
178  for (int i = start; i <= end; i++) {
179    if (data_[i] == elm) ++result;
180  }
181  return result;
182}
183
184
185template<typename T, class P>
186void List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) {
187  ToVector().Sort(cmp);
188#ifdef DEBUG
189  for (int i = 1; i < length_; i++)
190    ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0);
191#endif
192}
193
194
195template<typename T, class P>
196void List<T, P>::Sort() {
197  Sort(PointerValueCompare<T>);
198}
199
200
201template<typename T, class P>
202void List<T, P>::Initialize(int capacity) {
203  ASSERT(capacity >= 0);
204  data_ = (capacity > 0) ? NewData(capacity) : NULL;
205  capacity_ = capacity;
206  length_ = 0;
207}
208
209
210template <typename T>
211int SortedListBSearch(
212    const List<T>& list, T elem, int (*cmp)(const T* x, const T* y)) {
213  int low = 0;
214  int high = list.length() - 1;
215  while (low <= high) {
216    int mid = (low + high) / 2;
217    T mid_elem = list[mid];
218
219    if (cmp(&mid_elem, &elem) > 0) {
220      high = mid - 1;
221      continue;
222    }
223    if (cmp(&mid_elem, &elem) < 0) {
224      low = mid + 1;
225      continue;
226    }
227    // Found the elememt.
228    return mid;
229  }
230  return -1;
231}
232
233
234template <typename T>
235int SortedListBSearch(const List<T>& list, T elem) {
236  return SortedListBSearch<T>(list, elem, PointerValueCompare<T>);
237}
238
239
240} }  // namespace v8::internal
241
242#endif  // V8_LIST_INL_H_
243