Unbounded lock-free multi-producer/single-consumer queue. More...

#include <tpl_mpsc_queue.H>

Collaboration diagram for Aleph::MpscQueue< T >:

Classes
struct	Node

Public Member Functions
	MpscQueue () noexcept
	Construct an empty queue.

	~MpscQueue ()
	Destroy the queue, releasing any still-queued nodes.

	MpscQueue (const MpscQueue &)=delete
	Deleted copy constructor: the queue owns heap nodes with internal atomics that cannot be safely duplicated.

MpscQueue &	operator= (const MpscQueue &)=delete
	Deleted copy assignment operator.

	MpscQueue (MpscQueue &&)=delete
	Deleted move constructor: producers may hold a reference to a fixed queue address; see the class-level thread-safety note.

MpscQueue &	operator= (MpscQueue &&)=delete
	Deleted move assignment operator.

void	push (const T &value)
	Push a copy of `value` onto the queue.

void	push (T &&value)
	Push `value` onto the queue, moving it in.

template<typename... Args>
void	emplace (Args &&... args)
	Construct a new element in place at the back of the queue.

bool	try_pop (T &out)
	Attempt to pop the front element into `out`.

std::optional< T >	try_pop ()
	Attempt to pop the front element.

bool	is_empty () const noexcept
	Advisory check for whether the queue currently has no elements.

Private Member Functions
void	push_node (Node *n) noexcept
	Publish `n` as the new last node.

Node *	pop_node () noexcept
	Consumer-only: detach and return the front node, or `nullptr`.

Private Attributes
std::atomic< Node * >	head_

Node *	tail_

Node	stub_

Detailed Description

template<typename T>
class Aleph::MpscQueue< T >

Unbounded lock-free multi-producer/single-consumer queue.

See the file-level documentation in tpl_mpsc_queue.H for the full algorithm description, thread-safety contract, progress guarantees, and memory-ordering rationale.

Template Parameters

T	Type of the elements stored in the queue. Must be move- or copy-constructible; move-only types are supported.

Definition at line 127 of file tpl_mpsc_queue.H.

Constructor & Destructor Documentation

◆ MpscQueue() [1/3]

template<typename T >

Aleph::MpscQueue< T >::MpscQueue ( )

inlinenoexcept

Construct an empty queue.

Exceptions

Nothing.

Note: Not thread-safe against concurrent use of the object being constructed (ordinary construction rules).

Definition at line 207 of file tpl_mpsc_queue.H.

◆ ~MpscQueue()

template<typename T >

Aleph::MpscQueue< T >::~MpscQueue ( )

inline

Destroy the queue, releasing any still-queued nodes.

Note: Not thread-safe: no producer or consumer operation may be in progress on this queue when the destructor runs.

Definition at line 214 of file tpl_mpsc_queue.H.

References Aleph::next(), Aleph::MpscQueue< T >::Node::next, Aleph::MpscQueue< T >::stub_, and Aleph::MpscQueue< T >::tail_.

◆ MpscQueue() [2/3]

template<typename T >

Aleph::MpscQueue< T >::MpscQueue ( const MpscQueue< T > & )

delete

Deleted copy constructor: the queue owns heap nodes with internal atomics that cannot be safely duplicated.

◆ MpscQueue() [3/3]

template<typename T >

Aleph::MpscQueue< T >::MpscQueue ( MpscQueue< T > && )

delete

Deleted move constructor: producers may hold a reference to a fixed queue address; see the class-level thread-safety note.

Member Function Documentation

◆ emplace()

template<typename T >

template<typename... Args>

void Aleph::MpscQueue< T >::emplace ( Args &&... args )

inline

Construct a new element in place at the back of the queue.

Template Parameters

Args	Constructor argument types.

Parameters

args	Arguments forwarded to `T`'s constructor.

Exceptions

Whatever constructing T(std::forward<Args>(args)...) throws, or std::bad_alloc from allocating the node. If construction throws, the partially-built node is destroyed and nothing is enqueued.

Note: Lock-free. Safe to call concurrently from any number of producer threads.

Definition at line 278 of file tpl_mpsc_queue.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::MpscQueue< T >::push_node().

Referenced by Aleph::MpscQueue< T >::push(), Aleph::MpscQueue< T >::push(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ is_empty()

template<typename T >

bool Aleph::MpscQueue< T >::is_empty ( ) const

inlinenoexcept

Advisory check for whether the queue currently has no elements.

Returns: true if the queue looked empty at the moment of the call.

Exceptions

Nothing.

Note: Consumer-only, same restriction as try_pop. Advisory under concurrent pushes: a producer may complete a push immediately after this returns true. Like try_pop, this can also report true during the narrow window where a push's exchange has completed but its store has not.

Definition at line 341 of file tpl_mpsc_queue.H.

References Aleph::and, Aleph::MpscQueue< T >::Node::next, Aleph::MpscQueue< T >::stub_, and Aleph::MpscQueue< T >::tail_.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ operator=() [1/2]

template<typename T >

MpscQueue & Aleph::MpscQueue< T >::operator= ( const MpscQueue< T > & )

delete

Deleted copy assignment operator.

◆ operator=() [2/2]

template<typename T >

MpscQueue & Aleph::MpscQueue< T >::operator= ( MpscQueue< T > && )

delete

Deleted move assignment operator.

◆ pop_node()

template<typename T >

Node * Aleph::MpscQueue< T >::pop_node ( )

inlineprivatenoexcept

Consumer-only: detach and return the front node, or nullptr.

Implements Vyukov's pop exactly: on success, the returned node owns the dequeued value and is no longer reachable from the queue (the caller must destroy it once it is done reading ->value). Returning nullptr means either the queue is genuinely empty, or a producer's push_node was caught between its exchange and its store – both look identical to the consumer, and the documented contract is to treat that rare race as a transient "nothing to pop yet".

Definition at line 165 of file tpl_mpsc_queue.H.

References Aleph::MpscQueue< T >::head_, Aleph::next(), Aleph::MpscQueue< T >::Node::next, Aleph::MpscQueue< T >::push_node(), Aleph::MpscQueue< T >::stub_, and Aleph::MpscQueue< T >::tail_.

Referenced by Aleph::MpscQueue< T >::try_pop(), and Aleph::MpscQueue< T >::try_pop().

◆ push() [1/2]

template<typename T >

void Aleph::MpscQueue< T >::push ( const T & value )

inline

Push a copy of value onto the queue.

Parameters

value The value to enqueue (copied).

Exceptions

Whatever T's copy constructor throws, or std::bad_alloc. If construction throws, nothing is enqueued and the queue is left exactly as it was before the call.

Note: Lock-free. Safe to call concurrently from any number of producer threads.

Definition at line 252 of file tpl_mpsc_queue.H.

References Aleph::MpscQueue< T >::emplace(), and value.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ push() [2/2]

template<typename T >

void Aleph::MpscQueue< T >::push ( T && value )

inline

Push value onto the queue, moving it in.

Parameters

value The value to enqueue (moved from).

Exceptions

Whatever T's move constructor throws, or std::bad_alloc. If construction throws, value is left in the state T's move constructor leaves a throwing source in, and nothing is enqueued.

Note: Lock-free. Safe to call concurrently from any number of producer threads.

Definition at line 264 of file tpl_mpsc_queue.H.

References Aleph::MpscQueue< T >::emplace(), and value.

◆ push_node()

template<typename T >

void Aleph::MpscQueue< T >::push_node ( Node * n )

inlineprivatenoexcept

Publish n as the new last node.

Safe to call from any producer thread, and internally (single-threaded) to recycle &stub_.

Definition at line 148 of file tpl_mpsc_queue.H.

References Aleph::MpscQueue< T >::head_, and Aleph::MpscQueue< T >::Node::next.

Referenced by Aleph::MpscQueue< T >::emplace(), and Aleph::MpscQueue< T >::pop_node().

◆ try_pop() [1/2]

template<typename T >

std::optional< T > Aleph::MpscQueue< T >::try_pop ( )

inline

Attempt to pop the front element.

Returns: The dequeued value wrapped in std::optional, or std::nullopt if the queue looked empty (see the class-level note on the narrow producer-race window).

Exceptions

Whatever moving T into the returned std::optional throws. If it throws, the node has already been unlinked from the queue; the element is lost. The node itself is still freed (via RAII) even if the move throws.

Note: Consumer-only: must never be called concurrently with another try_pop/is_empty call, nor from more than one thread.

Definition at line 322 of file tpl_mpsc_queue.H.

References Aleph::MpscQueue< T >::pop_node().

◆ try_pop() [2/2]

template<typename T >

bool Aleph::MpscQueue< T >::try_pop ( T & out )

inline

Attempt to pop the front element into out.

Parameters

[out] out Reference receiving the dequeued value (move-assigned).

Returns: true if an element was dequeued, false if the queue looked empty (see the class-level note on the narrow producer-race window that can also yield false transiently).

Exceptions

Whatever T's move assignment throws. If it throws, the node has already been unlinked from the queue; the element is lost (this matches the "no defined recovery from a throwing move assignment" convention used elsewhere in Aleph's queues). The node itself is still freed (via RAII) even if the move throws.