eonix/gblibstdc++/include/memory

#ifndef __GBLIBCPP_MEMORY__
#define __GBLIBCPP_MEMORY__

#include <cstddef>
#include <type_traits>
#include <utility>

namespace std {

template <typename T>
constexpr T* addressof(T& arg) noexcept
{
    return __builtin_addressof(arg);
}

// template <typename T>
// constexpr enable_if_t<is_function_v<remove_reference_t<T>>, T*>
// addressof(T& arg) noexcept
// {
//     return &arg;
// }

// template <typename T>
// constexpr enable_if_t<!is_function_v<remove_reference_t<T>>, T*>
// addressof(T& arg) noexcept
// {
//     return reinterpret_cast<T*>(
//         &const_cast<char&>(
//             reinterpret_cast<const volatile char&>(arg)
//         )
//     );
// }

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

namespace __helpers {

template <typename Ptr, typename = void>
struct pointer_difference_type
{ using type = std::ptrdiff_t; };

template <typename Ptr>
struct pointer_difference_type<Ptr,
    std::void_t<typename Ptr::difference_type>>
{ using type = typename Ptr::difference_type; };

template <typename Ptr>
using pointer_difference_type_t =
    typename pointer_difference_type<Ptr>::type;

template <typename Base, typename T>
struct rebind;

template <template <typename, typename...> typename Template,
    typename NewType, typename OldType, typename... Args>
struct rebind<Template<OldType, Args...>, NewType> {
    using type = Template<NewType, Args...>;
};

template <typename Ptr, typename T, typename = void>
struct try_rebind { using type = typename rebind<Ptr, T>::type; };

template <typename Ptr, typename T>
struct try_rebind<Ptr, T,
    std::void_t<typename Ptr::template rebind<T>>> {
    using type = typename Ptr::template rebind<T>;
};

template <typename Ptr, typename = void>
struct pointer_element {};

template <typename Ptr>
struct pointer_element<Ptr, std::enable_if_t<
    std::is_same_v<void, std::void_t<typename Ptr::element_type>>
>> { using type = typename Ptr::element_type; };

template <template <typename, typename...> typename Template,
    typename T, typename... Args>
struct pointer_element<Template<T, Args...>, void>
{ using type = T; };

template <typename Ptr, typename = void>
struct pointer_traits_impl {};

template <typename Ptr>
struct pointer_traits_impl<Ptr,
    std::void_t<typename pointer_element<Ptr>::type>> {
    using pointer = Ptr;
    using element_type = typename pointer_element<Ptr>::type;
    using difference_type = pointer_difference_type_t<Ptr>;

    template <typename U>
    using rebind = typename try_rebind<Ptr, U>::type;

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

template <typename T>
struct pointer_traits_impl<T*, void> {
    using pointer = T*;
    using element_type = T;
    using difference_type = std::ptrdiff_t;

    template <typename U>
    using rebind = U*;

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

} // namespace __helpers

template <typename Ptr>
struct pointer_traits : public __helpers::pointer_traits_impl<Ptr> {};

namespace __helpers {

template <typename Alloc, typename = void>
struct allocator_pointer
{ using type = typename Alloc::value_type*; };

template <typename Alloc>
struct allocator_pointer<Alloc,
    std::void_t<typename Alloc::pointer>>
{ using type = typename Alloc::pointer; };

template <typename Alloc>
using allocator_pointer_t =
    typename allocator_pointer<Alloc>::type;


template <typename Alloc, typename Pointer, typename = void>
struct allocator_const_pointer {
    using type = typename std::pointer_traits<Pointer>::template
        rebind<const typename Alloc::value_type>;
};

template <typename Alloc, typename Pointer>
struct allocator_const_pointer<Alloc, Pointer,
    std::void_t<typename Alloc::const_pointer>>
{ using type = typename Alloc::const_pointer; };

template <typename Alloc, typename Pointer>
using allocator_const_pointer_t =
    typename allocator_const_pointer<Alloc, Pointer>::type;


template <typename Alloc, typename Pointer, typename = void>
struct allocator_void_pointer {
    using type = typename std::pointer_traits<Pointer>::template
        rebind<void>;
};

template <typename Alloc, typename Pointer>
struct allocator_void_pointer<Alloc, Pointer,
    std::void_t<typename Alloc::void_pointer>>
{ using type = typename Alloc::void_pointer; };

template <typename Alloc, typename Pointer>
using allocator_void_pointer_t =
    typename allocator_void_pointer<Alloc, Pointer>::type;


template <typename Alloc, typename Pointer, typename = void>
struct allocator_const_void_pointer {
    using type = typename std::pointer_traits<Pointer>::template
        rebind<const void>;
};

template <typename Alloc, typename Pointer>
struct allocator_const_void_pointer<Alloc, Pointer,
    std::void_t<typename Alloc::const_void_pointer>>
{ using type = typename Alloc::const_void_pointer; };

template <typename Alloc, typename Pointer>
using allocator_const_void_pointer_t =
    typename allocator_const_void_pointer<Alloc, Pointer>::type;


template <typename Alloc, typename = void>
struct allocator_difference_type
{ using type = std::ptrdiff_t; };
template <typename Alloc>
struct allocator_difference_type<Alloc,
    std::void_t<typename Alloc::difference_type>>
{ using type = typename Alloc::difference_type; };
template <typename Alloc>
using allocator_difference_type_t =
    typename allocator_difference_type<Alloc>::type;

template <typename Alloc, typename = void>
struct allocator_size_type
{ using type = std::size_t; };
template <typename Alloc>
struct allocator_size_type<Alloc,
    std::void_t<typename Alloc::size_type>>
{ using type = typename Alloc::size_type; };
template <typename Alloc>
using allocator_size_type_t =
    typename allocator_size_type<Alloc>::type;

template <typename Alloc, typename = void>
struct allocator_prop_copy
{ using type = std::false_type; };
template <typename Alloc>
struct allocator_prop_copy<Alloc,
    std::void_t<typename Alloc::propagate_on_container_copy_assignment>>
{ using type = typename Alloc::propagate_on_container_copy_assignment; };
template <typename Alloc>
using allocator_prop_copy_t =
    typename allocator_prop_copy<Alloc>::type;

template <typename Alloc, typename = void>
struct allocator_prop_move
{ using type = std::false_type; };
template <typename Alloc>
struct allocator_prop_move<Alloc,
    std::void_t<typename Alloc::propagate_on_container_move_assignment>>
{ using type = typename Alloc::propagate_on_container_move_assignment; };
template <typename Alloc>
using allocator_prop_move_t =
    typename allocator_prop_move<Alloc>::type;

template <typename Alloc, typename = void>
struct allocator_prop_swap
{ using type = std::false_type; };
template <typename Alloc>
struct allocator_prop_swap<Alloc,
    std::void_t<typename Alloc::propagate_on_container_swap>>
{ using type = typename Alloc::propagate_on_container_swap; };
template <typename Alloc>
using allocator_prop_swap_t =
    typename allocator_prop_swap<Alloc>::type;

template <typename Alloc, typename = void>
struct is_always_equal
{ using type = std::false_type; };
template <typename Alloc>
struct is_always_equal<Alloc,
    std::void_t<typename Alloc::is_always_equal>>
{ using type = typename Alloc::is_always_equal; };
template <typename Alloc>
using is_always_equal_t =
    typename is_always_equal<Alloc>::type;

template <typename Alloc, typename = void>
struct allocator_select_on_copy {
    static constexpr Alloc get(const Alloc& alloc)
    { return alloc; }
};

template <typename Alloc>
struct allocator_select_on_copy<Alloc, std::enable_if_t<
    std::is_same_v<void, std::void_t<decltype(
        std::declval<Alloc>().select_on_container_copy_construction()
    )>> >> {
    static constexpr Alloc get(const Alloc& alloc)
    { return alloc.select_on_container_copy_construction(); }
};

template <typename Allocator, typename T, typename = void>
struct allocator_rebind_type {
    using type = typename rebind<Allocator, T>::type;
};

template <typename Allocator, typename T>
struct allocator_rebind_type<Allocator, T, std::void_t<
    typename Allocator::template rebind<T>::other
>> {
    using type = typename Allocator::template rebind<T>::other;
};

} // namespace __helpers

template <typename T>
struct allocator {
    using value_type = T;
    using propagate_on_container_move_assignment = std::true_type;

    constexpr allocator() noexcept = default;
    constexpr allocator(const allocator& other) noexcept = default;

    template <typename U>
    constexpr allocator(const allocator<U>&) noexcept {}

    constexpr ~allocator() = default;

    // throws std::bad_alloc
    [[nodiscard]] constexpr T* allocate(std::size_t n)
    { return static_cast<T*>(::operator new(n * sizeof(T))); }

    // TODO: check allocated size
    constexpr void deallocate(T* ptr, std::size_t)
    { ::operator delete(ptr); }
};

template <typename T1, typename T2>
constexpr bool operator==(const allocator<T1>&, const allocator<T2>&) noexcept
{ return true; }

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

template <typename T>
constexpr void destroy_at(T* p)
{
    // TODO: destroy array
    p->~T();
}

template <typename Allocator>
struct allocator_traits {
    using allocator_type = Allocator;
    using value_type = typename Allocator::value_type;
    using pointer =
        __helpers::allocator_pointer_t<Allocator>;
    using const_pointer =
        __helpers::allocator_const_pointer_t<Allocator, pointer>;
    using void_pointer =
        __helpers::allocator_void_pointer_t<Allocator, pointer>;
    using const_void_pointer =
        __helpers::allocator_const_void_pointer_t<Allocator, pointer>;
    using difference_type =
        __helpers::allocator_difference_type_t<Allocator>;
    using size_type =
        __helpers::allocator_size_type_t<Allocator>;
    using propagate_on_container_copy_assignment =
        __helpers::allocator_prop_copy_t<Allocator>;
    using propagate_on_container_move_assignment =
        __helpers::allocator_prop_move_t<Allocator>;
    using propagate_on_container_swap =
        __helpers::allocator_prop_swap_t<Allocator>;
    using is_always_equal =
        __helpers::is_always_equal_t<Allocator>;

    template <typename T>
    using rebind_alloc =
        typename __helpers::allocator_rebind_type<Allocator, T>::type;

    [[nodiscard]] static constexpr pointer allocate(Allocator& alloc, size_type n)
    { return alloc.allocate(n); }
    static constexpr void deallocate(Allocator& alloc, pointer p, size_type n)
    { return alloc.deallocate(p, n); }
    template <typename T, typename... Args>
    static constexpr void construct(Allocator&, T* p, Args&&... args)
    { std::construct_at(p, std::forward<Args>(args)...); }
    template <typename T>
    static constexpr void destroy(Allocator&, T* p)
    { std::destroy_at(p); }

    static constexpr Allocator
        select_on_container_copy_construction(const Allocator& alloc)
    { return __helpers::allocator_select_on_copy<Allocator>::get(alloc); }
};

// TODO: weak_ptr
template <typename T>
class shared_ptr {
public:
    using element_type = std::remove_extent_t<T>;
    using pointer = element_type*; // TODO: pointer_traits
    using const_pointer = const element_type*;
    using reference = element_type&;
    using const_reference = const element_type&;

private:
    struct control_block_base {
        std::size_t ref_count;
        std::size_t weak_count;
        pointer ptr;

        constexpr control_block_base(std::size_t ref_count,
            std::size_t weak_count, pointer ptr)
            : ref_count(ref_count), weak_count(weak_count), ptr(ptr) { }

        virtual constexpr ~control_block_base() = default;
        virtual constexpr void do_delete() = 0;
    };

    template <typename Deleter>
    struct control_block : public virtual control_block_base {
        Deleter deleter;
        virtual constexpr ~control_block() = default;

        template <typename UDeleter>
        constexpr control_block(std::size_t ref_count,
            std::size_t weak_count, pointer ptr, UDeleter&& deleter)
            : control_block_base { ref_count, weak_count, ptr }
            , deleter(std::forward<UDeleter>(deleter)) { }

        virtual constexpr void do_delete() override
        {
            if (this->ptr)
                deleter(this->ptr);
            this->ptr = nullptr;
        }
    };

    struct default_control_block : public virtual control_block_base {
        virtual constexpr ~default_control_block() = default;

        constexpr default_control_block(std::size_t ref_count,
            std::size_t weak_count, pointer ptr)
            : control_block_base { ref_count, weak_count, ptr } { }

        virtual constexpr void do_delete() override
        {
            if (this->ptr)
                delete this->ptr;
            this->ptr = nullptr;
        }
    };

    control_block_base* cb { };

    void inc_ref()
    {
        if (cb)
            ++cb->ref_count; // TODO: lock and atomic
    }

    void dec_ref()
    {
        if (cb && --cb->ref_count == 0) {
            cb->do_delete();
            if (cb->weak_count == 0)
                delete cb;
        }
    }

private:
    template <typename Deleter>
    using rebind_allocator = typename std::allocator_traits<Deleter>::template
        rebind_alloc<control_block<Deleter>>;

    template <typename U>
    friend class shared_ptr;

public:
    constexpr shared_ptr() noexcept = default;
    constexpr shared_ptr(std::nullptr_t) noexcept : cb { } { }

    template <typename U>
    __GBLIBCPP_CONSTEXPR
    explicit shared_ptr(U* ptr) // TODO: array type
        : cb(new default_control_block { 1, 0, ptr }) { }

    template <typename U, typename Deleter>
    __GBLIBCPP_CONSTEXPR
    explicit shared_ptr(U* ptr, Deleter d)
        : cb(new control_block<Deleter> { 1, 0, ptr, d }) { }

    template <typename Deleter>
    __GBLIBCPP_CONSTEXPR
    explicit shared_ptr(std::nullptr_t, Deleter d)
        : cb(new control_block<Deleter> { 1, 0, nullptr, d }) { }

    // TODO: what the fuck
    // template <typename U, typename Deleter, typename Allocator>
    // __GBLIBCPP_CONSTEXPR
    // explicit shared_ptr(U* ptr, Deleter d, Allocator alloc)
    // {
    //     cb = std::allocator_traits<
    //         rebind_allocator<Deleter>>::allocate(alloc, 1);

    //     std::allocator_traits<
    //         rebind_allocator<Deleter>>::construct(alloc, cb, 1, 0, ptr, d);
    // }

    // template <typename Deleter, typename Allocator>
    // __GBLIBCPP_CONSTEXPR
    // explicit shared_ptr(std::nullptr_t, Deleter d, Allocator alloc)
    // {
    //     cb = std::allocator_traits<
    //         rebind_allocator<Deleter>>::allocate(alloc, 1);

    //     std::allocator_traits<
    //         rebind_allocator<Deleter>>::construct(alloc, cb, 1, 0, nullptr, d);
    // }

    __GBLIBCPP_CONSTEXPR
    shared_ptr(const shared_ptr& other) noexcept
        : cb(other.cb) { inc_ref(); }

    template <typename U>
    __GBLIBCPP_CONSTEXPR
    shared_ptr(const shared_ptr<U>& other) noexcept
        : cb(other.cb) { inc_ref(); }

    __GBLIBCPP_CONSTEXPR
    shared_ptr(shared_ptr&& other) noexcept
        : cb(std::exchange(other.cb, nullptr)) { }

    template <typename U>
    __GBLIBCPP_CONSTEXPR
    shared_ptr(shared_ptr<U>&& other) noexcept
        : cb(std::exchange(other.cb, nullptr)) { }
    
    // TODO: weak_ptr and unique_ptr

    __GBLIBCPP_CONSTEXPR
    ~shared_ptr() { dec_ref(); }

    __GBLIBCPP_CONSTEXPR
    shared_ptr& operator=(const shared_ptr& other) noexcept
    {
        if (cb != other.cb) {
            dec_ref();
            cb = other.cb;
            inc_ref();
        }
        return *this;
    }

    template <typename U>
    __GBLIBCPP_CONSTEXPR
    shared_ptr& operator=(const shared_ptr<U>& other) noexcept
    {
        if (cb != other.cb) {
            dec_ref();
            cb = other.cb;
            inc_ref();
        }
        return *this;
    }

    __GBLIBCPP_CONSTEXPR
    shared_ptr& operator=(shared_ptr&& other) noexcept
    {
        if (cb != other.cb) {
            dec_ref();
            cb = std::exchange(other.cb, nullptr);
        }
        return *this;
    }

    template <typename U>
    __GBLIBCPP_CONSTEXPR
    shared_ptr& operator=(shared_ptr<U>&& other) noexcept
    {
        if (cb != other.cb) {
            dec_ref();
            cb = std::exchange(other.cb, nullptr);
        }
        return *this;
    }

    __GBLIBCPP_CONSTEXPR
    element_type* get() const noexcept
    { return cb ? cb->ptr : nullptr; }

    __GBLIBCPP_CONSTEXPR
    explicit operator bool() const noexcept
    { return get(); }

    __GBLIBCPP_CONSTEXPR
    T& operator*() const noexcept { return *get(); }
    __GBLIBCPP_CONSTEXPR
    T* operator->() const noexcept { return get(); }
    __GBLIBCPP_CONSTEXPR
    element_type& operator[](std::size_t i) const noexcept { return get()[i]; }

    __GBLIBCPP_CONSTEXPR
    long use_count() const noexcept { return cb ? cb->ref_count : 0; }

    __GBLIBCPP_CONSTEXPR
    bool owner_before(const shared_ptr& other) const noexcept
    { return cb < other.cb; }

    __GBLIBCPP_CONSTEXPR
    void swap(shared_ptr& other) noexcept { std::swap(cb->ptr, other.cb->ptr); }

    __GBLIBCPP_CONSTEXPR
    void reset() noexcept { dec_ref(); cb = nullptr; }

    template <typename U>
    __GBLIBCPP_CONSTEXPR
    void reset(U* ptr) noexcept
    { dec_ref(); cb = new default_control_block { 1, 0, ptr }; }

    template <typename U, typename Deleter>
    __GBLIBCPP_CONSTEXPR
    void reset(U* ptr, Deleter d) noexcept
    { dec_ref(); cb = new control_block<Deleter> { 1, 0, ptr, d }; }

    // TODO: what the fuck
    // template <typename U, typename Deleter, typename Allocator>
    // __GBLIBCPP_CONSTEXPR
    // void reset(U* ptr, Deleter d, Allocator alloc)
    // {
    //     dec_ref();
    //     cb = std::allocator_traits<
    //         rebind_allocator<Deleter>>::allocate(alloc, 1);

    //     std::allocator_traits<
    //         rebind_allocator<Deleter>>::construct(alloc, cb, 1, 0, ptr, d);
    // }
};

// TODO: use only one allocation
// template <typename T, typename... Args>
// std::shared_ptr<T> make_shared(Args&&... args)
// {
//     return std::shared_ptr<T>(new T(std::forward<Args>(args)...));
// }

} // namespace std

#endif