// Copyright 2019 The Rust Project Developers. See the COPYRIGHT

// file at the top-level directory of this distribution and at

// http://rust-lang.org/COPYRIGHT.

//

// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or

// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license

// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your

// option. This file may not be copied, modified, or distributed

// except according to those terms.

//! Support for lookups based on minimal perfect hashing.

// This function is based on multiplication being fast and is "good enough". Also

// it can share some work between the unsalted and salted versions.

#[inline]

fn my_hash(key: u32, salt: u32, n: usize) -> usize {

    let y = key.wrapping_add(salt).wrapping_mul(2654435769);

    let y = y ^ key.wrapping_mul(0x31415926);

    (((y as u64) * (n as u64)) >> 32) as usize

}

/// Do a lookup using minimal perfect hashing.

///

/// The table is stored as a sequence of "salt" values, then a sequence of

/// values that contain packed key/value pairs. The strategy is to hash twice.

/// The first hash retrieves a salt value that makes the second hash unique.

/// The hash function doesn't have to be very good, just good enough that the

/// resulting map is unique.

#[inline]

pub(crate) fn mph_lookup<KV, V, FK, FV>(

    x: u32,

    salt: &[u16],

    kv: &[KV],

    fk: FK,

    fv: FV,

    default: V,

) -> V

where

    KV: Copy,

    FK: Fn(KV) -> u32,

    FV: Fn(KV) -> V,

{

    let s = salt[my_hash(x, 0, salt.len())] as u32;

    let key_val = kv[my_hash(x, s, salt.len())];

    if x == fk(key_val) {

        fv(key_val)

    } else {

        default

    }

}

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

497M

pub(crate) fn mph_lookup<KV, V, FK, FV>(

31

497M

    x: u32,

32

497M

    salt: &[u16],

33

497M

    kv: &[KV],

34

497M

    fk: FK,

35

497M

    fv: FV,

36

497M

    default: V,

37

497M

) -> V

38

497M

where

39

497M

    KV: Copy,

40

497M

    FK: Fn(KV) -> u32,

41

497M

    FV: Fn(KV) -> V,

42

{

43

497M

    let s = salt[my_hash(x, 0, salt.len())] as u32;

44

497M

    let key_val = kv[my_hash(x, s, salt.len())];

45

497M

    if x == fk(key_val) {

46

99.4M

        fv(key_val)

47

    } else {

48

398M

        default

49

    }

50

497M

}

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

121M

pub(crate) fn mph_lookup<KV, V, FK, FV>(

31

121M

    x: u32,

32

121M

    salt: &[u16],

33

121M

    kv: &[KV],

34

121M

    fk: FK,

35

121M

    fv: FV,

36

121M

    default: V,

37

121M

) -> V

38

121M

where

39

121M

    KV: Copy,

40

121M

    FK: Fn(KV) -> u32,

41

121M

    FV: Fn(KV) -> V,

42

{

43

121M

    let s = salt[my_hash(x, 0, salt.len())] as u32;

44

121M

    let key_val = kv[my_hash(x, s, salt.len())];

45

121M

    if x == fk(key_val) {

46

7.85M

        fv(key_val)

47

    } else {

48

113M

        default

49

    }

50

121M

}

unicode_normalization::perfect_hash::mph_lookup::<u32, bool, unicode_normalization::lookups::bool_lookup_fk, unicode_normalization::lookups::bool_lookup_fv>

Line

Count

Source

30

52

pub(crate) fn mph_lookup<KV, V, FK, FV>(

31

52

    x: u32,

32

52

    salt: &[u16],

33

52

    kv: &[KV],

34

52

    fk: FK,

35

52

    fv: FV,

36

52

    default: V,

37

52

) -> V

38

52

where

39

52

    KV: Copy,

40

52

    FK: Fn(KV) -> u32,

41

52

    FV: Fn(KV) -> V,

42

{

43

52

    let s = salt[my_hash(x, 0, salt.len())] as u32;

44

52

    let key_val = kv[my_hash(x, s, salt.len())];

45

52

    if x == fk(key_val) {

46

0

        fv(key_val)

47

    } else {

48

52

        default

49

    }

50

52

}

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.00G

pub(crate) fn mph_lookup<KV, V, FK, FV>(

31

1.00G

    x: u32,

32

1.00G

    salt: &[u16],

33

1.00G

    kv: &[KV],

34

1.00G

    fk: FK,

35

1.00G

    fv: FV,

36

1.00G

    default: V,

37

1.00G

) -> V

38

1.00G

where

39

1.00G

    KV: Copy,

40

1.00G

    FK: Fn(KV) -> u32,

41

1.00G

    FV: Fn(KV) -> V,

42

{

43

1.00G

    let s = salt[my_hash(x, 0, salt.len())] as u32;

44

1.00G

    let key_val = kv[my_hash(x, s, salt.len())];

45

1.00G

    if x == fk(key_val) {

46

619M

        fv(key_val)

47

    } else {

48

387M

        default

49

    }

50

1.00G

}