C ++ 11 free stack lock

Question

I read C ++ Concurrency in Anthony Williams action and don’t understand its implementation of push class lock_free_stack .

Why is atomic load not in a while loop? The reason he gave:

Therefore, you do not need to reboot your head every time through a loop, because the compiler does this for you.

But I do not get the picture. Can someone shed some light on this?

 template<typename T> class lock_free_stack { private: struct node { T data; node* next; node(T const& data_) : data(data_) {} }; std::atomic<node*> head; public: void push(T const& data) { node* const new_node=new node(data); new_node->next=head.load(); while(!head.compare_exchange_weak(new_node->next,new_node)); } }; 

Answer 1

The key is in the compare_exchange_weak interface, which in this case takes 2 arguments. The first is a reference to the expected value, and the second is the desired value. If the current atom value is not equal to the expected input, it will return false and the expected input will be set to the current value.

So, in this case, setting new_node->next = head . Then, saying that if head is still equal to new_node->next , change it to head . If this is no longer a value, it uses the link to new_node->next to give it the current value of head . Since each iteration of the loop that fails also replaces new_node->next with the current value of head , there is no reading to duplicate this in the body of the loop.

Answer 2

From the documentation of compare_exchange_weak :

Atomically compares the value stored in * with the value expected, and if they are equal, (performs a read-modify-write operation). Otherwise, it loads the value stored in * this into the expected one (the load operation is performed).

As you can see, otherwise the actual head value is loaded into the expected one.