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) {
182 template<
typename It1,
typename It2>
184 std::uninitialized_copy(std::make_move_iterator(I),
185 std::make_move_iterator(E), Dest);
190 template<
typename It1,
typename It2>
192 std::uninitialized_copy(I, E, Dest);
198 void grow(
size_t MinSize = 0);
201 void push_back(
const T &Elt) {
202 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
204 ::new ((
void*) this->end()) T(Elt);
205 this->setEnd(this->end()+1);
208 void push_back(T &&Elt) {
209 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
211 ::new ((
void*) this->end()) T(::std::move(Elt));
212 this->setEnd(this->end()+1);
216 this->setEnd(this->end()-1);
222 template <
typename T,
bool isPodLike>
224 size_t CurCapacity = this->capacity();
225 size_t CurSize = this->size();
227 size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
228 if (NewCapacity < MinSize)
229 NewCapacity = MinSize;
230 T *NewElts =
static_cast<T*
>(malloc(NewCapacity*
sizeof(T)));
233 this->uninitialized_move(this->begin(), this->end(), NewElts);
236 destroy_range(this->begin(), this->end());
239 if (!this->isSmall())
242 this->setEnd(NewElts+CurSize);
243 this->BeginX = NewElts;
244 this->CapacityX = this->begin()+NewCapacity;
250 template <
typename T>
256 static void destroy_range(T *, T *) {}
260 template<
typename It1,
typename It2>
263 uninitialized_copy(I, E, Dest);
268 template<
typename It1,
typename It2>
271 std::uninitialized_copy(I, E, Dest);
276 template <
typename T1,
typename T2>
278 T1 *I, T1 *E, T2 *Dest,
279 typename std::enable_if<std::is_same<
typename std::remove_const<T1>::type,
280 T2>::value>::type * =
nullptr) {
286 memcpy(Dest, I, (E - I) *
sizeof(T));
291 void grow(
size_t MinSize = 0) {
292 this->
grow_pod(MinSize*
sizeof(T),
sizeof(T));
295 void push_back(
const T &Elt) {
296 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
298 memcpy(this->end(), &Elt,
sizeof(T));
299 this->setEnd(this->end()+1);
303 this->setEnd(this->end()-1);
310 template <
typename T>
316 typedef typename SuperClass::iterator iterator;
317 typedef typename SuperClass::const_iterator const_iterator;
318 typedef typename SuperClass::size_type size_type;
329 this->destroy_range(this->begin(), this->end());
332 if (!this->isSmall())
338 this->destroy_range(this->begin(), this->end());
339 this->EndX = this->BeginX;
342 void resize(size_type N) {
343 if (N < this->size()) {
344 this->destroy_range(this->begin()+N, this->end());
345 this->setEnd(this->begin()+N);
346 }
else if (N > this->size()) {
347 if (this->capacity() < N)
349 for (
auto I = this->end(), E = this->begin() + N; I != E; ++I)
351 this->setEnd(this->begin()+N);
355 void resize(size_type N,
const T &NV) {
356 if (N < this->size()) {
357 this->destroy_range(this->begin()+N, this->end());
358 this->setEnd(this->begin()+N);
359 }
else if (N > this->size()) {
360 if (this->capacity() < N)
362 std::uninitialized_fill(this->end(), this->begin()+N, NV);
363 this->setEnd(this->begin()+N);
367 void reserve(size_type N) {
368 if (this->capacity() < N)
372 T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
373 T Result = ::std::move(this->back());
381 template<
typename in_iter>
382 void append(in_iter in_start, in_iter in_end) {
383 size_type NumInputs = std::distance(in_start, in_end);
385 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
386 this->grow(this->size()+NumInputs);
389 this->uninitialized_copy(in_start, in_end, this->end());
390 this->setEnd(this->end() + NumInputs);
394 void append(size_type NumInputs,
const T &Elt) {
396 if (NumInputs > size_type(this->capacity_ptr()-this->end()))
397 this->grow(this->size()+NumInputs);
400 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
401 this->setEnd(this->end() + NumInputs);
404 void append(std::initializer_list<T> IL) {
405 append(IL.begin(), IL.end());
408 void assign(size_type NumElts,
const T &Elt) {
410 if (this->capacity() < NumElts)
412 this->setEnd(this->begin()+NumElts);
413 std::uninitialized_fill(this->begin(), this->end(), Elt);
416 void assign(std::initializer_list<T> IL) {
421 iterator erase(const_iterator CI) {
423 iterator I =
const_cast<iterator
>(CI);
425 assert(I >= this->begin() &&
"Iterator to erase is out of bounds.");
426 assert(I < this->end() &&
"Erasing at past-the-end iterator.");
430 std::move(I+1, this->end(), I);
436 iterator erase(const_iterator CS, const_iterator CE) {
438 iterator S =
const_cast<iterator
>(CS);
439 iterator E =
const_cast<iterator
>(CE);
441 assert(S >= this->begin() &&
"Range to erase is out of bounds.");
442 assert(S <= E &&
"Trying to erase invalid range.");
443 assert(E <= this->end() &&
"Trying to erase past the end.");
447 iterator I = std::move(E, this->end(), S);
449 this->destroy_range(I, this->end());
454 iterator insert(iterator I, T &&Elt) {
455 if (I == this->end()) {
456 this->push_back(::std::move(Elt));
457 return this->end()-1;
460 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
461 assert(I <= this->end() &&
"Inserting past the end of the vector.");
463 if (this->EndX >= this->CapacityX) {
464 size_t EltNo = I-this->begin();
466 I = this->begin()+EltNo;
469 ::new ((
void*) this->end()) T(::std::move(this->back()));
471 std::move_backward(I, this->end()-1, this->end());
472 this->setEnd(this->end()+1);
477 if (I <= EltPtr && EltPtr < this->EndX)
480 *I = ::std::move(*EltPtr);
484 iterator insert(iterator I,
const T &Elt) {
485 if (I == this->end()) {
486 this->push_back(Elt);
487 return this->end()-1;
490 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
491 assert(I <= this->end() &&
"Inserting past the end of the vector.");
493 if (this->EndX >= this->CapacityX) {
494 size_t EltNo = I-this->begin();
496 I = this->begin()+EltNo;
498 ::new ((
void*) this->end()) T(std::move(this->back()));
500 std::move_backward(I, this->end()-1, this->end());
501 this->setEnd(this->end()+1);
505 const T *EltPtr = &Elt;
506 if (I <= EltPtr && EltPtr < this->EndX)
513 iterator insert(iterator I, size_type NumToInsert,
const T &Elt) {
515 size_t InsertElt = I - this->begin();
517 if (I == this->end()) {
518 append(NumToInsert, Elt);
519 return this->begin()+InsertElt;
522 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
523 assert(I <= this->end() &&
"Inserting past the end of the vector.");
526 reserve(this->size() + NumToInsert);
529 I = this->begin()+InsertElt;
535 if (
size_t(this->end()-I) >= NumToInsert) {
536 T *OldEnd = this->end();
537 append(std::move_iterator<iterator>(this->end() - NumToInsert),
538 std::move_iterator<iterator>(this->end()));
541 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
543 std::fill_n(I, NumToInsert, Elt);
551 T *OldEnd = this->end();
552 this->setEnd(this->end() + NumToInsert);
553 size_t NumOverwritten = OldEnd-I;
554 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
557 std::fill_n(I, NumOverwritten, Elt);
560 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
564 template<
typename ItTy>
565 iterator insert(iterator I, ItTy From, ItTy To) {
567 size_t InsertElt = I - this->begin();
569 if (I == this->end()) {
571 return this->begin()+InsertElt;
574 assert(I >= this->begin() &&
"Insertion iterator is out of bounds.");
575 assert(I <= this->end() &&
"Inserting past the end of the vector.");
577 size_t NumToInsert = std::distance(From, To);
580 reserve(this->size() + NumToInsert);
583 I = this->begin()+InsertElt;
589 if (
size_t(this->end()-I) >= NumToInsert) {
590 T *OldEnd = this->end();
591 append(std::move_iterator<iterator>(this->end() - NumToInsert),
592 std::move_iterator<iterator>(this->end()));
595 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
597 std::copy(From, To, I);
605 T *OldEnd = this->end();
606 this->setEnd(this->end() + NumToInsert);
607 size_t NumOverwritten = OldEnd-I;
608 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
611 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
617 this->uninitialized_copy(From, To, OldEnd);
621 void insert(iterator I, std::initializer_list<T> IL) {
622 insert(I, IL.begin(), IL.end());
625 template <
typename... ArgTypes>
void emplace_back(ArgTypes &&... Args) {
626 if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
628 ::new ((
void *)this->end()) T(std::forward<ArgTypes>(Args)...);
629 this->setEnd(this->end() + 1);
637 if (this->size() != RHS.size())
return false;
638 return std::equal(this->begin(), this->end(), RHS.begin());
641 return !(*
this == RHS);
645 return std::lexicographical_compare(this->begin(), this->end(),
646 RHS.begin(), RHS.end());
659 assert(N <= this->capacity());
660 this->setEnd(this->begin() + N);
665 template <
typename T>
667 if (
this == &RHS)
return;
670 if (!this->isSmall() && !RHS.
isSmall()) {
671 std::swap(this->BeginX, RHS.BeginX);
672 std::swap(this->EndX, RHS.EndX);
673 std::swap(this->CapacityX, RHS.CapacityX);
676 if (RHS.size() > this->capacity())
677 this->grow(RHS.size());
679 RHS.
grow(this->size());
682 size_t NumShared = this->size();
683 if (NumShared > RHS.size()) NumShared = RHS.size();
684 for (size_type i = 0; i != NumShared; ++i)
685 std::swap((*
this)[i], RHS[i]);
688 if (this->size() > RHS.size()) {
689 size_t EltDiff = this->size() - RHS.size();
690 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
691 RHS.setEnd(RHS.end()+EltDiff);
692 this->destroy_range(this->begin()+NumShared, this->end());
693 this->setEnd(this->begin()+NumShared);
694 }
else if (RHS.size() > this->size()) {
695 size_t EltDiff = RHS.size() - this->size();
696 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
697 this->setEnd(this->end() + EltDiff);
698 this->destroy_range(RHS.begin()+NumShared, RHS.end());
699 RHS.setEnd(RHS.begin()+NumShared);
703 template <
typename T>
707 if (
this == &RHS)
return *
this;
711 size_t RHSSize = RHS.size();
712 size_t CurSize = this->size();
713 if (CurSize >= RHSSize) {
717 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
719 NewEnd = this->begin();
722 this->destroy_range(NewEnd, this->end());
725 this->setEnd(NewEnd);
732 if (this->capacity() < RHSSize) {
734 this->destroy_range(this->begin(), this->end());
735 this->setEnd(this->begin());
738 }
else if (CurSize) {
740 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
744 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
745 this->begin()+CurSize);
748 this->setEnd(this->begin()+RHSSize);
752 template <
typename T>
755 if (
this == &RHS)
return *
this;
759 this->destroy_range(this->begin(), this->end());
760 if (!this->isSmall()) free(this->begin());
761 this->BeginX = RHS.BeginX;
762 this->EndX = RHS.EndX;
763 this->CapacityX = RHS.CapacityX;
770 size_t RHSSize = RHS.size();
771 size_t CurSize = this->size();
772 if (CurSize >= RHSSize) {
774 iterator NewEnd = this->begin();
776 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
779 this->destroy_range(NewEnd, this->end());
780 this->setEnd(NewEnd);
792 if (this->capacity() < RHSSize) {
794 this->destroy_range(this->begin(), this->end());
795 this->setEnd(this->begin());
798 }
else if (CurSize) {
800 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
804 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
805 this->begin()+CurSize);
808 this->setEnd(this->begin()+RHSSize);
818 template <
typename T,
unsigned N>
833 template <
typename T,
unsigned N>
841 explicit SmallVector(
size_t Size,
const T &Value = T())
843 this->assign(Size, Value);
846 template<
typename ItTy>
851 template <
typename RangeTy>
854 this->append(R.begin(), R.end());
866 const SmallVector &operator=(
const SmallVector &RHS) {
876 const SmallVector &operator=(SmallVector &&RHS) {
891 const SmallVector &operator=(std::initializer_list<T> IL) {
897 template<
typename T,
unsigned N>
913 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:269
size_t capacity() const
Return the total number of elements in the currently allocated buffer.
Definition: SmallVector.h:131
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:183
void append(size_type NumInputs, const T &Elt)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:394
size_t capacity_in_bytes() const
capacity_in_bytes - This returns capacity()*sizeof(T).
Definition: SmallVector.h:53
Definition: json.cpp:1170
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:191
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: WindowsSupport.h:184
SmallVectorTemplateBase<isPodLike = false> - This is where we put method implementations that are des...
Definition: SmallVector.h:169
void grow(size_t MinSize=0)
Grow the allocated memory (without initializing new elements), doubling the size of the allocated mem...
Definition: SmallVector.h:223
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:382
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:834
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:291
A range adaptor for a pair of iterators.
Definition: iterator_range.h:32
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:658
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:277
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:261
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