Struct 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.

Example:

let stack = treiber_stack::TreiberStack::initialized_with(42_usize);
assert!(!stack.is_empty());
assert_eq!(42_usize, *stack.peek().unwrap());

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

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

let stack = treiber_stack::TreiberStack::default();
assert!(stack.is_empty()); // stack is initially empty
stack.push(23_usize); // push one element

assert!(!stack.is_empty()); // the stack is not empty

assert_eq!(23_usize, *stack.pop().unwrap()); // pop the element back off
assert!(stack.is_empty()); // the stack is back to empty

pub fn push_arc(&self, a: Arc<T>)

Push an extant Arc onto the stack, which will become the head. This method is useful for cases where values are swapped between TreiberStacks or examined and replaced, making cloning the value out of the Arc just to have it put in a new Arc when it is pushed adds overhead.

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

Pop the head item from this stack.

Example:

let stack = treiber_stack::TreiberStack::from(vec![3_usize, 2, 1]);
assert_eq!(3, stack.len());
assert_eq!(1_usize, *stack.pop().unwrap());
assert_eq!(2_usize, *stack.pop().unwrap());
assert_eq!(3_usize, *stack.pop().unwrap());
assert_eq!(None, stack.pop());
assert!(stack.is_empty());

pub fn pop_raw(&self) -> Option<T>

where T: Copy,

Pop a value, if any, taking it out of the Arc it is stored in internally. Only available when T: Copy. Example:

let stack : treiber_stack::TreiberStack<usize> = treiber_stack::TreiberStack::from(vec![3_usize, 2, 1]);
assert_eq!(Some(1_usize), stack.pop_raw());
assert_eq!(Some(2_usize), stack.pop_raw());
assert_eq!(Some(3_usize), stack.pop_raw());
assert!(stack.pop_raw().is_none());
assert!(stack.is_empty());

pub fn drain_all_into<F: FnMut(Arc<T>)>(&self, f: F) -> usize

Drain all items from this Treiber stack, repeatedly calling the passed FnMut with each item, returning the number of elements passed to f. The head of the stack is replaced by an empty cell at the start of this method, so any concurrent write operations will not be reflected in the set of elements passed to f, and there should be no expectation that the stack is actually empty under concurrency at the end of this call. Prefer this method to drain_into() where the stack should be emptied, as it cannot encounter contention after the initial head-swap.

Example:

let stack: treiber_stack::TreiberStack<usize> = treiber_stack::TreiberStack::from(vec![6_usize, 5, 4, 3, 2, 1]);
let mut v = Vec::with_capacity(6);
stack.drain_all_into(|item| {
    v.push(*item);
});
assert_eq!(vec![1, 2, 3, 4, 5, 6], v);

pub fn drain_all_copy<F: FnMut(T)>(&self, f: F) -> usize

where T: Copy,

Drain all items from this Treiber stack, where items are Copy and can be removed from an Arc, repeatedly calling the passed FnMut with each item, returning the number of elements passed to f. The head of the stack is replaced by an empty cell at the start of this method, so any concurrent write operations will not be reflected in the set of elements passed to f, and there should be no expectation that the stack is actually empty under concurrency at the end of this call.

Example:

let stack: treiber_stack::TreiberStack<usize>  = treiber_stack::TreiberStack::from(vec![6_usize, 5, 4, 3, 2, 1]);
let mut v = Vec::with_capacity(6);
stack.drain_all_into(|item| {
    v.push(*item);
});
assert_eq!(vec![1, 2, 3, 4, 5, 6], v);

pub fn drain_into<F: FnMut(Arc<T>) -> bool>(&self, f: F) -> usize

Drain items from this Treiber stack, repeatedly calling the passed FnMut with each item until it returns false, returning the number of elements passed to f.

Example:

let stack = treiber_stack::TreiberStack::from(vec![6_usize, 5, 4, 3, 2, 1]);
let mut v = Vec::with_capacity(6);
stack.drain_into(|item| {
    v.push(*item);
    *item < 3
});
assert_eq!(vec![1, 2, 3], v);
assert_eq!(3, stack.len());
assert_eq!(vec![4_usize, 5, 6], stack.drain_transforming(|item| *item));

pub fn is_empty(&self) -> bool

Determine if the stack currently contains no elements

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

Example:

let stack : treiber_stack::TreiberStack<usize> = treiber_stack::TreiberStack::from(vec![1_usize, 2, 3]);
assert_eq!(3, stack.len());
stack.clear();
assert_eq!(0, stack.len());

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

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

let stack : treiber_stack::TreiberStack<usize> = treiber_stack::TreiberStack::from(vec![1_usize, 2, 3]);
assert!(stack.contains(|item| *item == 2));
assert!(!stack.contains(|item| *item == 23));

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. Example:

let stack = treiber_stack::TreiberStack::from(vec![3_usize, 2, 1]);
let drained = stack.drain();
assert_eq!(vec![std::sync::Arc::new(1_usize),
    std::sync::Arc::new(2_usize),
    std::sync::Arc::new(3_usize)], drained);

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. Example:

let stack = treiber_stack::TreiberStack::from(vec![3_usize, 2, 1]);
let drained = stack.drain_replace(52);
assert_eq!(vec![std::sync::Arc::new(1_usize),
    std::sync::Arc::new(2_usize),
    std::sync::Arc::new(3_usize)], drained);    
assert_eq!(1, stack.len());
assert_eq!(52, *stack.pop().unwrap());

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.

let stack : treiber_stack::TreiberStack<usize>
    = treiber_stack::TreiberStack::from(vec![3_usize, 2, 1]);
let drained = stack.drain_transforming(|item| *item * 10);
assert_eq!(vec![10_usize, 20, 30], drained);
assert!(stack.is_empty());

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

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

let stack = treiber_stack::TreiberStack::from(vec![3_usize, 2, 1]);
let snapshot = stack.snapshot();
assert_eq!(vec![std::sync::Arc::new(1_usize),
    std::sync::Arc::new(2_usize),
    std::sync::Arc::new(3_usize)], snapshot);    
assert_eq!(3, stack.len());
assert_eq!(1_usize, *stack.pop().unwrap());

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

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

let stack = treiber_stack::TreiberStack::from(vec![2_usize, 1]);
assert_eq!(1_usize, *stack.peek().unwrap()); // should be the last added element
assert_eq!(1_usize, *stack.pop().unwrap()); // head should be unaltered

assert_eq!(2_usize, *stack.peek().unwrap()); // now 2 is the head
assert_eq!(2_usize, *stack.pop().unwrap()); // pop that
assert_eq!(None, stack.peek()); // nothing to peek at

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.

Example:

let stack = treiber_stack::TreiberStack::from(vec![2_usize, 1]);
let mut copied_out = Vec::with_capacity(2);
// Pushing new items will *not* cause them to be visible in this iterator
for item in stack.iter() {
    stack.push(*item * 10);
    copied_out.push(*item);
}
// But they will now be present in the stack
assert_eq!(vec![20_usize, 10_usize, 1_usize, 2_usize], stack.drain_transforming(|item| *item));

pub fn exchange_contents(&self, other: &Self)

Swap the head nodes between two TreiberStacks of the same type.

Example:

let a : treiber_stack::TreiberStack<usize> = treiber_stack::TreiberStack::from(vec![3_usize, 2, 1]);
let b : treiber_stack::TreiberStack<usize> = treiber_stack::TreiberStack::from(vec![6_usize, 5, 4]);
a.exchange_contents(&b);
assert_eq!(4, a.pop_raw().unwrap());
assert_eq!(5, a.pop_raw().unwrap());
assert_eq!(6, a.pop_raw().unwrap());
assert!(a.is_empty());
assert_eq!(1, b.pop_raw().unwrap());
assert_eq!(2, b.pop_raw().unwrap());
assert_eq!(3, b.pop_raw().unwrap());
assert!(b.is_empty());

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>>> for TreiberStack<T>

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

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