#ifndef cas_h
#define cas_h

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

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

    void push(T t)
    {
        node *new_node = new node{head.load(std::memory_order_relaxed), t};
        while (!head.compare_exchange_weak(new_node->next, new_node,
                                           std::memory_order_release,
                                           std::memory_order_relaxed));
    }

    std::optional<T> pop()
    {
        node *old_head = head.load(std::memory_order_acquire);
        while (old_head &&
               !head.compare_exchange_weak(old_head, old_head->next,
                                           std::memory_order_acquire,
                                           std::memory_order_relaxed));
        if (old_head)
        {
            T data = old_head->data;
            delete old_head;
            return std::optional<T>(data);
        }
        else
        {
            return std::nullopt;
        }
    }

private:
    struct node
    {
        node *next;
        T data;
    };

    std::atomic<node *> head = nullptr;
};

#endif // cas_h