#ifndef shared_ptr_h
#define shared_ptr_h

#include <atomic>
#include <memory>
#include <optional>

template<typename T> class stack
{
public:
    ~stack() { while (pop()); }

    void push(T t)
    {
        auto p = std::make_shared<node>(head.load(std::memory_order_relaxed),
                                        std::move(t));
        while (!head.compare_exchange_weak(
            p->next, p, std::memory_order_release, std::memory_order_relaxed));
    }

    std::optional<T> pop()
    {
        auto p = head.load(std::memory_order_acquire);
        while (p && !head.compare_exchange_weak(p, p->next,
                                                std::memory_order_release,
                                                std::memory_order_relaxed));
        if (p)
            return std::optional<T>(std::move(p->data));
        else
            return std::nullopt;
    }

private:
    struct node
    {
        std::shared_ptr<node> next;
        T data;
    };

    std::atomic<std::shared_ptr<node>> head = nullptr; // NO LOCKFREE!!!

    // static_assert(std::atomic<std::shared_ptr<node>>::is_always_lock_free,
    //               "std::atomic<std::shared_ptr<node>> is not lock-free!");
};

#endif // shared_ptr_h