#ifndef tagged_ptr_h
#define tagged_ptr_h

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

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

    void push(T t)
    {
        node *p = new node{pointer(nullptr, 0), t};
        pointer old_head = head.load(std::memory_order_relaxed);
        do
        {
            p->next = old_head;
        } while (!head.compare_exchange_weak(
            old_head, pointer(p, old_head.get_tag() + 1),
            std::memory_order_release, std::memory_order_relaxed));
    }

    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_acquire,
                                               std::memory_order_relaxed))
                {
                    T data = old_head->data;
                    delete old_head.get_ptr();
                    return std::optional<T>(data);
                }
            }
            else
            {
                return std::nullopt;
            }
        }
    }

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 // tagged_ptr_h