//----------------------------------------------------
// abql.cc: array based queuing lock
//----------------------------------------------------

#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 array_based_queuing_lock
{
public:
    array_based_queuing_lock(size_t n) : flags(n), tail(0), next(0)
    {
        for (auto &i : flags) i.flag.store(false);
        flags[0].flag.store(true);
    }

    void lock(size_t id)
    {
        flags[id].flag.store(true, std::memory_order_release);
        size_t index = tail.fetch_add(1, std::memory_order_acq_rel);
        while (index != next.load(std::memory_order_acquire))
            std::this_thread::yield();
    }

    void unlock(size_t id)
    {
        size_t index = next.load(std::memory_order_relaxed);
        flags[id].flag.store(false, std::memory_order_release);
        next.store(index + 1, std::memory_order_release);
    }

private:
    struct padding
    {
        alignas(std::hardware_destructive_interference_size /
                sizeof(std::atomic<bool>)) std::atomic<bool> flag;
    };

    std::vector<padding> flags;
    std::atomic<size_t> tail;
    std::atomic<size_t> next;
} c(N);

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

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(id);
        if (!stop) seccion_critica();
        c.unlock(id);
    }
}

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

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();
}

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