Existe-t-il une implémentation en C++ d'une file d'attente ou d'un hachage sans verrou, prête à être produite ?

Question

J'ai pas mal cherché sur Google une file d'attente sans verrou en C++. J'ai trouvé du code et quelques essais - mais rien que je puisse compiler. Un hash sans verrou serait également le bienvenu.

RÉSUMÉ : Jusqu'à présent, je n'ai pas de réponse positive. Il n'y a pas de bibliothèque "prête pour la production", et étonnamment aucune des bibliothèques existantes n'est conforme à l'API des conteneurs STL.

Answer 1

J'ai écrit ceci à un moment donné, probablement en 2010, je suis sûr que j'ai été aidé par différentes références. Il s'agit de Multi-Producer Single Consumer.

template <typename T>
class MPSCLockFreeQueue 
{
private:
    struct Node 
    {
        Node( T val ) : value(val), next(NULL) { }
        T value;
        Node* next;
    };
    Node * Head;               
    __declspec(align(4)) Node * InsertionPoint;  //__declspec(align(4)) forces 32bit alignment this must be changed for 64bit when appropriate.

public:
    MPSCLockFreeQueue() 
    {
        InsertionPoint = new Node( T() );
        Head = InsertionPoint;
    }
    ~MPSCLockFreeQueue() 
    {
        // release the list
        T result;
        while( Consume(result) ) 
        {   
            //The list should be cleaned up before the destructor is called as there is no way to know whether or not to delete the value.
            //So we just do our best.
        }
    }

    void Produce( const T& t ) 
    {
        Node * node = new Node(t);
        Node * oldInsertionPoint = (Node *) InterLockedxChange((volatile void **)&InsertionPoint,node);
        oldInsertionPoint->next = node;
    }

    bool Consume( T& result ) 
    {
        if (Head->next)
        {
            Node * oldHead = Head;
            Head = Head->next;
            delete oldHead;
            result = Head->value;
            return true;
        }       
        return false;               // else report empty
    }

};