WPILibC++  2018.4.1-20180926150325-1206-g8b1274d
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
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 WPIUTIL_WPI_SMALLVECTOR_H
15 #define WPIUTIL_WPI_SMALLVECTOR_H
16 
17 // This file uses std::memcpy() to copy std::pair<unsigned int, unsigned int>.
18 // That type is POD, but the standard doesn't guarantee that. GCC doesn't treat
19 // the type as POD so it throws a warning. We want to consider this a warning
20 // instead of an error.
21 #if __GNUC__ >= 8
22 #pragma GCC diagnostic warning "-Wclass-memaccess"
23 #endif
24 
25 #include "wpi/iterator_range.h"
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"
31 #include <algorithm>
32 #include <cassert>
33 #include <cstddef>
34 #include <cstdlib>
35 #include <cstring>
36 #include <initializer_list>
37 #include <iterator>
38 #include <memory>
39 #include <new>
40 #include <type_traits>
41 #include <utility>
42 
43 namespace wpi {
44 
47 protected:
48  void *BeginX, *EndX, *CapacityX;
49 
50 protected:
51  SmallVectorBase(void *FirstEl, size_t Size)
52  : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
53 
56  void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize);
57 
58 public:
60  size_t size_in_bytes() const {
61  return size_t((char*)EndX - (char*)BeginX);
62  }
63 
65  size_t capacity_in_bytes() const {
66  return size_t((char*)CapacityX - (char*)BeginX);
67  }
68 
69  LLVM_NODISCARD bool empty() const { return BeginX == EndX; }
70 };
71 
75 template <typename T, typename = void>
77 private:
78  template <typename, unsigned> friend struct SmallVectorStorage;
79 
80  // Allocate raw space for N elements of type T. If T has a ctor or dtor, we
81  // don't want it to be automatically run, so we need to represent the space as
82  // something else. Use an array of char of sufficient alignment.
84  U FirstEl;
85  // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
86 
87 protected:
88  SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
89 
90  void grow_pod(size_t MinSizeInBytes, size_t TSize) {
91  SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
92  }
93 
96  bool isSmall() const {
97  return BeginX == static_cast<const void*>(&FirstEl);
98  }
99 
101  void resetToSmall() {
102  BeginX = EndX = CapacityX = &FirstEl;
103  }
104 
105  void setEnd(T *P) { this->EndX = P; }
106 
107 public:
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 *;
113 
114  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
115  using reverse_iterator = std::reverse_iterator<iterator>;
116 
117  using reference = T &;
118  using const_reference = const T &;
119  using pointer = T *;
120  using const_pointer = const T *;
121 
122  // forward iterator creation methods.
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; }
131 
132 protected:
133  iterator capacity_ptr() { return (iterator)this->CapacityX; }
134  const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
135 
136 public:
137  // reverse iterator creation methods.
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());}
142 
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); }
146 
148  size_t capacity() const { return capacity_ptr() - begin(); }
149 
151  pointer data() { return pointer(begin()); }
153  const_pointer data() const { return const_pointer(begin()); }
154 
155  LLVM_ATTRIBUTE_ALWAYS_INLINE
156  reference operator[](size_type idx) {
157  assert(idx < size());
158  return begin()[idx];
159  }
160  LLVM_ATTRIBUTE_ALWAYS_INLINE
161  const_reference operator[](size_type idx) const {
162  assert(idx < size());
163  return begin()[idx];
164  }
165 
166  reference front() {
167  assert(!empty());
168  return begin()[0];
169  }
170  const_reference front() const {
171  assert(!empty());
172  return begin()[0];
173  }
174 
175  reference back() {
176  assert(!empty());
177  return end()[-1];
178  }
179  const_reference back() const {
180  assert(!empty());
181  return end()[-1];
182  }
183 };
184 
187 template <typename T, bool isPodLike>
189 protected:
191 
192  static void destroy_range(T *S, T *E) {
193  while (S != E) {
194  --E;
195  E->~T();
196  }
197  }
198 
201  template<typename It1, typename It2>
202  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
203  std::uninitialized_copy(std::make_move_iterator(I),
204  std::make_move_iterator(E), Dest);
205  }
206 
209  template<typename It1, typename It2>
210  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
211  std::uninitialized_copy(I, E, Dest);
212  }
213 
217  void grow(size_t MinSize = 0);
218 
219 public:
220  void push_back(const T &Elt) {
221  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
222  this->grow();
223  ::new ((void*) this->end()) T(Elt);
224  this->setEnd(this->end()+1);
225  }
226 
227  void push_back(T &&Elt) {
228  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
229  this->grow();
230  ::new ((void*) this->end()) T(::std::move(Elt));
231  this->setEnd(this->end()+1);
232  }
233 
234  void pop_back() {
235  this->setEnd(this->end()-1);
236  this->end()->~T();
237  }
238 };
239 
240 // Define this out-of-line to dissuade the C++ compiler from inlining it.
241 template <typename T, bool isPodLike>
243  size_t CurCapacity = this->capacity();
244  size_t CurSize = this->size();
245  // Always grow, even from zero.
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)));
250 
251  // Move the elements over.
252  this->uninitialized_move(this->begin(), this->end(), NewElts);
253 
254  // Destroy the original elements.
255  destroy_range(this->begin(), this->end());
256 
257  // If this wasn't grown from the inline copy, deallocate the old space.
258  if (!this->isSmall())
259  free(this->begin());
260 
261  this->setEnd(NewElts+CurSize);
262  this->BeginX = NewElts;
263  this->CapacityX = this->begin()+NewCapacity;
264 }
265 
266 
269 template <typename T>
271 protected:
273 
274  // No need to do a destroy loop for POD's.
275  static void destroy_range(T *, T *) {}
276 
279  template<typename It1, typename It2>
280  static void uninitialized_move(It1 I, It1 E, It2 Dest) {
281  // Just do a copy.
282  uninitialized_copy(I, E, Dest);
283  }
284 
287  template<typename It1, typename It2>
288  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
289  // Arbitrary iterator types; just use the basic implementation.
290  std::uninitialized_copy(I, E, Dest);
291  }
292 
295  template <typename T1, typename T2>
296  static void uninitialized_copy(
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) {
300  // Use memcpy for PODs iterated by pointers (which includes SmallVector
301  // iterators): std::uninitialized_copy optimizes to memmove, but we can
302  // use memcpy here. Note that I and E are iterators and thus might be
303  // invalid for memcpy if they are equal.
304  if (I != E)
305  memcpy(Dest, I, (E - I) * sizeof(T));
306  }
307 
310  void grow(size_t MinSize = 0) {
311  this->grow_pod(MinSize*sizeof(T), sizeof(T));
312  }
313 
314 public:
315  void push_back(const T &Elt) {
316  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
317  this->grow();
318  memcpy(this->end(), &Elt, sizeof(T));
319  this->setEnd(this->end()+1);
320  }
321 
322  void pop_back() {
323  this->setEnd(this->end()-1);
324  }
325 };
326 
329 template <typename T>
330 class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
331  using SuperClass = SmallVectorTemplateBase<T, isPodLike<T>::value>;
332 
333 public:
334  using iterator = typename SuperClass::iterator;
335  using const_iterator = typename SuperClass::const_iterator;
336  using size_type = typename SuperClass::size_type;
337 
338 protected:
339  // Default ctor - Initialize to empty.
340  explicit SmallVectorImpl(unsigned N)
341  : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
342  }
343 
344 public:
345  SmallVectorImpl(const SmallVectorImpl &) = delete;
346 
347  ~SmallVectorImpl() {
348  // Subclass has already destructed this vector's elements.
349  // If this wasn't grown from the inline copy, deallocate the old space.
350  if (!this->isSmall())
351  free(this->begin());
352  }
353 
354  void clear() {
355  this->destroy_range(this->begin(), this->end());
356  this->EndX = this->BeginX;
357  }
358 
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()) {
364  if (this->capacity() < N)
365  this->grow(N);
366  for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
367  new (&*I) T();
368  this->setEnd(this->begin()+N);
369  }
370  }
371 
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()) {
377  if (this->capacity() < N)
378  this->grow(N);
379  std::uninitialized_fill(this->end(), this->begin()+N, NV);
380  this->setEnd(this->begin()+N);
381  }
382  }
383 
384  void reserve(size_type N) {
385  if (this->capacity() < N)
386  this->grow(N);
387  }
388 
389  LLVM_NODISCARD T pop_back_val() {
390  T Result = ::std::move(this->back());
391  this->pop_back();
392  return Result;
393  }
394 
395  void swap(SmallVectorImpl &RHS);
396 
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);
404  // Grow allocated space if needed.
405  if (NumInputs > size_type(this->capacity_ptr()-this->end()))
406  this->grow(this->size()+NumInputs);
407 
408  // Copy the new elements over.
409  this->uninitialized_copy(in_start, in_end, this->end());
410  this->setEnd(this->end() + NumInputs);
411  }
412 
414  void append(size_type NumInputs, const T &Elt) {
415  // Grow allocated space if needed.
416  if (NumInputs > size_type(this->capacity_ptr()-this->end()))
417  this->grow(this->size()+NumInputs);
418 
419  // Copy the new elements over.
420  std::uninitialized_fill_n(this->end(), NumInputs, Elt);
421  this->setEnd(this->end() + NumInputs);
422  }
423 
424  void append(std::initializer_list<T> IL) {
425  append(IL.begin(), IL.end());
426  }
427 
428  // FIXME: Consider assigning over existing elements, rather than clearing &
429  // re-initializing them - for all assign(...) variants.
430 
431  void assign(size_type NumElts, const T &Elt) {
432  clear();
433  if (this->capacity() < NumElts)
434  this->grow(NumElts);
435  this->setEnd(this->begin()+NumElts);
436  std::uninitialized_fill(this->begin(), this->end(), Elt);
437  }
438 
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) {
444  clear();
445  append(in_start, in_end);
446  }
447 
448  void assign(std::initializer_list<T> IL) {
449  clear();
450  append(IL);
451  }
452 
453  iterator erase(const_iterator CI) {
454  // Just cast away constness because this is a non-const member function.
455  iterator I = const_cast<iterator>(CI);
456 
457  assert(I >= this->begin() && "Iterator to erase is out of bounds.");
458  assert(I < this->end() && "Erasing at past-the-end iterator.");
459 
460  iterator N = I;
461  // Shift all elts down one.
462  std::move(I+1, this->end(), I);
463  // Drop the last elt.
464  this->pop_back();
465  return(N);
466  }
467 
468  iterator erase(const_iterator CS, const_iterator CE) {
469  // Just cast away constness because this is a non-const member function.
470  iterator S = const_cast<iterator>(CS);
471  iterator E = const_cast<iterator>(CE);
472 
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.");
476 
477  iterator N = S;
478  // Shift all elts down.
479  iterator I = std::move(E, this->end(), S);
480  // Drop the last elts.
481  this->destroy_range(I, this->end());
482  this->setEnd(I);
483  return(N);
484  }
485 
486  iterator insert(iterator I, T &&Elt) {
487  if (I == this->end()) { // Important special case for empty vector.
488  this->push_back(::std::move(Elt));
489  return this->end()-1;
490  }
491 
492  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
493  assert(I <= this->end() && "Inserting past the end of the vector.");
494 
495  if (this->EndX >= this->CapacityX) {
496  size_t EltNo = I-this->begin();
497  this->grow();
498  I = this->begin()+EltNo;
499  }
500 
501  ::new ((void*) this->end()) T(::std::move(this->back()));
502  // Push everything else over.
503  std::move_backward(I, this->end()-1, this->end());
504  this->setEnd(this->end()+1);
505 
506  // If we just moved the element we're inserting, be sure to update
507  // the reference.
508  T *EltPtr = &Elt;
509  if (I <= EltPtr && EltPtr < this->EndX)
510  ++EltPtr;
511 
512  *I = ::std::move(*EltPtr);
513  return I;
514  }
515 
516  iterator insert(iterator I, const T &Elt) {
517  if (I == this->end()) { // Important special case for empty vector.
518  this->push_back(Elt);
519  return this->end()-1;
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  if (this->EndX >= this->CapacityX) {
526  size_t EltNo = I-this->begin();
527  this->grow();
528  I = this->begin()+EltNo;
529  }
530  ::new ((void*) this->end()) T(std::move(this->back()));
531  // Push everything else over.
532  std::move_backward(I, this->end()-1, this->end());
533  this->setEnd(this->end()+1);
534 
535  // If we just moved the element we're inserting, be sure to update
536  // the reference.
537  const T *EltPtr = &Elt;
538  if (I <= EltPtr && EltPtr < this->EndX)
539  ++EltPtr;
540 
541  *I = *EltPtr;
542  return I;
543  }
544 
545  iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
546  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
547  size_t InsertElt = I - this->begin();
548 
549  if (I == this->end()) { // Important special case for empty vector.
550  append(NumToInsert, Elt);
551  return this->begin()+InsertElt;
552  }
553 
554  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
555  assert(I <= this->end() && "Inserting past the end of the vector.");
556 
557  // Ensure there is enough space.
558  reserve(this->size() + NumToInsert);
559 
560  // Uninvalidate the iterator.
561  I = this->begin()+InsertElt;
562 
563  // If there are more elements between the insertion point and the end of the
564  // range than there are being inserted, we can use a simple approach to
565  // insertion. Since we already reserved space, we know that this won't
566  // reallocate the vector.
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()));
571 
572  // Copy the existing elements that get replaced.
573  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
574 
575  std::fill_n(I, NumToInsert, Elt);
576  return I;
577  }
578 
579  // Otherwise, we're inserting more elements than exist already, and we're
580  // not inserting at the end.
581 
582  // Move over the elements that we're about to overwrite.
583  T *OldEnd = this->end();
584  this->setEnd(this->end() + NumToInsert);
585  size_t NumOverwritten = OldEnd-I;
586  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
587 
588  // Replace the overwritten part.
589  std::fill_n(I, NumOverwritten, Elt);
590 
591  // Insert the non-overwritten middle part.
592  std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
593  return I;
594  }
595 
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) {
601  // Convert iterator to elt# to avoid invalidating iterator when we reserve()
602  size_t InsertElt = I - this->begin();
603 
604  if (I == this->end()) { // Important special case for empty vector.
605  append(From, To);
606  return this->begin()+InsertElt;
607  }
608 
609  assert(I >= this->begin() && "Insertion iterator is out of bounds.");
610  assert(I <= this->end() && "Inserting past the end of the vector.");
611 
612  size_t NumToInsert = std::distance(From, To);
613 
614  // Ensure there is enough space.
615  reserve(this->size() + NumToInsert);
616 
617  // Uninvalidate the iterator.
618  I = this->begin()+InsertElt;
619 
620  // If there are more elements between the insertion point and the end of the
621  // range than there are being inserted, we can use a simple approach to
622  // insertion. Since we already reserved space, we know that this won't
623  // reallocate the vector.
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()));
628 
629  // Copy the existing elements that get replaced.
630  std::move_backward(I, OldEnd-NumToInsert, OldEnd);
631 
632  std::copy(From, To, I);
633  return I;
634  }
635 
636  // Otherwise, we're inserting more elements than exist already, and we're
637  // not inserting at the end.
638 
639  // Move over the elements that we're about to overwrite.
640  T *OldEnd = this->end();
641  this->setEnd(this->end() + NumToInsert);
642  size_t NumOverwritten = OldEnd-I;
643  this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
644 
645  // Replace the overwritten part.
646  for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
647  *J = *From;
648  ++J; ++From;
649  }
650 
651  // Insert the non-overwritten middle part.
652  this->uninitialized_copy(From, To, OldEnd);
653  return I;
654  }
655 
656  void insert(iterator I, std::initializer_list<T> IL) {
657  insert(I, IL.begin(), IL.end());
658  }
659 
660  template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
661  if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
662  this->grow();
663  ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
664  this->setEnd(this->end() + 1);
665  }
666 
667  SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
668 
669  SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
670 
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());
674  }
675  bool operator!=(const SmallVectorImpl &RHS) const {
676  return !(*this == RHS);
677  }
678 
679  bool operator<(const SmallVectorImpl &RHS) const {
680  return std::lexicographical_compare(this->begin(), this->end(),
681  RHS.begin(), RHS.end());
682  }
683 
693  void set_size(size_type N) {
694  assert(N <= this->capacity());
695  this->setEnd(this->begin() + N);
696  }
697 };
698 
699 template <typename T>
700 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
701  if (this == &RHS) return;
702 
703  // We can only avoid copying elements if neither vector is small.
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);
708  return;
709  }
710  if (RHS.size() > this->capacity())
711  this->grow(RHS.size());
712  if (this->size() > RHS.capacity())
713  RHS.grow(this->size());
714 
715  // Swap the shared elements.
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]);
720 
721  // Copy over the extra elts.
722  if (this->size() > RHS.size()) {
723  size_t EltDiff = this->size() - RHS.size();
724  this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
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();
730  this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
731  this->setEnd(this->end() + EltDiff);
732  this->destroy_range(RHS.begin()+NumShared, RHS.end());
733  RHS.setEnd(RHS.begin()+NumShared);
734  }
735 }
736 
737 template <typename T>
738 SmallVectorImpl<T> &SmallVectorImpl<T>::
739  operator=(const SmallVectorImpl<T> &RHS) {
740  // Avoid self-assignment.
741  if (this == &RHS) return *this;
742 
743  // If we already have sufficient space, assign the common elements, then
744  // destroy any excess.
745  size_t RHSSize = RHS.size();
746  size_t CurSize = this->size();
747  if (CurSize >= RHSSize) {
748  // Assign common elements.
749  iterator NewEnd;
750  if (RHSSize)
751  NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
752  else
753  NewEnd = this->begin();
754 
755  // Destroy excess elements.
756  this->destroy_range(NewEnd, this->end());
757 
758  // Trim.
759  this->setEnd(NewEnd);
760  return *this;
761  }
762 
763  // If we have to grow to have enough elements, destroy the current elements.
764  // This allows us to avoid copying them during the grow.
765  // FIXME: don't do this if they're efficiently moveable.
766  if (this->capacity() < RHSSize) {
767  // Destroy current elements.
768  this->destroy_range(this->begin(), this->end());
769  this->setEnd(this->begin());
770  CurSize = 0;
771  this->grow(RHSSize);
772  } else if (CurSize) {
773  // Otherwise, use assignment for the already-constructed elements.
774  std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
775  }
776 
777  // Copy construct the new elements in place.
778  this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
779  this->begin()+CurSize);
780 
781  // Set end.
782  this->setEnd(this->begin()+RHSSize);
783  return *this;
784 }
785 
786 template <typename T>
787 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
788  // Avoid self-assignment.
789  if (this == &RHS) return *this;
790 
791  // If the RHS isn't small, clear this vector and then steal its buffer.
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;
798  RHS.resetToSmall();
799  return *this;
800  }
801 
802  // If we already have sufficient space, assign the common elements, then
803  // destroy any excess.
804  size_t RHSSize = RHS.size();
805  size_t CurSize = this->size();
806  if (CurSize >= RHSSize) {
807  // Assign common elements.
808  iterator NewEnd = this->begin();
809  if (RHSSize)
810  NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
811 
812  // Destroy excess elements and trim the bounds.
813  this->destroy_range(NewEnd, this->end());
814  this->setEnd(NewEnd);
815 
816  // Clear the RHS.
817  RHS.clear();
818 
819  return *this;
820  }
821 
822  // If we have to grow to have enough elements, destroy the current elements.
823  // This allows us to avoid copying them during the grow.
824  // FIXME: this may not actually make any sense if we can efficiently move
825  // elements.
826  if (this->capacity() < RHSSize) {
827  // Destroy current elements.
828  this->destroy_range(this->begin(), this->end());
829  this->setEnd(this->begin());
830  CurSize = 0;
831  this->grow(RHSSize);
832  } else if (CurSize) {
833  // Otherwise, use assignment for the already-constructed elements.
834  std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
835  }
836 
837  // Move-construct the new elements in place.
838  this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
839  this->begin()+CurSize);
840 
841  // Set end.
842  this->setEnd(this->begin()+RHSSize);
843 
844  RHS.clear();
845  return *this;
846 }
847 
852 template <typename T, unsigned N>
854  typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
855 };
856 template <typename T> struct SmallVectorStorage<T, 1> {};
857 template <typename T> struct SmallVectorStorage<T, 0> {};
858 
867 template <typename T, unsigned N>
868 class SmallVector : public SmallVectorImpl<T> {
870  SmallVectorStorage<T, N> Storage;
871 
872 public:
874 
875  ~SmallVector() {
876  // Destroy the constructed elements in the vector.
877  this->destroy_range(this->begin(), this->end());
878  }
879 
880  explicit SmallVector(size_t Size, const T &Value = T())
881  : SmallVectorImpl<T>(N) {
882  this->assign(Size, Value);
883  }
884 
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>
889  SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
890  this->append(S, E);
891  }
892 
893  template <typename RangeTy>
894  explicit SmallVector(const iterator_range<RangeTy> &R)
895  : SmallVectorImpl<T>(N) {
896  this->append(R.begin(), R.end());
897  }
898 
899  SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
900  this->assign(IL);
901  }
902 
903  SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
904  if (!RHS.empty())
906  }
907 
908  const SmallVector &operator=(const SmallVector &RHS) {
910  return *this;
911  }
912 
913  SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
914  if (!RHS.empty())
915  SmallVectorImpl<T>::operator=(::std::move(RHS));
916  }
917 
918  SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
919  if (!RHS.empty())
920  SmallVectorImpl<T>::operator=(::std::move(RHS));
921  }
922 
923  const SmallVector &operator=(SmallVector &&RHS) {
924  SmallVectorImpl<T>::operator=(::std::move(RHS));
925  return *this;
926  }
927 
928  const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
929  SmallVectorImpl<T>::operator=(::std::move(RHS));
930  return *this;
931  }
932 
933  const SmallVector &operator=(std::initializer_list<T> IL) {
934  this->assign(IL);
935  return *this;
936  }
937 };
938 
939 template <typename T, unsigned N>
940 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
941  return X.capacity_in_bytes();
942 }
943 
944 } // end namespace wpi
945 
946 namespace std {
947 
949  template<typename T>
950  inline void
952  LHS.swap(RHS);
953  }
954 
956  template<typename T, unsigned N>
957  inline void
959  LHS.swap(RHS);
960  }
961 
962 } // end namespace std
963 
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
WPILib C++ utilities (wpiutil) namespace.
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