roc::core::MpscQueue< T, OwnershipPolicy, Node > Class Template Reference

Thread-safe lock-free node-based intrusive multi-producer single-consumer queue. More...

#include <mpsc_queue.h>

Inheritance diagram for roc::core::MpscQueue< T, OwnershipPolicy, Node >:

Collaboration diagram for roc::core::MpscQueue< T, OwnershipPolicy, Node >:

Public Types
typedef OwnershipPolicy< T >::Pointer	Pointer
	Pointer type. More...

Public Member Functions
void	push_back (T &elem)
	Add object to the end of the queue. Can be called concurrently. Acquires ownership of elem. After this call returns, any thread calling pop_front_exclusive() or try_pop_front_exclusive() is guaranteed to see a non-empty queue. But note that the latter can still fail if called concurrently with push_back(). More...
Pointer	try_pop_front_exclusive ()
	Try to remove object from the beginning of the queue (non-blocking version). Should NOT be called concurrently. Releases ownership of the returned object. More...
Pointer	pop_front_exclusive ()
	Remove object from the beginning of the queue (blocking version). Should NOT be called concurrently. Releases ownership of the returned object. More...

Detailed Description

template<class T, template< class TT > class OwnershipPolicy = RefCountedOwnership, class Node = MpscQueueNode<>>
class roc::core::MpscQueue< T, OwnershipPolicy, Node >

Thread-safe lock-free node-based intrusive multi-producer single-consumer queue.

Provides sequential consistency.

Based on Dmitry Vyukov algorithm:

• http://tiny.cc/3d3moz
• https://int08h.com/post/ode-to-a-vyukov-queue/
• https://github.com/samanbarghi/MPSCQ

Template Parameters

T	defines object type, it must inherit MpscQueueNode.
OwnershipPolicy	defines ownership policy which is used to acquire an element ownership when it's added to the queue and release ownership when it's removed from the queue.
Node	defines base class of queue nodes. It is needed if MpscQueueNode is used with non-default tag.

Definition at line 45 of file mpsc_queue.h.

Member Typedef Documentation

Pointer

template<class T , template< class TT > class OwnershipPolicy = RefCountedOwnership, class Node = MpscQueueNode<>>

typedef OwnershipPolicy<T>::Pointer roc::core::MpscQueue< T, OwnershipPolicy, Node >::Pointer

Pointer type.

Remarks

either raw or smart pointer depending on the ownership policy.

Definition at line 50 of file mpsc_queue.h.

Member Function Documentation

pop_front_exclusive()

template<class T , template< class TT > class OwnershipPolicy = RefCountedOwnership, class Node = MpscQueueNode<>>

Pointer roc::core::MpscQueue< T, OwnershipPolicy, Node >::pop_front_exclusive ( )

inline

Remove object from the beginning of the queue (blocking version). Should NOT be called concurrently. Releases ownership of the returned object.

Remarks

• Returns NULL if the queue is empty.
• May spin while a concurrent push_back() call is running.

• This operation is NOT lock-free (or wait-free). It may spin until all concurrent push_back() calls are finished.
• On the "fast-path", however, this operation does not wait for any threads and just performs a few atomic reads and writes.

Definition at line 114 of file mpsc_queue.h.

push_back()

template<class T , template< class TT > class OwnershipPolicy = RefCountedOwnership, class Node = MpscQueueNode<>>

void roc::core::MpscQueue< T, OwnershipPolicy, Node >::push_back ( T &  elem )

inline

Add object to the end of the queue. Can be called concurrently. Acquires ownership of elem. After this call returns, any thread calling pop_front_exclusive() or try_pop_front_exclusive() is guaranteed to see a non-empty queue. But note that the latter can still fail if called concurrently with push_back().

Note

• On CPUs with atomic exchange, e.g. x86, this operation is both lock-free and wait-free, i.e. it never waits for sleeping threads and never spins.
• On CPUs without atomic exchange, e.g. arm64, this operation is lock-free, but not wait-free, i.e. it never waits for sleeping threads, but with a low probability can spin while there are concurrent non-sleeping push_back() calls (because of the spin loop in the implementation of atomic exchange).
• Concurrent try_pop_front() and pop_front() does not affect this operation. Only concurrent push_back() calls can make it spin.

Definition at line 73 of file mpsc_queue.h.

try_pop_front_exclusive()

template<class T , template< class TT > class OwnershipPolicy = RefCountedOwnership, class Node = MpscQueueNode<>>

Pointer roc::core::MpscQueue< T, OwnershipPolicy, Node >::try_pop_front_exclusive ( )

inline

Try to remove object from the beginning of the queue (non-blocking version). Should NOT be called concurrently. Releases ownership of the returned object.

Remarks

• Returns NULL if the queue is empty.
• May return NULL even if the queue is actually non-empty, in particular if concurrent push_back() call is running, or if the push_back() results were not fully published yet.

Note

• This operation is both lock-free and wait-free on all architectures, i.e. it never waits for sleeping threads and never spins indefinitely.

Definition at line 91 of file mpsc_queue.h.

---

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

• roc_core/mpsc_queue.h