Struct orx_selfref_col::SelfRefCol

pub struct SelfRefCol<'a, V, T, P = SplitVec<Node<'a, V, T>, Recursive>>
where
    V: Variant<'a, T>,
    P: PinnedVec<Node<'a, V, T>>,
{ /* private fields */ }

SelfRefCol is a core data structure to conveniently build safe and efficient self referential collections, such as linked lists and trees.

Note that this core structure is capable of representing a wide range of self referential collections, where the variant is conveniently defined by expressive trait type definitions.

The represented collections have the following features:

• Relations are represented by regular & references avoiding the need to use smart pointers such as Box, Rc, Arc, etc.
• The collection makes sure that these references are set only among elements of the collections. In other words, no external references are allowed, or references of elements of the collection cannot leak out. This constructs the safety guarantees.
• The elements of the collection are internally stored in a PinnedVec implementation, which is crucial for the correctness of the references. Furthermore, in this way, elements of the collection are stored close to each other rather than being in arbitrary locations in memory. This provides better cache locality when compared to such collections where elements are stored by arbitrary heap allocations.

The collection is defined by the following generic arguments:

• T: type of the elements stored in the collection.
• V: type of the Variant defining the structure of the collection with the following:
  • V::Storage: defines how the elements of T will be stored:
    • NodeDataLazyClose: elements are stored as Option<T> allowing lazy node closure or element removal;
    • NodeDataEagerClose: elements are stored directly as T.
  • V::Prev: defines how references to previous elements will be stored.
    • NodeRefNone: there is no previous reference of elements.
    • NodeRefSingle: there is either one or no previous reference of elements, stored as Option<&Node>.
    • NodeRefsArray: there are multiple possible previous references up to a constant number N, stored as [Option<&Node>; N].
    • NodeRefsVec: there are multiple possible previous references, stored as Vec<&Node>.
  • V::Next: defines how references to next elements will be stored:
    • Similarly, represented as either one of NodeRefNone or NodeRefSingle or NodeRefsArray or NodeRefsVec.
  • V::Ends: defines how references to ends of the collection will be stored:
    • Similarly, represented as either one of NodeRefNone or NodeRefSingle or NodeRefsArray or NodeRefsVec.
  • V::MemoryReclaim: defines how memory of closed nodes will be reclaimed:
    • MemoryReclaimNever will never claim closed nodes.
    • MemoryReclaimOnThreshold<D> will claim memory of closed nodes whenever the ratio of closed nodes exceeds one over 2^D.

Example

Consider the following four structs implementing Variant to define four different self referential collections. Note that the definitions are expressive and concise leading to efficient implementations.

use orx_selfref_col::*;

#[derive(Clone, Copy)]
struct SinglyListVariant;

impl<'a, T: 'a> Variant<'a, T> for SinglyListVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimOnThreshold<2>; // closed nodes will be reclaimed when utilization drops below 75%
    type Prev = NodeRefNone; // previous nodes are not stored
    type Next = NodeRefSingle<'a, Self, T>; // there is only one next node, if any
    type Ends = NodeRefSingle<'a, Self, T>; // there is only one end, namely the front of the list
}

#[derive(Clone, Copy)]
struct DoublyListVariant;

impl<'a, T: 'a> Variant<'a, T> for DoublyListVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimOnThreshold<3>; // closed nodes will be reclaimed when utilization drops below 87.5%
    type Prev = NodeRefSingle<'a, Self, T>; // there is only one previous node, if any
    type Next = NodeRefSingle<'a, Self, T>; // there is only one next node, if any
    type Ends = NodeRefsArray<'a, 2, Self, T>; // there are two ends, namely the front and back of the list
}

#[derive(Clone, Copy)]
struct BinaryTreeVariant;

impl<'a, T: 'a> Variant<'a, T> for BinaryTreeVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimOnThreshold<1>; // closed nodes will be reclaimed when utilization drops below 50%
    type Prev = NodeRefSingle<'a, Self, T>; // there is only one previous node, namely parent node, if any
    type Next = NodeRefsArray<'a, 2, Self, T>; // there are 0, 1 or 2 next or children nodes
    type Ends = NodeRefSingle<'a, Self, T>; // there is only one end, namely the root of the tree
}

#[derive(Clone, Copy)]
struct DynamicTreeVariant;

impl<'a, T: 'a> Variant<'a, T> for DynamicTreeVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimNever; // closed nodes will be left as holes
    type Prev = NodeRefSingle<'a, Self, T>; // there is only one previous node, namely parent node, if any
    type Next = NodeRefsVec<'a, Self, T>; // there might be any number of next nodes, namely children nodes
    type Ends = NodeRefSingle<'a, Self, T>; // there is only one end, namely the root of the tree
}

Crates using SelfRefCol

The following crates use SelfRefCol to conveniently build the corresponding data structure:

• https://crates.io/crates/orx-linked-list: implements singly and doubly linked lists.

Implementations

impl<'a, V, T, P> SelfRefCol<'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<'a, V, T, P> SelfRefCol<'a, V, T, P>

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

pub fn new() -> Self

where P: Default,

Creates a new empty self referential collection.

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 clear(&mut self)

Clears the collection: clears all elements and the ends of the collection.

pub fn reclaim_closed_nodes(&mut self)

where P: 'a, T: 'a, V: Variant<'a, T, Storage = NodeDataLazyClose<T>>, for<'rf> SelfRefColMut<'rf, 'a, V, T, P>: Reclaim<V::Prev, V::Next>,

Manually attempts to reclaim closed nodes.

Safety

Note that reclaiming closed nodes invalidates node indices (NodeIndex) which are already stored outside of this collection.

• when MemoryReclaim policy is set to MemoryReclaimOnThreshold, there is no safety concern:
  • In this policy, memory reclaim operations automatically happen whenever utilization is below a threshold.
  • Therefore, manually triggering the reclaim operation is no different.
  • NodeIndex compares the memory state of the collection and:
    • NodeIndex::get_ref returns None in such a case, or
    • NodeIndex::as_ref panics (equivalent to unwrapping the result of get_ref).
• when MemoryReclaim policy is set to MemoryReclaimNever; however, the caller takes responsibility:
  • In this policy, memory reclaim operations never happen implicitly.
  • This can be considered as a performance optimization for cases where removals are rare.
  • This further gives the luxury to keep size of the NodeIndex equal to one pointer (rather than two pointers as in the MemoryReclaimOnThreshold case).
  • However, this means that NodeIndex is not able to detect the memory reclaims. The safety rule is then as follows:
    • Node indices will never be invalid due to implicit memory reclaim operations.
    • Node indices will be invalidated and must not be used whenever SelfRefCol::reclaim_closed_nodes(&mut self) is manually called.
  • Importantly, note that this will not lead to UB.
    • The safety concern is more around correctness of the reference rather than memory read violations.
    • SelfRefCol will never allow to read outside its memory.

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
    })
}

pub fn mutate<Move>( &mut self, value_to_move: Move, move_mutate_lambda: fn(_: SelfRefColMut<'_, 'a, V, T, P>, _: Move) )

Method allowing to mutate the collection.

This method takes the following arguments:

• value_to_move is, as the name suggests, a value to be moved to the mutation lambda. Two common use cases to move this value to the lambda are:
  • to add moved element(s) of T to the self referential collection,
  • to use moved NodeIndex (indices) to access elements in constant time.
• move_mutate_lambda is the expression defining the mutation.
  • The lambda takes two parameters:
    • the first parameter is the SelfRefColMut type which is the key for all SelfRefNode mutation and constant-time access methods;
    • the second parameter is the value moved into the lambda, which is exactly the value_to_move parameter of this method.
  • 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 for safety guarantees of the collection. This prevents capturing data from the environment, as well as, prevents leaking references outside of the lambda.

This design allows to conveniently mutate the references within the vector without the complexity of lifetimes and borrow checker. Prior references can be broken, references can be rearranged or new references can be built easily. Furthermore, references by NodeIndex can be used for direct constant-time access to elements. This convenience is achieved by the encapsulation of all mutations within a non-capturing lambda.

Example

The following code block demonstrates the use of the mutate function to define the push-front method of a singly linked list. Note that self.col below is a SelfRefCol. The pushed value is moved to the lambda. Inside the lambda, this value is pushed to the list, which is stored inside a linked list node. Links and ends (front of the singly linked list) are updated by using the reference to the newly pushed node.

pub fn push_front(&mut self, value: T) {
    self.col.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([Some(node), Some(node)]);
        }
    });
}

pub fn mutate_take<Move, Take>( &mut self, value_to_move: Move, move_mutate_take_lambda: fn(_: SelfRefColMut<'_, 'a, V, T, P>, _: Move) -> Take ) -> Take

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

Method allowing to mutate 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 mutation lambda. Two common use cases to move this value to the lambda are:
  • to add moved element(s) of T to the self referential collection,
  • to use moved NodeIndex (indices) to access elements in constant time.
• mutate_get_lambda is the expression defining the mutation.
  • The lambda takes two parameters:
    • the first parameter is the SelfRefColMut type which is the key for all SelfRefNode mutation and constant-time access methods;
    • 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.

This design allows to conveniently mutate the references within the vector without the complexity of lifetimes and borrow checker. Prior references can be broken, references can be rearranged or new references can be built easily. Furthermore, references by NodeIndex can be used for direct constant-time access to elements. This convenience is achieved by the encapsulation of all mutations within a non-capturing lambda.

Examples

Example - Take out Value

The following code block demonstrates the use of the mutate_take function to define the pop-front method of a singly linked list. Note that self.vec below is a SelfRefCol. Mutations are applied only if the vector is non-empty; i.e., there exists a front. When this is the case, the ends reference (front of the list) is updated. Furthermore, the prior-front’s underlying data is taken out and returned from the lambda. This, in turn, is returned from the pop_front method, demonstrating safely removing elements from the self referential collection.

pub fn pop_front(&mut self) -> Option<T> {
    self.col.mutate_take(|x| {
        x.ends().front().map(|prior_front| {
            let new_front = *prior_front.next().get();
            let new_back = some_only_if(new_front.is_some(), x.ends().back());
            x.set_ends([new_front, new_back]);

            if let Some(new_front) = new_front {
                new_front.clear_prev(&x);
            }
             
            prior_front.close_node_take_data(&x)
        })
    })
}

Example - Take out NodeIndex

The following is exactly the same push_front example given in mutate example. However, we return an index, NodeIndex, to the pushed element this time. This index can later be used to have a constant time access to the element.

pub fn push_front(&mut self, value: T) -> NodeIndex<'_, V, T> {
    self.col.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);
            new_front.index(&x)
        }
        None => {
            let node = x.push_get_ref(value);
            x.set_ends([Some(node), Some(node)]);
            node.index(&x)
        }
    });
}

pub fn mutate_filter_collect<Predicate, Collect>( &mut self, predicate: &Predicate, collect: &mut Collect, mutate_filter_collect_lambda: fn(_: SelfRefColMut<'_, 'a, V, T, P>, _: &Predicate, _: &mut Collect) )

where Predicate: Fn(&T) -> bool, Collect: FnMut(T),

This method takes three arguments:

• predicate is the function to be used to select elements to be kept.
• collect is the closure to collect the elements which does not satisfy the predicate and will be removed from this collection.
• mutate_filter_collect_lambda is the expression defining the retain together with the mutation.
  • In addition to predicate and collect, the lambda takes SelfRefColMut type which is the key for all SelfRefNode mutation methods to provide safety guarantees.
  • 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.

This method is a generalization of mutate_take which returns the element removed from the collection. In this method collect(T) is called on removed elements. This method might be doing nothing to drop the removed values, or might be pushing them to a captured collection such as a vector. Note that the signature of Collect is FnMut(T); this makes sure that the function is called with removed/owned element values making sure that no references can leak out.

This design allows to conveniently mutate the references within the vector without the complexity of lifetimes and borrow checker. Prior references can be broken, references can be rearranged or new references can be built easily and all in one function. This convenience while being safe is achieved by the encapsulation of all mutations within a non-capturing lambda.

Examples

use orx_selfref_col::*;

#[derive(Debug, Clone, Copy)]
struct Var;
impl<'a> Variant<'a, String> for Var {
    type Storage = NodeDataLazyClose<String>;
    type Prev = NodeRefSingle<'a, Self, String>;
    type Next = NodeRefsVec<'a, Self, String>;
    type Ends = NodeRefsArray<'a, 2, Self, String>;
    type MemoryReclaim = MemoryReclaimNever;
}

// build up collection
let mut col = SelfRefCol::<Var, _>::new();
let values = ['a', 'b', 'c', 'd', 'e'];
col.mutate(values.map(|x| x.to_string()), |x, vals| {
    for value in vals {
        let _ = x.push_get_ref(value);
    }
});

let taboo_list = ['a', 's', 'd', 'f'];
let taboo_list = taboo_list.map(|x| x.to_string());
let is_allowed = |c: &String| !taboo_list.contains(c);

let mut collected = vec![];
let mut collect = |c| collected.push(c);

col.mutate_filter_collect(&is_allowed, &mut collect, |x, predicate, collect| {
    for i in 0..x.len() {
        let node = x.get_node(i).expect("is-some");
        if let Some(value) = node.data() {
            if !predicate(value) {
                collect(node.close_node_take_data(&x));
            }
        }
    }
});

assert_eq!(3, col.len());
assert_eq!(&['a'.to_string(), 'd'.to_string()], collected.as_slice());

impl<'a, V, T> SelfRefCol<'a, V, T, SplitVec<Node<'a, V, T>, Recursive>>

where V: Variant<'a, T>,

pub fn append_mutate<Move>( &mut self, other: Self, value_to_move: Move, append_mutate_lambda: fn(_: SelfRefColMut<'_, 'a, V, T, SplitVec<Node<'a, V, T>, Recursive>>, _: SelfRefColMut<'_, 'a, V, T, SplitVec<Node<'a, V, T>, Recursive>>, _: Move) )

This method appends another self collection to this collection. Note that this method is available in self referential collections using an underlying pinned vector with orx_split_vec::Recursive growth. This allows appending underlying vectors in constant time.

This method takes the following arguments:

• other is the other self referential collection to be appended to this collection.
• value_to_move is, as the name suggests, a value to be moved to the mutation lambda.
• append_mutate_lambda is the expression defining the mutation.
  • The lambda takes three parameters.
  • The first parameter is the SelfRefColMut type which is the mutation key for this collection.
  • The second parameter is the SelfRefColMut key of the other collection.
  • The third parameter is the value moved into the lambda, which is exactly the value_to_move parameter of this method.
  • 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.

This design allows to conveniently mutate the references within the vector without the complexity of lifetimes and borrow checker. Prior references can be broken, references can be rearranged or new references can be built easily. Furthermore, references by NodeIndex can be used for direct constant-time access to elements. This convenience is achieved by the encapsulation of all mutations within a non-capturing lambda.

Example

The following code block demonstrates the use of the move_append_mutate function to define the append-front method of a singly linked list. The method appends the other list to the front of the self list in O(1) time complexity.

Note that appending the underlying storages are handled automatically by SelfRefCol. The lambda, taking mutation keys of both collections being merged, is responsible for fixing references. In this example, one next-relation is established and ends (front and back) of the list are updated.

pub fn append_front(&mut self, other: Self) {
    self.col.move_append_mutate(other.col, (), |x, y, _| {
        match (x.ends().front(), y.ends().back()) {
            (Some(a), Some(b)) => {
                b.set_next(&x, a);
                x.set_ends([y.ends().front(), x.ends().back()]);
            }
            (None, Some(_)) => {
                x.set_ends([y.ends().front(), y.ends().back()]);
            }
            _ => {}
        };
        None
    });
}

Trait Implementations

impl<'a, V, T, P> Debug for SelfRefCol<'a, V, T, P>

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

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

Formats the value using the given formatter.

impl<'a, V, T, P> Default for SelfRefCol<'a, V, T, P>

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

fn default() -> Self

Returns the “default value” for a type.

impl<'a, V, T, P> FromIterator<T> for SelfRefCol<'a, V, T, P>

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

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

Creates a value from an iterator.