无锁栈实现原理

本文是用过C++11标准下的原子变量atomic的CAS操作compare_exchange_weak，来实现无锁栈（Lock-free Stack）。

• 通过compare_exchange_weak方法，来实现栈顶元素添加操作的原子性。
• 栈内元素都会由Node数据结构封装，可以规避CAS操作的ABA问题。

无锁栈实现编码

#ifndef LOCK_FREE_STACK_HPP
#define LOCK_FREE_STACK_HPP

#include 

template
class LockFreeStack {
public:
    struct Node {
        Node() : data(nullptr), pre(nullptr) {}
        void reset() { data = nullptr; pre = nullptr;}

        T *data;
        Node* pre;
    };

    LockFreeStack() : count(0), back(nullptr) {}
    ~LockFreeStack() { clear(); }

    void push(const T* data) {
        Node* node = alloc();
        node->data = const_cast(data);
        for (;;) {
            node->pre = back;
            if (back.compare_exchange_weak(node->pre, node, std::memory_order_seq_cst) ) {
                break;
            } else {
                continue;
            }
        }
        ++count;
    }

    T* pop() {
        for (;;) {
            Node* back_node = back;
            if (nullptr == back_node) { return nullptr; }
            Node* second_node = back_node->pre;
            if(!back.compare_exchange_weak(back_node, second_node, std::memory_order_seq_cst)) {
                continue;
            } else {
                --count;
                T* data = back_node->data;
                recycle(back_node);
                return data;
            }
        }
    }
    bool empty() { return (bool)count; }
    int64_t size() { return count; }
    void clear() { while (nullptr != pop()) {}; }

private:
    Node *alloc() { return (new Node()); }
    void recycle(Node *node) { delete node; }

    std::atomic count;
    std::atomic back;
};
#endif