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