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