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"
30 #include "wpi/type_traits.h"
36 #include <initializer_list>
40 #include <type_traits>
49 unsigned Size = 0, Capacity;
53 : BeginX(FirstEl), Capacity(static_cast<unsigned>(Capacity)) {}
57 void grow_pod(
void *FirstEl,
size_t MinCapacity,
size_t TSize);
60 LLVM_ATTRIBUTE_ALWAYS_INLINE
61 size_t size()
const {
return Size; }
62 LLVM_ATTRIBUTE_ALWAYS_INLINE
63 size_t capacity()
const {
return Capacity; }
65 LLVM_NODISCARD
bool empty()
const {
return !Size; }
77 assert(Size <= capacity());
78 this->Size = static_cast<unsigned>(Size);
91 template <
typename T,
typename =
void>
96 void *getFirstEl()
const {
97 return const_cast<void *>(reinterpret_cast<const void *>(
98 reinterpret_cast<const char *>(
this) +
107 void grow_pod(
size_t MinCapacity,
size_t TSize) {
113 bool isSmall()
const {
return BeginX == getFirstEl(); }
117 BeginX = getFirstEl();
122 using size_type = size_t;
123 using difference_type = ptrdiff_t;
124 using value_type = T;
125 using iterator = T *;
126 using const_iterator =
const T *;
128 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
129 using reverse_iterator = std::reverse_iterator<iterator>;
131 using reference = T &;
132 using const_reference =
const T &;
134 using const_pointer =
const T *;
137 LLVM_ATTRIBUTE_ALWAYS_INLINE
138 iterator begin() {
return (iterator)this->BeginX; }
139 LLVM_ATTRIBUTE_ALWAYS_INLINE
140 const_iterator begin()
const {
return (const_iterator)this->BeginX; }
141 LLVM_ATTRIBUTE_ALWAYS_INLINE
142 iterator end() {
return begin() + size(); }
143 LLVM_ATTRIBUTE_ALWAYS_INLINE
144 const_iterator end()
const {
return begin() + size(); }
147 reverse_iterator rbegin() {
return reverse_iterator(end()); }
148 const_reverse_iterator rbegin()
const{
return const_reverse_iterator(end()); }
149 reverse_iterator rend() {
return reverse_iterator(begin()); }
150 const_reverse_iterator rend()
const {
return const_reverse_iterator(begin());}
152 size_type size_in_bytes()
const {
return size() *
sizeof(T); }
153 size_type max_size()
const {
return size_type(-1) /
sizeof(T); }
155 size_t capacity_in_bytes()
const {
return capacity() *
sizeof(T); }
162 LLVM_ATTRIBUTE_ALWAYS_INLINE
163 reference operator[](size_type idx) {
164 assert(idx < size());
167 LLVM_ATTRIBUTE_ALWAYS_INLINE
168 const_reference operator[](size_type idx)
const {
169 assert(idx < size());
177 const_reference front()
const {
186 const_reference back()
const {
194 template <typename T, bool = isPodLike<T>::value>
199 static void destroy_range(T *S, T *E) {
208 template<
typename It1,
typename It2>
210 std::uninitialized_copy(std::make_move_iterator(I),
211 std::make_move_iterator(E), Dest);
216 template<
typename It1,
typename It2>
218 std::uninitialized_copy(I, E, Dest);
224 void grow(
size_t MinSize = 0);
227 void push_back(
const T &Elt) {
228 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
230 ::new ((
void*) this->end()) T(Elt);
234 void push_back(T &&Elt) {
235 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
237 ::new ((
void*) this->end()) T(::std::move(Elt));
248 template <
typename T,
bool isPodLike>
250 if (MinSize > UINT32_MAX)
254 size_t NewCapacity = size_t(
NextPowerOf2(this->capacity() + 2));
255 NewCapacity = (std::min)((std::max)(NewCapacity, MinSize),
size_t(UINT32_MAX));
256 T *NewElts = static_cast<T*>(wpi::safe_malloc(NewCapacity*
sizeof(T)));
262 destroy_range(this->begin(), this->end());
268 this->BeginX = NewElts;
269 this->Capacity = static_cast<unsigned>(NewCapacity);
275 template <
typename T>
281 static void destroy_range(T *, T *) {}
285 template<
typename It1,
typename It2>
293 template<
typename It1,
typename It2>
296 std::uninitialized_copy(I, E, Dest);
301 template <
typename T1,
typename T2>
303 T1 *I, T1 *E, T2 *Dest,
304 typename std::enable_if<std::is_same<
typename std::remove_const<T1>::type,
305 T2>::value>::type * =
nullptr) {
311 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) *
sizeof(T));
316 void grow(
size_t MinSize = 0) { this->grow_pod(MinSize,
sizeof(T)); }
319 void push_back(
const T &Elt) {
320 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
322 memcpy(reinterpret_cast<void *>(this->end()), &Elt,
sizeof(T));
326 void pop_back() { this->
set_size(this->size() - 1); }
331 template <
typename T>
332 class SmallVectorImpl :
public SmallVectorTemplateBase<T> {
333 using SuperClass = SmallVectorTemplateBase<T>;
336 using iterator =
typename SuperClass::iterator;
337 using const_iterator =
typename SuperClass::const_iterator;
338 using size_type =
typename SuperClass::size_type;
342 explicit SmallVectorImpl(
unsigned N)
343 : SmallVectorTemplateBase<T, isPodLike<T>::value>(N) {}
346 SmallVectorImpl(
const SmallVectorImpl &) =
delete;
356 this->destroy_range(this->begin(), this->end());
360 void resize(size_type N) {
361 if (N < this->
size()) {
362 this->destroy_range(this->begin()+N, this->end());
364 }
else if (N > this->size()) {
365 if (this->capacity() < N)
367 for (
auto I = this->end(), E = this->begin() + N; I != E; ++I)
373 void resize(size_type N,
const T &NV) {
374 if (N < this->
size()) {
375 this->destroy_range(this->begin()+N, this->end());
377 }
else if (N > this->size()) {
378 if (this->capacity() < N)
380 std::uninitialized_fill(this->end(), this->begin()+N, NV);
385 void reserve(size_type N) {
386 if (this->capacity() < N)
390 LLVM_NODISCARD T pop_back_val() {
391 T Result = ::std::move(this->back());
396 void swap(SmallVectorImpl &RHS);
399 template <
typename in_iter,
400 typename =
typename std::enable_if<std::is_convertible<
401 typename std::iterator_traits<in_iter>::iterator_category,
402 std::input_iterator_tag>::value>::type>
403 void append(in_iter in_start, in_iter in_end) {
404 size_type NumInputs = std::distance(in_start, in_end);
406 if (NumInputs > this->capacity() - this->size())
407 this->
grow(this->size()+NumInputs);
411 this->
set_size(this->size() + NumInputs);
415 void append(size_type NumInputs,
const T &Elt) {
417 if (NumInputs > this->capacity() - this->size())
418 this->
grow(this->size()+NumInputs);
421 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
422 this->
set_size(this->size() + NumInputs);
425 void append(std::initializer_list<T> IL) {
426 append(IL.begin(), IL.end());
432 void assign(size_type NumElts,
const T &Elt) {
434 if (this->capacity() < NumElts)
437 std::uninitialized_fill(this->begin(), this->end(), Elt);
440 template <
typename in_iter,
441 typename =
typename std::enable_if<std::is_convertible<
442 typename std::iterator_traits<in_iter>::iterator_category,
443 std::input_iterator_tag>::value>::type>
444 void assign(in_iter in_start, in_iter in_end) {
446 append(in_start, in_end);
449 void assign(std::initializer_list<T> IL) {
454 iterator erase(const_iterator CI) {
456 iterator I = const_cast<iterator>(CI);
458 assert(I >= this->begin() &&
"Iterator to erase is out of bounds.");
459 assert(I < this->end() &&
"Erasing at past-the-end iterator.");
463 std::move(I+1, this->end(), I);
469 iterator erase(const_iterator CS, const_iterator CE) {
471 iterator S = const_cast<iterator>(CS);
472 iterator E = const_cast<iterator>(CE);
474 assert(S >= this->begin() &&
"Range to erase is out of bounds.");
475 assert(S <= E &&
"Trying to erase invalid range.");
476 assert(E <= this->end() &&
"Trying to erase past the end.");
480 iterator I = std::move(E, this->end(), S);
482 this->destroy_range(I, this->end());
487 iterator insert(iterator I, T &&Elt) {
488 if (I == this->end()) {
489 this->push_back(::std::move(Elt));
490 return this->end()-1;
493 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
494 assert(I <= this->end() &&
"Inserting past the end of the vector.");
496 if (this->size() >= this->capacity()) {
497 size_t EltNo = I-this->begin();
499 I = this->begin()+EltNo;
502 ::new ((
void*) this->end()) T(::std::move(this->back()));
504 std::move_backward(I, this->end()-1, this->end());
510 if (I <= EltPtr && EltPtr < this->end())
513 *I = ::std::move(*EltPtr);
517 iterator insert(iterator I, const T &Elt) {
518 if (I == this->end()) {
519 this->push_back(Elt);
520 return this->end()-1;
523 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
524 assert(I <= this->end() &&
"Inserting past the end of the vector.");
526 if (this->size() >= this->capacity()) {
527 size_t EltNo = I-this->begin();
529 I = this->begin()+EltNo;
531 ::new ((
void*) this->end()) T(std::move(this->back()));
533 std::move_backward(I, this->end()-1, this->end());
538 const T *EltPtr = &Elt;
539 if (I <= EltPtr && EltPtr < this->end())
546 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
548 size_t InsertElt = I - this->begin();
550 if (I == this->end()) {
551 append(NumToInsert, Elt);
552 return this->begin()+InsertElt;
555 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
556 assert(I <= this->end() &&
"Inserting past the end of the vector.");
559 reserve(this->size() + NumToInsert);
562 I = this->begin()+InsertElt;
568 if (
size_t(this->end()-I) >= NumToInsert) {
569 T *OldEnd = this->end();
570 append(std::move_iterator<iterator>(this->end() - NumToInsert),
571 std::move_iterator<iterator>(this->end()));
574 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
576 std::fill_n(I, NumToInsert, Elt);
584 T *OldEnd = this->end();
585 this->
set_size(this->size() + NumToInsert);
586 size_t NumOverwritten = OldEnd-I;
590 std::fill_n(I, NumOverwritten, Elt);
593 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
597 template <
typename ItTy,
598 typename =
typename std::enable_if<std::is_convertible<
599 typename std::iterator_traits<ItTy>::iterator_category,
600 std::input_iterator_tag>::value>::type>
601 iterator insert(iterator I, ItTy From, ItTy To) {
603 size_t InsertElt = I - this->begin();
605 if (I == this->end()) {
607 return this->begin()+InsertElt;
610 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
611 assert(I <= this->end() &&
"Inserting past the end of the vector.");
613 size_t NumToInsert = std::distance(From, To);
616 reserve(this->size() + NumToInsert);
619 I = this->begin()+InsertElt;
625 if (
size_t(this->end()-I) >= NumToInsert) {
626 T *OldEnd = this->end();
627 append(std::move_iterator<iterator>(this->end() - NumToInsert),
628 std::move_iterator<iterator>(this->end()));
631 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
633 std::copy(From, To, I);
641 T *OldEnd = this->end();
642 this->
set_size(this->size() + NumToInsert);
643 size_t NumOverwritten = OldEnd-I;
647 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
657 void insert(iterator I, std::initializer_list<T> IL) {
658 insert(I, IL.begin(), IL.end());
661 template <
typename... ArgTypes>
void emplace_back(ArgTypes &&... Args) {
662 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
664 ::new ((
void *)this->end()) T(std::forward<ArgTypes>(Args)...);
668 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
670 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
672 bool operator==(const SmallVectorImpl &RHS)
const {
673 if (this->size() != RHS.size())
return false;
674 return std::equal(this->begin(), this->end(), RHS.
begin());
676 bool operator!=(
const SmallVectorImpl &RHS)
const {
677 return !(*
this == RHS);
680 bool operator<(
const SmallVectorImpl &RHS)
const {
681 return std::lexicographical_compare(this->begin(), this->end(),
682 RHS.begin(), RHS.end());
686 template <
typename T>
687 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
688 if (
this == &RHS)
return;
691 if (!this->
isSmall() && !RHS.isSmall()) {
692 std::swap(this->BeginX, RHS.BeginX);
693 std::swap(this->Size, RHS.Size);
694 std::swap(this->Capacity, RHS.Capacity);
697 if (RHS.size() > this->capacity())
698 this->
grow(RHS.size());
699 if (this->size() > RHS.capacity())
700 RHS.grow(this->size());
703 size_t NumShared = this->size();
704 if (NumShared > RHS.size()) NumShared = RHS.size();
705 for (size_type i = 0; i != NumShared; ++i)
706 std::swap((*
this)[i], RHS[i]);
709 if (this->size() > RHS.size()) {
710 size_t EltDiff = this->size() - RHS.size();
712 RHS.set_size(RHS.size() + EltDiff);
713 this->destroy_range(this->begin()+NumShared, this->end());
715 }
else if (RHS.size() > this->size()) {
716 size_t EltDiff = RHS.size() - this->size();
718 this->
set_size(this->size() + EltDiff);
719 this->destroy_range(RHS.begin()+NumShared, RHS.end());
720 RHS.set_size(NumShared);
724 template <
typename T>
725 SmallVectorImpl<T> &SmallVectorImpl<T>::
726 operator=(
const SmallVectorImpl<T> &RHS) {
728 if (
this == &RHS)
return *
this;
732 size_t RHSSize = RHS.size();
733 size_t CurSize = this->size();
734 if (CurSize >= RHSSize) {
738 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
740 NewEnd = this->begin();
743 this->destroy_range(NewEnd, this->end());
753 if (this->capacity() < RHSSize) {
755 this->destroy_range(this->begin(), this->end());
759 }
else if (CurSize) {
761 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
766 this->begin()+CurSize);
773 template <
typename T>
774 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
776 if (
this == &RHS)
return *
this;
779 if (!RHS.isSmall()) {
780 this->destroy_range(this->begin(), this->end());
781 if (!this->
isSmall()) free(this->begin());
782 this->BeginX = RHS.BeginX;
783 this->Size = RHS.Size;
784 this->Capacity = RHS.Capacity;
791 size_t RHSSize = RHS.size();
792 size_t CurSize = this->size();
793 if (CurSize >= RHSSize) {
795 iterator NewEnd = this->begin();
797 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
800 this->destroy_range(NewEnd, this->end());
813 if (this->capacity() < RHSSize) {
815 this->destroy_range(this->begin(), this->end());
819 }
else if (CurSize) {
821 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
826 this->begin()+CurSize);
837 template <
typename T,
unsigned N>
855 template <
typename T,
unsigned N>
862 this->destroy_range(this->begin(), this->end());
865 explicit SmallVector(
size_t Size,
const T &Value = T())
867 this->assign(Size, Value);
870 template <
typename ItTy,
871 typename =
typename std::enable_if<std::is_convertible<
872 typename std::iterator_traits<ItTy>::iterator_category,
873 std::input_iterator_tag>::value>::type>
878 template <
typename RangeTy>
881 this->append(R.begin(), R.end());
918 const SmallVector &operator=(std::initializer_list<T> IL) {
924 template <
typename T,
unsigned N>
926 return X.capacity_in_bytes();
941 template<
typename T,
unsigned N>
949 #endif // LLVM_ADT_SMALLVECTOR_H