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/// \file
10/// This file defines the SmallVector class.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_SMALLVECTOR_H
15#define LLVM_ADT_SMALLVECTOR_H
16
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/type_traits.h"
19#include <algorithm>
20#include <cassert>
21#include <cstddef>
22#include <cstdlib>
23#include <cstring>
24#include <functional>
25#include <initializer_list>
26#include <iterator>
27#include <limits>
28#include <memory>
29#include <new>
30#include <type_traits>
31#include <utility>
32
33namespace llvm {
34
35template <typename T> class ArrayRef;
36
37template <typename IteratorT> class iterator_range;
38
39template <class Iterator>
40using EnableIfConvertibleToInputIterator = std::enable_if_t<std::is_convertible<
41 typename std::iterator_traits<Iterator>::iterator_category,
42 std::input_iterator_tag>::value>;
43
44/// This is all the stuff common to all SmallVectors.
45///
46/// The template parameter specifies the type which should be used to hold the
47/// Size and Capacity of the SmallVector, so it can be adjusted.
48/// Using 32 bit size is desirable to shrink the size of the SmallVector.
49/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
50/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
51/// buffering bitcode output - which can exceed 4GB.
52template <class Size_T> class SmallVectorBase {
53protected:
54 void *BeginX;
55 Size_T Size = 0, Capacity;
56
57 /// The maximum value of the Size_T used.
58 static constexpr size_t SizeTypeMax() {
59 return std::numeric_limits<Size_T>::max();
60 }
61
62 SmallVectorBase() = delete;
63 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
64 : BeginX(FirstEl), Capacity(TotalCapacity) {}
65
66 /// This is a helper for \a grow() that's out of line to reduce code
67 /// duplication. This function will report a fatal error if it can't grow at
68 /// least to \p MinSize.
69 void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
70
71 /// This is an implementation of the grow() method which only works
72 /// on POD-like data types and is out of line to reduce code duplication.
73 /// This function will report a fatal error if it cannot increase capacity.
74 void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
75
76public:
77 size_t size() const { return Size; }
78 size_t capacity() const { return Capacity; }
79
80 [[nodiscard]] bool empty() const { return !Size; }
81
82protected:
83 /// Set the array size to \p N, which the current array must have enough
84 /// capacity for.
85 ///
86 /// This does not construct or destroy any elements in the vector.
87 void set_size(size_t N) {
88 assert(N <= capacity());
89 Size = N;
90 }
91};
92
93template <class T>
94using SmallVectorSizeType =
95 std::conditional_t<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
96 uint32_t>;
97
98/// Figure out the offset of the first element.
99template <class T, typename = void> struct SmallVectorAlignmentAndSize {
100 alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
101 SmallVectorBase<SmallVectorSizeType<T>>)];
102 alignas(T) char FirstEl[sizeof(T)];
103};
104
105/// This is the part of SmallVectorTemplateBase which does not depend on whether
106/// the type T is a POD. The extra dummy template argument is used by ArrayRef
107/// to avoid unnecessarily requiring T to be complete.
108template <typename T, typename = void>
109class SmallVectorTemplateCommon
110 : public SmallVectorBase<SmallVectorSizeType<T>> {
111 using Base = SmallVectorBase<SmallVectorSizeType<T>>;
112
113 /// Find the address of the first element. For this pointer math to be valid
114 /// with small-size of 0 for T with lots of alignment, it's important that
115 /// SmallVectorStorage is properly-aligned even for small-size of 0.
116 void *getFirstEl() const {
117 return const_cast<void *>(reinterpret_cast<const void *>(
118 reinterpret_cast<const char *>(this) +
119 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
120 }
121 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
122
123protected:
124 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
125
126 void grow_pod(size_t MinSize, size_t TSize) {
127 Base::grow_pod(getFirstEl(), MinSize, TSize);
128 }
129
130 /// Return true if this is a smallvector which has not had dynamic
131 /// memory allocated for it.
132 bool isSmall() const { return this->BeginX == getFirstEl(); }
133
134 /// Put this vector in a state of being small.
135 void resetToSmall() {
136 this->BeginX = getFirstEl();
137 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
138 }
139
140 /// Return true if V is an internal reference to the given range.
141 bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
142 // Use std::less to avoid UB.
143 std::less<> LessThan;
144 return !LessThan(V, First) && LessThan(V, Last);
145 }
146
147 /// Return true if V is an internal reference to this vector.
148 bool isReferenceToStorage(const void *V) const {
149 return isReferenceToRange(V, this->begin(), this->end());
150 }
151
152 /// Return true if First and Last form a valid (possibly empty) range in this
153 /// vector's storage.
154 bool isRangeInStorage(const void *First, const void *Last) const {
155 // Use std::less to avoid UB.
156 std::less<> LessThan;
157 return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
158 !LessThan(this->end(), Last);
159 }
160
161 /// Return true unless Elt will be invalidated by resizing the vector to
162 /// NewSize.
163 bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
164 // Past the end.
165 if (LLVM_LIKELY(!isReferenceToStorage(Elt)))
166 return true;
167
168 // Return false if Elt will be destroyed by shrinking.
169 if (NewSize <= this->size())
170 return Elt < this->begin() + NewSize;
171
172 // Return false if we need to grow.
173 return NewSize <= this->capacity();
174 }
175
176 /// Check whether Elt will be invalidated by resizing the vector to NewSize.
177 void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
178 assert(isSafeToReferenceAfterResize(Elt, NewSize) &&
179 "Attempting to reference an element of the vector in an operation "
180 "that invalidates it");
181 }
182
183 /// Check whether Elt will be invalidated by increasing the size of the
184 /// vector by N.
185 void assertSafeToAdd(const void *Elt, size_t N = 1) {
186 this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
187 }
188
189 /// Check whether any part of the range will be invalidated by clearing.
190 void assertSafeToReferenceAfterClear(const T *From, const T *To) {
191 if (From == To)
192 return;
193 this->assertSafeToReferenceAfterResize(From, 0);
194 this->assertSafeToReferenceAfterResize(To - 1, 0);
195 }
196 template <
197 class ItTy,
198 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
199 bool> = false>
200 void assertSafeToReferenceAfterClear(ItTy, ItTy) {}
201
202 /// Check whether any part of the range will be invalidated by growing.
203 void assertSafeToAddRange(const T *From, const T *To) {
204 if (From == To)
205 return;
206 this->assertSafeToAdd(From, To - From);
207 this->assertSafeToAdd(To - 1, To - From);
208 }
209 template <
210 class ItTy,
211 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
212 bool> = false>
213 void assertSafeToAddRange(ItTy, ItTy) {}
214
215 /// Reserve enough space to add one element, and return the updated element
216 /// pointer in case it was a reference to the storage.
217 template <class U>
218 static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
219 size_t N) {
220 size_t NewSize = This->size() + N;
221 if (LLVM_LIKELY(NewSize <= This->capacity()))
222 return &Elt;
223
224 bool ReferencesStorage = false;
225 int64_t Index = -1;
226 if (!U::TakesParamByValue) {
227 if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
228 ReferencesStorage = true;
229 Index = &Elt - This->begin();
230 }
231 }
232 This->grow(NewSize);
233 return ReferencesStorage ? This->begin() + Index : &Elt;
234 }
235
236public:
237 using size_type = size_t;
238 using difference_type = ptrdiff_t;
239 using value_type = T;
240 using iterator = T *;
241 using const_iterator = const T *;
242
243 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
244 using reverse_iterator = std::reverse_iterator<iterator>;
245
246 using reference = T &;
247 using const_reference = const T &;
248 using pointer = T *;
249 using const_pointer = const T *;
250
251 using Base::capacity;
252 using Base::empty;
253 using Base::size;
254
255 // forward iterator creation methods.
256 iterator begin() { return (iterator)this->BeginX; }
257 const_iterator begin() const { return (const_iterator)this->BeginX; }
258 iterator end() { return begin() + size(); }
259 const_iterator end() const { return begin() + size(); }
260
261 // reverse iterator creation methods.
262 reverse_iterator rbegin() { return reverse_iterator(end()); }
263 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
264 reverse_iterator rend() { return reverse_iterator(begin()); }
265 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
266
267 size_type size_in_bytes() const { return size() * sizeof(T); }
268 size_type max_size() const {
269 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
270 }
271
272 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
273
274 /// Return a pointer to the vector's buffer, even if empty().
275 pointer data() { return pointer(begin()); }
276 /// Return a pointer to the vector's buffer, even if empty().
277 const_pointer data() const { return const_pointer(begin()); }
278
279 reference operator[](size_type idx) {
280 assert(idx < size());
281 return begin()[idx];
282 }
283 const_reference operator[](size_type idx) const {
284 assert(idx < size());
285 return begin()[idx];
286 }
287
288 reference front() {
289 assert(!empty());
290 return begin()[0];
291 }
292 const_reference front() const {
293 assert(!empty());
294 return begin()[0];
295 }
296
297 reference back() {
298 assert(!empty());
299 return end()[-1];
300 }
301 const_reference back() const {
302 assert(!empty());
303 return end()[-1];
304 }
305};
306
307/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
308/// method implementations that are designed to work with non-trivial T's.
309///
310/// We approximate is_trivially_copyable with trivial move/copy construction and
311/// trivial destruction. While the standard doesn't specify that you're allowed
312/// copy these types with memcpy, there is no way for the type to observe this.
313/// This catches the important case of std::pair<POD, POD>, which is not
314/// trivially assignable.
315template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
316 (is_trivially_move_constructible<T>::value) &&
317 std::is_trivially_destructible<T>::value>
318class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
319 friend class SmallVectorTemplateCommon<T>;
320
321protected:
322 static constexpr bool TakesParamByValue = false;
323 using ValueParamT = const T &;
324
325 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
326
327 static void destroy_range(T *S, T *E) {
328 while (S != E) {
329 --E;
330 E->~T();
331 }
332 }
333
334 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
335 /// constructing elements as needed.
336 template<typename It1, typename It2>
337 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
338 std::uninitialized_copy(std::make_move_iterator(I),
339 std::make_move_iterator(E), Dest);
340 }
341
342 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
343 /// constructing elements as needed.
344 template<typename It1, typename It2>
345 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
346 std::uninitialized_copy(I, E, Dest);
347 }
348
349 /// Grow the allocated memory (without initializing new elements), doubling
350 /// the size of the allocated memory. Guarantees space for at least one more
351 /// element, or MinSize more elements if specified.
352 void grow(size_t MinSize = 0);
353
354 /// Create a new allocation big enough for \p MinSize and pass back its size
355 /// in \p NewCapacity. This is the first section of \a grow().
356 T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
357 return static_cast<T *>(
358 SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
359 MinSize, sizeof(T), NewCapacity));
360 }
361
362 /// Move existing elements over to the new allocation \p NewElts, the middle
363 /// section of \a grow().
364 void moveElementsForGrow(T *NewElts);
365
366 /// Transfer ownership of the allocation, finishing up \a grow().
367 void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
368
369 /// Reserve enough space to add one element, and return the updated element
370 /// pointer in case it was a reference to the storage.
371 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
372 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
373 }
374
375 /// Reserve enough space to add one element, and return the updated element
376 /// pointer in case it was a reference to the storage.
377 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
378 return const_cast<T *>(
379 this->reserveForParamAndGetAddressImpl(this, Elt, N));
380 }
381
382 static T &&forward_value_param(T &&V) { return std::move(V); }
383 static const T &forward_value_param(const T &V) { return V; }
384
385 void growAndAssign(size_t NumElts, const T &Elt) {
386 // Grow manually in case Elt is an internal reference.
387 size_t NewCapacity;
388 T *NewElts = mallocForGrow(NumElts, NewCapacity);
389 std::uninitialized_fill_n(NewElts, NumElts, Elt);
390 this->destroy_range(this->begin(), this->end());
391 takeAllocationForGrow(NewElts, NewCapacity);
392 this->set_size(NumElts);
393 }
394
395 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
396 // Grow manually in case one of Args is an internal reference.
397 size_t NewCapacity;
398 T *NewElts = mallocForGrow(0, NewCapacity);
399 ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
400 moveElementsForGrow(NewElts);
401 takeAllocationForGrow(NewElts, NewCapacity);
402 this->set_size(this->size() + 1);
403 return this->back();
404 }
405
406public:
407 void push_back(const T &Elt) {
408 const T *EltPtr = reserveForParamAndGetAddress(Elt);
409 ::new ((void *)this->end()) T(*EltPtr);
410 this->set_size(this->size() + 1);
411 }
412
413 void push_back(T &&Elt) {
414 T *EltPtr = reserveForParamAndGetAddress(Elt);
415 ::new ((void *)this->end()) T(::std::move(*EltPtr));
416 this->set_size(this->size() + 1);
417 }
418
419 void pop_back() {
420 this->set_size(this->size() - 1);
421 this->end()->~T();
422 }
423};
424
425// Define this out-of-line to dissuade the C++ compiler from inlining it.
426template <typename T, bool TriviallyCopyable>
427void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
428 size_t NewCapacity;
429 T *NewElts = mallocForGrow(MinSize, NewCapacity);
430 moveElementsForGrow(NewElts);
431 takeAllocationForGrow(NewElts, NewCapacity);
432}
433
434// Define this out-of-line to dissuade the C++ compiler from inlining it.
435template <typename T, bool TriviallyCopyable>
436void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
437 T *NewElts) {
438 // Move the elements over.
439 this->uninitialized_move(this->begin(), this->end(), NewElts);
440
441 // Destroy the original elements.
442 destroy_range(this->begin(), this->end());
443}
444
445// Define this out-of-line to dissuade the C++ compiler from inlining it.
446template <typename T, bool TriviallyCopyable>
447void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
448 T *NewElts, size_t NewCapacity) {
449 // If this wasn't grown from the inline copy, deallocate the old space.
450 if (!this->isSmall())
451 free(this->begin());
452
453 this->BeginX = NewElts;
454 this->Capacity = NewCapacity;
455}
456
457/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
458/// method implementations that are designed to work with trivially copyable
459/// T's. This allows using memcpy in place of copy/move construction and
460/// skipping destruction.
461template <typename T>
462class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
463 friend class SmallVectorTemplateCommon<T>;
464
465protected:
466 /// True if it's cheap enough to take parameters by value. Doing so avoids
467 /// overhead related to mitigations for reference invalidation.
468 static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
469
470 /// Either const T& or T, depending on whether it's cheap enough to take
471 /// parameters by value.
472 using ValueParamT =
473 typename std::conditional<TakesParamByValue, T, const T &>::type;
474
475 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
476
477 // No need to do a destroy loop for POD's.
478 static void destroy_range(T *, T *) {}
479
480 /// Move the range [I, E) onto the uninitialized memory
481 /// starting with "Dest", constructing elements into it as needed.
482 template<typename It1, typename It2>
483 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
484 // Just do a copy.
485 uninitialized_copy(I, E, Dest);
486 }
487
488 /// Copy the range [I, E) onto the uninitialized memory
489 /// starting with "Dest", constructing elements into it as needed.
490 template<typename It1, typename It2>
491 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
492 // Arbitrary iterator types; just use the basic implementation.
493 std::uninitialized_copy(I, E, Dest);
494 }
495
496 /// Copy the range [I, E) onto the uninitialized memory
497 /// starting with "Dest", constructing elements into it as needed.
498 template <typename T1, typename T2>
499 static void uninitialized_copy(
500 T1 *I, T1 *E, T2 *Dest,
501 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
502 T2>::value> * = nullptr) {
503 // Use memcpy for PODs iterated by pointers (which includes SmallVector
504 // iterators): std::uninitialized_copy optimizes to memmove, but we can
505 // use memcpy here. Note that I and E are iterators and thus might be
506 // invalid for memcpy if they are equal.
507 if (I != E)
508 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
509 }
510
511 /// Double the size of the allocated memory, guaranteeing space for at
512 /// least one more element or MinSize if specified.
513 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
514
515 /// Reserve enough space to add one element, and return the updated element
516 /// pointer in case it was a reference to the storage.
517 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
518 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
519 }
520
521 /// Reserve enough space to add one element, and return the updated element
522 /// pointer in case it was a reference to the storage.
523 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
524 return const_cast<T *>(
525 this->reserveForParamAndGetAddressImpl(this, Elt, N));
526 }
527
528 /// Copy \p V or return a reference, depending on \a ValueParamT.
529 static ValueParamT forward_value_param(ValueParamT V) { return V; }
530
531 void growAndAssign(size_t NumElts, T Elt) {
532 // Elt has been copied in case it's an internal reference, side-stepping
533 // reference invalidation problems without losing the realloc optimization.
534 this->set_size(0);
535 this->grow(NumElts);
536 std::uninitialized_fill_n(this->begin(), NumElts, Elt);
537 this->set_size(NumElts);
538 }
539
540 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
541 // Use push_back with a copy in case Args has an internal reference,
542 // side-stepping reference invalidation problems without losing the realloc
543 // optimization.
544 push_back(T(std::forward<ArgTypes>(Args)...));
545 return this->back();
546 }
547
548public:
549 void push_back(ValueParamT Elt) {
550 const T *EltPtr = reserveForParamAndGetAddress(Elt);
551 memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
552 this->set_size(this->size() + 1);
553 }
554
555 void pop_back() { this->set_size(this->size() - 1); }
556};
557
558/// This class consists of common code factored out of the SmallVector class to
559/// reduce code duplication based on the SmallVector 'N' template parameter.
560template <typename T>
561class SmallVectorImpl : public SmallVectorTemplateBase<T> {
562 using SuperClass = SmallVectorTemplateBase<T>;
563
564public:
565 using iterator = typename SuperClass::iterator;
566 using const_iterator = typename SuperClass::const_iterator;
567 using reference = typename SuperClass::reference;
568 using size_type = typename SuperClass::size_type;
569
570protected:
571 using SmallVectorTemplateBase<T>::TakesParamByValue;
572 using ValueParamT = typename SuperClass::ValueParamT;
573
574 // Default ctor - Initialize to empty.
575 explicit SmallVectorImpl(unsigned N)
576 : SmallVectorTemplateBase<T>(N) {}
577
578 void assignRemote(SmallVectorImpl &&RHS) {
579 this->destroy_range(this->begin(), this->end());
580 if (!this->isSmall())
581 free(this->begin());
582 this->BeginX = RHS.BeginX;
583 this->Size = RHS.Size;
584 this->Capacity = RHS.Capacity;
585 RHS.resetToSmall();
586 }
587
588public:
589 SmallVectorImpl(const SmallVectorImpl &) = delete;
590
591 ~SmallVectorImpl() {
592 // Subclass has already destructed this vector's elements.
593 // If this wasn't grown from the inline copy, deallocate the old space.
594 if (!this->isSmall())
595 free(this->begin());
596 }
597
598 void clear() {
599 this->destroy_range(this->begin(), this->end());
600 this->Size = 0;
601 }
602
603private:
604 // Make set_size() private to avoid misuse in subclasses.
605 using SuperClass::set_size;
606
607 template <bool ForOverwrite> void resizeImpl(size_type N) {
608 if (N == this->size())
609 return;
610
611 if (N < this->size()) {
612 this->truncate(N);
613 return;
614 }
615
616 this->reserve(N);
617 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
618 if (ForOverwrite)
619 new (&*I) T;
620 else
621 new (&*I) T();
622 this->set_size(N);
623 }
624
625public:
626 void resize(size_type N) { resizeImpl<false>(N); }
627
628 /// Like resize, but \ref T is POD, the new values won't be initialized.
629 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
630
631 /// Like resize, but requires that \p N is less than \a size().
632 void truncate(size_type N) {
633 assert(this->size() >= N && "Cannot increase size with truncate");
634 this->destroy_range(this->begin() + N, this->end());
635 this->set_size(N);
636 }
637
638 void resize(size_type N, ValueParamT NV) {
639 if (N == this->size())
640 return;
641
642 if (N < this->size()) {
643 this->truncate(N);
644 return;
645 }
646
647 // N > this->size(). Defer to append.
648 this->append(N - this->size(), NV);
649 }
650
651 void reserve(size_type N) {
652 if (this->capacity() < N)
653 this->grow(N);
654 }
655
656 void pop_back_n(size_type NumItems) {
657 assert(this->size() >= NumItems);
658 truncate(this->size() - NumItems);
659 }
660
661 [[nodiscard]] T pop_back_val() {
662 T Result = ::std::move(this->back());
663 this->pop_back();
664 return Result;
665 }
666
667 void swap(SmallVectorImpl &RHS);
668
669 /// Add the specified range to the end of the SmallVector.
670 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>>
671 void append(ItTy in_start, ItTy in_end) {
672 this->assertSafeToAddRange(in_start, in_end);
673 size_type NumInputs = std::distance(in_start, in_end);
674 this->reserve(this->size() + NumInputs);
675 this->uninitialized_copy(in_start, in_end, this->end());
676 this->set_size(this->size() + NumInputs);
677 }
678
679 /// Append \p NumInputs copies of \p Elt to the end.
680 void append(size_type NumInputs, ValueParamT Elt) {
681 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
682 std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
683 this->set_size(this->size() + NumInputs);
684 }
685
686 void append(std::initializer_list<T> IL) {
687 append(IL.begin(), IL.end());
688 }
689
690 void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
691
692 void assign(size_type NumElts, ValueParamT Elt) {
693 // Note that Elt could be an internal reference.
694 if (NumElts > this->capacity()) {
695 this->growAndAssign(NumElts, Elt);
696 return;
697 }
698
699 // Assign over existing elements.
700 std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
701 if (NumElts > this->size())
702 std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
703 else if (NumElts < this->size())
704 this->destroy_range(this->begin() + NumElts, this->end());
705 this->set_size(NumElts);
706 }
707
708 // FIXME: Consider assigning over existing elements, rather than clearing &
709 // re-initializing them - for all assign(...) variants.
710
711 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>>
712 void assign(ItTy in_start, ItTy in_end) {
713 this->assertSafeToReferenceAfterClear(in_start, in_end);
714 clear();
715 append(in_start, in_end);
716 }
717
718 void assign(std::initializer_list<T> IL) {
719 clear();
720 append(IL);
721 }
722
723 void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
724
725 iterator erase(const_iterator CI) {
726 // Just cast away constness because this is a non-const member function.
727 iterator I = const_cast<iterator>(CI);
728
729 assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.");
730
731 iterator N = I;
732 // Shift all elts down one.
733 std::move(I+1, this->end(), I);
734 // Drop the last elt.
735 this->pop_back();
736 return(N);
737 }
738
739 iterator erase(const_iterator CS, const_iterator CE) {
740 // Just cast away constness because this is a non-const member function.
741 iterator S = const_cast<iterator>(CS);
742 iterator E = const_cast<iterator>(CE);
743
744 assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.");
745
746 iterator N = S;
747 // Shift all elts down.
748 iterator I = std::move(E, this->end(), S);
749 // Drop the last elts.
750 this->destroy_range(I, this->end());
751 this->set_size(I - this->begin());
752 return(N);
753 }
754
755private:
756 template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
757 // Callers ensure that ArgType is derived from T.
758 static_assert(
759 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
760 T>::value,
761 "ArgType must be derived from T!");
762
763 if (I == this->end()) { // Important special case for empty vector.
764 this->push_back(::std::forward<ArgType>(Elt));
765 return this->end()-1;
766 }
767
768 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
769
770 // Grow if necessary.
771 size_t Index = I - this->begin();
772 std::remove_reference_t<ArgType> *EltPtr =
773 this->reserveForParamAndGetAddress(Elt);
774 I = this->begin() + Index;
775
776 ::new ((void*) this->end()) T(::std::move(this->back()));
777 // Push everything else over.
778 std::move_backward(I, this->end()-1, this->end());
779 this->set_size(this->size() + 1);
780
781 // If we just moved the element we're inserting, be sure to update
782 // the reference (never happens if TakesParamByValue).
783 static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
784 "ArgType must be 'T' when taking by value!");
785 if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
786 ++EltPtr;
787
788 *I = ::std::forward<ArgType>(*EltPtr);
789 return I;
790 }
791
792public:
793 iterator insert(iterator I, T &&Elt) {
794 return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
795 }
796
797 iterator insert(iterator I, const T &Elt) {
798 return insert_one_impl(I, this->forward_value_param(Elt));
799 }
800
801 iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
802 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
803 size_t InsertElt = I - this->begin();
804
805 if (I == this->end()) { // Important special case for empty vector.
806 append(NumToInsert, Elt);
807 return this->begin()+InsertElt;
808 }
809
810 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
811
812 // Ensure there is enough space, and get the (maybe updated) address of
813 // Elt.
814 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
815
816 // Uninvalidate the iterator.
817 I = this->begin()+InsertElt;
818
819 // If there are more elements between the insertion point and the end of the
820 // range than there are being inserted, we can use a simple approach to
821 // insertion. Since we already reserved space, we know that this won't
822 // reallocate the vector.
823 if (size_t(this->end()-I) >= NumToInsert) {
824 T *OldEnd = this->end();
825 append(std::move_iterator<iterator>(this->end() - NumToInsert),
826 std::move_iterator<iterator>(this->end()));
827
828 // Copy the existing elements that get replaced.
829 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
830
831 // If we just moved the element we're inserting, be sure to update
832 // the reference (never happens if TakesParamByValue).
833 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
834 EltPtr += NumToInsert;
835
836 std::fill_n(I, NumToInsert, *EltPtr);
837 return I;
838 }
839
840 // Otherwise, we're inserting more elements than exist already, and we're
841 // not inserting at the end.
842
843 // Move over the elements that we're about to overwrite.
844 T *OldEnd = this->end();
845 this->set_size(this->size() + NumToInsert);
846 size_t NumOverwritten = OldEnd-I;
847 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
848
849 // If we just moved the element we're inserting, be sure to update
850 // the reference (never happens if TakesParamByValue).
851 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
852 EltPtr += NumToInsert;
853
854 // Replace the overwritten part.
855 std::fill_n(I, NumOverwritten, *EltPtr);
856
857 // Insert the non-overwritten middle part.
858 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
859 return I;
860 }
861
862 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>>
863 iterator insert(iterator I, ItTy From, ItTy To) {
864 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
865 size_t InsertElt = I - this->begin();
866
867 if (I == this->end()) { // Important special case for empty vector.
868 append(From, To);
869 return this->begin()+InsertElt;
870 }
871
872 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
873
874 // Check that the reserve that follows doesn't invalidate the iterators.
875 this->assertSafeToAddRange(From, To);
876
877 size_t NumToInsert = std::distance(From, To);
878
879 // Ensure there is enough space.
880 reserve(this->size() + NumToInsert);
881
882 // Uninvalidate the iterator.
883 I = this->begin()+InsertElt;
884
885 // If there are more elements between the insertion point and the end of the
886 // range than there are being inserted, we can use a simple approach to
887 // insertion. Since we already reserved space, we know that this won't
888 // reallocate the vector.
889 if (size_t(this->end()-I) >= NumToInsert) {
890 T *OldEnd = this->end();
891 append(std::move_iterator<iterator>(this->end() - NumToInsert),
892 std::move_iterator<iterator>(this->end()));
893
894 // Copy the existing elements that get replaced.
895 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
896
897 std::copy(From, To, I);
898 return I;
899 }
900
901 // Otherwise, we're inserting more elements than exist already, and we're
902 // not inserting at the end.
903
904 // Move over the elements that we're about to overwrite.
905 T *OldEnd = this->end();
906 this->set_size(this->size() + NumToInsert);
907 size_t NumOverwritten = OldEnd-I;
908 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
909
910 // Replace the overwritten part.
911 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
912 *J = *From;
913 ++J; ++From;
914 }
915
916 // Insert the non-overwritten middle part.
917 this->uninitialized_copy(From, To, OldEnd);
918 return I;
919 }
920
921 void insert(iterator I, std::initializer_list<T> IL) {
922 insert(I, IL.begin(), IL.end());
923 }
924
925 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
926 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
927 return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
928
929 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
930 this->set_size(this->size() + 1);
931 return this->back();
932 }
933
934 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
935
936 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
937
938 bool operator==(const SmallVectorImpl &RHS) const {
939 if (this->size() != RHS.size()) return false;
940 return std::equal(this->begin(), this->end(), RHS.begin());
941 }
942 bool operator!=(const SmallVectorImpl &RHS) const {
943 return !(*this == RHS);
944 }
945
946 bool operator<(const SmallVectorImpl &RHS) const {
947 return std::lexicographical_compare(this->begin(), this->end(),
948 RHS.begin(), RHS.end());
949 }
950 bool operator>(const SmallVectorImpl &RHS) const { return RHS < *this; }
951 bool operator<=(const SmallVectorImpl &RHS) const { return !(*this > RHS); }
952 bool operator>=(const SmallVectorImpl &RHS) const { return !(*this < RHS); }
953};
954
955template <typename T>
956void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
957 if (this == &RHS) return;
958
959 // We can only avoid copying elements if neither vector is small.
960 if (!this->isSmall() && !RHS.isSmall()) {
961 std::swap(this->BeginX, RHS.BeginX);
962 std::swap(this->Size, RHS.Size);
963 std::swap(this->Capacity, RHS.Capacity);
964 return;
965 }
966 this->reserve(RHS.size());
967 RHS.reserve(this->size());
968
969 // Swap the shared elements.
970 size_t NumShared = this->size();
971 if (NumShared > RHS.size()) NumShared = RHS.size();
972 for (size_type i = 0; i != NumShared; ++i)
973 std::swap((*this)[i], RHS[i]);
974
975 // Copy over the extra elts.
976 if (this->size() > RHS.size()) {
977 size_t EltDiff = this->size() - RHS.size();
978 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
979 RHS.set_size(RHS.size() + EltDiff);
980 this->destroy_range(this->begin()+NumShared, this->end());
981 this->set_size(NumShared);
982 } else if (RHS.size() > this->size()) {
983 size_t EltDiff = RHS.size() - this->size();
984 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
985 this->set_size(this->size() + EltDiff);
986 this->destroy_range(RHS.begin()+NumShared, RHS.end());
987 RHS.set_size(NumShared);
988 }
989}
990
991template <typename T>
992SmallVectorImpl<T> &SmallVectorImpl<T>::
993 operator=(const SmallVectorImpl<T> &RHS) {
994 // Avoid self-assignment.
995 if (this == &RHS) return *this;
996
997 // If we already have sufficient space, assign the common elements, then
998 // destroy any excess.
999 size_t RHSSize = RHS.size();
1000 size_t CurSize = this->size();
1001 if (CurSize >= RHSSize) {
1002 // Assign common elements.
1003 iterator NewEnd;
1004 if (RHSSize)
1005 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
1006 else
1007 NewEnd = this->begin();
1008
1009 // Destroy excess elements.
1010 this->destroy_range(NewEnd, this->end());
1011
1012 // Trim.
1013 this->set_size(RHSSize);
1014 return *this;
1015 }
1016
1017 // If we have to grow to have enough elements, destroy the current elements.
1018 // This allows us to avoid copying them during the grow.
1019 // FIXME: don't do this if they're efficiently moveable.
1020 if (this->capacity() < RHSSize) {
1021 // Destroy current elements.
1022 this->clear();
1023 CurSize = 0;
1024 this->grow(RHSSize);
1025 } else if (CurSize) {
1026 // Otherwise, use assignment for the already-constructed elements.
1027 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1028 }
1029
1030 // Copy construct the new elements in place.
1031 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1032 this->begin()+CurSize);
1033
1034 // Set end.
1035 this->set_size(RHSSize);
1036 return *this;
1037}
1038
1039template <typename T>
1040SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
1041 // Avoid self-assignment.
1042 if (this == &RHS) return *this;
1043
1044 // If the RHS isn't small, clear this vector and then steal its buffer.
1045 if (!RHS.isSmall()) {
1046 this->assignRemote(std::move(RHS));
1047 return *this;
1048 }
1049
1050 // If we already have sufficient space, assign the common elements, then
1051 // destroy any excess.
1052 size_t RHSSize = RHS.size();
1053 size_t CurSize = this->size();
1054 if (CurSize >= RHSSize) {
1055 // Assign common elements.
1056 iterator NewEnd = this->begin();
1057 if (RHSSize)
1058 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1059
1060 // Destroy excess elements and trim the bounds.
1061 this->destroy_range(NewEnd, this->end());
1062 this->set_size(RHSSize);
1063
1064 // Clear the RHS.
1065 RHS.clear();
1066
1067 return *this;
1068 }
1069
1070 // If we have to grow to have enough elements, destroy the current elements.
1071 // This allows us to avoid copying them during the grow.
1072 // FIXME: this may not actually make any sense if we can efficiently move
1073 // elements.
1074 if (this->capacity() < RHSSize) {
1075 // Destroy current elements.
1076 this->clear();
1077 CurSize = 0;
1078 this->grow(RHSSize);
1079 } else if (CurSize) {
1080 // Otherwise, use assignment for the already-constructed elements.
1081 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1082 }
1083
1084 // Move-construct the new elements in place.
1085 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1086 this->begin()+CurSize);
1087
1088 // Set end.
1089 this->set_size(RHSSize);
1090
1091 RHS.clear();
1092 return *this;
1093}
1094
1095/// Storage for the SmallVector elements. This is specialized for the N=0 case
1096/// to avoid allocating unnecessary storage.
1097template <typename T, unsigned N>
1098struct SmallVectorStorage {
1099 alignas(T) char InlineElts[N * sizeof(T)];
1100};
1101
1102/// We need the storage to be properly aligned even for small-size of 0 so that
1103/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1104/// well-defined.
1105template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1106
1107/// Forward declaration of SmallVector so that
1108/// calculateSmallVectorDefaultInlinedElements can reference
1109/// `sizeof(SmallVector<T, 0>)`.
1110template <typename T, unsigned N> class LLVM_GSL_OWNER SmallVector;
1111
1112/// Helper class for calculating the default number of inline elements for
1113/// `SmallVector<T>`.
1114///
1115/// This should be migrated to a constexpr function when our minimum
1116/// compiler support is enough for multi-statement constexpr functions.
1117template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1118 // Parameter controlling the default number of inlined elements
1119 // for `SmallVector<T>`.
1120 //
1121 // The default number of inlined elements ensures that
1122 // 1. There is at least one inlined element.
1123 // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1124 // it contradicts 1.
1125 static constexpr size_t kPreferredSmallVectorSizeof = 64;
1126
1127 // static_assert that sizeof(T) is not "too big".
1128 //
1129 // Because our policy guarantees at least one inlined element, it is possible
1130 // for an arbitrarily large inlined element to allocate an arbitrarily large
1131 // amount of inline storage. We generally consider it an antipattern for a
1132 // SmallVector to allocate an excessive amount of inline storage, so we want
1133 // to call attention to these cases and make sure that users are making an
1134 // intentional decision if they request a lot of inline storage.
1135 //
1136 // We want this assertion to trigger in pathological cases, but otherwise
1137 // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1138 // larger than kPreferredSmallVectorSizeof (otherwise,
1139 // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1140 // pattern seems useful in practice).
1141 //
1142 // One wrinkle is that this assertion is in theory non-portable, since
1143 // sizeof(T) is in general platform-dependent. However, we don't expect this
1144 // to be much of an issue, because most LLVM development happens on 64-bit
1145 // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
1146 // 32-bit hosts, dodging the issue. The reverse situation, where development
1147 // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
1148 // 64-bit host, is expected to be very rare.
1149 static_assert(
1150 sizeof(T) <= 256,
1151 "You are trying to use a default number of inlined elements for "
1152 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1153 "explicit number of inlined elements with `SmallVector<T, N>` to make "
1154 "sure you really want that much inline storage.");
1155
1156 // Discount the size of the header itself when calculating the maximum inline
1157 // bytes.
1158 static constexpr size_t PreferredInlineBytes =
1159 kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1160 static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1161 static constexpr size_t value =
1162 NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1163};
1164
1165/// This is a 'vector' (really, a variable-sized array), optimized
1166/// for the case when the array is small. It contains some number of elements
1167/// in-place, which allows it to avoid heap allocation when the actual number of
1168/// elements is below that threshold. This allows normal "small" cases to be
1169/// fast without losing generality for large inputs.
1170///
1171/// \note
1172/// In the absence of a well-motivated choice for the number of inlined
1173/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1174/// omitting the \p N). This will choose a default number of inlined elements
1175/// reasonable for allocation on the stack (for example, trying to keep \c
1176/// sizeof(SmallVector<T>) around 64 bytes).
1177///
1178/// \warning This does not attempt to be exception safe.
1179///
1180/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1181template <typename T,
1182 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1183class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
1184 SmallVectorStorage<T, N> {
1185public:
1186 SmallVector() : SmallVectorImpl<T>(N) {}
1187
1188 ~SmallVector() {
1189 // Destroy the constructed elements in the vector.
1190 this->destroy_range(this->begin(), this->end());
1191 }
1192
1193 explicit SmallVector(size_t Size, const T &Value = T())
1194 : SmallVectorImpl<T>(N) {
1195 this->assign(Size, Value);
1196 }
1197
1198 template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>>
1199 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1200 this->append(S, E);
1201 }
1202
1203 template <typename RangeTy>
1204 explicit SmallVector(const iterator_range<RangeTy> &R)
1205 : SmallVectorImpl<T>(N) {
1206 this->append(R.begin(), R.end());
1207 }
1208
1209 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1210 this->append(IL);
1211 }
1212
1213 template <typename U,
1214 typename = std::enable_if_t<std::is_convertible<U, T>::value>>
1215 explicit SmallVector(ArrayRef<U> A) : SmallVectorImpl<T>(N) {
1216 this->append(A.begin(), A.end());
1217 }
1218
1219 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
1220 if (!RHS.empty())
1221 SmallVectorImpl<T>::operator=(RHS);
1222 }
1223
1224 SmallVector &operator=(const SmallVector &RHS) {
1225 SmallVectorImpl<T>::operator=(RHS);
1226 return *this;
1227 }
1228
1229 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
1230 if (!RHS.empty())
1231 SmallVectorImpl<T>::operator=(::std::move(RHS));
1232 }
1233
1234 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1235 if (!RHS.empty())
1236 SmallVectorImpl<T>::operator=(::std::move(RHS));
1237 }
1238
1239 SmallVector &operator=(SmallVector &&RHS) {
1240 if (N) {
1241 SmallVectorImpl<T>::operator=(::std::move(RHS));
1242 return *this;
1243 }
1244 // SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the
1245 // case.
1246 if (this == &RHS)
1247 return *this;
1248 if (RHS.empty()) {
1249 this->destroy_range(this->begin(), this->end());
1250 this->Size = 0;
1251 } else {
1252 this->assignRemote(std::move(RHS));
1253 }
1254 return *this;
1255 }
1256
1257 SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1258 SmallVectorImpl<T>::operator=(::std::move(RHS));
1259 return *this;
1260 }
1261
1262 SmallVector &operator=(std::initializer_list<T> IL) {
1263 this->assign(IL);
1264 return *this;
1265 }
1266};
1267
1268template <typename T, unsigned N>
1269inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1270 return X.capacity_in_bytes();
1271}
1272
1273template <typename RangeType>
1274using ValueTypeFromRangeType =
1275 typename std::remove_const<typename std::remove_reference<
1276 decltype(*std::begin(std::declval<RangeType &>()))>::type>::type;
1277
1278/// Given a range of type R, iterate the entire range and return a
1279/// SmallVector with elements of the vector. This is useful, for example,
1280/// when you want to iterate a range and then sort the results.
1281template <unsigned Size, typename R>
1282SmallVector<ValueTypeFromRangeType<R>, Size> to_vector(R &&Range) {
1283 return {std::begin(Range), std::end(Range)};
1284}
1285template <typename R>
1286SmallVector<ValueTypeFromRangeType<R>> to_vector(R &&Range) {
1287 return {std::begin(Range), std::end(Range)};
1288}
1289
1290template <typename Out, unsigned Size, typename R>
1291SmallVector<Out, Size> to_vector_of(R &&Range) {
1292 return {std::begin(Range), std::end(Range)};
1293}
1294
1295template <typename Out, typename R> SmallVector<Out> to_vector_of(R &&Range) {
1296 return {std::begin(Range), std::end(Range)};
1297}
1298
1299} // end namespace llvm
1300
1301namespace std {
1302
1303 /// Implement std::swap in terms of SmallVector swap.
1304 template<typename T>
1305 inline void
1306 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
1307 LHS.swap(RHS);
1308 }
1309
1310 /// Implement std::swap in terms of SmallVector swap.
1311 template<typename T, unsigned N>
1312 inline void
1313 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
1314 LHS.swap(RHS);
1315 }
1316
1317} // end namespace std
1318
1319#endif // LLVM_ADT_SMALLVECTOR_H
1320

source code of llvm/include/llvm/ADT/SmallVector.h