Quickdry

This crate provides bump-pointer arena allocation.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT License (LICENSE-MIT or http://www.apache.org/licenses/LICENSE-2.0)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

lib.rs:

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);
}