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