Single-Считыватель-Single-Writer для Win32

Question

Hallo,

Ищу очередь Single-Считыватель-Single-Writer для 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(&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