Trait orx_fixed_vec::prelude::NotSelfRefVecItem
source · pub trait NotSelfRefVecItem { }Expand description
Marker trait for types to be contained in a PinnedVec which do not hold a field
which is a reference to a another element of the same vector.
Note that any type which does not implement NotSelfRefVecItem marker trait
is assumed to be a self-referencing-vector-item due to the following:
PinnedVecis particularly useful for defining complex data structures which elements of which often references each other; in other words, most of the timePinnedVec<T>will be used.- To be able to use
PinnedVecSimple: PinnedVecfor safe calls toinsert,remove,popandclone, one must explicitly implementNotSelfRefVecItemfor the elements explicitly stating the safety of the usage. - Finally, this trait is already implemented for most of the common primitive types.
It is more brief to describe what a SelfRefVecItem is
rather than describing NotSelfRefVecItem.
Such data types are particularly useful for data types defining
relations about its children such as trees or graphs.
An example struct is demonstrated in the following section.
Example
Consider the following type which is common to tree structures:
struct TreeNode<'a, T> {
value: T,
parent: Option<&'a TreeNode<'a, T>>,
}Further assume that we want to keep nodes of all trees in the same vector. Compared to alternatives, this is helpful at least for the following reasons:
- keeping all nodes together helps in achieving better cache locality,
- the references defining the tree structure are thin rather than wide pointers,
- requires less heap allocations: only the vector is allocated together with all its elements, as opposed to allocating each node separately in an arbitrary memory location.
Safety
On the other hand, such data structures require more care about safety and correctness.
Since each vector element can hold a reference to another vector element,
mut methods need to be investigated carefully.
See SelfRefVecItem for details of the safety analysis.
Significance
Unsafe methods when T is not a NotSelfRefVecItem
Whether the element type of a PinnedVec is NotSelfRefVecItem or not
has an impact on the mutable operations which change positions of already pushed elements.
The following is the list of these methods:
insertremovepopswaptruncateclone
These methods can be called safely when T: NotSelfRefVecItem;
only within an unsafe block otherwise.
Trait Implementations
NotSelfRefVecItem is a marker trait which is implemented for most primitives; however, one needs to implement
for new types to explicitly state that the type is not self-referential.