Anthony Williams, Section 7.2.1, lists the stack lock implementation in a book called "C ++ Concurrency in Action":
template <typename T>
class lock_free_stack {
struct node {
shared_ptr<T> data_;
node* next_;
node(const T& data) : data_(make_shared(data)) {}
};
atomic<node*> head_;
public:
void push(const T& data)
{
node* new_node = new node(data);
new_node->next_ = head_.load();
while(!head.compare_exchange_weak(new_node->next_, new_node));
}
shared_ptr<T> pop()
{
node* old_head = head_.load();
while (old_head &&
!head_.compare_exchange_weak(old_head, head_->next_));
return old_head ? old_head->data_ : shared_ptr<T>();
}
};
Then, in section 7.2.2, the author says: "... at pop () we chose a node leak to avoid a race condition where one thread deletes a node while the other thread still contains a pointer to it, something like dereferencing. "
1) I do not understand why such a scenario can occur and why the following pop () function will cause a race condition:
shared_ptr<T> pop()
{
node* old_head = head_.load();
while (old_head &&
!head_.compare_exchange_weak(old_head, head_->next_));
shared_ptr<T> res;
if (old_head) {
res.swap(old_head->data);
delete old_head;
return res;
} else {
return {};
}
}
2) How is it that for several threads that call pop () at the same time, the variable "old_head" can point to the same node object after line (3)?