//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include <memory>
#include <memory_resource>

#ifndef _LIBCPP_HAS_NO_ATOMIC_HEADER
#  include <atomic>
#elif !defined(_LIBCPP_HAS_NO_THREADS)
#  include <mutex>
#  if defined(__ELF__) && defined(_LIBCPP_LINK_PTHREAD_LIB)
#    pragma comment(lib, "pthread")
#  endif
#endif

_LIBCPP_BEGIN_NAMESPACE_STD

namespace pmr {

// memory_resource

memory_resource::~memory_resource() = default;

// new_delete_resource()

#ifdef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION
static bool is_aligned_to(void* ptr, size_t align) {
  void* p2     = ptr;
  size_t space = 1;
  void* result = std::align(align, 1, p2, space);
  return (result == ptr);
}
#endif

class _LIBCPP_EXPORTED_FROM_ABI __new_delete_memory_resource_imp : public memory_resource {
  void* do_allocate(size_t bytes, size_t align) override {
#ifndef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION
    return std::__libcpp_allocate(bytes, align);
#else
    if (bytes == 0)
      bytes = 1;
    void* result = std::__libcpp_allocate(bytes, align);
    if (!is_aligned_to(result, align)) {
      std::__libcpp_deallocate(result, bytes, align);
      __throw_bad_alloc();
    }
    return result;
#endif
  }

  void do_deallocate(void* p, size_t bytes, size_t align) override { std::__libcpp_deallocate(p, bytes, align); }

  bool do_is_equal(const memory_resource& other) const noexcept override { return &other == this; }
};

// null_memory_resource()

class _LIBCPP_EXPORTED_FROM_ABI __null_memory_resource_imp : public memory_resource {
  void* do_allocate(size_t, size_t) override { __throw_bad_alloc(); }
  void do_deallocate(void*, size_t, size_t) override {}
  bool do_is_equal(const memory_resource& other) const noexcept override { return &other == this; }
};

namespace {

union ResourceInitHelper {
  struct {
    __new_delete_memory_resource_imp new_delete_res;
    __null_memory_resource_imp null_res;
  } resources;
  char dummy;
  constexpr ResourceInitHelper() : resources() {}
  ~ResourceInitHelper() {}
};

// Pretend we're inside a system header so the compiler doesn't flag the use of the init_priority
// attribute with a value that's reserved for the implementation (we're the implementation).
#include "memory_resource_init_helper.h"

} // end namespace

memory_resource* new_delete_resource() noexcept { return &res_init.resources.new_delete_res; }

memory_resource* null_memory_resource() noexcept { return &res_init.resources.null_res; }

// default_memory_resource()

static memory_resource* __default_memory_resource(bool set = false, memory_resource* new_res = nullptr) noexcept {
#ifndef _LIBCPP_HAS_NO_ATOMIC_HEADER
  static constinit atomic<memory_resource*> __res{&res_init.resources.new_delete_res};
  if (set) {
    new_res = new_res ? new_res : new_delete_resource();
    // TODO: Can a weaker ordering be used?
    return std::atomic_exchange_explicit(&__res, new_res, memory_order_acq_rel);
  } else {
    return std::atomic_load_explicit(&__res, memory_order_acquire);
  }
#elif !defined(_LIBCPP_HAS_NO_THREADS)
  static constinit memory_resource* res = &res_init.resources.new_delete_res;
  static mutex res_lock;
  if (set) {
    new_res = new_res ? new_res : new_delete_resource();
    lock_guard<mutex> guard(res_lock);
    memory_resource* old_res = res;
    res                      = new_res;
    return old_res;
  } else {
    lock_guard<mutex> guard(res_lock);
    return res;
  }
#else
  static constinit memory_resource* res = &res_init.resources.new_delete_res;
  if (set) {
    new_res                  = new_res ? new_res : new_delete_resource();
    memory_resource* old_res = res;
    res                      = new_res;
    return old_res;
  } else {
    return res;
  }
#endif
}

memory_resource* get_default_resource() noexcept { return __default_memory_resource(); }

memory_resource* set_default_resource(memory_resource* __new_res) noexcept {
  return __default_memory_resource(true, __new_res);
}

// 23.12.5, mem.res.pool

static size_t roundup(size_t count, size_t alignment) {
  size_t mask = alignment - 1;
  return (count + mask) & ~mask;
}

struct unsynchronized_pool_resource::__adhoc_pool::__chunk_footer {
  __chunk_footer* __next_;
  char* __start_;
  size_t __align_;
  size_t __allocation_size() { return (reinterpret_cast<char*>(this) - __start_) + sizeof(*this); }
};

void unsynchronized_pool_resource::__adhoc_pool::__release_ptr(memory_resource* upstream) {
  while (__first_ != nullptr) {
    __chunk_footer* next = __first_->__next_;
    upstream->deallocate(__first_->__start_, __first_->__allocation_size(), __first_->__align_);
    __first_ = next;
  }
}

void* unsynchronized_pool_resource::__adhoc_pool::__do_allocate(memory_resource* upstream, size_t bytes, size_t align) {
  const size_t footer_size  = sizeof(__chunk_footer);
  const size_t footer_align = alignof(__chunk_footer);

  if (align < footer_align)
    align = footer_align;

  size_t aligned_capacity = roundup(bytes, footer_align) + footer_size;

  void* result = upstream->allocate(aligned_capacity, align);

  __chunk_footer* h = (__chunk_footer*)((char*)result + aligned_capacity - footer_size);
  h->__next_        = __first_;
  h->__start_       = (char*)result;
  h->__align_       = align;
  __first_          = h;
  return result;
}

void unsynchronized_pool_resource::__adhoc_pool::__do_deallocate(
    memory_resource* upstream, void* p, size_t bytes, size_t align) {
  _LIBCPP_ASSERT_NON_NULL(__first_ != nullptr, "deallocating a block that was not allocated with this allocator");
  if (__first_->__start_ == p) {
    __chunk_footer* next = __first_->__next_;
    upstream->deallocate(p, __first_->__allocation_size(), __first_->__align_);
    __first_ = next;
  } else {
    for (__chunk_footer* h = __first_; h->__next_ != nullptr; h = h->__next_) {
      if (h->__next_->__start_ == p) {
        __chunk_footer* next = h->__next_->__next_;
        upstream->deallocate(p, h->__next_->__allocation_size(), h->__next_->__align_);
        h->__next_ = next;
        return;
      }
    }
    // The request to deallocate memory ends up being a no-op, likely resulting in a memory leak.
    _LIBCPP_ASSERT_VALID_DEALLOCATION(false, "deallocating a block that was not allocated with this allocator");
  }
}

class unsynchronized_pool_resource::__fixed_pool {
  struct __chunk_footer {
    __chunk_footer* __next_;
    char* __start_;
    size_t __align_;
    size_t __allocation_size() { return (reinterpret_cast<char*>(this) - __start_) + sizeof(*this); }
  };

  struct __vacancy_header {
    __vacancy_header* __next_vacancy_;
  };

  __chunk_footer* __first_chunk_     = nullptr;
  __vacancy_header* __first_vacancy_ = nullptr;

public:
  explicit __fixed_pool() = default;

  void __release_ptr(memory_resource* upstream) {
    __first_vacancy_ = nullptr;
    while (__first_chunk_ != nullptr) {
      __chunk_footer* next = __first_chunk_->__next_;
      upstream->deallocate(__first_chunk_->__start_, __first_chunk_->__allocation_size(), __first_chunk_->__align_);
      __first_chunk_ = next;
    }
  }

  void* __try_allocate_from_vacancies() {
    if (__first_vacancy_ != nullptr) {
      void* result     = __first_vacancy_;
      __first_vacancy_ = __first_vacancy_->__next_vacancy_;
      return result;
    }
    return nullptr;
  }

  void* __allocate_in_new_chunk(memory_resource* upstream, size_t block_size, size_t chunk_size) {
    _LIBCPP_ASSERT_INTERNAL(chunk_size % block_size == 0, "");
    static_assert(__default_alignment >= alignof(std::max_align_t), "");
    static_assert(__default_alignment >= alignof(__chunk_footer), "");
    static_assert(__default_alignment >= alignof(__vacancy_header), "");

    const size_t footer_size  = sizeof(__chunk_footer);
    const size_t footer_align = alignof(__chunk_footer);

    size_t aligned_capacity = roundup(chunk_size, footer_align) + footer_size;

    void* result = upstream->allocate(aligned_capacity, __default_alignment);

    __chunk_footer* h = (__chunk_footer*)((char*)result + aligned_capacity - footer_size);
    h->__next_        = __first_chunk_;
    h->__start_       = (char*)result;
    h->__align_       = __default_alignment;
    __first_chunk_    = h;

    if (chunk_size > block_size) {
      __vacancy_header* last_vh = this->__first_vacancy_;
      for (size_t i = block_size; i != chunk_size; i += block_size) {
        __vacancy_header* vh = (__vacancy_header*)((char*)result + i);
        vh->__next_vacancy_  = last_vh;
        last_vh              = vh;
      }
      this->__first_vacancy_ = last_vh;
    }
    return result;
  }

  void __evacuate(void* p) {
    __vacancy_header* vh = (__vacancy_header*)(p);
    vh->__next_vacancy_  = __first_vacancy_;
    __first_vacancy_     = vh;
  }

  size_t __previous_chunk_size_in_bytes() const { return __first_chunk_ ? __first_chunk_->__allocation_size() : 0; }

  static const size_t __default_alignment = alignof(max_align_t);
};

size_t unsynchronized_pool_resource::__pool_block_size(int i) const { return size_t(1) << __log2_pool_block_size(i); }

int unsynchronized_pool_resource::__log2_pool_block_size(int i) const { return (i + __log2_smallest_block_size); }

int unsynchronized_pool_resource::__pool_index(size_t bytes, size_t align) const {
  if (align > alignof(std::max_align_t) || bytes > (size_t(1) << __num_fixed_pools_))
    return __num_fixed_pools_;
  else {
    int i = 0;
    bytes = (bytes > align) ? bytes : align;
    bytes -= 1;
    bytes >>= __log2_smallest_block_size;
    while (bytes != 0) {
      bytes >>= 1;
      i += 1;
    }
    return i;
  }
}

unsynchronized_pool_resource::unsynchronized_pool_resource(const pool_options& opts, memory_resource* upstream)
    : __res_(upstream), __fixed_pools_(nullptr) {
  size_t largest_block_size;
  if (opts.largest_required_pool_block == 0)
    largest_block_size = __default_largest_block_size;
  else if (opts.largest_required_pool_block < __smallest_block_size)
    largest_block_size = __smallest_block_size;
  else if (opts.largest_required_pool_block > __max_largest_block_size)
    largest_block_size = __max_largest_block_size;
  else
    largest_block_size = opts.largest_required_pool_block;

  if (opts.max_blocks_per_chunk == 0)
    __options_max_blocks_per_chunk_ = __max_blocks_per_chunk;
  else if (opts.max_blocks_per_chunk < __min_blocks_per_chunk)
    __options_max_blocks_per_chunk_ = __min_blocks_per_chunk;
  else if (opts.max_blocks_per_chunk > __max_blocks_per_chunk)
    __options_max_blocks_per_chunk_ = __max_blocks_per_chunk;
  else
    __options_max_blocks_per_chunk_ = opts.max_blocks_per_chunk;

  __num_fixed_pools_ = 1;
  size_t capacity    = __smallest_block_size;
  while (capacity < largest_block_size) {
    capacity <<= 1;
    __num_fixed_pools_ += 1;
  }
}

pool_options unsynchronized_pool_resource::options() const {
  pool_options p;
  p.max_blocks_per_chunk        = __options_max_blocks_per_chunk_;
  p.largest_required_pool_block = __pool_block_size(__num_fixed_pools_ - 1);
  return p;
}

void unsynchronized_pool_resource::release() {
  __adhoc_pool_.__release_ptr(__res_);
  if (__fixed_pools_ != nullptr) {
    const int n = __num_fixed_pools_;
    for (int i = 0; i < n; ++i)
      __fixed_pools_[i].__release_ptr(__res_);
    __res_->deallocate(__fixed_pools_, __num_fixed_pools_ * sizeof(__fixed_pool), alignof(__fixed_pool));
    __fixed_pools_ = nullptr;
  }
}

void* unsynchronized_pool_resource::do_allocate(size_t bytes, size_t align) {
  // A pointer to allocated storage (6.6.4.4.1) with a size of at least bytes.
  // The size and alignment of the allocated memory shall meet the requirements for
  // a class derived from memory_resource (23.12).
  // If the pool selected for a block of size bytes is unable to satisfy the memory request
  // from its own internal data structures, it will call upstream_resource()->allocate()
  // to obtain more memory. If bytes is larger than that which the largest pool can handle,
  // then memory will be allocated using upstream_resource()->allocate().

  int i = __pool_index(bytes, align);
  if (i == __num_fixed_pools_)
    return __adhoc_pool_.__do_allocate(__res_, bytes, align);
  else {
    if (__fixed_pools_ == nullptr) {
      __fixed_pools_ =
          (__fixed_pool*)__res_->allocate(__num_fixed_pools_ * sizeof(__fixed_pool), alignof(__fixed_pool));
      __fixed_pool* first = __fixed_pools_;
      __fixed_pool* last  = __fixed_pools_ + __num_fixed_pools_;
      for (__fixed_pool* pool = first; pool != last; ++pool)
        ::new ((void*)pool) __fixed_pool;
    }
    void* result = __fixed_pools_[i].__try_allocate_from_vacancies();
    if (result == nullptr) {
      auto min = [](size_t a, size_t b) { return a < b ? a : b; };
      auto max = [](size_t a, size_t b) { return a < b ? b : a; };

      size_t prev_chunk_size_in_bytes  = __fixed_pools_[i].__previous_chunk_size_in_bytes();
      size_t prev_chunk_size_in_blocks = prev_chunk_size_in_bytes >> __log2_pool_block_size(i);

      size_t chunk_size_in_blocks;

      if (prev_chunk_size_in_blocks == 0) {
        size_t min_blocks_per_chunk = max(__min_bytes_per_chunk >> __log2_pool_block_size(i), __min_blocks_per_chunk);
        chunk_size_in_blocks        = min_blocks_per_chunk;
      } else {
        static_assert(__max_bytes_per_chunk <= SIZE_MAX - (__max_bytes_per_chunk / 4), "unsigned overflow is possible");
        chunk_size_in_blocks = prev_chunk_size_in_blocks + (prev_chunk_size_in_blocks / 4);
      }

      size_t max_blocks_per_chunk =
          min((__max_bytes_per_chunk >> __log2_pool_block_size(i)),
              min(__max_blocks_per_chunk, __options_max_blocks_per_chunk_));
      if (chunk_size_in_blocks > max_blocks_per_chunk)
        chunk_size_in_blocks = max_blocks_per_chunk;

      size_t block_size = __pool_block_size(i);

      size_t chunk_size_in_bytes = (chunk_size_in_blocks << __log2_pool_block_size(i));
      result                     = __fixed_pools_[i].__allocate_in_new_chunk(__res_, block_size, chunk_size_in_bytes);
    }
    return result;
  }
}

void unsynchronized_pool_resource::do_deallocate(void* p, size_t bytes, size_t align) {
  // Returns the memory at p to the pool. It is unspecified if,
  // or under what circumstances, this operation will result in
  // a call to upstream_resource()->deallocate().

  int i = __pool_index(bytes, align);
  if (i == __num_fixed_pools_)
    return __adhoc_pool_.__do_deallocate(__res_, p, bytes, align);
  else {
    _LIBCPP_ASSERT_NON_NULL(
        __fixed_pools_ != nullptr, "deallocating a block that was not allocated with this allocator");
    __fixed_pools_[i].__evacuate(p);
  }
}

bool synchronized_pool_resource::do_is_equal(const memory_resource& other) const noexcept { return &other == this; }

// 23.12.6, mem.res.monotonic.buffer

static void* align_down(size_t align, size_t size, void*& ptr, size_t& space) {
  if (size > space)
    return nullptr;

  char* p1      = static_cast<char*>(ptr);
  char* new_ptr = reinterpret_cast<char*>(reinterpret_cast<uintptr_t>(p1 - size) & ~(align - 1));

  if (new_ptr < (p1 - space))
    return nullptr;

  ptr = new_ptr;
  space -= p1 - new_ptr;

  return ptr;
}

void* monotonic_buffer_resource::__initial_descriptor::__try_allocate_from_chunk(size_t bytes, size_t align) {
  if (!__cur_)
    return nullptr;
  void* new_ptr       = static_cast<void*>(__cur_);
  size_t new_capacity = (__cur_ - __start_);
  void* aligned_ptr   = align_down(align, bytes, new_ptr, new_capacity);
  if (aligned_ptr != nullptr)
    __cur_ = static_cast<char*>(new_ptr);
  return aligned_ptr;
}

void* monotonic_buffer_resource::__chunk_footer::__try_allocate_from_chunk(size_t bytes, size_t align) {
  void* new_ptr       = static_cast<void*>(__cur_);
  size_t new_capacity = (__cur_ - __start_);
  void* aligned_ptr   = align_down(align, bytes, new_ptr, new_capacity);
  if (aligned_ptr != nullptr)
    __cur_ = static_cast<char*>(new_ptr);
  return aligned_ptr;
}

void* monotonic_buffer_resource::do_allocate(size_t bytes, size_t align) {
  const size_t footer_size  = sizeof(__chunk_footer);
  const size_t footer_align = alignof(__chunk_footer);

  auto previous_allocation_size = [&]() {
    if (__chunks_ != nullptr)
      return __chunks_->__allocation_size();

    size_t newsize = (__initial_.__start_ != nullptr) ? (__initial_.__end_ - __initial_.__start_) : __initial_.__size_;

    return roundup(newsize, footer_align) + footer_size;
  };

  if (void* result = __initial_.__try_allocate_from_chunk(bytes, align))
    return result;
  if (__chunks_ != nullptr) {
    if (void* result = __chunks_->__try_allocate_from_chunk(bytes, align))
      return result;
  }

  // Allocate a brand-new chunk.

  if (align < footer_align)
    align = footer_align;

  size_t aligned_capacity  = roundup(bytes, footer_align) + footer_size;
  size_t previous_capacity = previous_allocation_size();

  if (aligned_capacity <= previous_capacity) {
    size_t newsize   = 2 * (previous_capacity - footer_size);
    aligned_capacity = roundup(newsize, footer_align) + footer_size;
  }

  char* start            = (char*)__res_->allocate(aligned_capacity, align);
  auto end               = start + aligned_capacity - footer_size;
  __chunk_footer* footer = (__chunk_footer*)(end);
  footer->__next_        = __chunks_;
  footer->__start_       = start;
  footer->__cur_         = end;
  footer->__align_       = align;
  __chunks_              = footer;

  return __chunks_->__try_allocate_from_chunk(bytes, align);
}

} // namespace pmr

_LIBCPP_END_NAMESPACE_STD