Trait orx_concurrent_vec::PinnedVec

pub trait PinnedVec<T>: IntoIterator<Item = T> {
    type Iter<'a>: Iterator<Item = &'a T>
       where T: 'a,
             Self: 'a;
    type IterMut<'a>: Iterator<Item = &'a mut T>
       where T: 'a,
             Self: 'a;
    type IterRev<'a>: Iterator<Item = &'a T>
       where T: 'a,
             Self: 'a;
    type IterMutRev<'a>: Iterator<Item = &'a mut T>
       where T: 'a,
             Self: 'a;

    // Required methods
    fn index_of(&self, element: &T) -> Option<usize>;
    fn contains_reference(&self, element: &T) -> bool;
    fn clear(&mut self);
    fn capacity(&self) -> usize;
    fn capacity_state(&self) -> CapacityState;
    fn extend_from_slice(&mut self, other: &[T])
       where T: Clone;
    fn get(&self, index: usize) -> Option<&T>;
    fn get_mut(&mut self, index: usize) -> Option<&mut T>;
    unsafe fn get_unchecked(&self, index: usize) -> &T;
    unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T;
    fn first(&self) -> Option<&T>;
    fn last(&self) -> Option<&T>;
    unsafe fn first_unchecked(&self) -> &T;
    unsafe fn last_unchecked(&self) -> &T;
    fn len(&self) -> usize;
    fn push(&mut self, value: T);
    fn insert(&mut self, index: usize, element: T);
    fn remove(&mut self, index: usize) -> T;
    fn pop(&mut self) -> Option<T>;
    fn swap(&mut self, a: usize, b: usize);
    fn truncate(&mut self, len: usize);
    fn iter(&self) -> Self::Iter<'_>;
    fn iter_mut(&mut self) -> Self::IterMut<'_>;
    fn iter_rev(&self) -> Self::IterRev<'_>;
    fn iter_mut_rev(&mut self) -> Self::IterMutRev<'_>;
    unsafe fn get_ptr_mut(&mut self, index: usize) -> Option<*mut T>;
    unsafe fn set_len(&mut self, new_len: usize);
    fn try_grow(&mut self) -> Result<usize, PinnedVecGrowthError>;
    unsafe fn grow_to(
        &mut self,
        new_capacity: usize,
        zero_memory: bool
    ) -> Result<usize, PinnedVecGrowthError>;
    unsafe fn concurrently_grow_to(
        &mut self,
        new_capacity: usize,
        zero_memory: bool
    ) -> Result<usize, PinnedVecGrowthError>;
    fn try_reserve_maximum_concurrent_capacity(
        &mut self,
        new_maximum_capacity: usize
    ) -> Result<usize, String>;

    // Provided method
    fn is_empty(&self) -> bool { ... }
}

Trait for vector representations differing from std::vec::Vec by the following:

=> memory location of an element already pushed to the collection never changes unless any of the following mut-methods is called:

• remove, pop,
• insert,
• clear, truncate.

In other words,

=> the mut-methods push or extend_from_slice do not change memory locations of already added elements.

Pinned Elements Guarantee

A PinnedVec guarantees that positions of its elements do not change implicitly.

To be specific, let’s assume that a pinned vector currently has n elements:

Method	Expected Behavior
push(new_element)	does not change the memory locations of the n elements
extend_from_slice(slice)	does not change the memory locations of the first n elements
insert(a, new_element)	does not change the memory locations of the first a elements, where a <= n; elements to the right of the inserted element might be changed, commonly shifted to right
pop()	does not change the memory locations of the first n-1 elements, the n-th element is removed
remove(a)	does not change the memory locations of the first a elements, where a < n; elements to the right of the removed element might be changed, commonly shifted to left
truncate(a)	does not change the memory locations of the first a elements, where a < n

Required Associated Types

type Iter<'a>: Iterator<Item = &'a T> where T: 'a, Self: 'a

Iterator yielding references to the elements of the vector.

type IterMut<'a>: Iterator<Item = &'a mut T> where T: 'a, Self: 'a

Iterator yielding mutable references to the elements of the vector.

type IterRev<'a>: Iterator<Item = &'a T> where T: 'a, Self: 'a

Iterator yielding references to the elements of the vector.

type IterMutRev<'a>: Iterator<Item = &'a mut T> where T: 'a, Self: 'a

Iterator yielding mutable references to the elements of the vector.

Required Methods

fn index_of(&self, element: &T) -> Option<usize>

Returns the index of the element with the given reference.

Note that T: Eq is not required; reference equality is used.

The complexity of this method depends on the particular PinnedVec implementation. However, making use of referential equality, it possible to perform much better than O(n), where n is the vector length.

For the two example implementations, complexity of this method:

• O(1) for FixedVec;
• O(f) for SplitVec where f << n is the number of fragments.

fn contains_reference(&self, element: &T) -> bool

Returns whether or not of the element with the given reference belongs to this vector. In other words, returns whether or not the reference to the element is valid.

Note that T: Eq is not required; memory address is used.

The complexity of this method depends on the particular PinnedVec implementation. However, making use of pinned element guarantees, it possible to perform much better than O(n), where n is the vector length.

For the two example implementations, complexity of this method:

• O(1) for FixedVec;
• O(f) for SplitVec where f << n is the number of fragments.

fn clear(&mut self)

Clears the vector, removing all values.

Note that this method has no effect on the allocated capacity of the vector.

Safety

clear operation is safe both when T: NotSelfRefVecItem or not due to the following:

• elements holding references to each other will be cleaned all together; hence, none of them can have an invalid reference;
• we cannot keep holding a reference to a vector element defined aliased the clear call, since clear requires a mut reference.

fn capacity(&self) -> usize

Returns the total number of elements the vector can hold without reallocating.

fn capacity_state(&self) -> CapacityState

Provides detailed information of capacity state of the pinned vector.

This information contains the current capacity which can be obtained by PinnedVec::capacity() method and extends with additional useful information.

fn extend_from_slice(&mut self, other: &[T])

where T: Clone,

Clones and appends all elements in a slice to the Vec.

Iterates over other, clones each element, and then appends it to this vec. The other slice is traversed in-order.

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

Returns a reference to an element with the given index returns None if the index is out of bounds.

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

Returns a mutable reference to an element with the given index returns None if the index is out of bounds.

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

Returns a reference to an element without doing bounds checking.

For a safe alternative see get.

Safety

Calling this method with an out-of-bounds index is [undefined behavior] even if the resulting reference is not used.

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

Returns a mutable reference to an element without doing bounds checking.

For a safe alternative see get_mut.

Safety

Calling this method with an out-of-bounds index is [undefined behavior] even if the resulting reference is not used.

fn first(&self) -> Option<&T>

Returns a reference to the first element of the vector; returns None if the vector is empty.

fn last(&self) -> Option<&T>

Returns a reference to the last element of the vector; returns None if the vector is empty.

unsafe fn first_unchecked(&self) -> &T

Returns a reference to the first element of the vector without bounds checking.

For a safe alternative see first.

Safety

Calling this method when the vector is empty is [undefined behavior] even if the resulting reference is not used.

unsafe fn last_unchecked(&self) -> &T

Returns a reference to the last element of the vector without bounds checking.

For a safe alternative see last.

Safety

Calling this method when the vector is empty is [undefined behavior] even if the resulting reference is not used.

fn len(&self) -> usize

Returns the number of elements in the vector, also referred to as its length.

fn push(&mut self, value: T)

Appends an element to the back of a collection.

fn insert(&mut self, index: usize, element: T)

Inserts an element at position index within the vector, shifting all elements after it to the right.

Panics

Panics if index >= len.

fn remove(&mut self, index: usize) -> T

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

Panics

Panics if index is out of bounds.

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

Removes the last element from a vector and returns it, or None if it is empty.

fn swap(&mut self, a: usize, b: usize)

Swaps two elements in the slice.

If a equals to b, it’s guaranteed that elements won’t change value.

Arguments

• a - The index of the first element
• b - The index of the second element.

fn truncate(&mut self, len: usize)

Shortens the vector, keeping the first len elements and dropping the rest.

If len is greater than the vector’s current length, this has no effect.

fn iter(&self) -> Self::Iter<'_>

Returns an iterator to elements of the vector.

fn iter_mut(&mut self) -> Self::IterMut<'_>

Returns an iterator of mutable references to elements of the vector.

fn iter_rev(&self) -> Self::IterRev<'_>

Returns a reversed back-to-front iterator to elements of the vector.

fn iter_mut_rev(&mut self) -> Self::IterMutRev<'_>

Returns a reversed back-to-front iterator mutable references to elements of the vector.

unsafe fn get_ptr_mut(&mut self, index: usize) -> Option<*mut T>

Returns a mutable reference to the index-th element of the vector.

Returns None if index-th position does not belong to the vector; i.e., if index is out of capacity.

Safety

This method allows to write to a memory which is greater than the vector’s length. On the other hand, it will never return a pointer to a memory location that the vector does not own.

unsafe fn set_len(&mut self, new_len: usize)

Forces the length of the vector to new_len.

This is a low-level operation that maintains none of the normal invariants of the type.

Safety

• new_len must be less than or equal to capacity().
• The elements at old_len..new_len must be initialized.

fn try_grow(&mut self) -> Result<usize, PinnedVecGrowthError>

Attempts to increase the capacity of the pinned vector with default additional amount defined by the specific implementation.

The method:

• ensures that all already allocated elements stay pinned their memory locations,
• and returns the new capacity which is greater than or equal to the current capacity if the operation succeeds,
• corresponding Err if it fails.

unsafe fn grow_to( &mut self, new_capacity: usize, zero_memory: bool ) -> Result<usize, PinnedVecGrowthError>

Increases the capacity of the vector at least up to the new_capacity:

• has no affect if new_capacity <= self.capacity(), and returns Ok(self.capacity());
• increases the capacity to x >= new_capacity otherwise if the operation succeeds.

When zero_memory is set to true, the pinned vector will zero out the new allocated memory corresponding to positions starting from self.len() to new_capacity.

Safety

This method is unsafe due to the internal guarantees of pinned vectors.

• A SplitVec, on the other hand, can grow to the new_capacity without any problem. However, it is not designed to have intermediate empty fragments, while grow_to can leave such fragments. Hence, the caller is responsible for handling this.

unsafe fn concurrently_grow_to( &mut self, new_capacity: usize, zero_memory: bool ) -> Result<usize, PinnedVecGrowthError>

Increases the capacity of the vector at least up to the new_capacity:

• has no affect if new_capacity <= self.capacity(), and returns Ok(self.capacity());
• increases the capacity to x >= new_capacity otherwise if the operation succeeds.

It differs from grow_to method by the following:

• as all PinnedVec methods, grow_to is responsible for keeping elements pinned to their locations;
• while concurrently_grow_to provides additional guarantees so that meta information storing memory locations of the elements also keep pinned to their locations.

This additional guarantee is irrelevant for single-threaded programs, while critical for concurrent programs.

When zero_memory is set to true, the pinned vector will zero out the new allocated memory corresponding to positions starting from self.len() to new_capacity.

Safety

This method is unsafe due to the internal guarantees of pinned vectors.

• A SplitVec, on the other hand, can grow to the new_capacity without any problem. However, it is not designed to have intermediate empty fragments, while grow_to can leave such fragments. Hence, the caller is responsible for handling this.

fn try_reserve_maximum_concurrent_capacity( &mut self, new_maximum_capacity: usize ) -> Result<usize, String>

Tries to make sure that the pinned vector is capable of growing up to the given new_maximum_capacity safely in a concurrent execution. Returns Ok of the new maximum capacity which is greater than or equal to the requested new_maximum_capacity; or the corresponding Error if the attempt fails.

Importantly, note that this method does not lead to reserving memory for new_maximum_capacity elements. It only makes sure that such an allocation will be possible with shared references which can be required in concurrent execution.

Provided Methods

fn is_empty(&self) -> bool

Returns true if the vector contains no elements.

Object Safety

This trait is not object safe.

Implementors

impl<T> PinnedVec<T> for FixedVec<T>

type Iter<'a> = Iter<'a, T> where T: 'a, FixedVec<T>: 'a

type IterMut<'a> = IterMut<'a, T> where T: 'a, FixedVec<T>: 'a

type IterRev<'a> = Rev<Iter<'a, T>> where T: 'a, FixedVec<T>: 'a

type IterMutRev<'a> = Rev<IterMut<'a, T>> where T: 'a, FixedVec<T>: 'a

impl<T, G> PinnedVec<T> for SplitVec<T, G>

where G: Growth,

type Iter<'a> = Iter<'a, T> where T: 'a, SplitVec<T, G>: 'a

type IterMut<'a> = IterMut<'a, T> where T: 'a, SplitVec<T, G>: 'a

type IterRev<'a> = IterRev<'a, T> where T: 'a, SplitVec<T, G>: 'a

type IterMutRev<'a> = IterMutRev<'a, T> where T: 'a, SplitVec<T, G>: 'a