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  int result_length = length_ + other.length_;
50  if (capacity_ < result_length) Resize(result_length);
51  for (int i = 0; i < other.length_; i++) {
52    data_[length_ + i] = other.data_[i];
53  }
54  length_ = result_length;
55}
56
57
58// Use two layers of inlining so that the non-inlined function can
59// use the same implementation as the inlined version.
60template<typename T, class P>
61void List<T, P>::ResizeAdd(const T& element) {
62  ResizeAddInternal(element);
63}
64
65
66template<typename T, class P>
67void List<T, P>::ResizeAddInternal(const T& element) {
68  ASSERT(length_ >= capacity_);
69  // Grow the list capacity by 50%, but make sure to let it grow
70  // even when the capacity is zero (possible initial case).
71  int new_capacity = 1 + capacity_ + (capacity_ >> 1);
72  // Since the element reference could be an element of the list, copy
73  // it out of the old backing storage before resizing.
74  T temp = element;
75  Resize(new_capacity);
76  data_[length_++] = temp;
77}
78
79
80template<typename T, class P>
81void List<T, P>::Resize(int new_capacity) {
82  T* new_data = List<T, P>::NewData(new_capacity);
83  memcpy(new_data, data_, capacity_ * sizeof(T));
84  List<T, P>::DeleteData(data_);
85  data_ = new_data;
86  capacity_ = new_capacity;
87}
88
89
90template<typename T, class P>
91Vector<T> List<T, P>::AddBlock(T value, int count) {
92  int start = length_;
93  for (int i = 0; i < count; i++) Add(value);
94  return Vector<T>(&data_[start], count);
95}
96
97
98template<typename T, class P>
99void List<T, P>::InsertAt(int index, const T& elm) {
100  ASSERT(index >= 0 && index <= length_);
101  Add(elm);
102  for (int i = length_ - 1; i > index; --i) {
103    data_[i] = data_[i - 1];
104  }
105  data_[index] = elm;
106}
107
108
109template<typename T, class P>
110T List<T, P>::Remove(int i) {
111  T element = at(i);
112  length_--;
113  while (i < length_) {
114    data_[i] = data_[i + 1];
115    i++;
116  }
117  return element;
118}
119
120
121template<typename T, class P>
122bool List<T, P>::RemoveElement(const T& elm) {
123  for (int i = 0; i < length_; i++) {
124    if (data_[i] == elm) {
125      Remove(i);
126      return true;
127    }
128  }
129  return false;
130}
131
132
133template<typename T, class P>
134void List<T, P>::Clear() {
135  DeleteData(data_);
136  Initialize(0);
137}
138
139
140template<typename T, class P>
141void List<T, P>::Rewind(int pos) {
142  length_ = pos;
143}
144
145
146template<typename T, class P>
147void List<T, P>::Iterate(void (*callback)(T* x)) {
148  for (int i = 0; i < length_; i++) callback(&data_[i]);
149}
150
151
152template<typename T, class P>
153template<class Visitor>
154void List<T, P>::Iterate(Visitor* visitor) {
155  for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
156}
157
158
159template<typename T, class P>
160bool List<T, P>::Contains(const T& elm) const {
161  for (int i = 0; i < length_; i++) {
162    if (data_[i] == elm)
163      return true;
164  }
165  return false;
166}
167
168
169template<typename T, class P>
170int List<T, P>::CountOccurrences(const T& elm, int start, int end) const {
171  int result = 0;
172  for (int i = start; i <= end; i++) {
173    if (data_[i] == elm) ++result;
174  }
175  return result;
176}
177
178
179template<typename T, class P>
180void List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) {
181  ToVector().Sort(cmp);
182#ifdef DEBUG
183  for (int i = 1; i < length_; i++)
184    ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0);
185#endif
186}
187
188
189template<typename T, class P>
190void List<T, P>::Sort() {
191  Sort(PointerValueCompare<T>);
192}
193
194
195template<typename T, class P>
196void List<T, P>::Initialize(int capacity) {
197  ASSERT(capacity >= 0);
198  data_ = (capacity > 0) ? NewData(capacity) : NULL;
199  capacity_ = capacity;
200  length_ = 0;
201}
202
203
204} }  // namespace v8::internal
205
206#endif  // V8_LIST_INL_H_
207