WPILibC++  unspecified
SmallVector.h
1 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the SmallVector class.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_SMALLVECTOR_H
15 #define LLVM_ADT_SMALLVECTOR_H
16 
17 #include "llvm/iterator_range.h"
18 #include "llvm/AlignOf.h"
19 #include "llvm/Compiler.h"
20 #include "llvm/MathExtras.h"
21 #include "llvm/type_traits.h"
22 #include <algorithm>
23 #include <cassert>
24 #include <cstddef>
25 #include <cstdlib>
26 #include <cstring>
27 #include <initializer_list>
28 #include <iterator>
29 #include <memory>
30 
31 namespace llvm {
32 
35 protected:
36  void *BeginX, *EndX, *CapacityX;
37 
38 protected:
39  SmallVectorBase(void *FirstEl, size_t Size)
40  : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
41 
44  void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize);
45 
46 public:
48  size_t size_in_bytes() const {
49  return size_t((char*)EndX - (char*)BeginX);
50  }
51 
53  size_t capacity_in_bytes() const {
54  return size_t((char*)CapacityX - (char*)BeginX);
55  }
56 
57  bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return BeginX == EndX; }
58 };
59 
60 template <typename T, unsigned N> struct SmallVectorStorage;
61 
65 template <typename T, typename = void>
67 private:
68  template <typename, unsigned> friend struct SmallVectorStorage;
69 
70  // Allocate raw space for N elements of type T. If T has a ctor or dtor, we
71  // don't want it to be automatically run, so we need to represent the space as
72  // something else. Use an array of char of sufficient alignment.
74  U FirstEl;
75  // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
76 
77 protected:
78  SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
79 
80  void grow_pod(size_t MinSizeInBytes, size_t TSize) {
81  SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
82  }
83 
86  bool isSmall() const {
87  return BeginX == static_cast<const void*>(&FirstEl);
88  }
89 
91  void resetToSmall() {
92  BeginX = EndX = CapacityX = &FirstEl;
93  }
94 
95  void setEnd(T *P) { this->EndX = P; }
96 public:
97  typedef size_t size_type;
98  typedef ptrdiff_t difference_type;
99  typedef T value_type;
100  typedef T *iterator;
101  typedef const T *const_iterator;
102 
103  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
104  typedef std::reverse_iterator<iterator> reverse_iterator;
105 
106  typedef T &reference;
107  typedef const T &const_reference;
108  typedef T *pointer;
109  typedef const T *const_pointer;
110 
111  // forward iterator creation methods.
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; }
116 protected:
117  iterator capacity_ptr() { return (iterator)this->CapacityX; }
118  const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
119 public:
120 
121  // reverse iterator creation methods.
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());}
126 
127  size_type size() const { return end()-begin(); }
128  size_type max_size() const { return size_type(-1) / sizeof(T); }
129 
131  size_t capacity() const { return capacity_ptr() - begin(); }
132 
134  pointer data() { return pointer(begin()); }
136  const_pointer data() const { return const_pointer(begin()); }
137 
138  reference operator[](size_type idx) {
139  assert(idx < size());
140  return begin()[idx];
141  }
142  const_reference operator[](size_type idx) const {
143  assert(idx < size());
144  return begin()[idx];
145  }
146 
147  reference front() {
148  assert(!empty());
149  return begin()[0];
150  }
151  const_reference front() const {
152  assert(!empty());
153  return begin()[0];
154  }
155 
156  reference back() {
157  assert(!empty());
158  return end()[-1];
159  }
160  const_reference back() const {
161  assert(!empty());
162  return end()[-1];
163  }
164 };
165 
168 template <typename T, bool isPodLike>
170 protected:
172 
173  static void destroy_range(T *S, T *E) {
174  while (S != E) {
175  --E;
176  E->~T();
177  }
178  }
179 
182  template<typename It1, typename It2>
183  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
184  std::uninitialized_copy(std::make_move_iterator(I),
185  std::make_move_iterator(E), Dest);
186  }
187 
190  template<typename It1, typename It2>
191  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
192  std::uninitialized_copy(I, E, Dest);
193  }
194 
198  void grow(size_t MinSize = 0);
199 
200 public:
201  void push_back(const T &Elt) {
202  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
203  this->grow();
204  ::new ((void*) this->end()) T(Elt);
205  this->setEnd(this->end()+1);
206  }
207 
208  void push_back(T &&Elt) {
209  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
210  this->grow();
211  ::new ((void*) this->end()) T(::std::move(Elt));
212  this->setEnd(this->end()+1);
213  }
214 
215  void pop_back() {
216  this->setEnd(this->end()-1);
217  this->end()->~T();
218  }
219 };
220 
221 // Define this out-of-line to dissuade the C++ compiler from inlining it.
222 template <typename T, bool isPodLike>
224  size_t CurCapacity = this->capacity();
225  size_t CurSize = this->size();
226  // Always grow, even from zero.
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)));
231 
232  // Move the elements over.
233  this->uninitialized_move(this->begin(), this->end(), NewElts);
234 
235  // Destroy the original elements.
236  destroy_range(this->begin(), this->end());
237 
238  // If this wasn't grown from the inline copy, deallocate the old space.
239  if (!this->isSmall())
240  free(this->begin());
241 
242  this->setEnd(NewElts+CurSize);
243  this->BeginX = NewElts;
244  this->CapacityX = this->begin()+NewCapacity;
245 }
246 
247 
250 template <typename T>
252 protected:
254 
255  // No need to do a destroy loop for POD's.
256  static void destroy_range(T *, T *) {}
257 
260  template<typename It1, typename It2>
261  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
262  // Just do a copy.
263  uninitialized_copy(I, E, Dest);
264  }
265 
268  template<typename It1, typename It2>
269  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
270  // Arbitrary iterator types; just use the basic implementation.
271  std::uninitialized_copy(I, E, Dest);
272  }
273 
276  template <typename T1, typename T2>
277  static void uninitialized_copy(
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) {
281  // Use memcpy for PODs iterated by pointers (which includes SmallVector
282  // iterators): std::uninitialized_copy optimizes to memmove, but we can
283  // use memcpy here. Note that I and E are iterators and thus might be
284  // invalid for memcpy if they are equal.
285  if (I != E)
286  memcpy(Dest, I, (E - I) * sizeof(T));
287  }
288 
291  void grow(size_t MinSize = 0) {
292  this->grow_pod(MinSize*sizeof(T), sizeof(T));
293  }
294 public:
295  void push_back(const T &Elt) {
296  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
297  this->grow();
298  memcpy(this->end(), &Elt, sizeof(T));
299  this->setEnd(this->end()+1);
300  }
301 
302  void pop_back() {
303  this->setEnd(this->end()-1);
304  }
305 };
306 
307 
310 template <typename T>
311 class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
313 
314  SmallVectorImpl(const SmallVectorImpl&) = delete;
315 public:
316  typedef typename SuperClass::iterator iterator;
317  typedef typename SuperClass::const_iterator const_iterator;
318  typedef typename SuperClass::size_type size_type;
319 
320 protected:
321  // Default ctor - Initialize to empty.
322  explicit SmallVectorImpl(unsigned N)
324  }
325 
326 public:
327  ~SmallVectorImpl() {
328  // Destroy the constructed elements in the vector.
329  this->destroy_range(this->begin(), this->end());
330 
331  // If this wasn't grown from the inline copy, deallocate the old space.
332  if (!this->isSmall())
333  free(this->begin());
334  }
335 
336 
337  void clear() {
338  this->destroy_range(this->begin(), this->end());
339  this->EndX = this->BeginX;
340  }
341 
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)
348  this->grow(N);
349  for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
350  new (&*I) T();
351  this->setEnd(this->begin()+N);
352  }
353  }
354 
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)
361  this->grow(N);
362  std::uninitialized_fill(this->end(), this->begin()+N, NV);
363  this->setEnd(this->begin()+N);
364  }
365  }
366 
367  void reserve(size_type N) {
368  if (this->capacity() < N)
369  this->grow(N);
370  }
371 
372  T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
373  T Result = ::std::move(this->back());
374  this->pop_back();
375  return Result;
376  }
377 
378  void swap(SmallVectorImpl &RHS);
379 
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);
384  // Grow allocated space if needed.
385  if (NumInputs > size_type(this->capacity_ptr()-this->end()))
386  this->grow(this->size()+NumInputs);
387 
388  // Copy the new elements over.
389  this->uninitialized_copy(in_start, in_end, this->end());
390  this->setEnd(this->end() + NumInputs);
391  }
392 
394  void append(size_type NumInputs, const T &Elt) {
395  // Grow allocated space if needed.
396  if (NumInputs > size_type(this->capacity_ptr()-this->end()))
397  this->grow(this->size()+NumInputs);
398 
399  // Copy the new elements over.
400  std::uninitialized_fill_n(this->end(), NumInputs, Elt);
401  this->setEnd(this->end() + NumInputs);
402  }
403 
404  void append(std::initializer_list<T> IL) {
405  append(IL.begin(), IL.end());
406  }
407 
408  void assign(size_type NumElts, const T &Elt) {
409  clear();
410  if (this->capacity() < NumElts)
411  this->grow(NumElts);
412  this->setEnd(this->begin()+NumElts);
413  std::uninitialized_fill(this->begin(), this->end(), Elt);
414  }
415 
416  void assign(std::initializer_list<T> IL) {
417  clear();
418  append(IL);
419  }
420 
421  iterator erase(const_iterator CI) {
422  // Just cast away constness because this is a non-const member function.
423  iterator I = const_cast<iterator>(CI);
424 
425  assert(I >= this->begin() && "Iterator to erase is out of bounds.");
426  assert(I < this->end() && "Erasing at past-the-end iterator.");
427 
428  iterator N = I;
429  // Shift all elts down one.
430  std::move(I+1, this->end(), I);
431  // Drop the last elt.
432  this->pop_back();
433  return(N);
434  }
435 
436  iterator erase(const_iterator CS, const_iterator CE) {
437  // Just cast away constness because this is a non-const member function.
438  iterator S = const_cast<iterator>(CS);
439  iterator E = const_cast<iterator>(CE);
440 
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.");
444 
445  iterator N = S;
446  // Shift all elts down.
447  iterator I = std::move(E, this->end(), S);
448  // Drop the last elts.
449  this->destroy_range(I, this->end());
450  this->setEnd(I);
451  return(N);
452  }
453 
454  iterator insert(iterator I, T &&Elt) {
455  if (I == this->end()) { // Important special case for empty vector.
456  this->push_back(::std::move(Elt));
457  return this->end()-1;
458  }
459 
460  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
461  assert(I <= this->end() && "Inserting past the end of the vector.");
462 
463  if (this->EndX >= this->CapacityX) {
464  size_t EltNo = I-this->begin();
465  this->grow();
466  I = this->begin()+EltNo;
467  }
468 
469  ::new ((void*) this->end()) T(::std::move(this->back()));
470  // Push everything else over.
471  std::move_backward(I, this->end()-1, this->end());
472  this->setEnd(this->end()+1);
473 
474  // If we just moved the element we're inserting, be sure to update
475  // the reference.
476  T *EltPtr = &Elt;
477  if (I <= EltPtr && EltPtr < this->EndX)
478  ++EltPtr;
479 
480  *I = ::std::move(*EltPtr);
481  return I;
482  }
483 
484  iterator insert(iterator I, const T &Elt) {
485  if (I == this->end()) { // Important special case for empty vector.
486  this->push_back(Elt);
487  return this->end()-1;
488  }
489 
490  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
491  assert(I <= this->end() && "Inserting past the end of the vector.");
492 
493  if (this->EndX >= this->CapacityX) {
494  size_t EltNo = I-this->begin();
495  this->grow();
496  I = this->begin()+EltNo;
497  }
498  ::new ((void*) this->end()) T(std::move(this->back()));
499  // Push everything else over.
500  std::move_backward(I, this->end()-1, this->end());
501  this->setEnd(this->end()+1);
502 
503  // If we just moved the element we're inserting, be sure to update
504  // the reference.
505  const T *EltPtr = &Elt;
506  if (I <= EltPtr && EltPtr < this->EndX)
507  ++EltPtr;
508 
509  *I = *EltPtr;
510  return I;
511  }
512 
513  iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
514  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
515  size_t InsertElt = I - this->begin();
516 
517  if (I == this->end()) { // Important special case for empty vector.
518  append(NumToInsert, Elt);
519  return this->begin()+InsertElt;
520  }
521 
522  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
523  assert(I <= this->end() && "Inserting past the end of the vector.");
524 
525  // Ensure there is enough space.
526  reserve(this->size() + NumToInsert);
527 
528  // Uninvalidate the iterator.
529  I = this->begin()+InsertElt;
530 
531  // If there are more elements between the insertion point and the end of the
532  // range than there are being inserted, we can use a simple approach to
533  // insertion. Since we already reserved space, we know that this won't
534  // reallocate the vector.
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()));
539 
540  // Copy the existing elements that get replaced.
541  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
542 
543  std::fill_n(I, NumToInsert, Elt);
544  return I;
545  }
546 
547  // Otherwise, we're inserting more elements than exist already, and we're
548  // not inserting at the end.
549 
550  // Move over the elements that we're about to overwrite.
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);
555 
556  // Replace the overwritten part.
557  std::fill_n(I, NumOverwritten, Elt);
558 
559  // Insert the non-overwritten middle part.
560  std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
561  return I;
562  }
563 
564  template<typename ItTy>
565  iterator insert(iterator I, ItTy From, ItTy To) {
566  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
567  size_t InsertElt = I - this->begin();
568 
569  if (I == this->end()) { // Important special case for empty vector.
570  append(From, To);
571  return this->begin()+InsertElt;
572  }
573 
574  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
575  assert(I <= this->end() && "Inserting past the end of the vector.");
576 
577  size_t NumToInsert = std::distance(From, To);
578 
579  // Ensure there is enough space.
580  reserve(this->size() + NumToInsert);
581 
582  // Uninvalidate the iterator.
583  I = this->begin()+InsertElt;
584 
585  // If there are more elements between the insertion point and the end of the
586  // range than there are being inserted, we can use a simple approach to
587  // insertion. Since we already reserved space, we know that this won't
588  // reallocate the vector.
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()));
593 
594  // Copy the existing elements that get replaced.
595  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
596 
597  std::copy(From, To, I);
598  return I;
599  }
600 
601  // Otherwise, we're inserting more elements than exist already, and we're
602  // not inserting at the end.
603 
604  // Move over the elements that we're about to overwrite.
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);
609 
610  // Replace the overwritten part.
611  for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
612  *J = *From;
613  ++J; ++From;
614  }
615 
616  // Insert the non-overwritten middle part.
617  this->uninitialized_copy(From, To, OldEnd);
618  return I;
619  }
620 
621  void insert(iterator I, std::initializer_list<T> IL) {
622  insert(I, IL.begin(), IL.end());
623  }
624 
625  template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
626  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
627  this->grow();
628  ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
629  this->setEnd(this->end() + 1);
630  }
631 
632  SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
633 
634  SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
635 
636  bool operator==(const SmallVectorImpl &RHS) const {
637  if (this->size() != RHS.size()) return false;
638  return std::equal(this->begin(), this->end(), RHS.begin());
639  }
640  bool operator!=(const SmallVectorImpl &RHS) const {
641  return !(*this == RHS);
642  }
643 
644  bool operator<(const SmallVectorImpl &RHS) const {
645  return std::lexicographical_compare(this->begin(), this->end(),
646  RHS.begin(), RHS.end());
647  }
648 
658  void set_size(size_type N) {
659  assert(N <= this->capacity());
660  this->setEnd(this->begin() + N);
661  }
662 };
663 
664 
665 template <typename T>
667  if (this == &RHS) return;
668 
669  // We can only avoid copying elements if neither vector is small.
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);
674  return;
675  }
676  if (RHS.size() > this->capacity())
677  this->grow(RHS.size());
678  if (this->size() > RHS.capacity())
679  RHS.grow(this->size());
680 
681  // Swap the shared elements.
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]);
686 
687  // Copy over the extra elts.
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);
700  }
701 }
702 
703 template <typename T>
705  operator=(const SmallVectorImpl<T> &RHS) {
706  // Avoid self-assignment.
707  if (this == &RHS) return *this;
708 
709  // If we already have sufficient space, assign the common elements, then
710  // destroy any excess.
711  size_t RHSSize = RHS.size();
712  size_t CurSize = this->size();
713  if (CurSize >= RHSSize) {
714  // Assign common elements.
715  iterator NewEnd;
716  if (RHSSize)
717  NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
718  else
719  NewEnd = this->begin();
720 
721  // Destroy excess elements.
722  this->destroy_range(NewEnd, this->end());
723 
724  // Trim.
725  this->setEnd(NewEnd);
726  return *this;
727  }
728 
729  // If we have to grow to have enough elements, destroy the current elements.
730  // This allows us to avoid copying them during the grow.
731  // FIXME: don't do this if they're efficiently moveable.
732  if (this->capacity() < RHSSize) {
733  // Destroy current elements.
734  this->destroy_range(this->begin(), this->end());
735  this->setEnd(this->begin());
736  CurSize = 0;
737  this->grow(RHSSize);
738  } else if (CurSize) {
739  // Otherwise, use assignment for the already-constructed elements.
740  std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
741  }
742 
743  // Copy construct the new elements in place.
744  this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
745  this->begin()+CurSize);
746 
747  // Set end.
748  this->setEnd(this->begin()+RHSSize);
749  return *this;
750 }
751 
752 template <typename T>
754  // Avoid self-assignment.
755  if (this == &RHS) return *this;
756 
757  // If the RHS isn't small, clear this vector and then steal its buffer.
758  if (!RHS.isSmall()) {
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;
764  RHS.resetToSmall();
765  return *this;
766  }
767 
768  // If we already have sufficient space, assign the common elements, then
769  // destroy any excess.
770  size_t RHSSize = RHS.size();
771  size_t CurSize = this->size();
772  if (CurSize >= RHSSize) {
773  // Assign common elements.
774  iterator NewEnd = this->begin();
775  if (RHSSize)
776  NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
777 
778  // Destroy excess elements and trim the bounds.
779  this->destroy_range(NewEnd, this->end());
780  this->setEnd(NewEnd);
781 
782  // Clear the RHS.
783  RHS.clear();
784 
785  return *this;
786  }
787 
788  // If we have to grow to have enough elements, destroy the current elements.
789  // This allows us to avoid copying them during the grow.
790  // FIXME: this may not actually make any sense if we can efficiently move
791  // elements.
792  if (this->capacity() < RHSSize) {
793  // Destroy current elements.
794  this->destroy_range(this->begin(), this->end());
795  this->setEnd(this->begin());
796  CurSize = 0;
797  this->grow(RHSSize);
798  } else if (CurSize) {
799  // Otherwise, use assignment for the already-constructed elements.
800  std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
801  }
802 
803  // Move-construct the new elements in place.
804  this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
805  this->begin()+CurSize);
806 
807  // Set end.
808  this->setEnd(this->begin()+RHSSize);
809 
810  RHS.clear();
811  return *this;
812 }
813 
818 template <typename T, unsigned N>
819 struct SmallVectorStorage {
820  typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
821 };
822 template <typename T> struct SmallVectorStorage<T, 1> {};
823 template <typename T> struct SmallVectorStorage<T, 0> {};
824 
833 template <typename T, unsigned N>
834 class SmallVector : public SmallVectorImpl<T> {
836  SmallVectorStorage<T, N> Storage;
837 public:
839  }
840 
841  explicit SmallVector(size_t Size, const T &Value = T())
842  : SmallVectorImpl<T>(N) {
843  this->assign(Size, Value);
844  }
845 
846  template<typename ItTy>
847  SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
848  this->append(S, E);
849  }
850 
851  template <typename RangeTy>
853  : SmallVectorImpl<T>(N) {
854  this->append(R.begin(), R.end());
855  }
856 
857  SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
858  this->assign(IL);
859  }
860 
861  SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
862  if (!RHS.empty())
864  }
865 
866  const SmallVector &operator=(const SmallVector &RHS) {
868  return *this;
869  }
870 
871  SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
872  if (!RHS.empty())
873  SmallVectorImpl<T>::operator=(::std::move(RHS));
874  }
875 
876  const SmallVector &operator=(SmallVector &&RHS) {
877  SmallVectorImpl<T>::operator=(::std::move(RHS));
878  return *this;
879  }
880 
881  SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
882  if (!RHS.empty())
883  SmallVectorImpl<T>::operator=(::std::move(RHS));
884  }
885 
886  const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
887  SmallVectorImpl<T>::operator=(::std::move(RHS));
888  return *this;
889  }
890 
891  const SmallVector &operator=(std::initializer_list<T> IL) {
892  this->assign(IL);
893  return *this;
894  }
895 };
896 
897 template<typename T, unsigned N>
898 static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
899  return X.capacity_in_bytes();
900 }
901 
902 } // End llvm namespace
903 
904 namespace std {
906  template<typename T>
907  inline void
909  LHS.swap(RHS);
910  }
911 
913  template<typename T, unsigned N>
914  inline void
916  LHS.swap(RHS);
917  }
918 }
919 
920 #endif
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
Definition: Path.inc:27
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: StringExtras.h:22
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 &#39;vector&#39; (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&#39;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&#39;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&#39;s buffer, even if empty().
Definition: SmallVector.h:136