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