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/utils.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(0 <= i); 68 SLOW_DCHECK(static_cast<unsigned>(i) < static_cast<unsigned>(length_)); 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 setting the length to zero. Even if T is a 133 // pointer type, clearing the list doesn't delete the entries. 134 INLINE(void Clear()); 135 136 // Drops all but the first 'pos' elements from the list. 137 INLINE(void Rewind(int pos)); 138 139 // Drop the last 'count' elements from the list. 140 INLINE(void RewindBy(int count)) { Rewind(length_ - count); } 141 142 // Swaps the contents of the two lists. 143 INLINE(void Swap(List<T, AllocationPolicy>* list)); 144 145 // Halve the capacity if fill level is less than a quarter. 146 INLINE(void Trim(AllocationPolicy allocator = AllocationPolicy())); 147 148 bool Contains(const T& elm) const; 149 int CountOccurrences(const T& elm, int start, int end) const; 150 151 // Iterate through all list entries, starting at index 0. 152 void Iterate(void (*callback)(T* x)); 153 template<class Visitor> 154 void Iterate(Visitor* visitor); 155 156 // Sort all list entries (using QuickSort) 157 template <typename CompareFunction> 158 void Sort(CompareFunction cmp, size_t start, size_t length); 159 template <typename CompareFunction> 160 void Sort(CompareFunction cmp); 161 void Sort(); 162 template <typename CompareFunction> 163 void StableSort(CompareFunction cmp, size_t start, size_t length); 164 template <typename CompareFunction> 165 void StableSort(CompareFunction cmp); 166 void StableSort(); 167 168 INLINE(void Initialize(int capacity, 169 AllocationPolicy allocator = AllocationPolicy())) { 170 DCHECK(capacity >= 0); 171 data_ = (capacity > 0) ? NewData(capacity, allocator) : NULL; 172 capacity_ = capacity; 173 length_ = 0; 174 } 175 176 private: 177 T* data_; 178 int capacity_; 179 int length_; 180 181 INLINE(T* NewData(int n, AllocationPolicy allocator)) { 182 return static_cast<T*>(allocator.New(n * sizeof(T))); 183 } 184 INLINE(void DeleteData(T* data)) { 185 AllocationPolicy::Delete(data); 186 } 187 188 // Increase the capacity of a full list, and add an element. 189 // List must be full already. 190 void ResizeAdd(const T& element, AllocationPolicy allocator); 191 192 // Inlined implementation of ResizeAdd, shared by inlined and 193 // non-inlined versions of ResizeAdd. 194 void ResizeAddInternal(const T& element, AllocationPolicy allocator); 195 196 // Resize the list. 197 void Resize(int new_capacity, AllocationPolicy allocator); 198 199 DISALLOW_COPY_AND_ASSIGN(List); 200 }; 201 202 203 template<typename T, class P> 204 size_t GetMemoryUsedByList(const List<T, P>& list) { 205 return list.length() * sizeof(T) + sizeof(list); 206 } 207 208 209 class Map; 210 class FieldType; 211 class Code; 212 template<typename T> class Handle; 213 typedef List<Map*> MapList; 214 typedef List<Code*> CodeList; 215 typedef List<Handle<Map> > MapHandleList; 216 typedef List<Handle<FieldType> > TypeHandleList; 217 typedef List<Handle<Code> > CodeHandleList; 218 219 // Perform binary search for an element in an already sorted 220 // list. Returns the index of the element of -1 if it was not found. 221 // |cmp| is a predicate that takes a pointer to an element of the List 222 // and returns +1 if it is greater, -1 if it is less than the element 223 // being searched. 224 template <typename T, class P> 225 int SortedListBSearch(const List<T>& list, P cmp); 226 template <typename T> 227 int SortedListBSearch(const List<T>& list, T elem); 228 229 230 } // namespace internal 231 } // namespace v8 232 233 234 #endif // V8_LIST_H_ 235
