kevy-map 7.0.0

//! Unit tests for [`KevyMap::scan_step`] — full-sweep coverage on a
//! fixed table, duplicate-freedom without rehash, and the dictScan
//! guarantee (no key present throughout is skipped) across a grow that
//! happens mid-sweep.

use std::collections::HashMap;

use crate::map::KevyMap;
use crate::scaled;

/// Drive a full sweep (cursor 0 → … → 0), recording how many times each
/// key was visited.
fn full_sweep(m: &KevyMap<u64, u64>) -> HashMap<u64, usize> {
    let mut seen: HashMap<u64, usize> = HashMap::new();
    let mut cursor = 0u64;
    let mut steps = 0usize;
    loop {
        cursor = m.scan_step(cursor, |k, _| {
            *seen.entry(*k).or_insert(0) += 1;
        });
        steps += 1;
        assert!(steps <= m.capacity().max(16), "sweep did not terminate");
        if cursor == 0 {
            break;
        }
    }
    seen
}

#[test]
fn empty_map_is_done_immediately() {
    let m: KevyMap<u64, u64> = KevyMap::new();
    let mut visited = 0;
    assert_eq!(m.scan_step(0, |_, _| visited += 1), 0);
    assert_eq!(visited, 0);
}

#[test]
fn full_coverage_exactly_once_on_fixed_table() {
    // Pre-size so no grow happens during the sweep: every live key must
    // be visited EXACTLY once (home groups partition the keyspace).
    let mut m: KevyMap<u64, u64> = KevyMap::with_capacity(scaled(10_000));
    for i in 0..scaled(10_000) as u64 {
        m.insert(i, i * 2);
    }
    let cap_before = m.capacity();
    let seen = full_sweep(&m);
    assert_eq!(m.capacity(), cap_before, "table grew unexpectedly");
    assert_eq!(seen.len(), scaled(10_000), "missed keys");
    for (k, n) in &seen {
        assert_eq!(*n, 1, "key {k} visited {n} times on a static table");
    }
}

#[test]
fn coverage_survives_tombstones() {
    // Deletions leave DELETED metadata; survivors must still all be
    // found exactly once (tombstone-reuse displacement is the tricky
    // path for the run-termination bound).
    let mut m: KevyMap<u64, u64> = KevyMap::with_capacity(scaled(4_096));
    for i in 0..scaled(4_000) as u64 {
        m.insert(i, i);
    }
    for i in (0..scaled(4_000) as u64).step_by(3) {
        m.remove(&i);
    }
    // Re-insert a few so tombstone reuse actually happens.
    for i in (0..scaled(600) as u64).step_by(3) {
        m.insert(i, i + 1);
    }
    let want: Vec<u64> =
        (0..scaled(4_000) as u64).filter(|i| i % 3 != 0 || *i < scaled(600) as u64).collect();
    let seen = full_sweep(&m);
    assert_eq!(seen.len(), want.len());
    for k in &want {
        assert_eq!(seen.get(k), Some(&1), "key {k} not visited exactly once");
    }
}

#[test]
fn grow_mid_sweep_never_skips_an_original_key() {
    // The dictScan guarantee: keys present for the WHOLE sweep are
    // returned at least once even when the table rehashes (grows)
    // between steps. Insert 2k keys, scan a few steps, then insert
    // 8k more (forcing at least two capacity doublings), finish the
    // sweep — every original key must have been seen.
    let mut m: KevyMap<u64, u64> = KevyMap::new();
    for i in 0..scaled(2_000) as u64 {
        m.insert(i, i);
    }
    let cap_small = m.capacity();

    let mut seen: HashMap<u64, usize> = HashMap::new();
    let mut cursor = 0u64;
    for _ in 0..8 {
        cursor = m.scan_step(cursor, |k, _| {
            *seen.entry(*k).or_insert(0) += 1;
        });
        assert_ne!(cursor, 0, "sweep finished before the grow could happen");
    }

    for i in scaled(2_000) as u64..scaled(10_000) as u64 {
        m.insert(i, i);
    }
    assert!(m.capacity() >= cap_small * 4, "test needs ≥2 doublings");

    let mut steps = 0usize;
    while cursor != 0 {
        cursor = m.scan_step(cursor, |k, _| {
            *seen.entry(*k).or_insert(0) += 1;
        });
        steps += 1;
        assert!(steps <= m.capacity(), "sweep did not terminate");
    }

    for i in 0..scaled(2_000) as u64 {
        assert!(seen.contains_key(&i), "original key {i} skipped across the grow");
    }
}

#[test]
fn cursor_stays_within_group_mask() {
    // Garbage high bits in a client-supplied cursor must be masked away
    // by the increment (dictScan's `v |= ~mask` trick) — the returned
    // cursor always addresses a real group of the current table.
    let mut m: KevyMap<u64, u64> = KevyMap::with_capacity(1_000);
    for i in 0..1_000u64 {
        m.insert(i, i);
    }
    let ngroups = (m.capacity() / 16) as u64;
    let garbage = (0xDEAD_BEEFu64 << 32) | 3;
    let next = m.scan_step(garbage, |_, _| {});
    assert!(next < ngroups, "cursor {next} escaped the group mask");
}

#[test]
fn a_bucket_walk_sees_every_key_once_while_the_capacity_holds() {
    let mut m: KevyMap<u64, u64> = KevyMap::with_capacity(4_000);
    for i in 0..3_000u64 {
        m.insert(i, i);
    }
    let cap = m.capacity();
    let (mut seen, mut at, mut round) = (HashMap::new(), 0, 0u64);
    while at < m.capacity() {
        at = m.scan_buckets(at, 64, |k, _| *seen.entry(*k).or_insert(0usize) += 1);
        // removals and inserts that fit move nothing already placed
        m.remove(&(round * 7));
        m.insert(10_000 + round, 0);
        round += 1;
    }
    assert_eq!(m.capacity(), cap, "the test needs a walk without growth");
    for i in 0..3_000u64 {
        let removed = i % 7 == 0 && i / 7 < round;
        if !removed {
            assert_eq!(seen.get(&i), Some(&1), "key {i} present throughout");
        }
    }
}

#[test]
fn a_bucket_walk_restarted_on_growth_misses_nothing() {
    // just under the 7/8 growth threshold of a 4096-bucket table
    let n = 3_500u64;
    let mut m: KevyMap<u64, u64> = KevyMap::new();
    for i in 0..n {
        m.insert(i, i);
    }
    let mut seen: HashMap<u64, usize> = HashMap::new();
    let first_cap = m.capacity();
    let (mut at, mut cap, mut next) = (0, first_cap, 1_000_000u64);
    while at < m.capacity() {
        if m.capacity() != cap {
            (at, cap) = (0, m.capacity());
        }
        at = m.scan_buckets(at, 16, |k, _| *seen.entry(*k).or_insert(0) += 1);
        // one insert a group: enough to grow the table mid-walk, too few
        // to grow it again before a restarted walk can finish
        m.insert(next, 0);
        next += 1;
    }
    assert!(cap > first_cap, "the test needs growth mid-walk");
    for i in 0..n {
        assert!(seen.contains_key(&i), "key {i} present throughout was skipped");
    }
}