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