template<typename T>
tf::TaskQueue class

Lock-free unbounded single-producer multiple-consumer queue.

Template parameters
T data type (must be a pointer)

Contents

This class implements the work stealing queue described in the paper, "Correct and Efficient Work-Stealing for Weak Memory Models," available at https://www.di.ens.fr/~zappa/readings/ppopp13.pdf.

Only the queue owner can perform pop and push operations, while others can steal data from the queue.

Constructors, destructors, conversion operators

TaskQueue(int64_t capacity = 1024) explicit
constructs the queue with a given capacity
~TaskQueue()
destructs the queue

Public functions

auto empty() const -> bool noexcept
queries if the queue is empty at the time of this call
auto size() const -> size_t noexcept
queries the number of items at the time of this call
auto capacity() const -> int64_t noexcept
queries the capacity of the queue
void push(T item)
inserts an item to the queue
auto pop() -> T
pops out an item from the queue
auto steal() -> T
steals an item from the queue

Function documentation

template<typename T>
tf::TaskQueue<T>::TaskQueue(int64_t capacity = 1024) explicit

constructs the queue with a given capacity

Parameters
capacity the capacity of the queue (must be power of 2)

template<typename T>
void tf::TaskQueue<T>::push(T item)

inserts an item to the queue

Parameters
item the item to perfect-forward to the queue

Only the owner thread can insert an item to the queue. The operation can trigger the queue to resize its capacity if more hub is required.

template<typename T>
T tf::TaskQueue<T>::pop()

pops out an item from the queue

Only the owner thread can pop out an item from the queue. The return can be a nullptr if this operation failed (empty queue).

template<typename T>
T tf::TaskQueue<T>::steal()

steals an item from the queue

Any threads can try to steal an item from the queue. The return can be a nullptr if this operation failed (not necessary empty).