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).

Only the std feature uses std, so with default features off, the crate also works on targets that do not have std.

[dependencies]
gen_map = "0.4"

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"));
// Removing "a" changed its slot's generation, so `a` no longer matches.
assert!(map.get(a).is_none());

// "c" goes in the slot that "a" was removed from, under a new key.
let c = map.insert("c");
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, whether the map keeps a count of its values and where the slots live.

use gen_map::{GenMap, GenMapConfig, GenSlotItem, KeepLen, 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>;
}

impl GenMapConfig for CompactConfig {
    type Len = KeepLen;
    // `S` is the type of the slots the map keeps its values in.
    type Storage<S: GenSlotItem> = 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, and what happens when a generation runs out.

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, as the documentation explains.

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);

A SparseSecondaryMap keeps its values in a HashMap under the indices of their keys, so it uses less memory than a SecondaryMap when only a few of a GenMap's keys have a value in it. It needs the std feature.

Dense maps

A DenseGenMap keeps its values one after another in a slice of their own, so iterating over them is as fast as iterating over a slice. Removing a value moves the last value into its place. A DenseSecondaryMap does the same for a SecondaryMap.

use gen_map::DenseGenMap;

let mut map = DenseGenMap::new();
let a = map.insert(1);
map.insert(2);
map.insert(3);
map.remove(a);
assert_eq!(map.values().copied().collect::<Vec<_>>(), [3, 2]);

Cargo features

• std is on by default, and it turns alloc on too. It adds SparseSecondaryMap, which keeps its values in std's HashMap. Turn default features off and alloc on to run without std.
• alloc adds the SingleVec, Vec and PairVec storages and the default config. Turn default features off and use arrayvec instead to run without an allocator.
• arrayvec lets a config use ArrayVec as a storage. An ArrayVec has a fixed capacity and never allocates.
• smallvec lets a config use SmallVec as a storage. A SmallVec keeps a few items 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.