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** ([`KevyMap::prefetch_for_hash`]) — lets the
7//!    command-batch driver prefetch the next command's metadata group
8//!    while finishing the current one.
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 16 at
12//!    a time (SSE2 / NEON, scalar elsewhere); slots AoS so the post-match
13//!    key+value read hits one cache line.
14//!
15//! ```
16//! use kevy_map::{KevyMap, KevySet};
17//!
18//! let mut m: KevyMap<Vec<u8>, u64> = KevyMap::new();
19//! m.insert(b"user:1".to_vec(), 7);
20//! // borrowed lookup: a byte slice finds a Vec<u8> key without allocating
21//! assert_eq!(m.get(b"user:1".as_slice()), Some(&7));
22//!
23//! let s: KevySet<u64> = [3, 1, 3].into_iter().collect();
24//! assert_eq!(s.len(), 2);
25//! ```
26//!
27//! See the crate README for the design rationale.
28//!
29//! Constraints: pure Rust, no `crates.io` deps; `unsafe` is allowed here (scoped
30//! to this crate) so `kevy-store` keeps `forbid(unsafe_code)`.
31
32#![warn(missing_docs)]
33#![cfg_attr(not(feature = "std"), no_std)]
34
35// Renamed: this crate has its own `alloc` module (the raw-table
36// allocation plumbing), so the alloc *crate* gets an alias.
37extern crate alloc as alloc_crate;
38
39mod alloc;
40mod clone;
41mod group;
42mod grow;
43mod into_iter;
44mod iter;
45mod map;
46mod map_keyed;
47mod raw_entry;
48mod scan;
49mod set;
50mod slot;
51#[cfg(test)]
52mod std_traits_tests;
53
54pub use alloc::malloc_footprint;
55pub use into_iter::IntoIter;
56pub use iter::{Iter, IterMut, Keys, Values};
57pub use kevy_hash::KevyHash;
58pub use map::KevyMap;
59pub use raw_entry::{RawEntryMut, RawOccupiedEntryMut, RawVacantEntryMut};
60pub use set::{KevySet, SetIntoIter, SetIter};
61
62// Send and Sync are part of the public contract: a change that loses
63// either fails to compile here rather than in a caller.
64const _: () = {
65    const fn send_sync<T: Send + Sync>() {}
66    send_sync::<KevyMap<u64, u64>>();
67    send_sync::<KevySet<u64>>();
68    send_sync::<IntoIter<u64, u64>>();
69    send_sync::<SetIntoIter<u64>>();
70    send_sync::<Iter<'static, u64, u64>>();
71    send_sync::<IterMut<'static, u64, u64>>();
72    send_sync::<Keys<'static, u64, u64>>();
73    send_sync::<Values<'static, u64, u64>>();
74    send_sync::<SetIter<'static, u64>>();
75    send_sync::<RawEntryMut<'static, u64, u64>>();
76};
77
78/// Loop counts for the heavy unit tests, scaled down under miri.
79///
80/// miri interprets every memory access. Five tests in this crate — the
81/// scan sweeps and the two large probe-chain tests — were 339 of the miri
82/// job's 389 seconds, and that job alone is the CI wall clock: 10.5 of
83/// 10.5 minutes, with 57 other jobs finishing inside its shadow.
84///
85/// What miri checks here is undefined behaviour in the probe, grow,
86/// tombstone and clone paths. Those are entered the same way at 1,000
87/// keys as at 10,000; the count buys coverage of the *logic*, and the
88/// native `cargo test` run still does that at full size. Each test keeps
89/// its structural assertion — two capacity doublings, no unexpected
90/// grow, every key visited exactly once — so a count too small to force
91/// the path it needs FAILS the test rather than quietly passing on less.
92#[cfg(test)]
93pub(crate) const fn scaled(full: usize) -> usize {
94    if cfg!(miri) {
95        let n = full / 10;
96        if n < 64 { 64 } else { n }
97    } else {
98        full
99    }
100}
kevy_map/lib.rs

kevy_map/
lib.rs
