1 files changed, 78 insertions, 17 deletions

diff --git a/compiler/rustc_data_structures/src/sharded.rs b/compiler/rustc_data_structures/src/sharded.rs
index 3016348f224..49cafcb17a0 100644
--- a/compiler/rustc_data_structures/src/sharded.rs
+++ b/compiler/rustc_data_structures/src/sharded.rs
@@ -1,11 +1,11 @@
 use std::borrow::Borrow;
-use std::collections::hash_map::RawEntryMut;
 use std::hash::{Hash, Hasher};
-use std::iter;
+use std::{iter, mem};
 
 use either::Either;
+use hashbrown::hash_table::{Entry, HashTable};
 
-use crate::fx::{FxHashMap, FxHasher};
+use crate::fx::FxHasher;
 use crate::sync::{CacheAligned, Lock, LockGuard, Mode, is_dyn_thread_safe};
 
 // 32 shards is sufficient to reduce contention on an 8-core Ryzen 7 1700,
@@ -140,17 +140,67 @@ pub fn shards() -> usize {
     1
 }
 
-pub type ShardedHashMap<K, V> = Sharded<FxHashMap<K, V>>;
+pub type ShardedHashMap<K, V> = Sharded<HashTable<(K, V)>>;
 
 impl<K: Eq, V> ShardedHashMap<K, V> {
     pub fn with_capacity(cap: usize) -> Self {
-        Self::new(|| FxHashMap::with_capacity_and_hasher(cap, rustc_hash::FxBuildHasher::default()))
+        Self::new(|| HashTable::with_capacity(cap))
     }
     pub fn len(&self) -> usize {
         self.lock_shards().map(|shard| shard.len()).sum()
     }
 }
 
+impl<K: Eq + Hash, V> ShardedHashMap<K, V> {
+    #[inline]
+    pub fn get<Q>(&self, key: &Q) -> Option<V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq,
+        V: Clone,
+    {
+        let hash = make_hash(key);
+        let shard = self.lock_shard_by_hash(hash);
+        let (_, value) = shard.find(hash, |(k, _)| k.borrow() == key)?;
+        Some(value.clone())
+    }
+
+    #[inline]
+    pub fn get_or_insert_with(&self, key: K, default: impl FnOnce() -> V) -> V
+    where
+        V: Copy,
+    {
+        let hash = make_hash(&key);
+        let mut shard = self.lock_shard_by_hash(hash);
+
+        match table_entry(&mut shard, hash, &key) {
+            Entry::Occupied(e) => e.get().1,
+            Entry::Vacant(e) => {
+                let value = default();
+                e.insert((key, value));
+                value
+            }
+        }
+    }
+
+    #[inline]
+    pub fn insert(&self, key: K, value: V) -> Option<V> {
+        let hash = make_hash(&key);
+        let mut shard = self.lock_shard_by_hash(hash);
+
+        match table_entry(&mut shard, hash, &key) {
+            Entry::Occupied(e) => {
+                let previous = mem::replace(&mut e.into_mut().1, value);
+                Some(previous)
+            }
+            Entry::Vacant(e) => {
+                e.insert((key, value));
+                None
+            }
+        }
+    }
+}
+
 impl<K: Eq + Hash + Copy> ShardedHashMap<K, ()> {
     #[inline]
     pub fn intern_ref<Q: ?Sized>(&self, value: &Q, make: impl FnOnce() -> K) -> K
@@ -160,13 +210,12 @@ impl<K: Eq + Hash + Copy> ShardedHashMap<K, ()> {
     {
         let hash = make_hash(value);
         let mut shard = self.lock_shard_by_hash(hash);
-        let entry = shard.raw_entry_mut().from_key_hashed_nocheck(hash, value);
 
-        match entry {
-            RawEntryMut::Occupied(e) => *e.key(),
-            RawEntryMut::Vacant(e) => {
+        match table_entry(&mut shard, hash, value) {
+            Entry::Occupied(e) => e.get().0,
+            Entry::Vacant(e) => {
                 let v = make();
-                e.insert_hashed_nocheck(hash, v, ());
+                e.insert((v, ()));
                 v
             }
         }
@@ -180,13 +229,12 @@ impl<K: Eq + Hash + Copy> ShardedHashMap<K, ()> {
     {
         let hash = make_hash(&value);
         let mut shard = self.lock_shard_by_hash(hash);
-        let entry = shard.raw_entry_mut().from_key_hashed_nocheck(hash, &value);
 
-        match entry {
-            RawEntryMut::Occupied(e) => *e.key(),
-            RawEntryMut::Vacant(e) => {
+        match table_entry(&mut shard, hash, &value) {
+            Entry::Occupied(e) => e.get().0,
+            Entry::Vacant(e) => {
                 let v = make(value);
-                e.insert_hashed_nocheck(hash, v, ());
+                e.insert((v, ()));
                 v
             }
         }
@@ -203,17 +251,30 @@ impl<K: Eq + Hash + Copy + IntoPointer> ShardedHashMap<K, ()> {
         let hash = make_hash(&value);
         let shard = self.lock_shard_by_hash(hash);
         let value = value.into_pointer();
-        shard.raw_entry().from_hash(hash, |entry| entry.into_pointer() == value).is_some()
+        shard.find(hash, |(k, ())| k.into_pointer() == value).is_some()
     }
 }
 
 #[inline]
-pub fn make_hash<K: Hash + ?Sized>(val: &K) -> u64 {
+fn make_hash<K: Hash + ?Sized>(val: &K) -> u64 {
     let mut state = FxHasher::default();
     val.hash(&mut state);
     state.finish()
 }
 
+#[inline]
+fn table_entry<'a, K, V, Q>(
+    table: &'a mut HashTable<(K, V)>,
+    hash: u64,
+    key: &Q,
+) -> Entry<'a, (K, V)>
+where
+    K: Hash + Borrow<Q>,
+    Q: ?Sized + Eq,
+{
+    table.entry(hash, move |(k, _)| k.borrow() == key, |(k, _)| make_hash(k))
+}
+
 /// Get a shard with a pre-computed hash value. If `get_shard_by_value` is
 /// ever used in combination with `get_shard_by_hash` on a single `Sharded`
 /// instance, then `hash` must be computed with `FxHasher`. Otherwise,