LCOV - code coverage report
Current view: top level - include/llvm/ADT - SmallVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1977 2315 85.4 %
Date: 2018-09-23 13:06:45 Functions: 3960 7435 53.3 %
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;
      42             :   unsigned Size = 0, Capacity;
      43             : 
      44             :   SmallVectorBase() = delete;
      45             :   SmallVectorBase(void *FirstEl, size_t Capacity)
      46  9528880689 :       : BeginX(FirstEl), Capacity(Capacity) {}
      47             : 
      48             :   /// This is an implementation of the grow() method which only works
      49             :   /// on POD-like data types and is out of line to reduce code duplication.
      50             :   void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
      51             : 
      52             : public:
      53 13711923162 :   size_t size() const { return Size; }
      54  2884349079 :   size_t capacity() const { return Capacity; }
      55             : 
      56    28790980 :   LLVM_NODISCARD bool empty() const { return !Size; }
      57             : 
      58             :   /// Set the array size to \p N, which the current array must have enough
      59             :   /// capacity for.
      60             :   ///
      61             :   /// This does not construct or destroy any elements in the vector.
      62             :   ///
      63             :   /// Clients can use this in conjunction with capacity() to write past the end
      64             :   /// of the buffer when they know that more elements are available, and only
      65             :   /// update the size later. This avoids the cost of value initializing elements
      66             :   /// which will only be overwritten.
      67           0 :   void set_size(size_t Size) {
      68             :     assert(Size <= capacity());
      69 20961112303 :     this->Size = Size;
      70           0 :   }
      71             : };
      72             : 
      73             : /// Figure out the offset of the first element.
      74             : template <class T, typename = void> struct SmallVectorAlignmentAndSize {
      75             :   AlignedCharArrayUnion<SmallVectorBase> Base;
      76             :   AlignedCharArrayUnion<T> FirstEl;
      77             : };
      78             : 
      79             : /// This is the part of SmallVectorTemplateBase which does not depend on whether
      80             : /// the type T is a POD. The extra dummy template argument is used by ArrayRef
      81             : /// to avoid unnecessarily requiring T to be complete.
      82             : template <typename T, typename = void>
      83             : class SmallVectorTemplateCommon : public SmallVectorBase {
      84             :   /// Find the address of the first element.  For this pointer math to be valid
      85             :   /// with small-size of 0 for T with lots of alignment, it's important that
      86             :   /// SmallVectorStorage is properly-aligned even for small-size of 0.
      87             :   void *getFirstEl() const {
      88             :     return const_cast<void *>(reinterpret_cast<const void *>(
      89             :         reinterpret_cast<const char *>(this) +
      90  3788754670 :         offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
      91             :   }
      92             :   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
      93             : 
      94             : protected:
      95             :   SmallVectorTemplateCommon(size_t Size)
      96             :       : SmallVectorBase(getFirstEl(), Size) {}
      97             : 
      98             :   void grow_pod(size_t MinCapacity, size_t TSize) {
      99   122668707 :     SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize);
     100             :   }
     101             : 
     102             :   /// Return true if this is a smallvector which has not had dynamic
     103             :   /// memory allocated for it.
     104   672431058 :   bool isSmall() const { return BeginX == getFirstEl(); }
     105             : 
     106             :   /// Put this vector in a state of being small.
     107             :   void resetToSmall() {
     108      950642 :     BeginX = getFirstEl();
     109      950642 :     Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
     110             :   }
     111             : 
     112             : public:
     113             :   using size_type = size_t;
     114             :   using difference_type = ptrdiff_t;
     115             :   using value_type = T;
     116             :   using iterator = T *;
     117             :   using const_iterator = const T *;
     118             : 
     119             :   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     120             :   using reverse_iterator = std::reverse_iterator<iterator>;
     121             : 
     122             :   using reference = T &;
     123             :   using const_reference = const T &;
     124             :   using pointer = T *;
     125             :   using const_pointer = const T *;
     126             : 
     127             :   // forward iterator creation methods.
     128             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     129 23511871518 :   iterator begin() { return (iterator)this->BeginX; }
     130             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     131 12156286823 :   const_iterator begin() const { return (const_iterator)this->BeginX; }
     132             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     133 37500801986 :   iterator end() { return begin() + size(); }
     134             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     135  4213905956 :   const_iterator end() const { return begin() + size(); }
     136             : 
     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           0 :   reverse_iterator rend()              { return reverse_iterator(begin()); }
     141           0 :   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
     142             : 
     143             :   size_type size_in_bytes() const { return size() * sizeof(T); }
     144             :   size_type max_size() const { return size_type(-1) / sizeof(T); }
     145             : 
     146          14 :   size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
     147             : 
     148             :   /// Return a pointer to the vector's buffer, even if empty().
     149           0 :   pointer data() { return pointer(begin()); }
     150             :   /// Return a pointer to the vector's buffer, even if empty().
     151           0 :   const_pointer data() const { return const_pointer(begin()); }
     152             : 
     153             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     154             :   reference operator[](size_type idx) {
     155             :     assert(idx < size());
     156  4835926201 :     return begin()[idx];
     157             :   }
     158             :   LLVM_ATTRIBUTE_ALWAYS_INLINE
     159             :   const_reference operator[](size_type idx) const {
     160             :     assert(idx < size());
     161 14609627063 :     return begin()[idx];
     162             :   }
     163             : 
     164           0 :   reference front() {
     165             :     assert(!empty());
     166           0 :     return begin()[0];
     167             :   }
     168           0 :   const_reference front() const {
     169             :     assert(!empty());
     170           0 :     return begin()[0];
     171             :   }
     172           0 : 
     173             :   reference back() {
     174           0 :     assert(!empty());
     175  1802692399 :     return end()[-1];
     176           0 :   }
     177             :   const_reference back() const {
     178           0 :     assert(!empty());
     179  1135240934 :     return end()[-1];
     180           0 :   }
     181             : };
     182           0 : 
     183  1058487205 : /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method
     184           0 : /// implementations that are designed to work with non-POD-like T's.
     185             : template <typename T, bool isPodLike>
     186           0 : class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
     187   106007790 : protected:
     188             :   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
     189             : 
     190     7563251 :   static void destroy_range(T *S, T *E) {
     191   892375816 :     while (S != E) {
     192   203137432 :       --E;
     193    11947646 :       E->~T();
     194             :     }
     195    13539383 :   }
     196        5449 : 
     197       66203 :   /// Move the range [I, E) into the uninitialized memory starting with "Dest",
     198     1423819 :   /// constructing elements as needed.
     199   310873356 :   template<typename It1, typename It2>
     200   242598232 :   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
     201     8821739 :     std::uninitialized_copy(std::make_move_iterator(I),
     202      667587 :                             std::make_move_iterator(E), Dest);
     203    12535586 :   }
     204     1295677 : 
     205      933494 :   /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
     206       56327 :   /// constructing elements as needed.
     207     5228529 :   template<typename It1, typename It2>
     208      866108 :   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
     209     2680912 :     std::uninitialized_copy(I, E, Dest);
     210     1529405 :   }
     211      336799 : 
     212        2381 :   /// Grow the allocated memory (without initializing new elements), doubling
     213      596175 :   /// the size of the allocated memory. Guarantees space for at least one more
     214      595173 :   /// element, or MinSize more elements if specified.
     215      929591 :   void grow(size_t MinSize = 0);
     216      139472 : 
     217      399136 : public:
     218   192170624 :   void push_back(const T &Elt) {
     219   192506133 :     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
     220     1502412 :       this->grow();
     221    27734387 :     ::new ((void*) this->end()) T(Elt);
     222   125064148 :     this->set_size(this->size() + 1);
     223   191910959 :   }
     224    98271620 : 
     225   113442585 :   void push_back(T &&Elt) {
     226    16150306 :     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
     227     1106132 :       this->grow();
     228   101217692 :     ::new ((void*) this->end()) T(::std::move(Elt));
     229   111593143 :     this->set_size(this->size() + 1);
     230    51955227 :   }
     231    39664865 : 
     232     3511172 :   void pop_back() {
     233   148634024 :     this->set_size(this->size() - 1);
     234   157300363 :     this->end()->~T();
     235    41596944 :   }
     236   125770562 : };
     237   165254439 : 
     238   162641534 : // Define this out-of-line to dissuade the C++ compiler from inlining it.
     239       20724 : template <typename T, bool isPodLike>
     240     3330518 : void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
     241   355307769 :   if (MinSize > UINT32_MAX)
     242   351562400 :     report_bad_alloc_error("SmallVector capacity overflow during allocation");
     243     1432832 : 
     244     4407946 :   // Always grow, even from zero.
     245    33061836 :   size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
     246    29262160 :   NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX));
     247     8491945 :   T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
     248     4025351 : 
     249     5535384 :   // Move the elements over.
     250     2075423 :   this->uninitialized_move(this->begin(), this->end(), NewElts);
     251       67583 : 
     252     2316109 :   // Destroy the original elements.
     253     7745377 :   destroy_range(this->begin(), this->end());
     254     4953592 : 
     255     3222846 :   // If this wasn't grown from the inline copy, deallocate the old space.
     256    12686699 :   if (!this->isSmall())
     257    12621851 :     free(this->begin());
     258      722194 : 
     259    14103406 :   this->BeginX = NewElts;
     260     3441009 :   this->Capacity = NewCapacity;
     261     4687591 : }
     262     2881353 : 
     263     1891878 : 
     264     2718461 : /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
     265     3335359 : /// implementations that are designed to work with POD-like T's.
     266     1522186 : template <typename T>
     267     4543021 : class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
     268     4620874 : protected:
     269     4362747 :   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
     270     1564256 : 
     271     2646879 :   // No need to do a destroy loop for POD's.
     272     1049475 :   static void destroy_range(T *, T *) {}
     273      901993 : 
     274      674335 :   /// Move the range [I, E) onto the uninitialized memory
     275     1770655 :   /// starting with "Dest", constructing elements into it as needed.
     276        2288 :   template<typename It1, typename It2>
     277     1089896 :   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
     278     2666778 :     // Just do a copy.
     279      945228 :     uninitialized_copy(I, E, Dest);
     280       49801 :   }
     281     2384033 : 
     282     1804612 :   /// Copy the range [I, E) onto the uninitialized memory
     283     1901601 :   /// starting with "Dest", constructing elements into it as needed.
     284     1695462 :   template<typename It1, typename It2>
     285     3823691 :   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
     286        4153 :     // Arbitrary iterator types; just use the basic implementation.
     287     2824357 :     std::uninitialized_copy(I, E, Dest);
     288     2492433 :   }
     289     1613753 : 
     290      361263 :   /// Copy the range [I, E) onto the uninitialized memory
     291      218462 :   /// starting with "Dest", constructing elements into it as needed.
     292     2210124 :   template <typename T1, typename T2>
     293     2256970 :   static void uninitialized_copy(
     294      183356 :       T1 *I, T1 *E, T2 *Dest,
     295     1720954 :       typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
     296      394459 :                                            T2>::value>::type * = nullptr) {
     297     2616334 :     // Use memcpy for PODs iterated by pointers (which includes SmallVector
     298     2222631 :     // iterators): std::uninitialized_copy optimizes to memmove, but we can
     299     2223469 :     // use memcpy here. Note that I and E are iterators and thus might be
     300       79196 :     // invalid for memcpy if they are equal.
     301  1577927378 :     if (I != E)
     302  1617326177 :       memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
     303      529571 :   }
     304       77128 : 
     305      182962 :   /// Double the size of the allocated memory, guaranteeing space for at
     306       14919 :   /// least one more element or MinSize if specified.
     307      122786 :   void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
     308     2313986 : 
     309     7289606 : public:
     310 18823378642 :   void push_back(const T &Elt) {
     311 18807320449 :     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
     312     2456024 :       this->grow();
     313 18807627746 :     memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
     314 18805285560 :     this->set_size(this->size() + 1);
     315 18805454001 :   }
     316   215004675 : 
     317   248309694 :   void pop_back() { this->set_size(this->size() - 1); }
     318    34244238 : };
     319   247474862 : 
     320   214872641 : /// This class consists of common code factored out of the SmallVector class to
     321   247474707 : /// reduce code duplication based on the SmallVector 'N' template parameter.
     322  2161823776 : template <typename T>
     323  2161817711 : class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
     324        2264 :   using SuperClass = SmallVectorTemplateBase<T, isPodLike<T>::value>;
     325  2129332153 : 
     326  2129437117 : public:
     327  2129437932 :   using iterator = typename SuperClass::iterator;
     328 15372859683 :   using const_iterator = typename SuperClass::const_iterator;
     329 15423017143 :   using size_type = typename SuperClass::size_type;
     330       11510 : 
     331 15373083383 : protected:
     332 16043141210 :   // Default ctor - Initialize to empty.
     333 16043151877 :   explicit SmallVectorImpl(unsigned N)
     334   368841027 :       : SmallVectorTemplateBase<T, isPodLike<T>::value>(N) {}
     335  1052536252 : 
     336   671753808 : public:
     337  1040656223 :   SmallVectorImpl(const SmallVectorImpl &) = delete;
     338   401658157 : 
     339   405519945 :   ~SmallVectorImpl() {
     340   166505618 :     // Subclass has already destructed this vector's elements.
     341   201096521 :     // If this wasn't grown from the inline copy, deallocate the old space.
     342   307461275 :     if (!this->isSmall())
     343  1334471403 :       free(this->begin());
     344  1325239104 :   }
     345   216441813 : 
     346  1236822169 :   void clear() {
     347  1218267724 :     this->destroy_range(this->begin(), this->end());
     348  1368365946 :     this->Size = 0;
     349   235149227 :   }
     350   149871040 : 
     351   139135230 :   void resize(size_type N) {
     352   216300529 :     if (N < this->size()) {
     353   167628275 :       this->destroy_range(this->begin()+N, this->end());
     354   426617058 :       this->set_size(N);
     355   252484385 :     } else if (N > this->size()) {
     356   250822070 :       if (this->capacity() < N)
     357   330519356 :         this->grow(N);
     358  1324897182 :       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
     359  1373117965 :         new (&*I) T();
     360  1472890838 :       this->set_size(N);
     361   181603239 :     }
     362   145821826 :   }
     363   100402016 : 
     364   117711551 :   void resize(size_type N, const T &NV) {
     365   352097134 :     if (N < this->size()) {
     366  1824584743 :       this->destroy_range(this->begin()+N, this->end());
     367   236504836 :       this->set_size(N);
     368   356110824 :     } else if (N > this->size()) {
     369   305978982 :       if (this->capacity() < N)
     370   649074876 :         this->grow(N);
     371   125937614 :       std::uninitialized_fill(this->end(), this->begin()+N, NV);
     372   152490281 :       this->set_size(N);
     373   104266697 :     }
     374   109108476 :   }
     375    68073963 : 
     376   388686267 :   void reserve(size_type N) {
     377   312838197 :     if (this->capacity() < N)
     378   621455546 :       this->grow(N);
     379   296196608 :   }
     380   251206842 : 
     381   135533252 :   LLVM_NODISCARD T pop_back_val() {
     382   106103122 :     T Result = ::std::move(this->back());
     383    53099168 :     this->pop_back();
     384   314248381 :     return Result;
     385    52683110 :   }
     386    86638993 : 
     387   215976379 :   void swap(SmallVectorImpl &RHS);
     388   172922715 : 
     389   104755421 :   /// Add the specified range to the end of the SmallVector.
     390   276030522 :   template <typename in_iter,
     391   179094462 :             typename = typename std::enable_if<std::is_convertible<
     392   206196953 :                 typename std::iterator_traits<in_iter>::iterator_category,
     393   206741681 :                 std::input_iterator_tag>::value>::type>
     394  1056088406 :   void append(in_iter in_start, in_iter in_end) {
     395  1064680621 :     size_type NumInputs = std::distance(in_start, in_end);
     396   256707110 :     // Grow allocated space if needed.
     397  1436294924 :     if (NumInputs > this->capacity() - this->size())
     398   548252892 :       this->grow(this->size()+NumInputs);
     399   261277261 : 
     400   638863224 :     // Copy the new elements over.
     401   640166009 :     this->uninitialized_copy(in_start, in_end, this->end());
     402  2428405417 :     this->set_size(this->size() + NumInputs);
     403  1213012169 :   }
     404   666626889 : 
     405   383176961 :   /// Add the specified range to the end of the SmallVector.
     406   282673315 :   void append(size_type NumInputs, const T &Elt) {
     407   205811491 :     // Grow allocated space if needed.
     408   225807485 :     if (NumInputs > this->capacity() - this->size())
     409   251082813 :       this->grow(this->size()+NumInputs);
     410   259008381 : 
     411    85216791 :     // Copy the new elements over.
     412   579152785 :     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
     413   584039231 :     this->set_size(this->size() + NumInputs);
     414   285527599 :   }
     415   378199814 : 
     416   365695699 :   void append(std::initializer_list<T> IL) {
     417   323016817 :     append(IL.begin(), IL.end());
     418    28251156 :   }
     419   146951902 : 
     420   867477609 :   // FIXME: Consider assigning over existing elements, rather than clearing &
     421   391519941 :   // re-initializing them - for all assign(...) variants.
     422   234306577 : 
     423   240610302 :   void assign(size_type NumElts, const T &Elt) {
     424   293991110 :     clear();
     425   207797068 :     if (this->capacity() < NumElts)
     426   134609128 :       this->grow(NumElts);
     427   206465502 :     this->set_size(NumElts);
     428   231424543 :     std::uninitialized_fill(this->begin(), this->end(), Elt);
     429   232300208 :   }
     430    56370613 : 
     431    99921770 :   template <typename in_iter,
     432   196942301 :             typename = typename std::enable_if<std::is_convertible<
     433   161789713 :                 typename std::iterator_traits<in_iter>::iterator_category,
     434   120929829 :                 std::input_iterator_tag>::value>::type>
     435   201868713 :   void assign(in_iter in_start, in_iter in_end) {
     436   230884130 :     clear();
     437   181061324 :     append(in_start, in_end);
     438   150750966 :   }
     439   235450459 : 
     440   225650121 :   void assign(std::initializer_list<T> IL) {
     441   152998432 :     clear();
     442   417381606 :     append(IL);
     443   297796668 :   }
     444   224638149 : 
     445   213901003 :   iterator erase(const_iterator CI) {
     446   271284950 :     // Just cast away constness because this is a non-const member function.
     447   235755362 :     iterator I = const_cast<iterator>(CI);
     448    78350240 : 
     449    64280273 :     assert(I >= this->begin() && "Iterator to erase is out of bounds.");
     450   162502275 :     assert(I < this->end() && "Erasing at past-the-end iterator.");
     451   175703594 : 
     452   114606535 :     iterator N = I;
     453   269577794 :     // Shift all elts down one.
     454   265509083 :     std::move(I+1, this->end(), I);
     455   266913021 :     // Drop the last elt.
     456   244065211 :     this->pop_back();
     457   140429166 :     return(N);
     458   179106487 :   }
     459   165912550 : 
     460   117396806 :   iterator erase(const_iterator CS, const_iterator CE) {
     461    98786603 :     // Just cast away constness because this is a non-const member function.
     462   327077391 :     iterator S = const_cast<iterator>(CS);
     463   234488972 :     iterator E = const_cast<iterator>(CE);
     464    72372591 : 
     465    69245150 :     assert(S >= this->begin() && "Range to erase is out of bounds.");
     466    88581941 :     assert(S <= E && "Trying to erase invalid range.");
     467    85100189 :     assert(E <= this->end() && "Trying to erase past the end.");
     468    77401644 : 
     469   117681401 :     iterator N = S;
     470   132796212 :     // Shift all elts down.
     471   124955938 :     iterator I = std::move(E, this->end(), S);
     472    77343987 :     // Drop the last elts.
     473   564521323 :     this->destroy_range(I, this->end());
     474   558060315 :     this->set_size(I - this->begin());
     475   142695619 :     return(N);
     476   513954321 :   }
     477   530400827 : 
     478   560606349 :   iterator insert(iterator I, T &&Elt) {
     479    58213838 :     if (I == this->end()) {  // Important special case for empty vector.
     480    62997272 :       this->push_back(::std::move(Elt));
     481    34320989 :       return this->end()-1;
     482    48283562 :     }
     483   636353926 : 
     484    61874327 :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     485   110670970 :     assert(I <= this->end() && "Inserting past the end of the vector.");
     486   110101588 : 
     487   168530887 :     if (this->size() >= this->capacity()) {
     488   181109040 :       size_t EltNo = I-this->begin();
     489    61493303 :       this->grow();
     490   161646448 :       I = this->begin()+EltNo;
     491   213340967 :     }
     492   127289377 : 
     493    33850780 :     ::new ((void*) this->end()) T(::std::move(this->back()));
     494    20642720 :     // Push everything else over.
     495    19329696 :     std::move_backward(I, this->end()-1, this->end());
     496    67612420 :     this->set_size(this->size() + 1);
     497    82552859 : 
     498    70285824 :     // If we just moved the element we're inserting, be sure to update
     499    72317230 :     // the reference.
     500    91985339 :     T *EltPtr = &Elt;
     501   196879590 :     if (I <= EltPtr && EltPtr < this->end())
     502    59192751 :       ++EltPtr;
     503    51023926 : 
     504    21729788 :     *I = ::std::move(*EltPtr);
     505    45029436 :     return I;
     506    63466307 :   }
     507    45504107 : 
     508   181631826 :   iterator insert(iterator I, const T &Elt) {
     509    65763025 :     if (I == this->end()) {  // Important special case for empty vector.
     510    40640509 :       this->push_back(Elt);
     511    77582082 :       return this->end()-1;
     512    64436916 :     }
     513    44590790 : 
     514    91353355 :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     515    75798843 :     assert(I <= this->end() && "Inserting past the end of the vector.");
     516    97263903 : 
     517    97928113 :     if (this->size() >= this->capacity()) {
     518   269347406 :       size_t EltNo = I-this->begin();
     519   285421056 :       this->grow();
     520   249089911 :       I = this->begin()+EltNo;
     521   322404376 :     }
     522   511022118 :     ::new ((void*) this->end()) T(std::move(this->back()));
     523   260663380 :     // Push everything else over.
     524   533522203 :     std::move_backward(I, this->end()-1, this->end());
     525   364270580 :     this->set_size(this->size() + 1);
     526   316884242 : 
     527    37427047 :     // If we just moved the element we're inserting, be sure to update
     528    40225208 :     // the reference.
     529    22455168 :     const T *EltPtr = &Elt;
     530   196975297 :     if (I <= EltPtr && EltPtr < this->end())
     531    68295526 :       ++EltPtr;
     532    22001747 : 
     533   172686001 :     *I = *EltPtr;
     534   143904165 :     return I;
     535    17863958 :   }
     536   297937526 : 
     537   148987619 :   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
     538   240263267 :     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
     539   178198999 :     size_t InsertElt = I - this->begin();
     540   123380045 : 
     541    46901145 :     if (I == this->end()) {  // Important special case for empty vector.
     542   113070050 :       append(NumToInsert, Elt);
     543   194014587 :       return this->begin()+InsertElt;
     544   204319870 :     }
     545   262551387 : 
     546   384284351 :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     547   108270297 :     assert(I <= this->end() && "Inserting past the end of the vector.");
     548   326809028 : 
     549   265024613 :     // Ensure there is enough space.
     550   398603605 :     reserve(this->size() + NumToInsert);
     551   300265180 : 
     552   305637685 :     // Uninvalidate the iterator.
     553    18440659 :     I = this->begin()+InsertElt;
     554   304365474 : 
     555   370018268 :     // If there are more elements between the insertion point and the end of the
     556   372982520 :     // range than there are being inserted, we can use a simple approach to
     557     9120116 :     // insertion.  Since we already reserved space, we know that this won't
     558    19519404 :     // reallocate the vector.
     559    76102582 :     if (size_t(this->end()-I) >= NumToInsert) {
     560   234018726 :       T *OldEnd = this->end();
     561   558874433 :       append(std::move_iterator<iterator>(this->end() - NumToInsert),
     562    22102268 :              std::move_iterator<iterator>(this->end()));
     563   238752880 : 
     564   236915608 :       // Copy the existing elements that get replaced.
     565   239653507 :       std::move_backward(I, OldEnd-NumToInsert, OldEnd);
     566    90300605 : 
     567    41685014 :       std::fill_n(I, NumToInsert, Elt);
     568    14916419 :       return I;
     569     8075557 :     }
     570   157815429 : 
     571    18556373 :     // Otherwise, we're inserting more elements than exist already, and we're
     572     7366121 :     // not inserting at the end.
     573    27384128 : 
     574    20971470 :     // Move over the elements that we're about to overwrite.
     575     5102860 :     T *OldEnd = this->end();
     576    49809935 :     this->set_size(this->size() + NumToInsert);
     577    55950688 :     size_t NumOverwritten = OldEnd-I;
     578    29267983 :     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
     579    89082867 : 
     580   112430776 :     // Replace the overwritten part.
     581    66327796 :     std::fill_n(I, NumOverwritten, Elt);
     582    37877515 : 
     583    68532945 :     // Insert the non-overwritten middle part.
     584    92470481 :     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
     585   148079056 :     return I;
     586    91368936 :   }
     587    82487830 : 
     588   136954408 :   template <typename ItTy,
     589  1108666655 :             typename = typename std::enable_if<std::is_convertible<
     590   149888926 :                 typename std::iterator_traits<ItTy>::iterator_category,
     591    65153188 :                 std::input_iterator_tag>::value>::type>
     592    59423120 :   iterator insert(iterator I, ItTy From, ItTy To) {
     593     7578922 :     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
     594   117642486 :     size_t InsertElt = I - this->begin();
     595    85631983 : 
     596    95354915 :     if (I == this->end()) {  // Important special case for empty vector.
     597    66720340 :       append(From, To);
     598    63336849 :       return this->begin()+InsertElt;
     599    83381039 :     }
     600    32676245 : 
     601    45928347 :     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
     602   101522802 :     assert(I <= this->end() && "Inserting past the end of the vector.");
     603   114403677 : 
     604    56589009 :     size_t NumToInsert = std::distance(From, To);
     605    52857657 : 
     606    85114214 :     // Ensure there is enough space.
     607    29002438 :     reserve(this->size() + NumToInsert);
     608    11597660 : 
     609     4458686 :     // Uninvalidate the iterator.
     610    50621114 :     I = this->begin()+InsertElt;
     611     4081790 : 
     612     5591097 :     // If there are more elements between the insertion point and the end of the
     613     7346884 :     // range than there are being inserted, we can use a simple approach to
     614     3035326 :     // insertion.  Since we already reserved space, we know that this won't
     615    17552343 :     // reallocate the vector.
     616     4945610 :     if (size_t(this->end()-I) >= NumToInsert) {
     617     3854584 :       T *OldEnd = this->end();
     618    10478211 :       append(std::move_iterator<iterator>(this->end() - NumToInsert),
     619     4695154 :              std::move_iterator<iterator>(this->end()));
     620    46008665 : 
     621    53100312 :       // Copy the existing elements that get replaced.
     622   128583355 :       std::move_backward(I, OldEnd-NumToInsert, OldEnd);
     623   156365354 : 
     624   148636957 :       std::copy(From, To, I);
     625   178783094 :       return I;
     626   158936547 :     }
     627   173981528 : 
     628    26623330 :     // Otherwise, we're inserting more elements than exist already, and we're
     629   196179401 :     // not inserting at the end.
     630   413617124 : 
     631   264743512 :     // Move over the elements that we're about to overwrite.
     632   175292463 :     T *OldEnd = this->end();
     633   139020152 :     this->set_size(this->size() + NumToInsert);
     634    25604105 :     size_t NumOverwritten = OldEnd-I;
     635   107977715 :     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
     636    31840704 : 
     637     9315495 :     // Replace the overwritten part.
     638     6371747 :     for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
     639    11124294 :       *J = *From;
     640   206063199 :       ++J; ++From;
     641   106231506 :     }
     642     3896281 : 
     643     5681474 :     // Insert the non-overwritten middle part.
     644    16520402 :     this->uninitialized_copy(From, To, OldEnd);
     645    16513978 :     return I;
     646     2331220 :   }
     647     1608168 : 
     648      971234 :   void insert(iterator I, std::initializer_list<T> IL) {
     649      712592 :     insert(I, IL.begin(), IL.end());
     650     1616622 :   }
     651     1498408 : 
     652     3453105 :   template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
     653    25483817 :     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
     654    46084730 :       this->grow();
     655    39847602 :     ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
     656    11415662 :     this->set_size(this->size() + 1);
     657    72541730 :   }
     658    63784600 : 
     659     1276680 :   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
     660     2967484 : 
     661    27700136 :   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
     662    94756260 : 
     663    39038011 :   bool operator==(const SmallVectorImpl &RHS) const {
     664    90667431 :     if (this->size() != RHS.size()) return false;
     665    42918661 :     return std::equal(this->begin(), this->end(), RHS.begin());
     666     6864680 :   }
     667     7915399 :   bool operator!=(const SmallVectorImpl &RHS) const {
     668    29370499 :     return !(*this == RHS);
     669    11540096 :   }
     670     3679081 : 
     671     7797334 :   bool operator<(const SmallVectorImpl &RHS) const {
     672     4646187 :     return std::lexicographical_compare(this->begin(), this->end(),
     673    31553318 :                                         RHS.begin(), RHS.end());
     674    32856346 :   }
     675    12746502 : };
     676    36437150 : 
     677     2579184 : template <typename T>
     678     5418054 : void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
     679     4352891 :   if (this == &RHS) return;
     680     4126042 : 
     681    98156022 :   // We can only avoid copying elements if neither vector is small.
     682    77532657 :   if (!this->isSmall() && !RHS.isSmall()) {
     683     2564173 :     std::swap(this->BeginX, RHS.BeginX);
     684     3126588 :     std::swap(this->Size, RHS.Size);
     685    25873511 :     std::swap(this->Capacity, RHS.Capacity);
     686    28744291 :     return;
     687     2925711 :   }
     688    61412934 :   if (RHS.size() > this->capacity())
     689    41501354 :     this->grow(RHS.size());
     690     1154417 :   if (this->size() > RHS.capacity())
     691      368844 :     RHS.grow(this->size());
     692    25381425 : 
     693     1209037 :   // Swap the shared elements.
     694     4622844 :   size_t NumShared = this->size();
     695   127858391 :   if (NumShared > RHS.size()) NumShared = RHS.size();
     696     2918417 :   for (size_type i = 0; i != NumShared; ++i)
     697     2511336 :     std::swap((*this)[i], RHS[i]);
     698     2135212 : 
     699     1550321 :   // Copy over the extra elts.
     700     4176333 :   if (this->size() > RHS.size()) {
     701     3579180 :     size_t EltDiff = this->size() - RHS.size();
     702     1233643 :     this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
     703     1535318 :     RHS.set_size(RHS.size() + EltDiff);
     704     1988795 :     this->destroy_range(this->begin()+NumShared, this->end());
     705     1703901 :     this->set_size(NumShared);
     706     3050467 :   } else if (RHS.size() > this->size()) {
     707     2809152 :     size_t EltDiff = RHS.size() - this->size();
     708    15656327 :     this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
     709    10495730 :     this->set_size(this->size() + EltDiff);
     710    11639509 :     this->destroy_range(RHS.begin()+NumShared, RHS.end());
     711    11330360 :     RHS.set_size(NumShared);
     712     1246903 :   }
     713   153710278 : }
     714     4082323 : 
     715   114280824 : template <typename T>
     716     4896654 : SmallVectorImpl<T> &SmallVectorImpl<T>::
     717     2499709 :   operator=(const SmallVectorImpl<T> &RHS) {
     718    24342018 :   // Avoid self-assignment.
     719     8342425 :   if (this == &RHS) return *this;
     720       95380 : 
     721     3068678 :   // If we already have sufficient space, assign the common elements, then
     722    14931304 :   // destroy any excess.
     723     9385656 :   size_t RHSSize = RHS.size();
     724    35979774 :   size_t CurSize = this->size();
     725    35360135 :   if (CurSize >= RHSSize) {
     726     1148873 :     // Assign common elements.
     727    36817632 :     iterator NewEnd;
     728     2825899 :     if (RHSSize)
     729      177055 :       NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
     730      203193 :     else
     731     5259597 :       NewEnd = this->begin();
     732    69214251 : 
     733    34273618 :     // Destroy excess elements.
     734      280375 :     this->destroy_range(NewEnd, this->end());
     735      402036 : 
     736     5399738 :     // Trim.
     737      485470 :     this->set_size(RHSSize);
     738     1126925 :     return *this;
     739      488556 :   }
     740     3705490 : 
     741     4300009 :   // If we have to grow to have enough elements, destroy the current elements.
     742      248047 :   // This allows us to avoid copying them during the grow.
     743      892745 :   // FIXME: don't do this if they're efficiently moveable.
     744     3718446 :   if (this->capacity() < RHSSize) {
     745     6122302 :     // Destroy current elements.
     746     1185396 :     this->destroy_range(this->begin(), this->end());
     747    52918646 :     this->set_size(0);
     748    28688233 :     CurSize = 0;
     749    14110731 :     this->grow(RHSSize);
     750     1029871 :   } else if (CurSize) {
     751    17546099 :     // Otherwise, use assignment for the already-constructed elements.
     752     4030044 :     std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
     753    26321718 :   }
     754   399735510 : 
     755    33919222 :   // Copy construct the new elements in place.
     756    52188438 :   this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
     757    50516065 :                            this->begin()+CurSize);
     758   116158728 : 
     759   135665131 :   // Set end.
     760    53107026 :   this->set_size(RHSSize);
     761    75309831 :   return *this;
     762    22954428 : }
     763    30124305 : 
     764    33947358 : template <typename T>
     765    29028222 : SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
     766    11704416 :   // Avoid self-assignment.
     767     6365752 :   if (this == &RHS) return *this;
     768     7799923 : 
     769    10521497 :   // If the RHS isn't small, clear this vector and then steal its buffer.
     770    18869408 :   if (!RHS.isSmall()) {
     771    18923586 :     this->destroy_range(this->begin(), this->end());
     772     4923877 :     if (!this->isSmall()) free(this->begin());
     773     3257939 :     this->BeginX = RHS.BeginX;
     774     1397274 :     this->Size = RHS.Size;
     775     1289494 :     this->Capacity = RHS.Capacity;
     776     2168237 :     RHS.resetToSmall();
     777    12192361 :     return *this;
     778    14847199 :   }
     779    22053277 : 
     780     1091314 :   // If we already have sufficient space, assign the common elements, then
     781    10489095 :   // destroy any excess.
     782     9916255 :   size_t RHSSize = RHS.size();
     783     1126118 :   size_t CurSize = this->size();
     784     7129949 :   if (CurSize >= RHSSize) {
     785     7236500 :     // Assign common elements.
     786    22271541 :     iterator NewEnd = this->begin();
     787    15113951 :     if (RHSSize)
     788     8299488 :       NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
     789    12643039 : 
     790     5586901 :     // Destroy excess elements and trim the bounds.
     791    12279653 :     this->destroy_range(NewEnd, this->end());
     792     8479038 :     this->set_size(RHSSize);
     793     3910891 : 
     794    19932649 :     // Clear the RHS.
     795    24641102 :     RHS.clear();
     796    16571131 : 
     797    32666055 :     return *this;
     798    12473731 :   }
     799    21195930 : 
     800     9132392 :   // If we have to grow to have enough elements, destroy the current elements.
     801     9044408 :   // This allows us to avoid copying them during the grow.
     802     5546111 :   // FIXME: this may not actually make any sense if we can efficiently move
     803    10092675 :   // elements.
     804    12364967 :   if (this->capacity() < RHSSize) {
     805     9620791 :     // Destroy current elements.
     806    17718225 :     this->destroy_range(this->begin(), this->end());
     807    34043560 :     this->set_size(0);
     808     7847206 :     CurSize = 0;
     809    12006446 :     this->grow(RHSSize);
     810    40028717 :   } else if (CurSize) {
     811    38223228 :     // Otherwise, use assignment for the already-constructed elements.
     812    13174131 :     std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
     813     4375207 :   }
     814    48520380 : 
     815    33710870 :   // Move-construct the new elements in place.
     816    27277330 :   this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
     817     4997346 :                            this->begin()+CurSize);
     818    53796023 : 
     819    29782872 :   // Set end.
     820    29914931 :   this->set_size(RHSSize);
     821    31072826 : 
     822      989825 :   RHS.clear();
     823    28773977 :   return *this;
     824     9754192 : }
     825    39904597 : 
     826    36408179 : /// Storage for the SmallVector elements.  This is specialized for the N=0 case
     827    38236689 : /// to avoid allocating unnecessary storage.
     828     5138076 : template <typename T, unsigned N>
     829     1055792 : struct SmallVectorStorage {
     830     7571005 :   AlignedCharArrayUnion<T> InlineElts[N];
     831    20344641 : };
     832    20107658 : 
     833    29170880 : /// We need the storage to be properly aligned even for small-size of 0 so that
     834     3925379 : /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
     835    28444758 : /// well-defined.
     836    10204513 : template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
     837    11685474 : 
     838     9317682 : /// This is a 'vector' (really, a variable-sized array), optimized
     839     5138778 : /// for the case when the array is small.  It contains some number of elements
     840     4169689 : /// in-place, which allows it to avoid heap allocation when the actual number of
     841    27479280 : /// elements is below that threshold.  This allows normal "small" cases to be
     842     9755786 : /// fast without losing generality for large inputs.
     843    19845707 : ///
     844    13722859 : /// Note that this does not attempt to be exception safe.
     845     6002279 : ///
     846    48989755 : template <typename T, unsigned N>
     847    51739550 : class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
     848    39053715 : public:
     849   262704709 :   SmallVector() : SmallVectorImpl<T>(N) {}
     850     1061120 : 
     851    37874582 :   ~SmallVector() {
     852    52612789 :     // Destroy the constructed elements in the vector.
     853     6864093 :     this->destroy_range(this->begin(), this->end());
     854   104801380 :   }
     855     5055350 : 
     856     1060529 :   explicit SmallVector(size_t Size, const T &Value = T())
     857    50850976 :     : SmallVectorImpl<T>(N) {
     858    78447156 :     this->assign(Size, Value);
     859    49707996 :   }
     860    21483677 : 
     861   164259770 :   template <typename ItTy,
     862    33990392 :             typename = typename std::enable_if<std::is_convertible<
     863    55993329 :                 typename std::iterator_traits<ItTy>::iterator_category,
     864    10460689 :                 std::input_iterator_tag>::value>::type>
     865    11512292 :   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
     866    24179528 :     this->append(S, E);
     867  1218029811 :   }
     868    13113551 : 
     869    13919389 :   template <typename RangeTy>
     870     7156182 :   explicit SmallVector(const iterator_range<RangeTy> &R)
     871     1423895 :       : SmallVectorImpl<T>(N) {
     872    12158997 :     this->append(R.begin(), R.end());
     873    46987889 :   }
     874    10939204 : 
     875    18050207 :   SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
     876    10909834 :     this->assign(IL);
     877    15165879 :   }
     878     8931518 : 
     879    30141156 :   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
     880     6308952 :     if (!RHS.empty())
     881    44497476 :       SmallVectorImpl<T>::operator=(RHS);
     882    29527469 :   }
     883     9435608 : 
     884    12480539 :   const SmallVector &operator=(const SmallVector &RHS) {
     885   137583096 :     SmallVectorImpl<T>::operator=(RHS);
     886     5481294 :     return *this;
     887    18991947 :   }
     888    34104259 : 
     889      886926 :   SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
     890    14170488 :     if (!RHS.empty())
     891    67505469 :       SmallVectorImpl<T>::operator=(::std::move(RHS));
     892    18380859 :   }
     893   366884635 : 
     894    58285471 :   SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
     895    77007419 :     if (!RHS.empty())
     896    20893709 :       SmallVectorImpl<T>::operator=(::std::move(RHS));
     897   139961560 :   }
     898    33840823 : 
     899    34596058 :   const SmallVector &operator=(SmallVector &&RHS) {
     900   185030359 :     SmallVectorImpl<T>::operator=(::std::move(RHS));
     901    20438633 :     return *this;
     902    53750918 :   }
     903    16116750 : 
     904    12808396 :   const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
     905    68765755 :     SmallVectorImpl<T>::operator=(::std::move(RHS));
     906    20204770 :     return *this;
     907   314571070 :   }
     908   344998780 : 
     909    56239029 :   const SmallVector &operator=(std::initializer_list<T> IL) {
     910     5295464 :     this->assign(IL);
     911    15845230 :     return *this;
     912    46337326 :   }
     913    95591469 : };
     914     5927387 : 
     915    47691911 : template <typename T, unsigned N>
     916    47718967 : inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
     917    75904602 :   return X.capacity_in_bytes();
     918    63354112 : }
     919    50301589 : 
     920    53857646 : } // end namespace llvm
     921   455723024 : 
     922    65971922 : namespace std {
     923   132071747 : 
     924     7068665 :   /// Implement std::swap in terms of SmallVector swap.
     925    81616999 :   template<typename T>
     926    20872157 :   inline void
     927     6527951 :   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
     928     3993324 :     LHS.swap(RHS);
     929    32533531 :   }
     930    27441362 : 
     931    20823062 :   /// Implement std::swap in terms of SmallVector swap.
     932     3903676 :   template<typename T, unsigned N>
     933     2613256 :   inline void
     934    16969080 :   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
     935    20848342 :     LHS.swap(RHS);
     936     7704543 :   }
     937    62152394 : 
     938    20857065 : } // end namespace std
     939    69705998 : 
     940     6095681 : #endif // LLVM_ADT_SMALLVECTOR_H

Generated by: LCOV version 1.13