#ifndef stack_h
#define stack_h 1

#include <atomic>
#include <optional>
#include <boost/lockfree/detail/tagged_ptr.hpp>

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

    void push(T t)
    {
        pointer new_node(new node{pointer{}, std::move(t)}); // new throws std::bad_alloc on failure
        while (true)
        {
            auto old_head = head.load(std::memory_order_relaxed);
            new_node->next = old_head;
            pointer new_head = pointer(new_node.get_ptr(), old_head.get_tag() + 1);
            if (head.compare_exchange_weak(old_head,
                                           new_head,
                                           std::memory_order_release,
                                           std::memory_order_relaxed))
                break;
        }
    }

    std::optional<T> pop()
    {
        while (true)
        {
            pointer old_head = head.load(std::memory_order_acquire);
            if (old_head)
            {
                pointer new_head = pointer(old_head->next.get_ptr(), old_head.get_tag() + 1);
                if (head.compare_exchange_weak(old_head,
                                               new_head,
                                               std::memory_order_release,
                                               std::memory_order_relaxed))
                {
                    T data = std::move(old_head->data); // move data out of the node
                    delete old_head.get_ptr();
                    return data;
                }
            }
            else
            {
                return std::nullopt; // stack is empty
            }
        }
    }

private:
    struct node;
    using pointer = typename boost::lockfree::detail::tagged_ptr<node>;

    struct node
    {
        pointer next;
        T data;
    };

    std::atomic<pointer> head{pointer{nullptr, 0}};
};

#endif // stack_h