#include
template
LockFreeQueue() : head_(new Node), tail_(head_.load()) {}
~LockFreeQueue() {
while (Node* const old_head = head_->next_) {
delete head_;
head_ = old_head;
}
delete head_;
}
void push(const T& value) {
auto new_node = std::make_unique<Node>(value);
Node* old_tail = tail_.exchange(new_node.get(), std::memory_order_acq_rel);
old_tail->next_.store(new_node.release(), std::memory_order_release);
size_.fetch_add(1, std::memory_order_release);
}
bool try_pop(T& value) {
Node* old_head = head_.load(std::memory_order_relaxed);
for (;;) {
Node* const new_head = old_head->next_.load();
if (new_head == nullptr) {
return false;
}
if (head_.compare_exchange_weak(old_head, new_head, std::memory_order_acquire)) {
value = new_head->value_;
size_.fetch_sub(1, std::memory_order_release);
delete old_head;
return true;
}
}
}
bool empty() const {
return size_.load(std::memory_order_acquire) == 0;
}
private:
struct Node {
T value_;
std::atomic<Node*> next_;
Node() : next_(nullptr) {}
explicit Node(const T& value) : value_(value), next_(nullptr) {}
};
std::atomic<Node*> head_;
std::atomic<Node*> tail_;
std::atomic<size_t> size_{0};
};