1 // Copyright 2006-2009 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #ifndef V8_LIST_INL_H_ 29 #define V8_LIST_INL_H_ 30 31 #include "list.h" 32 #include "platform.h" 33 34 namespace v8 { 35 namespace internal { 36 37 38 template<typename T, class P> 39 void List<T, P>::Add(const T& element, P alloc) { 40 if (length_ < capacity_) { 41 data_[length_++] = element; 42 } else { 43 List<T, P>::ResizeAdd(element, alloc); 44 } 45 } 46 47 48 template<typename T, class P> 49 void List<T, P>::AddAll(const List<T, P>& other, P alloc) { 50 AddAll(other.ToVector(), alloc); 51 } 52 53 54 template<typename T, class P> 55 void List<T, P>::AddAll(const Vector<T>& other, P alloc) { 56 int result_length = length_ + other.length(); 57 if (capacity_ < result_length) Resize(result_length, alloc); 58 for (int i = 0; i < other.length(); i++) { 59 data_[length_ + i] = other.at(i); 60 } 61 length_ = result_length; 62 } 63 64 65 // Use two layers of inlining so that the non-inlined function can 66 // use the same implementation as the inlined version. 67 template<typename T, class P> 68 void List<T, P>::ResizeAdd(const T& element, P alloc) { 69 ResizeAddInternal(element, alloc); 70 } 71 72 73 template<typename T, class P> 74 void List<T, P>::ResizeAddInternal(const T& element, P alloc) { 75 ASSERT(length_ >= capacity_); 76 // Grow the list capacity by 100%, but make sure to let it grow 77 // even when the capacity is zero (possible initial case). 78 int new_capacity = 1 + 2 * capacity_; 79 // Since the element reference could be an element of the list, copy 80 // it out of the old backing storage before resizing. 81 T temp = element; 82 Resize(new_capacity, alloc); 83 data_[length_++] = temp; 84 } 85 86 87 template<typename T, class P> 88 void List<T, P>::Resize(int new_capacity, P alloc) { 89 ASSERT_LE(length_, new_capacity); 90 T* new_data = NewData(new_capacity, alloc); 91 OS::MemCopy(new_data, data_, length_ * sizeof(T)); 92 List<T, P>::DeleteData(data_); 93 data_ = new_data; 94 capacity_ = new_capacity; 95 } 96 97 98 template<typename T, class P> 99 Vector<T> List<T, P>::AddBlock(T value, int count, P alloc) { 100 int start = length_; 101 for (int i = 0; i < count; i++) Add(value, alloc); 102 return Vector<T>(&data_[start], count); 103 } 104 105 106 template<typename T, class P> 107 void List<T, P>::Set(int index, const T& elm) { 108 ASSERT(index >= 0 && index <= length_); 109 data_[index] = elm; 110 } 111 112 113 template<typename T, class P> 114 void List<T, P>::InsertAt(int index, const T& elm, P alloc) { 115 ASSERT(index >= 0 && index <= length_); 116 Add(elm, alloc); 117 for (int i = length_ - 1; i > index; --i) { 118 data_[i] = data_[i - 1]; 119 } 120 data_[index] = elm; 121 } 122 123 124 template<typename T, class P> 125 T List<T, P>::Remove(int i) { 126 T element = at(i); 127 length_--; 128 while (i < length_) { 129 data_[i] = data_[i + 1]; 130 i++; 131 } 132 return element; 133 } 134 135 136 template<typename T, class P> 137 bool List<T, P>::RemoveElement(const T& elm) { 138 for (int i = 0; i < length_; i++) { 139 if (data_[i] == elm) { 140 Remove(i); 141 return true; 142 } 143 } 144 return false; 145 } 146 147 148 template<typename T, class P> 149 void List<T, P>::Allocate(int length, P allocator) { 150 DeleteData(data_); 151 Initialize(length, allocator); 152 length_ = length; 153 } 154 155 156 template<typename T, class P> 157 void List<T, P>::Clear() { 158 DeleteData(data_); 159 // We don't call Initialize(0) since that requires passing a Zone, 160 // which we don't really need. 161 data_ = NULL; 162 capacity_ = 0; 163 length_ = 0; 164 } 165 166 167 template<typename T, class P> 168 void List<T, P>::Rewind(int pos) { 169 length_ = pos; 170 } 171 172 173 template<typename T, class P> 174 void List<T, P>::Trim(P alloc) { 175 if (length_ < capacity_ / 4) { 176 Resize(capacity_ / 2, alloc); 177 } 178 } 179 180 181 template<typename T, class P> 182 void List<T, P>::Iterate(void (*callback)(T* x)) { 183 for (int i = 0; i < length_; i++) callback(&data_[i]); 184 } 185 186 187 template<typename T, class P> 188 template<class Visitor> 189 void List<T, P>::Iterate(Visitor* visitor) { 190 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]); 191 } 192 193 194 template<typename T, class P> 195 bool List<T, P>::Contains(const T& elm) const { 196 for (int i = 0; i < length_; i++) { 197 if (data_[i] == elm) 198 return true; 199 } 200 return false; 201 } 202 203 204 template<typename T, class P> 205 int List<T, P>::CountOccurrences(const T& elm, int start, int end) const { 206 int result = 0; 207 for (int i = start; i <= end; i++) { 208 if (data_[i] == elm) ++result; 209 } 210 return result; 211 } 212 213 214 template<typename T, class P> 215 void List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) { 216 ToVector().Sort(cmp); 217 #ifdef DEBUG 218 for (int i = 1; i < length_; i++) 219 ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0); 220 #endif 221 } 222 223 224 template<typename T, class P> 225 void List<T, P>::Sort() { 226 ToVector().Sort(); 227 } 228 229 230 template<typename T, class P> 231 void List<T, P>::Initialize(int capacity, P allocator) { 232 ASSERT(capacity >= 0); 233 data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL; 234 capacity_ = capacity; 235 length_ = 0; 236 } 237 238 239 template <typename T, typename P> 240 int SortedListBSearch(const List<T>& list, P cmp) { 241 int low = 0; 242 int high = list.length() - 1; 243 while (low <= high) { 244 int mid = (low + high) / 2; 245 T mid_elem = list[mid]; 246 247 if (cmp(&mid_elem) > 0) { 248 high = mid - 1; 249 continue; 250 } 251 if (cmp(&mid_elem) < 0) { 252 low = mid + 1; 253 continue; 254 } 255 // Found the elememt. 256 return mid; 257 } 258 return -1; 259 } 260 261 262 template<typename T> 263 class ElementCmp { 264 public: 265 explicit ElementCmp(T e) : elem_(e) {} 266 int operator()(const T* other) { 267 return PointerValueCompare(other, &elem_); 268 } 269 private: 270 T elem_; 271 }; 272 273 274 template <typename T> 275 int SortedListBSearch(const List<T>& list, T elem) { 276 return SortedListBSearch<T, ElementCmp<T> > (list, ElementCmp<T>(elem)); 277 } 278 279 280 } } // namespace v8::internal 281 282 #endif // V8_LIST_INL_H_ 283
