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 33 namespace v8 { 34 namespace internal { 35 36 37 template<typename T, class P> 38 void 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 47 template<typename T, class P> 48 void List<T, P>::AddAll(const List<T, P>& other) { 49 AddAll(other.ToVector()); 50 } 51 52 53 template<typename T, class P> 54 void 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. 66 template<typename T, class P> 67 void List<T, P>::ResizeAdd(const T& element) { 68 ResizeAddInternal(element); 69 } 70 71 72 template<typename T, class P> 73 void 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 86 template<typename T, class P> 87 void 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 96 template<typename T, class P> 97 Vector<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 104 template<typename T, class P> 105 void 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 115 template<typename T, class P> 116 T 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 127 template<typename T, class P> 128 bool 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 139 template<typename T, class P> 140 void List<T, P>::Clear() { 141 DeleteData(data_); 142 Initialize(0); 143 } 144 145 146 template<typename T, class P> 147 void List<T, P>::Rewind(int pos) { 148 length_ = pos; 149 } 150 151 152 template<typename T, class P> 153 void List<T, P>::Iterate(void (*callback)(T* x)) { 154 for (int i = 0; i < length_; i++) callback(&data_[i]); 155 } 156 157 158 template<typename T, class P> 159 template<class Visitor> 160 void List<T, P>::Iterate(Visitor* visitor) { 161 for (int i = 0; i < length_; i++) visitor->Apply(&data_[i]); 162 } 163 164 165 template<typename T, class P> 166 bool 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 175 template<typename T, class P> 176 int 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 185 template<typename T, class P> 186 void 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 195 template<typename T, class P> 196 void List<T, P>::Sort() { 197 Sort(PointerValueCompare<T>); 198 } 199 200 201 template<typename T, class P> 202 void 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 210 template <typename T> 211 int 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 234 template <typename T> 235 int 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
