Coverage Report

Created: 2026-10-28 06:19

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/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
4.84G
fn my_hash(key: u32, salt: u32, n: usize) -> usize {
17
4.84G
    let y = key.wrapping_add(salt).wrapping_mul(2654435769);
18
4.84G
    let y = y ^ key.wrapping_mul(0x31415926);
19
4.84G
    (((y as u64) * (n as u64)) >> 32) as usize
20
4.84G
}
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
2.42G
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
2.42G
    x: u32,
32
2.42G
    salt: &[u16],
33
2.42G
    kv: &[KV],
34
2.42G
    fk: FK,
35
2.42G
    fv: FV,
36
2.42G
    default: V,
37
2.42G
) -> V
38
2.42G
where
39
2.42G
    KV: Copy,
40
2.42G
    FK: Fn(KV) -> u32,
41
2.42G
    FV: Fn(KV) -> V,
42
{
43
2.42G
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
2.42G
    let key_val = kv[my_hash(x, s, salt.len())];
45
2.42G
    if x == fk(key_val) {
46
1.16G
        fv(key_val)
47
    } else {
48
1.26G
        default
49
    }
50
2.42G
}
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
833M
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
833M
    x: u32,
32
833M
    salt: &[u16],
33
833M
    kv: &[KV],
34
833M
    fk: FK,
35
833M
    fv: FV,
36
833M
    default: V,
37
833M
) -> V
38
833M
where
39
833M
    KV: Copy,
40
833M
    FK: Fn(KV) -> u32,
41
833M
    FV: Fn(KV) -> V,
42
{
43
833M
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
833M
    let key_val = kv[my_hash(x, s, salt.len())];
45
833M
    if x == fk(key_val) {
46
142M
        fv(key_val)
47
    } else {
48
691M
        default
49
    }
50
833M
}
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
127M
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
127M
    x: u32,
32
127M
    salt: &[u16],
33
127M
    kv: &[KV],
34
127M
    fk: FK,
35
127M
    fv: FV,
36
127M
    default: V,
37
127M
) -> V
38
127M
where
39
127M
    KV: Copy,
40
127M
    FK: Fn(KV) -> u32,
41
127M
    FV: Fn(KV) -> V,
42
{
43
127M
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
127M
    let key_val = kv[my_hash(x, s, salt.len())];
45
127M
    if x == fk(key_val) {
46
7.23M
        fv(key_val)
47
    } else {
48
120M
        default
49
    }
50
127M
}
unicode_normalization::perfect_hash::mph_lookup::<u32, bool, unicode_normalization::lookups::bool_lookup_fk, unicode_normalization::lookups::bool_lookup_fv>
Line
Count
Source
30
44
pub(crate) fn mph_lookup<KV, V, FK, FV>(
31
44
    x: u32,
32
44
    salt: &[u16],
33
44
    kv: &[KV],
34
44
    fk: FK,
35
44
    fv: FV,
36
44
    default: V,
37
44
) -> V
38
44
where
39
44
    KV: Copy,
40
44
    FK: Fn(KV) -> u32,
41
44
    FV: Fn(KV) -> V,
42
{
43
44
    let s = salt[my_hash(x, 0, salt.len())] as u32;
44
44
    let key_val = kv[my_hash(x, s, salt.len())];
45
44
    if x == fk(key_val) {
46
0
        fv(key_val)
47
    } else {
48
44
        default
49
    }
50
44
}
unicode_normalization::perfect_hash::mph_lookup::<u32, u8, unicode_normalization::lookups::u8_lookup_fk, unicode_normalization::lookups::u8_lookup_fv>
Line
Count
Source
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
{
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
1.01G
        fv(key_val)
47
    } else {
48
449M
        default
49
    }
50
1.46G
}