zone-alloc

This crate provides data types for zone-based (also known as region-based or arena-based) data allocation. Zone-based allocation is a type of memory management in which allocated objects are assigned to a specific zone. Data in the zone remain valid and usable for the lifetime of the zone, and all data in the zone are deallocated together after use.

This crate also provides "registries," which are container types that procide arena allocation of elements and interior mutability with simple runtime borrow checking.

[dependencies]
zone-alloc = "0.3"

Usage

This crate defines three containers:

• Arena<T> - A container that can be used for arena allocation of values of a given type.
• Registry<T> - An extension of Arena<T> that provides integer handles for allocated data.
• StrongRegistry<H, T> - An extension of Registry<T> that provides strongly-typed handles for allocated data.
• KeyedArena<K, T> - An extension of Arena<T> that maintains a mapping of keys to values.

Additional Crates

• zone-alloc-strong-handle-derive - Procedural macro for deriving the StrongHandle interface on simple wrappers around the Handle type when working with StrongRegistry.

Features

While the crate is by default built with the Rust standard library, this feature can be removed for no-std environments.

• default - std
• std - Depend on the Rust standard library.
• may-dangle - Use the #[may_dangle] attribute on the Drop implementation of ElementRef and ElementRefMut.

Examples

Linked List Nodes with Arena<T>

use zone_alloc::Arena;

#[derive(Debug, PartialEq, Eq)]
struct Node<'a, T> {
    parent: Option<&'a Node<'a, T>>,
    value: T,
}

impl<'a, T> Node<'a, T> {
    pub fn new(parent: Option<&'a Node<'a, T>>, value: T) -> Self {
        Self { parent, value }
    }
}

fn main() {
    let arena = Arena::new();
    let node = arena.alloc(Node::new(None, 1));
    let node = arena.alloc(Node::new(Some(node), 2));
    let node = arena.alloc(Node::new(Some(node), 3));

    assert_eq!(node.value, 3);
    assert_eq!(node.parent.unwrap().value, 2);
    assert_eq!(node.parent.unwrap().parent.unwrap().value, 1);
    assert_eq!(node.parent.unwrap().parent.unwrap().parent, None);
}

Circular References with Registry<T>

use zone_alloc::{
    Handle,
    Registry,
};

#[derive(Debug, PartialEq, Eq)]
struct Node<T> {
    parent: Option<Handle>,
    value: T,
}

impl<T> Node<T> {
    pub fn new(parent: Option<Handle>, value: T) -> Self {
        Self { parent, value }
    }
}

fn main() {
    let registry = Registry::new();
    let root_handle = registry.register(Node::new(None, "first"));
    let handle = registry.register(Node::new(Some(root_handle), "second"));
    let handle = registry.register(Node::new(Some(handle), "third"));
    registry.get_mut_unchecked(root_handle).parent = Some(handle);

    let node = registry.get(handle).unwrap();
    assert_eq!(node.value, "third");
    let node = registry.get(node.parent.unwrap()).unwrap();
    assert_eq!(node.value, "second");
    let node = registry.get(node.parent.unwrap()).unwrap();
    assert_eq!(node.value, "first");
    let node = registry.get(node.parent.unwrap()).unwrap();
    assert_eq!(node.value, "third");
}

Circular References with KeyedRegistry<T>

#[cfg(not(feature = "std"))]
extern crate alloc;

#[cfg(not(feature = "std"))]
use alloc::borrow::ToOwned;

use zone_alloc::KeyedRegistry;

#[derive(Debug, PartialEq, Eq)]
struct Node<K, V> {
    parent: Option<K>,
    value: V,
}

impl<K, V> Node<K, V> {
    pub fn new(parent: Option<K>, value: V) -> Self {
        Self { parent, value }
    }
}

fn main() {
    let registry = KeyedRegistry::new();
    registry.register("node-1".to_owned(), Node::new(None, "first"));
    registry.register(
        "node-2".to_owned(),
        Node::new(Some("node-1".to_owned()), "second"),
    );
    registry.register(
        "node-3".to_owned(),
        Node::new(Some("node-2".to_owned()), "third"),
    );
    registry.get_mut_unchecked("node-1").parent = Some("node-3".to_owned());

    let node = registry.get("node-3").unwrap();
    assert_eq!(node.value, "third");
    let node = registry.get(node.parent.as_ref().unwrap()).unwrap();
    assert_eq!(node.value, "second");
    let node = registry.get(node.parent.as_ref().unwrap()).unwrap();
    assert_eq!(node.value, "first");
    let node = registry.get(node.parent.as_ref().unwrap()).unwrap();
    assert_eq!(node.value, "third");
}

Runtime Borrow Checking

use zone_alloc::{
    BorrowError,
    Registry,
};

fn main() {
    let registry = Registry::new();
    registry.register_extend(100..200);

    // Multiple immutable borrows on the same element.
    let borrow_1 = registry.get(16);
    let borrow_2 = registry.get(16);
    let borrow_3 = registry.get(16);
    assert!(borrow_1.as_ref().is_ok_and(|i| i.eq(&116)));
    assert!(borrow_2.as_ref().is_ok_and(|i| i.eq(&116)));
    assert!(borrow_3.as_ref().is_ok_and(|i| i.eq(&116)));

    // Mutable borrow fails.
    assert_eq!(
        registry.get_mut(16).err(),
        Some(BorrowError::AlreadyBorrowed)
    );

    // Another element can be borrowed independently.
    let borrow_4 = registry.get(32);
    assert!(borrow_4.as_ref().is_ok_and(|i| i.eq(&132)));
    assert!(borrow_1.as_ref().is_ok_and(|i| i.eq(&116)));

    // Only one mutable borrow allowed.
    let mut borrow_5 = registry.get_mut(64).unwrap();
    assert!(borrow_5.eq(&164));
    *borrow_5 *= 2;
    assert!(borrow_5.eq(&328));
    assert_eq!(
        registry.get_mut(64).err(),
        Some(BorrowError::AlreadyBorrowed)
    );
    assert_eq!(registry.get(64).err(), Some(BorrowError::AlreadyBorrowed));

    // Refetch to show updated value, and show that previous borrows are still valid.
    drop(borrow_5);
    let borrow_5 = registry.get(64);
    assert!(borrow_5.as_ref().is_ok_and(|i| i.eq(&328)));
    assert!(borrow_4.as_ref().is_ok_and(|i| i.eq(&132)));
    assert!(borrow_1.as_ref().is_ok_and(|i| i.eq(&116)));
}