Очередь с одним чтением и одной записью для Win32

Привет,

Я ищу очередь Single-Reader-Single-Writer для Win32.

С уважением, Фридрих


person Friedrich    schedule 30.12.2010    source источник


Ответы (2)


Очередь на основе связанного списка с одним производителем/одним потребителем без ожидания: http://www.1024cores.net/home/lock-free-algorithms/queues/unbounded-spsc-queue

person Dmitry Vyukov    schedule 27.01.2011

Вот мое решение, основанное на 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(&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
person Friedrich    schedule 30.12.2010