title: Two threads deleting from a lock-free stack
body: <p>I am referring to page 185 and 186 in C++ Concurrency in Action. They give the following code as a method for a lock-free stack:</p>
  
  <pre><code>void push(T const&amp; data){
      node* const new_node = new node(data);
      new_node-&gt;next=head.load();
      while(!head.compare_exchange_weak(new_node-&gt;next, new_node));
  }
  </code></pre>
  
  <p>and on P186 it says the following:</p>
  
  <blockquote>
    <p>Of course, now that you have a means of adding data to the stack, you
    need a way of getting it off again. On the face of it, this is quite
    simple:</p>
    
    <ol>
    <li>Read the current value of <code>head</code></li>
    <li>Read <code>head-&gt;next</code></li>
    <li>Set <code>head</code> to <code>head-&gt;next</code></li>
    <li>Return the data from the retrieved node</li>
    <li>Delete the retrieved node</li>
    </ol>
    
    <p>However, in the presence of multiple threads, this isn't so simple. If
    there are two threads removing items from the stack they both might
    read the same value of <code>head</code> at step 1. If one thread then proceeds
    all the way through to step 5 before the other gets to step 2, the
    second thread will be dereferencing a dangling pointer.</p>
  </blockquote>
  
  <p>I thought that compare_exchange_weak() could be used to essentially complete step 2 and 3 atomically and the second thread could see that <code>head-&gt;next</code> is no longer valid?</p>
  
  <p>I am surprised we cannot use CAS to solve the above problem??</p>