Crate quickdry

Quickdry

Quickdry is a library for arena allocation.

An arena keeps a single pointer into a large slab of memory. Allocation is very quick, because it simply bumps the pointer forward, and maintains no metadata about individual allocations. In exchange, all the memory in an arena must be freed at once.

For example, a circular doubly-linked list in the style of the Linux kernel’s:

use core::{ptr, cell::Cell};
use core::alloc::Layout;
use quickdry::Arena;

#[repr(C)]
pub struct Node<'a> {
    pub data: i32,
    pub next: Cell<&'a Node<'a>>,
    pub prev: Cell<&'a Node<'a>>,
}

impl<'a> Node<'a> {
    pub fn in_arena(arena: &'a Arena, data: i32) -> &'a Self {
        #[repr(C)]
        struct NodeUninit<'a> {
            data: i32,
            next: Cell<Option<&'a NodeUninit<'a>>>,
            prev: Cell<Option<&'a NodeUninit<'a>>>,
        }

        unsafe {
            let ptr = arena.alloc(Layout::new::<Self>()) as *mut Self;

            let bootstrap = ptr as *mut NodeUninit<'a>;
            let next = Cell::new(None);
            let prev = Cell::new(None);
            ptr::write(bootstrap, NodeUninit { data, next, prev });

            let node = &*bootstrap;
            node.next.set(Some(node));
            node.prev.set(Some(node));

            &*ptr
        }
    }

    pub fn add_head(&'a self, new: &'a Self) { Self::insert(new, self, self.next.get()) }
    pub fn add_tail(&'a self, new: &'a Self) { Self::insert(new, self.prev.get(), self) }
    pub fn del(&'a self) { Self::remove(self.prev.get(), self.next.get()) }

    fn insert(new: &'a Self, prev: &'a Self, next: &'a Self) {
        next.prev.set(new);
        new.next.set(next);
        new.prev.set(prev);
        prev.next.set(new);
    }

    fn remove(prev: &'a Self, next: &'a Self) {
        next.prev.set(prev);
        prev.next.set(next);
    }
}

fn main() {
    let arena = Arena::default();
     
    let list = Node::in_arena(&arena, 3);
    list.add_head(Node::in_arena(&arena, 5));
    list.add_tail(Node::in_arena(&arena, 8));

    assert_eq!(list.data, 3);
    assert_eq!(list.next.get().data, 5);
    assert_eq!(list.next.get().next.get().data, 8);
    assert_eq!(list.next.get().next.get().next.get().data, 3);

    list.next.get().del();

    assert_eq!(list.data, 3);
    assert_eq!(list.next.get().data, 8);
    assert_eq!(list.next.get().next.get().data, 3);
}

Structs

Arena

Bump-pointer allocator.