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

Contents

• Reference
  • Constructors, destructors, conversion operators
  • Public functions

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