template<typename T, size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>
tf::BoundedTaskQueue class

class to create a lock-free bounded work-stealing queue

Template parameters
T data type
LogSize the base-2 logarithm of the queue size

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

BoundedTaskQueue() defaulted
constructs the queue with a given capacity
~BoundedTaskQueue() defaulted
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 -> size_t constexpr
queries the capacity of the queue
template<typename O>
auto try_push(O&& item) -> bool
tries to insert an item to the queue
template<typename O, typename C>
void push(O&& item, C&& on_full)
tries to insert an item to the queue or invoke the callable if fails
auto pop() -> T
pops out an item from the queue
auto steal() -> T
steals an item from the queue
auto steal_with_hint(size_t& num_empty_steals) -> T
attempts to steal a task with a hint mechanism

Function documentation

template<typename T, size_t LogSize> template<typename O>
bool tf::BoundedTaskQueue<T, LogSize>::try_push(O&& item)

tries to insert an item to the queue

Template parameters
O data type
Parameters
item the item to perfect-forward to the queue
Returns true if the insertion succeed or false (queue is full)

Only the owner thread can insert an item to the queue.

template<typename T, size_t LogSize> template<typename O, typename C>
void tf::BoundedTaskQueue<T, LogSize>::push(O&& item, C&& on_full)

tries to insert an item to the queue or invoke the callable if fails

Template parameters
O data type
C callable type
Parameters
item the item to perfect-forward to the queue
on_full callable to invoke when the queue is full (insertion fails)

Only the owner thread can insert an item to the queue.

template<typename T, size_t LogSize>
T tf::BoundedTaskQueue<T, LogSize>::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, size_t LogSize>
T tf::BoundedTaskQueue<T, LogSize>::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).

template<typename T, size_t LogSize>
T tf::BoundedTaskQueue<T, LogSize>::steal_with_hint(size_t& num_empty_steals)

attempts to steal a task with a hint mechanism

Parameters
num_empty_steals a reference to a counter tracking consecutive empty steal attempts

This function tries to steal a task from the queue. If the steal attempt is successful, the stolen task is returned. Additionally, if the queue is empty, the provided counter num_empty_steals is incremented; otherwise, num_empty_steals is reset to zero.