Struct orx_selfref_col::SelfRefColMut

pub struct SelfRefColMut<'rf, 'a, V, T, P>
where
    V: Variant<'a, T>,
    P: PinnedVec<Node<'a, V, T>>,
    'a: 'rf,
{ /* private fields */ }

Struct allowing to safely, conveniently and efficiently mutate a self referential collection.

Safety

This struct holds a mutable reference to the underlying self referential collection. Therefore, it allows to mutate the vector with immutable references, as in internal mutability of a refcell.

This struct cannot be created externally. It is only constructed by SelfRefCols methods such as mutate and mutate_take methods. You may find corresponding safety guarantees in the documentation of these methods, which in brief, relies on careful encapsulation of mutation preventing any reference to leak into the collection or any node reference to leak out.

Convenience

The nodes of the self referential collection, SelfRefNode, has convenient methods to mutate the references, such as:

• set_prev
• set_next
• clear_next
• clear_prev
• close_node_take_data

In addition, SelfRefColMut provides the following vector methods:

• push_get_ref
• set_ends

These allow to easily and conveniently update the relations among the nodes without lifetime or ownership complexities.

Example

For instance, the following example illustrates the push_front method in a doubly linked list. The lambda argument x is a SelfRefColMut. You might notice that the lambda body is close enough to the pseudocode of the method. All complexity of the safety guarantees is hidden by the additional parameter or the key, x, passed into these mut methods.

pub fn push_front(&mut self, value: T) {
    self.vec
        .move_mutate(value, |x, value| match x.ends().front() {
            None => {
                let node = x.push_get_ref(value);
                x.set_ends([Some(node), Some(node)]);
            }
            Some(prior_front) => {
                let new_front = x.push_get_ref(value);
                new_front.set_next(&x, prior_front);
                prior_front.set_prev(&x, new_front);
                x.set_ends([Some(new_front), x.ends().back()]);
            }
        });
    self.len += 1;
}

Implementations

impl<'rf, 'a, V, T, P> SelfRefColMut<'rf, 'a, V, T, P>

where V: Variant<'a, T, Storage = NodeDataLazyClose<T>>, P: PinnedVec<Node<'a, V, T>>,

pub fn node_utilization(&self) -> f32

Returns the node utilization as a fraction of active nodes to the used nodes:

• 1.0 when there is no closed node;
• 0.0 when all used memory is used by closed nodes.

impl<'rf, 'a, V, T, P> SelfRefColMut<'rf, 'a, V, T, P>

where V: Variant<'a, T>, P: PinnedVec<Node<'a, V, T>>,

pub fn get_node_ref( &self, node_index: NodeIndex<'a, V, T> ) -> Option<&'a Node<'a, V, T>>

O(1) Converts the node_index to Some of the valid reference to the node in this collection.

If the node index is invalid, the method returns None.

Note that the validity of the node index can also be queried by node_index::is_valid_for_collection method.

get_node_ref(collection) returns Some if all of of the following safety and correctness conditions hold:

• this index is created from the given collection,
• the node this index is created for still belongs to the collection; i.e., is not removed,
• the node positions in the collection are not reorganized to reclaim memory.

pub fn get_node_ref_or_error( &self, node_index: NodeIndex<'a, V, T> ) -> Result<&'a Node<'a, V, T>, NodeIndexError>

where P: PinnedVec<Node<'a, V, T>>,

O(1) Converts the node_index to a Ok of the valid reference to the node in this collection.

If the node index is invalid, the method returns Err of the corresponding NodeIndexError depending on the reason of invalidity.

Note that the corresponding error can also be queried by node_index::invalidity_reason_for_collection method.

get_node_ref_or_error(collection) returns Ok if all of of the following safety and correctness conditions hold:

• this index is created from the given collection,
• the node this index is created for still belongs to the collection; i.e., is not removed,
• the node positions in the collection are not reorganized to reclaim memory.

pub fn as_node_ref(&self, node_index: NodeIndex<'a, V, T>) -> &'a Node<'a, V, T>

O(1) Converts the node_index to a reference to the node in this collection. The call panics if node_index.is_valid_for_collection(collection) is false; i.e., if this node index is not valid for this collection.

Panics

Panics if the node index is invalid; i.e., if node_index.is_valid_for_collection returns false.

Note that is_valid_for_collection returns true if all of of the following safety and correctness conditions hold:

• this index is created from the given collection,
• the node this index is created for still belongs to the collection; i.e., is not removed,
• the node positions in the collection are not reorganized to reclaim memory.

pub fn first_node<'b>(&self) -> Option<&'b Node<'a, V, T>>

Returns a reference to the first node of the collection.

pub fn last_node<'b>(&self) -> Option<&'b Node<'a, V, T>>

Returns a reference to the last node of the collection.

pub fn get_node<'b>(&self, at: usize) -> Option<&'b Node<'a, V, T>>

Returns a reference to the at-th node of the collection.

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

Pushes the value to the vector and returns a reference to the created node.

Example

The following code block demonstrates the push-front operation of a singly linked list. The code is branched depending on whether or not there already exists a front; i.e., the list is not empty. In either case,

• the new value is pushed to the self referential collection;
• and a reference to the new list node containing this value is received right after by the push_get_ref method;
• this reference is then used to establish singly linked list relations.

pub fn push_front(&mut self, value: T) {
    self.col
        .move_mutate(value, |x, value| match x.ends().front() {
            Some(prior_front) => {
                let new_front = x.push_get_ref(value);
                new_front.set_next(&x, prior_front);
                x.set_ends(new_front);
            }
            None => {
                let node = x.push_get_ref(value);
                x.set_ends(node);
            }
        });
}

pub fn set_ends_refs(&self, ends: V::Ends)

Sets the ends of the self referential collection to the given ends.

Ends represent special references of the self referential structure. It can be nothing; i.e., NodeRefNone; however, they are common in such structures. For instance,

• ends of a singly linked list is the front of the list which can be represented as a NodeRefSingle reference;
• ends of a doubly linked list contains two references, front and back of the list which can be represented by a NodeRefsArray<2, _, _>;
• ends of a tree is the root which can again be represented as a NodeRefSingle reference.

Ends of a SelfRefCol is generic over NodeRefs trait which can be decided on the structure’s requirement.

pub fn set_ends<Ends: Into<V::Ends>>(&self, ends: Ends)

Sets the ends of the self referential collection to the given ends.

Ends represent special references of the self referential structure. It can be nothing; i.e., NodeRefNone; however, they are common in such structures. For instance,

• ends of a singly linked list is the front of the list which can be represented as a NodeRefSingle reference;
• ends of a doubly linked list contains two references, front and back of the list which can be represented by a NodeRefsArray<2, _, _>;
• ends of a tree is the root which can again be represented as a NodeRefSingle reference.

Ends of a SelfRefCol is generic over NodeRefs trait which can be decided on the structure’s requirement.

Methods from Deref<Target = SelfRefCol<'a, V, T, P>>

pub fn node_utilization(&self) -> f32

Returns the node utilization as a fraction of active nodes to the used nodes:

• 1.0 when there is no closed node;
• 0.0 when all used memory is used by closed nodes.

pub fn ends(&self) -> &V::Ends

Returns a reference to the ends of the self referential collection.

Ends represent special references of the self referential structure. It can be nothing; i.e., NodeRefNone; however, they are common in such structures. For instance,

• ends of a singly linked list is the front of the list which can be represented as a NodeRefSingle reference;
• ends of a doubly linked list contains two references, front and back of the list which can be represented by a NodeRefsArray<2, _, _>;
• ends of a tree is the root which can again be represented as a NodeRefSingle reference.

Ends of a SelfRefCol is generic over NodeRefs trait which can be decided on the structure’s requirement.

pub fn len(&self) -> usize

Returns length of the self referential collection.

pub fn is_empty(&self) -> bool

Returns whether or not the self referential collection is empty.

pub fn visit_take<Move, Take>( &self, value_to_move: Move, visit_take_lambda: fn(_: SelfRefColVisit<'_, 'a, V, T, P>, _: Move) -> Take ) -> Take

where Take: CanLeak<'a, V, T, P>,

Method allowing to visit nodes of the collection and return values from the collection.

This method can only return types which implement CanLeak. Note that only T and NodeIndex, and types wrapping these two types, such as Option or Vec, implement CanLeak. This ensures the safety guarantees ara maintained.

This method takes two arguments:

• value_to_move is, as the name suggests, a value to be moved to the visit lambda.
• visit_take_lambda is the expression defining the search inside the collection.
  • The lambda takes two parameters:
    • the first parameter is the SelfRefColVisit type which is the key for constant-time node access methods without mutation;
    • the second parameter is the value moved into the lambda, which is exactly the value_to_move parameter of this method.
  • And it returns a type implementing CanLeak to make sure that safety guarantees of SelfRefCol are maintained.
  • Note that the lambda is of a function pointer type; i.e., fn, rather than a function trait such as FnOnce. This is intentional and critical in terms of the safety guarantees. Its purpose is to prevent capturing data from the environment, as well as, prevent leaking vector references to outside of the lambda.

Examples

Example - Take out Value

The following code block demonstrates the use of the visit_take function to define the index_of method of a singly, or doubly, linked list. Note that self.col below is a SelfRefVisit. We can easily access the nodes and traverse through the references among them inside the lambda. In this example, we move inside a value to search. Once we reach a node with the given value, we return the node index which implements CanLeak.

pub fn index_of(&self, value: &T) -> Option<NodeIndex<'a, V, T>>
where
    T: PartialEq,
{
    self.col.visit_take(value, |x, value| {
        let mut current = x.ends().front();
        while let Some(node) = current {
            match node.data() {
                Some(data) if value == data => return Some(node.index(&x)),
                _ => current = *node.next().get(),
            }
        }
        None
    })
}

Trait Implementations

impl<'rf, 'a, V, T, P> Deref for SelfRefColMut<'rf, 'a, V, T, P>

where V: Variant<'a, T>, P: PinnedVec<Node<'a, V, T>>,

type Target = SelfRefCol<'a, V, T, P>

The resulting type after dereferencing.

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

Dereferences the value.

impl<'rf, 'a, V, T, P> From<&SelfRefColMut<'rf, 'a, V, T, P>> for SelfRefColVisit<'rf, 'a, V, T, P>

where V: Variant<'a, T>, P: PinnedVec<Node<'a, V, T>>,

fn from(value: &SelfRefColMut<'rf, 'a, V, T, P>) -> Self

Converts to this type from the input type.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefNone, NodeRefSingle<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefNone, Next = NodeRefSingle<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, const N: usize, V, T, P> Reclaim<NodeRefNone, NodeRefsArray<'a, N, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefNone, Next = NodeRefsArray<'a, N, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefNone, NodeRefsVec<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefNone, Next = NodeRefsVec<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefSingle<'a, V, T>, NodeRefNone> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefSingle<'a, V, T>, Next = NodeRefNone>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefSingle<'a, V, T>, NodeRefSingle<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefSingle<'a, V, T>, Next = NodeRefSingle<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, const N: usize, V, T, P> Reclaim<NodeRefSingle<'a, V, T>, NodeRefsArray<'a, N, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefSingle<'a, V, T>, Next = NodeRefsArray<'a, N, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefSingle<'a, V, T>, NodeRefsVec<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefSingle<'a, V, T>, Next = NodeRefsVec<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, const N: usize, V, T, P> Reclaim<NodeRefsArray<'a, N, V, T>, NodeRefNone> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsArray<'a, N, V, T>, Next = NodeRefNone>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, const N: usize, V, T, P> Reclaim<NodeRefsArray<'a, N, V, T>, NodeRefSingle<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsArray<'a, N, V, T>, Next = NodeRefSingle<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, const N: usize, const M: usize, V, T, P> Reclaim<NodeRefsArray<'a, N, V, T>, NodeRefsArray<'a, M, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsArray<'a, N, V, T>, Next = NodeRefsArray<'a, M, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, const N: usize, V, T, P> Reclaim<NodeRefsArray<'a, N, V, T>, NodeRefsVec<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsArray<'a, N, V, T>, Next = NodeRefsVec<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefsVec<'a, V, T>, NodeRefNone> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsVec<'a, V, T>, Next = NodeRefNone>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefsVec<'a, V, T>, NodeRefSingle<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsVec<'a, V, T>, Next = NodeRefSingle<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, const N: usize, V, T, P> Reclaim<NodeRefsVec<'a, V, T>, NodeRefsArray<'a, N, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsVec<'a, V, T>, Next = NodeRefsArray<'a, N, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.

impl<'rf, 'a, V, T, P> Reclaim<NodeRefsVec<'a, V, T>, NodeRefsVec<'a, V, T>> for SelfRefColMut<'rf, 'a, V, T, P>

where T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>, Prev = NodeRefsVec<'a, V, T>, Next = NodeRefsVec<'a, V, T>>, P: PinnedVec<Node<'a, V, T>> + 'a,

fn reclaim(&mut self)

Reclaims holes due to removals from the collection; i.e., not utilized memory.