#self-referential #pool #struct #safer #creation #value


This crate implements a ValuePool struct that makes the creation of self-referential data structures easier and safer

2 unstable releases

0.2.0 Feb 16, 2024
0.1.0 Feb 12, 2024

#449 in Data structures

Download history 14/week @ 2024-02-09 149/week @ 2024-02-16 27/week @ 2024-02-23 15/week @ 2024-03-01 6/week @ 2024-03-08 17/week @ 2024-03-15 24/week @ 2024-03-29 2/week @ 2024-04-05 6/week @ 2024-04-12 184/week @ 2024-04-19

198 downloads per month

MIT license

449 lines

This crate implements a ValuePool struct that makes the creation of self-referential data structures easier and safer.

Take a look at the examples/ folder.


  • unsafe - uses unsafe code for (potential) speed improvements. This should not create UB or change the behavior off your code.


  • enable use of SmallVec behind a feature once v2 is finished.


use value_pool::{ValuePool, ValueRef};

#[derive(Debug, Clone)]
struct Node<T> {
    value: T,
    next: Option<ValueRef<Node<T>>>,

impl<T> Node<T> {
    fn new(value: T, next: Option<ValueRef<Node<T>>>) -> Node<T> {
        Node { value, next }
#[derive(Debug, Clone)]
struct LinkedList<T> {
    start: ValueRef<Node<T>>,
    end: ValueRef<Node<T>>,
    store: ValuePool<Node<T>>,

impl<T> LinkedList<T> {
    pub fn new() -> LinkedList<T> {
        // We can use a ValueRef equal to 0 and then check in all methods if `store.is_empty`
        LinkedList {
            start: (ValueRef::default()),
            end: (ValueRef::default()),
            store: (ValuePool::new()),

    pub fn push_back(&mut self, value: T) -> Option<()> {
        // will return Option<()> here for ease of use
        // think of reference as a weird "pointer"
        let reference = self.store.push(Node::new(value, None));

        // Note: There is no guarantee that calling `self.store.push` on an empty store will
        // return ValueRef::new(0). We have to make sure self.start points to the right element
        if self.store.element_count() == 1 { // We just pushed the first value
            self.start = reference;
            self.end = reference;
        self.store.get_mut(self.end)?.next = Some(reference);
        self.end = reference;


    pub fn pop_front(&mut self) -> Option<T> {
        // will return Option<T> here in case self.store is empty
        if self.store.is_empty() {
            return None;
        // We expect that `self.store.take(self.start)` returns Some(...) if our LinkedList is in a valid state.
        // We could use `unwrap_unchecked` if we can guarantee that our LinkedList is in such a state or if we don't care about our safety.
        // Or we remove our first check if `self.store.is_empty` and just use the `?` (`self.store.take` will return None if it's empty)
        let first_node = self.store.take(self.start)?;
        // We can't use `.unwrap` or `?` here, because `first_node` could have no `first_node.next` node.
        // We don't want a panic or early return. We want to return `first_node.value`.
        // Note: `ValueRef::default() == ValueRef::new(0)`
        self.start = first_node.next.unwrap_or_default();