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