Single-Reader-Single-Writer Queue for Win32

Question

Hallo,

I am looking for a Single-Reader-Single-Writer queue for Win32.

Best regards, Friedrich

Answer 1

Here is my solution, based on the http://www.drdobbs.com/cpp/210604448 article. But I am not sure if it is really thread-safe. Well, this is not a re-view site, but if there is something wrong please tell me. Everybody is free to use this code, the malloc part should be exchanged with a lock-free memory-pool allocator.

#ifndef QUEUE_HPP_INCLUDED
#define QUEUE_HPP_INCLUDED

#include <Windows.h>

/// @brief A single reader, single writer queue
template <typename T>
class LockFreeQueue {
private:
    /// @brief Node of the queue
    struct Node {
        Node( T* val ) : value(val), next(0) { }
        T* value;
        Node* next;
    };

    Node* first; // for producer only
    Node* divider; // shared
    Node* last; // shared

    // no copy
    LockFreeQueue& operator=(const LockFreeQueue&);
    LockFreeQueue(const LockFreeQueue&);
public:
    /// @brief Constructor
    LockFreeQueue()
    :   first(new Node(0)),
        divider(first),
        last(first)
    {
    }

    /// @brief Destructor
    ~LockFreeQueue() 
    {
        while( first != 0 ) 
        {   
            // release the list
            Node* tmp = first;
            first = tmp->next;
            delete tmp;
        }
    }

    /// @brief Pushes to the end of the queue
    /// @warning Must only be called from the producer
    void push_back(T* t) 
    {
        last->next = new Node(t);   // add the new item
        // publish it
        InterlockedExchangePointer(&last, last->next); // last = last->next;
        while(first != divider)
        {   // trim unused nodes
            Node* tmp = first;
            first = first->next;
            delete tmp;
        }
    }

    /// @brief Pop an element from the front
    /// @warning Must only be called from the consumer
    /// @return true If a node was popped
    /// @return false If queue is empty
    bool pop_front(T* result ) 
    {
        if(divider != last) 
        {
            // if queue is nonempty
            result = divider->next->value;  // C: copy it back
            // D: publish that we took it
            InterlockedExchangePointer(&divider, divider->next); // divider = divider->next;
            return true; // and report success
        }
        return false; // else report empty
    }

    /// @brief Points to the element at the front
    /// @warning Must only be called from the consumer
    /// @return 0 if queue is empty
    /// @return Pointer to the first node
    T* front()
    {
        T* t = 0;
        if(divider != last) 
        {
            t = divider->next->value;
        }
        return t;
    }
};

#endif // QUEUE_HPP_INCLUDED

Answer 2

Waitfree single-producer/single-consumer linked-list-based queue: http://www.1024cores.net/home/lock-free-algorithms/queues/unbounded-spsc-queue