#include
template
LockFreeQueue() : head_(new Node), tail_(head_.load()) {}
void push(const T &item) {
std::unique_ptr<Node> new_node(new Node);
new_node->data = item;
while (true) {
Node *tail = tail_.load();
Node *next = tail->next.load();
if (tail == tail_.load()) {
if (next == nullptr) {
if (tail->next.compare_exchange_weak(next, new_node.get())) {
tail_.compare_exchange_weak(tail, new_node.get());
new_node.release();
return;
}
} else {
tail_.compare_exchange_weak(tail, next);
}
}
}
}
bool try_pop(T &item) {
while (true) {
Node *head = head_.load();
Node *tail = tail_.load();
Node *next = head->next.load();
if (head == head_.load()) {
if (head == tail) {
if (next == nullptr) {
return false;
}
tail_.compare_exchange_weak(tail, next);
} else {
item = next->data;
if (head_.compare_exchange_weak(head, next)) {
// delete head; 不需要手动释放内存，unique_ptr 会自动释放
return true;
}
}
}
}
}
private:
struct Node {
T data;
std::atomic<Node *> next{nullptr};
Node() {}
Node(const Node&) = delete;
Node& operator=(const Node&) = delete;
};
std::atomic<Node *> head_;
std::atomic<Node *> tail_;
};
