//----------------------------------------------------
// mcslock.cc
//----------------------------------------------------

#include <atomic>
#include <iostream>
#include <thread>
#include <vector>

//----------------------------------------------------

using namespace std::literals;

//----------------------------------------------------

const size_t N = 16;
std::atomic<bool> start = false, stop = false;

//----------------------------------------------------

class mcslock
{
private:
    struct node_type
    {
        std::atomic<node_type *> next;
        std::atomic<bool> locked;
    };

    alignas(std::hardware_destructive_interference_size)
        std::atomic<node_type *> tail;
    thread_local static std::unique_ptr<node_type> my_node;

public:
    mcslock() : tail(nullptr) {}

    void lock()
    {
        my_node = std::make_unique<node_type>();
        my_node->locked.store(true, std::memory_order_relaxed);
        node_type *prev =
            tail.exchange(my_node.get(), std::memory_order_acq_rel);

        if (prev != nullptr)
        {
            prev->next.store(my_node.get(), std::memory_order_release);
            while (my_node->locked.load(std::memory_order_acquire))
                std::this_thread::yield();
        }
    }

    void unlock()
    {
        if (my_node->next.load(std::memory_order_acquire) == nullptr)
        {
            node_type *expected = my_node.get();
            if (tail.compare_exchange_strong(
                    expected, nullptr, std::memory_order_release))
            {
                my_node.reset();
                return;
            }

            while (my_node->next.load(std::memory_order_acquire) == nullptr)
                std::this_thread::yield();
        }

        my_node->next.load(std::memory_order_acquire)
            ->locked.store(false, std::memory_order_release);
        my_node.reset();
    }
} c;

thread_local std::unique_ptr<mcslock::node_type> mcslock::my_node = nullptr;

//----------------------------------------------------

void seccion_critica()
{
    std::cout << "[" << std::this_thread::get_id() << "]: ";
    for (size_t i = 0; i < 10; ++i) std::cout << i;
    std::cout << std::endl;
}

//----------------------------------------------------

void hebra(size_t id)
{
    while (!start) std::this_thread::yield();
    while (!stop)
    {
        c.lock();
        if (!stop) seccion_critica();
        c.unlock();
    }
}

//----------------------------------------------------

int main()
{
    std::thread threads[N];

    for (size_t i = 0; i < N; ++i) threads[i] = std::thread(hebra, i);

    start = true;
    std::this_thread::sleep_for(100ms);
    stop = true;

    for (auto &t : threads) t.join();
}

//----------------------------------------------------