C++无锁队列

前言

经典面试题，C++基于CAS操作实现无锁队列。本文提供了一种基于静态数组的无锁队列实现，约40行。

Code

#include <cstddef>
#include <atomic>
#include <vector>

using namespace std;

template<typename T>
class RingBuffer {
private:
    vector<T> data;
    size_t cap;
    // write保证多线程并发写的准确性
    std::atomic<size_t> head{0}, tail{0}, write{0};
public:
    RingBuffer() = delete;

    RingBuffer(const RingBuffer &) = delete; // 删除拷贝构造函数

    RingBuffer &operator=(const RingBuffer &) = delete;

    RingBuffer &operator=(const RingBuffer &) volatile = delete;

    explicit RingBuffer(size_t n) : cap{n} {
        data.resize(n);
    }

    bool push(const T &val) {
        size_t t, w;
        do {
            t = tail.load();
            if ((t + 1) % cap == head.load()) {
                return false;
            }
        } while (!tail.compare_exchange_weak(t, (t + 1) % cap));
        data[t] = val;
        do {
            w = t;
        } while (!write.compare_exchange_weak(w, (w + 1) % cap));
        return true;
    }

    bool pop(T &val) {
        size_t h;
        do {
            h = head.load();
            if (h == write.load()) {
                return false;
            }
            val = data[h];
        } while (!head.compare_exchange_strong(h, (h + 1) % cap));
        return true;
    }
};