From 36d22d82aa202bb199967e9512281e9a53db42c9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 21:33:14 +0200 Subject: Adding upstream version 115.7.0esr. Signed-off-by: Daniel Baumann --- .../rust/unicode-normalization/src/perfect_hash.rs | 50 ++++++++++++++++++++++ 1 file changed, 50 insertions(+) create mode 100644 third_party/rust/unicode-normalization/src/perfect_hash.rs (limited to 'third_party/rust/unicode-normalization/src/perfect_hash.rs') 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 or the MIT license +// , 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( + 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 + } +} -- cgit v1.2.3