xenium::kirsch_kfifo_queue< T, Policies > Class Template Reference

An unbounded lock-free multi-producer/multi-consumer k-FIFO queue. More...

#include <kirsch_kfifo_queue.hpp>

Public Member Functions
void	push (value_type value)
	Pushes the given value to the queue. More...
bool	try_pop (value_type &result)
	Tries to pop an object from the queue. More...

Static Public Attributes
static constexpr std::size_t	entry_size = sizeof(entry)
	Provides the effective size of a single queue entry (including padding).

Detailed Description

template<class T, class... Policies>
class xenium::kirsch_kfifo_queue< T, Policies >

An unbounded lock-free multi-producer/multi-consumer k-FIFO queue.

This is an implementation of the proposal by Kirsch et al. [KLP13].

A k-FIFO queue can be understood as a queue where each element may be dequeued out-of-order up to k−1.

A limitation of this queue is that it can only handle pointers or trivially copyable types that are smaller than a pointer (i.e., T must be a raw pointer, a std::unique_ptr or a trivially copyable type like std::uint32_t).

Supported policies:

• xenium::policy::reclaimer
  Defines the reclamation scheme to be used for internal nodes. (required)
• xenium::policy::padding_bytes
  Defines the number of padding bytes for each entry. (optional; defaults to sizeof(T*))

Template Parameters

T
Policies	list of policies to customize the behaviour

Member Function Documentation

push()

template<class T , class... Policies>

void xenium::kirsch_kfifo_queue< T, Policies >::push

(

value_type

value

)

Pushes the given value to the queue.

This operation might have to allocate a new segment. Progress guarantees: lock-free (may perform a memory allocation)

Parameters

value

try_pop()

template<class T , class... Policies>

bool xenium::kirsch_kfifo_queue< T, Policies >::try_pop

(

value_type &

result

)

Tries to pop an object from the queue.

Progress guarantees: lock-free

Parameters

result

Returns

true if the operation was successful, otherwise false