Crate gen_map

Expand description

GenMap is a configurable generational map that stores each value in a slot and hands out a Key that points at that slot.

When a value is removed, the map frees its slot and may reuse that slot for a value inserted later. The key of the removed value stops matching the slot when the value is removed, so it does not match the value the map later puts in that slot either. 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. How it works lists the few cases where a key can match a value other than the one it was handed out for.

Inserting, removing and looking up a value are all O(1). The crate never uses std, and Cargo features lists the features that need an allocator.

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

// The map puts "c" in the slot that "a" was removed from. The key `a`
// stopped matching that slot when "a" was removed, so it does not match
// "c".
let c = map.insert("c");
assert_eq!(c.idx(), a.idx());
assert!(map.get(a).is_none());
assert_eq!(map[c], "c");

// The iterator yields each value with its key, in slot order. "c" is in the
// first slot, so it comes before "b".
let pairs: Vec<_> = map.iter().collect();
assert_eq!(pairs, [(c, &"c"), (b, &"b")]);

A SecondaryMap stores values under the keys a GenMap hands out.

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 config decides the size of a map’s keys and the collection the map keeps its slots in.

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

/// Maps with this config hand out keys with a `u8` index and a `u8`
/// generation, so each key is two bytes. A map with this config never gives
/// a slot the index `u8::MAX`, so it holds at most 255 slots.
struct Tiny;

impl MapConfig for Tiny {
    type KeyConfig = Split<u8, u8>;
}

impl<S: GenSlotItem> GenMapConfig<S> for Tiny {
    type Storage = 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);

§How it works

A key holds the index of its value’s slot and the generation that slot had when the key was handed out. A key only matches its slot while the slot’s generation equals the key’s. A new slot starts at generation zero, and the map adds one to a slot’s generation when it inserts a value into the slot and again when remove takes the value out. So the generation is odd while the slot holds a value and even while it does not. Once a value is removed, no copy of its key matches the slot, and the key the map hands out for the next value in that slot has a newer generation.

The map keeps a slot after its value is removed, and it reuses freed slots before it adds new ones. Only reset removes slots. The iterators, retain, drain and clear go through every slot, including the ones that hold no value, so the time they take follows slots_len rather than len.

The map adds one to a slot’s generation twice for each value, so a u32 generation lets a slot hold over two billion values one after another, and a 4-bit generation lets it hold eight. When the map removes a value whose key has the largest generation its key config can hold, the slot has no generations left. By default, the map then retires the slot and never uses it again. When WRAP_ON_OVERFLOW is true, the map instead starts the slot’s generation over at zero and keeps using the slot. The map then counts the slot’s generation up through the same values again, so a key from before the wrap can match a new value once the slot’s generation is back at the key’s.

Two methods also let a key match a value other than the one it was handed out for. reset removes every slot and starts the generations over, so a key from before the reset can match a value inserted after it. reattach puts any value under a key whose value detach took out, and the key then matches that value.

§Configuring the map

A map’s config is a type that implements MapConfig and GenMapConfig. The map only uses the config as a type and never creates a value of it, so an empty struct is enough. A config decides three things.

KeyConfig decides the integer types of a key’s index and generation, and how the key stores the two. Split keeps them as two fields, and Packed puts them in the bits of one integer. With either key config, Option<Key> is the same size as Key.
WRAP_ON_OVERFLOW decides whether the map retires a slot with no generations left or starts its generation over at zero.
Storage is the collection the map keeps its slots in. It can be a Vec, an ArrayVec, a SmallVec or any other type that implements SlotStorage.

When its C parameter is left out, as in GenMap<T>, a map uses DefaultMapConfig. Maps with that config hand out keys with a u32 index and a u32 generation, keep their slots in a Vec and retire a slot that has no generations left. GenMap::new only exists for the default config, so use GenMap::new_with_config for any other.

Maps whose configs have the same key config share a key type. A key does not record which map handed it out, so a map also accepts keys from another map with the same key config, and it may hold an unrelated value under such a key.

§Secondary maps

Use a SecondaryMap to add data to the values of a GenMap without changing their type. A SecondaryMap can only use a GenMap’s keys when both configs have the same KeyConfig, because only then do the two maps share a key type.

When a value is removed from the GenMap, the value stored under its key stays in the SecondaryMap. If the GenMap later puts a new value in the removed value’s slot, the new value’s key has the same index as the old key and a newer generation. The ReplaceStrategy of the SecondaryMap’s config decides whether a value inserted under that newer key replaces the old value.

§Cargo features

alloc is on by default. It adds the Vec storage and DefaultMapConfig. Without it, every map needs a config of its own.
arrayvec lets a config use arrayvec::ArrayVec as its storage. An ArrayVec has a fixed capacity and never allocates.
smallvec lets a config use smallvec::SmallVec as its storage. A SmallVec keeps its first slots inline and allocates when it needs room for more. This feature uses the 2.0 beta of smallvec. Until smallvec 2.0 is released, a newer beta or a new release of gen_map may break this feature, so it is not covered by semver.

The crate only needs an allocator when alloc or smallvec is on. To use the crate without any allocator, turn default features off and arrayvec on.

[dependencies]
gen_map = { version = "0.3", 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§

DefaultMapConfigalloc: The config of a GenMap<T> and a SecondaryMap<T>, which leave out their config parameter C.
Drain: Draining iterator over (key, value) pairs. It is created using GenMap::drain. Dropping it removes the values it has not yielded yet.
Even: An even number of type G.
ExistingWins: Never replaces a value that was inserted under a different generation. An insert into such a slot is refused until the value is removed.
GenMap: A generational map that holds values of type T and is configured by C.
IntoIter: Owning iterator over (key, value) pairs. It is created by consuming a map with into_iter, which a map only has when its storage implements IntoIterator. It implements DoubleEndedIterator, which gives it next_back and rev, only when the storage’s iterator implements both DoubleEndedIterator and ExactSizeIterator, because it needs the length of the storage’s iterator to work out the position of a slot taken from the back.
Iter: Iterator over (key, &value) pairs. It is created using GenMap::iter.
IterMut: Iterator over (key, &mut value) pairs. It is created using GenMap::iter_mut.
Key: A key to a value in a GenMap, returned by insert. The key config K decides how the key stores its index and generation.
Keys: Iterator over keys. It is created using GenMap::keys.
NewerWins: Replaces the slot’s value when the key’s generation is larger than the slot’s. It is the ReplaceStrategy of DefaultMapConfig.
Odd: An odd number of type G. It is never zero, so it is stored as a NonZero, which lets Option use zero to represent None and makes Option<Odd<G>> the same size as G.
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.
SecondaryDrain: Iterator that takes each value out, with its key, in index order. It is created using SecondaryMap::drain.
SecondaryIntoIter: Owning iterator over (key, value) pairs, in index order. It is created by consuming a map with into_iter, which a map only has when its storage implements IntoIterator. It implements DoubleEndedIterator, which gives it next_back and rev, only when the storage’s iterator implements both DoubleEndedIterator and ExactSizeIterator.
SecondaryIter: Iterator over (key, &value) pairs, in index order. It is created using SecondaryMap::iter.
SecondaryIterMut: Iterator over (key, &mut value) pairs, in index order. It is created using SecondaryMap::iter_mut.
SecondaryKeys: Iterator over keys, in index order. It is created using SecondaryMap::keys.
SecondaryMap: A map from the keys of a GenMap to values of type T, configured by C.
SecondarySlot: The slot a SecondaryMap keeps each of its values in. It has a generation, and it holds a T while the generation is odd and no value while it is even.
SecondaryValues: Iterator over references to the values, in index order. It is created using SecondaryMap::values.
SecondaryValuesMut: Iterator over mutable references to the values, in index order. It is created using SecondaryMap::values_mut.
Slot: A generation together with a T while the generation is odd, or a U while it is even.
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. A key can hold any index of type Idx and any odd generation of type Gen.
VacantEntry: The slot the next insert would use, handed out by GenMap::vacant_entry. No slot is written until insert is called, so dropping the entry inserts nothing.
Values: Iterator over shared references to values. It is created using GenMap::values.
ValuesMut: Iterator over mutable references to values. It is created using GenMap::values_mut.

Enums§

FullError: Why a GenMap has no room for another value.
GetDisjointMutAtError: Why GenMap::get_disjoint_mut_at or SecondaryMap::get_disjoint_mut_at could not hand out its references.
GetDisjointMutError: Why GenMap::get_disjoint_mut or SecondaryMap::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. S 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 the variant says which of the two happened. E is the closure’s error and S is the map’s StorageError.
Parity: The generation of a Slot together with its value. The variant says whether the generation is odd or even, and so whether the value is the slot’s T or its U.
SecondaryInsertError: Why SecondaryMap::insert could not insert. Each variant hands the value back so that the caller can keep it. S is the map’s SecondaryStorageError.

Traits§

GenMapConfig: This trait is used to choose what happens when a slot’s generation runs out, and the collection the slots of a GenMap live in.
GenSlotItem: Describes the slot a GenMap keeps each of its values in, for use as a bound in a GenMapConfig impl.
KeyConfig: Chooses the index and generation types of a Key, and how the key stores the two. A Key<K> holds a value of its key config K, and that value holds the index and the generation.
KeyPiece: An unsigned integer that can be the index or the generation of a Key. It is implemented for u8, u16, u32, u64, u128 and usize.
MapConfig: Chooses the KeyConfig of the keys a map works with.
MapConfigFor: What a GenMap<T, C> needs from its config C. C must implement MapConfig, and GenMapConfig for the map’s MapSlot<T, C>.
ReplaceStrategy: Decides whether a value inserted into a SecondaryMap under a key replaces the value already in the slot at the key’s index, when the value in the slot was inserted under a different generation.
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.
SecondaryMapConfig: This trait is used to choose the ReplaceStrategy of a SecondaryMap, and the collection its slots live in.
SecondaryMapConfigFor: What a SecondaryMap<T, C> needs from its config C. C must implement MapConfig, and SecondaryMapConfig for the map’s SecondaryMapSlot<T, C>.
SecondarySlotItem: Describes the slot a SecondaryMap keeps each of its values in, for use as a bound in a SecondaryMapConfig impl. Inside impl<S: SecondarySlotItem> SecondaryMapConfig<S> for YourConfig, S is the slot and S::Value is the type of the value in it.
SlotStorage: The collection a GenMap or a SecondaryMap keeps its slots in. A GenMapConfig or a SecondaryMapConfig chooses one with its Storage type.

Type Aliases§

DefaultKeyConfig: The key config a Key uses when its K parameter is left out.
MapGen: The generation type of the keys that a map with config C works with.
MapIdx: The index type of the keys that a map with config C works with.
MapKeyConfig: The key config that a map config C picks for its keys.
MapSlot: The Slot a GenMap<T, C> keeps each value in. While a slot is on the free list, its U is the index of the next free slot, or the largest value of the index type if it is the last free slot. No slot ever has that index, so it can’t be mistaken for the index of a real slot. A retired slot’s U is also the largest value of the index type. A detached slot’s U is its own index, which is how GenMap::reattach tells a detached slot apart from a free or retired one.
SecondaryMapSlot: The SecondarySlot a SecondaryMap<T, C> keeps each value in.
SecondaryStorageError: The error the storage of a SecondaryMap<T, C> gives when it cannot make room for a slot. It is TryReserveError for a Vec, CapacityError for an ArrayVec and CollectionAllocErr for a SmallVec.
StorageError: The error the storage of a GenMap<T, C> gives when it cannot 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

§Secondary maps

§Cargo features

§Minimum supported Rust version

Structs§

Enums§

Traits§

Type Aliases§

Crate gen_map