Fennix/Kernel/include_std/memory

/*
	This file is part of Fennix Kernel.

	Fennix Kernel 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 of
	the License, or (at your option) any later version.

	Fennix Kernel 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.

	You should have received a copy of the GNU General Public License
	along with Fennix Kernel. If not, see <https://www.gnu.org/licenses/>.
*/

#pragma once

#include <type_traits>
#include <functional>
#include <iterator>
#include <cstddef>
#include <utility>
#include <limits>
#include <atomic>
#include <new>

#include <debug.h>

namespace std
{
	namespace detail
	{
		template <class>
		constexpr bool is_unbounded_array_v = false;
		template <class T>
		constexpr bool is_unbounded_array_v<T[]> = true;

		template <class>
		constexpr bool is_bounded_array_v = false;
		template <class T, std::size_t N>
		constexpr bool is_bounded_array_v<T[N]> = true;
	}

	template <class T, class... Args>
	constexpr T *construct_at(T *p, Args &&...args)
	{
		return ::new (static_cast<void *>(p)) T(std::forward<Args>(args)...);
	}

	template <class T>
	constexpr void destroy_at(T *p)
	{
		p->~T();
	}

	template <class T>
	T *addressof(T &arg)
	{
		return reinterpret_cast<T *>(&const_cast<char &>(reinterpret_cast<const volatile char &>(arg)));
	}

	template <class T>
	const T *addressof(const T &&) = delete;

	template <class InputIt, class Size, class NoThrowForwardIt>
	NoThrowForwardIt uninitialized_copy_n(InputIt first, Size count, NoThrowForwardIt d_first)
	{
		using ValueType = typename std::iterator_traits<NoThrowForwardIt>::value_type;
		NoThrowForwardIt current = d_first;
		try
		{
			for (Size i = 0; i < count; ++i, (void)++current, ++first)
			{
				::new (static_cast<void *>(std::addressof(*current))) ValueType(*first);
			}
			return current;
		}
		catch (...)
		{
			for (; d_first != current; ++d_first)
			{
				d_first->~ValueType();
			}
			throw;
		}
	}

	template <class ExecutionPolicy, class ForwardIt, class Size, class NoThrowForwardIt>
	NoThrowForwardIt uninitialized_copy_n(ExecutionPolicy &&policy, ForwardIt first, Size count, NoThrowForwardIt d_first)
	{
		return uninitialized_copy_n(first, count, d_first);
	}

	template <class ForwardIt, class Size, class T>
	ForwardIt uninitialized_fill_n(ForwardIt first, Size count, const T &value)
	{
		using V = typename std::iterator_traits<ForwardIt>::value_type;
		ForwardIt current = first;
		try
		{
			for (; count > 0; ++current, (void)--count)
				::new (static_cast<void *>(std::addressof(*current))) V(value);
			return current;
		}
		catch (...)
		{
			for (; first != current; ++first)
				first->~V();
			throw;
		}
	}

	template <class ExecutionPolicy, class ForwardIt, class Size, class T>
	ForwardIt uninitialized_fill_n(ExecutionPolicy &&policy, ForwardIt first, Size count, const T &value)
	{
		return uninitialized_fill_n(first, count, value);
	}

	template <class Ptr>
	struct pointer_traits
	{
		using pointer = Ptr;
		using element_type = typename Ptr::element_type;
		using difference_type = typename Ptr::difference_type;

		template <class U>
		using rebind = typename Ptr::template rebind<U>;

		static pointer pointer_to(element_type &r) noexcept
		{
			return Ptr::pointer_to(r);
		}
	};

	template <class T>
	struct pointer_traits<T *>
	{
		using pointer = T *;
		using element_type = T;
		using difference_type = std::ptrdiff_t;

		template <class U>
		using rebind = U *;

		static pointer pointer_to(element_type &r) noexcept
		{
			return std::addressof(r);
		}
	};

	template <class Pointer, class SizeType = std::size_t>
	struct allocation_result
	{
		Pointer ptr;
		SizeType count;
	};

	template <class Alloc>
	struct allocator_traits
	{
		typedef Alloc allocator_type;
		typedef typename Alloc::value_type value_type;
		typedef typename Alloc::pointer pointer;
		typedef typename Alloc::const_pointer const_pointer;
		// typedef typename Alloc::void_pointer void_pointer;
		// typedef typename Alloc::const_void_pointer const_void_pointer;
		// typedef typename std::pointer_traits<pointer>::rebind<void> void_pointer;
		// typedef typename std::pointer_traits<pointer>::rebind<const void> const_void_pointer;
		typedef typename Alloc::difference_type difference_type;
		typedef typename Alloc::size_type size_type;
		// typedef typename Alloc::propagate_on_container_copy_assignment propagate_on_container_copy_assignment;
		typedef typename std::false_type propagate_on_container_copy_assignment;
		typedef typename Alloc::propagate_on_container_move_assignment propagate_on_container_move_assignment;
		typedef typename std::false_type propagate_on_container_swap;
		typedef typename Alloc::is_always_equal is_always_equal;

		template <class T>
		using rebind_alloc = typename Alloc::template rebind<T>::other;
		template <class T>
		using rebind_traits = allocator_traits<rebind_alloc<T>>;

		[[nodiscard]] static constexpr pointer allocate(Alloc &a, size_type n)
		{
			return a.allocate(n);
		}

		// [[nodiscard]] static constexpr pointer allocate(Alloc &a, size_type n, const_void_pointer hint)
		// {
		// 	return a.allocate(n, hint);
		// }

		[[nodiscard]] static constexpr std::allocation_result<pointer, size_type> allocate_at_least(Alloc &a, size_type n)
		{
			return a.allocate_at_least(n);
		}

		static constexpr void deallocate(Alloc &a, pointer p, size_type n)
		{
			a.deallocate(p, n);
		}

		template <class T, class... Args>
		static constexpr void construct(Alloc &a, T *p, Args &&...args)
		{
			std::construct_at(p, std::forward<Args>(args)...);
		}

		template <class T>
		static constexpr void destroy(Alloc &a, T *p)
		{
			std::destroy_at(p);
		}

		static constexpr size_type max_size(const Alloc &a)
		{
			return a.max_size();
		}

		static constexpr Alloc select_on_container_copy_construction(const Alloc &a)
		{
			return a;
		}
	};

	template <class T>
	struct allocator
	{
	public:
		typedef T value_type;
		typedef T *pointer;
		typedef const T *const_pointer;
		typedef T &reference;
		typedef const T &const_reference;
		typedef std::size_t size_type;
		typedef std::ptrdiff_t difference_type;
		typedef std::true_type propagate_on_container_move_assignment;
		typedef std::true_type is_always_equal;

		template <class U>
		struct rebind
		{
			typedef allocator<U> other;
		};

		allocator() {}
		allocator(const allocator &other) {}
		template <class U>
		allocator(const allocator<U> &other) {}
		~allocator() {}

		pointer allocate(size_type n, const void *hint = 0)
		{
			return static_cast<pointer>(::operator new(n * sizeof(T)));
		}

		std::allocation_result<T *, std::size_t> allocate_at_least(std::size_t n)
		{
			return {static_cast<T *>(::operator new(n * sizeof(T))), n};
		}

		void deallocate(T *p, std::size_t n)
		{
			::operator delete(p);
		}

		pointer address(reference x) const { return &x; }
		const_pointer address(const_reference x) const { return &x; }
	};

	template <class T>
	struct default_delete
	{
		constexpr default_delete() noexcept = default;

		template <class U>
		constexpr default_delete(const default_delete<U> &d) noexcept {}

		constexpr void operator()(T *ptr) const { delete ptr; }
	};

	template <class T>
	struct default_delete<T[]>
	{
		constexpr default_delete() noexcept = default;

		template <class U>
		constexpr default_delete(const default_delete<U[]> &d) noexcept {}

		template <class U>
		constexpr void operator()(U *ptr) const { delete[] ptr; }
	};

	template <class T, class Deleter = std::default_delete<T>>
	class unique_ptr
	{
	public:
		using pointer = T *; // std::remove_reference<Deleter>::type::pointer;
		using element_type = T;
		using deleter_type = Deleter;

	private:
		pointer _ptr;

	public:
#pragma region Constructors

		constexpr unique_ptr() noexcept : _ptr(nullptr) {}

		constexpr unique_ptr(std::nullptr_t) noexcept : _ptr(nullptr) {}

		constexpr explicit unique_ptr(pointer p) noexcept : _ptr(p) {}

		// constexpr unique_ptr(pointer p, /* TODO */ d1) noexcept : _ptr(p) {}

		// constexpr unique_ptr(pointer p, /* TODO */ d2) noexcept : _ptr(p) {}

		constexpr unique_ptr(unique_ptr &&u) noexcept : _ptr(u.release()) {}

		template <class U, class E>
		constexpr unique_ptr(unique_ptr<U, E> &&u) noexcept : _ptr(u.release()) {}

		unique_ptr(const unique_ptr &) = delete;

		~unique_ptr()
		{
			if (_ptr == nullptr)
				return;
			Deleter d;
			d(_ptr);
		}

		constexpr unique_ptr &operator=(unique_ptr &&r) noexcept
		{
			reset(r.release());
			return *this;
		}

		template <class U, class E>
		constexpr unique_ptr &operator=(unique_ptr<U, E> &&r) noexcept
		{
			reset(r.release());
			return *this;
		}

		constexpr unique_ptr &operator=(std::nullptr_t) noexcept
		{
			reset();
			return *this;
		}

		unique_ptr &operator=(const unique_ptr &) = delete;

#pragma endregion Constructors

#pragma region Modifiers

		constexpr pointer release() noexcept
		{
			pointer p = _ptr;
			_ptr = nullptr;
			return p;
		}

		constexpr void reset(pointer ptr = pointer()) noexcept
		{
			Deleter d;
			d(_ptr);
			_ptr = ptr;
		}

		void swap(unique_ptr &other) noexcept
		{
			pointer tmp = _ptr;
			_ptr = other._ptr;
			other._ptr = tmp;
		}

#pragma endregion Modifiers

#pragma region Observers

		constexpr pointer get() const noexcept { return _ptr; }
		constexpr Deleter &get_deleter() noexcept { return _ptr; }
		constexpr const Deleter &get_deleter() const noexcept { return _ptr; }
		constexpr explicit operator bool() const noexcept { return get() != nullptr; }

#pragma endregion Observers

#pragma region Element Access

		constexpr typename std::add_lvalue_reference<T>::type operator*() const noexcept(noexcept(*std::declval<pointer>())) { return *_ptr; }
		constexpr pointer operator->() const noexcept { return _ptr; }

#pragma endregion Element Access
	};

	template <class T, class Deleter>
	class unique_ptr<T[], Deleter>
	{
	public:
		using pointer = T *; // std::remove_reference<Deleter>::type::pointer;
		using element_type = T;
		using deleter_type = Deleter;

	private:
		pointer _ptr;

	public:
#pragma region Constructors

		constexpr unique_ptr() noexcept : _ptr(nullptr) {}

		constexpr unique_ptr(std::nullptr_t) noexcept : _ptr(nullptr) {}

		template <class U>
		constexpr explicit unique_ptr(U p) noexcept : _ptr(p) {}

		// template <class U>
		// constexpr unique_ptr(U p, /* TODO */ d1) noexcept : _ptr(p) {}

		// template <class U>
		// constexpr unique_ptr(U p, /* TODO */ d2) noexcept : _ptr(p) {}

		constexpr unique_ptr(unique_ptr &&u) noexcept : _ptr(u.release()) {}

		template <class U, class E>
		constexpr unique_ptr(unique_ptr<U, E> &&u) noexcept : _ptr(u.release()) {}

		unique_ptr(const unique_ptr &) = delete;

		~unique_ptr()
		{
			if (_ptr == nullptr)
				return;
			Deleter d;
			d(_ptr);
		}

		constexpr unique_ptr &operator=(unique_ptr &&r) noexcept
		{
			reset(r.release());
			return *this;
		}

		template <class U, class E>
		constexpr unique_ptr &operator=(unique_ptr<U, E> &&r) noexcept
		{
			reset(r.release());
			return *this;
		}

		constexpr unique_ptr &operator=(std::nullptr_t) noexcept
		{
			reset();
			return *this;
		}

		unique_ptr &operator=(const unique_ptr &) = delete;

#pragma endregion Constructors

#pragma region Modifiers

		constexpr pointer release() noexcept
		{
			pointer p = _ptr;
			_ptr = nullptr;
			return p;
		}

		template <class U>
		constexpr void reset(U ptr) noexcept
		{
			Deleter d;
			d(_ptr);
			_ptr = ptr;
		}

		constexpr void reset(std::nullptr_t = nullptr) noexcept
		{
			Deleter d;
			d(_ptr);
			_ptr = nullptr;
		}

		void swap(unique_ptr &other) noexcept
		{
			pointer tmp = _ptr;
			_ptr = other._ptr;
			other._ptr = tmp;
		}

#pragma endregion Modifiers

#pragma region Observers

		constexpr pointer get() const noexcept { return _ptr; }
		constexpr Deleter &get_deleter() noexcept { return _ptr; }
		constexpr const Deleter &get_deleter() const noexcept { return _ptr; }
		constexpr explicit operator bool() const noexcept { return get() != nullptr; }

#pragma endregion Observers

#pragma region Element Access

		constexpr T &operator[](std::size_t i) const { return _ptr[i]; }

#pragma endregion Element Access
	};

	template <class T, class... Args>
	std::enable_if_t<!std::is_array<T>::value, std::unique_ptr<T>>
	make_unique(Args &&...args)
	{
		return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
	}

	template <class T>
	std::enable_if_t<detail::is_unbounded_array_v<T>, std::unique_ptr<T>>
	make_unique(std::size_t n)
	{
		return std::unique_ptr<T>(new std::remove_extent_t<T>[n]());
	}

	template <class T, class... Args>
	std::enable_if_t<detail::is_bounded_array_v<T>> make_unique(Args &&...) = delete;

	template <class T>
		requires(!std::is_array_v<T>)
	std::unique_ptr<T> make_unique_for_overwrite()
	{
		return std::unique_ptr<T>(new T);
	}

	template <class T>
		requires std::is_unbounded_array_v<T>
	std::unique_ptr<T> make_unique_for_overwrite(std::size_t n)
	{
		return std::unique_ptr<T>(new std::remove_extent_t<T>[n]);
	}

	template <class T, class... Args>
		requires std::is_bounded_array_v<T>
	void make_unique_for_overwrite(Args &&...) = delete;

	template <class T1, class D1, class T2, class D2>
	constexpr bool operator==(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return x.get() == y.get(); }

	template <class T1, class D1, class T2, class D2>
	bool operator<(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y)
	{
		return std::less<typename std::common_type<typename unique_ptr<T1, D1>::pointer, typename unique_ptr<T2, D2>::pointer>::type>()(x.get(), y.get());
	}

	template <class T1, class D1, class T2, class D2>
	bool operator<=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return !(y < x); }

	template <class T1, class D1, class T2, class D2>
	bool operator>(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return y < x; }

	template <class T1, class D1, class T2, class D2>
	bool operator>=(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y) { return !(x < y); }

	// operator<=>(const unique_ptr<T1, D1> &x, const unique_ptr<T2, D2> &y);

	template <class T, class D>
	constexpr bool operator==(const unique_ptr<T, D> &x, std::nullptr_t) noexcept { return !x; }

	template <class T, class D>
	constexpr bool operator<(const unique_ptr<T, D> &x, std::nullptr_t) { return std::less<typename unique_ptr<T, D>::pointer>()(x.get(), nullptr); }

	template <class T, class D>
	constexpr bool operator<(std::nullptr_t, const unique_ptr<T, D> &y) { return std::less<typename unique_ptr<T, D>::pointer>()(nullptr, y.get()); }

	template <class T, class D>
	constexpr bool operator<=(const unique_ptr<T, D> &x, std::nullptr_t) { return !(nullptr < x); }

	template <class T, class D>
	constexpr bool operator<=(std::nullptr_t, const unique_ptr<T, D> &y) { return !(y < nullptr); }

	template <class T, class D>
	constexpr bool operator>(const unique_ptr<T, D> &x, std::nullptr_t) { return nullptr < x; }

	template <class T, class D>
	constexpr bool operator>(std::nullptr_t, const unique_ptr<T, D> &y) { return y < nullptr; }

	template <class T, class D>
	constexpr bool operator>=(const unique_ptr<T, D> &x, std::nullptr_t) { return !(x < nullptr); }

	template <class T, class D>
	constexpr bool operator>=(std::nullptr_t, const unique_ptr<T, D> &y) { return !(nullptr < y); }

	// operator<=>(const unique_ptr<T, D> &x, std::nullptr_t);

	// template <class CharT, class Traits, class Y, class D>
	// std::basic_ostream<CharT, Traits> &operator<<(std::basic_ostream<CharT, Traits> &os, const std::unique_ptr<Y, D> &p)
	// {
	// 	return os << p.get();
	// }

	template <class T, class D>
	void swap(std::unique_ptr<T, D> &lhs, std::unique_ptr<T, D> &rhs) noexcept
	{
		lhs.swap(rhs);
	}

	template <class T, class Alloc>
	struct uses_allocator : std::integral_constant<bool, false>
	{
	};

	template <class T, class Alloc>
	constexpr bool uses_allocator_v = uses_allocator<T, Alloc>::value;

	struct allocator_arg_t
	{
		explicit allocator_arg_t() = default;
	};

	constexpr std::allocator_arg_t allocator_arg{};

	template <class T>
	class weak_ptr;

	template <class T>
	class shared_ptr
	{
	private:
		struct control_block_base
		{
			long ref_count;
			virtual void destroy() = 0;
			virtual void *get_ptr() const = 0;
			control_block_base() : ref_count(1) {}
			virtual ~control_block_base() = default;
		};

		template <class Y, class Deleter>
		struct control_block_impl : control_block_base
		{
			Y *ptr;
			Deleter deleter;
			void destroy() override { deleter(ptr); }
			void *get_ptr() const override { return ptr; }
			control_block_impl(Y *p, Deleter d) : ptr(p), deleter(d) {}
			~control_block_impl() override {}
		};

		struct control_block_default : control_block_base
		{
			T *ptr;
			void destroy() override { delete ptr; }
			void *get_ptr() const override { return ptr; }
			control_block_default(T *p) : ptr(p) {}
			~control_block_default() override {}
		};

		template <class Y, class Deleter, class Alloc>
		struct control_block_alloc : control_block_base
		{
			Y *ptr;
			Deleter deleter;
			Alloc alloc;
			void destroy() override { deleter(ptr); }
			void *get_ptr() const override { return ptr; }
			control_block_alloc(Y *p, Deleter d, Alloc a) : ptr(p), deleter(d), alloc(a) {}
			~control_block_alloc() override {}

			void *operator new(std::size_t sz, Alloc &a)
			{
				using AllocTraits = std::allocator_traits<Alloc>;
				return AllocTraits::allocate(a, sz);
			}

			void operator delete(void *p, std::size_t sz)
			{
				::operator delete(p);
			}
		};

		control_block_base *cb;

	public:
		using weak_type = std::weak_ptr<T>;
		using element_type = std::remove_extent_t<T>;

		constexpr shared_ptr() noexcept : cb(nullptr) {}
		constexpr shared_ptr(std::nullptr_t) noexcept : cb(nullptr) {}

		template <class Y>
		explicit shared_ptr(Y *ptr) : cb(ptr ? new control_block_default(ptr) : nullptr) {}

		template <class Y, class Deleter>
		shared_ptr(Y *ptr, Deleter d) : cb(ptr ? new control_block_impl<Y, Deleter>(ptr, d) : nullptr) {}

		template <class Deleter>
		shared_ptr(std::nullptr_t ptr, Deleter d) : cb(nullptr) {}

		template <class Y, class Deleter, class Alloc>
		shared_ptr(Y *ptr, Deleter d, Alloc alloc)
			: cb(ptr ? new(alloc) control_block_alloc<Y, Deleter, Alloc>(ptr, d, alloc) : nullptr) {}

		template <class Deleter, class Alloc>
		shared_ptr(std::nullptr_t ptr, Deleter d, Alloc alloc) : cb(nullptr) {}

		template <class Y>
		shared_ptr(const shared_ptr<Y> &r, element_type *ptr) noexcept : cb(r.cb)
		{
			if (cb)
				++cb->ref_count;
		}

		template <class Y>
		shared_ptr(shared_ptr<Y> &&r, element_type *ptr) noexcept : cb(r.cb) { r.cb = nullptr; }

		shared_ptr(const shared_ptr &r) noexcept : cb(r.cb)
		{
			if (cb)
				++cb->ref_count;
		}

		template <class Y>
		shared_ptr(const shared_ptr<Y> &r) noexcept : cb(r.cb)
		{
			if (cb)
				++cb->ref_count;
		}

		shared_ptr(shared_ptr &&r) noexcept : cb(r.cb) { r.cb = nullptr; }

		template <class Y>
		shared_ptr(shared_ptr<Y> &&r) noexcept : cb(r.cb) { r.cb = nullptr; }

		template <class Y>
		explicit shared_ptr(const std::weak_ptr<Y> &r) : cb(nullptr) { /* Not implemented */ }

		template <class Y, class Deleter>
		shared_ptr(std::unique_ptr<Y, Deleter> &&r) : cb(r.get() ? new control_block_impl<Y, Deleter>(r.release(), Deleter()) : nullptr) {}

		~shared_ptr()
		{
			if (cb)
			{
				if (--cb->ref_count == 0)
				{
					cb->destroy();
					delete cb;
				}
			}
		}

		shared_ptr &operator=(const shared_ptr &r) noexcept
		{
			if (this != &r)
			{
				if (cb && --cb->ref_count == 0)
				{
					cb->destroy();
					delete cb;
				}
				cb = r.cb;
				if (cb)
					++cb->ref_count;
			}
			return *this;
		}

		template <class Y>
		shared_ptr &operator=(const shared_ptr<Y> &r) noexcept
		{
			if (cb && --cb->ref_count == 0)
			{
				cb->destroy();
				delete cb;
			}
			cb = r.cb;
			if (cb)
				++cb->ref_count;
			return *this;
		}

		shared_ptr &operator=(shared_ptr &&r) noexcept
		{
			if (this != &r)
			{
				if (cb && --cb->ref_count == 0)
				{
					cb->destroy();
					delete cb;
				}
				cb = r.cb;
				r.cb = nullptr;
			}
			return *this;
		}

		template <class Y>
		shared_ptr &operator=(shared_ptr<Y> &&r) noexcept
		{
			if (cb && --cb->ref_count == 0)
			{
				cb->destroy();
				delete cb;
			}
			cb = r.cb;
			r.cb = nullptr;
			return *this;
		}

		template <class Y, class Deleter>
		shared_ptr &operator=(std::unique_ptr<Y, Deleter> &&r)
		{
			reset(r.get(), Deleter());
			r.release();
			return *this;
		}

		void reset() noexcept
		{
			if (cb && --cb->ref_count == 0)
			{
				cb->destroy();
				delete cb;
			}
			cb = nullptr;
		}

		template <class Y>
		void reset(Y *ptr)
		{
			reset();
			if (ptr)
				cb = new control_block_default(ptr);
		}

		template <class Y, class Deleter>
		void reset(Y *ptr, Deleter d)
		{
			reset();
			if (ptr)
				cb = new control_block_impl<Y, Deleter>(ptr, d);
		}

		template <class Y, class Deleter, class Alloc>
		void reset(Y *ptr, Deleter d, Alloc alloc)
		{
			reset();
			if (ptr)
				cb = new (alloc) control_block_alloc<Y, Deleter, Alloc>(ptr, d, alloc);
		}

		void swap(shared_ptr &r) noexcept
		{
			control_block_base *tmp = cb;
			cb = r.cb;
			r.cb = tmp;
		}

		element_type *get() const noexcept { return cb ? static_cast<element_type *>(cb->get_ptr()) : nullptr; }
		T &operator*() const noexcept { return *get(); }
		T *operator->() const noexcept { return get(); }
		element_type &operator[](std::ptrdiff_t idx) const { return get()[idx]; }
		long use_count() const noexcept { return cb ? cb->ref_count : 0; }
		explicit operator bool() const noexcept { return cb != nullptr; }

		template <class Y>
		bool owner_before(const shared_ptr<Y> &other) const noexcept { return cb < other.cb; }

		template <class Y>
		bool owner_before(const std::weak_ptr<Y> &other) const noexcept { return cb < other.cb; }
	};

	template <class T, class... Args>
	shared_ptr<T> make_shared(Args &&...args) { return shared_ptr<T>(new T(std::forward<Args>(args)...)); }

	template <class T>
	shared_ptr<T> make_shared(std::size_t N) { return shared_ptr<T>(new T[N]); }

	template <class T>
	shared_ptr<T> make_shared() { return shared_ptr<T>(new T); }

	template <class T>
	shared_ptr<T> make_shared(std::size_t N, const std::remove_extent_t<T> &u) { return shared_ptr<T>(new T[N](u)); }

	template <class T>
	shared_ptr<T> make_shared(const std::remove_extent_t<T> &u) { return shared_ptr<T>(new T(u)); }

	template <class T>
	shared_ptr<T> make_shared_for_overwrite() { return shared_ptr<T>(new T); }

	template <class T>
	shared_ptr<T> make_shared_for_overwrite(std::size_t N) { return shared_ptr<T>(new T[N]); }

	template <class T, class Alloc, class... Args>
	shared_ptr<T> allocate_shared(const Alloc &alloc, Args &&...args)
	{
		using AllocTraits = std::allocator_traits<Alloc>;
		using U = typename std::remove_extent<T>::type;
		Alloc a = alloc;
		U *ptr = AllocTraits::allocate(a, 1);
		try
		{
			AllocTraits::construct(a, ptr, std::forward<Args>(args)...);
			return shared_ptr<T>(ptr, [a](U *p) mutable
								 {
				AllocTraits::destroy(a, p);
				AllocTraits::deallocate(a, p, 1); }, a);
		}
		catch (...)
		{
			AllocTraits::deallocate(a, ptr, 1);
			throw;
		}
	}

	template <class T, class Alloc>
	shared_ptr<T> allocate_shared(const Alloc &alloc, std::size_t N)
	{
		using AllocTraits = std::allocator_traits<Alloc>;
		using U = typename std::remove_extent<T>::type;
		Alloc a = alloc;
		U *ptr = AllocTraits::allocate(a, N);
		try
		{
			for (std::size_t i = 0; i < N; ++i)
				AllocTraits::construct(a, ptr + i);
			return shared_ptr<T>(ptr, [a, N](U *p) mutable
								 {
				for (std::size_t i = 0; i < N; ++i)
					AllocTraits::destroy(a, p + i);
				AllocTraits::deallocate(a, p, N); }, a);
		}
		catch (...)
		{
			AllocTraits::deallocate(a, ptr, N);
			throw;
		}
	}

	template <class T, class Alloc>
	shared_ptr<T> allocate_shared(const Alloc &alloc)
	{
		return allocate_shared<T>(alloc);
	}

	template <class T, class Alloc>
	shared_ptr<T> allocate_shared(const Alloc &alloc, std::size_t N, const std::remove_extent_t<T> &u)
	{
		using AllocTraits = std::allocator_traits<Alloc>;
		using U = typename std::remove_extent<T>::type;
		Alloc a = alloc;
		U *ptr = AllocTraits::allocate(a, N);
		try
		{
			for (std::size_t i = 0; i < N; ++i)
				AllocTraits::construct(a, ptr + i, u);
			return shared_ptr<T>(ptr, [a, N](U *p) mutable
								 {
				for (std::size_t i = 0; i < N; ++i)
					AllocTraits::destroy(a, p + i);
				AllocTraits::deallocate(a, p, N); }, a);
		}
		catch (...)
		{
			AllocTraits::deallocate(a, ptr, N);
			throw;
		}
	}

	template <class T, class Alloc>
	shared_ptr<T> allocate_shared(const Alloc &alloc, const std::remove_extent_t<T> &u)
	{
		return allocate_shared<T>(alloc, 1, u);
	}

	template <class T, class Alloc>
	shared_ptr<T> allocate_shared_for_overwrite(const Alloc &alloc)
	{
		using AllocTraits = std::allocator_traits<Alloc>;
		using U = typename std::remove_extent<T>::type;
		Alloc a = alloc;
		U *ptr = AllocTraits::allocate(a, 1);
		return shared_ptr<T>(ptr, [a](U *p) mutable
							 { AllocTraits::deallocate(a, p, 1); }, a);
	}

	template <class T, class Alloc>
	shared_ptr<T> allocate_shared_for_overwrite(const Alloc &alloc, std::size_t N)
	{
		using AllocTraits = std::allocator_traits<Alloc>;
		using U = typename std::remove_extent<T>::type;
		Alloc a = alloc;
		U *ptr = AllocTraits::allocate(a, N);
		return shared_ptr<T>(ptr, [a, N](U *p) mutable
							 { AllocTraits::deallocate(a, p, N); }, a);
	}

	template <class T, class U>
	std::shared_ptr<T> static_pointer_cast(const std::shared_ptr<U> &r) noexcept
	{
		auto p = static_cast<typename std::shared_ptr<T>::element_type *>(r.get());
		return std::shared_ptr<T>{r, p};
	}

	template <class T, class U>
	std::shared_ptr<T> static_pointer_cast(std::shared_ptr<U> &&r) noexcept
	{
		auto p = static_cast<typename std::shared_ptr<T>::element_type *>(r.get());
		return std::shared_ptr<T>{r, p};
	}

	template <class T, class U>
	std::shared_ptr<T> dynamic_pointer_cast(const std::shared_ptr<U> &r) noexcept
	{
		if (auto p = dynamic_cast<typename std::shared_ptr<T>::element_type *>(r.get()))
			return std::shared_ptr<T>{r, p};
		else
			return std::shared_ptr<T>{};
	}

	template <class T, class U>
	std::shared_ptr<T> dynamic_pointer_cast(std::shared_ptr<U> &&r) noexcept
	{
		if (auto p = dynamic_cast<typename std::shared_ptr<T>::element_type *>(r.get()))
			return std::shared_ptr<T>{r, p};
		else
			return std::shared_ptr<T>{};
	}

	template <class T, class U>
	std::shared_ptr<T> const_pointer_cast(const std::shared_ptr<U> &r) noexcept
	{
		auto p = const_cast<typename std::shared_ptr<T>::element_type *>(r.get());
		return std::shared_ptr<T>{r, p};
	}

	template <class T, class U>
	std::shared_ptr<T> const_pointer_cast(std::shared_ptr<U> &&r) noexcept
	{
		auto p = const_cast<typename std::shared_ptr<T>::element_type *>(r.get());
		return std::shared_ptr<T>{r, p};
	}

	template <class T, class U>
	std::shared_ptr<T> reinterpret_pointer_cast(const std::shared_ptr<U> &r) noexcept
	{
		auto p = reinterpret_cast<typename std::shared_ptr<T>::element_type *>(r.get());
		return std::shared_ptr<T>{r, p};
	}

	template <class T, class U>
	std::shared_ptr<T> reinterpret_pointer_cast(std::shared_ptr<U> &&r) noexcept
	{
		auto p = reinterpret_cast<typename std::shared_ptr<T>::element_type *>(r.get());
		return std::shared_ptr<T>{r, p};
	}

	template <class Deleter, class T>
	Deleter *get_deleter(const std::shared_ptr<T> &p) noexcept { return p.cb ? &p.cb->deleter : nullptr; }

	template <class T, class U>
	bool operator==(const std::shared_ptr<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return lhs.get() == rhs.get(); }

	template <class T, class U>
	bool operator!=(const std::shared_ptr<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return !(lhs == rhs); }

	// template <class T, class U>
	// bool operator<(const std::shared_ptr<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return std::less<V>()(lhs.get(), rhs.get()); }

	template <class T, class U>
	bool operator>(const std::shared_ptr<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return rhs < lhs; }

	template <class T, class U>
	bool operator<=(const std::shared_ptr<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return !(rhs < lhs); }

	template <class T, class U>
	bool operator>=(const std::shared_ptr<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return !(lhs < rhs); }

	// template <class T, class U>
	// std::strong_ordering operator<=>(const std::shared_ptr<T> &lhs, const std::shared_ptr<U> &rhs) noexcept { return std::compare_three_way{}(x.get(), y.get()); }

	template <class T>
	bool operator==(const std::shared_ptr<T> &lhs, std::nullptr_t) noexcept { return !lhs; }

	template <class T>
	bool operator==(std::nullptr_t, const std::shared_ptr<T> &rhs) noexcept { return !rhs; }

	template <class T>
	bool operator!=(const std::shared_ptr<T> &lhs, std::nullptr_t) noexcept { return (bool)lhs; }

	template <class T>
	bool operator!=(std::nullptr_t, const std::shared_ptr<T> &rhs) noexcept { return (bool)rhs; }

	// template <class T>
	// bool operator<(const std::shared_ptr<T> &lhs, std::nullptr_t) noexcept { return std::less<std::shared_ptr<T>::element_type *>()(lhs.get(), nullptr); }

	// template <class T>
	// bool operator<(std::nullptr_t, const std::shared_ptr<T> &rhs) noexcept { return std::less<std::shared_ptr<T>::element_type *>()(nullptr, rhs.get()); }

	template <class T>
	bool operator>(const std::shared_ptr<T> &lhs, std::nullptr_t) noexcept { return nullptr < lhs; }

	template <class T>
	bool operator>(std::nullptr_t, const std::shared_ptr<T> &rhs) noexcept { return rhs < nullptr; }

	template <class T>
	bool operator<=(const std::shared_ptr<T> &lhs, std::nullptr_t) noexcept { return !(nullptr < lhs); }

	template <class T>
	bool operator<=(std::nullptr_t, const std::shared_ptr<T> &rhs) noexcept { return !(rhs < nullptr); }

	template <class T>
	bool operator>=(const std::shared_ptr<T> &lhs, std::nullptr_t) noexcept { return !(lhs < nullptr); }

	template <class T>
	bool operator>=(std::nullptr_t, const std::shared_ptr<T> &rhs) noexcept { return !(nullptr < rhs); }

	// template <class T>
	// std::strong_ordering operator<=>(const std::shared_ptr<T> &lhs, std::nullptr_t) noexcept { return std::compare_three_way{}(x.get(), static_cast<std::shared_ptr<T>::element_type*>(nullptr)); }

	// template <class T, class U, class V>
	// std::basic_ostream<U, V> &operator<<(std::basic_ostream<U, V> &os, const std::shared_ptr<T> &ptr) { return os << ptr.get(); }

	template <class T>
	void swap(std::shared_ptr<T> &lhs, std::shared_ptr<T> &rhs) noexcept { lhs.swap(rhs); }

	// template <class T>
	// struct std::atomic<std::shared_ptr<T>>;

	template <class T>
	struct hash<std::shared_ptr<T>>;
}