123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 |
- #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;
- }
|