Coverage Report

Created: 2025-08-29 06:50

/src/unicode-normalization/src/perfect_hash.rs
Line
Count
Source
1
// Copyright 2019 The Rust Project Developers. See the COPYRIGHT
2
// file at the top-level directory of this distribution and at
3
// http://rust-lang.org/COPYRIGHT.
4
//
5
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8
// option. This file may not be copied, modified, or distributed
9
// except according to those terms.
10
11
//! Support for lookups based on minimal perfect hashing.
12
13
// This function is based on multiplication being fast and is "good enough". Also
14
// it can share some work between the unsalted and salted versions.
15
#[inline]
16
2.93G
fn my_hash(key: u32, salt: u32, n: usize) -> usize {
17
2.93G
    let y = key.wrapping_add(salt).wrapping_mul(2654435769);
18
2.93G
    let y = y ^ key.wrapping_mul(0x31415926);
19
2.93G
    (((y as u64) * (n as u64)) >> 32) as usize
20
2.93G
}
21
22
/// Do a lookup using minimal perfect hashing.
23
///
24
/// The table is stored as a sequence of "salt" values, then a sequence of
25
/// values that contain packed key/value pairs. The strategy is to hash twice.
26
/// The first hash retrieves a salt value that makes the second hash unique.
27
/// The hash function doesn't have to be very good, just good enough that the
28
/// resulting map is unique.
29
#[inline]
30
1.46G
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
1.46G
    x: u32,
32
1.46G
    salt: &[u16],
33
1.46G
    kv: &[KV],
34
1.46G
    fk: FK,
35
1.46G
    fv: FV,
36
1.46G
    default: V,
37
1.46G
) -> V
38
1.46G
where
39
1.46G
    KV: Copy,
40
1.46G
    FK: Fn(KV) -> u32,
41
1.46G
    FV: Fn(KV) -> V,
42
1.46G
{
43
1.46G
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
1.46G
    let key_val = kv[my_hash(x, s, salt.len())];
45
1.46G
    if x == fk(key_val) {
46
772M
        fv(key_val)
47
    } else {
48
693M
        default
49
    }
50
1.46G
}
unicode_normalization::perfect_hash::mph_lookup::<(u32, (u16, u16)), core::option::Option<(u16, u16)>, unicode_normalization::lookups::pair_lookup_fk<(u16, u16)>, unicode_normalization::lookups::pair_lookup_fv_opt<(u16, u16)>>
Line
Count
Source
30
505M
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
505M
    x: u32,
32
505M
    salt: &[u16],
33
505M
    kv: &[KV],
34
505M
    fk: FK,
35
505M
    fv: FV,
36
505M
    default: V,
37
505M
) -> V
38
505M
where
39
505M
    KV: Copy,
40
505M
    FK: Fn(KV) -> u32,
41
505M
    FV: Fn(KV) -> V,
42
505M
{
43
505M
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
505M
    let key_val = kv[my_hash(x, s, salt.len())];
45
505M
    if x == fk(key_val) {
46
96.9M
        fv(key_val)
47
    } else {
48
408M
        default
49
    }
50
505M
}
unicode_normalization::perfect_hash::mph_lookup::<(u32, char), core::option::Option<char>, unicode_normalization::lookups::pair_lookup_fk<char>, unicode_normalization::lookups::pair_lookup_fv_opt<char>>
Line
Count
Source
30
64.6M
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
64.6M
    x: u32,
32
64.6M
    salt: &[u16],
33
64.6M
    kv: &[KV],
34
64.6M
    fk: FK,
35
64.6M
    fv: FV,
36
64.6M
    default: V,
37
64.6M
) -> V
38
64.6M
where
39
64.6M
    KV: Copy,
40
64.6M
    FK: Fn(KV) -> u32,
41
64.6M
    FV: Fn(KV) -> V,
42
64.6M
{
43
64.6M
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
64.6M
    let key_val = kv[my_hash(x, s, salt.len())];
45
64.6M
    if x == fk(key_val) {
46
3.80M
        fv(key_val)
47
    } else {
48
60.8M
        default
49
    }
50
64.6M
}
unicode_normalization::perfect_hash::mph_lookup::<u32, bool, unicode_normalization::lookups::bool_lookup_fk, unicode_normalization::lookups::bool_lookup_fv>
Line
Count
Source
30
47
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
47
    x: u32,
32
47
    salt: &[u16],
33
47
    kv: &[KV],
34
47
    fk: FK,
35
47
    fv: FV,
36
47
    default: V,
37
47
) -> V
38
47
where
39
47
    KV: Copy,
40
47
    FK: Fn(KV) -> u32,
41
47
    FV: Fn(KV) -> V,
42
47
{
43
47
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
47
    let key_val = kv[my_hash(x, s, salt.len())];
45
47
    if x == fk(key_val) {
46
1
        fv(key_val)
47
    } else {
48
46
        default
49
    }
50
47
}
unicode_normalization::perfect_hash::mph_lookup::<u32, u8, unicode_normalization::lookups::u8_lookup_fk, unicode_normalization::lookups::u8_lookup_fv>
Line
Count
Source
30
896M
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
896M
    x: u32,
32
896M
    salt: &[u16],
33
896M
    kv: &[KV],
34
896M
    fk: FK,
35
896M
    fv: FV,
36
896M
    default: V,
37
896M
) -> V
38
896M
where
39
896M
    KV: Copy,
40
896M
    FK: Fn(KV) -> u32,
41
896M
    FV: Fn(KV) -> V,
42
896M
{
43
896M
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
896M
    let key_val = kv[my_hash(x, s, salt.len())];
45
896M
    if x == fk(key_val) {
46
672M
        fv(key_val)
47
    } else {
48
224M
        default
49
    }
50
896M
}