1 // Copyright 2011 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_LIST_H_ 6 #define V8_LIST_H_ 7 8 #include <algorithm> 9 10 #include "src/checks.h" 11 #include "src/vector.h" 12 13 namespace v8 { 14 namespace internal { 15 16 template<typename T> class Vector; 17 18 // ---------------------------------------------------------------------------- 19 // The list is a template for very light-weight lists. We are not 20 // using the STL because we want full control over space and speed of 21 // the code. This implementation is based on code by Robert Griesemer 22 // and Rob Pike. 23 // 24 // The list is parameterized by the type of its elements (T) and by an 25 // allocation policy (P). The policy is used for allocating lists in 26 // the C free store or the zone; see zone.h. 27 28 // Forward defined as 29 // template <typename T, 30 // class AllocationPolicy = FreeStoreAllocationPolicy> class List; 31 template <typename T, class AllocationPolicy> 32 class List { 33 public: 34 explicit List(AllocationPolicy allocator = AllocationPolicy()) { 35 Initialize(0, allocator); 36 } 37 INLINE(explicit List(int capacity, 38 AllocationPolicy allocator = AllocationPolicy())) { 39 Initialize(capacity, allocator); 40 } 41 INLINE(~List()) { DeleteData(data_); } 42 43 // Deallocates memory used by the list and leaves the list in a consistent 44 // empty state. 45 void Free() { 46 DeleteData(data_); 47 Initialize(0); 48 } 49 50 INLINE(void* operator new(size_t size, 51 AllocationPolicy allocator = AllocationPolicy())) { 52 return allocator.New(static_cast<int>(size)); 53 } 54 INLINE(void operator delete(void* p)) { 55 AllocationPolicy::Delete(p); 56 } 57 58 // Please the MSVC compiler. We should never have to execute this. 59 INLINE(void operator delete(void* p, AllocationPolicy allocator)) { 60 UNREACHABLE(); 61 } 62 63 // Returns a reference to the element at index i. This reference is 64 // not safe to use after operations that can change the list's 65 // backing store (e.g. Add). 66 inline T& operator[](int i) const { 67 DCHECK_LE(0, i); 68 DCHECK_GT(static_cast<unsigned>(length_), static_cast<unsigned>(i)); 69 return data_[i]; 70 } 71 inline T& at(int i) const { return operator[](i); } 72 inline T& last() const { return at(length_ - 1); } 73 inline T& first() const { return at(0); } 74 75 typedef T* iterator; 76 inline iterator begin() const { return &data_[0]; } 77 inline iterator end() const { return &data_[length_]; } 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() const { return Vector<T>(data_, length_); } 84 85 Vector<const T> ToConstVector() const { 86 return Vector<const T>(data_, length_); 87 } 88 89 // Adds a copy of the given 'element' to the end of the list, 90 // expanding the list if necessary. 91 void Add(const T& element, AllocationPolicy allocator = AllocationPolicy()); 92 93 // Add all the elements from the argument list to this list. 94 void AddAll(const List<T, AllocationPolicy>& other, 95 AllocationPolicy allocator = AllocationPolicy()); 96 97 // Add all the elements from the vector to this list. 98 void AddAll(const Vector<T>& other, 99 AllocationPolicy allocator = AllocationPolicy()); 100 101 // Inserts the element at the specific index. 102 void InsertAt(int index, const T& element, 103 AllocationPolicy allocator = AllocationPolicy()); 104 105 // Overwrites the element at the specific index. 106 void Set(int index, const T& element); 107 108 // Added 'count' elements with the value 'value' and returns a 109 // vector that allows access to the elements. The vector is valid 110 // until the next change is made to this list. 111 Vector<T> AddBlock(T value, int count, 112 AllocationPolicy allocator = AllocationPolicy()); 113 114 // Removes the i'th element without deleting it even if T is a 115 // pointer type; moves all elements above i "down". Returns the 116 // removed element. This function's complexity is linear in the 117 // size of the list. 118 T Remove(int i); 119 120 // Remove the given element from the list. Returns whether or not 121 // the input is included in the list in the first place. 122 bool RemoveElement(const T& elm); 123 124 // Removes the last element without deleting it even if T is a 125 // pointer type. Returns the removed element. 126 INLINE(T RemoveLast()) { return Remove(length_ - 1); } 127 128 // Deletes current list contents and allocates space for 'length' elements. 129 INLINE(void Allocate(int length, 130 AllocationPolicy allocator = AllocationPolicy())); 131 132 // Clears the list by freeing the storage memory. If you want to keep the 133 // memory, use Rewind(0) instead. Be aware, that even if T is a 134 // pointer type, clearing the list doesn't delete the entries. 135 INLINE(void Clear()); 136 137 // Drops all but the first 'pos' elements from the list. 138 INLINE(void Rewind(int pos)); 139 140 // Drop the last 'count' elements from the list. 141 INLINE(void RewindBy(int count)) { Rewind(length_ - count); } 142 143 // Swaps the contents of the two lists. 144 INLINE(void Swap(List<T, AllocationPolicy>* list)); 145 146 // Halve the capacity if fill level is less than a quarter. 147 INLINE(void Trim(AllocationPolicy allocator = AllocationPolicy())); 148 149 bool Contains(const T& elm) const; 150 int CountOccurrences(const T& elm, int start, int end) const; 151 152 // Iterate through all list entries, starting at index 0. 153 void Iterate(void (*callback)(T* x)); 154 template<class Visitor> 155 void Iterate(Visitor* visitor); 156 157 // Sort all list entries (using QuickSort) 158 template <typename CompareFunction> 159 void Sort(CompareFunction cmp, size_t start, size_t length); 160 template <typename CompareFunction> 161 void Sort(CompareFunction cmp); 162 void Sort(); 163 template <typename CompareFunction> 164 void StableSort(CompareFunction cmp, size_t start, size_t length); 165 template <typename CompareFunction> 166 void StableSort(CompareFunction cmp); 167 void StableSort(); 168 169 INLINE(void Initialize(int capacity, 170 AllocationPolicy allocator = AllocationPolicy())) { 171 DCHECK(capacity >= 0); 172 data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL; 173 capacity_ = capacity; 174 length_ = 0; 175 } 176 177 private: 178 T* data_; 179 int capacity_; 180 int length_; 181 182 INLINE(T* NewData(int n, AllocationPolicy allocator)) { 183 return static_cast<T*>(allocator.New(n * sizeof(T))); 184 } 185 INLINE(void DeleteData(T* data)) { 186 AllocationPolicy::Delete(data); 187 } 188 189 // Increase the capacity of a full list, and add an element. 190 // List must be full already. 191 void ResizeAdd(const T& element, AllocationPolicy allocator); 192 193 // Inlined implementation of ResizeAdd, shared by inlined and 194 // non-inlined versions of ResizeAdd. 195 void ResizeAddInternal(const T& element, AllocationPolicy allocator); 196 197 // Resize the list. 198 void Resize(int new_capacity, AllocationPolicy allocator); 199 200 DISALLOW_COPY_AND_ASSIGN(List); 201 }; 202 203 204 template<typename T, class P> 205 size_t GetMemoryUsedByList(const List<T, P>& list) { 206 return list.length() * sizeof(T) + sizeof(list); 207 } 208 209 210 class Map; 211 class FieldType; 212 class Code; 213 template<typename T> class Handle; 214 typedef List<Map*> MapList; 215 typedef List<Code*> CodeList; 216 typedef List<Handle<Map> > MapHandleList; 217 typedef List<Handle<FieldType> > TypeHandleList; 218 typedef List<Handle<Code> > CodeHandleList; 219 220 // Perform binary search for an element in an already sorted 221 // list. Returns the index of the element of -1 if it was not found. 222 // |cmp| is a predicate that takes a pointer to an element of the List 223 // and returns +1 if it is greater, -1 if it is less than the element 224 // being searched. 225 template <typename T, class P> 226 int SortedListBSearch(const List<T>& list, P cmp); 227 template <typename T> 228 int SortedListBSearch(const List<T>& list, T elem); 229 230 231 } // namespace internal 232 } // namespace v8 233 234 235 #endif // V8_LIST_H_ 236
