Riddance

Riddance is a Rust library crate that provides a Registry container, which stores objects and issues unique IDs for them, also known as a "slot map" or an "arena". See the documentation on docs.rs.

lib.rs:

Riddance provides a Registry container, which stores objects and issues unique IDs for them, also known as a "slot map" or an "arena".

Example: the graph problem

In most programming languages it's easy to build a group of objects that reference each other, but the easy way doesn't work in Rust:

struct Person {
    name: String,
    friends: Vec<Person>,
}

let mut alice = Person { name: "Alice".into(), friends: vec![] };
let mut bob = Person { name: "Bob".into(), friends: vec![] };
alice.friends.push(bob);
bob.friends.push(alice); // error: borrow of moved value: `bob`

The simplest solution is to use Vec indexes instead of references, but then you can't delete elements, and it's also easy to make mistakes when different types all have usize IDs. Registry uses "generational indexes" under the hood to support deletion, and it creates element-type-specific IDs by default:

use riddance::{Id, Registry};

struct Person {
    name: String,
    friends: Vec<Id<Person>>,
}

let mut people = Registry::new();
let alice_id = people.insert(Person { name: "Alice".into(), friends: vec![] });
let bob_id = people.insert(Person { name: "Bob".into(), friends: vec![] });
people[alice_id].friends.push(bob_id);
people[bob_id].friends.push(alice_id);

// Deletion works and frees up space.
people.remove(alice_id);
assert!(people.get(alice_id).is_none());
assert!(people.get(bob_id).is_some());

Basic features

• Registry::insert returns a unique, copyable Id<T> that you can use to reference the inserted element, with get, get_mut, or square bracket indexing. The performance of these lookups is similar to Vec indexing, faster than HashMap for example.
• Registry::remove returns the original element and frees up capacity for future elements. Each element slot has a "generation" (31 bits by default), and each removal increments the generation of the removed slot, so new IDs can reuse free slots without being confused for old IDs. When the generation of a given slot reaches its maximum (after 2 billion removals), that slot is "retired". This guarantees that new IDs are always unique.
• Like a HashMap, you can iterate over values, over IDs, or both.

Advanced features

• New IDs can be "reserved" atomically, without requiring mutable access to the Registry. See reserve_id and reserve_ids. This allows multiple threads of an application to build objects in parallel and finish inserting them later with insert_reserved.
• The default [Id] type is 64 bits, but callers that want smallers IDs can use Id32, which has a configurable number of generation bits. This leads to a tradeoff between maximum number of elements the Registry can hold and the rate at which slots get retired.
• Registry::recycle_retired adds retired slots back to the free list. When you recycle, you must promise not to call any Registry methods with removed ("dangling") IDs from before the recycle, or else you'll cause logic errors. This is hard to use correctly, and it's only intended for callers who use Id32 with an aggressively small number of generation bits. Most callers don't need it.

Comparison with other slot map / arena crates

The most well-established crate is slotmap, which provides the SlotMap container. The main differences between Registry and SlotMap are:

• This crate is new and still incomplete. SlotMap is much better tested and more feature-complete.
• The slotmap crate provides several different implementations with different performance tradeoffs, like efficient iteration or sparse storage. This crate only provides Registry.
• SlotMap doesn't retire slots. In rare circumstances, it's possible for IDs from two different insertions to collide.
• SlotMap doesn't support atomically reserving IDs.