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