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 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.2.2"

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. 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, KeyConfig, MapConfig, Packed};

/// Four byte keys with 24 bits of index and 8 bits of generation.
struct CompactKey;

impl KeyConfig for CompactKey {
    type Idx = u32;
    type Gen = u8;
    type Layout = Packed<u32, 8>;
}

struct CompactConfig;

impl MapConfig for CompactConfig {
    type KeyConfig = CompactKey;
}

// `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 layouts, 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. Its config picks a ReplaceStrategy, which decides whether an insert replaces a value that was inserted under a different generation. The config also picks the storage the slots live in, which can be any storage a GenMap can use. The map keeps a slot at every index up to the highest index that an insert has used.

use gen_map::{GenMap, SecondaryMap};

let mut names = GenMap::new();
let mut ages = SecondaryMap::new();
let alice = names.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

gen_map is released under the MIT license.