// <memory> -*- C++ -*-

// Copyright (C) 2001-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/*
 * Copyright (c) 1997-1999
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

/** @file include/memory
 *  This is a Standard C++ Library header.
 *  @ingroup memory
 */

#ifndef _GLIBCXX_MEMORY
#define _GLIBCXX_MEMORY 1

#pragma GCC system_header

/**
 * @defgroup memory Memory
 * @ingroup utilities
 *
 * Components for memory allocation, deallocation, and management.
 */

/**
 * @defgroup pointer_abstractions Pointer Abstractions
 * @ingroup memory
 *
 * Smart pointers, etc.
 */

#include <bits/stl_algobase.h>
#include <bits/allocator.h>
#include <bits/stl_construct.h>
#include <bits/stl_uninitialized.h>
#include <bits/stl_tempbuf.h>
#include <bits/stl_raw_storage_iter.h>

#if __cplusplus >= 201103L
#  include <exception>        	  // std::exception
#  include <typeinfo>         	  // std::type_info in get_deleter
#  include <iosfwd>           	  // std::basic_ostream
#  include <ext/atomicity.h>
#  include <ext/concurrence.h>
#  include <bits/functexcept.h>
#  include <bits/stl_function.h>  // std::less
#  include <bits/uses_allocator.h>
#  include <bits/alloc_traits.h>
#  include <type_traits>
#  include <debug/debug.h>
#  include <bits/unique_ptr.h>
#  include <bits/shared_ptr.h>
#  include <bits/shared_ptr_atomic.h>
#  if _GLIBCXX_USE_DEPRECATED
#    include <backward/auto_ptr.h>
#  endif
#else
#  include <backward/auto_ptr.h>
#endif

#if __cplusplus >= 201103L
#include <cstdint>
#if __cplusplus > 201703L
# include <bit>			// for ispow2
# include <new>			// for placement operator new
# include <tuple>		// for tuple, make_tuple, make_from_tuple
#endif
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

/**
 *  @brief Fit aligned storage in buffer.
 *  @ingroup memory
 *
 *  This function tries to fit @a __size bytes of storage with alignment
 *  @a __align into the buffer @a __ptr of size @a __space bytes.  If such
 *  a buffer fits then @a __ptr is changed to point to the first byte of the
 *  aligned storage and @a __space is reduced by the bytes used for alignment.
 *
 *  C++11 20.6.5 [ptr.align]
 *
 *  @param __align   A fundamental or extended alignment value.
 *  @param __size    Size of the aligned storage required.
 *  @param __ptr     Pointer to a buffer of @a __space bytes.
 *  @param __space   Size of the buffer pointed to by @a __ptr.
 *  @return the updated pointer if the aligned storage fits, otherwise nullptr.
 *
 */
inline void*
align(size_t __align, size_t __size, void*& __ptr, size_t& __space) noexcept
{
#ifdef _GLIBCXX_USE_C99_STDINT_TR1
  const auto __intptr = reinterpret_cast<uintptr_t>(__ptr);
#else
  // Cannot use std::uintptr_t so assume that std::size_t can be used instead.
  static_assert(sizeof(size_t) >= sizeof(void*),
      "std::size_t must be a suitable substitute for std::uintptr_t");
  const auto __intptr = reinterpret_cast<unsigned long long>(__ptr);
#endif
  const auto __aligned = (__intptr - 1u + __align) & -__align;
  const auto __diff = __aligned - __intptr;
  if ((__size + __diff) > __space)
    return nullptr;
  else
    {
      __space -= __diff;
      return __ptr = reinterpret_cast<void*>(__aligned);
    }
}

/** @defgroup ptr_safety Pointer Safety and Garbage Collection
 *  @ingroup memory
 *
 * Utilities to assist with garbage collection in an implementation
 * that supports <em>strict pointer safety</em>.
 * This implementation only supports <em>relaxed pointer safety</em>
 * and so these functions have no effect.
 *
 * C++11 20.6.4 [util.dynamic.safety], Pointer safety
 *
 * @{
 */

/// Constants representing the different types of pointer safety.
enum class pointer_safety { relaxed, preferred, strict };

/// Inform a garbage collector that an object is still in use.
inline void
declare_reachable(void*) { }

/// Unregister an object previously registered with declare_reachable.
template <typename _Tp>
  inline _Tp*
  undeclare_reachable(_Tp* __p) { return __p; }

/// Inform a garbage collector that a region of memory need not be traced.
inline void
declare_no_pointers(char*, size_t) { }

/// Unregister a range previously registered with declare_no_pointers.
inline void
undeclare_no_pointers(char*, size_t) { }

/// The type of pointer safety supported by the implementation.
inline pointer_safety
get_pointer_safety() noexcept { return pointer_safety::relaxed; }
// @}

#if __cplusplus > 201703L
  /** @brief Inform the compiler that a pointer is aligned.
   *
   *  @tparam _Align An alignment value (i.e. a power of two)
   *  @tparam _Tp    An object type
   *  @param  __ptr  A pointer that is aligned to _Align
   *  @ingroup memory
   */
  template<size_t _Align, class _Tp>
    [[nodiscard,__gnu__::__always_inline__]]
    constexpr _Tp* assume_aligned(_Tp* __ptr)
    {
      static_assert(std::ispow2(_Align));
      _GLIBCXX_DEBUG_ASSERT((std::uintptr_t)__ptr % _Align == 0);
      return static_cast<_Tp*>(__builtin_assume_aligned(__ptr, _Align));
    }
#endif // C++2a

#if __cplusplus > 201703L
  template<typename _Tp>
    struct __is_pair : false_type { };
  template<typename _Tp, typename _Up>
    struct __is_pair<pair<_Tp, _Up>> : true_type { };
  template<typename _Tp, typename _Up>
    struct __is_pair<const pair<_Tp, _Up>> : true_type { };

/** @addtogroup allocators
 *  @{
 */
  template<typename _Tp, typename __ = _Require<__not_<__is_pair<_Tp>>>,
	   typename _Alloc, typename... _Args>
    constexpr auto
    __uses_alloc_args(const _Alloc& __a, _Args&&... __args) noexcept
    {
      if constexpr (uses_allocator_v<remove_cv_t<_Tp>, _Alloc>)
	{
	  if constexpr (is_constructible_v<_Tp, allocator_arg_t,
					   const _Alloc&, _Args...>)
	    {
	      return tuple<allocator_arg_t, const _Alloc&, _Args&&...>(
		  allocator_arg, __a, std::forward<_Args>(__args)...);
	    }
	  else
	    {
	      static_assert(is_constructible_v<_Tp, _Args..., const _Alloc&>,
		  "construction with an allocator must be possible"
		  " if uses_allocator is true");

	      return tuple<_Args&&..., const _Alloc&>(
		  std::forward<_Args>(__args)..., __a);
	    }
	}
      else
	{
	  static_assert(is_constructible_v<_Tp, _Args...>);

	  return tuple<_Args&&...>(std::forward<_Args>(__args)...);
	}
    }

#if __cpp_concepts
  template<typename _Tp>
    concept _Std_pair = __is_pair<_Tp>::value;
#endif

// This is a temporary workaround until -fconcepts is implied by -std=gnu++2a
#if __cpp_concepts
# define _GLIBCXX_STD_PAIR_CONSTRAINT(T) _Std_pair T
# define _GLIBCXX_STD_PAIR_CONSTRAINT_(T) _Std_pair T
#else
# define _GLIBCXX_STD_PAIR_CONSTRAINT(T) \
      typename T, typename __ = _Require<__is_pair<T>>
# define _GLIBCXX_STD_PAIR_CONSTRAINT_(T) typename T, typename
#endif

  template<typename _Tp,
#if ! __cpp_concepts
	   typename __ = _Require<__not_<__is_pair<_Tp>>>,
#endif
	   typename _Alloc, typename... _Args>
    constexpr auto
    uses_allocator_construction_args(const _Alloc& __a,
				     _Args&&... __args) noexcept
#if __cpp_concepts
    requires (! _Std_pair<_Tp>)
#endif
    {
      return std::__uses_alloc_args<_Tp>(__a, std::forward<_Args>(__args)...);
    }

  template<_GLIBCXX_STD_PAIR_CONSTRAINT(_Tp), typename _Alloc,
	   typename _Tuple1, typename _Tuple2>
    constexpr auto
    uses_allocator_construction_args(const _Alloc& __a, piecewise_construct_t,
				     _Tuple1&& __x, _Tuple2&& __y) noexcept;

  template<_GLIBCXX_STD_PAIR_CONSTRAINT(_Tp), typename _Alloc>
    constexpr auto
    uses_allocator_construction_args(const _Alloc&) noexcept;

  template<_GLIBCXX_STD_PAIR_CONSTRAINT(_Tp), typename _Alloc,
	   typename _Up, typename _Vp>
    constexpr auto
    uses_allocator_construction_args(const _Alloc&, _Up&&, _Vp&&) noexcept;

  template<_GLIBCXX_STD_PAIR_CONSTRAINT(_Tp), typename _Alloc,
	   typename _Up, typename _Vp>
    constexpr auto
    uses_allocator_construction_args(const _Alloc&,
				     const pair<_Up, _Vp>&) noexcept;

  template<_GLIBCXX_STD_PAIR_CONSTRAINT(_Tp), typename _Alloc,
	   typename _Up, typename _Vp>
    constexpr auto
    uses_allocator_construction_args(const _Alloc&, pair<_Up, _Vp>&&) noexcept;

  template<_GLIBCXX_STD_PAIR_CONSTRAINT_(_Tp), typename _Alloc,
	   typename _Tuple1, typename _Tuple2>
    constexpr auto
    uses_allocator_construction_args(const _Alloc& __a, piecewise_construct_t,
				     _Tuple1&& __x, _Tuple2&& __y) noexcept
    {
      using _Tp1 = typename _Tp::first_type;
      using _Tp2 = typename _Tp::second_type;

      return std::make_tuple(piecewise_construct,
	  std::apply([&__a](auto&&... __args1) {
	      return std::uses_allocator_construction_args<_Tp1>(
		  __a, std::forward<decltype(__args1)>(__args1)...);
	  }, std::forward<_Tuple1>(__x)),
	  std::apply([&__a](auto&&... __args2) {
	      return std::uses_allocator_construction_args<_Tp2>(
		  __a, std::forward<decltype(__args2)>(__args2)...);
	  }, std::forward<_Tuple2>(__y)));
    }

  template<_GLIBCXX_STD_PAIR_CONSTRAINT_(_Tp), typename _Alloc>
    constexpr auto
    uses_allocator_construction_args(const _Alloc& __a) noexcept
    {
      using _Tp1 = typename _Tp::first_type;
      using _Tp2 = typename _Tp::second_type;

      return std::make_tuple(piecewise_construct,
	  std::uses_allocator_construction_args<_Tp1>(__a),
	  std::uses_allocator_construction_args<_Tp2>(__a));
    }

  template<_GLIBCXX_STD_PAIR_CONSTRAINT_(_Tp), typename _Alloc,
	   typename _Up, typename _Vp>
    constexpr auto
    uses_allocator_construction_args(const _Alloc& __a, _Up&& __u, _Vp&& __v)
      noexcept
    {
      using _Tp1 = typename _Tp::first_type;
      using _Tp2 = typename _Tp::second_type;

      return std::make_tuple(piecewise_construct,
	  std::uses_allocator_construction_args<_Tp1>(__a,
	    std::forward<_Up>(__u)),
	  std::uses_allocator_construction_args<_Tp2>(__a,
	    std::forward<_Vp>(__v)));
    }

  template<_GLIBCXX_STD_PAIR_CONSTRAINT_(_Tp), typename _Alloc,
	   typename _Up, typename _Vp>
    constexpr auto
    uses_allocator_construction_args(const _Alloc& __a,
				     const pair<_Up, _Vp>& __pr) noexcept
    {
      using _Tp1 = typename _Tp::first_type;
      using _Tp2 = typename _Tp::second_type;

      return std::make_tuple(piecewise_construct,
	  std::uses_allocator_construction_args<_Tp1>(__a, __pr.first),
	  std::uses_allocator_construction_args<_Tp2>(__a, __pr.second));
    }

  template<_GLIBCXX_STD_PAIR_CONSTRAINT_(_Tp), typename _Alloc,
	   typename _Up, typename _Vp>
    constexpr auto
    uses_allocator_construction_args(const _Alloc& __a,
				     pair<_Up, _Vp>&& __pr) noexcept
    {
      using _Tp1 = typename _Tp::first_type;
      using _Tp2 = typename _Tp::second_type;

      return std::make_tuple(piecewise_construct,
	  std::uses_allocator_construction_args<_Tp1>(__a,
	    std::move(__pr).first),
	  std::uses_allocator_construction_args<_Tp2>(__a,
	    std::move(__pr).second));
    }

  template<typename _Tp, typename _Alloc, typename... _Args>
    inline _Tp
    make_obj_using_allocator(const _Alloc& __a, _Args&&... __args)
    {
      return std::make_from_tuple<_Tp>(
	  std::uses_allocator_construction_args<_Tp>(__a,
	    std::forward<_Args>(__args)...));
    }

  template<typename _Tp, typename _Alloc, typename... _Args>
    inline _Tp*
    uninitialized_construct_using_allocator(_Tp* __p, const _Alloc& __a,
					    _Args&&... __args)
    {
      void* __vp = const_cast<void*>(static_cast<const volatile void*>(__p));
      return ::new(__vp) _Tp(std::make_obj_using_allocator<_Tp>(__a,
	    std::forward<_Args>(__args)...));
    }
// @}

#endif // C++2a

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
#endif // C++11

#if __cplusplus > 201402L
// Parallel STL algorithms
# if _PSTL_EXECUTION_POLICIES_DEFINED
// If <execution> has already been included, pull in implementations
#  include <pstl/glue_memory_impl.h>
# else
// Otherwise just pull in forward declarations
#  include <pstl/glue_memory_defs.h>
# endif

// Feature test macro for parallel algorithms
# define __cpp_lib_parallel_algorithm 201603L
#endif // C++17

#endif /* _GLIBCXX_MEMORY */