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
33 namespace v8 {
34 namespace internal {
35
36
37 template<typename T, class P>
Add(const T & element)38 void 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
47 template<typename T, class P>
AddAll(const List<T,P> & other)48 void List<T, P>::AddAll(const List<T, P>& other) {
49 AddAll(other.ToVector());
50 }
51
52
53 template<typename T, class P>
AddAll(const Vector<T> & other)54 void 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.
66 template<typename T, class P>
ResizeAdd(const T & element)67 void List<T, P>::ResizeAdd(const T& element) {
68 ResizeAddInternal(element);
69 }
70
71
72 template<typename T, class P>
ResizeAddInternal(const T & element)73 void 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
86 template<typename T, class P>
Resize(int new_capacity)87 void 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
96 template<typename T, class P>
AddBlock(T value,int count)97 Vector<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
104 template<typename T, class P>
InsertAt(int index,const T & elm)105 void 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
115 template<typename T, class P>
Remove(int i)116 T 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
127 template<typename T, class P>
RemoveElement(const T & elm)128 bool 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
139 template<typename T, class P>
Clear()140 void List<T, P>::Clear() {
141 DeleteData(data_);
142 Initialize(0);
143 }
144
145
146 template<typename T, class P>
Rewind(int pos)147 void List<T, P>::Rewind(int pos) {
148 length_ = pos;
149 }
150
151
152 template<typename T, class P>
Iterate(void (* callback)(T * x))153 void List<T, P>::Iterate(void (*callback)(T* x)) {
154 for (int i = 0; i < length_; i++) callback(&data_[i]);
155 }
156
157
158 template<typename T, class P>
159 template<class Visitor>
Iterate(Visitor * visitor)160 void List<T, P>::Iterate(Visitor* visitor) {
161 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]);
162 }
163
164
165 template<typename T, class P>
Contains(const T & elm)166 bool 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
175 template<typename T, class P>
CountOccurrences(const T & elm,int start,int end)176 int 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
185 template<typename T, class P>
Sort(int (* cmp)(const T * x,const T * y))186 void 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
195 template<typename T, class P>
Sort()196 void List<T, P>::Sort() {
197 Sort(PointerValueCompare<T>);
198 }
199
200
201 template<typename T, class P>
Initialize(int capacity)202 void 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
210 template <typename T>
SortedListBSearch(const List<T> & list,T elem,int (* cmp)(const T * x,const T * y))211 int 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
234 template <typename T>
SortedListBSearch(const List<T> & list,T elem)235 int 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