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