]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file defines the SmallVector class. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
13 | ||
14 | #ifndef LLVM_ADT_SMALLVECTOR_H | |
15 | #define LLVM_ADT_SMALLVECTOR_H | |
16 | ||
1a4d82fc | 17 | #include "llvm/ADT/iterator_range.h" |
223e47cc LB |
18 | #include "llvm/Support/AlignOf.h" |
19 | #include "llvm/Support/Compiler.h" | |
1a4d82fc | 20 | #include "llvm/Support/MathExtras.h" |
223e47cc LB |
21 | #include "llvm/Support/type_traits.h" |
22 | #include <algorithm> | |
23 | #include <cassert> | |
24 | #include <cstddef> | |
25 | #include <cstdlib> | |
26 | #include <cstring> | |
27 | #include <iterator> | |
28 | #include <memory> | |
29 | ||
30 | namespace llvm { | |
31 | ||
1a4d82fc | 32 | /// This is all the non-templated stuff common to all SmallVectors. |
223e47cc LB |
33 | class SmallVectorBase { |
34 | protected: | |
35 | void *BeginX, *EndX, *CapacityX; | |
36 | ||
37 | protected: | |
38 | SmallVectorBase(void *FirstEl, size_t Size) | |
39 | : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {} | |
40 | ||
1a4d82fc | 41 | /// This is an implementation of the grow() method which only works |
223e47cc LB |
42 | /// on POD-like data types and is out of line to reduce code duplication. |
43 | void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize); | |
44 | ||
45 | public: | |
1a4d82fc | 46 | /// This returns size()*sizeof(T). |
223e47cc LB |
47 | size_t size_in_bytes() const { |
48 | return size_t((char*)EndX - (char*)BeginX); | |
49 | } | |
50 | ||
51 | /// capacity_in_bytes - This returns capacity()*sizeof(T). | |
52 | size_t capacity_in_bytes() const { | |
53 | return size_t((char*)CapacityX - (char*)BeginX); | |
54 | } | |
55 | ||
1a4d82fc | 56 | bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return BeginX == EndX; } |
223e47cc LB |
57 | }; |
58 | ||
59 | template <typename T, unsigned N> struct SmallVectorStorage; | |
60 | ||
1a4d82fc JJ |
61 | /// This is the part of SmallVectorTemplateBase which does not depend on whether |
62 | /// the type T is a POD. The extra dummy template argument is used by ArrayRef | |
63 | /// to avoid unnecessarily requiring T to be complete. | |
223e47cc LB |
64 | template <typename T, typename = void> |
65 | class SmallVectorTemplateCommon : public SmallVectorBase { | |
66 | private: | |
67 | template <typename, unsigned> friend struct SmallVectorStorage; | |
68 | ||
69 | // Allocate raw space for N elements of type T. If T has a ctor or dtor, we | |
70 | // don't want it to be automatically run, so we need to represent the space as | |
71 | // something else. Use an array of char of sufficient alignment. | |
72 | typedef llvm::AlignedCharArrayUnion<T> U; | |
73 | U FirstEl; | |
74 | // Space after 'FirstEl' is clobbered, do not add any instance vars after it. | |
75 | ||
76 | protected: | |
77 | SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {} | |
78 | ||
79 | void grow_pod(size_t MinSizeInBytes, size_t TSize) { | |
80 | SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize); | |
81 | } | |
82 | ||
1a4d82fc | 83 | /// Return true if this is a smallvector which has not had dynamic |
223e47cc LB |
84 | /// memory allocated for it. |
85 | bool isSmall() const { | |
86 | return BeginX == static_cast<const void*>(&FirstEl); | |
87 | } | |
88 | ||
1a4d82fc | 89 | /// Put this vector in a state of being small. |
223e47cc LB |
90 | void resetToSmall() { |
91 | BeginX = EndX = CapacityX = &FirstEl; | |
92 | } | |
93 | ||
94 | void setEnd(T *P) { this->EndX = P; } | |
95 | public: | |
96 | typedef size_t size_type; | |
97 | typedef ptrdiff_t difference_type; | |
98 | typedef T value_type; | |
99 | typedef T *iterator; | |
100 | typedef const T *const_iterator; | |
101 | ||
102 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
103 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
104 | ||
105 | typedef T &reference; | |
106 | typedef const T &const_reference; | |
107 | typedef T *pointer; | |
108 | typedef const T *const_pointer; | |
109 | ||
110 | // forward iterator creation methods. | |
111 | iterator begin() { return (iterator)this->BeginX; } | |
112 | const_iterator begin() const { return (const_iterator)this->BeginX; } | |
113 | iterator end() { return (iterator)this->EndX; } | |
114 | const_iterator end() const { return (const_iterator)this->EndX; } | |
115 | protected: | |
116 | iterator capacity_ptr() { return (iterator)this->CapacityX; } | |
117 | const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;} | |
118 | public: | |
119 | ||
120 | // reverse iterator creation methods. | |
121 | reverse_iterator rbegin() { return reverse_iterator(end()); } | |
122 | const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } | |
123 | reverse_iterator rend() { return reverse_iterator(begin()); } | |
124 | const_reverse_iterator rend() const { return const_reverse_iterator(begin());} | |
125 | ||
126 | size_type size() const { return end()-begin(); } | |
127 | size_type max_size() const { return size_type(-1) / sizeof(T); } | |
128 | ||
1a4d82fc | 129 | /// Return the total number of elements in the currently allocated buffer. |
223e47cc LB |
130 | size_t capacity() const { return capacity_ptr() - begin(); } |
131 | ||
1a4d82fc | 132 | /// Return a pointer to the vector's buffer, even if empty(). |
223e47cc | 133 | pointer data() { return pointer(begin()); } |
1a4d82fc | 134 | /// Return a pointer to the vector's buffer, even if empty(). |
223e47cc LB |
135 | const_pointer data() const { return const_pointer(begin()); } |
136 | ||
85aaf69f SL |
137 | reference operator[](size_type idx) { |
138 | assert(idx < size()); | |
223e47cc LB |
139 | return begin()[idx]; |
140 | } | |
85aaf69f SL |
141 | const_reference operator[](size_type idx) const { |
142 | assert(idx < size()); | |
223e47cc LB |
143 | return begin()[idx]; |
144 | } | |
145 | ||
146 | reference front() { | |
970d7e83 | 147 | assert(!empty()); |
223e47cc LB |
148 | return begin()[0]; |
149 | } | |
150 | const_reference front() const { | |
970d7e83 | 151 | assert(!empty()); |
223e47cc LB |
152 | return begin()[0]; |
153 | } | |
154 | ||
155 | reference back() { | |
970d7e83 | 156 | assert(!empty()); |
223e47cc LB |
157 | return end()[-1]; |
158 | } | |
159 | const_reference back() const { | |
970d7e83 | 160 | assert(!empty()); |
223e47cc LB |
161 | return end()[-1]; |
162 | } | |
163 | }; | |
164 | ||
165 | /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method | |
166 | /// implementations that are designed to work with non-POD-like T's. | |
167 | template <typename T, bool isPodLike> | |
168 | class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> { | |
169 | protected: | |
170 | SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} | |
171 | ||
172 | static void destroy_range(T *S, T *E) { | |
173 | while (S != E) { | |
174 | --E; | |
175 | E->~T(); | |
176 | } | |
177 | } | |
178 | ||
1a4d82fc | 179 | /// Use move-assignment to move the range [I, E) onto the |
223e47cc LB |
180 | /// objects starting with "Dest". This is just <memory>'s |
181 | /// std::move, but not all stdlibs actually provide that. | |
182 | template<typename It1, typename It2> | |
183 | static It2 move(It1 I, It1 E, It2 Dest) { | |
223e47cc LB |
184 | for (; I != E; ++I, ++Dest) |
185 | *Dest = ::std::move(*I); | |
186 | return Dest; | |
223e47cc LB |
187 | } |
188 | ||
1a4d82fc | 189 | /// Use move-assignment to move the range |
223e47cc LB |
190 | /// [I, E) onto the objects ending at "Dest", moving objects |
191 | /// in reverse order. This is just <algorithm>'s | |
192 | /// std::move_backward, but not all stdlibs actually provide that. | |
193 | template<typename It1, typename It2> | |
194 | static It2 move_backward(It1 I, It1 E, It2 Dest) { | |
223e47cc LB |
195 | while (I != E) |
196 | *--Dest = ::std::move(*--E); | |
197 | return Dest; | |
223e47cc LB |
198 | } |
199 | ||
1a4d82fc JJ |
200 | /// Move the range [I, E) into the uninitialized memory starting with "Dest", |
201 | /// constructing elements as needed. | |
223e47cc LB |
202 | template<typename It1, typename It2> |
203 | static void uninitialized_move(It1 I, It1 E, It2 Dest) { | |
223e47cc LB |
204 | for (; I != E; ++I, ++Dest) |
205 | ::new ((void*) &*Dest) T(::std::move(*I)); | |
223e47cc LB |
206 | } |
207 | ||
1a4d82fc JJ |
208 | /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", |
209 | /// constructing elements as needed. | |
223e47cc LB |
210 | template<typename It1, typename It2> |
211 | static void uninitialized_copy(It1 I, It1 E, It2 Dest) { | |
212 | std::uninitialized_copy(I, E, Dest); | |
213 | } | |
214 | ||
1a4d82fc JJ |
215 | /// Grow the allocated memory (without initializing new elements), doubling |
216 | /// the size of the allocated memory. Guarantees space for at least one more | |
217 | /// element, or MinSize more elements if specified. | |
223e47cc | 218 | void grow(size_t MinSize = 0); |
1a4d82fc | 219 | |
223e47cc LB |
220 | public: |
221 | void push_back(const T &Elt) { | |
1a4d82fc JJ |
222 | if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) |
223 | this->grow(); | |
224 | ::new ((void*) this->end()) T(Elt); | |
225 | this->setEnd(this->end()+1); | |
223e47cc LB |
226 | } |
227 | ||
223e47cc | 228 | void push_back(T &&Elt) { |
1a4d82fc JJ |
229 | if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) |
230 | this->grow(); | |
231 | ::new ((void*) this->end()) T(::std::move(Elt)); | |
232 | this->setEnd(this->end()+1); | |
223e47cc | 233 | } |
1a4d82fc | 234 | |
223e47cc LB |
235 | void pop_back() { |
236 | this->setEnd(this->end()-1); | |
237 | this->end()->~T(); | |
238 | } | |
85aaf69f SL |
239 | |
240 | #if LLVM_HAS_VARIADIC_TEMPLATES | |
241 | template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) { | |
242 | if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) | |
243 | this->grow(); | |
244 | ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...); | |
245 | this->setEnd(this->end() + 1); | |
246 | } | |
247 | #else | |
248 | private: | |
249 | template <typename Constructor> void emplace_back_impl(Constructor construct) { | |
250 | if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) | |
251 | this->grow(); | |
252 | construct((void *)this->end()); | |
253 | this->setEnd(this->end() + 1); | |
254 | } | |
255 | ||
256 | public: | |
257 | void emplace_back() { | |
258 | emplace_back_impl([](void *Mem) { ::new (Mem) T(); }); | |
259 | } | |
260 | template <typename T1> void emplace_back(T1 &&A1) { | |
261 | emplace_back_impl([&](void *Mem) { ::new (Mem) T(std::forward<T1>(A1)); }); | |
262 | } | |
263 | template <typename T1, typename T2> void emplace_back(T1 &&A1, T2 &&A2) { | |
264 | emplace_back_impl([&](void *Mem) { | |
265 | ::new (Mem) T(std::forward<T1>(A1), std::forward<T2>(A2)); | |
266 | }); | |
267 | } | |
268 | template <typename T1, typename T2, typename T3> | |
269 | void emplace_back(T1 &&A1, T2 &&A2, T3 &&A3) { | |
270 | T(std::forward<T1>(A1), std::forward<T2>(A2), std::forward<T3>(A3)); | |
271 | emplace_back_impl([&](void *Mem) { | |
272 | ::new (Mem) | |
273 | T(std::forward<T1>(A1), std::forward<T2>(A2), std::forward<T3>(A3)); | |
274 | }); | |
275 | } | |
276 | template <typename T1, typename T2, typename T3, typename T4> | |
277 | void emplace_back(T1 &&A1, T2 &&A2, T3 &&A3, T4 &&A4) { | |
278 | emplace_back_impl([&](void *Mem) { | |
279 | ::new (Mem) T(std::forward<T1>(A1), std::forward<T2>(A2), | |
280 | std::forward<T3>(A3), std::forward<T4>(A4)); | |
281 | }); | |
282 | } | |
283 | #endif // LLVM_HAS_VARIADIC_TEMPLATES | |
223e47cc LB |
284 | }; |
285 | ||
286 | // Define this out-of-line to dissuade the C++ compiler from inlining it. | |
287 | template <typename T, bool isPodLike> | |
288 | void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { | |
289 | size_t CurCapacity = this->capacity(); | |
290 | size_t CurSize = this->size(); | |
1a4d82fc JJ |
291 | // Always grow, even from zero. |
292 | size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2)); | |
223e47cc LB |
293 | if (NewCapacity < MinSize) |
294 | NewCapacity = MinSize; | |
295 | T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T))); | |
296 | ||
297 | // Move the elements over. | |
298 | this->uninitialized_move(this->begin(), this->end(), NewElts); | |
299 | ||
300 | // Destroy the original elements. | |
301 | destroy_range(this->begin(), this->end()); | |
302 | ||
303 | // If this wasn't grown from the inline copy, deallocate the old space. | |
304 | if (!this->isSmall()) | |
305 | free(this->begin()); | |
306 | ||
307 | this->setEnd(NewElts+CurSize); | |
308 | this->BeginX = NewElts; | |
309 | this->CapacityX = this->begin()+NewCapacity; | |
310 | } | |
311 | ||
312 | ||
313 | /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method | |
314 | /// implementations that are designed to work with POD-like T's. | |
315 | template <typename T> | |
316 | class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> { | |
317 | protected: | |
318 | SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {} | |
319 | ||
320 | // No need to do a destroy loop for POD's. | |
321 | static void destroy_range(T *, T *) {} | |
322 | ||
1a4d82fc | 323 | /// Use move-assignment to move the range [I, E) onto the |
223e47cc LB |
324 | /// objects starting with "Dest". For PODs, this is just memcpy. |
325 | template<typename It1, typename It2> | |
326 | static It2 move(It1 I, It1 E, It2 Dest) { | |
327 | return ::std::copy(I, E, Dest); | |
328 | } | |
329 | ||
1a4d82fc JJ |
330 | /// Use move-assignment to move the range [I, E) onto the objects ending at |
331 | /// "Dest", moving objects in reverse order. | |
223e47cc LB |
332 | template<typename It1, typename It2> |
333 | static It2 move_backward(It1 I, It1 E, It2 Dest) { | |
334 | return ::std::copy_backward(I, E, Dest); | |
335 | } | |
336 | ||
1a4d82fc | 337 | /// Move the range [I, E) onto the uninitialized memory |
223e47cc LB |
338 | /// starting with "Dest", constructing elements into it as needed. |
339 | template<typename It1, typename It2> | |
340 | static void uninitialized_move(It1 I, It1 E, It2 Dest) { | |
341 | // Just do a copy. | |
342 | uninitialized_copy(I, E, Dest); | |
343 | } | |
344 | ||
1a4d82fc | 345 | /// Copy the range [I, E) onto the uninitialized memory |
223e47cc LB |
346 | /// starting with "Dest", constructing elements into it as needed. |
347 | template<typename It1, typename It2> | |
348 | static void uninitialized_copy(It1 I, It1 E, It2 Dest) { | |
349 | // Arbitrary iterator types; just use the basic implementation. | |
350 | std::uninitialized_copy(I, E, Dest); | |
351 | } | |
352 | ||
1a4d82fc | 353 | /// Copy the range [I, E) onto the uninitialized memory |
223e47cc LB |
354 | /// starting with "Dest", constructing elements into it as needed. |
355 | template<typename T1, typename T2> | |
356 | static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) { | |
357 | // Use memcpy for PODs iterated by pointers (which includes SmallVector | |
358 | // iterators): std::uninitialized_copy optimizes to memmove, but we can | |
359 | // use memcpy here. | |
360 | memcpy(Dest, I, (E-I)*sizeof(T)); | |
361 | } | |
362 | ||
1a4d82fc | 363 | /// Double the size of the allocated memory, guaranteeing space for at |
223e47cc LB |
364 | /// least one more element or MinSize if specified. |
365 | void grow(size_t MinSize = 0) { | |
366 | this->grow_pod(MinSize*sizeof(T), sizeof(T)); | |
367 | } | |
368 | public: | |
369 | void push_back(const T &Elt) { | |
1a4d82fc JJ |
370 | if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) |
371 | this->grow(); | |
372 | memcpy(this->end(), &Elt, sizeof(T)); | |
373 | this->setEnd(this->end()+1); | |
223e47cc | 374 | } |
1a4d82fc | 375 | |
223e47cc LB |
376 | void pop_back() { |
377 | this->setEnd(this->end()-1); | |
378 | } | |
379 | }; | |
380 | ||
381 | ||
1a4d82fc JJ |
382 | /// This class consists of common code factored out of the SmallVector class to |
383 | /// reduce code duplication based on the SmallVector 'N' template parameter. | |
223e47cc LB |
384 | template <typename T> |
385 | class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> { | |
386 | typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass; | |
387 | ||
970d7e83 | 388 | SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION; |
223e47cc LB |
389 | public: |
390 | typedef typename SuperClass::iterator iterator; | |
391 | typedef typename SuperClass::size_type size_type; | |
392 | ||
393 | protected: | |
394 | // Default ctor - Initialize to empty. | |
395 | explicit SmallVectorImpl(unsigned N) | |
396 | : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) { | |
397 | } | |
398 | ||
399 | public: | |
400 | ~SmallVectorImpl() { | |
401 | // Destroy the constructed elements in the vector. | |
402 | this->destroy_range(this->begin(), this->end()); | |
403 | ||
404 | // If this wasn't grown from the inline copy, deallocate the old space. | |
405 | if (!this->isSmall()) | |
406 | free(this->begin()); | |
407 | } | |
408 | ||
409 | ||
410 | void clear() { | |
411 | this->destroy_range(this->begin(), this->end()); | |
412 | this->EndX = this->BeginX; | |
413 | } | |
414 | ||
85aaf69f | 415 | void resize(size_type N) { |
223e47cc LB |
416 | if (N < this->size()) { |
417 | this->destroy_range(this->begin()+N, this->end()); | |
418 | this->setEnd(this->begin()+N); | |
419 | } else if (N > this->size()) { | |
420 | if (this->capacity() < N) | |
421 | this->grow(N); | |
1a4d82fc JJ |
422 | for (auto I = this->end(), E = this->begin() + N; I != E; ++I) |
423 | new (&*I) T(); | |
223e47cc LB |
424 | this->setEnd(this->begin()+N); |
425 | } | |
426 | } | |
427 | ||
85aaf69f | 428 | void resize(size_type N, const T &NV) { |
223e47cc LB |
429 | if (N < this->size()) { |
430 | this->destroy_range(this->begin()+N, this->end()); | |
431 | this->setEnd(this->begin()+N); | |
432 | } else if (N > this->size()) { | |
433 | if (this->capacity() < N) | |
434 | this->grow(N); | |
435 | std::uninitialized_fill(this->end(), this->begin()+N, NV); | |
436 | this->setEnd(this->begin()+N); | |
437 | } | |
438 | } | |
439 | ||
85aaf69f | 440 | void reserve(size_type N) { |
223e47cc LB |
441 | if (this->capacity() < N) |
442 | this->grow(N); | |
443 | } | |
444 | ||
1a4d82fc | 445 | T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() { |
223e47cc | 446 | T Result = ::std::move(this->back()); |
223e47cc LB |
447 | this->pop_back(); |
448 | return Result; | |
449 | } | |
450 | ||
451 | void swap(SmallVectorImpl &RHS); | |
452 | ||
1a4d82fc | 453 | /// Add the specified range to the end of the SmallVector. |
223e47cc LB |
454 | template<typename in_iter> |
455 | void append(in_iter in_start, in_iter in_end) { | |
456 | size_type NumInputs = std::distance(in_start, in_end); | |
457 | // Grow allocated space if needed. | |
458 | if (NumInputs > size_type(this->capacity_ptr()-this->end())) | |
459 | this->grow(this->size()+NumInputs); | |
460 | ||
461 | // Copy the new elements over. | |
462 | // TODO: NEED To compile time dispatch on whether in_iter is a random access | |
463 | // iterator to use the fast uninitialized_copy. | |
464 | std::uninitialized_copy(in_start, in_end, this->end()); | |
465 | this->setEnd(this->end() + NumInputs); | |
466 | } | |
467 | ||
1a4d82fc | 468 | /// Add the specified range to the end of the SmallVector. |
223e47cc LB |
469 | void append(size_type NumInputs, const T &Elt) { |
470 | // Grow allocated space if needed. | |
471 | if (NumInputs > size_type(this->capacity_ptr()-this->end())) | |
472 | this->grow(this->size()+NumInputs); | |
473 | ||
474 | // Copy the new elements over. | |
475 | std::uninitialized_fill_n(this->end(), NumInputs, Elt); | |
476 | this->setEnd(this->end() + NumInputs); | |
477 | } | |
478 | ||
85aaf69f | 479 | void assign(size_type NumElts, const T &Elt) { |
223e47cc LB |
480 | clear(); |
481 | if (this->capacity() < NumElts) | |
482 | this->grow(NumElts); | |
483 | this->setEnd(this->begin()+NumElts); | |
484 | std::uninitialized_fill(this->begin(), this->end(), Elt); | |
485 | } | |
486 | ||
487 | iterator erase(iterator I) { | |
488 | assert(I >= this->begin() && "Iterator to erase is out of bounds."); | |
489 | assert(I < this->end() && "Erasing at past-the-end iterator."); | |
490 | ||
491 | iterator N = I; | |
492 | // Shift all elts down one. | |
493 | this->move(I+1, this->end(), I); | |
494 | // Drop the last elt. | |
495 | this->pop_back(); | |
496 | return(N); | |
497 | } | |
498 | ||
499 | iterator erase(iterator S, iterator E) { | |
500 | assert(S >= this->begin() && "Range to erase is out of bounds."); | |
501 | assert(S <= E && "Trying to erase invalid range."); | |
502 | assert(E <= this->end() && "Trying to erase past the end."); | |
503 | ||
504 | iterator N = S; | |
505 | // Shift all elts down. | |
506 | iterator I = this->move(E, this->end(), S); | |
507 | // Drop the last elts. | |
508 | this->destroy_range(I, this->end()); | |
509 | this->setEnd(I); | |
510 | return(N); | |
511 | } | |
512 | ||
223e47cc LB |
513 | iterator insert(iterator I, T &&Elt) { |
514 | if (I == this->end()) { // Important special case for empty vector. | |
515 | this->push_back(::std::move(Elt)); | |
516 | return this->end()-1; | |
517 | } | |
518 | ||
519 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
520 | assert(I <= this->end() && "Inserting past the end of the vector."); | |
521 | ||
1a4d82fc JJ |
522 | if (this->EndX >= this->CapacityX) { |
523 | size_t EltNo = I-this->begin(); | |
524 | this->grow(); | |
525 | I = this->begin()+EltNo; | |
526 | } | |
223e47cc | 527 | |
1a4d82fc JJ |
528 | ::new ((void*) this->end()) T(::std::move(this->back())); |
529 | // Push everything else over. | |
530 | this->move_backward(I, this->end()-1, this->end()); | |
531 | this->setEnd(this->end()+1); | |
223e47cc | 532 | |
1a4d82fc JJ |
533 | // If we just moved the element we're inserting, be sure to update |
534 | // the reference. | |
535 | T *EltPtr = &Elt; | |
536 | if (I <= EltPtr && EltPtr < this->EndX) | |
537 | ++EltPtr; | |
538 | ||
539 | *I = ::std::move(*EltPtr); | |
540 | return I; | |
223e47cc | 541 | } |
223e47cc LB |
542 | |
543 | iterator insert(iterator I, const T &Elt) { | |
544 | if (I == this->end()) { // Important special case for empty vector. | |
545 | this->push_back(Elt); | |
546 | return this->end()-1; | |
547 | } | |
548 | ||
549 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
550 | assert(I <= this->end() && "Inserting past the end of the vector."); | |
551 | ||
1a4d82fc JJ |
552 | if (this->EndX >= this->CapacityX) { |
553 | size_t EltNo = I-this->begin(); | |
554 | this->grow(); | |
555 | I = this->begin()+EltNo; | |
223e47cc | 556 | } |
1a4d82fc JJ |
557 | ::new ((void*) this->end()) T(std::move(this->back())); |
558 | // Push everything else over. | |
559 | this->move_backward(I, this->end()-1, this->end()); | |
560 | this->setEnd(this->end()+1); | |
561 | ||
562 | // If we just moved the element we're inserting, be sure to update | |
563 | // the reference. | |
564 | const T *EltPtr = &Elt; | |
565 | if (I <= EltPtr && EltPtr < this->EndX) | |
566 | ++EltPtr; | |
567 | ||
568 | *I = *EltPtr; | |
569 | return I; | |
223e47cc LB |
570 | } |
571 | ||
572 | iterator insert(iterator I, size_type NumToInsert, const T &Elt) { | |
573 | // Convert iterator to elt# to avoid invalidating iterator when we reserve() | |
574 | size_t InsertElt = I - this->begin(); | |
575 | ||
576 | if (I == this->end()) { // Important special case for empty vector. | |
577 | append(NumToInsert, Elt); | |
578 | return this->begin()+InsertElt; | |
579 | } | |
580 | ||
581 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
582 | assert(I <= this->end() && "Inserting past the end of the vector."); | |
583 | ||
584 | // Ensure there is enough space. | |
85aaf69f | 585 | reserve(this->size() + NumToInsert); |
223e47cc LB |
586 | |
587 | // Uninvalidate the iterator. | |
588 | I = this->begin()+InsertElt; | |
589 | ||
590 | // If there are more elements between the insertion point and the end of the | |
591 | // range than there are being inserted, we can use a simple approach to | |
592 | // insertion. Since we already reserved space, we know that this won't | |
593 | // reallocate the vector. | |
594 | if (size_t(this->end()-I) >= NumToInsert) { | |
595 | T *OldEnd = this->end(); | |
1a4d82fc JJ |
596 | append(std::move_iterator<iterator>(this->end() - NumToInsert), |
597 | std::move_iterator<iterator>(this->end())); | |
223e47cc LB |
598 | |
599 | // Copy the existing elements that get replaced. | |
600 | this->move_backward(I, OldEnd-NumToInsert, OldEnd); | |
601 | ||
602 | std::fill_n(I, NumToInsert, Elt); | |
603 | return I; | |
604 | } | |
605 | ||
606 | // Otherwise, we're inserting more elements than exist already, and we're | |
607 | // not inserting at the end. | |
608 | ||
609 | // Move over the elements that we're about to overwrite. | |
610 | T *OldEnd = this->end(); | |
611 | this->setEnd(this->end() + NumToInsert); | |
612 | size_t NumOverwritten = OldEnd-I; | |
613 | this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); | |
614 | ||
615 | // Replace the overwritten part. | |
616 | std::fill_n(I, NumOverwritten, Elt); | |
617 | ||
618 | // Insert the non-overwritten middle part. | |
619 | std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt); | |
620 | return I; | |
621 | } | |
622 | ||
623 | template<typename ItTy> | |
624 | iterator insert(iterator I, ItTy From, ItTy To) { | |
625 | // Convert iterator to elt# to avoid invalidating iterator when we reserve() | |
626 | size_t InsertElt = I - this->begin(); | |
627 | ||
628 | if (I == this->end()) { // Important special case for empty vector. | |
629 | append(From, To); | |
630 | return this->begin()+InsertElt; | |
631 | } | |
632 | ||
633 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
634 | assert(I <= this->end() && "Inserting past the end of the vector."); | |
635 | ||
636 | size_t NumToInsert = std::distance(From, To); | |
637 | ||
638 | // Ensure there is enough space. | |
85aaf69f | 639 | reserve(this->size() + NumToInsert); |
223e47cc LB |
640 | |
641 | // Uninvalidate the iterator. | |
642 | I = this->begin()+InsertElt; | |
643 | ||
644 | // If there are more elements between the insertion point and the end of the | |
645 | // range than there are being inserted, we can use a simple approach to | |
646 | // insertion. Since we already reserved space, we know that this won't | |
647 | // reallocate the vector. | |
648 | if (size_t(this->end()-I) >= NumToInsert) { | |
649 | T *OldEnd = this->end(); | |
1a4d82fc JJ |
650 | append(std::move_iterator<iterator>(this->end() - NumToInsert), |
651 | std::move_iterator<iterator>(this->end())); | |
223e47cc LB |
652 | |
653 | // Copy the existing elements that get replaced. | |
654 | this->move_backward(I, OldEnd-NumToInsert, OldEnd); | |
655 | ||
656 | std::copy(From, To, I); | |
657 | return I; | |
658 | } | |
659 | ||
660 | // Otherwise, we're inserting more elements than exist already, and we're | |
661 | // not inserting at the end. | |
662 | ||
663 | // Move over the elements that we're about to overwrite. | |
664 | T *OldEnd = this->end(); | |
665 | this->setEnd(this->end() + NumToInsert); | |
666 | size_t NumOverwritten = OldEnd-I; | |
667 | this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten); | |
668 | ||
669 | // Replace the overwritten part. | |
670 | for (T *J = I; NumOverwritten > 0; --NumOverwritten) { | |
671 | *J = *From; | |
672 | ++J; ++From; | |
673 | } | |
674 | ||
675 | // Insert the non-overwritten middle part. | |
676 | this->uninitialized_copy(From, To, OldEnd); | |
677 | return I; | |
678 | } | |
679 | ||
680 | SmallVectorImpl &operator=(const SmallVectorImpl &RHS); | |
681 | ||
223e47cc | 682 | SmallVectorImpl &operator=(SmallVectorImpl &&RHS); |
223e47cc LB |
683 | |
684 | bool operator==(const SmallVectorImpl &RHS) const { | |
685 | if (this->size() != RHS.size()) return false; | |
686 | return std::equal(this->begin(), this->end(), RHS.begin()); | |
687 | } | |
688 | bool operator!=(const SmallVectorImpl &RHS) const { | |
689 | return !(*this == RHS); | |
690 | } | |
691 | ||
692 | bool operator<(const SmallVectorImpl &RHS) const { | |
693 | return std::lexicographical_compare(this->begin(), this->end(), | |
694 | RHS.begin(), RHS.end()); | |
695 | } | |
696 | ||
697 | /// Set the array size to \p N, which the current array must have enough | |
698 | /// capacity for. | |
699 | /// | |
700 | /// This does not construct or destroy any elements in the vector. | |
701 | /// | |
702 | /// Clients can use this in conjunction with capacity() to write past the end | |
703 | /// of the buffer when they know that more elements are available, and only | |
704 | /// update the size later. This avoids the cost of value initializing elements | |
705 | /// which will only be overwritten. | |
85aaf69f | 706 | void set_size(size_type N) { |
223e47cc LB |
707 | assert(N <= this->capacity()); |
708 | this->setEnd(this->begin() + N); | |
709 | } | |
710 | }; | |
711 | ||
712 | ||
713 | template <typename T> | |
714 | void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) { | |
715 | if (this == &RHS) return; | |
716 | ||
717 | // We can only avoid copying elements if neither vector is small. | |
718 | if (!this->isSmall() && !RHS.isSmall()) { | |
719 | std::swap(this->BeginX, RHS.BeginX); | |
720 | std::swap(this->EndX, RHS.EndX); | |
721 | std::swap(this->CapacityX, RHS.CapacityX); | |
722 | return; | |
723 | } | |
724 | if (RHS.size() > this->capacity()) | |
725 | this->grow(RHS.size()); | |
726 | if (this->size() > RHS.capacity()) | |
727 | RHS.grow(this->size()); | |
728 | ||
729 | // Swap the shared elements. | |
730 | size_t NumShared = this->size(); | |
731 | if (NumShared > RHS.size()) NumShared = RHS.size(); | |
85aaf69f | 732 | for (size_type i = 0; i != NumShared; ++i) |
223e47cc LB |
733 | std::swap((*this)[i], RHS[i]); |
734 | ||
735 | // Copy over the extra elts. | |
736 | if (this->size() > RHS.size()) { | |
737 | size_t EltDiff = this->size() - RHS.size(); | |
738 | this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end()); | |
739 | RHS.setEnd(RHS.end()+EltDiff); | |
740 | this->destroy_range(this->begin()+NumShared, this->end()); | |
741 | this->setEnd(this->begin()+NumShared); | |
742 | } else if (RHS.size() > this->size()) { | |
743 | size_t EltDiff = RHS.size() - this->size(); | |
744 | this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end()); | |
745 | this->setEnd(this->end() + EltDiff); | |
746 | this->destroy_range(RHS.begin()+NumShared, RHS.end()); | |
747 | RHS.setEnd(RHS.begin()+NumShared); | |
748 | } | |
749 | } | |
750 | ||
751 | template <typename T> | |
752 | SmallVectorImpl<T> &SmallVectorImpl<T>:: | |
753 | operator=(const SmallVectorImpl<T> &RHS) { | |
754 | // Avoid self-assignment. | |
755 | if (this == &RHS) return *this; | |
756 | ||
757 | // If we already have sufficient space, assign the common elements, then | |
758 | // destroy any excess. | |
759 | size_t RHSSize = RHS.size(); | |
760 | size_t CurSize = this->size(); | |
761 | if (CurSize >= RHSSize) { | |
762 | // Assign common elements. | |
763 | iterator NewEnd; | |
764 | if (RHSSize) | |
765 | NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin()); | |
766 | else | |
767 | NewEnd = this->begin(); | |
768 | ||
769 | // Destroy excess elements. | |
770 | this->destroy_range(NewEnd, this->end()); | |
771 | ||
772 | // Trim. | |
773 | this->setEnd(NewEnd); | |
774 | return *this; | |
775 | } | |
776 | ||
777 | // If we have to grow to have enough elements, destroy the current elements. | |
778 | // This allows us to avoid copying them during the grow. | |
779 | // FIXME: don't do this if they're efficiently moveable. | |
780 | if (this->capacity() < RHSSize) { | |
781 | // Destroy current elements. | |
782 | this->destroy_range(this->begin(), this->end()); | |
783 | this->setEnd(this->begin()); | |
784 | CurSize = 0; | |
785 | this->grow(RHSSize); | |
786 | } else if (CurSize) { | |
787 | // Otherwise, use assignment for the already-constructed elements. | |
788 | std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin()); | |
789 | } | |
790 | ||
791 | // Copy construct the new elements in place. | |
792 | this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(), | |
793 | this->begin()+CurSize); | |
794 | ||
795 | // Set end. | |
796 | this->setEnd(this->begin()+RHSSize); | |
797 | return *this; | |
798 | } | |
799 | ||
223e47cc LB |
800 | template <typename T> |
801 | SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { | |
802 | // Avoid self-assignment. | |
803 | if (this == &RHS) return *this; | |
804 | ||
805 | // If the RHS isn't small, clear this vector and then steal its buffer. | |
806 | if (!RHS.isSmall()) { | |
807 | this->destroy_range(this->begin(), this->end()); | |
808 | if (!this->isSmall()) free(this->begin()); | |
809 | this->BeginX = RHS.BeginX; | |
810 | this->EndX = RHS.EndX; | |
811 | this->CapacityX = RHS.CapacityX; | |
812 | RHS.resetToSmall(); | |
813 | return *this; | |
814 | } | |
815 | ||
816 | // If we already have sufficient space, assign the common elements, then | |
817 | // destroy any excess. | |
818 | size_t RHSSize = RHS.size(); | |
819 | size_t CurSize = this->size(); | |
820 | if (CurSize >= RHSSize) { | |
821 | // Assign common elements. | |
822 | iterator NewEnd = this->begin(); | |
823 | if (RHSSize) | |
824 | NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd); | |
825 | ||
826 | // Destroy excess elements and trim the bounds. | |
827 | this->destroy_range(NewEnd, this->end()); | |
828 | this->setEnd(NewEnd); | |
829 | ||
830 | // Clear the RHS. | |
831 | RHS.clear(); | |
832 | ||
833 | return *this; | |
834 | } | |
835 | ||
836 | // If we have to grow to have enough elements, destroy the current elements. | |
837 | // This allows us to avoid copying them during the grow. | |
838 | // FIXME: this may not actually make any sense if we can efficiently move | |
839 | // elements. | |
840 | if (this->capacity() < RHSSize) { | |
841 | // Destroy current elements. | |
842 | this->destroy_range(this->begin(), this->end()); | |
843 | this->setEnd(this->begin()); | |
844 | CurSize = 0; | |
845 | this->grow(RHSSize); | |
846 | } else if (CurSize) { | |
847 | // Otherwise, use assignment for the already-constructed elements. | |
1a4d82fc | 848 | this->move(RHS.begin(), RHS.begin()+CurSize, this->begin()); |
223e47cc LB |
849 | } |
850 | ||
851 | // Move-construct the new elements in place. | |
852 | this->uninitialized_move(RHS.begin()+CurSize, RHS.end(), | |
853 | this->begin()+CurSize); | |
854 | ||
855 | // Set end. | |
856 | this->setEnd(this->begin()+RHSSize); | |
857 | ||
858 | RHS.clear(); | |
859 | return *this; | |
860 | } | |
223e47cc LB |
861 | |
862 | /// Storage for the SmallVector elements which aren't contained in | |
863 | /// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1' | |
864 | /// element is in the base class. This is specialized for the N=1 and N=0 cases | |
865 | /// to avoid allocating unnecessary storage. | |
866 | template <typename T, unsigned N> | |
867 | struct SmallVectorStorage { | |
868 | typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1]; | |
869 | }; | |
870 | template <typename T> struct SmallVectorStorage<T, 1> {}; | |
871 | template <typename T> struct SmallVectorStorage<T, 0> {}; | |
872 | ||
1a4d82fc | 873 | /// This is a 'vector' (really, a variable-sized array), optimized |
223e47cc LB |
874 | /// for the case when the array is small. It contains some number of elements |
875 | /// in-place, which allows it to avoid heap allocation when the actual number of | |
876 | /// elements is below that threshold. This allows normal "small" cases to be | |
877 | /// fast without losing generality for large inputs. | |
878 | /// | |
879 | /// Note that this does not attempt to be exception safe. | |
880 | /// | |
881 | template <typename T, unsigned N> | |
882 | class SmallVector : public SmallVectorImpl<T> { | |
1a4d82fc | 883 | /// Inline space for elements which aren't stored in the base class. |
223e47cc LB |
884 | SmallVectorStorage<T, N> Storage; |
885 | public: | |
886 | SmallVector() : SmallVectorImpl<T>(N) { | |
887 | } | |
888 | ||
85aaf69f | 889 | explicit SmallVector(size_t Size, const T &Value = T()) |
223e47cc LB |
890 | : SmallVectorImpl<T>(N) { |
891 | this->assign(Size, Value); | |
892 | } | |
893 | ||
894 | template<typename ItTy> | |
895 | SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) { | |
896 | this->append(S, E); | |
897 | } | |
898 | ||
1a4d82fc JJ |
899 | template <typename RangeTy> |
900 | explicit SmallVector(const llvm::iterator_range<RangeTy> R) | |
901 | : SmallVectorImpl<T>(N) { | |
902 | this->append(R.begin(), R.end()); | |
903 | } | |
904 | ||
223e47cc LB |
905 | SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) { |
906 | if (!RHS.empty()) | |
907 | SmallVectorImpl<T>::operator=(RHS); | |
908 | } | |
909 | ||
910 | const SmallVector &operator=(const SmallVector &RHS) { | |
911 | SmallVectorImpl<T>::operator=(RHS); | |
912 | return *this; | |
913 | } | |
914 | ||
223e47cc LB |
915 | SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) { |
916 | if (!RHS.empty()) | |
917 | SmallVectorImpl<T>::operator=(::std::move(RHS)); | |
918 | } | |
919 | ||
920 | const SmallVector &operator=(SmallVector &&RHS) { | |
921 | SmallVectorImpl<T>::operator=(::std::move(RHS)); | |
922 | return *this; | |
923 | } | |
223e47cc LB |
924 | }; |
925 | ||
926 | template<typename T, unsigned N> | |
927 | static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) { | |
928 | return X.capacity_in_bytes(); | |
929 | } | |
930 | ||
931 | } // End llvm namespace | |
932 | ||
933 | namespace std { | |
934 | /// Implement std::swap in terms of SmallVector swap. | |
935 | template<typename T> | |
936 | inline void | |
937 | swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) { | |
938 | LHS.swap(RHS); | |
939 | } | |
940 | ||
941 | /// Implement std::swap in terms of SmallVector swap. | |
942 | template<typename T, unsigned N> | |
943 | inline void | |
944 | swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) { | |
945 | LHS.swap(RHS); | |
946 | } | |
947 | } | |
948 | ||
949 | #endif |