Win32 的单读取器单写入器队列

Question

你好，

我正在寻找 Win32 的单读单写队列。

最好的问候，弗里德里希

Answer 1

Waitfree 基于单生产者/单消费者链表的队列：
http://www.1024cores.net/home/lock -free-algorithms/queues/unbounded-spsc-queue

Answer 2

这是我的解决方案，基于 http://www.drdobbs.com/cpp/210604448文章。但我不确定它是否真的是线程安全的。好吧，这不是一个重新查看网站，但如果有什么问题请告诉我。每个人都可以自由使用这段代码，malloc 部分应该与无锁内存池分配器交换。

#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(÷r, 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