Struct cordyceps::stack::TransferStack

source ·
pub struct TransferStack<T: Linked<Links<T>>> { /* private fields */ }
Expand description

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:

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§

source§

impl<T> TransferStack<T>
where T: Linked<Links<T>>,

source

pub const fn new() -> Self

Available on non-loom only.

Returns a new TransferStack with no elements.

source

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.

source

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§

source§

impl<T> Debug for TransferStack<T>
where T: Linked<Links<T>>,

source§

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

Formats the value using the given formatter. Read more
source§

impl<T> Drop for TransferStack<T>
where T: Linked<Links<T>>,

source§

fn drop(&mut self)

Executes the destructor for this type. Read more

Auto Trait Implementations§

§

impl<T> !Freeze for TransferStack<T>

§

impl<T> RefUnwindSafe for TransferStack<T>

§

impl<T> Send for TransferStack<T>

§

impl<T> Sync for TransferStack<T>

§

impl<T> Unpin for TransferStack<T>

§

impl<T> UnwindSafe for TransferStack<T>
where T: RefUnwindSafe,

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.