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 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. 60 template<typename T, class P> 61 void List<T, P>::ResizeAdd(const T& element) { 62 ResizeAddInternal(element); 63 } 64 65 66 template<typename T, class P> 67 void 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 80 template<typename T, class P> 81 void 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 90 template<typename T, class P> 91 Vector<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 98 template<typename T, class P> 99 T List<T, P>::Remove(int i) { 100 T element = at(i); 101 length_--; 102 while (i < length_) { 103 data_[i] = data_[i + 1]; 104 i++; 105 } 106 return element; 107 } 108 109 110 template<typename T, class P> 111 void List<T, P>::Clear() { 112 DeleteData(data_); 113 Initialize(0); 114 } 115 116 117 template<typename T, class P> 118 void List<T, P>::Rewind(int pos) { 119 length_ = pos; 120 } 121 122 123 template<typename T, class P> 124 void List<T, P>::Iterate(void (*callback)(T* x)) { 125 for (int i = 0; i < length_; i++) callback(&data_[i]); 126 } 127 128 129 template<typename T, class P> 130 bool List<T, P>::Contains(const T& elm) { 131 for (int i = 0; i < length_; i++) { 132 if (data_[i] == elm) 133 return true; 134 } 135 return false; 136 } 137 138 139 template<typename T, class P> 140 void List<T, P>::Sort(int (*cmp)(const T* x, const T* y)) { 141 ToVector().Sort(cmp); 142 #ifdef DEBUG 143 for (int i = 1; i < length_; i++) 144 ASSERT(cmp(&data_[i - 1], &data_[i]) <= 0); 145 #endif 146 } 147 148 149 template<typename T, class P> 150 void List<T, P>::Sort() { 151 Sort(PointerValueCompare<T>); 152 } 153 154 155 template<typename T, class P> 156 void List<T, P>::Initialize(int capacity) { 157 ASSERT(capacity >= 0); 158 data_ = (capacity > 0) ? NewData(capacity) : NULL; 159 capacity_ = capacity; 160 length_ = 0; 161 } 162 163 164 } } // namespace v8::internal 165 166 #endif // V8_LIST_INL_H_ 167
