Cpp-Taskflow  2.2.0
tf::WorkStealingQueue< T > Class Template Reference

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

#include <spmc_queue.hpp>

Public Member Functions

 WorkStealingQueue (int64_t capacity=1024)
 constructs the queue with a given capacity More...
 
 ~WorkStealingQueue ()
 destructs the queue
 
bool empty () const noexcept
 queries if the queue is empty at the time of this call
 
size_t size () const noexcept
 queries the number of items at the time of this call
 
int64_t capacity () const noexcept
 queries the capacity of the queue
 
template<typename O >
void push (O &&item)
 inserts an item to the queue More...
 
std::optional< T > pop ()
 pops out an item from the queue More...
 
std::optional< T > unsync_pop ()
 pops out an item from the queue without synchronization with thieves More...
 
std::optional< T > steal ()
 steals an item from the queue More...
 

Detailed Description

template<typename T>
class tf::WorkStealingQueue< T >

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

Template Parameters
Tdata type

This class implements the work stealing queue described in the paper, "Dynamic Circular Work-stealing Deque," SPAA, 2015. Only the queue owner can perform pop and push operations, while others can steal data from the queue.

PPoPP implementation paper "Correct and Efficient Work-Stealing for Weak Memory Models" https://www.di.ens.fr/~zappa/readings/ppopp13.pdf

Constructor & Destructor Documentation

◆ WorkStealingQueue()

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

constructs the queue with a given capacity

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

Member Function Documentation

◆ pop()

template<typename T >
std::optional< T > tf::WorkStealingQueue< 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 std::nullopt if this operation failed (empty queue).

◆ push()

template<typename T >
template<typename O >
void tf::WorkStealingQueue< T >::push ( O &&  item)

inserts an item 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 space is required.

Template Parameters
Odata type
Parameters
itemthe item to perfect-forward to the queue

◆ steal()

template<typename T >
std::optional< T > tf::WorkStealingQueue< T >::steal ( )

steals an item from the queue

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

◆ unsync_pop()

template<typename T >
std::optional< T > tf::WorkStealingQueue< T >::unsync_pop ( )

pops out an item from the queue without synchronization with thieves

Only the onwer thread can pop out an item from the queue, given no other threads trying to steal an item at the same time

The return can be a std::nullopt if this operation failed (empty queue).


The documentation for this class was generated from the following file: