#ifndef nothrow_h
#define nothrow_h

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

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

    void push(T t)
    {
        pointer new_node{new (std::nothrow) node{pointer{}, t}};
        if (!new_node.ptr)
            std::terminate();
        do
        {
            new_node.ptr->next = head.load(std::memory_order_relaxed);
            new_node.tag = new_node.ptr->next.tag + 1;
        } while (!head.compare_exchange_weak(new_node.ptr->next, new_node,
                                             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.ptr)
            {
                pointer new_head =
                    pointer{old_head.ptr->next.ptr, old_head.tag + 1};
                if (head.compare_exchange_weak(old_head, new_head,
                                               std::memory_order_acquire,
                                               std::memory_order_relaxed))
                {
                    T data = old_head.ptr->data;
                    delete old_head.ptr;
                    return std::optional<T>(data);
                }
            }
            else
            {
                return std::nullopt;
            }
        }
    }

private:
    struct node;

    struct alignas(sizeof(node *) + sizeof(size_t)) pointer
    {
        node *ptr;  // puntero al nodo
        size_t tag; // etiqueta para evitar el problema ABA
    };

    struct node
    {
        pointer next; // puntero al siguiente nodo
        T data;
    };

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

#endif // nothrow_h