title: C++ Lock free producer/consumer queue
body: <p>I was looking at the sample code for a lock-free queue at:</p>
  
  <p><a href="http://drdobbs.com/high-performance-computing/210604448?pgno=2" rel="nofollow noreferrer">http://drdobbs.com/high-performance-computing/210604448?pgno=2</a></p>
  
  <p>(Also reference in many SO questions such as <a href="https://stackoverflow.com/questions/1164023/is-there-a-production-ready-lock-free-queue-or-hash-implementation-in-c">Is there a production ready lock-free queue or hash implementation in C++</a>)</p>
  
  <p>This looks like it should work for a single producer/consumer, although there are a number of typos in the code. I've updated the code to read as shown below, but it's crashing on me. Anybody have suggestions why?</p>
  
  <p>In particular, should divider and last be declared as something like:</p>
  
  <pre><code>atomic&lt;Node *&gt; divider, last;    // shared
  </code></pre>
  
  <p>I don't have a compiler supporting C++0x on this machine, so perhaps that's all I need...</p>
  
  <pre><code>// Implementation from http://drdobbs.com/high-performance-computing/210604448
  // Note that the code in that article (10/26/11) is broken.
  // The attempted fixed version is below.
  
  template &lt;typename T&gt;
  class LockFreeQueue {
  private:
      struct Node {
          Node( T val ) : value(val), next(0) { }
          T value;
          Node* next;
      };
      Node *first,      // for producer only
      *divider, *last;    // shared
  public:
      LockFreeQueue()
      {
          first = divider = last = new Node(T()); // add dummy separator
      }
      ~LockFreeQueue()
      {
          while( first != 0 )    // release the list
          {
              Node* tmp = first;
              first = tmp-&gt;next;
              delete tmp;
          }
      }
      void Produce( const T&amp; t )
      {
          last-&gt;next = new Node(t);    // add the new item
          last = last-&gt;next;      // publish it
  
          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-&gt;next-&gt;value; // C: copy it back
              divider = divider-&gt;next;      // D: publish that we took it
              return true;                  // and report success
          }
          return false;                   // else report empty
      }
  };
  </code></pre>
  
  <p>I wrote the following code to test this. Main (not shown) just calls TestQ().</p>
  
  <pre><code>#include "LockFreeQueue.h"
  
  const int numThreads = 1;
  std::vector&lt;LockFreeQueue&lt;int&gt; &gt; q(numThreads);
  
  void *Solver(void *whichID)
  {
      int id = (long)whichID;
      printf("Thread %d initialized\n", id);
      int result = 0;
      do {
          if (q[id].Consume(result))
          {
              int y = 0;
              for (int x = 0; x &lt; result; x++)
              { y++; }
              y = 0;
          }
      } while (result != -1);
      return 0;
  }
  
  
  void TestQ()
  {
      std::vector&lt;pthread_t&gt; threads;
      for (int x = 0; x &lt; numThreads; x++)
      {
          pthread_t thread;
          pthread_create(&amp;thread, NULL, Solver, (void *)x);
          threads.push_back(thread);
      }
      for (int y = 0; y &lt; 1000000; y++)
      {
          for (unsigned int x = 0; x &lt; threads.size(); x++)
          {
              q[x].Produce(y);
          }
      }
      for (unsigned int x = 0; x &lt; threads.size(); x++)
      {
          q[x].Produce(-1);
      }
      for (unsigned int x = 0; x &lt; threads.size(); x++)
          pthread_join(threads[x], 0);    
  }
  </code></pre>
  
  <hr>
  
  <p>Update: It ends up that the crash is being caused by the queue declaration:</p>
  
  <pre><code>std::vector&lt;LockFreeQueue&lt;int&gt; &gt; q(numThreads);
  </code></pre>
  
  <p>When I change this to be a simple array, it runs fine. (I implemented a version with locks and it was crashing too.) I see that the destructor is being called immediate after the constructor, resulting in doubly-freed memory. But, does anyone know WHY the destructor would be called immediately with a std::vector?</p>