Struct orx_imp_vec::ImpVec

pub struct ImpVec<T, P = SplitVec<T>>
where
    P: PinnedVec<T>,
{ /* private fields */ }

A data structure to enable conveniently building performant self referential collections such as trees, graphs and linked lists.

ImpVec 👿 is a wrapper around a PinnedVec which guarantees that memory location of its elements do not change unless elements are removed from the vector. In addition to dereferencing the PinnedVec methods, ImpVec adds the following methods which are specialized for defining and building self referential collections using plain & references:

fn set_next(&mut self, element: &T, next: Option<&'a T>)
fn set_prev(&mut self, element: &T, prev: Option<&'a T>)
fn replace_at(&mut self, at: usize, new_value: T) -> Option<T>
unsafe fn push_get_ref(&self, value: T) -> &T
unsafe fn move_get_ref(&mut self, source_idx: usize, destination_idx: usize, fill_source_with: T) -> Option<(&T, &T)>

Implementations

impl<T, P: PinnedVec<T>> ImpVec<T, P>

pub fn new() -> Self

where P: Default,

Creates a new empty vector.

pub fn into_pinned(self) -> P

Converts the ImpVec into underlying PinnedVec.

This operation corresponds to moving the pinned vec out of a ref cell; and hence, is not expensive. Likewise, the pinned vec can then be converted back into an imp vec by wrapping it up by a ref cell under the hood.

Converting an ImpVec to PinnedVec is useful for the following reasons:

• It reduces one level of abstraction by getting rid of the ref cell, and hence, achieving SplitVec or FixedVec (same as std vec) performance depending on the type of the pinned vec.
• It means that immutable pushes are not allowed anymore.
  • In a vector holding inter-element references, this means that such references will not be added or removed.
  • In other words, it safely ensures that the building of the structure is completed.

Examples

You may see and example back-and-forth conversions between a PinnedVec.

Complete type annotations are not needed byt added to make the conversions explicitly visible.

use orx_imp_vec::prelude::*;

let mut imp: ImpVec<char, SplitVec<char, Doubling>> = SplitVec::with_doubling_growth().into();
for _ in 0..3 {
    imp.push('s');
}
assert_eq!(imp, vec!['s', 's', 's']);

let mut split: SplitVec<char, Doubling> = imp.into_pinned();
assert_eq!(split, vec!['s', 's', 's']);

let mut imp_again: ImpVec<_, _> = split.into();
imp_again.push('s');
assert_eq!(imp_again, vec!['s', 's', 's', 's']);

let split_back = imp_again.into_pinned();
assert_eq!(split_back, vec!['s', 's', 's', 's']);

impl<'a, T, P> ImpVec<T, P>

where P: PinnedVec<T> + 'a,

pub fn replace_at(&mut self, at: usize, new_value: T) -> Option<T>

Replaces the data at the at-th position of the vector with the new_value; and returns the old data at this position.

Does nothing and returns None if at is out of bounds.

Safety

This method is safe due to the following:

• acts only if at is within the storage owned by the vector.
• all references to the element at the at-th position are still valid since the length of the vector does not change.
• the underlying data at this position change; however, this is done with a &mut self reference.

pub unsafe fn push_get_ref<'b>(&'b mut self, value: T) -> &'a T

where P: 'a, 'a: 'b,

Appends an element to the back of a collection and returns a reference to it.

Unlike std::vec::Vec or orx_split_vec::SplitVec; push operation for ImpVec does not require a mutable reference (see Safety section).

This is a crucial method for building self-referential-collections which is the underlying motivation of an ImpVec. See the Motivation section for details.

Examples

use orx_imp_vec::prelude::{ImpVec, PinnedVec};

let mut vec: ImpVec<_> = ImpVec::new();

let ref1 = unsafe { vec.push_get_ref(1) };
let ref_elem_addr = ref1 as *const i32;

vec.push(2);
vec.push(3);
let ref4 = unsafe { vec.push_get_ref(4) };

// capacity is expaneded here from 4 to 8; however, in chunks;
// therefore, data is not moved around and the references remain valid.
let ref5 = unsafe { vec.push_get_ref(5) };


assert_eq!(ref1, &1);
assert_eq!(ref4, &4);
assert_eq!(ref5, &5);
assert_eq!(vec, [1, 2, 3, 4, 5]);

let ref_elem_addr_after_growth = &vec[0] as *const i32;
assert_eq!(ref_elem_addr, ref_elem_addr_after_growth);

As you may see below, any mutable method that can possibly invalidate the references are not allowed.

use orx_imp_vec::prelude::*;

let mut vec: ImpVec<_, _> = SplitVec::with_linear_growth(10).into(); // mut required for the `insert`
let ref1 = unsafe { vec.push_get_ref(1) };
vec.push(2);
vec.push(3);

assert_eq!(ref1, &1);
assert_eq!(vec, [1, 2, 3]);

vec.insert(0, 42);
assert_eq!(vec, [42, 1, 2, 3]);

// below line does not compile as the 'insert' call breaks reference 'ref1'
// let value1 = *ref1;

Safety

This method is unsafe due to the broken lifetime relation of the returned reference from this vector. In brief, the returned reference can outlive this vector which is undefined behavior (UB). The following example demonstrates that this UB can be experienced.

use orx_imp_vec::prelude::*;

let mut imp: ImpVec<_> = ImpVec::new();
let first = unsafe { imp.push_get_ref('a') };

assert_eq!(&'a', &imp[0]);
assert_eq!(&'a', first);

drop(imp);

// assert_eq!(&'a', &imp[0]); // this should NOT compile, and correctly does NOT compile

// the following should also NOT compile; however, it does!
assert_eq!(&'a', first);

Due to the demonstrated problem, push_get_ref method is unsafe and should be used carefully.

In particular, caller we must take the responsibility to make sure that the returned reference does not outlive the vector. The wrapper structures or methods can safely be used once this guarantee is provided.

Motivation

The reason this method exists is to narrow down the unsafe code and complexity. To be precise, the entire complexity of building self-referential-collections can be narrowed to the limited usage of two main unsafe methods push_get_ref and crate::ImpVec::move_get_ref.

Consider for instance two doubly-linked list implementations std::collections::LinkedList and orx_linked_list::LinkedList.

std::collections::LinkedList is a relatively low level implementation with heavy use of raw pointers. The file https://doc.rust-lang.org/src/alloc/collections/linked_list.rs.html contains unsafe keyword used more than 60 times. The unsafe code blocks contain reads/writes to memory through raw pointers which is dangerous and allows much more unsafety than required for defining a linked list.

A higher level implementation can be found here https://crates.io/crates/orx-linked-list which is built on an underlying ImpVec storage. Complete repository contains the unsafe keyword seven times corresponding to repeated usage of only three methods:

• ImpVec::push_get_ref
• ImpVec::move_get_ref
• ImpVec::unsafe_truncate which actually is a deref method from PinnedVec::unsafe_truncate

In brief, a full-fetched doubly-linked-list can be built in rust:

• with thin references
• without smart pointers
• without any raw pointers
• by using only three unsafe methods which are specialized for building self referential collections

Furthermore, it performs significantly faster proving the performance benefit by cache locality which can be attained by putting nodes close to each other within an ImpVec.

pub unsafe fn move_get_ref<'b>( &mut self, source_idx: usize, destination_idx: usize, fill_source_with: T ) -> Option<(&'b T, &'b T)>

where 'a: 'b,

Performs the following:

• copies the data at source_idx onto the element at destination_idx;
• replaces the data at the source_idx with the fill_source_with;
• returns references to the new values of the elements at (source_idx, destination_idx).

Does nothing and returns None if any of source_idx and destination_idx is out of bounds.

Note that after the move operation

• value at the destination_idx will be equal to the prior value at the source_idx, and
• value at the source_idx will be equal to fill_source_with.

Example

use orx_imp_vec::*;

let mut imp: ImpVec<_> = ['a', 'b', 'c'].into_iter().collect();

assert_eq!(&['a', 'b', 'c'], &imp);

let (ref0, ref1) = unsafe { imp.move_get_ref(0, 1, 'x') }.unwrap();

assert_eq!(&imp[0], &'x');
assert_eq!(&imp[1], &'a');

assert_eq!(ref0, &'x');
assert_eq!(ref1, &'a');

Safety

This method is safe due to the following:

• acts only if source_idx and destination_idx are within the storage owned by the vector.
• all references to the element at the source_idx-th position and destination_idx-th position are still valid since the length of the vector does not change.
• the underlying data at these positions change; however, this is done with a &mut self reference.

On the other hand, this method is unsafe due to the broken lifetime relation of the returned references from this vector. In brief, the returned references can outlive this vector which is undefined behavior (UB). The following example demonstrates that this UB can be experienced.

use orx_imp_vec::*;

let mut imp: ImpVec<_> = ['a', 'b', 'c'].into_iter().collect();

assert_eq!(&['a', 'b', 'c'], &imp);

let (ref0, ref1) = unsafe { imp.move_get_ref(0, 1, 'x') }.unwrap();

assert_eq!(&imp[0], &'x');
assert_eq!(&imp[1], &'a');

assert_eq!(ref0, &'x');
assert_eq!(ref1, &'a');

drop(imp);

// following two lines should NOT compile, and correctly do NOT compile
// assert_eq!(&imp[0], &'x');
// assert_eq!(&imp[1], &'a');

// the following lines should also NOT compile; however, they do!
assert_eq!(ref0, &'x');
assert_eq!(ref1, &'a');

Due to the demonstrated problem, move_get_ref method is unsafe and should be used carefully.

In particular, caller we must take the responsibility to make sure that the returned references does not outlive the vector. The wrapper structures or methods can safely be used once this guarantee is provided.

Motivation

The reason this method exists is to narrow down the unsafe code and complexity. To be precise, the entire complexity of building self-referential-collections can be narrowed to the limited usage of two main unsafe methods move_get_ref and crate::ImpVec::push_get_ref.

Consider for instance two doubly-linked list implementations std::collections::LinkedList and orx_linked_list::LinkedList.

std::collections::LinkedList is a relatively low level implementation with heavy use of raw pointers. The file https://doc.rust-lang.org/src/alloc/collections/linked_list.rs.html contains unsafe keyword used more than 60 times. The unsafe code blocks contain reads/writes to memory through raw pointers which is dangerous and allows much more unsafety than required for defining a linked list.

A higher level implementation can be found here https://crates.io/crates/orx-linked-list which is built on an underlying ImpVec storage. Complete repository contains the unsafe keyword seven times corresponding to repeated usage of only three methods:

• ImpVec::push_get_ref
• ImpVec::move_get_ref
• ImpVec::unsafe_truncate which actually is a deref method from PinnedVec::unsafe_truncate

In brief, a full-fetched doubly-linked-list can be built in rust:

• with thin references
• without smart pointers
• without any raw pointers
• by using only three unsafe methods which are specialized for building self referential collections

Furthermore, it performs significantly faster proving the performance benefit by cache locality which can be attained by putting nodes close to each other within an ImpVec.

impl<'a, T, P> ImpVec<T, P>

where P: PinnedVec<T> + 'a, T: SelfRefNext<'a> + 'a,

pub fn set_next(&mut self, element: &T, next: Option<&'a T>)

Using interior mutability peforms the following:

• element.set_next(next)

so that element will point to the next element after the operation.

Panics

Panics:

• if element does not belong to this vector, or
• if next is of Some variant and underlying reference does not belong to this vector.

Safety

Due to the guards defined in the Panics section, element and next (if some) belong to the same vector living together and sharing the same lifetime.

Example

This is one of the specialized methods for building self-referential-collections when the elements implement orx_pinned_vec::SelfRefNext.

It is not trivial to provide a partial and trivial example. However, the usefulness of this method can be demonstrated by its usage within the orx_linked_list::LinkedList implementation.

The crate defines a double-linked-list Node with optional next and prev references. Node implements orx_pinned_vec::SelfRefNext and orx_pinned_vec::SelfRefPrev; therefore, we can use ImpVec::set_next method. The following code block is the push_back method implementation of the LinkedList:

pub fn push_back(&mut self, value: T) {
    match self.back_node() {
        None => self.push_first_node(value),
        Some(old_back) => {
            let node = Node::active(value, Some(old_back), None);
            let back = unsafe { self.vec.push_get_ref(node) };
            self.vec.set_next(old_back, Some(back));
            self.slice = LinkedListSlice::new(self.len() + 1, self.front_node(), Some(back));
        }
    }
}

In the trivial case when there is no back_node (the list is empty), we simply push the value as the first node.

Otherwise:

• We get a reference to the back node, we’ll now call it old_back since it will no longer be the back of the list.
• We create a new node for the new value:
  • previous node of node is set to Some(old_back),
  • next node of node is None since it is the new back of the list.
• We use the push_get_ref method to push node to the storage vector and get a reference to it.
  • SAFETY: we must make sure that the reference back does not outlive self; which is satisfied here.
• We tell our self.vec which is an ImpVec to set the next of old_back to Some(back) to link the old back to the new back.
• Then, we set that our list now is one element longer, with the old self.front_node() and new back node which is Some(back).

impl<'a, T, P> ImpVec<T, P>

where P: PinnedVec<T> + 'a, T: SelfRefPrev<'a> + 'a,

pub fn set_prev(&mut self, element: &T, prev: Option<&'a T>)

Using interior mutability peforms the following:

• element.set_prev(prev)

so that element will point to the prev element after the operation.

Panics

Panics:

• if element does not belong to this vector, or
• if prev is of Some variant and underlying reference does not belong to this vector.

Safety

Due to the guards defined in the Panics section, element and prev (if some) belong to the same vector living together and sharing the same lifetime.

Example

This is one of the specialized methods for building self-referential-collections when the elements implement orx_pinned_vec::SelfRefNext.

It is not trivial to provide a partial and trivial example. However, the usefulness of this method can be demonstrated by its usage within the orx_linked_list::LinkedList implementation.

The crate defines a double-linked-list Node with optional next and prev references. Node implements orx_pinned_vec::SelfRefNext and orx_pinned_vec::SelfRefPrev; therefore, we can use ImpVec::set_next method. The following code block is the push_front method implementation of the LinkedList:

pub fn push_front(&mut self, value: T) {
    match self.front_node() {
        None => self.push_first_node(value),
        Some(old_front) => {
            let node = Node::active(value, None, Some(old_front));
            let front = unsafe { self.vec.push_get_ref(node) };
            self.vec.set_prev(old_front, Some(front));
            self.slice = LinkedListSlice::new(self.len() + 1, Some(front), self.back_node());
        }
    }
}

In the trivial case when there is no front_node (the list is empty), we simply push the value as the first node.

Otherwise:

• We get a reference to the front node, we’ll now call it old_front since it will no longer be the front of the list.
• We create a new node for the new value:
  • next node of node is set to Some(old_front),
  • previous node of node is None since it is the new front of the list.
• We use the push_get_ref method to push node to the storage vector and get a reference to it.
  • SAFETY: we must make sure that the reference front does not outlive self, which is satisfied here.
• We tell our self.vec which is an ImpVec to set the prev of old_front to Some(front) to link the old front node to the new front ndoe.
• Then, we set that our list now is one element longer, with the old self.back_node() and new front node which is Some(front).

Trait Implementations

impl<T, P> Debug for ImpVec<T, P>

where P: PinnedVec<T>, T: Debug,

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

Formats the value using the given formatter.

impl<T, P: PinnedVec<T> + Default> Default for ImpVec<T, P>

fn default() -> Self

Returns the “default value” for a type.

impl<T, P> Deref for ImpVec<T, P>

where P: PinnedVec<T>,

type Target = P

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T, P> DerefMut for ImpVec<T, P>

where P: PinnedVec<T>,

fn deref_mut(&mut self) -> &mut Self::Target

Mutably dereferences the value.

impl<T> From<ImpVec<T, FixedVec<T>>> for FixedVec<T>

fn from(value: ImpVec<T, FixedVec<T>>) -> Self

Converts to this type from the input type.

impl<T, P: PinnedVec<T>> From<ImpVec<T, P>> for RefCell<P>

fn from(value: ImpVec<T, P>) -> Self

Converts to this type from the input type.

impl<T, G: Growth> From<ImpVec<T, SplitVec<T, G>>> for SplitVec<T, G>

fn from(value: ImpVec<T, SplitVec<T, G>>) -> Self

Converts to this type from the input type.

impl<T, P: PinnedVec<T>> From<P> for ImpVec<T, P>

fn from(value: P) -> Self

Converts to this type from the input type.

impl<T, P: PinnedVec<T> + FromIterator<T>> FromIterator<T> for ImpVec<T, P>

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

Creates a value from an iterator.

impl<T, P> Index<usize> for ImpVec<T, P>

where P: PinnedVec<T>,

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<T, P> IndexMut<usize> for ImpVec<T, P>

where P: PinnedVec<T>,

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

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

impl<T, P, const N: usize> PartialEq<ImpVec<T, P>> for [T; N]

where P: PinnedVec<T>, T: PartialEq,

fn eq(&self, other: &ImpVec<T, P>) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, P, G> PartialEq<ImpVec<T, P>> for SplitVec<T, G>

where P: PinnedVec<T>, T: PartialEq, G: Growth,

fn eq(&self, other: &ImpVec<T, P>) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, P> PartialEq<ImpVec<T, P>> for Vec<T>

where P: PinnedVec<T>, T: PartialEq,

fn eq(&self, other: &ImpVec<T, P>) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, P1, P2> PartialEq<ImpVec<T, P2>> for ImpVec<T, P1>

where P1: PinnedVec<T>, P2: PinnedVec<T>, T: PartialEq,

fn eq(&self, other: &ImpVec<T, P2>) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, P, S> PartialEq<S> for ImpVec<T, P>

where P: PinnedVec<T>, S: AsRef<[T]>, T: PartialEq,

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

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, P> Eq for ImpVec<T, P>

where P: PinnedVec<T>, T: PartialEq,