#pragma once
#include <iostream>
#include <atomic>
#include <vector>

using namespace std;

template<typename T>
struct Node
{
    T data;	//数据
    atomic_bool hasData; //是否有数据
};

template<typename T>
class LockFreeQueue
{
public:
    LockFreeQueue(int size = 1024)
        :msg(size)
    {
        r_index = 0;
        w_index = 0;
    };
    bool enqueue(T& value);  // 入队列
    bool dequeue(T& value);  // 出队列

private:
    vector<Node<T>> msg;	// 消息队列
    atomic<size_t> r_index; // 读索引(不考虑溢出情况)
    atomic<size_t> w_index; // 写索引(不考虑溢出情况)
};

template<typename T>
bool LockFreeQueue<T>::enqueue(T& value)
{
    size_t l_w_index = w_index.load(std::memory_order_relaxed);
    Node<T>* node = NULL;

    // CAS比较是否和预期一致，一致则对写索引递增1，不一致则重试
    do
    {
        //队列是否已满
        if (l_w_index >= r_index.load(std::memory_order_relaxed) + msg.size()) {
            return false;
        }

        // 判断是否有数据
        size_t index = l_w_index % msg.size();
        node = &msg[index];
        if (node->hasData.load(std::memory_order_relaxed))
        {
            return false;
        }
    } while (!w_index.compare_exchange_weak(l_w_index, l_w_index + 1, std::memory_order_relaxed));

    //写数据
    node->data = std::move(value);//左值转右值，避免拷贝带来的浪费
    node->hasData.store(true);

    return true;
}

template<typename T>
bool LockFreeQueue<T>::dequeue(T& value)
{
    size_t l_r_index = r_index.load(std::memory_order_relaxed);;
    Node<T>* node = NULL;

    // CAS比较是否和预期一致，一致则对读索引递增1，不一致则重试
    do
    {
        //队列是否为空
        if (l_r_index > w_index.load(std::memory_order_relaxed))
        {
            return false;
        }

        // 判断是否有数据
        size_t index = l_r_index % msg.size();
        node = &msg[index];
        if (!node->hasData.load(std::memory_order_relaxed))
        {
            return false;
        }
    } while (!r_index.compare_exchange_weak(l_r_index, l_r_index + 1, std::memory_order_relaxed));

    //读数据
    value = std::move(node->data);
    node->hasData.store(false);

    return true;
}