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_H_ 29 #define V8_LIST_H_ 30 31 namespace v8 { 32 namespace internal { 33 34 35 // ---------------------------------------------------------------------------- 36 // The list is a template for very light-weight lists. We are not 37 // using the STL because we want full control over space and speed of 38 // the code. This implementation is based on code by Robert Griesemer 39 // and Rob Pike. 40 // 41 // The list is parameterized by the type of its elements (T) and by an 42 // allocation policy (P). The policy is used for allocating lists in 43 // the C free store or the zone; see zone.h. 44 45 // Forward defined as 46 // template <typename T, class P = FreeStoreAllocationPolicy> class List; 47 template <typename T, class P> 48 class List { 49 public: 50 51 List() { Initialize(0); } 52 INLINE(explicit List(int capacity)) { Initialize(capacity); } 53 INLINE(~List()) { DeleteData(data_); } 54 55 // Deallocates memory used by the list and leaves the list in a consistent 56 // empty state. 57 void Free() { 58 DeleteData(data_); 59 Initialize(0); 60 } 61 62 INLINE(void* operator new(size_t size)) { 63 return P::New(static_cast<int>(size)); 64 } 65 INLINE(void operator delete(void* p, size_t)) { return P::Delete(p); } 66 67 // Returns a reference to the element at index i. This reference is 68 // not safe to use after operations that can change the list's 69 // backing store (eg, Add). 70 inline T& operator[](int i) const { 71 ASSERT(0 <= i); 72 ASSERT(i < length_); 73 return data_[i]; 74 } 75 inline T& at(int i) const { return operator[](i); } 76 inline T& last() const { return at(length_ - 1); } 77 inline T& first() const { return at(0); } 78 79 INLINE(bool is_empty() const) { return length_ == 0; } 80 INLINE(int length() const) { return length_; } 81 INLINE(int capacity() const) { return capacity_; } 82 83 Vector<T> ToVector() { return Vector<T>(data_, length_); } 84 85 Vector<const T> ToConstVector() { return Vector<const T>(data_, length_); } 86 87 // Adds a copy of the given 'element' to the end of the list, 88 // expanding the list if necessary. 89 void Add(const T& element); 90 91 // Add all the elements from the argument list to this list. 92 void AddAll(const List<T, P>& other); 93 94 // Added 'count' elements with the value 'value' and returns a 95 // vector that allows access to the elements. The vector is valid 96 // until the next change is made to this list. 97 Vector<T> AddBlock(T value, int count); 98 99 // Removes the i'th element without deleting it even if T is a 100 // pointer type; moves all elements above i "down". Returns the 101 // removed element. This function's complexity is linear in the 102 // size of the list. 103 T Remove(int i); 104 105 // Removes the last element without deleting it even if T is a 106 // pointer type. Returns the removed element. 107 INLINE(T RemoveLast()) { return Remove(length_ - 1); } 108 109 // Clears the list by setting the length to zero. Even if T is a 110 // pointer type, clearing the list doesn't delete the entries. 111 INLINE(void Clear()); 112 113 // Drops all but the first 'pos' elements from the list. 114 INLINE(void Rewind(int pos)); 115 116 bool Contains(const T& elm); 117 118 // Iterate through all list entries, starting at index 0. 119 void Iterate(void (*callback)(T* x)); 120 121 // Sort all list entries (using QuickSort) 122 void Sort(int (*cmp)(const T* x, const T* y)); 123 void Sort(); 124 125 INLINE(void Initialize(int capacity)); 126 127 private: 128 T* data_; 129 int capacity_; 130 int length_; 131 132 INLINE(T* NewData(int n)) { return static_cast<T*>(P::New(n * sizeof(T))); } 133 INLINE(void DeleteData(T* data)) { P::Delete(data); } 134 135 // Increase the capacity of a full list, and add an element. 136 // List must be full already. 137 void ResizeAdd(const T& element); 138 139 // Inlined implementation of ResizeAdd, shared by inlined and 140 // non-inlined versions of ResizeAdd. 141 void ResizeAddInternal(const T& element); 142 143 // Resize the list. 144 void Resize(int new_capacity); 145 146 DISALLOW_COPY_AND_ASSIGN(List); 147 }; 148 149 class FrameElement; 150 151 // Add() is inlined, ResizeAdd() called by Add() is inlined except for 152 // Lists of FrameElements, and ResizeAddInternal() is inlined in ResizeAdd(). 153 template <> 154 void List<FrameElement, 155 FreeStoreAllocationPolicy>::ResizeAdd(const FrameElement& element); 156 157 } } // namespace v8::internal 158 159 #endif // V8_LIST_H_ 160
