#include <iostream>
#include <atomic>
#include <array>
#include <thread>

template <typename T>
struct node {
    T      value;
    node*  next{nullptr};
};

typedef node<int> node_type;

std::atomic<node_type*> _begin;

node_type* get() {
    node_type* b = _begin;

    while (!_begin.compare_exchange_weak(b, b->next))
        ;

    return b;
}

void give(node_type* v) {
    v->next = _begin;

    while (!_begin.compare_exchange_weak(v->next, v))
        ;
}

void get_and_give() {
    for (int i = 0; i < 1000000; ++i) {
        auto n = get();

        give(n);
    }
}

int main(int argc, const char * argv[])
{
    std::array<node_type, 4> _nodes;

    for (auto & i : _nodes)
        give(&i);

    std::thread t1(get_and_give);
    std::thread t2(get_and_give);
    std::thread t3(get_and_give);

    get_and_give();

    t1.join();
    t2.join();
    t3.join();

    return 0;
}