gen_map

A customizable generational map that returns a Key upon inserting a value. The key can be used to later access or remove the value, and removing a value bumps its slot's generation, so the old key no longer matches the slot. The operations for inserting, removing and accessing a value are all O(1).

The crate never uses std, so it also works on targets that do not have it.

[dependencies]

gen_map = "0.3"

Example

use gen_map::GenMap;

let mut map = GenMap::new();
let a = map.insert("a");
let b = map.insert("b");

assert_eq!(map[a], "a");
assert_eq!(map[b], "b");
assert_eq!(map.remove(a), Some("a"));
assert!(map.get(a).is_none()); // A removed key never matches again.

let c = map.insert("c"); // This takes the slot `a` had, but under a new key.
assert_ne!(a, c);

for (key, value) in &map {
    println!("{key:?} = {value}");
}

Configuring the map

A KeyConfig picks the key's index and generation types and how the key stores them. Split<Idx, Gen> keeps the two as separate fields, and Packed<R, GEN_BITS> puts them in the bits of one integer and picks the smallest types that can hold them. A MapConfig is used to decide the key config, and a GenMapConfig is used to decide what happens when a slot's generation runs out and where the slots live.

use gen_map::{GenMap, GenMapConfig, GenSlotItem, MapConfig, Packed};

/// Maps with this config hand out four byte keys with 24 bits of index and 8
/// bits of generation.
struct CompactConfig;

impl MapConfig for CompactConfig {
    type KeyConfig = Packed<u32, 8>;
}

// `S` is the slot the map keeps each value in.
impl<S: GenSlotItem> GenMapConfig<S> for CompactConfig {
    type Storage = Vec<S>;
}

let mut map = GenMap::<&str, CompactConfig>::new_with_config();
let key = map.insert("a");
assert_eq!(core::mem::size_of_val(&key), 4);

The documentation covers the rest, such as key configs, storage, what happens when a generation runs out, and limiting which maps can use a config.

Secondary maps

A SecondaryMap stores values under the keys a GenMap hands out, to add data to a GenMap's values without changing their type. Like a GenMap, it can be configured, and the documentation covers how it can be configured.

use gen_map::{GenMap, SecondaryMap};

let mut people = GenMap::new();
let mut ages = SecondaryMap::new();
let alice = people.insert("Alice");
ages.insert(alice, 30).unwrap();
assert_eq!(ages[alice], 30);

Cargo features

alloc is on by default. It adds the Vec storage and the default config. Turn default features off and use arrayvec instead to run without an allocator.
arrayvec adds ArrayVec storage for a GenMap or a SecondaryMap. An ArrayVec has a fixed capacity and never allocates.
smallvec adds SmallVec storage for a GenMap or a SecondaryMap. A SmallVec keeps a few slots inline before it allocates. The feature uses a beta of smallvec 2.0, so it is not covered by semver.

License