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