fhp_core/
hash.rs

1//! Fast hash functions for selector matching.
2//!
3//! Provides FNV-1a hashing used by the arena (to compute per-node class/id
4//! hashes during tree building) and by the selector matcher (to reject
5//! non-matching nodes with a single integer comparison).
6
7/// FNV-1a hash of a byte slice, returning a `u32`.
8///
9/// Used for exact-match comparisons (id_hash) and as a building block
10/// for the class bloom filter.
11#[inline]
12pub fn selector_hash(bytes: &[u8]) -> u32 {
13    let mut hash: u32 = 2_166_136_261; // FNV offset basis
14    for &byte in bytes {
15        hash ^= byte as u32;
16        hash = hash.wrapping_mul(16_777_619); // FNV prime
17    }
18    hash
19}
20
21/// Compute a single bloom bit position from a class token.
22///
23/// Returns a `u64` with exactly one bit set at position `hash % 64`.
24/// Used to build and query the per-node 64-bit class bloom filter.
25#[inline]
26pub fn class_bloom_bit(class_bytes: &[u8]) -> u64 {
27    1u64 << (selector_hash(class_bytes) % 64)
28}
29
30#[cfg(test)]
31mod tests {
32    use super::*;
33
34    #[test]
35    fn hash_deterministic() {
36        assert_eq!(selector_hash(b"hello"), selector_hash(b"hello"));
37    }
38
39    #[test]
40    fn hash_different_inputs() {
41        assert_ne!(selector_hash(b"hello"), selector_hash(b"world"));
42    }
43
44    #[test]
45    fn hash_empty() {
46        // Empty input should return the offset basis.
47        assert_eq!(selector_hash(b""), 2_166_136_261);
48    }
49
50    #[test]
51    fn bloom_bit_single_bit() {
52        let bit = class_bloom_bit(b"content");
53        assert_eq!(bit.count_ones(), 1);
54    }
55
56    #[test]
57    fn bloom_bit_in_range() {
58        let bit = class_bloom_bit(b"test");
59        assert!(bit != 0);
60        assert!(bit.is_power_of_two());
61    }
62}
fhp_core/hash.rs

fhp_core/
hash.rs
