#include
template
LockFreeQueue() {
Node* dummy = new Node();
head_ = tail_ = dummy;
}
~LockFreeQueue() {
while (Node* const old_head = head_) {
head_ = old_head->next_;
delete old_head;
}
}
void push(const T& value) {
Node* new_node = new Node(value);
tail_->next_ = new_node;
tail_ = new_node;
size_.fetch_add(1, std::memory_order_release);
}
bool try_pop(T& value) {
Node* old_head = head_;
for (;;) {
Node* const new_head = old_head->next_;
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_;
Node* next_;
explicit Node(const T& value) : value_(value), next_(nullptr) {}
Node() : next_(nullptr) {}
};
Node* head_;
std::atomic<Node*> tail_;
std::atomic<size_t> size_{0};
};
