//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the SmallVector class.
//
//===----------------------------------------------------------------------===//

// ATen: modified from llvm::SmallVector.
// replaced report_bad_alloc_error with std::bad_alloc
// replaced isPodLike<T> with C10_IS_TRIVIALLY_COPYABLE (moved to Macros.h)
// replaced iterator_range constructor with inline Container&& constructor
// removed LLVM_NODISCARD and LLVM_ATTRIBUTE_ALWAYS_INLINE qualifiers
// removed LLVM_UNLIKELY

#pragma once

#include <c10/util/AlignOf.h>
#include <c10/macros/Macros.h>

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>

namespace c10 {

namespace detail {

// From llvm/Support/MathExtras.h
static inline uint64_t NextPowerOf2(uint64_t A) {
  A |= (A >> 1);
  A |= (A >> 2);
  A |= (A >> 4);
  A |= (A >> 8);
  A |= (A >> 16);
  A |= (A >> 32);
  return A + 1;
}

} // namespace detail

/// This is all the non-templated stuff common to all SmallVectors.
class C10_API SmallVectorBase {
 protected:
  void *BeginX, *EndX, *CapacityX;

 protected:
  SmallVectorBase(void* FirstEl, size_t Size)
      : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl + Size) {}

  /// 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.
  void grow_pod(void* FirstEl, size_t MinSizeInBytes, size_t TSize);

 public:
  /// This returns size()*sizeof(T).
  size_t size_in_bytes() const {
    return size_t((char*)EndX - (char*)BeginX);
  }

  /// capacity_in_bytes - This returns capacity()*sizeof(T).
  size_t capacity_in_bytes() const {
    return size_t((char*)CapacityX - (char*)BeginX);
  }

  bool empty() const {
    return BeginX == EndX;
  }
};

/// 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 {
 private:
  template <typename, unsigned>
  friend struct SmallVectorStorage;

  // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
  // don't want it to be automatically run, so we need to represent the space as
  // something else.  Use an array of char of sufficient alignment.
  using U = AlignedCharArrayUnion<T>;
  U FirstEl;
  // Space after 'FirstEl' is clobbered, do not add any instance vars after it.

 protected:
  SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}

  void grow_pod(size_t MinSizeInBytes, size_t TSize) {
    SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
  }

  /// Return true if this is a smallvector which has not had dynamic
  /// memory allocated for it.
  bool isSmall() const {
    return BeginX == static_cast<const void*>(&FirstEl);
  }

  /// Put this vector in a state of being small.
  void resetToSmall() {
    BeginX = EndX = CapacityX = &FirstEl;
  }

  void setEnd(T* P) {
    this->EndX = P;
  }

 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*;

  // forward iterator creation methods.
  iterator begin() {
    return (iterator)this->BeginX;
  }
  const_iterator begin() const {
    return (const_iterator)this->BeginX;
  }
  iterator end() {
    return (iterator)this->EndX;
  }
  const_iterator end() const {
    return (const_iterator)this->EndX;
  }

 protected:
  iterator capacity_ptr() {
    return (iterator)this->CapacityX;
  }
  const_iterator capacity_ptr() const {
    return (const_iterator)this->CapacityX;
  }

 public:
  // 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() const {
    return end() - begin();
  }
  size_type max_size() const {
    return size_type(-1) / sizeof(T);
  }

  /// Return the total number of elements in the currently allocated buffer.
  size_t capacity() const {
    return capacity_ptr() - begin();
  }

  /// 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());
  }

  // SmallVector::at is NOT from LLVM.
  reference at(size_type idx) {
    assert(idx < size());
    return begin()[idx];
  }
  const_reference at(size_type idx) const {
    assert(idx < size());
    return begin()[idx];
  }

  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<isPodLike = false> - This is where we put method
/// implementations that are designed to work with non-POD-like T's.
template <typename T, bool isPodLike>
class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
 protected:
  SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}

  static void destroy_range(T* S, T* E) {
    while (S != E) {
      --E;
      E->~T();
    }
  }

  /// Move the range [Iit, Eit) into the uninitialized memory starting with "Dest",
  /// constructing elements as needed.
  template <typename It1, typename It2>
  static void uninitialized_move(It1 Iit, It1 Eit, It2 Dest) {
    std::uninitialized_copy(
        std::make_move_iterator(Iit), std::make_move_iterator(Eit), Dest);
  }

  /// Copy the range [Iit, Eit) onto the uninitialized memory starting with "Dest",
  /// constructing elements as needed.
  template <typename It1, typename It2>
  static void uninitialized_copy(It1 Iit, It1 Eit, It2 Dest) {
    std::uninitialized_copy(Iit, Eit, 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);

 public:
  void push_back(const T& Elt) {
    if (this->EndX >= this->CapacityX)
      this->grow();
    ::new ((void*)this->end()) T(Elt);
    this->setEnd(this->end() + 1);
  }

  void push_back(T&& Elt) {
    if (this->EndX >= this->CapacityX)
      this->grow();
    ::new ((void*)this->end()) T(::std::move(Elt));
    this->setEnd(this->end() + 1);
  }

  void pop_back() {
    this->setEnd(this->end() - 1);
    this->end()->~T();
  }
};

// Define this out-of-line to dissuade the C++ compiler from inlining it.
template <typename T, bool isPodLike>
void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
  size_t CurCapacity = this->capacity();
  size_t CurSize = this->size();
  // Always grow, even from zero.
  size_t NewCapacity = size_t(detail::NextPowerOf2(CurCapacity + 2));
  if (NewCapacity < MinSize)
    NewCapacity = MinSize;
  T* NewElts = static_cast<T*>(malloc(NewCapacity * sizeof(T)));
  if (NewElts == nullptr)
    throw std::bad_alloc();

  // Move the elements over.
  this->uninitialized_move(this->begin(), this->end(), NewElts);

  // Destroy the original elements.
  destroy_range(this->begin(), this->end());

  // If this wasn't grown from the inline copy, deallocate the old space.
  if (!this->isSmall())
    free(this->begin());

  this->setEnd(NewElts + CurSize);
  this->BeginX = NewElts;
  this->CapacityX = this->begin() + NewCapacity;
}

/// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
/// implementations that are designed to work with POD-like T's.
template <typename T>
class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
 protected:
  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 [Iit, Eit) onto the uninitialized memory
  /// starting with "Dest", constructing elements into it as needed.
  template <typename It1, typename It2>
  static void uninitialized_move(It1 Iit, It1 Eit, It2 Dest) {
    // Just do a copy.
    uninitialized_copy(Iit, Eit, Dest);
  }

  /// Copy the range [Iit, Eit) onto the uninitialized memory
  /// starting with "Dest", constructing elements into it as needed.
  template <typename It1, typename It2>
  static void uninitialized_copy(It1 Iit, It1 Eit, It2 Dest) {
    // Arbitrary iterator types; just use the basic implementation.
    std::uninitialized_copy(Iit, Eit, Dest);
  }

  /// Copy the range [Iit, Eit) onto the uninitialized memory
  /// starting with "Dest", constructing elements into it as needed.
  template <typename T1, typename T2>
  static void uninitialized_copy(