[−][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
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);
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 |
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 ( |
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. This variant only works
with types implementing |
SmallArena | A "Small" arena based on a resizable slice (i.e. a |
TinyArena | A "tiny" arena containing up to 65536 elements. This variant only works with
types implementing |
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 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. |
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. |
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. |