Crate gen_map

Expand description

A generational map with a configurable key.

GenMap stores values and hands out a Key for each one. A key stays valid until its value is removed, and by default it never matches a value that later takes the same slot. The only exceptions are a config that wraps generations and reset, both described below. That makes keys safe to hold on to where plain indices or references are not, such as in graphs, entity systems and anything else that refers to values by handle.

Inserting, removing and looking up a value are all O(1). The crate is no_std, and it only needs an allocator for storage that uses the heap, such as Vec. The Vec storage comes from the alloc feature, which is on by default and can be turned off. See Cargo features.

§Examples

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.remove(a), Some("a"));
assert!(map.get(a).is_none());

// `c` takes the slot `a` had, but `a` still does not match the new value.
let c = map.insert("c");
assert_eq!(c.idx(), a.idx());
assert!(map.get(a).is_none());
assert_eq!(map[c], "c");

for (key, value) in &map {
    assert!(key == b || key == c);
    assert!(*value == "b" || *value == "c");
}

§How it works

The map keeps its values in a list of slots. A key is the index of a slot together with the slot’s generation at the time the key was handed out, and Key::idx and Key::generation read the two back. A slot’s generation goes up by one on every insert and every remove, so it is odd while the slot holds a value and even while it does not. A key only matches its slot while the two generations are equal, so removing a value invalidates every copy of its key at once, and the next value in that slot gets a key with a newer generation.

Freed slots go on a free list and are reused before the map adds new ones, so the map only grows when no slot is free.

§Configuring the map

A Config decides four things.

Idx and Gen are the integer types of the index and the generation. Any type that implements KeyPiece works, which is every unsigned integer from u8 to u128, and usize.
Layout is how a key stores the generation and index. Split keeps them as two fields and Packed puts them in the bits of one integer.
Storage is the collection the slots live in, such as a Vec.
WRAP_ON_OVERFLOW says what happens to a slot whose generation runs out.

DefaultConfig is the config a GenMap uses when none is named. Its keys are a u32 index and a u32 generation stored as two fields, its slots live in a Vec, and a slot retires when its generation runs out.

A config is only used as a type parameter and never created as a value, so an empty struct is enough.

use gen_map::{Config, GenMap, Split};

/// A `u8` index and a `u8` generation, so keys are two bytes and the map
/// holds at most 256 slots.
struct Tiny;

impl Config for Tiny {
    type Idx = u8;
    type Gen = u8;
    type Layout = Split;
    type Storage<S> = Vec<S>;
}

let mut map = GenMap::<u64, Tiny>::new_with_config();
let key = map.insert(7);
assert_eq!(core::mem::size_of_val(&key), 2);
assert_eq!(map[key], 7);

GenMap::new only exists for the default config. Rust does not use a default type parameter when it infers types, so a new that took any config would need the config written out on every call. Any other config goes through GenMap::new_with_config.

§Key layouts

Split stores the index and the generation as two fields, so a key is as large as the two together, plus any padding their alignment needs. The index and the generation can each use every value of their type.

Packed stores them in the bits of one integer instead. Packed<R, GEN_BITS> gives the low GEN_BITS bits of an R to the generation and the bits above them to the index, so a key is as large as R, and the two parts can have any bit counts that add up to the bits of R. The config’s Idx and Gen only have to be wide enough for their parts, and a config whose bit counts do not add up fails to compile.

use gen_map::{Config, GenMap, Key, Packed};

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

impl Config for Compact {
    type Idx = u32;
    type Gen = u8;
    type Layout = Packed<u32, 8>;
    type Storage<S> = Vec<S>;
}

let mut map = GenMap::<&str, Compact>::new_with_config();
let key = map.insert("a");
assert_eq!(core::mem::size_of::<Key<Compact>>(), 4);
assert_eq!(map[key], "a");

With either layout, Option<Key> is the same size as Key.

§When a generation runs out

A slot’s generation can only go up to the largest one its key can hold, which is Gen::MAX for Split and the largest value of the generation part for Packed. Each value a slot holds uses up two generations, one when it is inserted and one when it is removed, so a u32 generation lets a slot hold over two billion values, while a 4 bit generation lets it hold eight. What happens to a slot after that is up to WRAP_ON_OVERFLOW.

By default, the slot retires. It stays in the storage but is never used again, so no stale key can ever match a new value.

When WRAP_ON_OVERFLOW is true, the generation wraps back to zero and the slot is reused. No slot is ever lost, but a key that is old enough can match a new value once the generation wraps around to it again.

retire removes a value and retires its slot, no matter how the map is configured. Code built on a map that wraps can use it to keep the slots it chooses from wrapping, and Key::is_max_generation can be used to determine when a slot has reached that point.

§Storage

The slots can live in any collection that implements SlotStorage. A Vec does, and so do two collections from other crates when their features are on. ArrayVec from arrayvec has a fixed capacity and never allocates, and SmallVec from smallvec keeps a few slots inline before it allocates. SlotStorage is an unsafe trait, because the map relies on the storage behaving like a Vec when it reads slots without bounds checks.

The methods that make room ahead of time, which are reserve, try_reserve, with_capacity and with_capacity_and_config, only exist when the storage also implements ReserveStorage, as Vec and SmallVec do.

§When the map is full

A map is full when none of its slots are free, and it can not add another one, either because its keys have no index left for a new slot or because the storage can not make room for one. A u8 index, for example, allows 256 slots.

insert panics on a full map. The other ways to insert report a full map as an error.

try_insert returns an InsertError that hands the value back.
vacant_entry picks the slot before the value exists, and returns a FullError if there is none. The entry’s key is the key the value will get, and dropping the entry leaves the map as it was.
try_insert_with_key runs a closure that may fail, and returns an InsertWithError if the map is full or the closure fails.

When a Vec can not allocate, these methods also return a StorageFull error instead of panicking.

use gen_map::{Config, GenMap, InsertError, Split};

struct Tiny;

impl Config for Tiny {
    type Idx = u8;
    type Gen = u8;
    type Layout = Split;
    type Storage<S> = Vec<S>;
}

let mut map = GenMap::<u32, Tiny>::new_with_config();
for i in 0..256 {
    map.insert(i);
}
match map.try_insert(256) {
    Err(InsertError::IndexExhausted(value)) => assert_eq!(value, 256),
    _ => unreachable!(),
}

§Values that know their own key

insert_with_key gives a closure the new value’s key before the value is stored, which helps with values that refer to themselves, such as the nodes of a graph.

use gen_map::{GenMap, Key};

struct Node {
    me: Key,
    edges: Vec<Key>,
}

let mut graph = GenMap::new();
let a = graph.insert_with_key(|me| Node { me, edges: Vec::new() });
let b = graph.insert_with_key(|me| Node { me, edges: vec![a] });
assert_eq!(graph[b].me, b);
assert_eq!(graph[b].edges, [a]);

§Taking a value out for a while

detach moves a value out of the map but keeps its slot reserved for its key, and reattach puts a value back under that same key. In between, the key is invalid and no insert can take the slot. This lets code take a value out, change it while borrowing the rest of the map, and put it back under the same key.

use gen_map::GenMap;

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

let mut value = map.detach(a).unwrap();
value += map[b];
map.reattach(a, value);
assert_eq!(map[a], 3);

§Several values at once

get_disjoint_mut hands out mutable references to several values at once, after checking that every key is valid and that no two keys point at the same slot. get_disjoint_mut_at does the same with slot indices, and hands each key back with its value.

use gen_map::GenMap;

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

let [x, y] = map.get_disjoint_mut([a, b]).unwrap();
core::mem::swap(x, y);
assert_eq!((map[a], map[b]), (2, 1));

§Looking a slot up by its index

key_at and get_at find the value in the slot at an index along with its current key, for code that only kept the index. generation_at returns a slot’s generation whether it holds a value or not.

§Iterating and removing in bulk

Every iterator visits the values in slot order, which is also the order of their keys. iter, iter_mut, keys, values, values_mut and the owning into_iter all know their exact length and can run from both ends.

retain, drain and clear remove values but keep every slot and its generation, so old keys stay invalid. reset removes the slots too while keeping the allocation. The generations start over after a reset, so a key from before the reset can match a value inserted after it.

§Unchecked access

Every lookup has an _unchecked form, such as get_unchecked, that skips the checks the normal form makes, for code that already knows its key or index is valid. Calling one with an invalid key or index is undefined behavior.

Key::from_raw_parts builds a key from an index and a generation. It is unsafe because the generation must be odd and both parts must fit the layout, and looking up a key that breaks either rule is undefined behavior.

§Cargo features

alloc is on by default. It adds the Vec storage, DefaultConfig and GenMap::new, and makes DefaultConfig the config that GenMap and Key use when none is named. Without it the crate needs no allocator, and every map needs a config whose storage does not allocate, such as an ArrayVec.
arrayvec lets a config use arrayvec::ArrayVec as its storage.
smallvec lets a config use smallvec::SmallVec as its storage. It uses the 2.0 beta of smallvec, which needs an allocator and Rust 1.86. Until smallvec 2.0 is released, a newer smallvec beta or a new release of gen_map may break this feature, so it is not covered by semver.

To use the map without any allocator, turn alloc off and arrayvec on.

[dependencies]
gen_map = { version = "0.2", default-features = false, features = ["arrayvec"] }

§Minimum supported Rust version

The crate builds on Rust 1.79 and later. The smallvec feature needs Rust 1.86, because the 2.0 beta of smallvec does.

Structs§

DefaultConfig: The config a GenMap uses when none is named.
Drain: Draining iterator over (key, value) pairs. Created by GenMap::drain. Dropping it removes whatever has not been yielded yet.
GenMap: A generational map whose key is configured by C.
IntoIter: Owning iterator over (key, value) pairs. Created by consuming a map with into_iter.
Iter: Iterator over (key, &value) pairs. Created by GenMap::iter.
IterMut: Iterator over (key, &mut value) pairs. Created by GenMap::iter_mut.
Key: A key to a value in a GenMap, returned by insert. The config’s Layout says how the key stores its index and generation.
Keys: Iterator over keys. Created by GenMap::keys.
Packed: Stores the index and the generation in the bits of one integer R, so a key is as large as R. The low GEN_BITS bits hold the generation and the bits above them hold the index.
PackedRepr: The type a key with the Packed layout stores its index and generation in. Only pack_unchecked can make one, so its generation field is never zero.
Slot: One entry of a map’s storage, the S of a config’s Storage<S>. It has no public API.
Split: Stores the index and the generation as two fields, so a key is as large as the two put together, plus any padding their alignment needs. Every value of Idx and Gen fits.
SplitRepr: The type a key with the Split layout stores its index and generation in.
VacantEntry: The slot the next insert would use, handed out by GenMap::vacant_entry. Nothing is written until insert is called, so dropping the entry leaves the map as it was.
Values: Iterator over shared references to values. Created by GenMap::values.
ValuesMut: Iterator over mutable references to values. Created by GenMap::values_mut.

Enums§

FullError: Why a GenMap has no room for another value.
GetDisjointMutAtError: Why GenMap::get_disjoint_mut_at could not hand out its references.
GetDisjointMutError: Why GenMap::get_disjoint_mut could not hand out its references.
InsertError: Why GenMap::try_insert could not insert. Each variant hands the value back so that the caller can keep it. E is the map’s StorageError.
InsertWithError: Why GenMap::try_insert_with_key could not insert. The map can be full before the closure runs, or the closure can refuse to make a value, and this tells the two apart. E is the closure’s error and S is the map’s StorageError.

Traits§

Config: Compile time configuration of a GenMap.
KeyLayout: How a Key stores its index and generation. A Config picks one through its Layout type.
KeyPiece: An unsigned integer that can be the index or the generation of a Key. Implemented for u8, u16, u32, u64, u128 and usize.
ReserveStorage: A SlotStorage that can make room for more items on request. After try_reserve has returned Ok for n more items, the next n calls of try_push succeed.
SlotStorage: The collection a GenMap keeps its slots in. A Config names one through its Storage type.

Type Aliases§

StorageError: The error the storage of a GenMap<T, C> gives when it can not make room for another slot. It is TryReserveError for a Vec, CapacityError for an ArrayVec and CollectionAllocErr for a SmallVec.

Crate gen_map

Crate gen_map Copy item path

§Examples

§How it works

§Configuring the map

§Key layouts

§When a generation runs out

§Storage

§When the map is full

§Values that know their own key

§Taking a value out for a while

§Several values at once

§Looking a slot up by its index

§Iterating and removing in bulk

§Unchecked access

§Cargo features

§Minimum supported Rust version

Structs§

Enums§

Traits§

Type Aliases§

Crate gen_map