Struct Bag

pub struct Bag<T, const ARRAY_LEN: usize = DEFAULT_ARRAY_LEN> { /* private fields */ }

Bag is a lock-free concurrent unordered instance container.

Bag is a linearizable concurrent instance container where ARRAY_LEN instances are stored in a fixed-size array, and the rest are managed by its backup container; this makes a Bag especially efficient if the expected number of instances does not exceed ARRAY_LEN.

The maximum value of ARRAY_LEN is limited to usize::BITS / 2 which is the default value, and if a larger value is specified, Bag::new panics.

Implementations

impl<T, const ARRAY_LEN: usize> Bag<T, ARRAY_LEN>

pub fn new() -> Self

Creates a new Bag.

Panics

Panics if the specified ARRAY_LEN value is larger than usize::BITS / 2.

Examples

use scc::Bag;

let bag: Bag<usize, 16> = Bag::new();

pub fn push(&self, val: T)

Pushes an instance of T.

Examples

use scc::Bag;

let bag: Bag<usize> = Bag::default();

bag.push(11);

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

Pops an instance in the Bag if not empty.

Examples

use scc::Bag;

let bag: Bag<usize> = Bag::default();

bag.push(37);

assert_eq!(bag.pop(), Some(37));
assert!(bag.pop().is_none());

pub fn pop_all<B, F: FnMut(B, T) -> B>(&self, init: B, fold: F) -> B

Pops all the entries at once, and folds them into an accumulator.

Examples

use scc::Bag;

let bag: Bag<usize> = Bag::default();

bag.push(7);
bag.push(17);
bag.push(37);

assert_eq!(bag.pop_all(0, |a, v| a + v), 61);

bag.push(47);
assert_eq!(bag.pop(), Some(47));
assert!(bag.pop().is_none());
assert!(bag.is_empty());

pub fn len(&self) -> usize

Returns the number of entries in the Bag.

This method iterates over all the entry arrays in the Bag to count the number of entries, therefore its time complexity is O(N).

Examples

use scc::Bag;

let bag: Bag<usize> = Bag::default();
assert_eq!(bag.len(), 0);

bag.push(7);
assert_eq!(bag.len(), 1);

for v in 0..64 {
   bag.push(v);
}
bag.pop();
assert_eq!(bag.len(), 64);

pub fn is_empty(&self) -> bool

Returns true if the Bag is empty.

Examples

use scc::Bag;

let bag: Bag<usize> = Bag::default();
assert!(bag.is_empty());

bag.push(7);
assert!(!bag.is_empty());

assert_eq!(bag.pop(), Some(7));
assert!(bag.is_empty());

pub fn iter_mut(&mut self) -> IterMut<'_, T, ARRAY_LEN>

Iterates over contained instances for modifying them.

Examples

use scc::Bag;

let mut bag: Bag<usize> = Bag::default();

bag.push(3);
bag.push(3);

assert_eq!(bag.iter_mut().count(), 2);
bag.iter_mut().for_each(|e| { *e += 1; });

assert_eq!(bag.pop(), Some(4));
assert_eq!(bag.pop(), Some(4));
assert!(bag.pop().is_none());

Trait Implementations

impl<T: Debug, const ARRAY_LEN: usize> Debug for Bag<T, ARRAY_LEN>

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

Formats the value using the given formatter.

impl<T> Default for Bag<T, DEFAULT_ARRAY_LEN>

fn default() -> Self

Returns the “default value” for a type.

impl<T, const ARRAY_LEN: usize> Drop for Bag<T, ARRAY_LEN>

fn drop(&mut self)

Executes the destructor for this type.

impl<T, const ARRAY_LEN: usize> FromIterator<T> for Bag<T, ARRAY_LEN>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<'b, T, const ARRAY_LEN: usize> IntoIterator for &'b mut Bag<T, ARRAY_LEN>

type IntoIter = IterMut<'b, T, ARRAY_LEN>

Which kind of iterator are we turning this into?

type Item = &'b mut T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, const ARRAY_LEN: usize> IntoIterator for Bag<T, ARRAY_LEN>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, ARRAY_LEN>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.