Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink > Class Template Reference

C++ implementation of Dmitry Vyukov's lock-free MPSC queue (Intrusive). More...

#include "MPSCQueue.h"

Public Member Functions
	MPSCQueueIntrusive ()
	Constructs a new MPSCQueueIntrusive object.
	~MPSCQueueIntrusive ()
	Destroys the MPSCQueueIntrusive object.
void	Enqueue (T *input)
	Enqueues a new item in the queue.
bool	Dequeue (T *&result)
	Dequeues an item from the queue.

Private Member Functions
	MPSCQueueIntrusive (MPSCQueueIntrusive const &)=delete
	Deleted copy constructor.
MPSCQueueIntrusive &	operator= (MPSCQueueIntrusive const &)=delete
	Deleted copy assignment operator.

Private Attributes
std::aligned_storage_t< sizeof(T), alignof(T)>	_dummy
	Storage for the dummy object.
T *	_dummyPtr
	Pointer to the dummy object.
std::atomic< T * >	_head
	Atomic pointer to the head node of the queue.
std::atomic< T * >	_tail
	Atomic pointer to the tail node of the queue.

Detailed Description

template<typename T, std::atomic< T * > T::* IntrusiveLink>
class Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >

C++ implementation of Dmitry Vyukov's lock-free MPSC queue (Intrusive).

This queue allows multiple producers to enqueue items concurrently, but only one consumer can dequeue items. The queue is lock-free and intrusive, meaning that the enqueued objects must have an atomic link to the next item in the queue.

Template Parameters

T	The type of data that is being enqueued in the queue.
IntrusiveLink	A member pointer to the atomic link used for linking the nodes.

Constructor & Destructor Documentation

MPSCQueueIntrusive() [1/2]

template<typename T , std::atomic< T * > T::* IntrusiveLink>

Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::MPSCQueueIntrusive ( )

inline

Constructs a new MPSCQueueIntrusive object.

Initializes the queue with a dummy node and sets up atomic pointers to the head and tail. The dummy node's atomic link is initialized.

            : _dummyPtr(reinterpret_cast<T*>(std::addressof(_dummy))), _head(_dummyPtr), _tail(_dummyPtr)
        {
            // Initialize the intrusive link in the dummy node
            std::atomic<T*>* dummyNext = new (&(_dummyPtr->*IntrusiveLink)) std::atomic<T*>();
            dummyNext->store(nullptr, std::memory_order_release);
        }

References Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_dummyPtr.

~MPSCQueueIntrusive()

template<typename T , std::atomic< T * > T::* IntrusiveLink>

Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::~MPSCQueueIntrusive ( )

inline

Destroys the MPSCQueueIntrusive object.

Dequeues all items and deletes them.

        {
            T* output;
            while (Dequeue(output))
                delete output;
        }

References Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Dequeue().

MPSCQueueIntrusive() [2/2]

template<typename T , std::atomic< T * > T::* IntrusiveLink>

Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::MPSCQueueIntrusive ( MPSCQueueIntrusive< T, IntrusiveLink > const &  )

privatedelete

Deleted copy constructor.

Member Function Documentation

Dequeue()

template<typename T , std::atomic< T * > T::* IntrusiveLink>

bool Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Dequeue ( T *&  result )

inline

Dequeues an item from the queue.

This function removes the item at the front of the queue and returns it.

Parameters

result

Reference to a pointer where the dequeued item will be stored.

Returns

True if an item was successfully dequeued, false if the queue was empty.

        {
            T* tail = _tail.load(std::memory_order_acquire);
            T* next = (tail->*IntrusiveLink).load(std::memory_order_acquire);
            if (tail == _dummyPtr)
            {
                if (!next)
                    return false;
 
                _tail.store(next, std::memory_order_release);
                tail = next;
                next = (next->*IntrusiveLink).load(std::memory_order_acquire);
            }
 
            if (next)
            {
                _tail.store(next, std::memory_order_release);
                result = tail;
                return true;
            }
 
            T* head = _head.load(std::memory_order_acquire);
            if (tail != head)
                return false;
 
            Enqueue(_dummyPtr);
            next = (tail->*IntrusiveLink).load(std::memory_order_acquire);
            if (next)
            {
                _tail.store(next, std::memory_order_release);
                result = tail;
                return true;
            }
            return false;
        }

References Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_dummyPtr, Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_head, Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_tail, and Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Enqueue().

Referenced by Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::~MPSCQueueIntrusive().

Enqueue()

template<typename T , std::atomic< T * > T::* IntrusiveLink>

void Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Enqueue ( T *  input )

inline

Enqueues a new item in the queue.

This function adds a new item at the head of the queue.

Parameters

input

Pointer to the item to be enqueued.

< Exchange with acquire-release semantics

        {
            // Set the next link to nullptr initially
            (input->*IntrusiveLink).store(nullptr, std::memory_order_release);
            T* prevHead = _head.exchange(input, std::memory_order_acq_rel);  
            (prevHead->*IntrusiveLink).store(input, std::memory_order_release);
        }

References Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_head.

Referenced by Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Dequeue().

operator=()

template<typename T , std::atomic< T * > T::* IntrusiveLink>

MPSCQueueIntrusive & Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::operator= ( MPSCQueueIntrusive< T, IntrusiveLink > const &  )

privatedelete

Deleted copy assignment operator.

Member Data Documentation

_dummy

template<typename T , std::atomic< T * > T::* IntrusiveLink>

std::aligned_storage_t<sizeof(T), alignof(T)> Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_dummy

private

Storage for the dummy object.

_dummyPtr

template<typename T , std::atomic< T * > T::* IntrusiveLink>

T* Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_dummyPtr

private

Pointer to the dummy object.

Referenced by Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Dequeue(), and Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::MPSCQueueIntrusive().

_head

template<typename T , std::atomic< T * > T::* IntrusiveLink>

std::atomic<T*> Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_head

private

Atomic pointer to the head node of the queue.

Referenced by Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Dequeue(), and Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Enqueue().

_tail

template<typename T , std::atomic< T * > T::* IntrusiveLink>

std::atomic<T*> Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::_tail

private

Atomic pointer to the tail node of the queue.

Referenced by Acore::Impl::MPSCQueueIntrusive< T, IntrusiveLink >::Dequeue().

---

The documentation for this class was generated from the following file:

• azerothcore-wotlk/src/common/Threading/MPSCQueue.h