15 stable releases
2.1.0 | Sep 25, 2024 |
---|---|
2.0.0 | Sep 16, 2024 |
1.8.0 | Aug 12, 2024 |
1.7.0 | Jul 25, 2024 |
1.0.1 | Feb 27, 2024 |
#495 in Data structures
421 downloads per month
Used in orx-linked-list
47KB
851 lines
orx-selfref-col
SelfRefCol
is a core data structure to conveniently build safe and efficient self referential collections, such as linked lists and trees.
Features
Safe
It is tricky to implement safe self referential collections, SelfRefCol
provides a safe and convenient api to enable them with the following approach:
- memory locations of elements of the collection will never change unless explicitly changed due to the pinned elements guarantees of the underlying
PinnedVec
, - all references will be ensured to be among elements of the same collection.
orx-linked-list crate defines both singly and doubly linked lists based on SelfRefCol
.
Efficient
The elements of the SelfRefCol
are internally stored in a PinnedVec
implementation, which is crucial for the correctness and safety 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 in order to improve cache locality.
Variants
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.
V: Variant
: defines the structure of the collection with the following:V::Item
: is the type of the items or elements.V::Prev
: defines how references to previous elements will be stored.RefsNone
: there is no previous reference of elements.RefsSingle
: there is either one or no previous reference of elements, stored asOption<&Node>
.RefsArray
: there are multiple possible previous references up to a constant numberN
, stored as[Option<&Node>; N]
.RefsVec
: there are multiple possible previous references, stored asVec<&Node>
.
V::Next
: defines how references to next elements will be stored:- Similarly, represented as either one of
RefsNone
orRefsSingle
orRefsArray
orRefsVec
.
- Similarly, represented as either one of
V::Ends
: defines how references to ends of the collection will be stored:- Similarly, represented as either one of
RefsNone
orRefsSingle
orRefsArray
orRefsVec
.
- Similarly, represented as either one of
M: MemoryReclaimPolicy
: 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 over2^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::*;
use core::marker::PhantomData;
pub struct Singly<T> {
p: PhantomData<T>,
}
impl<T> Variant for Singly<T> {
type Item = T;
type Prev = RefsNone;
type Next = RefsSingle<Self>;
type Ends = RefsSingle<Self>; // front
}
pub struct Doubly<T> {
p: PhantomData<T>,
}
impl<T> Variant for Doubly<T> {
type Item = T;
type Prev = RefsSingle<Self>;
type Next = RefsSingle<Self>;
type Ends = RefsArray<2, Self>; // front & back
}
pub struct BinaryTree<T> {
p: PhantomData<T>,
}
impl<T> Variant for BinaryTree<T> {
type Item = T;
type Prev = RefsSingle<Self>; // parent
type Next = RefsArray<2, Self>; // 2 children
type Ends = RefsSingle<Self>; // root
}
pub struct DynamicTree<T> {
p: PhantomData<T>,
}
impl<T> Variant for DynamicTree<T> {
type Item = T;
type Prev = RefsSingle<Self>; // parent
type Next = RefsVec<Self>; // n children
type Ends = RefsSingle<Self>; // root
}
NodeIndex
NodeIndex
belongs in the intersection of the two features efficient and safe.
A NodeIndex
is a struct holding a reference to an element of the collection. It provides constant time access to the element. Furthermore, a node index can be stored independently of the collection, elsewhere.
In this sense NodeIndex
to a SelfRefCol
is sort of analogous to usize
to standard Vec
.
However, it puts a special emphasis on safety and correctness. The following invalid uses cannot happen with NodeIndex
and SelfRefCol
. The following safety guarantees are provided by the self referential collection:
- cannot use a
NodeIndex
on a wrongSelfRefCol
- cannot use a
NodeIndex
after the corresponding element is removed - cannot use a
NodeIndex
after a reorganization of the elements
Crates using SelfRefCol
The following crates use SelfRefCol
to conveniently build the corresponding data structure:
- orx-linked-list: implements singly and doubly linked lists.
Contributing
Contributions are welcome! If you notice an error, have a question or think something could be improved, please open an issue or create a PR.
License
This library is licensed under MIT license. See LICENSE for details.
Dependencies
~475KB