tf::AtomicIntrusiveStack< T, MemberPtr > Class Template Reference

class to create a lock-free, ABA-safe intrusive stack More...

#include <taskflow/core/freelist.hpp>

Public Member Functions
	AtomicIntrusiveStack ()
	constructs an empty stack
bool	empty () const
	queries whether the stack is empty at the time of this call
void	push (T node)
	pushes a node onto the top of the stack
T	pop ()
	removes and returns the top node, or nullptr if the stack is empty

Detailed Description

template<typename T, auto MemberPtr>
class tf::AtomicIntrusiveStack< T, MemberPtr >

class to create a lock-free, ABA-safe intrusive stack

Template Parameters

T	pointer type of the node (e.g., Node*)
MemberPtr	pointer-to-member that identifies the intrusive link field within the node type (e.g., &Node::next)

An intrusive stack embeds the link pointer directly inside each node rather than allocating separate list nodes. The caller selects which field serves as the link by supplying MemberPtr. While a node is held in the stack that field is exclusively owned by the stack and must not be accessed by the caller.

The field identified by MemberPtr must be of type T (a pointer to the same node type) so the stack can chain nodes through it:

struct Node {
  Node* next {nullptr};  // used as the intrusive link
  int   value{0};
};
tf::AtomicIntrusiveStack<Node*, &Node::next> stack;

All methods are safe to call concurrently from multiple threads. push and bulk_push are lock-free. pop is lock-free.

ABA safety

Each CAS operation pairs the pointer with a monotonically-incrementing version tag stored in a 128-bit TaggedPointer atomic. This requires CMPXCHG16B support on x86-64. A 64-bit tagged-pointer alternative for platforms without 128-bit CAS is available in the commented-out section at the bottom of this file.

Constructor & Destructor Documentation

AtomicIntrusiveStack()

template<typename T , auto MemberPtr>

tf::AtomicIntrusiveStack< T, MemberPtr >::AtomicIntrusiveStack ( )

inline

constructs an empty stack

struct Node { Node* next {nullptr}; };
tf::AtomicIntrusiveStack<Node*, &Node::next> stack;
assert(stack.empty() == true);

Member Function Documentation

empty()

template<typename T , auto MemberPtr>

bool tf::AtomicIntrusiveStack< T, MemberPtr >::empty ( ) const

inline

queries whether the stack is empty at the time of this call

The result is a snapshot and may be stale by the time the caller acts on it in a concurrent setting.

struct Node { Node* next {nullptr}; };
tf::AtomicIntrusiveStack<Node*, &Node::next> stack;
 
assert(stack.empty() == true);
Node n;
stack.push(&n);
assert(stack.empty() == false);
stack.pop();
assert(stack.empty() == true);

pop()

template<typename T , auto MemberPtr>

T tf::AtomicIntrusiveStack< T, MemberPtr >::pop ( )

inline

removes and returns the top node, or nullptr if the stack is empty

Returns

pointer to the popped node, or nullptr if the stack was empty

Atomically swaps the head to the next node in the chain. The popped node's link field is cleared to nullptr before it is returned, so the caller receives a clean node with no dangling stack pointer. Safe to call concurrently with other push, bulk_push, and pop calls.

struct Node { Node* next {nullptr}; int value {0}; };
tf::AtomicIntrusiveStack<Node*, &Node::next> stack;
 
// pop from empty stack returns nullptr
assert(stack.pop() == nullptr);
 
Node a{nullptr, 1}, b{nullptr, 2};
stack.push(&a);
stack.push(&b);
 
Node* n = stack.pop();
assert(n == &b);
 
assert(stack.pop() == &a);
assert(stack.pop() == nullptr);

push()

template<typename T , auto MemberPtr>

void tf::AtomicIntrusiveStack< T, MemberPtr >::push ( T node )

inline

pushes a node onto the top of the stack

Parameters

node	pointer to the node to push; must not be nullptr

Sets the node's link field to the current head and atomically swaps the head to node. The version tag is incremented on every successful CAS to prevent ABA. Safe to call concurrently with other push, bulk_push, and pop calls.

struct Node { Node* next {nullptr}; int value {0}; };
tf::AtomicIntrusiveStack<Node*, &Node::next> stack;
 
Node a{nullptr, 1}, b{nullptr, 2};
stack.push(&a);
stack.push(&b);
// stack order top-to-bottom: b -> a
assert(stack.pop() == &b);
assert(stack.pop() == &a);
assert(stack.pop() == nullptr);

---

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

• taskflow/core/freelist.hpp