Skip to main content

ConcurrentShardedStack

Struct ConcurrentShardedStack 

Source
pub struct ConcurrentShardedStack<T> { /* private fields */ }
Expand description

Concurrent sharded Treiber stack.

Ordering is LIFO within each shard, not across shards. An unsuccessful pop is a scan, not an atomic snapshot: Empty can be returned even when the stack remained nonempty throughout the call. Closing also takes effect one shard at a time; see close.

Implementations§

Source§

impl<T> ConcurrentShardedStack<T>

Source

pub fn new() -> Self

Creates a stack using available_parallelism() as concurrency hint.

Source

pub fn with_concurrency(shard_count: usize) -> Self

Creates a stack with exact shard count.

Panics if:

  • shard_count == 0
  • shard_count is not power of two
Source

pub fn push(&self, value: T) -> Result<(), PushError<T>>

Pushes a value into the stack.

Returns Err(PushError::Closed(value)) if this thread’s shard is closed. While close is in progress, some shards may reject pushes while others still accept them. After close returns, every shard rejects pushes.

Source

pub fn pop(&self) -> Result<T, PopError>

Pops a value from the stack non-blocking.

Scan order:

  • first scan the current thread’s own shard;
  • then scan the shard whose last binary bit differs;
  • then scan shards whose next binary bit differs;
  • continue widening the differing-bit window until all shards are scanned.

For example, with 8 shards and local shard start, the XOR masks are:

0,
1,
2, 3,
4, 5, 6, 7

So the actual scan order is:

start,
start ^ 1,
start ^ 2, start ^ 3,
start ^ 4, start ^ 5, start ^ 6, start ^ 7

Returns Err(PopError::Empty) if no element is found and at least one shard is still observed open. This is not a consistent snapshot: other threads can push into an already-scanned shard and drain a later shard, so Empty can occur even if the stack was never globally empty during the call. Consumers with active producers should retry rather than use Empty as a completion signal.

Returns Err(PopError::Closed) if no element is found and every shard is observed closed. Unlike Empty, this is terminal: closed shards cannot receive more elements.

Source

pub fn close(&self) -> bool

Closes every shard. Existing elements can still be popped.

Closure propagates one shard at a time. During the call, a push can be rejected on one shard while a later push succeeds on another, and is_closed can still return false after a rejected push. Once this method returns, all shards are closed.

Returns true if this call closed at least one shard. Concurrent calls can both return true; the result does not identify a unique closer.

Source

pub fn is_closed(&self) -> bool

Checks whether every shard is closed.

Source

pub fn shard_count(&self) -> usize

Trait Implementations§

Source§

impl<T> Default for ConcurrentShardedStack<T>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<T> Drop for ConcurrentShardedStack<T>

Source§

fn drop(&mut self)

Executes the destructor for this type. Read more
Source§

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)
Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned. Read more
Source§

impl<T: Send> Send for ConcurrentShardedStack<T>

Source§

impl<T: Send> Sync for ConcurrentShardedStack<T>

Auto Trait Implementations§

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

Source§

const ALIGN: usize

The alignment of pointer.
Source§

type Init = T

The type for initializers.
Source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
Source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
Source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
Source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
Source§

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

Source§

type Error = !

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

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

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

Source§

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.