contrib/llvm/include/llvm/ADT/SmallVector.h

   1 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the SmallVector class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_SMALLVECTOR_H
  15 #define LLVM_ADT_SMALLVECTOR_H
  16
  17 #include "llvm/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       : 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   size_t size() const { return Size; }
  54   size_t capacity() const { return Capacity; }
  55
  56   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   void set_size(size_t Size) {
  68     assert(Size <= capacity());
  69     this->Size = Size;
  70   }
  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         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     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   bool isSmall() const { return BeginX == getFirstEl(); }
 105
 106   /// Put this vector in a state of being small.
 107   void resetToSmall() {
 108     BeginX = getFirstEl();
 109     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   iterator begin() { return (iterator)this->BeginX; }
 130   LLVM_ATTRIBUTE_ALWAYS_INLINE
 131   const_iterator begin() const { return (const_iterator)this->BeginX; }
 132   LLVM_ATTRIBUTE_ALWAYS_INLINE
 133   iterator end() { return begin() + size(); }
 134   LLVM_ATTRIBUTE_ALWAYS_INLINE
 135   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   reverse_iterator rend()              { return reverse_iterator(begin()); }
 141   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   size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
 147
 148   /// Return a pointer to the vector's buffer, even if empty().
 149   pointer data() { return pointer(begin()); }
 150   /// Return a pointer to the vector's buffer, even if empty().
 151   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     return begin()[idx];
 157   }
 158   LLVM_ATTRIBUTE_ALWAYS_INLINE
 159   const_reference operator[](size_type idx) const {
 160     assert(idx < size());
 161     return begin()[idx];
 162   }
 163
 164   reference front() {
 165     assert(!empty());
 166     return begin()[0];
 167   }
 168   const_reference front() const {
 169     assert(!empty());
 170     return begin()[0];
 171   }
 172
 173   reference back() {
 174     assert(!empty());
 175     return end()[-1];
 176   }
 177   const_reference back() const {
 178     assert(!empty());
 179     return end()[-1];
 180   }
 181 };
 182
 183 /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method
 184 /// implementations that are designed to work with non-POD-like T's.
 185 template <typename T, bool = isPodLike<T>::value>
 186 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
 187 protected:
 188   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
 189
 190   static void destroy_range(T *S, T *E) {
 191     while (S != E) {
 192       --E;
 193       E->~T();
 194     }
 195   }
 196
 197   /// Move the range [I, E) into the uninitialized memory starting with "Dest",
 198   /// constructing elements as needed.
 199   template<typename It1, typename It2>
 200   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
 201     std::uninitialized_copy(std::make_move_iterator(I),
 202                             std::make_move_iterator(E), Dest);
 203   }
 204
 205   /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
 206   /// constructing elements as needed.
 207   template<typename It1, typename It2>
 208   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
 209     std::uninitialized_copy(I, E, Dest);
 210   }
 211
 212   /// Grow the allocated memory (without initializing new elements), doubling
 213   /// the size of the allocated memory. Guarantees space for at least one more
 214   /// element, or MinSize more elements if specified.
 215   void grow(size_t MinSize = 0);
 216
 217 public:
 218   void push_back(const T &Elt) {
 219     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
 220       this->grow();
 221     ::new ((void*) this->end()) T(Elt);
 222     this->set_size(this->size() + 1);
 223   }
 224
 225   void push_back(T &&Elt) {
 226     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
 227       this->grow();
 228     ::new ((void*) this->end()) T(::std::move(Elt));
 229     this->set_size(this->size() + 1);
 230   }
 231
 232   void pop_back() {
 233     this->set_size(this->size() - 1);
 234     this->end()->~T();
 235   }
 236 };
 237
 238 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 239 template <typename T, bool isPodLike>
 240 void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
 241   if (MinSize > UINT32_MAX)
 242     report_bad_alloc_error("SmallVector capacity overflow during allocation");
 243
 244   // Always grow, even from zero.
 245   size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
 246   NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX));
 247   T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
 248
 249   // Move the elements over.
 250   this->uninitialized_move(this->begin(), this->end(), NewElts);
 251
 252   // Destroy the original elements.
 253   destroy_range(this->begin(), this->end());
 254
 255   // If this wasn't grown from the inline copy, deallocate the old space.
 256   if (!this->isSmall())
 257     free(this->begin());
 258
 259   this->BeginX = NewElts;
 260   this->Capacity = NewCapacity;
 261 }
 262
 263
 264 /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
 265 /// implementations that are designed to work with POD-like T's.
 266 template <typename T>
 267 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
 268 protected:
 269   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
 270
 271   // No need to do a destroy loop for POD's.
 272   static void destroy_range(T *, T *) {}
 273
 274   /// Move the range [I, E) onto the uninitialized memory
 275   /// starting with "Dest", constructing elements into it as needed.
 276   template<typename It1, typename It2>
 277   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
 278     // Just do a copy.
 279     uninitialized_copy(I, E, Dest);
 280   }
 281
 282   /// Copy the range [I, E) onto the uninitialized memory
 283   /// starting with "Dest", constructing elements into it as needed.
 284   template<typename It1, typename It2>
 285   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
 286     // Arbitrary iterator types; just use the basic implementation.
 287     std::uninitialized_copy(I, E, Dest);
 288   }
 289
 290   /// Copy the range [I, E) onto the uninitialized memory
 291   /// starting with "Dest", constructing elements into it as needed.
 292   template <typename T1, typename T2>
 293   static void uninitialized_copy(
 294       T1 *I, T1 *E, T2 *Dest,
 295       typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
 296                                            T2>::value>::type * = nullptr) {
 297     // Use memcpy for PODs iterated by pointers (which includes SmallVector
 298     // iterators): std::uninitialized_copy optimizes to memmove, but we can
 299     // use memcpy here. Note that I and E are iterators and thus might be
 300     // invalid for memcpy if they are equal.
 301     if (I != E)
 302       memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
 303   }
 304
 305   /// Double the size of the allocated memory, guaranteeing space for at
 306   /// least one more element or MinSize if specified.
 307   void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
 308
 309 public:
 310   void push_back(const T &Elt) {
 311     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
 312       this->grow();
 313     memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
 314     this->set_size(this->size() + 1);
 315   }
 316
 317   void pop_back() { this->set_size(this->size() - 1); }
 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> {
 324   using SuperClass = SmallVectorTemplateBase<T>;
 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) {}
 335
 336 public:
 337   SmallVectorImpl(const SmallVectorImpl &) = delete;
 338
 339   ~SmallVectorImpl() {
 340     // Subclass has already destructed this vector's elements.
 341     // If this wasn't grown from the inline copy, deallocate the old space.
 342     if (!this->isSmall())
 343       free(this->begin());
 344   }
 345
 346   void clear() {
 347     this->destroy_range(this->begin(), this->end());
 348     this->Size = 0;
 349   }
 350
 351   void resize(size_type N) {
 352     if (N < this->size()) {
 353       this->destroy_range(this->begin()+N, this->end());
 354       this->set_size(N);
 355     } else if (N > this->size()) {
 356       if (this->capacity() < N)
 357         this->grow(N);
 358       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
 359         new (&*I) T();
 360       this->set_size(N);
 361     }
 362   }
 363
 364   void resize(size_type N, const T &NV) {
 365     if (N < this->size()) {
 366       this->destroy_range(this->begin()+N, this->end());
 367       this->set_size(N);
 368     } else if (N > this->size()) {
 369       if (this->capacity() < N)
 370         this->grow(N);
 371       std::uninitialized_fill(this->end(), this->begin()+N, NV);
 372       this->set_size(N);
 373     }
 374   }
 375
 376   void reserve(size_type N) {
 377     if (this->capacity() < N)
 378       this->grow(N);
 379   }
 380
 381   LLVM_NODISCARD T pop_back_val() {
 382     T Result = ::std::move(this->back());
 383     this->pop_back();
 384     return Result;
 385   }
 386
 387   void swap(SmallVectorImpl &RHS);
 388
 389   /// Add the specified range to the end of the SmallVector.
 390   template <typename in_iter,
 391             typename = typename std::enable_if<std::is_convertible<
 392                 typename std::iterator_traits<in_iter>::iterator_category,
 393                 std::input_iterator_tag>::value>::type>
 394   void append(in_iter in_start, in_iter in_end) {
 395     size_type NumInputs = std::distance(in_start, in_end);
 396     // Grow allocated space if needed.
 397     if (NumInputs > this->capacity() - this->size())
 398       this->grow(this->size()+NumInputs);
 399
 400     // Copy the new elements over.
 401     this->uninitialized_copy(in_start, in_end, this->end());
 402     this->set_size(this->size() + NumInputs);
 403   }
 404
 405   /// Add the specified range to the end of the SmallVector.
 406   void append(size_type NumInputs, const T &Elt) {
 407     // Grow allocated space if needed.
 408     if (NumInputs > this->capacity() - this->size())
 409       this->grow(this->size()+NumInputs);
 410
 411     // Copy the new elements over.
 412     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
 413     this->set_size(this->size() + NumInputs);
 414   }
 415
 416   void append(std::initializer_list<T> IL) {
 417     append(IL.begin(), IL.end());
 418   }
 419
 420   // FIXME: Consider assigning over existing elements, rather than clearing &
 421   // re-initializing them - for all assign(...) variants.
 422
 423   void assign(size_type NumElts, const T &Elt) {
 424     clear();
 425     if (this->capacity() < NumElts)
 426       this->grow(NumElts);
 427     this->set_size(NumElts);
 428     std::uninitialized_fill(this->begin(), this->end(), Elt);
 429   }
 430
 431   template <typename in_iter,
 432             typename = typename std::enable_if<std::is_convertible<
 433                 typename std::iterator_traits<in_iter>::iterator_category,
 434                 std::input_iterator_tag>::value>::type>
 435   void assign(in_iter in_start, in_iter in_end) {
 436     clear();
 437     append(in_start, in_end);
 438   }
 439
 440   void assign(std::initializer_list<T> IL) {
 441     clear();
 442     append(IL);
 443   }
 444
 445   iterator erase(const_iterator CI) {
 446     // Just cast away constness because this is a non-const member function.
 447     iterator I = const_cast<iterator>(CI);
 448
 449     assert(I >= this->begin() && "Iterator to erase is out of bounds.");
 450     assert(I < this->end() && "Erasing at past-the-end iterator.");
 451
 452     iterator N = I;
 453     // Shift all elts down one.
 454     std::move(I+1, this->end(), I);
 455     // Drop the last elt.
 456     this->pop_back();
 457     return(N);
 458   }
 459
 460   iterator erase(const_iterator CS, const_iterator CE) {
 461     // Just cast away constness because this is a non-const member function.
 462     iterator S = const_cast<iterator>(CS);
 463     iterator E = const_cast<iterator>(CE);
 464
 465     assert(S >= this->begin() && "Range to erase is out of bounds.");
 466     assert(S <= E && "Trying to erase invalid range.");
 467     assert(E <= this->end() && "Trying to erase past the end.");
 468
 469     iterator N = S;
 470     // Shift all elts down.
 471     iterator I = std::move(E, this->end(), S);
 472     // Drop the last elts.
 473     this->destroy_range(I, this->end());
 474     this->set_size(I - this->begin());
 475     return(N);
 476   }
 477
 478   iterator insert(iterator I, T &&Elt) {
 479     if (I == this->end()) {  // Important special case for empty vector.
 480       this->push_back(::std::move(Elt));
 481       return this->end()-1;
 482     }
 483
 484     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
 485     assert(I <= this->end() && "Inserting past the end of the vector.");
 486
 487     if (this->size() >= this->capacity()) {
 488       size_t EltNo = I-this->begin();
 489       this->grow();
 490       I = this->begin()+EltNo;
 491     }
 492
 493     ::new ((void*) this->end()) T(::std::move(this->back()));
 494     // Push everything else over.
 495     std::move_backward(I, this->end()-1, this->end());
 496     this->set_size(this->size() + 1);
 497
 498     // If we just moved the element we're inserting, be sure to update
 499     // the reference.
 500     T *EltPtr = &Elt;
 501     if (I <= EltPtr && EltPtr < this->end())
 502       ++EltPtr;
 503
 504     *I = ::std::move(*EltPtr);
 505     return I;
 506   }
 507
 508   iterator insert(iterator I, const T &Elt) {
 509     if (I == this->end()) {  // Important special case for empty vector.
 510       this->push_back(Elt);
 511       return this->end()-1;
 512     }
 513
 514     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
 515     assert(I <= this->end() && "Inserting past the end of the vector.");
 516
 517     if (this->size() >= this->capacity()) {
 518       size_t EltNo = I-this->begin();
 519       this->grow();
 520       I = this->begin()+EltNo;
 521     }
 522     ::new ((void*) this->end()) T(std::move(this->back()));
 523     // Push everything else over.
 524     std::move_backward(I, this->end()-1, this->end());
 525     this->set_size(this->size() + 1);
 526
 527     // If we just moved the element we're inserting, be sure to update
 528     // the reference.
 529     const T *EltPtr = &Elt;
 530     if (I <= EltPtr && EltPtr < this->end())
 531       ++EltPtr;
 532
 533     *I = *EltPtr;
 534     return I;
 535   }
 536
 537   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
 538     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 539     size_t InsertElt = I - this->begin();
 540
 541     if (I == this->end()) {  // Important special case for empty vector.
 542       append(NumToInsert, Elt);
 543       return this->begin()+InsertElt;
 544     }
 545
 546     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
 547     assert(I <= this->end() && "Inserting past the end of the vector.");
 548
 549     // Ensure there is enough space.
 550     reserve(this->size() + NumToInsert);
 551
 552     // Uninvalidate the iterator.
 553     I = this->begin()+InsertElt;
 554
 555     // If there are more elements between the insertion point and the end of the
 556     // range than there are being inserted, we can use a simple approach to
 557     // insertion.  Since we already reserved space, we know that this won't
 558     // reallocate the vector.
 559     if (size_t(this->end()-I) >= NumToInsert) {
 560       T *OldEnd = this->end();
 561       append(std::move_iterator<iterator>(this->end() - NumToInsert),
 562              std::move_iterator<iterator>(this->end()));
 563
 564       // Copy the existing elements that get replaced.
 565       std::move_backward(I, OldEnd-NumToInsert, OldEnd);
 566
 567       std::fill_n(I, NumToInsert, Elt);
 568       return I;
 569     }
 570
 571     // Otherwise, we're inserting more elements than exist already, and we're
 572     // not inserting at the end.
 573
 574     // Move over the elements that we're about to overwrite.
 575     T *OldEnd = this->end();
 576     this->set_size(this->size() + NumToInsert);
 577     size_t NumOverwritten = OldEnd-I;
 578     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
 579
 580     // Replace the overwritten part.
 581     std::fill_n(I, NumOverwritten, Elt);
 582
 583     // Insert the non-overwritten middle part.
 584     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
 585     return I;
 586   }
 587
 588   template <typename ItTy,
 589             typename = typename std::enable_if<std::is_convertible<
 590                 typename std::iterator_traits<ItTy>::iterator_category,
 591                 std::input_iterator_tag>::value>::type>
 592   iterator insert(iterator I, ItTy From, ItTy To) {
 593     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
 594     size_t InsertElt = I - this->begin();
 595
 596     if (I == this->end()) {  // Important special case for empty vector.
 597       append(From, To);
 598       return this->begin()+InsertElt;
 599     }
 600
 601     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
 602     assert(I <= this->end() && "Inserting past the end of the vector.");
 603
 604     size_t NumToInsert = std::distance(From, To);
 605
 606     // Ensure there is enough space.
 607     reserve(this->size() + NumToInsert);
 608
 609     // Uninvalidate the iterator.
 610     I = this->begin()+InsertElt;
 611
 612     // If there are more elements between the insertion point and the end of the
 613     // range than there are being inserted, we can use a simple approach to
 614     // insertion.  Since we already reserved space, we know that this won't
 615     // reallocate the vector.
 616     if (size_t(this->end()-I) >= NumToInsert) {
 617       T *OldEnd = this->end();
 618       append(std::move_iterator<iterator>(this->end() - NumToInsert),
 619              std::move_iterator<iterator>(this->end()));
 620
 621       // Copy the existing elements that get replaced.
 622       std::move_backward(I, OldEnd-NumToInsert, OldEnd);
 623
 624       std::copy(From, To, I);
 625       return I;
 626     }
 627
 628     // Otherwise, we're inserting more elements than exist already, and we're
 629     // not inserting at the end.
 630
 631     // Move over the elements that we're about to overwrite.
 632     T *OldEnd = this->end();
 633     this->set_size(this->size() + NumToInsert);
 634     size_t NumOverwritten = OldEnd-I;
 635     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
 636
 637     // Replace the overwritten part.
 638     for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
 639       *J = *From;
 640       ++J; ++From;
 641     }
 642
 643     // Insert the non-overwritten middle part.
 644     this->uninitialized_copy(From, To, OldEnd);
 645     return I;
 646   }
 647
 648   void insert(iterator I, std::initializer_list<T> IL) {
 649     insert(I, IL.begin(), IL.end());
 650   }
 651
 652   template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
 653     if (LLVM_UNLIKELY(this->size() >= this->capacity()))
 654       this->grow();
 655     ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
 656     this->set_size(this->size() + 1);
 657   }
 658
 659   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
 660
 661   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
 662
 663   bool operator==(const SmallVectorImpl &RHS) const {
 664     if (this->size() != RHS.size()) return false;
 665     return std::equal(this->begin(), this->end(), RHS.begin());
 666   }
 667   bool operator!=(const SmallVectorImpl &RHS) const {
 668     return !(*this == RHS);
 669   }
 670
 671   bool operator<(const SmallVectorImpl &RHS) const {
 672     return std::lexicographical_compare(this->begin(), this->end(),
 673                                         RHS.begin(), RHS.end());
 674   }
 675 };
 676
 677 template <typename T>
 678 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
 679   if (this == &RHS) return;
 680
 681   // We can only avoid copying elements if neither vector is small.
 682   if (!this->isSmall() && !RHS.isSmall()) {
 683     std::swap(this->BeginX, RHS.BeginX);
 684     std::swap(this->Size, RHS.Size);
 685     std::swap(this->Capacity, RHS.Capacity);
 686     return;
 687   }
 688   if (RHS.size() > this->capacity())
 689     this->grow(RHS.size());
 690   if (this->size() > RHS.capacity())
 691     RHS.grow(this->size());
 692
 693   // Swap the shared elements.
 694   size_t NumShared = this->size();
 695   if (NumShared > RHS.size()) NumShared = RHS.size();
 696   for (size_type i = 0; i != NumShared; ++i)
 697     std::swap((*this)[i], RHS[i]);
 698
 699   // Copy over the extra elts.
 700   if (this->size() > RHS.size()) {
 701     size_t EltDiff = this->size() - RHS.size();
 702     this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
 703     RHS.set_size(RHS.size() + EltDiff);
 704     this->destroy_range(this->begin()+NumShared, this->end());
 705     this->set_size(NumShared);
 706   } else if (RHS.size() > this->size()) {
 707     size_t EltDiff = RHS.size() - this->size();
 708     this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
 709     this->set_size(this->size() + EltDiff);
 710     this->destroy_range(RHS.begin()+NumShared, RHS.end());
 711     RHS.set_size(NumShared);
 712   }
 713 }
 714
 715 template <typename T>
 716 SmallVectorImpl<T> &SmallVectorImpl<T>::
 717   operator=(const SmallVectorImpl<T> &RHS) {
 718   // Avoid self-assignment.
 719   if (this == &RHS) return *this;
 720
 721   // If we already have sufficient space, assign the common elements, then
 722   // destroy any excess.
 723   size_t RHSSize = RHS.size();
 724   size_t CurSize = this->size();
 725   if (CurSize >= RHSSize) {
 726     // Assign common elements.
 727     iterator NewEnd;
 728     if (RHSSize)
 729       NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
 730     else
 731       NewEnd = this->begin();
 732
 733     // Destroy excess elements.
 734     this->destroy_range(NewEnd, this->end());
 735
 736     // Trim.
 737     this->set_size(RHSSize);
 738     return *this;
 739   }
 740
 741   // If we have to grow to have enough elements, destroy the current elements.
 742   // This allows us to avoid copying them during the grow.
 743   // FIXME: don't do this if they're efficiently moveable.
 744   if (this->capacity() < RHSSize) {
 745     // Destroy current elements.
 746     this->destroy_range(this->begin(), this->end());
 747     this->set_size(0);
 748     CurSize = 0;
 749     this->grow(RHSSize);
 750   } else if (CurSize) {
 751     // Otherwise, use assignment for the already-constructed elements.
 752     std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
 753   }
 754
 755   // Copy construct the new elements in place.
 756   this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
 757                            this->begin()+CurSize);
 758
 759   // Set end.
 760   this->set_size(RHSSize);
 761   return *this;
 762 }
 763
 764 template <typename T>
 765 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
 766   // Avoid self-assignment.
 767   if (this == &RHS) return *this;
 768
 769   // If the RHS isn't small, clear this vector and then steal its buffer.
 770   if (!RHS.isSmall()) {
 771     this->destroy_range(this->begin(), this->end());
 772     if (!this->isSmall()) free(this->begin());
 773     this->BeginX = RHS.BeginX;
 774     this->Size = RHS.Size;
 775     this->Capacity = RHS.Capacity;
 776     RHS.resetToSmall();
 777     return *this;
 778   }
 779
 780   // If we already have sufficient space, assign the common elements, then
 781   // destroy any excess.
 782   size_t RHSSize = RHS.size();
 783   size_t CurSize = this->size();
 784   if (CurSize >= RHSSize) {
 785     // Assign common elements.
 786     iterator NewEnd = this->begin();
 787     if (RHSSize)
 788       NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
 789
 790     // Destroy excess elements and trim the bounds.
 791     this->destroy_range(NewEnd, this->end());
 792     this->set_size(RHSSize);
 793
 794     // Clear the RHS.
 795     RHS.clear();
 796
 797     return *this;
 798   }
 799
 800   // If we have to grow to have enough elements, destroy the current elements.
 801   // This allows us to avoid copying them during the grow.
 802   // FIXME: this may not actually make any sense if we can efficiently move
 803   // elements.
 804   if (this->capacity() < RHSSize) {
 805     // Destroy current elements.
 806     this->destroy_range(this->begin(), this->end());
 807     this->set_size(0);
 808     CurSize = 0;
 809     this->grow(RHSSize);
 810   } else if (CurSize) {
 811     // Otherwise, use assignment for the already-constructed elements.
 812     std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
 813   }
 814
 815   // Move-construct the new elements in place.
 816   this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
 817                            this->begin()+CurSize);
 818
 819   // Set end.
 820   this->set_size(RHSSize);
 821
 822   RHS.clear();
 823   return *this;
 824 }
 825
 826 /// Storage for the SmallVector elements.  This is specialized for the N=0 case
 827 /// to avoid allocating unnecessary storage.
 828 template <typename T, unsigned N>
 829 struct SmallVectorStorage {
 830   AlignedCharArrayUnion<T> InlineElts[N];
 831 };
 832
 833 /// We need the storage to be properly aligned even for small-size of 0 so that
 834 /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
 835 /// well-defined.
 836 template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
 837
 838 /// This is a 'vector' (really, a variable-sized array), optimized
 839 /// for the case when the array is small.  It contains some number of elements
 840 /// in-place, which allows it to avoid heap allocation when the actual number of
 841 /// elements is below that threshold.  This allows normal "small" cases to be
 842 /// fast without losing generality for large inputs.
 843 ///
 844 /// Note that this does not attempt to be exception safe.
 845 ///
 846 template <typename T, unsigned N>
 847 class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
 848 public:
 849   SmallVector() : SmallVectorImpl<T>(N) {}
 850
 851   ~SmallVector() {
 852     // Destroy the constructed elements in the vector.
 853     this->destroy_range(this->begin(), this->end());
 854   }
 855
 856   explicit SmallVector(size_t Size, const T &Value = T())
 857     : SmallVectorImpl<T>(N) {
 858     this->assign(Size, Value);
 859   }
 860
 861   template <typename ItTy,
 862             typename = typename std::enable_if<std::is_convertible<
 863                 typename std::iterator_traits<ItTy>::iterator_category,
 864                 std::input_iterator_tag>::value>::type>
 865   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
 866     this->append(S, E);
 867   }
 868
 869   template <typename RangeTy>
 870   explicit SmallVector(const iterator_range<RangeTy> &R)
 871       : SmallVectorImpl<T>(N) {
 872     this->append(R.begin(), R.end());
 873   }
 874
 875   SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
 876     this->assign(IL);
 877   }
 878
 879   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
 880     if (!RHS.empty())
 881       SmallVectorImpl<T>::operator=(RHS);
 882   }
 883
 884   const SmallVector &operator=(const SmallVector &RHS) {
 885     SmallVectorImpl<T>::operator=(RHS);
 886     return *this;
 887   }
 888
 889   SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
 890     if (!RHS.empty())
 891       SmallVectorImpl<T>::operator=(::std::move(RHS));
 892   }
 893
 894   SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
 895     if (!RHS.empty())
 896       SmallVectorImpl<T>::operator=(::std::move(RHS));
 897   }
 898
 899   const SmallVector &operator=(SmallVector &&RHS) {
 900     SmallVectorImpl<T>::operator=(::std::move(RHS));
 901     return *this;
 902   }
 903
 904   const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
 905     SmallVectorImpl<T>::operator=(::std::move(RHS));
 906     return *this;
 907   }
 908
 909   const SmallVector &operator=(std::initializer_list<T> IL) {
 910     this->assign(IL);
 911     return *this;
 912   }
 913 };
 914
 915 template <typename T, unsigned N>
 916 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
 917   return X.capacity_in_bytes();
 918 }
 919
 920 } // end namespace llvm
 921
 922 namespace std {
 923
 924   /// Implement std::swap in terms of SmallVector swap.
 925   template<typename T>
 926   inline void
 927   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
 928     LHS.swap(RHS);
 929   }
 930
 931   /// Implement std::swap in terms of SmallVector swap.
 932   template<typename T, unsigned N>
 933   inline void
 934   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
 935     LHS.swap(RHS);
 936   }
 937
 938 } // end namespace std
 939
 940 #endif // LLVM_ADT_SMALLVECTOR_H