Crate compact_arena

Expand description

A crate with a few single-typed arenas that work exclusively with indexes. The indexes are sized with the arena. This can reduce memory footprint when changing pointers to indices e.g. on 64-bit systems.

The arenas use a variant of “branded indices”: The indices contain an invariant lifetime tag that binds them to their respective arena so you cannot mix up two arenas by accident. Unlike the indexing crate, this generates the type tags from unique mutable borrows of unit tuples without requiring a closure. This allows us to store indices within objects that we put into the arena, which is a boon to things like graph data structures.

The lifetime tags make it impossible to share an arena via an Arc, but one can use crossbeam-utils’ scoped threads to work around this limitation. See examples/threads.rs for a working example.

Use the mk_arena!/mk_tiny_arena!/mk_nano_arena! macros to create an arena, then add or try_add items to it and index it with arena[idx].

§Examples

mk_nano_arena!(arena);
let idx = arena.add(1usize);
assert_eq!(1, arena[idx]);

You can work with multiple arenas:

mk_nano_arena!(a);
mk_nano_arena!(b);
..

The compiler gives you a type error if you mix up arenas:

mk_nano_arena!(a);
mk_nano_arena!(b);
let i = a.add(1usize);
let _ = b[i];

The indices should not be able to escape the block with the mk_*arena call

let idx = { mk_tiny_arena!(arena); arena.add(1usize) };

Also, arenas may not be instantiated recursively:

fn recursive(idx: Option<Idx8<'_>>) {
    mk_nano_arena!(arena); // `tag` does not live long enough
    if let Some(idx) = idx {
        assert_eq!("hello", arena[idx]);
    } else {
        recursive(Some(arena.add("hello")));
    }
}
recursive(None);

Even if you try to mix up arenas using multiple threads, you will run into lifetime errors:

fn mixup(c: Result<Sender<Idx16<'_>>, Receiver<Idx16<'_>>>) {
    mk_tiny_arena!(arena);
    match (s, r) {
        Ok(s) => s.send(arena.add(1usize)).unwrap(),
        Err(r) => assert_eq!(1, arena[r.recv().unwrap()]),
    }
}
    
fn main() {
    let (s, r) = channel();
    let st = thread::spawn(|| mixup(Ok(s)));
    let rt = thread::spawn(|| mixup(Err(r)));
    st.join().unwrap();
    rt.join().unwrap();
}

The SmallArena type keeps its storage in a Vec that may be useful to reuse. For that reason we have the recycle_arena! macro. There is no variant of this for the Tinyarena and NanoArena types, which store their items inline.

Macros§

in_arena
Run a piece of code inside an arena
in_nano_arena
Run code using a nano arena. The indirection through the macro is required to bind the indices to the arena.
in_tiny_arena
Run code using a tiny arena. The indirection through this macro is required to bind the indices to the arena.
mk_arena
Run code using an arena. The indirection through the macro is required to safely bind the indices to the arena. The macro takes an identifier that will be bound to the &mut Arena<_, _> and an expression that will be executed within a block where the arena is instantiated. The arena will be dropped afterwards.
mk_nano_arena
Create a tiny arena. The indirection through this macro is required to bind the indices to the arena.
mk_tiny_arena
Create a tiny arena. The indirection through this macro is required to bind the indices to the arena.
recycle_arena
Empty the arena, and set the binding to a new arena using the storage of the argument.
tagged
Fix an invariant lifetime to a tag value.

Structs§

CapacityExceeded
An error type that gets returned on trying to add an element to an already full arena. It contains the element so you can reuse it
Idx
An index into the arena. You will not directly use this type, but one of the aliases this crate provides (Idx32, Idx16 or Idx8).
InvariantLifetime
This is one part of the secret sauce that ensures that indices from different arenas cannot be mixed. You should never need to use this type in your code.
NanoArena
A “nano” arena containing up to 256 elements.
SmallArena
A “Small” arena based on a resizable slice (i.e. a Vec) that can be indexed with 32-bit Idx32s. This can help reduce memory overhead when using many pointer-heavy objects on 64-bit systems.
TinyArena
A “tiny” arena containing <64K elements.

Functions§

invariant_lifetime
Create an invariant lifetime. This is one part of the secret sauce that ensures that indices from different arenas cannot be mixed. You should never need to use this type in your code.

Type Aliases§