title: Lock-Free Queue with boost::atomic - Am I doing this right?
body: <p><strong>Short version:</strong></p>
  
  <p>I'm trying to replace std::atomic from C++11 used in a lock-free, single producer, single consumer queue implementation from <a href="http://drdobbs.com/parallel/210604448" rel="nofollow">here</a>. How do I replace this with <a href="http://www.chaoticmind.net/~hcb/projects/boost.atomic/" rel="nofollow"><code>boost::atomic</code></a>?</p>
  
  <p><strong>Long version:</strong></p>
  
  <p>I'm trying to get a better performance out of our app with worker threads. Each thread has its own task queue. We have to synchronize using lock before dequeue/enqueue each task. </p>
  
  <p>Then I found Herb Sutter's article on lock-free queue. It seems like an ideal replacement. But the code uses <code>std::atomic</code> from C++11, which I couldn't introduce to the project at this time.</p>
  
  <p>More googling led to some examples, such as <a href="http://www.soa-world.de/echelon/2011/02/a-simple-lock-free-queue-in-c.html" rel="nofollow">this one for Linux (echelon's)</a>, and <a href="http://tinesware.blogspot.com/2009/07/simple-lockfree-queue-c-windows.html" rel="nofollow">this one for Windows (TINESWARE's)</a>. Both use platform's specific constructs such as WinAPI's <code>InterlockedExchangePointer</code>, and GCC's <code>__sync_lock_test_and_set</code>.</p>
  
  <p>I only need to support Windows &amp; Linux so maybe I can get away with some <code>#ifdef</code>s. But I thought it might be nicer to use what <code>boost::atomic</code> provides. Boost Atomic is not part of official Boost library yet. So I downloaded the source from <a href="http://www.chaoticmind.net/~hcb/projects/boost.atomic/" rel="nofollow">http://www.chaoticmind.net/~hcb/projects/boost.atomic/</a> and use the include files with my project.</p>
  
  <p>This is what I get so far:</p>
  
  <pre><code>#pragma once
  
  #include &lt;boost/atomic.hpp&gt;
  
  template &lt;typename T&gt;
  class LockFreeQueue
  {
  private:
      struct Node
      {
          Node(T val) : value(val), next(NULL) { }
          T value;
          Node* next;
      };
      Node* first; // for producer only
      boost::atomic&lt;Node*&gt; divider;  // shared
      boost::atomic&lt;Node*&gt; last; // shared
  
  public:
      LockFreeQueue()
      {
          first = new Node(T());
          divider = first;
          last= first;
      }
  
      ~LockFreeQueue()
      {
          while(first != NULL) // release the list
          {
              Node* tmp = first;
              first = tmp-&gt;next;
              delete tmp;
          }
      }
  
      void Produce(const T&amp; t)
      {
          last.load()-&gt;next = new Node(t); // add the new item
          last = last.load()-&gt;next;
          while(first != divider) // trim unused nodes
          {
              Node* tmp = first;
              first = first-&gt;next;
              delete tmp;
          }
      }
  
      bool Consume(T&amp; result)
      {
          if(divider != last) // if queue is nonempty
          {
              result = divider.load()-&gt;next-&gt;value; // C: copy it back
              divider = divider.load()-&gt;next;
              return true;  // and report success
          }
          return false;  // else report empty
      }
  };
  </code></pre>
  
  <p>Some modifications to note:</p>
  
  <pre><code>boost::atomic&lt;Node*&gt; divider;  // shared
  boost::atomic&lt;Node*&gt; last; // shared
  </code></pre>
  
  <p>and</p>
  
  <pre><code>    last.load()-&gt;next = new Node(t); // add the new item
      last = last.load()-&gt;next;
  </code></pre>
  
  <p>and</p>
  
  <pre><code>        result = divider.load()-&gt;next-&gt;value; // C: copy it back
          divider = divider.load()-&gt;next;
  </code></pre>
  
  <p>Am I applying the load() (and the implicit store()) from boost::atomic correctly right here? Can we say this is equivalent to Sutter's original C++11 lock-free queue?</p>
  
  <p>PS. I studied many of the threads on SO, but none seems to provide an example for boost::atomic &amp; lock-free queue.</p>