Struct dycovec::DycoVec

pub struct DycoVec<T> { /* fields omitted */ }

A dynamically-allocated, concurrent vector.

DycoVecs are thread-safe vectors that support random access, iteration, and tail pushing in an O(1), wait-free* manner, and that's it! It's possible, given &mut self, to clear self and mutate elements, but to do so without &mut self requires wrapping T in a type such as Mutex.

Technical Details

The technical details of DycoVecs are something you're likely to find boring and uninteresting. Read below if you wish, but beware!

Memory Use

Storage is allocated in lazily-allocated individually-contiguous chunks. This means that, given a first chunk capacity of n, pushing less than n (but at least one) elements uses the same memory as pushing n elements, while pushing n + 1 elements makes the DycoVec now have two segments: the first chunk, and a larger second chunk.

Almost Wait-free

The DycoVec is almost always wait-free to push on to, and is otherwise still lock-free. The only exception to wait-freedom is when a segment has filled and a new one is being allocated. This will result in every thread simultaneously attempting to enter a specific critical section. The first to do so will allocate the segment. After finishing, all other threads vying for the lock will enter the critical section as appropriate, notice the segment is already allocated, and immediately unlock. So, the maximum hold-up will be O(n) (n being the number of threads). But, as a reminder, this whole parade only happens when the DycoVec has yet to be allocated.

The only other time the lock is locked is during cloning as to prevent an incomplete allocation from providing bad data for the clone.

Implementations

impl<T> DycoVec<T>

pub fn new() -> Self

Create a new DycoVec with zero length.

The DycoVec will no allocate memory until elements are pushed onto it.

pub fn from_boxed_slice(s: Box<[T]>) -> Self

Create a new DycoVec from a boxed slice.

pub unsafe fn get_unchecked(&self, index: usize) -> &T

Index self by index

pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T

Mutably index self by index

pub fn get(&self, index: usize) -> Option<&T>

Index self by index

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Mutably index self by index

pub fn clear(&mut self)

Clear all elements in self.

Drops all elements stored in self without losing the allocated space.

pub fn push(&self, t: T) -> usize

Push an element to the end of self and return the new index.

pub fn len(&self) -> usize

Get the number of elements in self.

pub fn is_empty(&self) -> bool

Returns true if the DycoVec contains no elements.

pub const fn iter(&self) -> Iter<'_, T>

Create an immutable iterator over the elements of self.

pub fn into_vec(self) -> Vec<T>

Consumes the DycoVec, returning a Vec containing the elements.

Trait Implementations

impl<T: Clone> Clone for DycoVec<T>

pub fn clone(&self) -> Self

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for DycoVec<T>

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

Formats the value using the given formatter.

impl<T> Default for DycoVec<T>

pub fn default() -> Self

Returns the "default value" for a type.

impl<T: Eq> Eq for DycoVec<T>

impl<T> Extend<T> for DycoVec<T>

pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T: 'a> From<&'a DycoVec<T>> for Vec<&'a T>

pub fn from(dv: &'a DycoVec<T>) -> Self

Performs the conversion.

impl<T> From<DycoVec<T>> for Vec<T>

pub fn from(dv: DycoVec<T>) -> Self

Performs the conversion.

impl<T> FromIterator<T> for DycoVec<T>

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

Creates a value from an iterator.

impl<T: Hash> Hash for DycoVec<T>

pub fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<T> Index<usize> for DycoVec<T>

type Output = T

The returned type after indexing.

pub fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for DycoVec<T>

pub fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<T> IntoIterator for DycoVec<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T: 'a> IntoIterator for &'a DycoVec<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

pub fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Ord> Ord for DycoVec<T>

pub fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

#[must_use]pub fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]pub fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]pub fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq<DycoVec<T>> for DycoVec<T>

pub fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<T: PartialOrd> PartialOrd<DycoVec<T>> for DycoVec<T>

pub fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

#[must_use]pub fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]pub fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]pub fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.