#include <stdint.h>
#include <stddef.h>
#include <memory>

#include "testing/base/public/benchmark.h"

namespace {

template <int option>
struct Vector {
  using allocator_type = std::allocator<int>;
  using __alloc_traits = std::allocator_traits<allocator_type>;
  using pointer = typename __alloc_traits::pointer;
  using size_type = size_t;

  ~Vector() { __alloc_traits::deallocate(alloc_, begin_, end_cap_ - begin_); }

  void reserve(size_type n) {
    if (n > capacity()) {
      __grow(n);
    }
  }

  void clear() { end_ = begin_; }

  void push_back(int value) {
    if (option == 1) {
      pointer end = end_;
      if (end == end_cap_) {
        size_type sz = end_ - begin_;
        size_type n = sz ? sz * 2 : 2;
        __push_back_slow_path(n, value);
      } else {
        *end = value;
        end_ = end + 1;
      }
    } else if (option == 2) {
      pointer end = end_;
      if (end == end_cap_) {
        size_type sz = end_ - begin_;
        size_type n = sz ? sz * 2 : 2;
        __push_back_slow_path(n, value);
        end = end_ - 1;
      } else {
        *end = value;
      }
      end_ = end + 1;
    } else if (option == 3) {
      pointer end = end_;
      if (end == end_cap_) {
        size_type sz = end_ - begin_;
        size_type n = sz ? sz * 2 : 2;
        begin_ = __push_back_slow_path(begin_, sz, n, value);
        end_ = end = begin_ + sz;
        end_cap_ = begin_ + n;
      } else {
        *end = value;
        end_ = end + 1;
      }
    }
  }

  int* data() { return begin_; }
  size_type size() const { return end_ - begin_; }
  size_type capacity() const { return end_cap_ - begin_; }

 private:
  struct buffer {
    pointer begin;
    pointer first;
    pointer end;
    pointer end_cap;

    buffer(size_t sz, size_type n) {
      allocator_type alloc;
      begin = __alloc_traits::allocate(alloc, n);
      first = end = begin + sz;
      end_cap = begin + n;
    }

    ~buffer() {
      allocator_type alloc;
      __alloc_traits::deallocate(alloc, begin, end_cap - begin);
    }

    void construct_backwards(int i) { *(--first) = i; }

    void construct_backwards(pointer begin, pointer end) {
      while (end != begin) {
        *(--first) = *(--end);
      }
    }
  };

  void __swap_in_buffer(buffer& b);

  void __grow(size_type n);
  void __push_back_slow_path(size_type n, int i);
  static pointer __push_back_slow_path(pointer begin,
                                       size_type sz, size_type n, int i);

  [[no_unique_address]] allocator_type alloc_;
  pointer begin_ = nullptr;
  pointer end_ = nullptr;
  pointer end_cap_ = nullptr;
};

template <int option>
void Vector<option>::__swap_in_buffer(buffer& b) {
  b.first = begin_;
  begin_ = b.begin;
  b.begin = b.first;
  std::swap(b.end, end_);
  std::swap(b.end_cap, end_cap_);
}

template <int option>
void Vector<option>::__grow(size_type n) {
  size_type sz = end_ - begin_;
  buffer b(sz, n);
  b.construct_backwards(begin_, begin_ + sz);
  __swap_in_buffer(b);
}

template <int option>
#if !defined(INLINE_SLOW_PATH)
__attribute__((noinline))
#endif
void Vector<option>::__push_back_slow_path(size_type n, int value) {
  size_t sz = end_ - begin_;
  buffer b(sz + 1, n);
  b.construct_backwards(value);
  b.construct_backwards(begin_, end_);
  __swap_in_buffer(b);
}

template <int option>
#if !defined(INLINE_SLOW_PATH)
__attribute__((noinline))
#endif
typename Vector<option>::pointer
Vector<option>::__push_back_slow_path(pointer begin, size_t sz, size_type n,
                                      int value) {
  buffer b(sz + 1, n);
  b.construct_backwards(value);
  b.construct_backwards(begin, begin + sz);

  b.end = begin + sz;
  b.end_cap = begin + n;

  b.first = begin;
  begin = b.begin;
  b.begin = b.first;

  return begin;
}

template <typename Vector>
void BM_Pushback(benchmark::State& state) {
  int count = state.range(0);
  Vector vec;
  vec.reserve(count);
  while (state.KeepRunningBatch(count)) {
    vec.clear();
#pragma nounroll
    for (int i = 0; i < count; ++i) {
      vec.push_back(i);
    }
    testing::DoNotOptimize(vec.data());
  }
}

BENCHMARK(BM_Pushback<Vector<1>>)->Arg(4000);
BENCHMARK(BM_Pushback<Vector<2>>)->Arg(4000);
BENCHMARK(BM_Pushback<Vector<3>>)->Arg(4000);

}  // namespace