14 #ifndef LLVM_ADT_SMALLVECTOR_H
15 #define LLVM_ADT_SMALLVECTOR_H
18 #include "llvm/AlignOf.h"
19 #include "llvm/Compiler.h"
20 #include "llvm/MathExtras.h"
21 #include "llvm/type_traits.h"
27 #include <initializer_list>
36 void *BeginX, *EndX, *CapacityX;
40 : BeginX(FirstEl), EndX(FirstEl), CapacityX((
char*)FirstEl+Size) {}
44 void grow_pod(
void *FirstEl,
size_t MinSizeInBytes,
size_t TSize);
49 return size_t((
char*)EndX - (
char*)BeginX);
54 return size_t((
char*)CapacityX - (
char*)BeginX);
57 bool LLVM_ATTRIBUTE_UNUSED_RESULT empty()
const {
return BeginX == EndX; }
65 template <
typename T,
typename =
void>
80 void grow_pod(
size_t MinSizeInBytes,
size_t TSize) {
87 return BeginX ==
static_cast<const void*
>(&FirstEl);
92 BeginX = EndX = CapacityX = &FirstEl;
95 void setEnd(T *P) { this->EndX = P; }
97 typedef size_t size_type;
98 typedef ptrdiff_t difference_type;
101 typedef const T *const_iterator;
103 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
104 typedef std::reverse_iterator<iterator> reverse_iterator;
106 typedef T &reference;
107 typedef const T &const_reference;
109 typedef const T *const_pointer;
112 iterator begin() {
return (iterator)this->BeginX; }
113 const_iterator begin()
const {
return (const_iterator)this->BeginX; }
114 iterator end() {
return (iterator)this->EndX; }
115 const_iterator end()
const {
return (const_iterator)this->EndX; }
117 iterator capacity_ptr() {
return (iterator)this->CapacityX; }
118 const_iterator capacity_ptr()
const {
return (const_iterator)this->CapacityX;}
122 reverse_iterator rbegin() {
return reverse_iterator(end()); }
123 const_reverse_iterator rbegin()
const{
return const_reverse_iterator(end()); }
124 reverse_iterator rend() {
return reverse_iterator(begin()); }
125 const_reverse_iterator rend()
const {
return const_reverse_iterator(begin());}
127 size_type size()
const {
return end()-begin(); }
128 size_type max_size()
const {
return size_type(-1) /
sizeof(T); }
131 size_t capacity()
const {
return capacity_ptr() - begin(); }
134 pointer
data() {
return pointer(begin()); }
136 const_pointer
data()
const {
return const_pointer(begin()); }
138 reference operator[](size_type idx) {
139 assert(idx < size());
142 const_reference operator[](size_type idx)
const {
143 assert(idx < size());
151 const_reference front()
const {
160 const_reference back()
const {
168 template <
typename T,
bool isPodLike>
173 static void destroy_range(T *S, T *E) {
183 template<
typename It1,
typename It2>
184 static It2
move(It1 I, It1 E, It2 Dest) {
185 for (; I != E; ++I, ++Dest)
186 *Dest = ::std::move(*I);
194 template<
typename It1,
typename It2>
197 *--Dest = ::std::move(*--E);
203 template<
typename It1,
typename It2>
205 for (; I != E; ++I, ++Dest)
206 ::
new ((
void*) &*Dest) T(::std::move(*I));
211 template<
typename It1,
typename It2>
213 std::uninitialized_copy(I, E, Dest);
219 void grow(
size_t MinSize = 0);
222 void push_back(
const T &Elt) {
223 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
225 ::new ((
void*) this->end()) T(Elt);
226 this->setEnd(this->end()+1);
229 void push_back(T &&Elt) {
230 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
232 ::new ((
void*) this->end()) T(::std::
move(Elt));
233 this->setEnd(this->end()+1);
237 this->setEnd(this->end()-1);
243 template <
typename T,
bool isPodLike>
245 size_t CurCapacity = this->
capacity();
246 size_t CurSize = this->size();
248 size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
249 if (NewCapacity < MinSize)
250 NewCapacity = MinSize;
251 T *NewElts =
static_cast<T*
>(malloc(NewCapacity*
sizeof(T)));
257 destroy_range(this->begin(), this->end());
263 this->setEnd(NewElts+CurSize);
264 this->BeginX = NewElts;
265 this->CapacityX = this->begin()+NewCapacity;
271 template <
typename T>
277 static void destroy_range(T *, T *) {}
281 template<
typename It1,
typename It2>
282 static It2
move(It1 I, It1 E, It2 Dest) {
283 return ::std::copy(I, E, Dest);
288 template<
typename It1,
typename It2>
290 return ::std::copy_backward(I, E, Dest);
295 template<
typename It1,
typename It2>
303 template<
typename It1,
typename It2>
306 std::uninitialized_copy(I, E, Dest);
311 template <
typename T1,
typename T2>
313 T1 *I, T1 *E, T2 *Dest,
314 typename std::enable_if<std::is_same<
typename std::remove_const<T1>::type,
315 T2>::value>::type * =
nullptr) {
319 memcpy(Dest, I, (E-I)*
sizeof(T));
324 void grow(
size_t MinSize = 0) {
325 this->grow_pod(MinSize*
sizeof(T),
sizeof(T));
328 void push_back(
const T &Elt) {
329 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
331 memcpy(this->end(), &Elt,
sizeof(T));
332 this->setEnd(this->end()+1);
336 this->setEnd(this->end()-1);
343 template <
typename T>
344 class SmallVectorImpl :
public SmallVectorTemplateBase<T, isPodLike<T>::value> {
345 typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass;
347 SmallVectorImpl(
const SmallVectorImpl&) =
delete;
349 typedef typename SuperClass::iterator iterator;
350 typedef typename SuperClass::size_type size_type;
354 explicit SmallVectorImpl(
unsigned N)
355 : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
361 this->destroy_range(this->begin(), this->end());
370 this->destroy_range(this->begin(), this->end());
371 this->EndX = this->BeginX;
374 void resize(size_type N) {
375 if (N < this->size()) {
376 this->destroy_range(this->begin()+N, this->end());
377 this->setEnd(this->begin()+N);
378 }
else if (N > this->size()) {
381 for (
auto I = this->end(), E = this->begin() + N; I != E; ++I)
383 this->setEnd(this->begin()+N);
387 void resize(size_type N,
const T &NV) {
388 if (N < this->size()) {
389 this->destroy_range(this->begin()+N, this->end());
390 this->setEnd(this->begin()+N);
391 }
else if (N > this->size()) {
394 std::uninitialized_fill(this->end(), this->begin()+N, NV);
395 this->setEnd(this->begin()+N);
399 void reserve(size_type N) {
404 T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
405 T Result = ::std::move(this->back());
410 void swap(SmallVectorImpl &RHS);
413 template<
typename in_iter>
414 void append(in_iter in_start, in_iter in_end) {
415 size_type NumInputs = std::distance(in_start, in_end);
417 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
418 this->
grow(this->size()+NumInputs);
422 this->setEnd(this->end() + NumInputs);
426 void append(size_type NumInputs,
const T &Elt) {
428 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
429 this->
grow(this->size()+NumInputs);
432 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
433 this->setEnd(this->end() + NumInputs);
436 void append(std::initializer_list<T> IL) {
437 append(IL.begin(), IL.end());
440 void assign(size_type NumElts,
const T &Elt) {
444 this->setEnd(this->begin()+NumElts);
445 std::uninitialized_fill(this->begin(), this->end(), Elt);
448 void assign(std::initializer_list<T> IL) {
453 iterator erase(iterator I) {
454 assert(I >= this->begin() &&
"Iterator to erase is out of bounds.");
455 assert(I < this->end() &&
"Erasing at past-the-end iterator.");
459 this->
move(I+1, this->end(), I);
465 iterator erase(iterator S, iterator E) {
466 assert(S >= this->begin() &&
"Range to erase is out of bounds.");
467 assert(S <= E &&
"Trying to erase invalid range.");
468 assert(E <= this->end() &&
"Trying to erase past the end.");
472 iterator I = this->
move(E, this->end(), S);
474 this->destroy_range(I, this->end());
479 iterator insert(iterator I, T &&Elt) {
480 if (I == this->end()) {
481 this->push_back(::std::move(Elt));
482 return this->end()-1;
485 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
486 assert(I <= this->end() &&
"Inserting past the end of the vector.");
488 if (this->EndX >= this->CapacityX) {
489 size_t EltNo = I-this->begin();
491 I = this->begin()+EltNo;
494 ::new ((
void*) this->end()) T(::std::
move(this->back()));
497 this->setEnd(this->end()+1);
502 if (I <= EltPtr && EltPtr < this->EndX)
505 *I = ::std::
move(*EltPtr);
509 iterator insert(iterator I, const T &Elt) {
510 if (I == this->end()) {
511 this->push_back(Elt);
512 return this->end()-1;
515 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
516 assert(I <= this->end() &&
"Inserting past the end of the vector.");
518 if (this->EndX >= this->CapacityX) {
519 size_t EltNo = I-this->begin();
521 I = this->begin()+EltNo;
523 ::new ((
void*) this->end()) T(std::
move(this->back()));
526 this->setEnd(this->end()+1);
530 const T *EltPtr = &Elt;
531 if (I <= EltPtr && EltPtr < this->EndX)
538 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
540 size_t InsertElt = I - this->begin();
542 if (I == this->end()) {
543 append(NumToInsert, Elt);
544 return this->begin()+InsertElt;
547 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
548 assert(I <= this->end() &&
"Inserting past the end of the vector.");
551 reserve(this->size() + NumToInsert);
554 I = this->begin()+InsertElt;
560 if (
size_t(this->end()-I) >= NumToInsert) {
561 T *OldEnd = this->end();
562 append(std::move_iterator<iterator>(this->end() - NumToInsert),
563 std::move_iterator<iterator>(this->end()));
568 std::fill_n(I, NumToInsert, Elt);
576 T *OldEnd = this->end();
577 this->setEnd(this->end() + NumToInsert);
578 size_t NumOverwritten = OldEnd-I;
582 std::fill_n(I, NumOverwritten, Elt);
585 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
589 template<
typename ItTy>
590 iterator insert(iterator I, ItTy From, ItTy To) {
592 size_t InsertElt = I - this->begin();
594 if (I == this->end()) {
596 return this->begin()+InsertElt;
599 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
600 assert(I <= this->end() &&
"Inserting past the end of the vector.");
602 size_t NumToInsert = std::distance(From, To);
605 reserve(this->size() + NumToInsert);
608 I = this->begin()+InsertElt;
614 if (
size_t(this->end()-I) >= NumToInsert) {
615 T *OldEnd = this->end();
616 append(std::move_iterator<iterator>(this->end() - NumToInsert),
617 std::move_iterator<iterator>(this->end()));
622 std::copy(From, To, I);
630 T *OldEnd = this->end();
631 this->setEnd(this->end() + NumToInsert);
632 size_t NumOverwritten = OldEnd-I;
636 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
646 void insert(iterator I, std::initializer_list<T> IL) {
647 insert(I, IL.begin(), IL.end());
650 template <
typename... ArgTypes>
void emplace_back(ArgTypes &&... Args) {
651 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
653 ::new ((
void *)this->end()) T(std::forward<ArgTypes>(Args)...);
654 this->setEnd(this->end() + 1);
657 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
659 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
661 bool operator==(const SmallVectorImpl &RHS)
const {
662 if (this->size() != RHS.size())
return false;
663 return std::equal(this->begin(), this->end(), RHS.begin());
665 bool operator!=(
const SmallVectorImpl &RHS)
const {
666 return !(*
this == RHS);
669 bool operator<(
const SmallVectorImpl &RHS)
const {
670 return std::lexicographical_compare(this->begin(), this->end(),
671 RHS.begin(), RHS.end());
685 this->setEnd(this->begin() + N);
690 template <
typename T>
691 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
692 if (
this == &RHS)
return;
695 if (!this->
isSmall() && !RHS.isSmall()) {
696 std::swap(this->BeginX, RHS.BeginX);
697 std::swap(this->EndX, RHS.EndX);
698 std::swap(this->CapacityX, RHS.CapacityX);
702 this->
grow(RHS.size());
703 if (this->size() > RHS.capacity())
704 RHS.grow(this->size());
707 size_t NumShared = this->size();
708 if (NumShared > RHS.size()) NumShared = RHS.size();
709 for (size_type i = 0; i != NumShared; ++i)
710 std::swap((*
this)[i], RHS[i]);
713 if (this->size() > RHS.size()) {
714 size_t EltDiff = this->size() - RHS.size();
716 RHS.setEnd(RHS.end()+EltDiff);
717 this->destroy_range(this->begin()+NumShared, this->end());
718 this->setEnd(this->begin()+NumShared);
719 }
else if (RHS.size() > this->size()) {
720 size_t EltDiff = RHS.size() - this->size();
722 this->setEnd(this->end() + EltDiff);
723 this->destroy_range(RHS.begin()+NumShared, RHS.end());
724 RHS.setEnd(RHS.begin()+NumShared);
728 template <
typename T>
729 SmallVectorImpl<T> &SmallVectorImpl<T>::
730 operator=(
const SmallVectorImpl<T> &RHS) {
732 if (
this == &RHS)
return *
this;
736 size_t RHSSize = RHS.size();
737 size_t CurSize = this->size();
738 if (CurSize >= RHSSize) {
742 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
744 NewEnd = this->begin();
747 this->destroy_range(NewEnd, this->end());
750 this->setEnd(NewEnd);
759 this->destroy_range(this->begin(), this->end());
760 this->setEnd(this->begin());
763 }
else if (CurSize) {
765 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
770 this->begin()+CurSize);
773 this->setEnd(this->begin()+RHSSize);
777 template <
typename T>
778 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
780 if (
this == &RHS)
return *
this;
783 if (!RHS.isSmall()) {
784 this->destroy_range(this->begin(), this->end());
785 if (!this->
isSmall()) free(this->begin());
786 this->BeginX = RHS.BeginX;
787 this->EndX = RHS.EndX;
788 this->CapacityX = RHS.CapacityX;
795 size_t RHSSize = RHS.size();
796 size_t CurSize = this->size();
797 if (CurSize >= RHSSize) {
799 iterator NewEnd = this->begin();
801 NewEnd = this->
move(RHS.begin(), RHS.end(), NewEnd);
804 this->destroy_range(NewEnd, this->end());
805 this->setEnd(NewEnd);
819 this->destroy_range(this->begin(), this->end());
820 this->setEnd(this->begin());
823 }
else if (CurSize) {
825 this->
move(RHS.begin(), RHS.begin()+CurSize, this->begin());
830 this->begin()+CurSize);
833 this->setEnd(this->begin()+RHSSize);
843 template <
typename T,
unsigned N>
844 struct SmallVectorStorage {
845 typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
858 template <
typename T,
unsigned N>
866 explicit SmallVector(
size_t Size,
const T &Value = T())
868 this->assign(Size, Value);
871 template<
typename ItTy>
876 template <
typename RangeTy>
879 this->append(R.begin(), R.end());
916 const SmallVector &operator=(std::initializer_list<T> IL) {
922 template<
typename T,
unsigned N>
938 template<
typename T,
unsigned N>
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:304
size_t capacity() const
Return the total number of elements in the currently allocated buffer.
Definition: SmallVector.h:131
static It2 move_backward(It1 I, It1 E, It2 Dest)
Use move-assignment to move the range [I, E) onto the objects ending at "Dest", moving objects in rev...
Definition: SmallVector.h:289
static It2 move(It1 I, It1 E, It2 Dest)
Use move-assignment to move the range [I, E) onto the objects starting with "Dest".
Definition: SmallVector.h:184
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
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:204
void append(size_type NumInputs, const T &Elt)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:426
size_t capacity_in_bytes() const
capacity_in_bytes - This returns capacity()*sizeof(T).
Definition: SmallVector.h:53
static It2 move_backward(It1 I, It1 E, It2 Dest)
Use move-assignment to move the range [I, E) onto the objects ending at "Dest", moving objects in rev...
Definition: SmallVector.h:195
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:212
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: StringRef.h:23
SmallVectorTemplateBase<isPodLike = false> - This is where we put method implementations that are desig...
Definition: SmallVector.h:169
static It2 move(It1 I, It1 E, It2 Dest)
Use move-assignment to move the range [I, E) onto the objects starting with "Dest".
Definition: SmallVector.h:282
void grow(size_t MinSize=0)
Grow the allocated memory (without initializing new elements), doubling the size of the allocated mem...
Definition: SmallVector.h:244
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:414
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:859
bool isSmall() const
Return true if this is a smallvector which has not had dynamic memory allocated for it...
Definition: SmallVector.h:86
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:324
A range adaptor for a pair of iterators.
Definition: iterator_range.h:31
This is the part of SmallVectorTemplateBase which does not depend on whether the type T is a POD...
Definition: SmallVector.h:66
void set_size(size_type N)
Set the array size to N, which the current array must have enough capacity for.
Definition: SmallVector.h:683
pointer data()
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:134
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:312
This is all the non-templated stuff common to all SmallVectors.
Definition: SmallVector.h:34
size_t size_in_bytes() const
This returns size()*sizeof(T).
Definition: SmallVector.h:48
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:296
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 ...
Definition: SmallVector.cpp:19
Storage for the SmallVector elements which aren't contained in SmallVectorTemplateCommon.
Definition: SmallVector.h:60
void resetToSmall()
Put this vector in a state of being small.
Definition: SmallVector.h:91
const_pointer data() const
Return a pointer to the vector's buffer, even if empty().
Definition: SmallVector.h:136