dispenso::ChaseLevDeque< T, Capacity > Class Template Reference

A lock-free SPMC bounded work-stealing deque. More...

#include <chase_lev_deque.h>

Public Member Functions
	ChaseLevDeque ()=default
	Constructs an empty deque. Storage is uninitialized; elements are constructed in-place when pushed.
	ChaseLevDeque (const ChaseLevDeque &)=delete
	ChaseLevDeque (ChaseLevDeque &&)=delete
	~ChaseLevDeque ()=default
	Destroys the deque. Trivially-copyable elements need no explicit teardown.
bool	try_push (const T &item)
	Pushes an element onto the bottom of the deque (owner-only).
bool	try_pop (T &out)
	Pops the most recently pushed element (LIFO, owner-only).
bool	try_pop_into (T *storage)
	Pops the most recently pushed element into uninitialized storage (LIFO, owner-only). Useful when T is not default-constructible.
bool	try_steal (T &out)
	Steals the oldest element from the top of the deque (FIFO).
bool	try_steal_into (T *storage)
	Steals the oldest element into uninitialized storage (FIFO).
bool	empty () const
	Returns true if the deque appears empty.
size_type	size () const
	Returns the apparent number of elements in the deque.

Static Public Member Functions
static constexpr size_type	capacity () noexcept
	Returns the maximum number of elements the deque can hold.

Detailed Description

template<typename T, size_t Capacity = 32>
class dispenso::ChaseLevDeque< T, Capacity >

A lock-free SPMC bounded work-stealing deque.

The owning thread pushes/pops at the bottom end (LIFO), and any thread can steal from the top end (FIFO). The fast paths (push, non-contended pop) use no compare-and-swap; only the contended last-element pop and steal require CAS. This makes the deque the standard primitive for low-overhead recursive fork-join work distribution.

Storage is a fixed-size circular buffer indexed by monotonically-advancing top and bottom counters. Capacity is fixed at compile time and must be a power of two.

Template Parameters

T

The type of elements stored. Must be trivially copyable. The Chase-Lev steal protocol performs a tentative read of the slot before the CAS that claims it; a losing stealer simply discards the read. This is sound only when the read is a value copy that leaves the slot intact, which the trivially-copyable constraint guarantees. For move-only payloads, store a raw pointer (or other small POD wrapper) in the deque.

Capacity

Maximum number of in-flight elements. Must be a power of two and at least 1. Defaults to 32, sized for typical recursive fork-join depths while keeping the buffer in a few cache lines.

Thread Safety

• Exactly one thread (the owner) may call try_push, try_pop, and try_pop_into.
• Any thread (including the owner) may call try_steal and try_steal_into.
• empty(), size(), and capacity() may be called from any thread, but provide only a snapshot that may be immediately stale.

Steal Contention

try_steal returns false on both an empty deque and a lost CAS race. The two cases are not distinguished in the API; callers that want to retry on contention may compare size() before and after, or simply retry a small number of times.

Performance Characteristics

• Push: one relaxed load + one release store (of bottom_) + one acquire load. No CAS.
• Non-contended pop: one relaxed store + a seq_cst fence + one relaxed load. No CAS.
• Last-element pop and steal: one CAS on top_.

Example Usage

dispenso::ChaseLevDeque<int, 64> deque;
 
// Owner thread
deque.try_push(42);
int v;
if (deque.try_pop(v)) { use(v); }
 
// Any thread
int stolen;
if (deque.try_steal(stolen)) { use(stolen); }

Definition at line 100 of file chase_lev_deque.h.

Constructor & Destructor Documentation

~ChaseLevDeque()

template<typename T , size_t Capacity = 32>

dispenso::ChaseLevDeque< T, Capacity >::~ChaseLevDeque ( )

default

Destroys the deque. Trivially-copyable elements need no explicit teardown.

Note

Destruction is not thread-safe. Ensure no thread is pushing, popping, or stealing when the deque is destroyed.

Member Function Documentation

capacity()

template<typename T , size_t Capacity = 32>

static constexpr size_type dispenso::ChaseLevDeque< T, Capacity >::capacity ( )

inlinestaticconstexprnoexcept

Returns the maximum number of elements the deque can hold.

Definition at line 315 of file chase_lev_deque.h.

empty()

template<typename T , size_t Capacity = 32>

bool dispenso::ChaseLevDeque< T, Capacity >::empty ( ) const

inline

Returns true if the deque appears empty.

Definition at line 301 of file chase_lev_deque.h.

size()

template<typename T , size_t Capacity = 32>

size_type dispenso::ChaseLevDeque< T, Capacity >::size ( ) const

inline

Returns the apparent number of elements in the deque.

Definition at line 308 of file chase_lev_deque.h.

try_pop()

template<typename T , size_t Capacity = 32>

bool dispenso::ChaseLevDeque< T, Capacity >::try_pop ( T & out )

inline

Pops the most recently pushed element (LIFO, owner-only).

Parameters

[out]

out

Destination; written on success; value is unspecified on failure.

Returns

true on success, false if the deque is empty or the last element was simultaneously stolen.

Note

Only the owning thread may call this. On the non-contended path there is no CAS — only a relaxed store, a seq_cst fence, and a relaxed load.

Definition at line 176 of file chase_lev_deque.h.

try_pop_into()

template<typename T , size_t Capacity = 32>

bool dispenso::ChaseLevDeque< T, Capacity >::try_pop_into ( T * storage )

inline

Pops the most recently pushed element into uninitialized storage (LIFO, owner-only). Useful when T is not default-constructible.

Parameters

[out]

storage

Pointer to suitably-aligned uninitialized storage.

Returns

true on success, false otherwise.

Definition at line 208 of file chase_lev_deque.h.

try_push()

template<typename T , size_t Capacity = 32>

bool dispenso::ChaseLevDeque< T, Capacity >::try_push ( const T & item )

inline

Pushes an element onto the bottom of the deque (owner-only).

Parameters

item	Element to push.

Returns

true on success, false if the deque is full.

Note

Only the owning thread may call this. The fast path is one relaxed load and one release store (of bottom_) plus one acquire load (of top_) for the full/empty check, and the slot write. No fence, no CAS.

Definition at line 147 of file chase_lev_deque.h.

try_steal()

template<typename T , size_t Capacity = 32>

bool dispenso::ChaseLevDeque< T, Capacity >::try_steal ( T & out )

inline

Steals the oldest element from the top of the deque (FIFO).

Parameters

[out]

out

Destination; written on success; value is unspecified on failure.

Returns

true on success, false if the deque is empty or the CAS was lost to another concurrent stealer or a last-element pop.

Note

Callable from any thread. Distinguishing "empty" from "contended" is not exposed; callers may retry on false if work is expected.

Definition at line 247 of file chase_lev_deque.h.

try_steal_into()

template<typename T , size_t Capacity = 32>

bool dispenso::ChaseLevDeque< T, Capacity >::try_steal_into ( T * storage )

inline

Steals the oldest element into uninitialized storage (FIFO).

See also

try_steal(T&)

Definition at line 275 of file chase_lev_deque.h.

---

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

• /github/workspace/dispenso/chase_lev_deque.h