Line data    Source code

       1              : //! A fast hasher for the maps of the core, which are keyed by short names and small ids.
       2              : //!
       3              : //! The default SipHash of the standard library resists collision attacks that do not matter here
       4              : //! and dominated the lookups of the analyzer. This is the FxHash of rustc.
       5              : 
       6              : use std::hash::{BuildHasherDefault, Hasher};
       7              : 
       8              : /// The FxHash hasher
       9              : #[derive(Clone, Copy, Default)]
      10              : pub struct FxHasher {
      11              :     /// The hash state
      12              :     hash: u64,
      13              : }
      14              : 
      15              : const SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95;
      16              : 
      17              : impl FxHasher {
      18              :     #[inline]
      19       235136 :     fn add(&mut self, word: u64) {
      20       235136 :         self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(SEED);
      21       235136 :     }
      22              : }
      23              : 
      24              : impl Hasher for FxHasher {
      25              :     #[inline]
      26        77423 :     fn write(&mut self, bytes: &[u8]) {
      27        77423 :         let mut chunks = bytes.chunks_exact(8);
      28        77423 :         for chunk in &mut chunks {
      29        15580 :             self.add(u64::from_le_bytes(chunk.try_into().unwrap()));
      30        15580 :         }
      31        77423 :         let rest = chunks.remainder();
      32        77423 :         if !rest.is_empty() {
      33        46793 :             let mut word = [0u8; 8];
      34        46793 :             word[..rest.len()].copy_from_slice(rest);
      35        46793 :             self.add(u64::from_le_bytes(word));
      36        47464 :         }
      37        77423 :     }
      38              :     #[inline]
      39        78266 :     fn write_u8(&mut self, i: u8) {
      40        78266 :         self.add(i as u64);
      41        78266 :     }
      42              :     #[inline]
      43           12 :     fn write_u16(&mut self, i: u16) {
      44           12 :         self.add(i as u64);
      45           12 :     }
      46              :     #[inline]
      47        88686 :     fn write_u32(&mut self, i: u32) {
      48        88686 :         self.add(i as u64);
      49        88686 :     }
      50              :     #[inline]
      51          849 :     fn write_u64(&mut self, i: u64) {
      52          849 :         self.add(i);
      53          849 :     }
      54              :     #[inline]
      55         4950 :     fn write_usize(&mut self, i: usize) {
      56         4950 :         self.add(i as u64);
      57         4950 :     }
      58              :     #[inline]
      59        95911 :     fn finish(&self) -> u64 {
      60        95911 :         self.hash
      61        95911 :     }
      62              : }
      63              : 
      64              : /// A hash map with FxHash
      65              : pub type HashMap<K, V> = std::collections::HashMap<K, V, BuildHasherDefault<FxHasher>>;
      66              : /// A hash set with FxHash
      67              : pub type HashSet<K> = std::collections::HashSet<K, BuildHasherDefault<FxHasher>>;