Here is a classical attempt to implement a lock-free stack (based on this article). I rewrote it in C++11 and also tried to add memory orders which I would like to confirm to be correct.template<typename T>class stack {    struct node_t final     {        T value;        node_t *next;    };    struct head_t final     {        uintptr_t aba;        node_t *node;        head_t() noexcept :aba(0),node(nullptr)        {}        head_t(node_t* ptr) noexcept :aba(0),node(ptr)        {}    };    static_assert(sizeof(head_t) == 2*sizeof(uintptr_t), Stack head should be 2 pointers size.);    typedef typename std::aligned_storage<sizeof(node_t), std::alignment_of<node_t>::value>::type aligned_node_t;    std::unique_ptr<aligned_node_t[]> buffer_ptr;    node_t *node_buffer;    char cache_padding_1_[64 - sizeof(node_t*)];    std::atomic<head_t> head;    char cache_padding_2_[64 - sizeof(std::atomic<head_t>)];    std::atomic<head_t> free_nodes;    char cache_padding_3_[64 - sizeof(std::atomic<head_t>)];public:    stack(size_t capacity)    {        head.store( head_t(), std::memory_order_relaxed );        // preallocate nodes        buffer_ptr.reset(new aligned_node_t[capacity]);        node_buffer = reinterpret_cast<node_t*>(buffer_ptr.get());        for(size_t i = 0; i < capacity - 1; ++i)        {            node_buffer[i].next = &node_buffer[i + 1];        }        node_buffer[capacity-1].next = nullptr;        free_nodes.store( head_t(node_buffer), std::memory_order_relaxed );    }    template<class U>    bool push(U && data)    {        node_t *node = _pop(free_nodes);        if (node == nullptr)            return false;        node->value = std::forward<U>(data);        _push(head, node);        return true;    }    bool pop(T& data)    {        node_t *node = _pop(head);        if (node == nullptr)            return false;        data = std::move(node->value);        _push(free_nodes, node);        return true;    }private:    node_t* _pop(std::atomic<head_t>& h)    {        head_t next, orig = h.load(std::memory_order_relaxed);        do {            if (orig.node == nullptr)                return nullptr;            next.aba = orig.aba + 1;            next.node = orig.node->next;        } while (!h.compare_exchange_weak(orig, next,                                        std::memory_order_acq_rel,                                        std::memory_order_acquire));        return orig.node;    }    void _push(std::atomic<head_t>& h, node_t* node)    {        head_t next, orig = h.load(std::memory_order_relaxed);        do {            node->next = orig.node;            next.aba = orig.aba + 1;            next.node = node;        } while (!h.compare_exchange_weak(orig, next,                                        std::memory_order_acq_rel,                                        std::memory_order_acquire));    }};
Lock-free bounded stack in C++11
c++;c++11;stack;lock free