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