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