#ifndef rcu_h
#define rcu_h

#include <atomic>
#include <optional>
#include <thread>

// ---------------------------------------------------------------------------
// Implementación mínima de RCU (Read-Copy-Update)
// ---------------------------------------------------------------------------

namespace rcu
{
    // Estado por hilo: cuenta de secciones críticas de lectura anidadas.
    // Se asigna dinámicamente para que sobreviva al exit del hilo sin
    // dejar punteros colgantes en la lista global.
    struct alignas(64) thread_state
    {
        std::atomic<uint64_t> readers{0};
        std::atomic<thread_state *> next{nullptr};
    };

    // Lista enlazada lock-free de todos los estados de hilo registrados.
    inline std::atomic<thread_state *> thread_list{nullptr};

    // RAII: construye un thread_state y lo inserta en la lista global.
    // Intencionadamente no libera la memoria en el destructor para evitar
    // carreras use-after-free en synchronize().
    struct thread_guard
    {
        thread_state *const state;

        thread_guard(): state(new thread_state())
        {
            thread_state *head = thread_list.load(std::memory_order_relaxed);
            do
            {
                state->next.store(head, std::memory_order_relaxed);
            } while (!thread_list.compare_exchange_weak(
                head, state, std::memory_order_release,
                std::memory_order_relaxed));
        }
    };

    // Una instancia por hilo; la primera llamada a read_lock() la
    // inicializa y registra el hilo en la lista global.
    inline thread_local thread_guard tg;

    // Entrar en una sección crítica de lectura RCU.
    inline void read_lock()
    {
        tg.state->readers.fetch_add(1, std::memory_order_acquire);
    }

    // Salir de la sección crítica de lectura RCU.
    inline void read_unlock()
    {
        tg.state->readers.fetch_sub(1, std::memory_order_release);
    }

    // Bloquea hasta que todos los lectores activos en el momento de la
    // llamada hayan salido de su sección crítica (período de gracia).
    inline void synchronize()
    {
        // seq_cst garantiza que vemos todos los read_lock() anteriores.
        thread_state *ts = thread_list.load(std::memory_order_seq_cst);
        while (ts)
        {
            while (ts->readers.load(std::memory_order_acquire) > 0)
                std::this_thread::yield();
            ts = ts->next.load(std::memory_order_acquire);
        }
    }

} // namespace rcu

// ---------------------------------------------------------------------------
// Pila no bloqueante protegida con RCU
// ---------------------------------------------------------------------------

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

    // push: no requiere RCU; el nuevo nodo no es visible hasta el CAS.
    void push(T t)
    {
        node *new_node =
            new node{head.load(std::memory_order_relaxed), std::move(t)};
        // compare_exchange_weak actualiza new_node->next si el CAS falla.
        while (!head.compare_exchange_weak(new_node->next, new_node,
                                           std::memory_order_release,
                                           std::memory_order_relaxed));
    }

    // pop: retira el nodo cabeza y lo libera tras el período de gracia.
    std::optional<T> pop()
    {
        // Anunciamos que estamos leyendo antes de cargar head.
        rcu::read_lock();
        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));
        rcu::read_unlock();

        if (old_head)
        {
            T data = std::move(old_head->data);
            // Esperar a que ningún hilo tenga una referencia a old_head.
            rcu::synchronize();
            delete old_head;
            return data;
        }
        return std::nullopt;
    }

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

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

#endif // rcu_h