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       260870 :     fn add(&mut self, word: u64) {
      20       260870 :         self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(SEED);
      21       260870 :     }
      22              : }
      23              : 
      24              : impl Hasher for FxHasher {
      25              :     #[inline]
      26        82202 :     fn write(&mut self, bytes: &[u8]) {
      27        82202 :         let mut chunks = bytes.chunks_exact(8);
      28        82202 :         for chunk in &mut chunks {
      29        20589 :             self.add(u64::from_le_bytes(chunk.try_into().unwrap()));
      30        20589 :         }
      31        82202 :         let rest = chunks.remainder();
      32        82202 :         if !rest.is_empty() {
      33        53759 :             let mut word = [0u8; 8];
      34        53759 :             word[..rest.len()].copy_from_slice(rest);
      35        53759 :             self.add(u64::from_le_bytes(word));
      36        54137 :         }
      37        82202 :     }
      38              :     #[inline]
      39        83096 :     fn write_u8(&mut self, i: u8) {
      40        83096 :         self.add(i as u64);
      41        83096 :     }
      42              :     #[inline]
      43           12 :     fn write_u16(&mut self, i: u16) {
      44           12 :         self.add(i as u64);
      45           12 :     }
      46              :     #[inline]
      47        97445 :     fn write_u32(&mut self, i: u32) {
      48        97445 :         self.add(i as u64);
      49        97445 :     }
      50              :     #[inline]
      51          900 :     fn write_u64(&mut self, i: u64) {
      52          900 :         self.add(i);
      53          900 :     }
      54              :     #[inline]
      55         5069 :     fn write_usize(&mut self, i: usize) {
      56         5069 :         self.add(i as u64);
      57         5069 :     }
      58              :     #[inline]
      59       109218 :     fn finish(&self) -> u64 {
      60       109218 :         self.hash
      61       109218 :     }
      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>>;