osom_lib_hash_tables/bytell/
hash_to_index.rs

1//! Contains strategies for converting hash values to indices in the bytell hash table.
2
3use osom_lib_macros::debug_check_or_release_hint;
4use osom_lib_primitives::power_of_two::PowerOfTwo32;
5use osom_lib_reprc::macros::reprc;
6
7/// This trait represents a strategy for converting hash values to indices in the bytell hash table.
8pub trait HashToIndex: Default + Clone {
9    /// Converts a hash value to an index in the bytell hash table.
10    fn hash_to_index(&self, hash_value: u64, table_capacity: PowerOfTwo32) -> usize;
11
12    /// Updates the hash-to-index policy when the table changes its capacity.
13    fn update_for_new_table_capacity(&mut self, table_capacity: PowerOfTwo32);
14}
15
16/// Represents the Fibonacci variant of hash-to-index policy.
17#[derive(Default, Clone, Copy)]
18#[reprc]
19#[repr(transparent)]
20pub struct FibonacciHashToIndex {
21    shift: u8,
22}
23
24impl HashToIndex for FibonacciHashToIndex {
25    #[inline]
26    fn hash_to_index(&self, hash_value: u64, table_capacity: PowerOfTwo32) -> usize {
27        let value = table_capacity.value();
28        debug_check_or_release_hint!(value.is_power_of_two(), "table_size not a power of two");
29        let shift = self.shift;
30        let mut result = hash_value;
31        result ^= result >> shift;
32        result = result.wrapping_mul(11400714819323198485) >> shift;
33        debug_check_or_release_hint!(result < u64::from(u32::MAX), "hash_to_index beyond u32::MAX");
34
35        #[allow(clippy::cast_possible_truncation)]
36        {
37            result as usize
38        }
39    }
40
41    fn update_for_new_table_capacity(&mut self, table_capacity: PowerOfTwo32) {
42        #[allow(clippy::cast_possible_truncation)]
43        {
44            self.shift = (64 - table_capacity.value().trailing_zeros()) as u8;
45        }
46    }
47}
48
49/// Represents the power of two variant of hash-to-index policy. This basically
50/// just does modulo operation.
51#[derive(Default, Clone, Copy)]
52#[reprc]
53#[repr(transparent)]
54pub struct PowerOfTwoHashToIndex;
55
56impl HashToIndex for PowerOfTwoHashToIndex {
57    #[inline(always)]
58    fn hash_to_index(&self, hash_value: u64, table_capacity: PowerOfTwo32) -> usize {
59        #[allow(clippy::cast_possible_truncation)]
60        let hash_value = hash_value as u32;
61        (hash_value & (table_capacity.value() - 1)) as usize
62    }
63
64    #[inline(always)]
65    fn update_for_new_table_capacity(&mut self, _: PowerOfTwo32) {}
66}
osom_lib_hash_tables/bytell/hash_to_index.rs

osom_lib_hash_tables/bytell/
hash_to_index.rs
