kevy-map 7.0.0

use super::*;
use crate::raw_entry::RawEntryMut;
use crate::set::KevySet;
use std::cell::Cell;

#[test]
fn new_is_empty() {
    let m: KevyMap<u64, u64> = KevyMap::new();
    assert_eq!(m.len(), 0);
    assert!(m.is_empty());
    assert_eq!(m.capacity(), 0);
    assert_eq!(m.get(&5u64), None);
    assert!(!m.contains_key(&5u64));
}

#[test]
fn insert_get() {
    let mut m = KevyMap::<u64, u64>::new();
    assert!(m.insert(1, 10).is_none());
    assert_eq!(m.len(), 1);
    assert_eq!(m.get(&1u64), Some(&10));
    assert_eq!(m.get(&2u64), None);
    assert!(m.contains_key(&1u64));
}

#[test]
fn insert_duplicate_replaces_value_returns_old() {
    let mut m = KevyMap::<u64, u64>::new();
    assert_eq!(m.insert(1, 10), None);
    assert_eq!(m.insert(1, 20), Some(10));
    assert_eq!(m.len(), 1);
    assert_eq!(m.get(&1u64), Some(&20));
}

#[test]
fn remove_returns_value_decreases_len() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 10);
    m.insert(2, 20);
    assert_eq!(m.remove(&1u64), Some(10));
    assert_eq!(m.len(), 1);
    assert_eq!(m.remove(&1u64), None);
    assert_eq!(m.get(&1u64), None);
    assert_eq!(m.get(&2u64), Some(&20));
}

#[test]
fn tombstone_reused_on_reinsert() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 10);
    m.remove(&1u64);
    assert_eq!(m.len(), 0);
    m.insert(1, 30);
    assert_eq!(m.len(), 1);
    assert_eq!(m.get(&1u64), Some(&30));
}

#[test]
fn grow_preserves_all_entries_10k() {
    let mut m = KevyMap::<u64, u64>::new();
    let n = crate::scaled(10_000) as u64;
    for i in 0..n {
        m.insert(i, i.wrapping_mul(7));
    }
    assert_eq!(m.len(), n as usize);
    for i in 0..n {
        assert_eq!(m.get(&i), Some(&i.wrapping_mul(7)));
    }
}

#[test]
fn byte_string_keys_with_borrow_lookup() {
    let mut m = KevyMap::<Vec<u8>, u64>::new();
    m.insert(b"foo".to_vec(), 1);
    m.insert(b"bar".to_vec(), 2);
    assert_eq!(m.get(b"foo".as_slice()), Some(&1));
    assert_eq!(m.get(b"missing".as_slice()), None);
    assert_eq!(m.remove(b"bar".as_slice()), Some(2));
    assert_eq!(m.len(), 1);
    assert!(!m.contains_key(b"bar".as_slice()));
}

/// The three probes agree — including the arm that a fix made cold.
///
/// One probe loop is written three times in `map_keyed.rs`, and the split
/// is deliberate rather than accidental:
///
///  - `find_by_borrow` — lookup only, so it never tracks `DELETED`.
///  - `probe_by_borrow_fast` — lookup plus an insert slot, no tombstones.
///  - `probe_by_borrow_slow` — the same, remembering the first `DELETED`
///    so a later insert reclaims it.
///
/// The middle two exist because a lookup should not pay for insert
/// bookkeeping, and the third because tombstone tracking should not be paid
/// when there are none. All three walk groups, match `h2`, compare the
/// borrowed key and stop on `EMPTY`. What the rule against a second
/// implementation warns about is exactly this: they evolve apart, disagree
/// on some boundary, and both sets of tests stay green.
///
/// So this asks them the same question and requires the same answer, in
/// both table states. The slow arm reached fifteen never-executed regions
/// after the commit that stopped one `DEL` from putting the table on its
/// slow probe permanently — the fix working, and a correctness path going
/// quiet at the same time. `probe_by_borrow` is reached through
/// `raw_entry_mut`, which is the only caller; `get` takes `find_by_borrow`
/// instead, which is why a `get`-based test does not reach it at all.
#[test]
fn find_and_probe_agree_with_and_without_tombstones() {
    // Scaled, like every other heavy test here: miri interprets each access
    // and this crate's miri job is the CI wall clock. The paths this walks
    // are entered the same way at 64 keys as at 400 — several probe groups,
    // tombstones inside them — and the assertions below are derived from `n`
    // so a count too small to force those paths fails rather than passes on
    // less.
    let n = crate::scaled(400) as u64;
    let key = |i: u64| format!("key-{i:05}").into_bytes();
    let mut m = KevyMap::<Vec<u8>, u64>::new();
    for i in 0..n {
        m.insert(key(i), i);
    }

    // Both arms of `probe_by_borrow` are exercised: this first pass has no
    // tombstones, the second has 134 of them.
    let mut checked = 0;
    for phase in 0..2 {
        if phase == 1 {
            // Every third, so tombstones land inside groups rather than in
            // one run the probe can step over.
            let mut removed = 0;
            for i in (0..n).step_by(3) {
                assert_eq!(m.remove(key(i).as_slice()), Some(i), "removing {i}");
                removed += 1;
            }
            assert!(
                removed > 0 && (removed as u64) < n,
                "both states must exist: {removed} of {n}"
            );
        }
        for i in 0..n + 50 {
            let k = key(i);
            let by_find = m.find_by_borrow(k.as_slice()).is_some();
            let by_probe =
                matches!(m.probe_by_borrow(k.as_slice()), crate::map::ProbeOutcome::Found(_));
            assert_eq!(
                by_find, by_probe,
                "phase {phase}, key {i}: find_by_borrow says {by_find}, \
                 probe_by_borrow says {by_probe}"
            );
            let present = i < n && !(phase == 1 && i % 3 == 0);
            assert_eq!(by_find, present, "phase {phase}, key {i}: expected present={present}");
            checked += 1;
        }
    }
    assert_eq!(checked, 2 * (n + 50), "both phases ran over the whole key range");

    // And the slow arm's other job: a reinsert lands in a tombstone.
    let before = m.len();
    m.insert(key(0), 999);
    assert_eq!(m.len(), before + 1);
    assert_eq!(m.get(key(0).as_slice()), Some(&999));
}

#[test]
fn iter_yields_all_entries() {
    let mut m = KevyMap::<u64, u64>::new();
    for i in 0..20u64 {
        m.insert(i, i + 100);
    }
    let mut seen: Vec<(u64, u64)> = m.iter().map(|(&k, &v)| (k, v)).collect();
    seen.sort_unstable();
    let expected: Vec<(u64, u64)> = (0..20).map(|i| (i, i + 100)).collect();
    assert_eq!(seen, expected);
}

struct DropCount<'a>(&'a Cell<usize>);
impl Drop for DropCount<'_> {
    fn drop(&mut self) {
        self.0.set(self.0.get() + 1);
    }
}

#[test]
fn clear_drops_entries_and_resets_len() {
    let counter = Cell::new(0);
    let mut m: KevyMap<u64, DropCount<'_>> = KevyMap::new();
    for i in 0..50u64 {
        m.insert(i, DropCount(&counter));
    }
    assert_eq!(m.len(), 50);
    m.clear();
    assert_eq!(m.len(), 0);
    assert_eq!(counter.get(), 50);
    assert!(m.capacity() >= 50);
    m.insert(0, DropCount(&counter));
    assert_eq!(m.len(), 1);
    drop(m);
    assert_eq!(counter.get(), 51);
}

#[test]
fn drop_runs_for_remaining_entries() {
    let counter = Cell::new(0);
    {
        let mut m: KevyMap<u64, DropCount<'_>> = KevyMap::new();
        for i in 0..30u64 {
            m.insert(i, DropCount(&counter));
        }
        m.remove(&5u64);
        assert_eq!(counter.get(), 1);
    }
    assert_eq!(counter.get(), 30);
}

#[test]
fn grow_then_remove_then_grow_again_stays_consistent() {
    let mut m = KevyMap::<u64, u64>::new();
    let (half, full, twice) =
        (crate::scaled(1_000) as u64, crate::scaled(2_000) as u64, crate::scaled(4_000) as u64);
    for i in 0..full {
        m.insert(i, i);
    }
    for i in 0..half {
        assert_eq!(m.remove(&i), Some(i));
    }
    for i in full..twice {
        m.insert(i, i);
    }
    assert_eq!(m.len(), (twice - half) as usize);
    for i in half..twice {
        assert_eq!(m.get(&i), Some(&i));
    }
    for i in 0..half {
        assert_eq!(m.get(&i), None);
    }
}

#[test]
fn with_capacity_preallocates() {
    let m: KevyMap<u64, u64> = KevyMap::with_capacity(100);
    // ceil(100 * 8 / 7) = 115 → next_pow2 = 128
    assert_eq!(m.capacity(), 128);
    let m: KevyMap<u64, u64> = KevyMap::with_capacity(0);
    assert_eq!(m.capacity(), 0);
    let m: KevyMap<u64, u64> = KevyMap::with_capacity(1);
    assert_eq!(m.capacity(), MIN_CAP);
}

#[test]
fn get_mut_allows_mutation() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 10);
    *m.get_mut(&1u64).unwrap() = 20;
    assert_eq!(m.get(&1u64), Some(&20));
    assert!(m.get_mut(&2u64).is_none());
}

#[test]
fn debug_format_matches_map_shape() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 10);
    m.insert(2, 20);
    let s = format!("{m:?}");
    // Order is unspecified but both entries must appear and the shape is a map.
    assert!(s.starts_with('{'));
    assert!(s.ends_with('}'));
    assert!(s.contains("1: 10") || s.contains("1:10"));
    assert!(s.contains("2: 20") || s.contains("2:20"));
}

#[test]
fn into_iter_ref_works() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 10);
    m.insert(2, 20);
    let mut total = 0u64;
    for (k, v) in &m {
        total += *k + *v;
    }
    assert_eq!(total, 1 + 10 + 2 + 20);
}

#[test]
fn many_collisions_via_long_byte_keys() {
    // Stresses the linear probing loop on a real keyspace shape (variable-
    // length byte keys; the hasher avalanches via fmix64 so h2 distribution
    // is uniform — exercises real-world probe chains rather than a
    // degenerate collision storm).
    let mut m = KevyMap::<Vec<u8>, u64>::new();
    let n = crate::scaled(5_000) as u64;
    for i in 0..n {
        let k = format!("session:{i:08}:user").into_bytes();
        m.insert(k, i);
    }
    assert_eq!(m.len(), n as usize);
    for i in 0..n {
        let k = format!("session:{i:08}:user");
        assert_eq!(m.get(k.as_bytes()), Some(&i));
    }
}

#[test]
fn zst_value_type() {
    let mut m = KevyMap::<u64, ()>::new();
    assert!(m.insert(1, ()).is_none());
    assert!(m.insert(1, ()).is_some());
    assert!(m.contains_key(&1u64));
    assert_eq!(m.remove(&1u64), Some(()));
}

#[test]
fn set_basic_ops() {
    let mut s: KevySet<Vec<u8>> = KevySet::new();
    assert!(s.insert(b"a".to_vec()));
    assert!(!s.insert(b"a".to_vec())); // duplicate ⇒ false
    assert_eq!(s.len(), 1);
    assert!(s.contains(b"a".as_slice()));
    assert!(!s.contains(b"b".as_slice()));
    assert!(s.remove(b"a".as_slice()));
    assert!(!s.remove(b"a".as_slice()));
    assert!(s.is_empty());
}

#[test]
fn set_iter_yields_members() {
    let mut s: KevySet<u64> = KevySet::new();
    for i in 0..10u64 {
        s.insert(i);
    }
    let mut got: Vec<u64> = s.iter().copied().collect();
    got.sort_unstable();
    assert_eq!(got, (0..10u64).collect::<Vec<_>>());
}

#[test]
fn prefetch_for_hash_is_safe_on_any_state() {
    // Just exercise the API on empty and populated tables; it's a hint
    // with no observable side effect, so we can only test it doesn't
    // panic / miscompile.
    let m: KevyMap<u64, u64> = KevyMap::new();
    m.prefetch_for_hash(0);
    m.prefetch_for_hash(u64::MAX);
    let mut m = KevyMap::<u64, u64>::new();
    for i in 0..50u64 {
        m.insert(i, i);
    }
    for i in 0..50u64 {
        m.prefetch_for_hash(i.kevy_hash());
    }
}

#[test]
fn capacity_grows_doubling_from_min_cap() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 1);
    assert_eq!(m.capacity(), MIN_CAP);
    // Fill to just past 7/8 of MIN_CAP: threshold = 14
    for i in 2..=14u64 {
        m.insert(i, i);
    }
    // 14 entries, threshold = 14, next insert grows.
    m.insert(15, 15);
    assert_eq!(m.capacity(), MIN_CAP * 2);
}

// ---- API-surface smoke tests (coverage padding for delegating methods) --

#[test]
fn map_keys_iter() {
    let mut m = KevyMap::<u64, u64>::new();
    for i in 0..5u64 {
        m.insert(i, i + 10);
    }
    let mut ks: Vec<u64> = m.keys().copied().collect();
    ks.sort_unstable();
    assert_eq!(ks, vec![0, 1, 2, 3, 4]);
}

#[test]
fn map_values_iter() {
    let mut m = KevyMap::<u64, u64>::new();
    for i in 0..5u64 {
        m.insert(i, i + 10);
    }
    let mut vs: Vec<u64> = m.values().copied().collect();
    vs.sort_unstable();
    assert_eq!(vs, vec![10, 11, 12, 13, 14]);
}

#[test]
fn map_iter_mut_writes_visible_via_get() {
    let mut m = KevyMap::<u64, u64>::new();
    assert!(m.iter_mut().next().is_none()); // cap == 0 path

    for i in 0..50u64 {
        m.insert(i, i);
    }
    for i in (0..50u64).step_by(2) {
        m.remove(&i); // tombstones must be skipped, not yielded
    }
    let mut seen = 0usize;
    for (&k, v) in &mut m {
        assert_eq!(k % 2, 1);
        *v += 100;
        seen += 1;
    }
    assert_eq!(seen, 25);
    for i in (1..50u64).step_by(2) {
        assert_eq!(m.get(&i), Some(&(i + 100)));
    }
}

#[test]
fn map_default_is_empty() {
    let m: KevyMap<u64, u64> = KevyMap::default();
    assert!(m.is_empty());
    assert_eq!(m.capacity(), 0);
}

#[test]
fn map_from_iterator() {
    let m: KevyMap<u64, u64> = (0..10u64).map(|i| (i, i * 2)).collect();
    assert_eq!(m.len(), 10);
    assert_eq!(m.get(&5u64), Some(&10));
}

#[test]
fn map_extend() {
    let mut m = KevyMap::<u64, u64>::new();
    m.extend((0..5u64).map(|i| (i, i)));
    assert_eq!(m.len(), 5);
    assert_eq!(m.get(&3u64), Some(&3));
}

#[test]
fn map_index_panics_on_missing() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 10);
    assert_eq!(m[&1u64], 10);
    let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
        let _ = m[&99u64];
    }));
    assert!(r.is_err(), "Index on missing key should panic");
}

#[test]
fn set_with_capacity_capacity_clear() {
    let mut s: KevySet<u64> = KevySet::with_capacity(50);
    assert!(s.capacity() >= 50);
    for i in 0..10u64 {
        s.insert(i);
    }
    assert_eq!(s.len(), 10);
    s.clear();
    assert!(s.is_empty());
    // capacity preserved
    assert!(s.capacity() >= 50);
}

#[test]
fn set_as_map_smoke() {
    let mut s: KevySet<u64> = KevySet::new();
    s.insert(7);
    assert_eq!(s.as_map().len(), 1);
    assert!(s.as_map().contains_key(&7u64));
}

#[test]
fn set_default_debug() {
    let s: KevySet<u64> = KevySet::default();
    assert!(s.is_empty());
    let dbg = format!("{s:?}");
    assert_eq!(dbg, "{}");
}

#[test]
fn set_into_iter_ref() {
    let mut s: KevySet<u64> = KevySet::new();
    for i in 0..3u64 {
        s.insert(i);
    }
    let mut sum = 0u64;
    for k in &s {
        sum += k;
    }
    assert_eq!(sum, 3);
}

#[test]
fn set_from_iterator() {
    let s: KevySet<u64> = (0..5u64).collect();
    assert_eq!(s.len(), 5);
    assert!(s.contains(&3u64));
}

#[test]
fn set_extend() {
    let mut s: KevySet<u64> = KevySet::new();
    s.extend(0..5u64);
    assert_eq!(s.len(), 5);
}

// ──────────────────── Clone (COW-serialization E-1) ────────────────────

#[test]
fn clone_preserves_entries_and_independence() {
    let mut m: KevyMap<Vec<u8>, u64> = KevyMap::new();
    let n = crate::scaled(1_000) as u64;
    for i in 0..n {
        m.insert(format!("k{i}").into_bytes(), i);
    }
    let c = m.clone();
    assert_eq!(c.len(), n as usize);
    for i in 0..n {
        assert_eq!(c.get(format!("k{i}").as_bytes()), Some(&i));
    }
    // Independence both ways.
    m.insert(b"k5".to_vec(), 999_999);
    m.remove(b"k7".as_slice());
    assert_eq!(c.get(b"k5".as_slice()), Some(&5));
    assert_eq!(c.get(b"k7".as_slice()), Some(&7));
}

/// Tombstones must survive the clone: probes walk through DELETED and stop
/// at EMPTY, so a dropped tombstone would strand every key inserted past it.
#[test]
fn clone_after_heavy_deletion_keeps_probes_correct() {
    let mut m: KevyMap<Vec<u8>, u64> = KevyMap::new();
    for i in 0..crate::scaled(4096) as u64 {
        m.insert(format!("key-{i}").into_bytes(), i);
    }
    for i in (0..crate::scaled(4096) as u64).step_by(2) {
        assert!(m.remove(format!("key-{i}").as_bytes()).is_some());
    }
    let c = m.clone();
    assert_eq!(c.len(), m.len());
    for i in 0..crate::scaled(4096) as u64 {
        let want = (i % 2 == 1).then_some(i);
        assert_eq!(c.get(format!("key-{i}").as_bytes()).copied(), want, "key-{i}");
    }
}

#[test]
fn clone_empty_and_unallocated() {
    let m: KevyMap<Vec<u8>, u64> = KevyMap::new();
    let c = m.clone();
    assert!(c.is_empty());
    assert_eq!(c.capacity(), 0);

    let mut m2: KevyMap<Vec<u8>, u64> = KevyMap::with_capacity(64);
    m2.insert(b"a".to_vec(), 1);
    m2.remove(b"a".as_slice());
    let c2 = m2.clone(); // allocated, zero live entries, one tombstone
    assert!(c2.is_empty());
    assert_eq!(c2.capacity(), m2.capacity());
}

#[test]
fn clone_set_round_trip() {
    let mut s: KevySet<Vec<u8>> = KevySet::new();
    for i in 0..100u32 {
        s.insert(format!("m{i}").into_bytes());
    }
    let c = s.clone();
    assert_eq!(c.len(), 100);
    assert!(c.contains(b"m42".as_slice()));
}

// --- raw_entry_mut --------------------------------------------------------

#[test]
fn raw_entry_mut_occupied_get_and_get_mut() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(7, 100);
    match m.raw_entry_mut(&7u64) {
        RawEntryMut::Occupied(mut occ) => {
            assert_eq!(occ.key(), &7u64);
            assert_eq!(occ.get(), &100);
            *occ.get_mut() = 200;
            assert_eq!(occ.get(), &200);
        }
        RawEntryMut::Vacant(_) => panic!("expected Occupied for present key"),
    }
    assert_eq!(m.get(&7u64), Some(&200));
}

#[test]
fn raw_entry_mut_into_mut_returns_existing_borrow() {
    // into_mut consumes the handle but the &mut V it returns must
    // borrow from the original map borrow (lifetime 'a), not from the
    // (now-gone) handle. Compile-checks the lifetime contract.
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(1, 42);
    let v: &mut u64 = match m.raw_entry_mut(&1u64) {
        RawEntryMut::Occupied(occ) => occ.into_mut(),
        RawEntryMut::Vacant(_) => panic!("expected Occupied"),
    };
    *v = 999;
    assert_eq!(m.get(&1u64), Some(&999));
}

#[test]
fn raw_entry_mut_remove_drops_entry_and_releases_borrow() {
    let mut m = KevyMap::<u64, u64>::new();
    m.insert(11, 110);
    m.insert(22, 220);
    let removed = match m.raw_entry_mut(&11u64) {
        RawEntryMut::Occupied(occ) => occ.remove(),
        RawEntryMut::Vacant(_) => panic!("expected Occupied"),
    };
    assert_eq!(removed, 110);
    assert_eq!(m.len(), 1);
    assert_eq!(m.get(&11u64), None);
    assert_eq!(m.get(&22u64), Some(&220));
    // Re-insert into the slot we just freed (tombstone reuse path).
    assert!(m.insert(11, 111).is_none());
    assert_eq!(m.get(&11u64), Some(&111));
}

#[test]
fn raw_entry_mut_vacant_insert_returns_new_mut() {
    let mut m = KevyMap::<u64, u64>::new();
    let v: &mut u64 = match m.raw_entry_mut(&5u64) {
        RawEntryMut::Vacant(vac) => vac.insert(5, 50),
        RawEntryMut::Occupied(_) => panic!("expected Vacant on empty map"),
    };
    assert_eq!(*v, 50);
    *v = 51;
    assert_eq!(m.get(&5u64), Some(&51));
    assert_eq!(m.len(), 1);
}

#[test]
fn raw_entry_mut_vacant_insert_grows_when_needed() {
    // Fill to ≥ threshold (7/8 of MIN_CAP = 14 entries) so the next
    // raw-entry vacant insert triggers maybe_grow internally.
    let mut m = KevyMap::<u64, u64>::new();
    for i in 0..20u64 {
        m.insert(i, i.wrapping_mul(3));
    }
    match m.raw_entry_mut(&999u64) {
        RawEntryMut::Vacant(vac) => {
            let v = vac.insert(999, 1234);
            assert_eq!(*v, 1234);
        }
        RawEntryMut::Occupied(_) => panic!("expected Vacant for fresh key"),
    }
    assert_eq!(m.get(&999u64), Some(&1234));
    for i in 0..20u64 {
        assert_eq!(m.get(&i), Some(&i.wrapping_mul(3)));
    }
}

#[test]
fn raw_entry_mut_borrow_lookup_with_bytes_key() {
    // Mirrors the Store::live_entry use case: lookup by &[u8] borrow,
    // hold the entry, then either keep the borrow or remove via the
    // same handle.
    let mut m = KevyMap::<Vec<u8>, u64>::new();
    m.insert(b"alpha".to_vec(), 1);
    m.insert(b"beta".to_vec(), 2);
    match m.raw_entry_mut(b"alpha".as_slice()) {
        RawEntryMut::Occupied(occ) => {
            assert_eq!(occ.get(), &1);
            let val = occ.remove();
            assert_eq!(val, 1);
        }
        RawEntryMut::Vacant(_) => panic!("expected Occupied"),
    }
    assert_eq!(m.get(b"alpha".as_slice()), None);
    assert_eq!(m.get(b"beta".as_slice()), Some(&2));
}

// ── growth under churn: the table may not ratchet on tombstones ──────
//
// The load check counts `occupied + deleted`, so a workload that keeps a
// constant live set — the ordinary Redis shape of expiry, eviction and
// DEL — drives the table through grow after grow on tombstones alone,
// and every grow doubles. The live set never moves; the allocation does,
// and never comes back.

/// Insert and delete in step, so `len()` never moves, and the capacity
/// must not either past the first settle.
///
/// A table at 7/8 load holds `cap` slots for `7cap/8` live entries, so
/// the ceiling this asserts is 8/7 of what a full table would need. The
/// number to beat is not tight — it is the difference between "bounded"
/// and "doubling forever".
#[test]
fn churn_at_a_constant_live_set_does_not_grow_the_table() {
    let mut m: KevyMap<Vec<u8>, u64> = KevyMap::new();
    // Under miri the loop is interpreted, so a smaller set; it stays a
    // power of two so the table settles at the same half load as 4096
    // does. 409 would sit above 7/8 of 512 and grow once on its first
    // tombstones, which is not the ratchet this looks for.
    const LIVE: usize = if cfg!(miri) { 512 } else { 4096 };
    for i in 0..LIVE {
        m.insert(format!("k{i}").into_bytes(), i as u64);
    }
    let settled = m.capacity();
    assert!(settled >= LIVE, "sanity: the table holds what was put in it");

    // Ten times the live set, in and out, one for one.
    for i in LIVE..LIVE * 11 {
        m.insert(format!("k{i}").into_bytes(), i as u64);
        m.remove(format!("k{}", i - LIVE).as_bytes());
        assert_eq!(m.len(), LIVE, "the live set is the invariant of this loop");
    }

    assert_eq!(
        m.capacity(),
        settled,
        "the live set never moved, so neither should the table: {} slots for {LIVE} \
         entries after 10x churn, settled at {settled}",
        m.capacity()
    );
}

/// The narrower half of the same question, isolated: one `DEL` must not
/// leave the table permanently on its slow probe path.
#[test]
fn a_single_erase_leaves_no_tombstone_when_the_group_has_room() {
    let mut m: KevyMap<Vec<u8>, u64> = KevyMap::new();
    m.insert(b"only".to_vec(), 1);
    assert_eq!(m.remove(b"only".as_slice()), Some(1));
    assert_eq!(m.len(), 0);
    assert_eq!(
        m.tombstones(),
        0,
        "a group with fifteen empty slots has nowhere for a probe to continue to, \
         so the erased slot is EMPTY and not DELETED"
    );
}

/// The slow probe path still exists for the case that still needs it.
///
/// `erase_mark` writes `EMPTY` where no probe could have walked
/// through, which is most single erases — and that is the point. But a
/// dense table erased in the middle of a run leaves real tombstones,
/// and the probe has to walk past them to the key beyond. Without a
/// test that reaches it, the path went from three never-executed
/// regions to fifteen.
#[test]
fn a_probe_walks_past_tombstones_to_the_key_beyond() {
    let mut m: KevyMap<Vec<u8>, u64> = KevyMap::new();
    // Enough to fill several groups so a run of full slots exists.
    for i in 0..2048u64 {
        m.insert(format!("k{i}").into_bytes(), i);
    }
    // Erase a long contiguous stretch of the key space. Some of these
    // land inside runs and must become tombstones.
    for i in 200..1400u64 {
        m.remove(format!("k{i}").as_bytes());
    }
    assert!(m.tombstones() > 0, "a dense erase must leave some tombstone to probe past");
    // Every survivor is still reachable, which is what a tombstone is for.
    for i in (0..200u64).chain(1400..2048) {
        assert_eq!(
            m.get(format!("k{i}").as_bytes()),
            Some(&i),
            "k{i} became unreachable across the erased stretch"
        );
    }
    // And the erased ones are gone, not merely hidden.
    for i in 200..1400u64 {
        assert_eq!(m.get(format!("k{i}").as_bytes()), None, "k{i} came back");
    }
}

#[test]
fn into_iter_moves_each_entry_out_once_and_drops_the_rest() {
    let counter = Cell::new(0usize);
    let mut m: KevyMap<u64, DropCount<'_>> = KevyMap::new();
    for i in 0..100 {
        m.insert(i, DropCount(&counter));
    }
    let mut it = m.into_iter();
    assert_eq!(it.len(), 100);
    let taken: Vec<_> = it.by_ref().take(30).collect();
    assert_eq!((taken.len(), it.len(), counter.get()), (30, 70, 0));
    drop(it);
    assert_eq!(counter.get(), 70, "the 70 never yielded drop with the iterator");
    drop(taken);
    assert_eq!(counter.get(), 100, "and the yielded ones exactly once, by their owner");
}

#[test]
fn into_iter_of_an_unallocated_map_is_empty() {
    let m: KevyMap<u64, u64> = KevyMap::new();
    assert_eq!(m.into_iter().next(), None);
    let s: KevySet<u64> = KevySet::new();
    assert_eq!(s.into_iter().count(), 0);
}

#[test]
fn a_mapped_table_hands_back_pages_as_it_grows_and_keeps_every_entry() {
    // (u64, [u64; 7]) slots are 64 bytes: 2^17 of them fill 8 MiB, so the
    // growth to 2^18 moves out of a mapped table four huge pages long and
    // hands the first ones back while later entries are still to move
    let n = if cfg!(miri) { 2_000 } else { 120_000 };
    let mut m: KevyMap<u64, [u64; 7]> = KevyMap::new();
    for i in 0..n {
        m.insert(i, [i; 7]);
    }
    if !cfg!(miri) {
        assert_eq!(m.capacity(), 1 << 18, "the last growth moved a 2^17 table");
    }
    for i in 0..n {
        assert_eq!(m.get(&i), Some(&[i; 7]), "entry {i} survived the move");
    }
    assert_eq!(m.len(), n as usize);
}