//! A fast hasher for the in-memory graphs (spec §25): their keys begin with

//! BLAKE3 hashes, so the bytes are already uniform and SipHash's cost buys

//! nothing. A per-process random seed keeps bucket placement unpredictable,

//! so keys chosen by someone else cannot be aimed at one bucket.

use std::hash::{BuildHasher, Hasher};

use std::sync::OnceLock;

fn seed() -> u64 {

    static SEED: OnceLock<u64> = OnceLock::new();

    *SEED.get_or_init(rand::random::<u64>)

}

/// Builds [`FastHasher`]s with the process seed.

#[derive(Clone, Copy, Debug)]

pub struct FastState(u64);

impl Default for FastState {

    fn default() -> FastState {

        FastState(seed())

    }

}

impl BuildHasher for FastState {

    type Hasher = FastHasher;

    fn build_hasher(&self) -> FastHasher {

        FastHasher(self.0)

    }

}

/// Folds each 8-byte word into the state with a multiply and rotate, then

/// finishes with SplitMix64's mixer so every input bit reaches every output bit.

pub struct FastHasher(u64);

impl FastHasher {

    #[inline]

    fn mix(&mut self, word: u64) {

        self.0 = (self.0 ^ word)

            .wrapping_mul(0x9e37_79b9_7f4a_7c15)

            .rotate_left(31);

    }

}

impl Hasher for FastHasher {

    #[inline]

    fn write(&mut self, bytes: &[u8]) {

        let (chunks, rest) = bytes.as_chunks::<8>();

        for c in chunks {

            self.mix(u64::from_le_bytes(*c));

        }

        if !rest.is_empty() {

            let mut b = [0u8; 8];

            b[..rest.len()].copy_from_slice(rest);

            self.mix(u64::from_le_bytes(b) ^ ((rest.len() as u64) << 59));

        }

    }

    #[inline]

    fn write_u8(&mut self, n: u8) {

        self.mix(n as u64 | 0x100);

    }

    #[inline]

    fn write_u32(&mut self, n: u32) {

        self.mix(n as u64 | 0x1_0000_0000);

    }

    #[inline]

    fn write_u64(&mut self, n: u64) {

        self.mix(n);

    }

    #[inline]

    fn write_usize(&mut self, n: usize) {

        self.mix(n as u64);

    }

    #[inline]

    fn finish(&self) -> u64 {

        let mut z = self.0;

        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);

        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);

        z ^ (z >> 31)

    }

}

pub type FastMap<K, V> = std::collections::HashMap<K, V, FastState>;

pub type FastSet<K> = std::collections::HashSet<K, FastState>;

#[cfg(test)]

mod tests {

    use super::*;

    use std::hash::Hash;

    fn h<T: Hash + ?Sized>(state: &FastState, v: &T) -> u64 {

        state.hash_one(v)

    }

    #[test]

    fn distinct_keys_spread_and_equal_keys_agree() {

        let s = FastState(42);

        let a = ([7u8; 32], 1u32);

        assert_eq!(h(&s, &a), h(&s, &a));

        assert_ne!(h(&s, &a), h(&s, &([7u8; 32], 2u32)), "the index matters");

        assert_ne!(

            h(&s, &[1u8, 2, 3][..]),

            h(&s, &[1u8, 2, 3, 0][..]),

            "length matters"

        );

        // Consecutive indices of one change land in different buckets of a small table.

        let buckets: std::collections::HashSet<u64> =

            (0..64u32).map(|i| h(&s, &([9u8; 32], i)) & 63).collect();

        assert!(buckets.len() > 32, "{} of 64 buckets used", buckets.len());

        assert_ne!(

            h(&FastState(1), &a),

            h(&FastState(2), &a),

            "the seed matters"

        );

    }

    #[test]

    fn maps_work() {

        let mut m: FastMap<([u8; 32], u32), u32> = FastMap::default();

        for i in 0..10_000u32 {

            m.insert(([(i % 251) as u8; 32], i), i);

        }

        assert_eq!(m.len(), 10_000);

        assert_eq!(m[&([77u8; 32], 77)], 77);

    }

}