robinxx_map 0.1.0

//! Hashing primitives and `xxhash-rust` wrapper for `RobinHoodKey` trait.
//!
//! # Summary
//! Defines the custom trait required for all map keys, defaulting to `xxh3` 64-bit output.
//!
//! # Description
//! This module provides the `RobinHoodKey` trait, which abstracts the hashing process
//! for the `RobinHoodMap` data structure. It guarantees deterministic 64-bit xxHash3
//! output across platforms and runs, optimized for low-latency open-addressing probing.
//! Implementations cover common primitive types, string/byte types, and a macro for
//! extensibility. Fully `#![no_std]` compatible with explicit `alloc` support.
//!
//! # Examples
//! ```
//! use robinxx_map::RobinHoodKey;
//!
//! let key = 42u64;
//! let hash = key.hash_xxh3();
//! assert_eq!(key.hash_xxh3(), key.hash_xxh3(), "Hash must be deterministic");
//! ```
//!
//! # Panics
//! None. All hashing operations are infallible and do not allocate.
//!
//! # Errors
//! Not applicable. The trait method returns `u64` directly without `Result`.
//!
//! # Safety
//! Implementations must not read uninitialized memory. The blanket implementation
//! for byte-slice types guarantees safety via Rust's borrowing rules. Primitive
//! implementations use `to_ne_bytes()` to avoid undefined behavior from endianness.
//!
//! # See Also
//! - [`crate::map::RobinHoodMap`] for the primary data structure.
//! - [`xxhash_rust::xxh3`](https://docs.rs/xxhash-rust) for the underlying algorithm.

use ::alloc::string::String;
use xxhash_rust::xxh3::xxh3_64;

/// Trait for types that can be hashed using xxHash3 for `RobinHoodMap`.
///
/// # Summary
/// Abstracts key hashing to guarantee deterministic 64-bit xxHash3 output.
///
/// # Description
/// This trait allows `RobinHoodMap` to accept custom key types while ensuring
/// consistent, platform-independent hash values. Implementations must produce
/// identical hashes for identical inputs across runs. The trait is optimized
/// for low-latency execution to support high-throughput open-addressing probing.
///
/// # Examples
/// ```
/// use robinxx_map::RobinHoodKey;
///
/// let key = 42u64;
/// let hash = key.hash_xxh3();
/// assert_eq!(key.hash_xxh3(), key.hash_xxh3(), "Hash must be deterministic");
///
/// let data = "robinxx_map";
/// assert_eq!(data.hash_xxh3(), data.hash_xxh3()); // Deterministic
/// ```
///
/// # Panics
/// Never panics. xxHash3 operates on valid byte slices without allocation or unwinding.
///
/// # Errors
/// Not applicable. Returns `u64` directly; hashing is infallible.
///
/// # Safety
/// Implementations must not read uninitialized memory. The `AsRef<[u8]>` blanket
/// impl enforces this at compile time. Primitive impls use native endianness
/// via `to_ne_bytes()` to avoid undefined behavior.
///
/// # See Also
/// - [`crate::map::RobinHoodMap`] for the primary data structure.
/// - [`xxhash_rust::xxh3`](https://docs.rs/xxhash-rust) for the underlying non-cryptographic hash algorithm.
pub trait RobinHoodKey {
    /// Computes a 64-bit xxHash3 digest for the key.
    ///
    /// # Summary
    /// Returns a deterministic 64-bit hash value for the key.
    ///
    /// # Description
    /// The output is deterministic and platform-independent for identical inputs.
    /// The implementation is optimized for low latency to support high-throughput
    /// open-addressing probing in `RobinHoodMap`.
    ///
    /// # Examples
    /// ```
    /// use robinxx_map::RobinHoodKey;
    ///
    /// let data = "robinxx_map";
    /// let hash = data.hash_xxh3();
    /// assert_eq!(hash, data.hash_xxh3()); // Deterministic
    /// ```
    ///
    /// # Panics
    /// Never panics. xxHash3 operates on valid byte slices without allocation or unwinding.
    ///
    /// # Errors
    /// Not applicable.
    ///
    /// # Safety
    /// Caller must ensure `self` references initialized memory. The `AsRef<[u8]>`
    /// blanket impl enforces this at compile time. Primitive impls use native
    /// endianness to avoid undefined behavior.
    ///
    /// # See Also
    /// - [`RobinHoodKey`] trait definition.
    fn hash_xxh3(&self) -> u64;
}

/// Implementation of `RobinHoodKey` for `&str`.
///
/// # Summary
/// Hashes string slices using xxHash3 on UTF-8 byte representation.
///
/// # Description
/// Converts the string slice to its UTF-8 byte representation before hashing.
/// This ensures consistent hashing across platforms regardless of string encoding.
///
/// # Examples
/// ```
/// use robinxx_map::RobinHoodKey;
///
/// let s = "hello";
/// let hash = s.hash_xxh3();
/// assert!(hash != 0);
/// ```
///
/// # Panics
/// Never panics.
///
/// # Errors
/// Not applicable.
///
/// # Safety
/// Safe. Relies on Rust's guaranteed UTF-8 validity for `&str`.
///
/// # See Also
/// - [`RobinHoodKey::hash_xxh3`]
impl RobinHoodKey for &str {
    #[inline]
    fn hash_xxh3(&self) -> u64 {
        xxh3_64(self.as_bytes())
    }
}

/// Implementation of `RobinHoodKey` for `String`.
///
/// # Summary
/// Hashes owned strings using xxHash3 on UTF-8 byte representation.
///
/// # Description
/// Converts the owned `String` to its UTF-8 byte representation before hashing.
/// This ensures consistent hashing across platforms regardless of string encoding.
///
/// # Examples
/// ```
/// use robinxx_map::RobinHoodKey;
///
/// let s = String::from("hello");
/// let hash = s.hash_xxh3();
/// assert!(hash != 0);
/// ```
///
/// # Panics
/// Never panics.
///
/// # Errors
/// Not applicable.
///
/// # Safety
/// Safe. Relies on Rust's guaranteed UTF-8 validity for `String`.
///
/// # See Also
/// - [`RobinHoodKey::hash_xxh3`]
impl RobinHoodKey for String {
    #[inline]
    fn hash_xxh3(&self) -> u64 {
        xxh3_64(self.as_bytes())
    }
}

/// Implementation of `RobinHoodKey` for `&[u8]`.
///
/// # Summary
/// Hashes byte slices directly using xxHash3.
///
/// # Description
/// Provides direct hashing for arbitrary byte slices without encoding conversion.
/// Useful for binary keys or pre-hashed data.
///
/// # Examples
/// ```
/// use robinxx_map::RobinHoodKey;
///
/// let bytes: &[u8] = b"binary_key";
/// let hash = bytes.hash_xxh3();
/// assert!(hash != 0);
/// ```
///
/// # Panics
/// Never panics.
///
/// # Errors
/// Not applicable.
///
/// # Safety
/// Safe. Caller guarantees slice references initialized memory.
///
/// # See Also
/// - [`RobinHoodKey::hash_xxh3`]
impl RobinHoodKey for &[u8] {
    #[inline]
    fn hash_xxh3(&self) -> u64 {
        xxh3_64(self)
    }
}

/// Implementation of `RobinHoodKey` for `Vec<u8>`.
///
/// # Summary
/// Hashes owned byte vectors using xxHash3.
///
/// # Description
/// Provides direct hashing for owned byte vectors without encoding conversion.
/// Useful for binary keys or pre-hashed data with dynamic allocation.
///
/// # Examples
/// ```
/// use robinxx_map::RobinHoodKey;
///
/// let bytes: Vec<u8> = b"binary_key".to_vec();
/// let hash = bytes.hash_xxh3();
/// assert!(hash != 0);
/// ```
///
/// # Panics
/// Never panics.
///
/// # Errors
/// Not applicable.
///
/// # Safety
/// Safe. Relies on `Vec`'s guaranteed initialized memory.
///
/// # See Also
/// - [`RobinHoodKey::hash_xxh3`]
impl RobinHoodKey for alloc::vec::Vec<u8> {
    #[inline]
    fn hash_xxh3(&self) -> u64 {
        xxh3_64(self)
    }
}

/// Macro to implement `RobinHoodKey` for primitive integer types.
///
/// # Summary
/// Generates `RobinHoodKey` impls for integer primitives using native-endian byte conversion.
///
/// # Description
/// This macro reduces boilerplate by implementing `hash_xxh3` for multiple integer types
/// in a single invocation. Each implementation uses `to_ne_bytes()` for zero-copy serialization.
/// Hash values are consistent within a single platform but NOT guaranteed
/// to be identical across platforms with different byte orders (endianness).
/// For cross-platform hash consistency, implement `RobinHoodKey` manually
/// using `to_le_bytes()` or `to_be_bytes()`.
///
/// # Examples
/// ```ignore
/// // Internal usage - generates impls for listed types:
/// impl_hash_primitive!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
/// ```
///
/// # Panics
/// Never panics. `to_ne_bytes()` is infallible for primitive integers.
///
/// # Errors
/// Not applicable.
///
/// # Safety
/// Safe. `to_ne_bytes()` produces a valid byte array; xxHash3 operates on initialized memory.
///
/// # See Also
/// - [`RobinHoodKey`] trait definition.
/// - [`primitive::to_ne_bytes`](https://doc.rust-lang.org/std/primitive.i32.html#method.to_ne_bytes)
macro_rules! impl_hash_primitive {
    ($($t:ty),*) => {
        $(
            impl RobinHoodKey for $t {
                #[inline]
                fn hash_xxh3(&self) -> u64 {
                    xxh3_64(&self.to_ne_bytes())
                }
            }
        )*
    }
}

// Generate implementations for all standard integer primitives.
impl_hash_primitive!(
    u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize
);

/// Implementation of `RobinHoodKey` for `bool`.
///
/// # Summary
/// Hashes boolean values by mapping `true`→`[1u8]`, `false`→`[0u8]`.
///
/// # Description
/// Provides a simple, deterministic mapping for boolean keys. The single-byte
/// representation ensures minimal overhead while maintaining hash distribution
/// quality via xxHash3.
///
/// # Examples
/// ```
/// use robinxx_map::RobinHoodKey;
///
/// assert_ne!(true.hash_xxh3(), false.hash_xxh3());
/// ```
///
/// # Panics
/// Never panics.
///
/// # Errors
/// Not applicable.
///
/// # Safety
/// Safe. Uses a compile-time constant byte array.
///
/// # See Also
/// - [`RobinHoodKey::hash_xxh3`]
impl RobinHoodKey for bool {
    #[inline]
    fn hash_xxh3(&self) -> u64 {
        let byte = u8::from(*self);
        xxh3_64(&[byte])
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use alloc::string::String;

    #[test]
    fn test_u64_hash_deterministic() {
        let val: u64 = 12345;
        let h1 = val.hash_xxh3();
        let h2 = val.hash_xxh3();
        assert_eq!(h1, h2, "Hash must be deterministic for identical input")
    }

    #[test]
    fn test_str_hash_consistency() {
        let s1 = "robinhood";
        let s2 = String::from("robinhood");
        assert_eq!(
            s1.hash_xxh3(),
            s2.hash_xxh3(),
            "String and &str must produce identical hashes"
        );
    }

    #[test]
    fn test_empty_slice_hash() {
        let empty: &[u8] = &[];
        let hash = empty.hash_xxh3();
        assert_eq!(hash, xxh3_64(&[]));
    }

    #[test]
    fn test_bool_hash_distinct() {
        let h_true = true.hash_xxh3();
        let h_false = false.hash_xxh3();
        assert_ne!(
            h_true, h_false,
            "true and false must produce distinct hashes"
        );
    }

    #[test]
    fn test_primitive_endianness_stable() {
        let a: u32 = 0x11223344;
        let b: u32 = 0x11223344;
        assert_eq!(a.hash_xxh3(), b.hash_xxh3());
    }
}