Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

///

/// \file

/// This file defines the SmallVector class.

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_SMALLVECTOR_H

#define LLVM_ADT_SMALLVECTOR_H

#include "llvm/Support/Compiler.h"

#include "llvm/Support/type_traits.h"

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <cstdlib>

#include <cstring>

#include <functional>

#include <initializer_list>

#include <iterator>

#include <limits>

#include <memory>

#include <new>

#include <type_traits>

#include <utility>

namespace llvm {

template <typename T> class ArrayRef;

template <typename IteratorT> class iterator_range;

template <class Iterator>

using EnableIfConvertibleToInputIterator = std::enable_if_t<std::is_convertible<

    typename std::iterator_traits<Iterator>::iterator_category,

    std::input_iterator_tag>::value>;

/// This is all the stuff common to all SmallVectors.

///

/// The template parameter specifies the type which should be used to hold the

/// Size and Capacity of the SmallVector, so it can be adjusted.

/// Using 32 bit size is desirable to shrink the size of the SmallVector.

/// Using 64 bit size is desirable for cases like SmallVector<char>, where a

/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for

/// buffering bitcode output - which can exceed 4GB.

template <class Size_T> class SmallVectorBase {

protected:

  void *BeginX;

  Size_T Size = 0, Capacity;

  /// The maximum value of the Size_T used.

  static constexpr size_t SizeTypeMax() {

    return std::numeric_limits<Size_T>::max();

  }

  SmallVectorBase() = delete;

  SmallVectorBase(void *FirstEl, size_t TotalCapacity)

      : BeginX(FirstEl), Capacity(TotalCapacity) {}

  /// This is a helper for \a grow() that's out of line to reduce code

  /// duplication.  This function will report a fatal error if it can't grow at

  /// least to \p MinSize.

  void *mallocForGrow(void *FirstEl, size_t MinSize, size_t TSize,

                      size_t &NewCapacity);

  /// This is an implementation of the grow() method which only works

  /// on POD-like data types and is out of line to reduce code duplication.

  /// This function will report a fatal error if it cannot increase capacity.

  void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);

  /// If vector was first created with capacity 0, getFirstEl() points to the

  /// memory right after, an area unallocated. If a subsequent allocation,

  /// that grows the vector, happens to return the same pointer as getFirstEl(),

  /// get a new allocation, otherwise isSmall() will falsely return that no

  /// allocation was done (true) and the memory will not be freed in the

  /// destructor. If a VSize is given (vector size), also copy that many

  /// elements to the new allocation - used if realloca fails to increase

  /// space, and happens to allocate precisely at BeginX.

  /// This is unlikely to be called often, but resolves a memory leak when the

  /// situation does occur.

  void *replaceAllocation(void *NewElts, size_t TSize, size_t NewCapacity,

                          size_t VSize = 0);

public:

  size_t size() const { return Size; }

  size_t capacity() const { return Capacity; }

  [[nodiscard]] bool empty() const { return !Size; }

protected:

  /// Set the array size to \p N, which the current array must have enough

  /// capacity for.

  ///

  /// This does not construct or destroy any elements in the vector.

  void set_size(size_t N) {

    assert(N <= capacity());

    Size = N;

  }

};

template <class T>

using SmallVectorSizeType =

    std::conditional_t<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,

                       uint32_t>;

/// Figure out the offset of the first element.

template <class T, typename = void> struct SmallVectorAlignmentAndSize {

  alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(

      SmallVectorBase<SmallVectorSizeType<T>>)];

  alignas(T) char FirstEl[sizeof(T)];

};

/// This is the part of SmallVectorTemplateBase which does not depend on whether

/// the type T is a POD. The extra dummy template argument is used by ArrayRef

/// to avoid unnecessarily requiring T to be complete.

template <typename T, typename = void>

class SmallVectorTemplateCommon

    : public SmallVectorBase<SmallVectorSizeType<T>> {

  using Base = SmallVectorBase<SmallVectorSizeType<T>>;

protected:

  /// Find the address of the first element.  For this pointer math to be valid

  /// with small-size of 0 for T with lots of alignment, it's important that

  /// SmallVectorStorage is properly-aligned even for small-size of 0.

  void *getFirstEl() const {

    return const_cast<void *>(reinterpret_cast<const void *>(

        reinterpret_cast<const char *>(this) +

        offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));

  }

  // Space after 'FirstEl' is clobbered, do not add any instance vars after it.

  SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}

  void grow_pod(size_t MinSize, size_t TSize) {

    Base::grow_pod(getFirstEl(), MinSize, TSize);

  }

  /// Return true if this is a smallvector which has not had dynamic

  /// memory allocated for it.

  bool isSmall() const { return this->BeginX == getFirstEl(); }

  /// Put this vector in a state of being small.

  void resetToSmall() {

    this->BeginX = getFirstEl();

    this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.

  }

  /// Return true if V is an internal reference to the given range.

  bool isReferenceToRange(const void *V, const void *First, const void *Last) const {

    // Use std::less to avoid UB.

    std::less<> LessThan;

    return !LessThan(V, First) && LessThan(V, Last);

  }

  /// Return true if V is an internal reference to this vector.

  bool isReferenceToStorage(const void *V) const {

    return isReferenceToRange(V, this->begin(), this->end());

  }

  /// Return true if First and Last form a valid (possibly empty) range in this

  /// vector's storage.

  bool isRangeInStorage(const void *First, const void *Last) const {

    // Use std::less to avoid UB.

    std::less<> LessThan;

    return !LessThan(First, this->begin()) && !LessThan(Last, First) &&

           !LessThan(this->end(), Last);

  }

  /// Return true unless Elt will be invalidated by resizing the vector to

  /// NewSize.

  bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {

    // Past the end.

    if (LLVM_LIKELY(!isReferenceToStorage(Elt)))

      return true;

    // Return false if Elt will be destroyed by shrinking.

    if (NewSize <= this->size())

      return Elt < this->begin() + NewSize;

    // Return false if we need to grow.

    return NewSize <= this->capacity();

  }

  /// Check whether Elt will be invalidated by resizing the vector to NewSize.

  void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {

    assert(isSafeToReferenceAfterResize(Elt, NewSize) &&

           "Attempting to reference an element of the vector in an operation "

           "that invalidates it");

  }

  /// Check whether Elt will be invalidated by increasing the size of the

  /// vector by N.

  void assertSafeToAdd(const void *Elt, size_t N = 1) {

    this->assertSafeToReferenceAfterResize(Elt, this->size() + N);

  }

  /// Check whether any part of the range will be invalidated by clearing.

  void assertSafeToReferenceAfterClear(const T *From, const T *To) {

    if (From == To)

      return;

    this->assertSafeToReferenceAfterResize(From, 0);

    this->assertSafeToReferenceAfterResize(To - 1, 0);

  }

  template <

      class ItTy,

      std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,

                       bool> = false>

  void assertSafeToReferenceAfterClear(ItTy, ItTy) {}

  /// Check whether any part of the range will be invalidated by growing.

  void assertSafeToAddRange(const T *From, const T *To) {

    if (From == To)

      return;

    this->assertSafeToAdd(From, To - From);

    this->assertSafeToAdd(To - 1, To - From);

  }

  template <

      class ItTy,

      std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,

                       bool> = false>

  void assertSafeToAddRange(ItTy, ItTy) {}

  /// Reserve enough space to add one element, and return the updated element

  /// pointer in case it was a reference to the storage.

  template <class U>

  static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,

                                                   size_t N) {

    size_t NewSize = This->size() + N;

    if (LLVM_LIKELY(NewSize <= This->capacity()))

      return &Elt;

    bool ReferencesStorage = false;

    int64_t Index = -1;

    if (!U::TakesParamByValue) {

      if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {

        ReferencesStorage = true;

        Index = &Elt - This->begin();

      }

    }

    This->grow(NewSize);

    return ReferencesStorage ? This->begin() + Index : &Elt;

  }

public:

  using size_type = size_t;

  using difference_type = ptrdiff_t;

  using value_type = T;

  using iterator = T *;

  using const_iterator = const T *;

  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  using reverse_iterator = std::reverse_iterator<iterator>;

  using reference = T &;

  using const_reference = const T &;

  using pointer = T *;

  using const_pointer = const T *;

  using Base::capacity;

  using Base::empty;

  using Base::size;

  // forward iterator creation methods.

  iterator begin() { return (iterator)this->BeginX; }

  const_iterator begin() const { return (const_iterator)this->BeginX; }

  iterator end() { return begin() + size(); }

  const_iterator end() const { return begin() + size(); }

  // reverse iterator creation methods.

  reverse_iterator rbegin()            { return reverse_iterator(end()); }

  const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }

  reverse_iterator rend()              { return reverse_iterator(begin()); }

  const_reverse_iterator rend() const { return const_reverse_iterator(begin());}

  size_type size_in_bytes() const { return size() * sizeof(T); }

  size_type max_size() const {

    return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));

  }

  size_t capacity_in_bytes() const { return capacity() * sizeof(T); }

  /// Return a pointer to the vector's buffer, even if empty().

  pointer data() { return pointer(begin()); }

  /// Return a pointer to the vector's buffer, even if empty().

  const_pointer data() const { return const_pointer(begin()); }

  reference operator[](size_type idx) {

    assert(idx < size());

    return begin()[idx];

  }

  const_reference operator[](size_type idx) const {

    assert(idx < size());

    return begin()[idx];

  }

  reference front() {

    assert(!empty());

    return begin()[0];

  }

  const_reference front() const {

    assert(!empty());

    return begin()[0];

  }

  reference back() {

    assert(!empty());

    return end()[-1];

  }

  const_reference back() const {

    assert(!empty());

    return end()[-1];

  }

};

/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put

/// method implementations that are designed to work with non-trivial T's.

///

/// We approximate is_trivially_copyable with trivial move/copy construction and

/// trivial destruction. While the standard doesn't specify that you're allowed

/// copy these types with memcpy, there is no way for the type to observe this.

/// This catches the important case of std::pair<POD, POD>, which is not

/// trivially assignable.

template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&

                             (is_trivially_move_constructible<T>::value) &&

                             std::is_trivially_destructible<T>::value>

class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {

  friend class SmallVectorTemplateCommon<T>;

protected:

  static constexpr bool TakesParamByValue = false;

  using ValueParamT = const T &;

  SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

  static void destroy_range(T *S, T *E) {

    while (S != E) {

      --E;

      E->~T();

    }

  }

  /// Move the range [I, E) into the uninitialized memory starting with "Dest",

  /// constructing elements as needed.

  template<typename It1, typename It2>

  static void uninitialized_move(It1 I, It1 E, It2 Dest) {

    std::uninitialized_move(I, E, Dest);

  }

  /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",

  /// constructing elements as needed.

  template<typename It1, typename It2>

  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {

    std::uninitialized_copy(I, E, Dest);

  }

  /// Grow the allocated memory (without initializing new elements), doubling

  /// the size of the allocated memory. Guarantees space for at least one more

  /// element, or MinSize more elements if specified.

  void grow(size_t MinSize = 0);

  /// Create a new allocation big enough for \p MinSize and pass back its size

  /// in \p NewCapacity. This is the first section of \a grow().

  T *mallocForGrow(size_t MinSize, size_t &NewCapacity);

  /// Move existing elements over to the new allocation \p NewElts, the middle

  /// section of \a grow().

  void moveElementsForGrow(T *NewElts);

  /// Transfer ownership of the allocation, finishing up \a grow().

  void takeAllocationForGrow(T *NewElts, size_t NewCapacity);

  /// Reserve enough space to add one element, and return the updated element

  /// pointer in case it was a reference to the storage.

  const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {

    return this->reserveForParamAndGetAddressImpl(this, Elt, N);

  }

  /// Reserve enough space to add one element, and return the updated element

  /// pointer in case it was a reference to the storage.

  T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {

    return const_cast<T *>(

        this->reserveForParamAndGetAddressImpl(this, Elt, N));

  }

  static T &&forward_value_param(T &&V) { return std::move(V); }

  static const T &forward_value_param(const T &V) { return V; }

  void growAndAssign(size_t NumElts, const T &Elt) {

    // Grow manually in case Elt is an internal reference.

    size_t NewCapacity;

    T *NewElts = mallocForGrow(NumElts, NewCapacity);

    std::uninitialized_fill_n(NewElts, NumElts, Elt);

    this->destroy_range(this->begin(), this->end());

    takeAllocationForGrow(NewElts, NewCapacity);

    this->set_size(NumElts);

  }

  template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {

    // Grow manually in case one of Args is an internal reference.

    size_t NewCapacity;

    T *NewElts = mallocForGrow(0, NewCapacity);

    ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);

    moveElementsForGrow(NewElts);

    takeAllocationForGrow(NewElts, NewCapacity);

    this->set_size(this->size() + 1);

    return this->back();

  }

public:

  void push_back(const T &Elt) {

    const T *EltPtr = reserveForParamAndGetAddress(Elt);

    ::new ((void *)this->end()) T(*EltPtr);

    this->set_size(this->size() + 1);

  }

  void push_back(T &&Elt) {

    T *EltPtr = reserveForParamAndGetAddress(Elt);

    ::new ((void *)this->end()) T(::std::move(*EltPtr));

    this->set_size(this->size() + 1);

  }

  void pop_back() {

    this->set_size(this->size() - 1);

    this->end()->~T();

  }

};

// Define this out-of-line to dissuade the C++ compiler from inlining it.

template <typename T, bool TriviallyCopyable>

void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {

  size_t NewCapacity;

  T *NewElts = mallocForGrow(MinSize, NewCapacity);

  moveElementsForGrow(NewElts);

  takeAllocationForGrow(NewElts, NewCapacity);

}

template <typename T, bool TriviallyCopyable>

T *SmallVectorTemplateBase<T, TriviallyCopyable>::mallocForGrow(

    size_t MinSize, size_t &NewCapacity) {

  return static_cast<T *>(

      SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(

          this->getFirstEl(), MinSize, sizeof(T), NewCapacity));

}

// Define this out-of-line to dissuade the C++ compiler from inlining it.

template <typename T, bool TriviallyCopyable>

void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(

    T *NewElts) {

  // Move the elements over.

  this->uninitialized_move(this->begin(), this->end(), NewElts);

  // Destroy the original elements.

  destroy_range(this->begin(), this->end());

}

// Define this out-of-line to dissuade the C++ compiler from inlining it.

template <typename T, bool TriviallyCopyable>

void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(

    T *NewElts, size_t NewCapacity) {

  // If this wasn't grown from the inline copy, deallocate the old space.

  if (!this->isSmall())

    free(this->begin());

  this->BeginX = NewElts;

  this->Capacity = NewCapacity;

}

/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put

/// method implementations that are designed to work with trivially copyable

/// T's. This allows using memcpy in place of copy/move construction and

/// skipping destruction.

template <typename T>

class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {

  friend class SmallVectorTemplateCommon<T>;

protected:

  /// True if it's cheap enough to take parameters by value. Doing so avoids

  /// overhead related to mitigations for reference invalidation.

  static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);

  /// Either const T& or T, depending on whether it's cheap enough to take

  /// parameters by value.

  using ValueParamT = std::conditional_t<TakesParamByValue, T, const T &>;

  SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

  // No need to do a destroy loop for POD's.

  static void destroy_range(T *, T *) {}

  /// Move the range [I, E) onto the uninitialized memory

  /// starting with "Dest", constructing elements into it as needed.

  template<typename It1, typename It2>

  static void uninitialized_move(It1 I, It1 E, It2 Dest) {

    // Just do a copy.

    uninitialized_copy(I, E, Dest);

  }

  /// Copy the range [I, E) onto the uninitialized memory

  /// starting with "Dest", constructing elements into it as needed.

  template<typename It1, typename It2>

  static void uninitialized_copy(It1 I, It1 E, It2 Dest) {

    // Arbitrary iterator types; just use the basic implementation.

    std::uninitialized_copy(I, E, Dest);

  }

  /// Copy the range [I, E) onto the uninitialized memory

  /// starting with "Dest", constructing elements into it as needed.

  template <typename T1, typename T2>

  static void uninitialized_copy(

      T1 *I, T1 *E, T2 *Dest,

      std::enable_if_t<std::is_same<std::remove_const_t<T1>, T2>::value> * =

          nullptr) {

    // Use memcpy for PODs iterated by pointers (which includes SmallVector

    // iterators): std::uninitialized_copy optimizes to memmove, but we can

    // use memcpy here. Note that I and E are iterators and thus might be

    // invalid for memcpy if they are equal.

    if (I != E)

      memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));

  }

  /// Double the size of the allocated memory, guaranteeing space for at

  /// least one more element or MinSize if specified.

  void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }

  /// Reserve enough space to add one element, and return the updated element

  /// pointer in case it was a reference to the storage.

  const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {

    return this->reserveForParamAndGetAddressImpl(this, Elt, N);

  }

  /// Reserve enough space to add one element, and return the updated element

  /// pointer in case it was a reference to the storage.

  T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {

    return const_cast<T *>(

        this->reserveForParamAndGetAddressImpl(this, Elt, N));

  }

  /// Copy \p V or return a reference, depending on \a ValueParamT.

  static ValueParamT forward_value_param(ValueParamT V) { return V; }

  void growAndAssign(size_t NumElts, T Elt) {

    // Elt has been copied in case it's an internal reference, side-stepping

    // reference invalidation problems without losing the realloc optimization.

    this->set_size(0);

    this->grow(NumElts);

    std::uninitialized_fill_n(this->begin(), NumElts, Elt);

    this->set_size(NumElts);

  }

  template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {

    // Use push_back with a copy in case Args has an internal reference,

    // side-stepping reference invalidation problems without losing the realloc

    // optimization.

    push_back(T(std::forward<ArgTypes>(Args)...));

    return this->back();

  }

public:

  void push_back(ValueParamT Elt) {

    const T *EltPtr = reserveForParamAndGetAddress(Elt);

    memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));

    this->set_size(this->size() + 1);

  }

  void pop_back() { this->set_size(this->size() - 1); }

};

/// This class consists of common code factored out of the SmallVector class to

/// reduce code duplication based on the SmallVector 'N' template parameter.

template <typename T>

class SmallVectorImpl : public SmallVectorTemplateBase<T> {

  using SuperClass = SmallVectorTemplateBase<T>;

public:

  using iterator = typename SuperClass::iterator;

  using const_iterator = typename SuperClass::const_iterator;

  using reference = typename SuperClass::reference;

  using size_type = typename SuperClass::size_type;

protected:

  using SmallVectorTemplateBase<T>::TakesParamByValue;

  using ValueParamT = typename SuperClass::ValueParamT;

  // Default ctor - Initialize to empty.

  explicit SmallVectorImpl(unsigned N)

      : SmallVectorTemplateBase<T>(N) {}

  void assignRemote(SmallVectorImpl &&RHS) {

    this->destroy_range(this->begin(), this->end());

    if (!this->isSmall())

      free(this->begin());

    this->BeginX = RHS.BeginX;

    this->Size = RHS.Size;

    this->Capacity = RHS.Capacity;

    RHS.resetToSmall();

  }

public:

  SmallVectorImpl(const SmallVectorImpl &) = delete;

  ~SmallVectorImpl() {

    // Subclass has already destructed this vector's elements.

    // If this wasn't grown from the inline copy, deallocate the old space.

    if (!this->isSmall())

      free(this->begin());

  }

  void clear() {

    this->destroy_range(this->begin(), this->end());

    this->Size = 0;

  }

private:

  // Make set_size() private to avoid misuse in subclasses.

  using SuperClass::set_size;

  template <bool ForOverwrite> void resizeImpl(size_type N) {

    if (N == this->size())

      return;

    if (N < this->size()) {

      this->truncate(N);

      return;

    }

    this->reserve(N);

    for (auto I = this->end(), E = this->begin() + N; I != E; ++I)

      if (ForOverwrite)

        new (&*I) T;

      else

        new (&*I) T();

    this->set_size(N);

  }

public:

  void resize(size_type N) { resizeImpl<false>(N); }

  /// Like resize, but \ref T is POD, the new values won't be initialized.

  void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }

  /// Like resize, but requires that \p N is less than \a size().

  void truncate(size_type N) {

    assert(this->size() >= N && "Cannot increase size with truncate");

    this->destroy_range(this->begin() + N, this->end());

    this->set_size(N);

  }

  void resize(size_type N, ValueParamT NV) {

    if (N == this->size())

      return;

    if (N < this->size()) {

      this->truncate(N);

      return;

    }

    // N > this->size(). Defer to append.

    this->append(N - this->size(), NV);

  }

  void reserve(size_type N) {

    if (this->capacity() < N)

      this->grow(N);

  }

  void pop_back_n(size_type NumItems) {

    assert(this->size() >= NumItems);

    truncate(this->size() - NumItems);

  }

  [[nodiscard]] T pop_back_val() {

    T Result = ::std::move(this->back());

    this->pop_back();

    return Result;

  }

  void swap(SmallVectorImpl &RHS);

  /// Add the specified range to the end of the SmallVector.

  template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>>

  void append(ItTy in_start, ItTy in_end) {

    this->assertSafeToAddRange(in_start, in_end);

    size_type NumInputs = std::distance(in_start, in_end);

    this->reserve(this->size() + NumInputs);

    this->uninitialized_copy(in_start, in_end, this->end());

    this->set_size(this->size() + NumInputs);

  }

  /// Append \p NumInputs copies of \p Elt to the end.

  void append(size_type NumInputs, ValueParamT Elt) {

    const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);

    std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);

    this->set_size(this->size() + NumInputs);

  }

  void append(std::initializer_list<T> IL) {

    append(IL.begin(), IL.end());

  }

  void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }

  void assign(size_type NumElts, ValueParamT Elt) {

    // Note that Elt could be an internal reference.

    if (NumElts > this->capacity()) {

      this->growAndAssign(NumElts, Elt);

      return;

    }

    // Assign over existing elements.

    std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);

    if (NumElts > this->size())

      std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);

    else if (NumElts < this->size())

      this->destroy_range(this->begin() + NumElts, this->end());

    this->set_size(NumElts);

  }

  // FIXME: Consider assigning over existing elements, rather than clearing &

  // re-initializing them - for all assign(...) variants.

  template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>>

  void assign(ItTy in_start, ItTy in_end) {

    this->assertSafeToReferenceAfterClear(in_start, in_end);

    clear();

    append(in_start, in_end);