14 #ifndef WPIUTIL_WPI_SMALLVECTOR_H
15 #define WPIUTIL_WPI_SMALLVECTOR_H
22 #pragma GCC diagnostic warning "-Wclass-memaccess"
26 #include "wpi/AlignOf.h"
27 #include "wpi/Compiler.h"
28 #include "wpi/MathExtras.h"
29 #include "wpi/memory.h"
30 #include "wpi/type_traits.h"
36 #include <initializer_list>
40 #include <type_traits>
48 void *BeginX, *EndX, *CapacityX;
52 : BeginX(FirstEl), EndX(FirstEl), CapacityX((
char*)FirstEl+Size) {}
56 void grow_pod(
void *FirstEl,
size_t MinSizeInBytes,
size_t TSize);
61 return size_t((
char*)EndX - (
char*)BeginX);
66 return size_t((
char*)CapacityX - (
char*)BeginX);
69 LLVM_NODISCARD
bool empty()
const {
return BeginX == EndX; }
75 template <
typename T,
typename =
void>
90 void grow_pod(
size_t MinSizeInBytes,
size_t TSize) {
97 return BeginX ==
static_cast<const void*
>(&FirstEl);
102 BeginX = EndX = CapacityX = &FirstEl;
105 void setEnd(T *P) { this->EndX = P; }
108 using size_type = size_t;
109 using difference_type = ptrdiff_t;
110 using value_type = T;
111 using iterator = T *;
112 using const_iterator =
const T *;
114 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
115 using reverse_iterator = std::reverse_iterator<iterator>;
117 using reference = T &;
118 using const_reference =
const T &;
120 using const_pointer =
const T *;
123 LLVM_ATTRIBUTE_ALWAYS_INLINE
124 iterator begin() {
return (iterator)this->BeginX; }
125 LLVM_ATTRIBUTE_ALWAYS_INLINE
126 const_iterator begin()
const {
return (const_iterator)this->BeginX; }
127 LLVM_ATTRIBUTE_ALWAYS_INLINE
128 iterator end() {
return (iterator)this->EndX; }
129 LLVM_ATTRIBUTE_ALWAYS_INLINE
130 const_iterator end()
const {
return (const_iterator)this->EndX; }
133 iterator capacity_ptr() {
return (iterator)this->CapacityX; }
134 const_iterator capacity_ptr()
const {
return (const_iterator)this->CapacityX;}
138 reverse_iterator rbegin() {
return reverse_iterator(end()); }
139 const_reverse_iterator rbegin()
const{
return const_reverse_iterator(end()); }
140 reverse_iterator rend() {
return reverse_iterator(begin()); }
141 const_reverse_iterator rend()
const {
return const_reverse_iterator(begin());}
143 LLVM_ATTRIBUTE_ALWAYS_INLINE
144 size_type size()
const {
return end()-begin(); }
145 size_type max_size()
const {
return size_type(-1) /
sizeof(T); }
148 size_t capacity()
const {
return capacity_ptr() - begin(); }
155 LLVM_ATTRIBUTE_ALWAYS_INLINE
156 reference operator[](size_type idx) {
157 assert(idx < size());
160 LLVM_ATTRIBUTE_ALWAYS_INLINE
161 const_reference operator[](size_type idx)
const {
162 assert(idx < size());
170 const_reference front()
const {
179 const_reference back()
const {
187 template <
typename T,
bool isPodLike>
192 static void destroy_range(T *S, T *E) {
201 template<
typename It1,
typename It2>
203 std::uninitialized_copy(std::make_move_iterator(I),
204 std::make_move_iterator(E), Dest);
209 template<
typename It1,
typename It2>
211 std::uninitialized_copy(I, E, Dest);
217 void grow(
size_t MinSize = 0);
220 void push_back(
const T &Elt) {
221 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
223 ::new ((
void*) this->end()) T(Elt);
224 this->setEnd(this->end()+1);
227 void push_back(T &&Elt) {
228 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
230 ::new ((
void*) this->end()) T(::
std::move(Elt));
231 this->setEnd(this->end()+1);
235 this->setEnd(this->end()-1);
241 template <
typename T,
bool isPodLike>
243 size_t CurCapacity = this->
capacity();
244 size_t CurSize = this->size();
246 size_t NewCapacity = size_t(
NextPowerOf2(CurCapacity+2));
247 if (NewCapacity < MinSize)
248 NewCapacity = MinSize;
249 T *NewElts =
static_cast<T*
>(
CheckedMalloc(NewCapacity*
sizeof(T)));
255 destroy_range(this->begin(), this->end());
261 this->setEnd(NewElts+CurSize);
262 this->BeginX = NewElts;
263 this->CapacityX = this->begin()+NewCapacity;
269 template <
typename T>
275 static void destroy_range(T *, T *) {}
279 template<
typename It1,
typename It2>
287 template<
typename It1,
typename It2>
290 std::uninitialized_copy(I, E, Dest);
295 template <
typename T1,
typename T2>
297 T1 *I, T1 *E, T2 *Dest,
298 typename std::enable_if<std::is_same<
typename std::remove_const<T1>::type,
299 T2>::value>::type * =
nullptr) {
305 memcpy(Dest, I, (E - I) *
sizeof(T));
310 void grow(
size_t MinSize = 0) {
311 this->grow_pod(MinSize*
sizeof(T),
sizeof(T));
315 void push_back(
const T &Elt) {
316 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
318 memcpy(this->end(), &Elt,
sizeof(T));
319 this->setEnd(this->end()+1);
323 this->setEnd(this->end()-1);
329 template <
typename T>
330 class SmallVectorImpl :
public SmallVectorTemplateBase<T, isPodLike<T>::value> {
331 using SuperClass = SmallVectorTemplateBase<T, isPodLike<T>::value>;
334 using iterator =
typename SuperClass::iterator;
335 using const_iterator =
typename SuperClass::const_iterator;
336 using size_type =
typename SuperClass::size_type;
340 explicit SmallVectorImpl(
unsigned N)
341 : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
345 SmallVectorImpl(
const SmallVectorImpl &) =
delete;
355 this->destroy_range(this->begin(), this->end());
356 this->EndX = this->BeginX;
359 void resize(size_type N) {
360 if (N < this->
size()) {
361 this->destroy_range(this->begin()+N, this->end());
362 this->setEnd(this->begin()+N);
363 }
else if (N > this->
size()) {
366 for (
auto I = this->end(), E = this->begin() + N; I != E; ++I)
368 this->setEnd(this->begin()+N);
372 void resize(size_type N,
const T &NV) {
373 if (N < this->
size()) {
374 this->destroy_range(this->begin()+N, this->end());
375 this->setEnd(this->begin()+N);
376 }
else if (N > this->
size()) {
379 std::uninitialized_fill(this->end(), this->begin()+N, NV);
380 this->setEnd(this->begin()+N);
384 void reserve(size_type N) {
389 LLVM_NODISCARD T pop_back_val() {
390 T Result = ::std::move(this->back());
395 void swap(SmallVectorImpl &RHS);
398 template <
typename in_iter,
399 typename =
typename std::enable_if<std::is_convertible<
400 typename std::iterator_traits<in_iter>::iterator_category,
401 std::input_iterator_tag>::value>::type>
402 void append(in_iter in_start, in_iter in_end) {
403 size_type NumInputs = std::distance(in_start, in_end);
405 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
410 this->setEnd(this->end() + NumInputs);
414 void append(size_type NumInputs,
const T &Elt) {
416 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
420 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
421 this->setEnd(this->end() + NumInputs);
424 void append(std::initializer_list<T> IL) {
425 append(IL.begin(), IL.end());
431 void assign(size_type NumElts,
const T &Elt) {
435 this->setEnd(this->begin()+NumElts);
436 std::uninitialized_fill(this->begin(), this->end(), Elt);
439 template <
typename in_iter,
440 typename =
typename std::enable_if<std::is_convertible<
441 typename std::iterator_traits<in_iter>::iterator_category,
442 std::input_iterator_tag>::value>::type>
443 void assign(in_iter in_start, in_iter in_end) {
445 append(in_start, in_end);
448 void assign(std::initializer_list<T> IL) {
453 iterator erase(const_iterator CI) {
455 iterator I =
const_cast<iterator
>(CI);
457 assert(I >= this->begin() &&
"Iterator to erase is out of bounds.");
458 assert(I < this->end() &&
"Erasing at past-the-end iterator.");
462 std::move(I+1, this->end(), I);
468 iterator erase(const_iterator CS, const_iterator CE) {
470 iterator S =
const_cast<iterator
>(CS);
471 iterator E =
const_cast<iterator
>(CE);
473 assert(S >= this->begin() &&
"Range to erase is out of bounds.");
474 assert(S <= E &&
"Trying to erase invalid range.");
475 assert(E <= this->end() &&
"Trying to erase past the end.");
479 iterator I = std::move(E, this->end(), S);
481 this->destroy_range(I, this->end());
486 iterator insert(iterator I, T &&Elt) {
487 if (I == this->end()) {
488 this->push_back(::std::move(Elt));
489 return this->end()-1;
492 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
493 assert(I <= this->end() &&
"Inserting past the end of the vector.");
495 if (this->EndX >= this->CapacityX) {
496 size_t EltNo = I-this->begin();
498 I = this->begin()+EltNo;
501 ::new ((
void*) this->end()) T(::
std::move(this->back()));
503 std::move_backward(I, this->end()-1, this->end());
504 this->setEnd(this->end()+1);
509 if (I <= EltPtr && EltPtr < this->EndX)
512 *I = ::
std::move(*EltPtr);
516 iterator insert(iterator I, const T &Elt) {
517 if (I == this->end()) {
518 this->push_back(Elt);
519 return this->end()-1;
522 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
523 assert(I <= this->end() &&
"Inserting past the end of the vector.");
525 if (this->EndX >= this->CapacityX) {
526 size_t EltNo = I-this->begin();
528 I = this->begin()+EltNo;
530 ::new ((
void*) this->end()) T(
std::move(this->back()));
532 std::move_backward(I, this->end()-1, this->end());
533 this->setEnd(this->end()+1);
537 const T *EltPtr = &Elt;
538 if (I <= EltPtr && EltPtr < this->EndX)
545 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
547 size_t InsertElt = I - this->begin();
549 if (I == this->end()) {
550 append(NumToInsert, Elt);
551 return this->begin()+InsertElt;
554 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
555 assert(I <= this->end() &&
"Inserting past the end of the vector.");
558 reserve(this->
size() + NumToInsert);
561 I = this->begin()+InsertElt;
567 if (
size_t(this->end()-I) >= NumToInsert) {
568 T *OldEnd = this->end();
569 append(std::move_iterator<iterator>(this->end() - NumToInsert),
570 std::move_iterator<iterator>(this->end()));
573 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
575 std::fill_n(I, NumToInsert, Elt);
583 T *OldEnd = this->end();
584 this->setEnd(this->end() + NumToInsert);
585 size_t NumOverwritten = OldEnd-I;
589 std::fill_n(I, NumOverwritten, Elt);
592 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
596 template <
typename ItTy,
597 typename =
typename std::enable_if<std::is_convertible<
598 typename std::iterator_traits<ItTy>::iterator_category,
599 std::input_iterator_tag>::value>::type>
600 iterator insert(iterator I, ItTy From, ItTy To) {
602 size_t InsertElt = I - this->begin();
604 if (I == this->end()) {
606 return this->begin()+InsertElt;
609 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
610 assert(I <= this->end() &&
"Inserting past the end of the vector.");
612 size_t NumToInsert = std::distance(From, To);
615 reserve(this->
size() + NumToInsert);
618 I = this->begin()+InsertElt;
624 if (
size_t(this->end()-I) >= NumToInsert) {
625 T *OldEnd = this->end();
626 append(std::move_iterator<iterator>(this->end() - NumToInsert),
627 std::move_iterator<iterator>(this->end()));
630 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
632 std::copy(From, To, I);
640 T *OldEnd = this->end();
641 this->setEnd(this->end() + NumToInsert);
642 size_t NumOverwritten = OldEnd-I;
646 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
656 void insert(iterator I, std::initializer_list<T> IL) {
657 insert(I, IL.begin(), IL.end());
660 template <
typename... ArgTypes>
void emplace_back(ArgTypes &&... Args) {
661 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
663 ::new ((
void *)this->end()) T(
std::forward<ArgTypes>(Args)...);
664 this->setEnd(this->end() + 1);
667 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
669 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
671 bool operator==(const SmallVectorImpl &RHS)
const {
672 if (this->
size() != RHS.size())
return false;
673 return std::equal(this->begin(), this->end(), RHS.
begin());
675 bool operator!=(
const SmallVectorImpl &RHS)
const {
676 return !(*
this == RHS);
679 bool operator<(
const SmallVectorImpl &RHS)
const {
680 return std::lexicographical_compare(this->begin(), this->end(),
681 RHS.begin(), RHS.end());
695 this->setEnd(this->begin() + N);
699 template <
typename T>
700 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
701 if (
this == &RHS)
return;
704 if (!this->
isSmall() && !RHS.isSmall()) {
705 std::swap(this->BeginX, RHS.BeginX);
706 std::swap(this->EndX, RHS.EndX);
707 std::swap(this->CapacityX, RHS.CapacityX);
711 this->
grow(RHS.size());
712 if (this->
size() > RHS.capacity())
713 RHS.grow(this->size());
716 size_t NumShared = this->
size();
717 if (NumShared > RHS.size()) NumShared = RHS.size();
718 for (size_type i = 0; i != NumShared; ++i)
719 std::swap((*
this)[i], RHS[i]);
722 if (this->
size() > RHS.size()) {
723 size_t EltDiff = this->
size() - RHS.size();
725 RHS.setEnd(RHS.end()+EltDiff);
726 this->destroy_range(this->begin()+NumShared, this->end());
727 this->setEnd(this->begin()+NumShared);
728 }
else if (RHS.size() > this->
size()) {
729 size_t EltDiff = RHS.size() - this->
size();
731 this->setEnd(this->end() + EltDiff);
732 this->destroy_range(RHS.begin()+NumShared, RHS.end());
733 RHS.setEnd(RHS.begin()+NumShared);
737 template <
typename T>
738 SmallVectorImpl<T> &SmallVectorImpl<T>::
739 operator=(
const SmallVectorImpl<T> &RHS) {
741 if (
this == &RHS)
return *
this;
745 size_t RHSSize = RHS.size();
746 size_t CurSize = this->
size();
747 if (CurSize >= RHSSize) {
751 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
753 NewEnd = this->begin();
756 this->destroy_range(NewEnd, this->end());
759 this->setEnd(NewEnd);
768 this->destroy_range(this->begin(), this->end());
769 this->setEnd(this->begin());
772 }
else if (CurSize) {
774 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
779 this->begin()+CurSize);
782 this->setEnd(this->begin()+RHSSize);
786 template <
typename T>
787 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
789 if (
this == &RHS)
return *
this;
792 if (!RHS.isSmall()) {
793 this->destroy_range(this->begin(), this->end());
794 if (!this->
isSmall()) free(this->begin());
795 this->BeginX = RHS.BeginX;
796 this->EndX = RHS.EndX;
797 this->CapacityX = RHS.CapacityX;
804 size_t RHSSize = RHS.size();
805 size_t CurSize = this->
size();
806 if (CurSize >= RHSSize) {
808 iterator NewEnd = this->begin();
810 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
813 this->destroy_range(NewEnd, this->end());
814 this->setEnd(NewEnd);
828 this->destroy_range(this->begin(), this->end());
829 this->setEnd(this->begin());
832 }
else if (CurSize) {
834 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
839 this->begin()+CurSize);
842 this->setEnd(this->begin()+RHSSize);
852 template <
typename T,
unsigned N>
867 template <
typename T,
unsigned N>
877 this->destroy_range(this->begin(), this->end());
880 explicit SmallVector(
size_t Size,
const T &Value = T())
882 this->assign(Size, Value);
885 template <
typename ItTy,
886 typename =
typename std::enable_if<std::is_convertible<
887 typename std::iterator_traits<ItTy>::iterator_category,
888 std::input_iterator_tag>::value>::type>
893 template <
typename RangeTy>
896 this->append(R.begin(), R.end());
908 const SmallVector &operator=(
const SmallVector &RHS) {
923 const SmallVector &operator=(SmallVector &&RHS) {
933 const SmallVector &operator=(std::initializer_list<T> IL) {
939 template <
typename T,
unsigned N>
956 template<
typename T,
unsigned N>
964 #endif // LLVM_ADT_SMALLVECTOR_H
This is all the non-templated stuff common to all SmallVectors.
Definition: SmallVector.h:46
static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest, typename std::enable_if< std::is_same< typename std::remove_const< T1 >::type, T2 >::value >::type *=nullptr)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
Definition: SmallVector.h:296
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: hostname.h:17
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:868
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:210
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:310
void grow(size_t MinSize=0)
Grow the allocated memory (without initializing new elements), doubling the size of the allocated mem...
Definition: SmallVector.h:242
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
Definition: SmallVector.h:946
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:288
namespace to hold default to_json function
Definition: SmallString.h:21
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:280
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
A range adaptor for a pair of iterators.
Definition: iterator_range.h:32
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:614
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:202
size_t size_in_bytes() const
This returns size()*sizeof(T).
Definition: SmallVector.h:60
size_t capacity() const
Return the total number of elements in the currently allocated buffer.
Definition: SmallVector.h:148
void * CheckedMalloc(size_t size)
Wrapper around std::malloc that calls std::terminate on out of memory.
void append(size_type NumInputs, const T &Elt)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:414
size_t capacity_in_bytes() const
capacity_in_bytes - This returns capacity()*sizeof(T).
Definition: SmallVector.h:65
SmallVectorTemplateBase - This is where we put method implementations that are des...
Definition: SmallVector.h:188
void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize)
This is an implementation of the grow() method which only works on POD-like data types and is out of ...
const_pointer data() const
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:153
void set_size(size_type N)
Set the array size to N, which the current array must have enough capacity for.
Definition: SmallVector.h:693
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:999
bool isSmall() const
Return true if this is a smallvector which has not had dynamic memory allocated for it...
Definition: SmallVector.h:96
This is the part of SmallVectorTemplateBase which does not depend on whether the type T is a POD...
Definition: SmallVector.h:76
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:402
Data buffer.
Definition: Buffer.h:27
void resetToSmall()
Put this vector in a state of being small.
Definition: SmallVector.h:101
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:151
Storage for the SmallVector elements which aren't contained in SmallVectorTemplateCommon.
Definition: SmallVector.h:853