Crate typed_generational_arena

Expand description

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 Aliases§

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

Crate typed_generational_arenaCopy item path