template<typename T, unsigned TF_MAX_PRIORITY = static_cast<unsigned>(TaskPriority::MAX)>
tf::TaskQueue class

class to create a lock-free unbounded single-producer multiple-consumer queue

Template parameters
T data type (must be a pointer type)
TF_MAX_PRIORITY maximum level of the priority

This class implements the work-stealing queue described in the paper, Correct and Efficient Work-Stealing for Weak Memory Models, and extends it to include priority.

Only the queue owner can perform pop and push operations, while others can steal data from the queue simultaneously. Priority starts from zero (highest priority) to the template value TF_MAX_PRIORITY-1 (lowest priority). All operations are associated with priority values to indicate the corresponding queues to which an operation is applied.

The default template value, TF_MAX_PRIORITY, is TaskPriority::MAX which applies only three priority levels to the task queue.

auto [A, B, C, D, E] = taskflow.emplace(
  [] () { },
  [&] () { 
    std::cout << "Task B: " << counter++ << '\n';  // 0
  },
  [&] () { 
    std::cout << "Task C: " << counter++ << '\n';  // 2
  },
  [&] () { 
    std::cout << "Task D: " << counter++ << '\n';  // 1
  },
  [] () { }
);

A.precede(B, C, D); 
E.succeed(B, C, D);
  
B.priority(tf::TaskPriority::HIGH);
C.priority(tf::TaskPriority::LOW);
D.priority(tf::TaskPriority::NORMAL);
  
executor.run(taskflow).wait();

In the above example, we have a task graph of five tasks, A, B, C, D, and E, in which B, C, and D can run in simultaneously when A finishes. Since we only uses one worker thread in the executor, we can deterministically run B first, then D, and C in order of their priority values. The output is as follows:

Task B: 0
Task D: 1
Task C: 2

Constructors, destructors, conversion operators

TaskQueue(int64_t capacity = 512) 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 empty(unsigned priority) const -> bool noexcept
queries if the queue is empty at a specific priority value
auto size() const -> size_t noexcept
queries the number of items at the time of this call
auto size(unsigned priority) const -> size_t noexcept
queries the number of items with the given priority at the time of this call
auto capacity() const -> int64_t noexcept
queries the capacity of the queue
auto capacity(unsigned priority) const -> int64_t noexcept
queries the capacity of the queue at a specific priority value
auto push(T item, unsigned priority) -> TF_FORCE_INLINE void
inserts an item to the queue
auto pop() -> T
pops out an item from the queue
auto pop(unsigned priority) -> TF_FORCE_INLINE T
pops out an item with a specific priority value from the queue
auto steal() -> T
steals an item from the queue
auto steal(unsigned priority) -> T
steals an item with a specific priority value from the queue

Function documentation

template<typename T, unsigned TF_MAX_PRIORITY>
tf::TaskQueue<T, TF_MAX_PRIORITY>::TaskQueue(int64_t capacity = 512) explicit

constructs the queue with a given capacity

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

template<typename T, unsigned TF_MAX_PRIORITY>
TF_FORCE_INLINE void tf::TaskQueue<T, TF_MAX_PRIORITY>::push(T item, unsigned priority)

inserts an item to the queue

Parameters
item the item to push to the queue
priority priority value of the item to push (default = 0)

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<typename T, unsigned TF_MAX_PRIORITY>
T tf::TaskQueue<T, TF_MAX_PRIORITY>::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, unsigned TF_MAX_PRIORITY>
TF_FORCE_INLINE T tf::TaskQueue<T, TF_MAX_PRIORITY>::pop(unsigned priority)

pops out an item with a specific priority value from the queue

Parameters
priority priority of the item to pop

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, unsigned TF_MAX_PRIORITY>
T tf::TaskQueue<T, TF_MAX_PRIORITY>::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, unsigned TF_MAX_PRIORITY>
T tf::TaskQueue<T, TF_MAX_PRIORITY>::steal(unsigned priority)

steals an item with a specific priority value from the queue

Parameters
priority priority of the item to steal

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