Struct treiber_stack::TreiberStack

pub struct TreiberStack<T: Send + Sync> { /* private fields */ }

A thread-safe, lockless, single-ended linked list using atomics to update the head node. Since this structure can be modified concurrently at all times, all operations that calculate size or retrieve contents are retrieving a snapshot-in-time of the state of the stack.

Iteration order is last-in, first-out.

As with any concurrent data structure, all operations are performed against a snapshot of the structure as it existed when the operation was performed.

The key to atomic data structures is that there must be exactly one atomic mutation per operation and exactly one place to do it - more and races become possible. So the only mutable element to this structure is the pointer to the head of the list.

Deletion happens only by popping elements - while it is theoretically possible to delete arbitrary items (by re-stitching an entirely new linked list sans the element to be deleted, repeatedly in the case that the head has changed, but this is subject to the ABA problem and at best, difficult to prove the correctness of).

Uses the arc_swap crate under the hood - which means that returned elements are in an Arc (a necessity of the assign-and-test nature of atomics is that for non-Copy types, it must be possible to pass ownership of the element being added more than once in the case of contention). If you need to mutate the contents, you likely need some indirection in the element type that permits you to pull a mutable instance out of them, such as a Mutex or other smart pointer that allows for interior mutability and is thread-safe.

Implementations

impl<T: Send + Sync> TreiberStack<T>

pub fn initialized_with(item: T) -> Self

Create a new instance with the passed object as the head.

pub fn push<I: Into<T>>(&self, val: I)

Push an item onto the stack, which will become the head.

pub fn pop(&self) -> Option<Arc<T>>

Pop the head item from this stack.

pub fn is_empty(&self) -> bool

Determine if the stack is empty

pub fn len(&self) -> usize

Get the number of elements on the stack at the time this method was called

pub fn clear(&self)

Discard the contents of this stack.

pub fn contains<F: FnMut(&T) -> bool>(&self, predicate: F) -> bool

Determine if any element contained in this stack matches the passed predicate.

pub fn drain(&self) -> Vec<Arc<T>>

Empty this stack, returning a Vec of its contents. Note that the head is detached, emptying the stack immediately, prior to collecting the contents, so additions to the stack while iteration is in progress will not be detected.

In the case that you want to be sure all items have been processed (say, tasks to do during process shutdown), use a while loop testing emptiness for some period of time after initiating shutdown and ensuring no further items can be added.

pub fn drain_replace(&self, new_head: T) -> Vec<Arc<T>>

Empty this stack, returning a Vec of its contents, replacing the head with the passed value in a single atomic swap.

pub fn drain_transforming<R, F: FnMut(Arc<T>) -> R>( &self, transform: F ) -> Vec<R>

Empty this stack, using the passed function to transform the values encountered, and returning a Vec of the result. Note that the resulting Vec will be in reverse order that elements were added, in LIFO order.

pub fn snapshot(&self) -> Vec<Arc<T>>

Take a snapshot of the contents without altering the stack or removing entries.

pub fn peek(&self) -> Option<Arc<T>>

Retrieve a copy of the head element of the stack without altering the stack.

pub fn iter(&self) -> TreiberStackIterator<T>

Create an iterator over this stack. The snapshot the iterator will use is fixed at the time of creation.

Trait Implementations

impl<T> Debug for TreiberStack<T>where T: Debug + Send + Sync,

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

Formats the value using the given formatter.

impl<T: Send + Sync> Default for TreiberStack<T>

Creates a new empty Treiber stack.

fn default() -> Self

Returns the “default value” for a type.

impl<T> Display for TreiberStack<T>where T: Display + Send + Sync,

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

Formats the value using the given formatter.

impl<T: Send + Sync, I: IntoIterator<Item = J>, J: Into<T>> From<I> for TreiberStack<T>

fn from(value: I) -> Self

Converts to this type from the input type.

impl<T: Send + Sync> Into<Vec<Arc<T>, Global>> for TreiberStack<T>

fn into(self) -> Vec<Arc<T>>

Converts this type into the (usually inferred) input type.