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