Struct KevyMap 

pub struct KevyMap<K, V> { /* private fields */ }

An open-addressing Swiss-style hashtable keyed by KevyHash.

Power-of-two capacity (mask = cap - 1); 7/8 load factor; linear probing over the metadata array; full slots’ (K, V) live AoS in a parallel slot array of MaybeUninit<(K, V)> co-allocated with the metadata.

When cap == 0 both pointers are dangling and no allocation is held.

Examples

Keys are byte strings or integers — whatever implements KevyHash. There is deliberately no &str impl: the keyspace deals in bytes, and a key that exists only as UTF-8 would need validating on every lookup.

let mut m: kevy_map::KevyMap<Vec<u8>, u32> = kevy_map::KevyMap::new();
assert_eq!(m.insert(b"k".to_vec(), 1), None, "insert returns what it displaced");
assert_eq!(m.insert(b"k".to_vec(), 2), Some(1));
assert_eq!(m.get(b"k".as_slice()), Some(&2));
assert_eq!(m.remove(b"k".as_slice()), Some(2));
assert_eq!(m.get(b"k".as_slice()), None);
assert!(m.is_empty());

Implementations

impl<K, V> KevyMap<K, V>

pub fn new() -> Self

Construct an empty map without allocating.

Examples

// The key must implement `KevyHash`, which is deliberately a small
// set: byte strings and integers, the things a KV engine keys on.
let m: kevy_map::KevyMap<Vec<u8>, u32> = kevy_map::KevyMap::new();
assert!(m.is_empty());
assert_eq!(m.len(), 0);

pub fn with_capacity(cap_hint: usize) -> Self

Construct a map sized to hold cap_hint entries without growing (accounting for the 7/8 load factor).

Examples

// A hint, not a promise: capacity is rounded to the table's own
// shape, and `len` still starts at zero.
let m: kevy_map::KevyMap<u32, u32> = kevy_map::KevyMap::with_capacity(100);
assert_eq!(m.len(), 0);

pub fn len(&self) -> usize

Live entry count.

Examples

let mut m = kevy_map::KevyMap::new();
m.insert(1u32, "a");
m.insert(1u32, "b");
assert_eq!(m.len(), 1, "the second insert REPLACED the first");

pub fn is_empty(&self) -> bool

Whether the map has zero live entries.

pub fn capacity(&self) -> usize

Allocated slot count (NOT live entries).

pub fn clear(&mut self)

Drop every live entry and reset the metadata. Keeps the allocation.

Examples

let mut m = kevy_map::KevyMap::new();
for i in 0..8u32 { m.insert(i, i); }
m.clear();
assert!(m.is_empty());
assert_eq!(m.get(&0), None);

pub fn iter(&self) -> Iter<'_, K, V>

(&K, &V) over all live entries; order is unspecified.

Examples

let mut m = kevy_map::KevyMap::new();
for i in 0..4u32 { m.insert(i, i * 10); }
// Unordered, like any hash table: sort before comparing.
let mut got: Vec<_> = m.iter().map(|(k, v)| (*k, *v)).collect();
got.sort_unstable();
assert_eq!(got, vec![(0, 0), (1, 10), (2, 20), (3, 30)]);

pub fn iter_from_bucket(&self, start: usize) -> Iter<'_, K, V>

iter that begins at bucket start (clamped to capacity()) and walks to the end. To sweep the full ring beginning at a random offset — the pattern the kevy-store eviction sampler uses — chain it with a second iter_from_bucket(0) and take(start).

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

(&K, &mut V) over all live entries; order is unspecified. Keys stay shared (mutating a key in place would corrupt its bucket).

pub fn keys(&self) -> Keys<'_, K, V>

&K over all live entries.

Examples

let mut m = kevy_map::KevyMap::new();
m.insert(b"a".to_vec(), 1u32);
m.insert(b"b".to_vec(), 2);
let mut ks: Vec<_> = m.keys().cloned().collect();
ks.sort_unstable();
assert_eq!(ks, vec![b"a".to_vec(), b"b".to_vec()]);

pub fn values(&self) -> Values<'_, K, V>

&V over all live entries.

pub fn prefetch_for_hash(&self, hash: u64)

Hint the CPU to fetch the bucket cache line that a probe at hash would start at. The prefetch lever against the bucket-probe DRAM miss: the command-batch driver calls this for command N+1 while finishing command N, so by the time N+1 actually probes the metadata, the line is in L1.

No-op when the table is empty. Cheap when not empty (a single prefetcht0 on x86_64 / prfm pldl1keep on aarch64; a regular volatile load on other arches via std::intrinsics — but we only use stable intrinsics here, so non-x86/aarch64 architectures degrade to a no-op rather than a fake hint).

inline(always) is the point — see the prefetch_t0 rationale.

impl<K: KevyHash + Eq, V> KevyMap<K, V>

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Insert (key, value). Returns the old value if key was already present. Following std::HashMap semantics, the existing K is kept on overwrite — only V is replaced.

Examples

let mut m = kevy_map::KevyMap::new();
assert_eq!(m.insert(b"k".to_vec(), 1u32), None, "no previous value");
assert_eq!(m.insert(b"k".to_vec(), 2), Some(1), "the OLD value comes back");
assert_eq!(m.get(b"k".as_slice()), Some(&2));

impl<K, V> KevyMap<K, V>

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: KevyHash + Eq + ?Sized,

Borrow the value for key, or None if absent.

Examples

let mut m = kevy_map::KevyMap::new();
m.insert(b"k".to_vec(), 1u32);
// Borrowed lookup: a `&[u8]` finds a `Vec<u8>` key without allocating.
assert_eq!(m.get(b"k".as_slice()), Some(&1));
assert_eq!(m.get(b"nope".as_slice()), None);

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

where K: Borrow<Q>, Q: KevyHash + Eq + ?Sized,

Mutably borrow the value for key, or None if absent.

Examples

let mut m = kevy_map::KevyMap::new();
m.insert(b"k".to_vec(), 1u32);
if let Some(v) = m.get_mut(b"k".as_slice()) { *v += 41; }
assert_eq!(m.get(b"k".as_slice()), Some(&42));

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: KevyHash + Eq + ?Sized,

Whether key is present in the map.

Examples

let mut m = kevy_map::KevyMap::new();
m.insert(b"k".to_vec(), ());
assert!(m.contains_key(b"k".as_slice()));
assert!(!m.contains_key(b"j".as_slice()));

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: KevyHash + Eq + ?Sized,

Remove key’s entry; returns the previous value if present.

Examples

let mut m = kevy_map::KevyMap::new();
m.insert(b"k".to_vec(), 7u32);
assert_eq!(m.remove(b"k".as_slice()), Some(7), "the value comes back");
assert_eq!(m.remove(b"k".as_slice()), None, "absent — None, not a panic");
assert!(m.is_empty());

impl<K, V> KevyMap<K, V>

pub fn raw_entry_mut<Q>(&mut self, key: &Q) -> RawEntryMut<'_, K, V>

where K: Borrow<Q> + KevyHash + Eq, Q: KevyHash + Eq + ?Sized,

Look up key; return an RawEntryMut giving single-probe access to the located (or vacant) slot.

One full probe. The returned handle borrows self mutably; the borrow is released only when the handle is dropped (or consumed via RawOccupiedEntryMut::remove / RawOccupiedEntryMut::into_mut).

impl<K: KevyHash + Eq, V> KevyMap<K, V>

pub fn scan_step(&self, cursor: u64, f: impl FnMut(&K, &V)) -> u64

Visit one bucket-group’s worth of the map and return the next cursor. Start a sweep with cursor = 0; a returned 0 means the sweep is complete. Grows between calls never skip a key that was present throughout (see the module docs); shrinks don’t exist (KevyMap never shrinks in place).

f is called once per entry whose home group is the cursor’s group — at most once per entry per call, in unspecified order.

Bounded work: one call touches one 16-bucket home group plus its probe-run overhang (short at the 7/8 load factor).

Examples

let mut m = kevy_map::KevyMap::new();
for i in 0..64u32 { m.insert(i, i); }

// A SCAN-style cursor: bounded work per call, 0 both starts and
// ends the walk, and every key is seen at least once across it.
let mut seen = Vec::new();
let mut cur = 0u64;
loop {
    cur = m.scan_step(cur, |k, _| seen.push(*k));
    if cur == 0 { break; }
}
seen.sort_unstable();
seen.dedup();
assert_eq!(seen.len(), 64);

Trait Implementations

impl<K: Clone, V: Clone> Clone for KevyMap<K, V>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for KevyMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V> Default for KevyMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Drop for KevyMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<K: KevyHash + Eq, V> Extend<(K, V)> for KevyMap<K, V>

fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K: KevyHash + Eq, V> FromIterator<(K, V)> for KevyMap<K, V>

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<K, Q, V> Index<&Q> for KevyMap<K, V>

where K: Borrow<Q>, Q: KevyHash + Eq + ?Sized,

m[&q] panics on missing key (matches std::HashMap::Index semantics).

type Output = V

The returned type after indexing.

fn index(&self, key: &Q) -> &V

Performs the indexing (container[index]) operation.

impl<'a, K, V> IntoIterator for &'a KevyMap<K, V>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a mut KevyMap<K, V>

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Send, V: Send> Send for KevyMap<K, V>

impl<K: Sync, V: Sync> Sync for KevyMap<K, V>