LCOV - code coverage report
Current view: top level - include/llvm/ADT - SmallVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 298 305 97.7 %
Date: 2018-06-17 00:07:59 Functions: 3636 4161 87.4 %
Legend: Lines: hit not hit

          Line data    Source code
       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/ADT/iterator_range.h"
      18             : #include "llvm/Support/AlignOf.h"
      19             : #include "llvm/Support/Compiler.h"
      20             : #include "llvm/Support/MathExtras.h"
      21             : #include "llvm/Support/MemAlloc.h"
      22             : #include "llvm/Support/type_traits.h"
      23             : #include "llvm/Support/ErrorHandling.h"
      24             : #include <algorithm>
      25             : #include <cassert>
      26             : #include <cstddef>
      27             : #include <cstdlib>
      28             : #include <cstring>
      29             : #include <initializer_list>
      30             : #include <iterator>
      31             : #include <memory>
      32             : #include <new>
      33             : #include <type_traits>
      34             : #include <utility>
      35             : 
      36             : namespace llvm {
      37             : 
      38             : /// This is all the non-templated stuff common to all SmallVectors.
      39             : class SmallVectorBase {
      40             : protected:
      41             :   void *BeginX, *EndX, *CapacityX;
      42             : 
      43             : protected:
      44             :   SmallVectorBase(void *FirstEl, size_t Size)
      45  2817759443 :     : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
      46             : 
      47             :   /// This is an implementation of the grow() method which only works
      48             :   /// on POD-like data types and is out of line to reduce code duplication.
      49             :   void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize);
      50             : 
      51             : public:
      52             :   /// This returns size()*sizeof(T).
      53             :   size_t size_in_bytes() const {
      54    83948482 :     return size_t((char*)EndX - (char*)BeginX);
      55             :   }
      56             : 
      57             :   /// capacity_in_bytes - This returns capacity()*sizeof(T).
      58             :   size_t capacity_in_bytes() const {
      59    83948495 :     return size_t((char*)CapacityX - (char*)BeginX);
      60             :   }
      61             : 
      62     2277433 :   LLVM_NODISCARD bool empty() const { return BeginX == EndX; }
      63             : };
      64             : 
      65             : /// This is the part of SmallVectorTemplateBase which does not depend on whether
      66             : /// the type T is a POD. The extra dummy template argument is used by ArrayRef
      67             : /// to avoid unnecessarily requiring T to be complete.
      68             : template <typename T, typename = void>
      69             : class SmallVectorTemplateCommon : public SmallVectorBase {
      70             : private:
      71             :   template <typename, unsigned> friend struct SmallVectorStorage;
      72             : 
      73             :   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
      74             :   // don't want it to be automatically run, so we need to represent the space as
      75             :   // something else.  Use an array of char of sufficient alignment.
      76             :   using U = AlignedCharArrayUnion<T>;
      77             :   U FirstEl;
      78             :   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
      79             : 
      80             : protected:
      81  2792764473 :   SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
      82             : 
      83             :   void grow_pod(size_t MinSizeInBytes, size_t TSize) {
      84    83948506 :     SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
      85             :   }
      86             : 
      87             :   /// Return true if this is a smallvector which has not had dynamic
      88             :   /// memory allocated for it.
      89             :   bool isSmall() const {
      90   824946862 :     return BeginX == static_cast<const void*>(&FirstEl);
      91             :   }
      92             : 
      93             :   /// Put this vector in a state of being small.
      94             :   void resetToSmall() {
      95      518588 :     BeginX = EndX = CapacityX = &FirstEl;
      96             :   }
      97             : 
      98  9470942324 :   void setEnd(T *P) { this->EndX = P; }
      99             : 
     100             : public:
     101             :   using size_type = size_t;
     102             :   using difference_type = ptrdiff_t;
     103             :   using value_type = T;
     104             :   using iterator = T *;
     105             :   using const_iterator = const T *;
     106             : 
     107             :   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     108             :   using reverse_iterator = std::reverse_iterator<iterator>;
     109             : 
     110             :   using reference = T &;
     111             :   using const_reference = const T &;
     112             :   using pointer = T *;
     113             :   using const_pointer = const T *;
     114             : 
     115             :   // forward iterator creation methods.
     116             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     117  5922251152 :   iterator begin() { return (iterator)this->BeginX; }
     118             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     119 12888490661 :   const_iterator begin() const { return (const_iterator)this->BeginX; }
     120             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     121 19598879753 :   iterator end() { return (iterator)this->EndX; }
     122             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     123  4964994023 :   const_iterator end() const { return (const_iterator)this->EndX; }
     124             : 
     125             : protected:
     126             :   iterator capacity_ptr() { return (iterator)this->CapacityX; }
     127             :   const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
     128             : 
     129             : public:
     130             :   // reverse iterator creation methods.
     131             :   reverse_iterator rbegin()            { return reverse_iterator(end()); }
     132             :   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
     133             :   reverse_iterator rend()              { return reverse_iterator(begin()); }
     134             :   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
     135             : 
     136             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     137  6851483530 :   size_type size() const { return end()-begin(); }
     138             :   size_type max_size() const { return size_type(-1) / sizeof(T); }
     139             : 
     140             :   /// Return the total number of elements in the currently allocated buffer.
     141   462158441 :   size_t capacity() const { return capacity_ptr() - begin(); }
     142             : 
     143             :   /// Return a pointer to the vector's buffer, even if empty().
     144             :   pointer data() { return pointer(begin()); }
     145             :   /// Return a pointer to the vector's buffer, even if empty().
     146             :   const_pointer data() const { return const_pointer(begin()); }
     147             : 
     148             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     149             :   reference operator[](size_type idx) {
     150             :     assert(idx < size());
     151  2232952035 :     return begin()[idx];
     152             :   }
     153             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     154             :   const_reference operator[](size_type idx) const {
     155             :     assert(idx < size());
     156  8626620490 :     return begin()[idx];
     157             :   }
     158             : 
     159             :   reference front() {
     160             :     assert(!empty());
     161             :     return begin()[0];
     162             :   }
     163             :   const_reference front() const {
     164             :     assert(!empty());
     165             :     return begin()[0];
     166             :   }
     167             : 
     168             :   reference back() {
     169             :     assert(!empty());
     170   113267113 :     return end()[-1];
     171             :   }
     172             :   const_reference back() const {
     173             :     assert(!empty());
     174    10254962 :     return end()[-1];
     175             :   }
     176             : };
     177             : 
     178             : /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method
     179             : /// implementations that are designed to work with non-POD-like T's.
     180             : template <typename T, bool isPodLike>
     181             : class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
     182             : protected:
     183             :   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
     184             : 
     185     4448138 :   static void destroy_range(T *S, T *E) {
     186   183049893 :     while (S != E) {
     187    89863670 :       --E;
     188    14728672 :       E->~T();
     189             :     }
     190     4448138 :   }
     191             : 
     192             :   /// Move the range [I, E) into the uninitialized memory starting with "Dest",
     193             :   /// constructing elements as needed.
     194             :   template<typename It1, typename It2>
     195             :   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
     196         271 :     std::uninitialized_copy(std::make_move_iterator(I),
     197             :                             std::make_move_iterator(E), Dest);
     198             :   }
     199             : 
     200             :   /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
     201             :   /// constructing elements as needed.
     202             :   template<typename It1, typename It2>
     203        1547 :   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
     204             :     std::uninitialized_copy(I, E, Dest);
     205        1547 :   }
     206             : 
     207             :   /// Grow the allocated memory (without initializing new elements), doubling
     208             :   /// the size of the allocated memory. Guarantees space for at least one more
     209             :   /// element, or MinSize more elements if specified.
     210             :   void grow(size_t MinSize = 0);
     211             : 
     212             : public:
     213    82386988 :   void push_back(const T &Elt) {
     214    82386988 :     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
     215     1224205 :       this->grow();
     216    82386988 :     ::new ((void*) this->end()) T(Elt);
     217    82386988 :     this->setEnd(this->end()+1);
     218    82386988 :   }
     219             : 
     220    30282327 :   void push_back(T &&Elt) {
     221    30282327 :     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
     222      349328 :       this->grow();
     223    30282327 :     ::new ((void*) this->end()) T(::std::move(Elt));
     224    30282327 :     this->setEnd(this->end()+1);
     225    30282327 :   }
     226             : 
     227     9400940 :   void pop_back() {
     228    47202503 :     this->setEnd(this->end()-1);
     229    34795849 :     this->end()->~T();
     230     9400940 :   }
     231             : };
     232             : 
     233             : // Define this out-of-line to dissuade the C++ compiler from inlining it.
     234             : template <typename T, bool isPodLike>
     235     2627766 : void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
     236             :   size_t CurCapacity = this->capacity();
     237             :   size_t CurSize = this->size();
     238             :   // Always grow, even from zero.
     239     2627766 :   size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
     240     2627766 :   if (NewCapacity < MinSize)
     241             :     NewCapacity = MinSize;
     242     2627766 :   T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
     243             : 
     244             :   // Move the elements over.
     245             :   this->uninitialized_move(this->begin(), this->end(), NewElts);
     246             : 
     247             :   // Destroy the original elements.
     248       11996 :   destroy_range(this->begin(), this->end());
     249             : 
     250             :   // If this wasn't grown from the inline copy, deallocate the old space.
     251     2627766 :   if (!this->isSmall())
     252     1029657 :     free(this->begin());
     253             : 
     254     2627766 :   this->setEnd(NewElts+CurSize);
     255     2627766 :   this->BeginX = NewElts;
     256     2627766 :   this->CapacityX = this->begin()+NewCapacity;
     257     2627766 : }
     258             : 
     259             : 
     260             : /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
     261             : /// implementations that are designed to work with POD-like T's.
     262             : template <typename T>
     263             : class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
     264             : protected:
     265             :   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
     266             : 
     267             :   // No need to do a destroy loop for POD's.
     268             :   static void destroy_range(T *, T *) {}
     269             : 
     270             :   /// Move the range [I, E) onto the uninitialized memory
     271             :   /// starting with "Dest", constructing elements into it as needed.
     272             :   template<typename It1, typename It2>
     273             :   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
     274             :     // Just do a copy.
     275             :     uninitialized_copy(I, E, Dest);
     276             :   }
     277             : 
     278             :   /// Copy the range [I, E) onto the uninitialized memory
     279             :   /// starting with "Dest", constructing elements into it as needed.
     280             :   template<typename It1, typename It2>
     281        5888 :   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
     282             :     // Arbitrary iterator types; just use the basic implementation.
     283     1641241 :     std::uninitialized_copy(I, E, Dest);
     284        5888 :   }
     285             : 
     286             :   /// Copy the range [I, E) onto the uninitialized memory
     287             :   /// starting with "Dest", constructing elements into it as needed.
     288             :   template <typename T1, typename T2>
     289             :   static void uninitialized_copy(
     290             :       T1 *I, T1 *E, T2 *Dest,
     291             :       typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
     292             :                                            T2>::value>::type * = nullptr) {
     293             :     // Use memcpy for PODs iterated by pointers (which includes SmallVector
     294             :     // iterators): std::uninitialized_copy optimizes to memmove, but we can
     295             :     // use memcpy here. Note that I and E are iterators and thus might be
     296             :     // invalid for memcpy if they are equal.
     297   726966863 :     if (I != E)
     298   713626655 :       memcpy(Dest, I, (E - I) * sizeof(T));
     299             :   }
     300             : 
     301             :   /// Double the size of the allocated memory, guaranteeing space for at
     302             :   /// least one more element or MinSize if specified.
     303             :   void grow(size_t MinSize = 0) {
     304    17111209 :     this->grow_pod(MinSize*sizeof(T), sizeof(T));
     305             :   }
     306             : 
     307             : public:
     308  7872280829 :   void push_back(const T &Elt) {
     309  7872280829 :     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
     310             :       this->grow();
     311  7872280829 :     memcpy(this->end(), &Elt, sizeof(T));
     312  7872280829 :     this->setEnd(this->end()+1);
     313  7872280829 :   }
     314             : 
     315             :   void pop_back() {
     316   337839271 :     this->setEnd(this->end()-1);
     317             :   }
     318             : };
     319             : 
     320             : /// This class consists of common code factored out of the SmallVector class to
     321             : /// reduce code duplication based on the SmallVector 'N' template parameter.
     322             : template <typename T>
     323             : class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
     324             :   using SuperClass = SmallVectorTemplateBase<T, isPodLike<T>::value>;
     325             : 
     326             : public:
     327             :   using iterator = typename SuperClass::iterator;
     328             :   using const_iterator = typename SuperClass::const_iterator;
     329             :   using size_type = typename SuperClass::size_type;
     330             : 
     331             : protected:
     332             :   // Default ctor - Initialize to empty.
     333             :   explicit SmallVectorImpl(unsigned N)
     334             :     : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
     335             :   }
     336             : 
     337             : public:
     338             :   SmallVectorImpl(const SmallVectorImpl &) = delete;
     339             : 
     340             :   ~SmallVectorImpl() {
     341             :     // Subclass has already destructed this vector's elements.
     342             :     // If this wasn't grown from the inline copy, deallocate the old space.
     343  2363461131 :     if (!this->isSmall())
     344    53354943 :       free(this->begin());
     345             :   }
     346             : 
     347    10236988 :   void clear() {
     348     1127064 :     this->destroy_range(this->begin(), this->end());
     349   665153319 :     this->EndX = this->BeginX;
     350    10236988 :   }
     351             : 
     352    97615295 :   void resize(size_type N) {
     353    97615295 :     if (N < this->size()) {
     354     8483034 :       this->destroy_range(this->begin()+N, this->end());
     355        4178 :       this->setEnd(this->begin()+N);
     356    89132261 :     } else if (N > this->size()) {
     357    63486662 :       if (this->capacity() < N)
     358      676657 :         this->grow(N);
     359  1350811304 :       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
     360  1287324640 :         new (&*I) T();
     361    20868375 :       this->setEnd(this->begin()+N);
     362             :     }
     363    97615297 :   }
     364             : 
     365    20227546 :   void resize(size_type N, const T &NV) {
     366    20227546 :     if (N < this->size()) {
     367        4323 :       this->destroy_range(this->begin()+N, this->end());
     368           0 :       this->setEnd(this->begin()+N);
     369    20223223 :     } else if (N > this->size()) {
     370    13596529 :       if (this->capacity() < N)
     371       54589 :         this->grow(N);
     372    18480170 :       std::uninitialized_fill(this->end(), this->begin()+N, NV);
     373     7865969 :       this->setEnd(this->begin()+N);
     374             :     }
     375    20227546 :   }
     376             : 
     377    99579219 :   void reserve(size_type N) {
     378   117868645 :     if (this->capacity() < N)
     379      232069 :       this->grow(N);
     380    99579219 :   }
     381             : 
     382       16132 :   LLVM_NODISCARD T pop_back_val() {
     383   202404708 :     T Result = ::std::move(this->back());
     384     1115985 :     this->pop_back();
     385       17543 :     return Result;
     386             :   }
     387             : 
     388             :   void swap(SmallVectorImpl &RHS);
     389             : 
     390             :   /// Add the specified range to the end of the SmallVector.
     391             :   template <typename in_iter,
     392             :             typename = typename std::enable_if<std::is_convertible<
     393             :                 typename std::iterator_traits<in_iter>::iterator_category,
     394             :                 std::input_iterator_tag>::value>::type>
     395   715892726 :   void append(in_iter in_start, in_iter in_end) {
     396   715904328 :     size_type NumInputs = std::distance(in_start, in_end);
     397             :     // Grow allocated space if needed.
     398  1431785452 :     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
     399     7081434 :       this->grow(this->size()+NumInputs);
     400             : 
     401             :     // Copy the new elements over.
     402     2337528 :     this->uninitialized_copy(in_start, in_end, this->end());
     403   715895329 :     this->setEnd(this->end() + NumInputs);
     404   715895329 :   }
     405             : 
     406             :   /// Add the specified range to the end of the SmallVector.
     407      975047 :   void append(size_type NumInputs, const T &Elt) {
     408             :     // Grow allocated space if needed.
     409     1950094 :     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
     410        8097 :       this->grow(this->size()+NumInputs);
     411             : 
     412             :     // Copy the new elements over.
     413      124551 :     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
     414      975047 :     this->setEnd(this->end() + NumInputs);
     415      975047 :   }
     416             : 
     417             :   void append(std::initializer_list<T> IL) {
     418    19214601 :     append(IL.begin(), IL.end());
     419             :   }
     420             : 
     421             :   // FIXME: Consider assigning over existing elements, rather than clearing &
     422             :   // re-initializing them - for all assign(...) variants.
     423             : 
     424    72977464 :   void assign(size_type NumElts, const T &Elt) {
     425      280508 :     clear();
     426    72977464 :     if (this->capacity() < NumElts)
     427        1299 :       this->grow(NumElts);
     428    72977464 :     this->setEnd(this->begin()+NumElts);
     429    58503653 :     std::uninitialized_fill(this->begin(), this->end(), Elt);
     430    72977464 :   }
     431             : 
     432             :   template <typename in_iter,
     433             :             typename = typename std::enable_if<std::is_convertible<
     434             :                 typename std::iterator_traits<in_iter>::iterator_category,
     435             :                 std::input_iterator_tag>::value>::type>
     436       59374 :   void assign(in_iter in_start, in_iter in_end) {
     437             :     clear();
     438       60843 :     append(in_start, in_end);
     439       59374 :   }
     440             : 
     441      455886 :   void assign(std::initializer_list<T> IL) {
     442      455325 :     clear();
     443             :     append(IL);
     444      455886 :   }
     445             : 
     446    15911676 :   iterator erase(const_iterator CI) {
     447             :     // Just cast away constness because this is a non-const member function.
     448             :     iterator I = const_cast<iterator>(CI);
     449             : 
     450             :     assert(I >= this->begin() && "Iterator to erase is out of bounds.");
     451             :     assert(I < this->end() && "Erasing at past-the-end iterator.");
     452             : 
     453             :     iterator N = I;
     454             :     // Shift all elts down one.
     455    24434924 :     std::move(I+1, this->end(), I);
     456             :     // Drop the last elt.
     457     8273456 :     this->pop_back();
     458    15911676 :     return(N);
     459             :   }
     460             : 
     461      925125 :   iterator erase(const_iterator CS, const_iterator CE) {
     462             :     // Just cast away constness because this is a non-const member function.
     463             :     iterator S = const_cast<iterator>(CS);
     464             :     iterator E = const_cast<iterator>(CE);
     465             : 
     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.");
     469             : 
     470             :     iterator N = S;
     471             :     // Shift all elts down.
     472             :     iterator I = std::move(E, this->end(), S);
     473             :     // Drop the last elts.
     474          22 :     this->destroy_range(I, this->end());
     475             :     this->setEnd(I);
     476      925125 :     return(N);
     477             :   }
     478             : 
     479     2110332 :   iterator insert(iterator I, T &&Elt) {
     480     2110332 :     if (I == this->end()) {  // Important special case for empty vector.
     481     1277230 :       this->push_back(::std::move(Elt));
     482     1277230 :       return this->end()-1;
     483             :     }
     484             : 
     485             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     486             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     487             : 
     488      833102 :     if (this->EndX >= this->CapacityX) {
     489       16514 :       size_t EltNo = I-this->begin();
     490           6 :       this->grow();
     491        8257 :       I = this->begin()+EltNo;
     492             :     }
     493             : 
     494      833803 :     ::new ((void*) this->end()) T(::std::move(this->back()));
     495             :     // Push everything else over.
     496      833101 :     std::move_backward(I, this->end()-1, this->end());
     497      833102 :     this->setEnd(this->end()+1);
     498             : 
     499             :     // If we just moved the element we're inserting, be sure to update
     500             :     // the reference.
     501             :     T *EltPtr = &Elt;
     502      833102 :     if (I <= EltPtr && EltPtr < this->EndX)
     503           0 :       ++EltPtr;
     504             : 
     505      832343 :     *I = ::std::move(*EltPtr);
     506      833046 :     return I;
     507             :   }
     508             : 
     509    10621058 :   iterator insert(iterator I, const T &Elt) {
     510    10621058 :     if (I == this->end()) {  // Important special case for empty vector.
     511     8615896 :       this->push_back(Elt);
     512     8615896 :       return this->end()-1;
     513             :     }
     514             : 
     515             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     516             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     517             : 
     518     2005162 :     if (this->EndX >= this->CapacityX) {
     519       48870 :       size_t EltNo = I-this->begin();
     520         232 :       this->grow();
     521       24435 :       I = this->begin()+EltNo;
     522             :     }
     523     2005182 :     ::new ((void*) this->end()) T(std::move(this->back()));
     524             :     // Push everything else over.
     525     2005142 :     std::move_backward(I, this->end()-1, this->end());
     526     2005162 :     this->setEnd(this->end()+1);
     527             : 
     528             :     // If we just moved the element we're inserting, be sure to update
     529             :     // the reference.
     530             :     const T *EltPtr = &Elt;
     531     2005162 :     if (I <= EltPtr && EltPtr < this->EndX)
     532         258 :       ++EltPtr;
     533             : 
     534     1973031 :     *I = *EltPtr;
     535     2005162 :     return I;
     536             :   }
     537             : 
     538      134703 :   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
     539             :     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
     540      269406 :     size_t InsertElt = I - this->begin();
     541             : 
     542      134703 :     if (I == this->end()) {  // Important special case for empty vector.
     543       28188 :       append(NumToInsert, Elt);
     544       28188 :       return this->begin()+InsertElt;
     545             :     }
     546             : 
     547             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     548             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     549             : 
     550             :     // Ensure there is enough space.
     551      106515 :     reserve(this->size() + NumToInsert);
     552             : 
     553             :     // Uninvalidate the iterator.
     554      106515 :     I = this->begin()+InsertElt;
     555             : 
     556             :     // If there are more elements between the insertion point and the end of the
     557             :     // range than there are being inserted, we can use a simple approach to
     558             :     // insertion.  Since we already reserved space, we know that this won't
     559             :     // reallocate the vector.
     560      106515 :     if (size_t(this->end()-I) >= NumToInsert) {
     561             :       T *OldEnd = this->end();
     562      195820 :       append(std::move_iterator<iterator>(this->end() - NumToInsert),
     563             :              std::move_iterator<iterator>(this->end()));
     564             : 
     565             :       // Copy the existing elements that get replaced.
     566             :       std::move_backward(I, OldEnd-NumToInsert, OldEnd);
     567             : 
     568        2539 :       std::fill_n(I, NumToInsert, Elt);
     569             :       return I;
     570             :     }
     571             : 
     572             :     // Otherwise, we're inserting more elements than exist already, and we're
     573             :     // not inserting at the end.
     574             : 
     575             :     // Move over the elements that we're about to overwrite.
     576             :     T *OldEnd = this->end();
     577        8605 :     this->setEnd(this->end() + NumToInsert);
     578             :     size_t NumOverwritten = OldEnd-I;
     579        8605 :     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
     580             : 
     581             :     // Replace the overwritten part.
     582         244 :     std::fill_n(I, NumOverwritten, Elt);
     583             : 
     584             :     // Insert the non-overwritten middle part.
     585        8605 :     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
     586           0 :     return I;
     587             :   }
     588             : 
     589             :   template <typename ItTy,
     590             :             typename = typename std::enable_if<std::is_convertible<
     591             :                 typename std::iterator_traits<ItTy>::iterator_category,
     592             :                 std::input_iterator_tag>::value>::type>
     593     5045549 :   iterator insert(iterator I, ItTy From, ItTy To) {
     594             :     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
     595    10091098 :     size_t InsertElt = I - this->begin();
     596             : 
     597     5045549 :     if (I == this->end()) {  // Important special case for empty vector.
     598     4963700 :       append(From, To);
     599     4963700 :       return this->begin()+InsertElt;
     600             :     }
     601             : 
     602             :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     603             :     assert(I <= this->end() && "Inserting past the end of the vector.");
     604             : 
     605       81849 :     size_t NumToInsert = std::distance(From, To);
     606             : 
     607             :     // Ensure there is enough space.
     608       81849 :     reserve(this->size() + NumToInsert);
     609             : 
     610             :     // Uninvalidate the iterator.
     611       81849 :     I = this->begin()+InsertElt;
     612             : 
     613             :     // If there are more elements between the insertion point and the end of the
     614             :     // range than there are being inserted, we can use a simple approach to
     615             :     // insertion.  Since we already reserved space, we know that this won't
     616             :     // reallocate the vector.
     617       81849 :     if (size_t(this->end()-I) >= NumToInsert) {
     618             :       T *OldEnd = this->end();
     619      160754 :       append(std::move_iterator<iterator>(this->end() - NumToInsert),
     620             :              std::move_iterator<iterator>(this->end()));
     621             : 
     622             :       // Copy the existing elements that get replaced.
     623             :       std::move_backward(I, OldEnd-NumToInsert, OldEnd);
     624             : 
     625             :       std::copy(From, To, I);
     626       78288 :       return I;
     627             :     }
     628             : 
     629             :     // Otherwise, we're inserting more elements than exist already, and we're
     630             :     // not inserting at the end.
     631             : 
     632             :     // Move over the elements that we're about to overwrite.
     633             :     T *OldEnd = this->end();
     634        1472 :     this->setEnd(this->end() + NumToInsert);
     635             :     size_t NumOverwritten = OldEnd-I;
     636        1472 :     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
     637             : 
     638             :     // Replace the overwritten part.
     639       29116 :     for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
     640       13822 :       *J = *From;
     641       13822 :       ++J; ++From;
     642             :     }
     643             : 
     644             :     // Insert the non-overwritten middle part.
     645             :     this->uninitialized_copy(From, To, OldEnd);
     646           0 :     return I;
     647             :   }
     648             : 
     649             :   void insert(iterator I, std::initializer_list<T> IL) {
     650             :     insert(I, IL.begin(), IL.end());
     651             :   }
     652             : 
     653    58901002 :   template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
     654    58901002 :     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
     655       82943 :       this->grow();
     656    95880207 :     ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
     657    58901002 :     this->setEnd(this->end() + 1);
     658    58901002 :   }
     659             : 
     660             :   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
     661             : 
     662             :   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
     663             : 
     664    34368692 :   bool operator==(const SmallVectorImpl &RHS) const {
     665    34398005 :     if (this->size() != RHS.size()) return false;
     666         109 :     return std::equal(this->begin(), this->end(), RHS.begin());
     667             :   }
     668          10 :   bool operator!=(const SmallVectorImpl &RHS) const {
     669     9491165 :     return !(*this == RHS);
     670             :   }
     671             : 
     672     1356171 :   bool operator<(const SmallVectorImpl &RHS) const {
     673             :     return std::lexicographical_compare(this->begin(), this->end(),
     674     1356171 :                                         RHS.begin(), RHS.end());
     675             :   }
     676             : 
     677             :   /// Set the array size to \p N, which the current array must have enough
     678             :   /// capacity for.
     679             :   ///
     680             :   /// This does not construct or destroy any elements in the vector.
     681             :   ///
     682             :   /// Clients can use this in conjunction with capacity() to write past the end
     683             :   /// of the buffer when they know that more elements are available, and only
     684             :   /// update the size later. This avoids the cost of value initializing elements
     685             :   /// which will only be overwritten.
     686             :   void set_size(size_type N) {
     687             :     assert(N <= this->capacity());
     688    20498108 :     this->setEnd(this->begin() + N);
     689             :   }
     690             : };
     691             : 
     692             : template <typename T>
     693     8343670 : void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
     694     8343670 :   if (this == &RHS) return;
     695             : 
     696             :   // We can only avoid copying elements if neither vector is small.
     697     8412653 :   if (!this->isSmall() && !RHS.isSmall()) {
     698             :     std::swap(this->BeginX, RHS.BeginX);
     699             :     std::swap(this->EndX, RHS.EndX);
     700             :     std::swap(this->CapacityX, RHS.CapacityX);
     701             :     return;
     702             :   }
     703     8337228 :   if (RHS.size() > this->capacity())
     704           9 :     this->grow(RHS.size());
     705     8337336 :   if (this->size() > RHS.capacity())
     706           2 :     RHS.grow(this->size());
     707             : 
     708             :   // Swap the shared elements.
     709             :   size_t NumShared = this->size();
     710     8337336 :   if (NumShared > RHS.size()) NumShared = RHS.size();
     711    42018682 :   for (size_type i = 0; i != NumShared; ++i)
     712          36 :     std::swap((*this)[i], RHS[i]);
     713             : 
     714             :   // Copy over the extra elts.
     715     8337336 :   if (this->size() > RHS.size()) {
     716      479912 :     size_t EltDiff = this->size() - RHS.size();
     717      479912 :     this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
     718      479912 :     RHS.setEnd(RHS.end()+EltDiff);
     719      479912 :     this->destroy_range(this->begin()+NumShared, this->end());
     720        3117 :     this->setEnd(this->begin()+NumShared);
     721     7857424 :   } else if (RHS.size() > this->size()) {
     722      163403 :     size_t EltDiff = RHS.size() - this->size();
     723      163403 :     this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
     724      163403 :     this->setEnd(this->end() + EltDiff);
     725      163403 :     this->destroy_range(RHS.begin()+NumShared, RHS.end());
     726         100 :     RHS.setEnd(RHS.begin()+NumShared);
     727             :   }
     728             : }
     729             : 
     730             : template <typename T>
     731    44414708 : SmallVectorImpl<T> &SmallVectorImpl<T>::
     732             :   operator=(const SmallVectorImpl<T> &RHS) {
     733             :   // Avoid self-assignment.
     734    44414708 :   if (this == &RHS) return *this;
     735             : 
     736             :   // If we already have sufficient space, assign the common elements, then
     737             :   // destroy any excess.
     738             :   size_t RHSSize = RHS.size();
     739             :   size_t CurSize = this->size();
     740    44414676 :   if (CurSize >= RHSSize) {
     741             :     // Assign common elements.
     742             :     iterator NewEnd;
     743     3340258 :     if (RHSSize)
     744       80216 :       NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
     745             :     else
     746             :       NewEnd = this->begin();
     747             : 
     748             :     // Destroy excess elements.
     749         133 :     this->destroy_range(NewEnd, this->end());
     750             : 
     751             :     // Trim.
     752             :     this->setEnd(NewEnd);
     753     3340258 :     return *this;
     754             :   }
     755             : 
     756             :   // If we have to grow to have enough elements, destroy the current elements.
     757             :   // This allows us to avoid copying them during the grow.
     758             :   // FIXME: don't do this if they're efficiently moveable.
     759    41074418 :   if (this->capacity() < RHSSize) {
     760             :     // Destroy current elements.
     761           0 :     this->destroy_range(this->begin(), this->end());
     762             :     this->setEnd(this->begin());
     763             :     CurSize = 0;
     764        2463 :     this->grow(RHSSize);
     765    36711480 :   } else if (CurSize) {
     766             :     // Otherwise, use assignment for the already-constructed elements.
     767       46620 :     std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
     768             :   }
     769             : 
     770             :   // Copy construct the new elements in place.
     771    82148832 :   this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
     772    38977140 :                            this->begin()+CurSize);
     773             : 
     774             :   // Set end.
     775    41074416 :   this->setEnd(this->begin()+RHSSize);
     776    41074416 :   return *this;
     777             : }
     778             : 
     779             : template <typename T>
     780    38000481 : SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
     781             :   // Avoid self-assignment.
     782    38000481 :   if (this == &RHS) return *this;
     783             : 
     784             :   // If the RHS isn't small, clear this vector and then steal its buffer.
     785    38000482 :   if (!RHS.isSmall()) {
     786           7 :     this->destroy_range(this->begin(), this->end());
     787      518588 :     if (!this->isSmall()) free(this->begin());
     788      518588 :     this->BeginX = RHS.BeginX;
     789      518588 :     this->EndX = RHS.EndX;
     790      518588 :     this->CapacityX = RHS.CapacityX;
     791             :     RHS.resetToSmall();
     792      518588 :     return *this;
     793             :   }
     794             : 
     795             :   // If we already have sufficient space, assign the common elements, then
     796             :   // destroy any excess.
     797             :   size_t RHSSize = RHS.size();
     798             :   size_t CurSize = this->size();
     799    37481894 :   if (CurSize >= RHSSize) {
     800             :     // Assign common elements.
     801             :     iterator NewEnd = this->begin();
     802    13977413 :     if (RHSSize)
     803             :       NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
     804             : 
     805             :     // Destroy excess elements and trim the bounds.
     806           0 :     this->destroy_range(NewEnd, this->end());
     807             :     this->setEnd(NewEnd);
     808             : 
     809             :     // Clear the RHS.
     810        1935 :     RHS.clear();
     811             : 
     812    13977413 :     return *this;
     813             :   }
     814             : 
     815             :   // If we have to grow to have enough elements, destroy the current elements.
     816             :   // This allows us to avoid copying them during the grow.
     817             :   // FIXME: this may not actually make any sense if we can efficiently move
     818             :   // elements.
     819    23504481 :   if (this->capacity() < RHSSize) {
     820             :     // Destroy current elements.
     821           0 :     this->destroy_range(this->begin(), this->end());
     822             :     this->setEnd(this->begin());
     823             :     CurSize = 0;
     824        1289 :     this->grow(RHSSize);
     825    23503044 :   } else if (CurSize) {
     826             :     // Otherwise, use assignment for the already-constructed elements.
     827      476802 :     std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
     828             :   }
     829             : 
     830             :   // Move-construct the new elements in place.
     831    47008962 :   this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
     832    19734484 :                            this->begin()+CurSize);
     833             : 
     834             :   // Set end.
     835    23504481 :   this->setEnd(this->begin()+RHSSize);
     836             : 
     837      630508 :   RHS.clear();
     838    23504481 :   return *this;
     839             : }
     840             : 
     841             : /// Storage for the SmallVector elements which aren't contained in
     842             : /// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
     843             : /// element is in the base class. This is specialized for the N=1 and N=0 cases
     844             : /// to avoid allocating unnecessary storage.
     845             : template <typename T, unsigned N>
     846             : struct SmallVectorStorage {
     847             :   typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
     848             : };
     849             : template <typename T> struct SmallVectorStorage<T, 1> {};
     850             : template <typename T> struct SmallVectorStorage<T, 0> {};
     851             : 
     852             : /// This is a 'vector' (really, a variable-sized array), optimized
     853             : /// for the case when the array is small.  It contains some number of elements
     854             : /// in-place, which allows it to avoid heap allocation when the actual number of
     855             : /// elements is below that threshold.  This allows normal "small" cases to be
     856             : /// fast without losing generality for large inputs.
     857             : ///
     858             : /// Note that this does not attempt to be exception safe.
     859             : ///
     860             : template <typename T, unsigned N>
     861             : class SmallVector : public SmallVectorImpl<T> {
     862             :   /// Inline space for elements which aren't stored in the base class.
     863             :   SmallVectorStorage<T, N> Storage;
     864             : 
     865             : public:
     866  2527662945 :   SmallVector() : SmallVectorImpl<T>(N) {}
     867             : 
     868    74438758 :   ~SmallVector() {
     869             :     // Destroy the constructed elements in the vector.
     870     3308917 :     this->destroy_range(this->begin(), this->end());
     871   673526022 :   }
     872             : 
     873    71676918 :   explicit SmallVector(size_t Size, const T &Value = T())
     874     8759484 :     : SmallVectorImpl<T>(N) {
     875    72057068 :     this->assign(Size, Value);
     876             :   }
     877             : 
     878             :   template <typename ItTy,
     879             :             typename = typename std::enable_if<std::is_convertible<
     880             :                 typename std::iterator_traits<ItTy>::iterator_category,
     881             :                 std::input_iterator_tag>::value>::type>
     882    85795059 :   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
     883    85810352 :     this->append(S, E);
     884        5469 :   }
     885             : 
     886             :   template <typename RangeTy>
     887      118084 :   explicit SmallVector(const iterator_range<RangeTy> &R)
     888        1273 :       : SmallVectorImpl<T>(N) {
     889      118182 :     this->append(R.begin(), R.end());
     890         104 :   }
     891             : 
     892    18007132 :   SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
     893        2857 :     this->assign(IL);
     894             :   }
     895             : 
     896    46253741 :   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
     897    48680871 :     if (!RHS.empty())
     898    30406429 :       SmallVectorImpl<T>::operator=(RHS);
     899             :   }
     900             : 
     901             :   const SmallVector &operator=(const SmallVector &RHS) {
     902    10874356 :     SmallVectorImpl<T>::operator=(RHS);
     903             :     return *this;
     904             :   }
     905             : 
     906    25176678 :   SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
     907    24876962 :     if (!RHS.empty())
     908    16864286 :       SmallVectorImpl<T>::operator=(::std::move(RHS));
     909             :   }
     910             : 
     911       91759 :   SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
     912         248 :     if (!RHS.empty())
     913       91759 :       SmallVectorImpl<T>::operator=(::std::move(RHS));
     914             :   }
     915             : 
     916             :   const SmallVector &operator=(SmallVector &&RHS) {
     917    18470752 :     SmallVectorImpl<T>::operator=(::std::move(RHS));
     918             :     return *this;
     919             :   }
     920             : 
     921             :   const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
     922        1679 :     SmallVectorImpl<T>::operator=(::std::move(RHS));
     923             :     return *this;
     924             :   }
     925             : 
     926             :   const SmallVector &operator=(std::initializer_list<T> IL) {
     927      572275 :     this->assign(IL);
     928             :     return *this;
     929             :   }
     930             : };
     931             : 
     932             : template <typename T, unsigned N>
     933             : inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
     934          13 :   return X.capacity_in_bytes();
     935             : }
     936             : 
     937             : } // end namespace llvm
     938             : 
     939             : namespace std {
     940             : 
     941             :   /// Implement std::swap in terms of SmallVector swap.
     942             :   template<typename T>
     943             :   inline void
     944             :   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
     945       34689 :     LHS.swap(RHS);
     946             :   }
     947             : 
     948             :   /// Implement std::swap in terms of SmallVector swap.
     949             :   template<typename T, unsigned N>
     950             :   inline void
     951             :   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
     952     1299210 :     LHS.swap(RHS);
     953             :   }
     954             : 
     955             : } // end namespace std
     956             : 
     957             : #endif // LLVM_ADT_SMALLVECTOR_H

Generated by: LCOV version 1.13