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 table_allocation(&self) -> Option<(*const u8, Layout)>

The table’s own allocation as the global allocator made it: its start and layout. None when there is no table, or when a large one was mapped directly rather than allocated. What a defrag pass asks the allocator about before copying a map.

use kevy_map::KevyMap;
let mut m: KevyMap<u32, u32> = KevyMap::new();
assert!(m.table_allocation().is_none(), "nothing allocated yet");
m.insert(1, 2);
let (ptr, layout) = m.table_allocation().ok_or("a table")?;
assert!(!ptr.is_null() && layout.size() > 0);

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

pub fn footprint(&self) -> usize

Bytes the table occupies where it lives: the whole mapping for a table large enough to be mapped directly, otherwise its one block’s malloc_footprint. 0 before anything was inserted.

A pure function of the capacity, so a caller can charge a growth by reading this before and after an insert.

let mut m: kevy_map::KevyMap<u64, u64> = kevy_map::KevyMap::new();
assert_eq!(m.footprint(), 0, "no table yet");
m.insert(1, 1);
// sixteen 16-byte slots, then one control byte each plus a trailing group
assert_eq!(m.footprint(), kevy_map::malloc_footprint(16 * 16 + 16 + 16));

pub fn grown_footprint(&self) -> usize

The bytes Self::footprint will read once the table has grown to twice its capacity (sixteen slots for a map with no table yet): what a caller holding memory to a budget sets aside before the growth arrives, so the growth does not land on memory it has no room for.

let mut m: kevy_map::KevyMap<u64, u64> = kevy_map::KevyMap::new();
m.insert(1, 1);
let promised = m.grown_footprint();
while m.room() > 0 {
    m.insert(m.len() as u64 + 1, 0);
}
m.insert(u64::MAX, 0); // no room left: this insert grows the table
assert_eq!(m.footprint(), promised);

pub fn room(&self) -> usize

New keys the table takes before an insert grows it: 0 when the next insert rebuilds it (or there is no table yet).

let mut m: kevy_map::KevyMap<u64, u64> = kevy_map::KevyMap::new();
assert_eq!(m.room(), 0, "no table yet");
m.insert(1, 1);
// sixteen slots hold fourteen keys at the 7/8 load bound
assert_eq!(m.room(), 14 - 1);

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

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

KevyMap::insert, also answering by how many bytes Self::footprint moved — nonzero only when the insert had to grow the table first, and then read around the growth alone, so an insert that does not grow costs what a plain one does.

let mut m: kevy_map::KevyMap<u32, u32> = kevy_map::KevyMap::new();
let (old, grown) = m.insert_sized(1, 10);
assert_eq!((old, grown), (None, m.footprint() as isize), "the first insert allocates");
assert_eq!(m.insert_sized(1, 11), (Some(10), 0), "an overwrite with room moves nothing");

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.

pub fn tombstones(&self) -> usize

Slots holding a tombstone: erased, but still probed through.

A test’s window onto the growth question — the load check counts occupied + deleted, so this is half of what decides a grow.

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

pub fn scan_buckets( &self, start: usize, count: usize, f: impl FnMut(&K, &V), ) -> usize

Visit buckets [start, start + count) in storage order and return where the next call should start; a return of Self::capacity means the walk reached the end.

The order KevyMap::iter uses, so neighbouring entries come out together and nothing is rehashed to find its place. Positions hold only while the capacity does: removals leave their slot and inserts never move an entry, but a growth moves every one. A walk that lets the map change between calls restarts when the capacity changes; KevyMap::scan_step is the walk that needs no restart, at the price of hashing every entry it visits.

Examples

let mut m = kevy_map::KevyMap::new();
for i in 0..100u32 { m.insert(i, i); }
let (mut seen, mut at) = (Vec::new(), 0);
while at < m.capacity() {
    at = m.scan_buckets(at, 32, |k, _| seen.push(*k));
}
seen.sort_unstable();
assert_eq!(seen, (0..100).collect::<Vec<_>>());

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

pub fn find_slot<Q>(&self, key: &Q) -> Option<usize>

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

The slot key occupies, or None if it is absent. One probe; the index stays valid until the next insert or remove.

let mut m = kevy_map::KevyMap::new();
m.insert(7u64, "seven");
let slot = m.find_slot(&7).ok_or("present")?;
assert_eq!(m.slot(slot), Some((&7, &"seven")));
assert_eq!(m.find_slot(&8), None);

pub fn slot(&self, slot: usize) -> Option<(&K, &V)>

The key and value at slot, or None when the slot is out of range or not occupied. No hashing; the returned key says whose entry it is.

let mut m = kevy_map::KevyMap::new();
m.insert(1u64, 10u32);
let slot = m.find_slot(&1).ok_or("present")?;
m.remove(&1);
assert_eq!(m.slot(slot), None, "a freed slot reads as empty");
assert_eq!(m.slot(usize::MAX), None);

pub fn slot_mut(&mut self, slot: usize) -> Option<(&K, &mut V)>

Mutable slot: the key and a mutable value at slot, or None when the slot is out of range or not occupied.

let mut m = kevy_map::KevyMap::new();
m.insert(1u64, 10u32);
let slot = m.find_slot(&1).ok_or("present")?;
if let Some((&1, v)) = m.slot_mut(slot) {
    *v += 1;
}
assert_eq!(m.get(&1), Some(&11));

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: Eq> Eq for KevyMap<K, V>

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: T)

🔬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<K, V> IntoIterator for KevyMap<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<K, V>

Creates an iterator from a value.

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, V> PartialEq for KevyMap<K, V>

where K: KevyHash + Eq, V: PartialEq,

Two maps are equal when they hold the same keys, each with an equal value — capacity and probe layout do not matter.

use kevy_map::KevyMap;
let a: KevyMap<u64, u8> = [(1, 1), (2, 2)].into_iter().collect();
let mut b = KevyMap::with_capacity(64);
b.insert(2, 2);
b.insert(1, 1);
assert_eq!(a, b);
b.insert(3, 3);
assert_ne!(a, b);

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

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

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