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 13 namespace v8 { 14 namespace internal { 15 16 17 template<typename T, class P> 18 void 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 27 template<typename T, class P> 28 void List<T, P>::AddAll(const List<T, P>& other, P alloc) { 29 AddAll(other.ToVector(), alloc); 30 } 31 32 33 template<typename T, class P> 34 void 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. 48 template<typename T, class P> 49 void List<T, P>::ResizeAdd(const T& element, P alloc) { 50 ResizeAddInternal(element, alloc); 51 } 52 53 54 template<typename T, class P> 55 void 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 68 template<typename T, class P> 69 void 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 79 template<typename T, class P> 80 Vector<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 87 template<typename T, class P> 88 void List<T, P>::Set(int index, const T& elm) { 89 DCHECK(index >= 0 && index <= length_); 90 data_[index] = elm; 91 } 92 93 94 template<typename T, class P> 95 void 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 105 template<typename T, class P> 106 T 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 117 template<typename T, class P> 118 bool 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 128 template <typename T, class P> 129 void 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 135 template<typename T, class P> 136 void List<T, P>::Allocate(int length, P allocator) { 137 DeleteData(data_); 138 Initialize(length, allocator); 139 length_ = length; 140 } 141 142 143 template<typename T, class P> 144 void 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 154 template<typename T, class P> 155 void List<T, P>::Rewind(int pos) { 156 DCHECK(0 <= pos && pos <= length_); 157 length_ = pos; 158 } 159 160 161 template<typename T, class P> 162 void List<T, P>::Trim(P alloc) { 163 if (length_ < capacity_ / 4) { 164 Resize(capacity_ / 2, alloc); 165 } 166 } 167 168 169 template<typename T, class P> 170 void List<T, P>::Iterate(void (*callback)(T* x)) { 171 for (int i = 0; i < length_; i++) callback(&data_[i]); 172 } 173 174 175 template<typename T, class P> 176 template<class Visitor> 177 void List<T, P>::Iterate(Visitor* visitor) { 178 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]); 179 } 180 181 182 template<typename T, class P> 183 bool 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 192 template<typename T, class P> 193 int 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 202 template <typename T, class P> 203 template <typename CompareFunction> 204 void List<T, P>::Sort(CompareFunction cmp) { 205 Sort(cmp, 0, length_); 206 } 207 208 209 template <typename T, class P> 210 template <typename CompareFunction> 211 void 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 219 template<typename T, class P> 220 void List<T, P>::Sort() { 221 ToVector().Sort(); 222 } 223 224 225 template <typename T, class P> 226 template <typename CompareFunction> 227 void List<T, P>::StableSort(CompareFunction cmp) { 228 StableSort(cmp, 0, length_); 229 } 230 231 232 template <typename T, class P> 233 template <typename CompareFunction> 234 void 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 242 template <typename T, class P> 243 void List<T, P>::StableSort() { 244 ToVector().StableSort(); 245 } 246 247 248 template <typename T, typename P> 249 int 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 271 template<typename T> 272 class 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 283 template <typename T> 284 int 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
