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 12 namespace v8 { 13 namespace internal { 14 15 16 template<typename T, class P> 17 void 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 26 template<typename T, class P> 27 void List<T, P>::AddAll(const List<T, P>& other, P alloc) { 28 AddAll(other.ToVector(), alloc); 29 } 30 31 32 template<typename T, class P> 33 void 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. 45 template<typename T, class P> 46 void List<T, P>::ResizeAdd(const T& element, P alloc) { 47 ResizeAddInternal(element, alloc); 48 } 49 50 51 template<typename T, class P> 52 void 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 65 template<typename T, class P> 66 void 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 76 template<typename T, class P> 77 Vector<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 84 template<typename T, class P> 85 void List<T, P>::Set(int index, const T& elm) { 86 DCHECK(index >= 0 && index <= length_); 87 data_[index] = elm; 88 } 89 90 91 template<typename T, class P> 92 void 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 102 template<typename T, class P> 103 T 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 114 template<typename T, class P> 115 bool 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 126 template<typename T, class P> 127 void List<T, P>::Allocate(int length, P allocator) { 128 DeleteData(data_); 129 Initialize(length, allocator); 130 length_ = length; 131 } 132 133 134 template<typename T, class P> 135 void 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 145 template<typename T, class P> 146 void List<T, P>::Rewind(int pos) { 147 DCHECK(0 <= pos && pos <= length_); 148 length_ = pos; 149 } 150 151 152 template<typename T, class P> 153 void List<T, P>::Trim(P alloc) { 154 if (length_ < capacity_ / 4) { 155 Resize(capacity_ / 2, alloc); 156 } 157 } 158 159 160 template<typename T, class P> 161 void List<T, P>::Iterate(void (*callback)(T* x)) { 162 for (int i = 0; i < length_; i++) callback(&data_[i]); 163 } 164 165 166 template<typename T, class P> 167 template<class Visitor> 168 void List<T, P>::Iterate(Visitor* visitor) { 169 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]); 170 } 171 172 173 template<typename T, class P> 174 bool 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 183 template<typename T, class P> 184 int 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 193 template<typename T, class P> 194 void 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 203 template<typename T, class P> 204 void List<T, P>::Sort() { 205 ToVector().Sort(); 206 } 207 208 209 template<typename T, class P> 210 void 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 218 template <typename T, typename P> 219 int 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 241 template<typename T> 242 class 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 253 template <typename T> 254 int 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