diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
commit | 36d22d82aa202bb199967e9512281e9a53db42c9 (patch) | |
tree | 105e8c98ddea1c1e4784a60a5a6410fa416be2de /third_party/rust/unicode-normalization/src/perfect_hash.rs | |
parent | Initial commit. (diff) | |
download | firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.tar.xz firefox-esr-36d22d82aa202bb199967e9512281e9a53db42c9.zip |
Adding upstream version 115.7.0esr.upstream/115.7.0esr
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/unicode-normalization/src/perfect_hash.rs')
-rw-r--r-- | third_party/rust/unicode-normalization/src/perfect_hash.rs | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/third_party/rust/unicode-normalization/src/perfect_hash.rs b/third_party/rust/unicode-normalization/src/perfect_hash.rs new file mode 100644 index 0000000000..3dbc166396 --- /dev/null +++ b/third_party/rust/unicode-normalization/src/perfect_hash.rs @@ -0,0 +1,50 @@ +// 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 + } +} |