1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

use core::hash::Hash;

use crate::buf::{Buf, Visit};
use crate::error::{Error, ErrorKind};
use crate::phf::Entry;
use crate::sip::{Hash128, Hasher128, SipHasher13};

#[non_exhaustive]
pub(crate) struct Hashes {
    pub(crate) g: usize,
    pub(crate) f1: u32,
    pub(crate) f2: u32,
}

pub(crate) type HashKey = u64;

#[inline]
pub(crate) fn displace(f1: u32, f2: u32, d1: u32, d2: u32) -> u32 {
    d2.wrapping_add(f1.wrapping_mul(d1)).wrapping_add(f2)
}

#[inline]
pub(crate) fn hash<T>(buf: &Buf, value: &T, key: &HashKey) -> Result<Hashes, Error>
where
    T: ?Sized + Visit,
    T::Target: Hash,
{
    let mut hasher = SipHasher13::new_with_keys(0, *key);
    value.visit(buf, |value| value.hash(&mut hasher))?;

    let Hash128 { h1, h2 } = hasher.finish128();

    Ok(Hashes {
        g: (h1 >> 32) as usize,
        f1: h1 as u32,
        f2: h2 as u32,
    })
}

#[inline]
pub(crate) fn get_index(
    &Hashes { g, f1, f2 }: &Hashes,
    displacements: &[Entry<u32, u32>],
    len: usize,
) -> Result<usize, Error> {
    let index = g % displacements.len();

    let Some(&Entry { key: d1, value: d2 }) = displacements.get(index) else {
        return Err(Error::new(ErrorKind::IndexOutOfBounds {
            index,
            len: displacements.len(),
        }));
    };

    Ok(displace(f1, f2, d1, d2) as usize % len)
}

#[inline]
pub(crate) fn get_custom_index<'a, D>(
    &Hashes { g, f1, f2 }: &Hashes,
    get: D,
    displacements_len: usize,
    len: usize,
) -> Result<usize, Error>
where
    D: FnOnce(usize) -> Result<Option<&'a Entry<u32, u32>>, Error>,
{
    let index = g % displacements_len;

    let Some(&Entry { key: d1, value: d2 }) = get(index)? else {
        return Err(Error::new(ErrorKind::IndexOutOfBounds {
            index,
            len: displacements_len,
        }));
    };

    Ok(displace(f1, f2, d1, d2) as usize % len)
}