musli_zerocopy/phf/
hashing.rs

1use core::hash::Hash;
2
3use crate::buf::{Buf, Visit};
4use crate::error::{Error, ErrorKind};
5use crate::phf::Entry;
6use crate::sip::{Hash128, Hasher128, SipHasher13};
7
8#[non_exhaustive]
9pub(crate) struct Hashes {
10    pub(crate) g: usize,
11    pub(crate) f1: u32,
12    pub(crate) f2: u32,
13}
14
15pub(crate) type HashKey = u64;
16
17#[inline]
18pub(crate) fn displace(f1: u32, f2: u32, d1: u32, d2: u32) -> u32 {
19    d2.wrapping_add(f1.wrapping_mul(d1)).wrapping_add(f2)
20}
21
22#[inline]
23pub(crate) fn hash<T>(buf: &Buf, value: &T, key: &HashKey) -> Result<Hashes, Error>
24where
25    T: ?Sized + Visit,
26    T::Target: Hash,
27{
28    let mut hasher = SipHasher13::new_with_keys(0, *key);
29    value.visit(buf, |value| value.hash(&mut hasher))?;
30
31    let Hash128 { h1, h2 } = hasher.finish128();
32
33    Ok(Hashes {
34        g: (h1 >> 32) as usize,
35        f1: h1 as u32,
36        f2: h2 as u32,
37    })
38}
39
40#[inline]
41pub(crate) fn get_index(
42    &Hashes { g, f1, f2 }: &Hashes,
43    displacements: &[Entry<u32, u32>],
44    len: usize,
45) -> Result<usize, Error> {
46    let index = g % displacements.len();
47
48    let Some(&Entry { key: d1, value: d2 }) = displacements.get(index) else {
49        return Err(Error::new(ErrorKind::IndexOutOfBounds {
50            index,
51            len: displacements.len(),
52        }));
53    };
54
55    Ok(displace(f1, f2, d1, d2) as usize % len)
56}
57
58#[inline]
59pub(crate) fn get_custom_index<'a, D>(
60    &Hashes { g, f1, f2 }: &Hashes,
61    get: D,
62    displacements_len: usize,
63    len: usize,
64) -> Result<usize, Error>
65where
66    D: FnOnce(usize) -> Result<Option<&'a Entry<u32, u32>>, Error>,
67{
68    let index = g % displacements_len;
69
70    let Some(&Entry { key: d1, value: d2 }) = get(index)? else {
71        return Err(Error::new(ErrorKind::IndexOutOfBounds {
72            index,
73            len: displacements_len,
74        }));
75    };
76
77    Ok(displace(f1, f2, d1, d2) as usize % len)
78}
musli_zerocopy/phf/hashing.rs

musli_zerocopy/phf/
hashing.rs
