[−][src]Crate typed_generational_arena

A safe arena allocator that allows deletion without suffering from the ABA problem by using generational type-safe indices. Forked from generational-arena.

Inspired by Catherine West's closing keynote at RustConf 2018, where these ideas were presented in the context of an Entity-Component-System for games programming.

What? Why?

Imagine you are working with a graph and you want to add and delete individual nodes at a time, or you are writing a game and its world consists of many inter-referencing objects with dynamic lifetimes that depend on user input. These are situations where matching Rust's ownership and lifetime rules can get tricky.

It doesn't make sense to use shared ownership with interior mutability (ie Rc<RefCell<T>> or Arc<Mutex<T>>) nor borrowed references (ie &'a T or &'a mut T) for structures. The cycles rule out reference counted types, and the required shared mutability rules out borrows. Furthermore, lifetimes are dynamic and don't follow the borrowed-data-outlives-the-borrower discipline.

In these situations, it is tempting to store objects in a Vec<T> and have them reference each other via their indices. No more borrow checker or ownership problems! Often, this solution is good enough.

However, now we can't delete individual items from that Vec<T> when we no longer need them, because we end up either

messing up the indices of every element that follows the deleted one, or
suffering from the ABA problem. To elaborate further, if we tried to replace the Vec<T> with a Vec<Option<T>>, and delete an element by setting it to None, then we create the possibility for this buggy sequence:
- obj1 references obj2 at index i
- someone else deletes obj2 from index i, setting that element to None
- a third thing allocates obj3, which ends up at index i, because the element at that index is None and therefore available for allocation
- obj1 attempts to get obj2 at index i, but incorrectly is given obj3, when instead the get should fail.

By introducing a monotonically increasing generation counter to the collection, associating each element in the collection with the generation when it was inserted, and getting elements from the collection with the pair of index and the generation at the time when the element was inserted, then we can solve the aforementioned ABA problem. When indexing into the collection, if the index pair's generation does not match the generation of the element at that index, then the operation fails.

Features

Zero unsafe
Well tested, including quickchecks
no_std compatibility
All the trait implementations you expect: IntoIterator, FromIterator, Extend, etc...

Usage

First, add typed-generational-arena to your Cargo.toml:

[dependencies]
typed-generational-arena = "0.2"

Then, import the crate and use one of the variations of the typed_generational_arena::Arena type! In these examples, we use typed_generational_arena::StandardArena, but you can use any combination of index and generation ID best fits your purposes.

extern crate typed_generational_arena;
use typed_generational_arena::StandardArena;

let mut arena = StandardArena::new();

// Insert some elements into the arena.
let rza = arena.insert("Robert Fitzgerald Diggs");
let gza = arena.insert("Gary Grice");
let bill = arena.insert("Bill Gates");

// Inserted elements can be accessed infallibly via indexing (and missing
// entries will panic).
assert_eq!(arena[rza], "Robert Fitzgerald Diggs");

// Alternatively, the `get` and `get_mut` methods provide fallible lookup.
if let Some(genius) = arena.get(gza) {
    println!("The gza gza genius: {}", genius);
}
if let Some(val) = arena.get_mut(bill) {
    *val = "Bill Gates doesn't belong in this set...";
}

// We can remove elements.
arena.remove(bill);

// Insert a new one.
let murray = arena.insert("Bill Murray");

// The arena does not contain `bill` anymore, but it does contain `murray`, even
// though they are almost certainly at the same index within the arena in
// practice. Ambiguities are resolved with an associated generation tag.
assert!(!arena.contains(bill));
assert!(arena.contains(murray));

// Iterate over everything inside the arena.
for (idx, value) in &arena {
    println!("{:?} is at {:?}", value, idx);
}

`no_std`

To enable no_std compatibility, disable the on-by-default "std" feature. This currently requires nightly Rust and feature(alloc) to get access to Vec.

[dependencies]
typed-generational-arena = { version = "0.2", default-features = false }

Serialization and Deserialization with `serde`

To enable serialization/deserialization support, enable the "serde" feature.

[dependencies]
typed-generational-arena = { version = "0.2", features = ["serde"] }

Structs

Arena	The `Arena` allows inserting and removing elements that are referred to by `Index`.
DisableRemoval	If this is used as a generational index, then the arena is no longer generational and does not allow element removal
Drain	An iterator that removes elements from the arena.
IgnoreGeneration	If this is used as a generational index, then the arena ignores generation
Index	An index (and generation) into an `Arena`.
IntoIter	An iterator over the elements in an arena.
Iter	An iterator over shared references to the elements in an arena.
IterMut	An iterator over exclusive references to elements in this arena.
NonZeroIndex	An arena index which is always nonzero. Useful for Option size optimizations
NonzeroGeneration	A generation counter which is always nonzero. Useful for size optimizations on Option
NonzeroWrapGeneration	A wrapping generation counter which is always nonzero. Useful for size optimizations on Option

Traits

ArenaIndex	A type which can be used as an index to an arena
FixedGenerationalIndex	A type which can be used as the index of a generation which may not be able to be incremented
GenerationalIndex	A type which can be used as the index of a generation, which can be incremented
IgnoredGeneration	A marker trait which says that a generation type is ignored

Type Definitions

NanoArena	An arena which can only hold up to (2^{8}) elements, but unlimited generations, with the caveat that generations after (2^{8}) wrap and hence may collide, leading, for example, to reading a new value when the old one was deleted.
NanoIndex	A typed index into a `NanoArena`
PicoArena	An arena which can only hold up to (2^{8} - 1) elements, but unlimited generations, with the caveat that generations after (2^{8} - 1) wrap and hence may collide, leading, for example, to reading a new value when the old one was deleted.
PicoIndex	A typed index into a `NanoArena`
PtrSlab	A slab arena which can hold up to `std::usize::MAX - 1` elements but does not support element removal, and has size optimized optional indices
PtrSlabIndex	An index into a `PtrSlab<T>`
Slab	A slab arena with a given index, which does not support efficient removal
SlabIndex	An index into a slab of type `T` by a certain type
SmallArena	An arena which can only hold up to (2^{32} - 1) elements and generations
SmallIndex	A typed index into a `StandardArena`
SmallPtrSlab	A slab arena which can hold up to `2^{32} - 1` elements but does not support element removal, and has size optimized optional indices
SmallPtrSlabIndex	An index into a `SmallPtrSlab<T>`
SmallSlab	A slab arena which can hold up to `2^{32}` elements but does not support element removal
SmallSlabIndex	An index into a `SmallSlab<T>`
StandardArena	A standard arena of `T` indexed by `usize`, with `2^{64} - 1` generations
StandardIndex	A typed index into a `StandardArena`
StandardSlab	A standard slab arena which can hold up to `std::usize::MAX` elements but does not support element removal
StandardSlabIndex	An index into a `Slab<T>`
TinyArena	An arena which can only hold up to (2^{16}) elements and (2^{16} - 1) generations
TinyIndex	A typed index into a `StandardArena`
TinyWrapArena	An arena which can only hold up to (2^{16}) elements, but unlimited generations, with the caveat that generations after (2^{16} - 1) wrap and hence may, with low probability, collide, leading, for example, to reading a new value when the old one was deleted.
TinyWrapIndex	A typed index into a `TinyWrapArena`
U64Arena	An arena of `T` indexed by `usize`, with `2^{64}` generations
U64Index	An index into a `U64Arena`