[][src]Crate compact_arena

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:

# use compact_arena::mk_nano_arena;
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

This example deliberately fails to compile
let idx = { mk_tiny_arena!(arena); arena.add(1usize) };

Also, arenas may not be instantiated recursively:

This example deliberately fails to compile
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);

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.

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).

NanoArena

A "nano" arena containing up to 256 elements. This variant only works with types implementing Default.

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 up to 65536 elements. This variant only works with types implementing Default.

Type Definitions

Idx8

The index type for a nano arena is 8 bits large. You will usually get the index from the arena and use it by indexing, e.g. arena[index].

Idx16

The index type for a tiny arena is 16 bits large. You will usually get the index from the arena and use it by indexing, e.g. arena[index].

Idx32

The index type for a small arena is 32 bits large. You will usually get the index from the arena and use it by indexing, e.g. arena[index].