ogeom_core/
collections.rs

1//! Hash maps and sets for the whole kernel.
2//!
3//! [`FastMap`] and [`FastSet`] are `hashbrown` tables hashed by foldhash
4//! with a fixed seed. The seed is what matters: a map's iteration order is
5//! then a function of its insertions alone, the same in every run and every
6//! process, so a stage that walks a map cannot answer differently from one
7//! run to the next. The std tables seed themselves randomly and are refused
8//! by clippy (`disallowed-types` in `clippy.toml`) outside the few public
9//! signatures that already promised them.
10//!
11//! A fixed seed gives up the defence against keys chosen to collide. The
12//! kernel hashes its own ids and coordinates, not adversarial strings.
13//!
14//! The tables have no `new` or `with_capacity`: build them with
15//! `FastMap::default()`, `collect()`, or
16//! `FastMap::with_capacity_and_hasher(n, FastHasher::default())`.
17
18pub use hashbrown::{hash_map, hash_set};
19
20/// The hasher every [`FastMap`] and [`FastSet`] builds: foldhash, seeded
21/// the same way in every process.
22pub type FastHasher = foldhash::fast::FixedState;
23
24/// A hash map whose iteration order depends only on its contents and the
25/// order they were inserted in.
26pub type FastMap<K, V> = hashbrown::HashMap<K, V, FastHasher>;
27
28/// A hash set whose iteration order depends only on its contents and the
29/// order they were inserted in.
30pub type FastSet<T> = hashbrown::HashSet<T, FastHasher>;
31
32#[cfg(test)]
33mod tests {
34    use super::*;
35
36    #[test]
37    fn iteration_order_is_fixed_by_the_insertions() {
38        let build = || {
39            let mut map = FastMap::default();
40            for i in 0..1000_u64 {
41                map.insert(i.wrapping_mul(0x9e37_79b9_7f4a_7c15), i);
42            }
43            map.into_iter().collect::<Vec<_>>()
44        };
45        assert_eq!(build(), build());
46    }
47}
ogeom_core/collections.rs

ogeom_core/
collections.rs
