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.
10 #include "src/checks.h"
11 #include "src/utils.h"
16 template<typename T> class Vector;
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
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.
29 // template <typename T,
30 // class AllocationPolicy = FreeStoreAllocationPolicy> class List;
31 template <typename T, class AllocationPolicy>
34 explicit List(AllocationPolicy allocator = AllocationPolicy()) {
35 Initialize(0, allocator);
37 INLINE(explicit List(int capacity,
38 AllocationPolicy allocator = AllocationPolicy())) {
39 Initialize(capacity, allocator);
41 INLINE(~List()) { DeleteData(data_); }
43 // Deallocates memory used by the list and leaves the list in a consistent
50 INLINE(void* operator new(size_t size,
51 AllocationPolicy allocator = AllocationPolicy())) {
52 return allocator.New(static_cast<int>(size));
54 INLINE(void operator delete(void* p)) {
55 AllocationPolicy::Delete(p);
58 // Please the MSVC compiler. We should never have to execute this.
59 INLINE(void operator delete(void* p, AllocationPolicy allocator)) {
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 {
68 SLOW_DCHECK(static_cast<unsigned>(i) < static_cast<unsigned>(length_));
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); }
76 inline iterator begin() const { return &data_[0]; }
77 inline iterator end() const { return &data_[length_]; }
79 INLINE(bool is_empty() const) { return length_ == 0; }
80 INLINE(int length() const) { return length_; }
81 INLINE(int capacity() const) { return capacity_; }
83 Vector<T> ToVector() const { return Vector<T>(data_, length_); }
85 Vector<const T> ToConstVector() const {
86 return Vector<const T>(data_, length_);
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());
93 // Add all the elements from the argument list to this list.
94 void AddAll(const List<T, AllocationPolicy>& other,
95 AllocationPolicy allocator = AllocationPolicy());
97 // Add all the elements from the vector to this list.
98 void AddAll(const Vector<T>& other,
99 AllocationPolicy allocator = AllocationPolicy());
101 // Inserts the element at the specific index.
102 void InsertAt(int index, const T& element,
103 AllocationPolicy allocator = AllocationPolicy());
105 // Overwrites the element at the specific index.
106 void Set(int index, const T& element);
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());
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
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);
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); }
128 // Deletes current list contents and allocates space for 'length' elements.
129 INLINE(void Allocate(int length,
130 AllocationPolicy allocator = AllocationPolicy()));
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());
136 // Drops all but the first 'pos' elements from the list.
137 INLINE(void Rewind(int pos));
139 // Drop the last 'count' elements from the list.
140 INLINE(void RewindBy(int count)) { Rewind(length_ - count); }
142 // Swaps the contents of the two lists.
143 INLINE(void Swap(List<T, AllocationPolicy>* list));
145 // Halve the capacity if fill level is less than a quarter.
146 INLINE(void Trim(AllocationPolicy allocator = AllocationPolicy()));
148 bool Contains(const T& elm) const;
149 int CountOccurrences(const T& elm, int start, int end) const;
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);
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);
162 template <typename CompareFunction>
163 void StableSort(CompareFunction cmp, size_t start, size_t length);
164 template <typename CompareFunction>
165 void StableSort(CompareFunction cmp);
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;
181 INLINE(T* NewData(int n, AllocationPolicy allocator)) {
182 return static_cast<T*>(allocator.New(n * sizeof(T)));
184 INLINE(void DeleteData(T* data)) {
185 AllocationPolicy::Delete(data);
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);
192 // Inlined implementation of ResizeAdd, shared by inlined and
193 // non-inlined versions of ResizeAdd.
194 void ResizeAddInternal(const T& element, AllocationPolicy allocator);
197 void Resize(int new_capacity, AllocationPolicy allocator);
199 DISALLOW_COPY_AND_ASSIGN(List);
203 template<typename T, class P>
204 size_t GetMemoryUsedByList(const List<T, P>& list) {
205 return list.length() * sizeof(T) + sizeof(list);
210 template<class> class TypeImpl;
211 struct HeapTypeConfig;
212 typedef TypeImpl<HeapTypeConfig> HeapType;
214 template<typename T> class Handle;
215 typedef List<Map*> MapList;
216 typedef List<Code*> CodeList;
217 typedef List<Handle<Map> > MapHandleList;
218 typedef List<Handle<HeapType> > TypeHandleList;
219 typedef List<Handle<Code> > CodeHandleList;
221 // Perform binary search for an element in an already sorted
222 // list. Returns the index of the element of -1 if it was not found.
223 // |cmp| is a predicate that takes a pointer to an element of the List
224 // and returns +1 if it is greater, -1 if it is less than the element
226 template <typename T, class P>
227 int SortedListBSearch(const List<T>& list, P cmp);
228 template <typename T>
229 int SortedListBSearch(const List<T>& list, T elem);
232 } // namespace internal