tf::BoundedWSQ< T, LogSize > Class Template Reference

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

#include <taskflow/core/wsq.hpp>

Public Types
using	value_type = std::conditional_t<std::is_pointer_v<T>, T, std::optional<T>>
	the return type of queue operations

Public Member Functions
	BoundedWSQ ()=default
	constructs the queue with a given capacity
	~BoundedWSQ ()=default
	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
constexpr size_t	capacity () const
	queries the capacity of the queue
template<typename O >
bool	try_push (O &&item)
	tries to insert an item to the queue
template<typename I >
size_t	try_bulk_push (I &first, size_t N)
	tries to insert a batch of items into the queue
value_type	pop ()
	pops out an item from the queue
value_type	steal ()
	steals an item from the queue
value_type	steal_with_feedback ()
	attempts to steal an item from the queue with three-state feedback

Static Public Member Functions
static constexpr auto	empty_value ()
	returns the empty sentinel value for the queue element type
static auto	contended_value ()
	returns the contended sentinel value for pointer element types

Detailed Description

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

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.

A work-stealing queue supports a single owner thread that performs push and pop operations, while multiple concurrent thief threads may steal tasks from the opposite end of the queue. The implementation is designed to operate correctly under weak memory models and uses atomic operations with carefully chosen memory orderings to ensure correctness and scalability.

The queue has a fixed capacity determined at construction time and does not grow dynamically. When the queue is full, push operations may fail or require external handling.

Member Typedef Documentation

value_type

template<typename T , size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>

using tf::BoundedWSQ< T, LogSize >::value_type = std::conditional_t<std::is_pointer_v<T>, T, std::optional<T>>

the return type of queue operations

value_type represents the type returned by pop and steal operations. For pointer element types T, it is T itself and uses nullptr to indicate an empty result. For non-pointer types, it is std::optional<T>, where std::nullopt denotes the absence of a value.

static_assert(std::is_same_v<tf::UnboundedWSQ<int>::value_type, std::optional<int>>);
static_assert(std::is_same_v<tf::UnboundedWSQ<int*>::value_type, nullptr);

This design avoids the overhead of std::optional for pointer types while providing a uniform empty-result semantics.

Constructor & Destructor Documentation

BoundedWSQ()

template<typename T , size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>

tf::BoundedWSQ< T, LogSize >::BoundedWSQ ( )

default

constructs the queue with a given capacity

tf::BoundedWSQ<int, 10> wsq;  
static_assert(wsq.capacity() == 1024);

Member Function Documentation

capacity()

template<typename T , size_t LogSize>

size_t tf::BoundedWSQ< T, LogSize >::capacity ( ) const

constexpr

queries the capacity of the queue

The capacity of a bounded work-stealing queue is decided at compile time.

tf::BoundedWSQ<int, 10> wsq;
static_assert(wsq.capacity() == 1024);

contended_value()

template<typename T , size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>

static auto tf::BoundedWSQ< T, LogSize >::contended_value ( )

inlinestatic

returns the contended sentinel value for pointer element types

When steal_with_feedback returns this value, the queue was non-empty but the CAS was lost to another concurrent thief. The caller should retry the same victim immediately since work is known to exist.

Delegates to wsq_contended_value<T>(). See that function for a full explanation of the sentinel value and its safety guarantees.

empty()

template<typename T , size_t LogSize>

bool tf::BoundedWSQ< T, LogSize >::empty ( ) const

noexcept

queries if the queue is empty at the time of this call

tf::BoundedWSQ<int, 10> wsq;  
assert(wsq.empty() == true);
wsq.push(1);
assert(wsq.empty() == false);

empty_value()

template<typename T , size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>

static constexpr auto tf::BoundedWSQ< T, LogSize >::empty_value ( )

inlinestaticconstexpr

returns the empty sentinel value for the queue element type

This function provides a type-appropriate empty value used to indicate that a pop or steal operation failed. For pointer types, the empty value is nullptr of type T; for non-pointer types, it is std::nullopt of type std::optional<T>.

The function is implemented as a constexpr helper to avoid additional storage, runtime overhead, or code duplication across queue operations.

Returns

an empty value_type representing the absence of an element.

pop()

template<typename T , size_t LogSize>

BoundedWSQ< T, LogSize >::value_type tf::BoundedWSQ< T, LogSize >::pop

(

)

pops out an item from the queue

The method pops an item out of the queue based on a last-in-first-out (LIFO) order. The return can be an empty_value() if this operation failed (empty queue).

tf::BoundedWSQ<int, 10> wsq;  
wsq.push(1);
wsq.push(2);
wsq.push(3);
assert(wsq.pop().value() = 3);
assert(wsq.pop().value() = 2);
assert(wsq.pop().value() = 1);
assert(wsq.pop() == std::nullopt);

Only the owner thread can pop out an item from the queue.

size()

template<typename T , size_t LogSize>

size_t tf::BoundedWSQ< T, LogSize >::size ( ) const

noexcept

queries the number of items at the time of this call

tf::BoundedWSQ<int, 10> wsq;  
assert(wsq.size() == 0);
wsq.push(1);
assert(wsq.size() == 1);

steal()

template<typename T , size_t LogSize>

BoundedWSQ< T, LogSize >::value_type tf::BoundedWSQ< T, LogSize >::steal

(

)

steals an item from the queue

Any threads can try to steal an item from the queue. The return can be an empty_value() if this operation failed. The elements stolen from the queue follow a first-in-first-out (FIFO) order.

tf::BoundedWSQ<int, 10> wsq;  
wsq.push(1);
wsq.push(2);
wsq.push(3);
assert(wsq.steal().value() = 1);
assert(wsq.steal().value() = 2);
assert(wsq.steal().value() = 3);
assert(wsq.steal() == std::nullopt);

Multiple threads can simultaneously steal items from the queue.

steal_with_feedback()

template<typename T , size_t LogSize>

BoundedWSQ< T, LogSize >::value_type tf::BoundedWSQ< T, LogSize >::steal_with_feedback

(

)

attempts to steal an item from the queue with three-state feedback

Returns

one of three sentinel-encoded values (for pointer types T):

• a valid pointer: item successfully stolen (CAS succeeded, queue was non-empty)
• contended_value(): queue was non-empty but the CAS was lost to another concurrent thief; the caller should retry the same victim immediately since work is known to exist
• empty_value() (nullptr): queue was genuinely empty; the caller should move on to a different victim

For non-pointer types T, the return is std::optional<T> and only two states are possible (value present or std::nullopt); contention cannot be distinguished from emptiness and the method behaves identically to steal.

Sentinel safety for pointer types

The contended sentinel is reinterpret_cast<T>(uintptr_t{1}), i.e., the pointer value 0x1. This is guaranteed never to be a valid object pointer because the C++ standard and every major platform ABI require that any live object is aligned to at least alignof(T) bytes. For pointer element types used with this queue (e.g., Node*), alignof(Node) is at least 8 (and in Taskflow's case 64, due to alignas(TF_CACHELINE_SIZE) on Node members). Therefore the low bits of any real pointer are always zero, making 0x1 an impossible address. For void* there is no pointee type to check, but the same reasoning applies — no allocator ever returns address 0x1.

Caller usage pattern

tf::BoundedWSQ<Node*> wsq;
Node* result = wsq.steal_with_feedback();
 
if(result == wsq.empty_value()) {
  // queue was empty — move on to another victim
}
else if(result == wsq.contended_value()) {
  // lost CAS race — queue has work, retry this victim
}
else {
  // result is a valid stolen item — use it
}

Multiple threads can simultaneously call this method.

try_bulk_push()

template<typename T , size_t LogSize>

template<typename I >

size_t tf::BoundedWSQ< T, LogSize >::try_bulk_push	(	I &	first,
		size_t	N )

tries to insert a batch of items into the queue

Template Parameters

I	input iterator type

Parameters

first	iterator to the first item in the batch
N	number of items to insert beginning at first

Returns

the number of items successfully inserted

This method attempts to push up to N items from the range [first, first + N) into the queue. Insertion stops early if the queue becomes full. The iterator first is updated in place and will point to the next uninserted element after the call.

Bulk insertion is often faster than inserting elements one by one because it requires fewer atomic operations.

tf::BoundedWSQ<int, 10> wsq;  
static_assert(wsq.capacity() == 1024);
std::vector<int> vec(1030, 1);
auto first = vec.begin();
assert(wsq.try_bulk_push(first, vec.size()) == wsq.capacity());
assert(std::distance(vec.begin(), first) == wsq.capacity());

Only the owner thread can insert items into the queue.

try_push()

template<typename T , size_t LogSize>

template<typename O >

bool tf::BoundedWSQ< 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)

This method attempts to push one item into the queue. If the operation succeed, it returns true or false otherwise.

tf::BoundedWSQ<int, 10> wsq;  
static_assert(wsq.capacity() == 1024);
for(int i=0; i<1024; i++) {
  assert(wsq.try_push(i) == true);
}
assert(wsq.size() == 1024);
assert(wsq.try_push(0) == false);

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

---

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

• taskflow/core/wsq.hpp