xenium::vyukov_bounded_queue< T, Policies > Struct Template Reference

A bounded generic multi-producer/multi-consumer FIFO queue. More...

#include <vyukov_bounded_queue.hpp>

Public Member Functions
	vyukov_bounded_queue (std::size_t size)
	Constructs a new instance with the specified maximum size. More...
template<class... Args>
bool	try_push (Args &&... args)
	Tries to push a new element to the queue. More...
template<class... Args>
bool	try_push_strong (Args &&... args)
	Tries to push a new element to the queue. More...
template<class... Args>
bool	try_push_weak (Args &&... args)
	Tries to push a new element to the queue. More...
bool	try_pop (T &result)
	Tries to pop an element from the queue. More...
bool	try_pop_strong (T &result)
	Tries to pop an element from the queue as long as the queue is not empty. More...
bool	try_pop_weak (T &result)
	Tries to pop an element from the queue. More...

Detailed Description

template<class T, class... Policies>
struct xenium::vyukov_bounded_queue< T, Policies >

A bounded generic multi-producer/multi-consumer FIFO queue.

This implementation is based on the bounded MPMC queue proposed by Vyukov [Vy10]. It is fully generic and can handle any type T, as long as it is default constructible and either copyable or movable.

Producers and consumers operate independently, but the operations are not lock-free, i.e., a try_pop may have to wait for a pending try_push operation to finish and vice versa.

The try_push_weak and try_pop_weak versions are lock-free, but may fail in situations were the non-weak versions would succeed. Consider the following situation: Thread T1 and thread T2 both push to the queue. T1 starts before T2, but T2 finishes faster. Now T2 tries to pop from the queue. The queue is not empty (T2 has previously pushed an element, and there are no other pop operations involved), but T1 has still not finished its push operation. However, because T1 has started its push before T2, this is the next item to be popped. In such a situation try_pop would keep spinning until T1 has finished, while try_pop_weak would immediately return false, even though the queue is not empty.

Template Parameters

T	type of the stored elements.

Constructor & Destructor Documentation

vyukov_bounded_queue()

template<class T , class... Policies>

xenium::vyukov_bounded_queue< T, Policies >::vyukov_bounded_queue ( std::size_t  size )

inlineexplicit

Constructs a new instance with the specified maximum size.

Parameters

size	max number of elements in the queue; must be a power of two greater one.

Member Function Documentation

try_pop()

template<class T , class... Policies>

bool xenium::vyukov_bounded_queue< T, Policies >::try_pop ( T &  result )

inline

Tries to pop an element from the queue.

If policy::default_to_weak has been specified to be true, this method forwards to try_pop_weak, otherwise it forwards to try_pop_strong.

Progress guarantees: see try_pop_weak/try_pop_strong

Parameters

result

the value popped from the queue if the operation was successful

Returns

true if the operation was successful, otherwise false

try_pop_strong()

template<class T , class... Policies>

bool xenium::vyukov_bounded_queue< T, Policies >::try_pop_strong ( T &  result )

inline

Tries to pop an element from the queue as long as the queue is not empty.

In case a push operation is still pending try_pop keeps spinning until the push has finished.

Progress guarantees: blocking

Parameters

result

the value popped from the queue if the operation was successful

Returns

true if the operation was successful, otherwise false

try_pop_weak()

template<class T , class... Policies>

bool xenium::vyukov_bounded_queue< T, Policies >::try_pop_weak ( T &  result )

inline

Tries to pop an element from the queue.

This operation fails if the queue is empty or a push operation on the element to be popped is still pending.

Progress guarantees: lock-free

Parameters

result

the value popped from the queue if the operation was successful

Returns

true if the operation was successful, otherwise false

try_push()

template<class T , class... Policies>

template<class... Args>

bool xenium::vyukov_bounded_queue< T, Policies >::try_push ( Args &&...  args )

inline

Tries to push a new element to the queue.

If policy::default_to_weak has been specified to be true, this method forwards to try_push_weak, otherwise it forwards to try_push_strong.

Progress guarantees: see try_push_weak/try_push_strong

Template Parameters

Args

Parameters

args

Returns

true if the operation was successful, otherwise false

try_push_strong()

template<class T , class... Policies>

template<class... Args>

bool xenium::vyukov_bounded_queue< T, Policies >::try_push_strong ( Args &&...  args )

inline

Tries to push a new element to the queue.

Tries to reserve a cell for the new element as long as the number of elements does not exceed the specified size.

If the argument is of type T, the element is either copy-assigned or move-assigned (depending on whether Args is an l-value or r-value). Otherwise, a temporary T instance is created using perfect-forwarding on the given arguments, which is then move-assigned.

Progress guarantees: blocking

Template Parameters

Args

Parameters

args

Returns

true if the operation was successful, otherwise false

try_push_weak()

template<class T , class... Policies>

template<class... Args>

bool xenium::vyukov_bounded_queue< T, Policies >::try_push_weak ( Args &&...  args )

inline

Tries to push a new element to the queue.

Tries to reserve a cell for the new element; fails if the queue is full or a pop operation on the element to be pushed to is still pending.

If the argument is of type T, the element is either copy-assigned or move-assigned (depending on whether Args is an l-value or r-value). Otherwise, a temporary T instance is created using perfect-forwarding on the given arguments, which is then move-assigned.

Progress guarantees: lock-free

Template Parameters

Args

Parameters

args

Returns

true if the operation was successful, otherwise false