kevy_map/lib.rs
1//! `kevy-map` — a purpose-built open-addressing hashtable for kevy's keyspace.
2//!
3//! Per-shard, single-threaded, single-trust-domain. Trades `std::HashMap`'s
4//! generality for three kevy-specific wins:
5//!
6//! 1. **Bucket-address API** (`prefetch_for_hash`, future) — exposes the
7//! table's bucket metadata pointer so the command-batch driver can
8//! `prefetcht0` the next command's group while finishing the current.
9//! 2. **No DoS-hardening tax** — single trust domain ⇒ no random seed.
10//! Hasher is `kevy_hash::KevyHash` (one-call inlinable).
11//! 3. **Cache-conscious layout** — Swiss-style metadata bytes scanned (scalar
12//! in this commit; SSE2 group scan lands in a later pass); slots
13//! AoS so the post-match key+value read hits one cache line.
14//!
15//! See the crate README for the design rationale.
16//!
17//! Constraints: pure Rust, no `crates.io` deps; `unsafe` is allowed here (scoped
18//! to this crate) so `kevy-store` keeps `forbid(unsafe_code)`.
19
20#![warn(missing_docs)]
21#![cfg_attr(not(feature = "std"), no_std)]
22
23// Renamed: this crate has its own `alloc` module (the raw-table
24// allocation plumbing), so the alloc *crate* gets an alias.
25extern crate alloc as alloc_crate;
26
27mod alloc;
28mod clone;
29mod group;
30mod iter;
31mod map;
32mod map_keyed;
33mod raw_entry;
34mod scan;
35mod set;
36
37pub use iter::{Iter, IterMut, Keys, Values};
38pub use kevy_hash::KevyHash;
39pub use map::KevyMap;
40pub use raw_entry::{RawEntryMut, RawOccupiedEntryMut, RawVacantEntryMut};
41pub use set::{KevySet, SetIter};
42
43/// Loop counts for the heavy unit tests, scaled down under miri.
44///
45/// miri interprets every memory access. Five tests in this crate — the
46/// scan sweeps and the two large probe-chain tests — were 339 of the miri
47/// job's 389 seconds, and that job alone is the CI wall clock: 10.5 of
48/// 10.5 minutes, with 57 other jobs finishing inside its shadow.
49///
50/// What miri checks here is undefined behaviour in the probe, grow,
51/// tombstone and clone paths. Those are entered the same way at 1,000
52/// keys as at 10,000; the count buys coverage of the *logic*, and the
53/// native `cargo test` run still does that at full size. Each test keeps
54/// its structural assertion — two capacity doublings, no unexpected
55/// grow, every key visited exactly once — so a count too small to force
56/// the path it needs FAILS the test rather than quietly passing on less.
57#[cfg(test)]
58pub(crate) const fn scaled(full: usize) -> usize {
59 if cfg!(miri) {
60 let n = full / 10;
61 if n < 64 { 64 } else { n }
62 } else {
63 full
64 }
65}