Compare-and-exchange conditionally replaces an atomic value. It compares the current value with an expected value and stores a desired value only when they match. It returns true if the store happened. On failure, it returns false and updates the expected argument with the atomic value, giving the caller a starting point for another attempt. section 5.2.3
C++ provides compare_exchange_weak() and compare_exchange_strong(). The weak form can fail even when the values match; this is a spurious failure, and the atomic value remains unchanged. Use the weak form in a retry loop when such failures are acceptable. Unlike exchange(), which replaces the value and returns its old value, compare-exchange makes replacement conditional. section 5.2.3
bool expected=false; extern atomic<bool> b; // set somewhere else while(!b.compare_exchange_weak(expected,true) && !expected);
The loop retries a weak compare-exchange while its expected value remains false. A failed call updates expected, so the condition can distinguish a retry from a changed value. section 5.2.3
A lock-free stack push shows why the comparison matters. First construct a node and set its next pointer to the current head. A plain assignment to head would risk discarding another thread’s push if that thread changed head in the meantime. Compare-exchange instead installs the new node only if head still equals the value saved in next. On failure, it writes the current head into next; the loop tries again without a separate reload. The node’s data must be ready before head points to it, because another thread may then read it. section 7.2.1
Listing 7.2. Implementing push() without locks
template<typename T>
class lock_free_stack
{
private:
struct node
{
T data;
node* next;
node(T const& data_): #1
data(data_)
{}
};
std::atomic<node*> head;
public:
void push(T const& data)
{
node* const new_node=new node(data); #2
new_node->next=head.load(); #3
while(!head.compare_exchange_weak(new_node->next,new_node)); #4
}
};
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":8,\"ch\":71},{\"line\":8,\"ch\":73}],[{\"line\":16,\"ch\":71},{\"line\":16,\"ch\":73}],[{\"line\":17,\"ch\":71},{\"line\":17,\"ch\":73}],[{\"line\":18,\"ch\":71},{\"line\":18,\"ch\":73}]]"}
!@%STYLE%@!
Follow push() from node construction through the head load and retry loop. In the compare-exchange call, new_node->next is both the expected head and the place where a failed attempt receives the updated head. section 7.2.1
A successful head update is not, by itself, a complete stack implementation. A pop example can return data without reclaiming its removed node, leaving a memory leak. Compare-exchange solves the conditional-update race; surrounding code must still handle the rest of the data structure’s behavior. section 7.2.1
