Struct TransferStack

pub struct TransferStack<T: Linked<Links<T>>> { /* private fields */ }

An intrusive lock-free singly-linked FIFO stack, where all entries currently in the stack are consumed in a single atomic operation.

A transfer stack is perhaps the world’s simplest lock-free concurrent data structure. It provides two primary operations:

• TransferStack::push, which appends an element to the end of the transfer stack,

• TransferStack::take_all, which atomically takes all elements currently on the transfer stack and returns them as a new mutable Stack.

These are both O(1) operations, although push performs a compare-and-swap loop that may be retried if another producer concurrently pushed an element.

In order to be part of a TransferStack, a type T must implement the Linked trait for stack::Links<T>.

Pushing elements into a TransferStack takes ownership of those elements through an owning Handle type. Dropping a TransferStack drops all elements currently linked into the stack.

A transfer stack is often useful in cases where a large number of resources must be efficiently transferred from several producers to a consumer, such as for reuse or cleanup. For example, a TransferStack can be used as the “thread” (shared) free list in a mimalloc-style sharded allocator, with a mutable Stack used as the local (unsynchronized) free list. When an allocation is freed from the same CPU core that it was allocated on, it is pushed to the local free list, using an unsynchronized mutable Stack::push operation. If an allocation is freed from a different thread, it is instead pushed to that thread’s shared free list, a TransferStack, using an atomic TransferStack::push operation. New allocations are popped from the local unsynchronized free list, and if the local free list is empty, the entire shared free list is moved onto the local free list. This allows objects which do not leave the CPU core they were allocated on to be both allocated and deallocated using unsynchronized operations, and new allocations only perform an atomic operation when the local free list is empty.

Implementations

impl<T> TransferStack<T>

where T: Linked<Links<T>>,

pub const fn new() -> Self

Returns a new TransferStack with no elements.

pub fn push(&self, element: T::Handle)

Pushes element onto the end of this TransferStack, taking ownership of it.

This is an O(1) operation, although it performs a compare-and-swap loop that may repeat if another producer is concurrently calling push on the same TransferStack.

This takes ownership over element through its owning Handle type. If the TransferStack is dropped before the pushed element is removed from the stack, the element will be dropped.

pub fn take_all(&self) -> Stack<T>

Takes all elements currently in this TransferStack, returning a new mutable Stack containing those elements.

This is an O(1) operation which does not allocate memory. It will never loop and does not spin.

Trait Implementations

impl<T> Debug for TransferStack<T>

where T: Linked<Links<T>>,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Drop for TransferStack<T>

where T: Linked<Links<T>>,

fn drop(&mut self)

Executes the destructor for this type.