diff options
Diffstat (limited to 'compiler/rustc_data_structures/src')
8 files changed, 86 insertions, 24 deletions
diff --git a/compiler/rustc_data_structures/src/graph/tests.rs b/compiler/rustc_data_structures/src/graph/tests.rs index b69b9dbc4a8..e48b9686c26 100644 --- a/compiler/rustc_data_structures/src/graph/tests.rs +++ b/compiler/rustc_data_structures/src/graph/tests.rs @@ -3,7 +3,7 @@ use std::cmp::max; use super::*; use crate::fx::FxHashMap; -pub struct TestGraph { +pub(super) struct TestGraph { num_nodes: usize, start_node: usize, successors: FxHashMap<usize, Vec<usize>>, @@ -11,7 +11,7 @@ pub struct TestGraph { } impl TestGraph { - pub fn new(start_node: usize, edges: &[(usize, usize)]) -> Self { + pub(super) fn new(start_node: usize, edges: &[(usize, usize)]) -> Self { let mut graph = TestGraph { num_nodes: start_node + 1, start_node, diff --git a/compiler/rustc_data_structures/src/lib.rs b/compiler/rustc_data_structures/src/lib.rs index a3b62b46919..865424fd6bb 100644 --- a/compiler/rustc_data_structures/src/lib.rs +++ b/compiler/rustc_data_structures/src/lib.rs @@ -24,7 +24,6 @@ #![feature(dropck_eyepatch)] #![feature(extend_one)] #![feature(file_buffered)] -#![feature(hash_raw_entry)] #![feature(macro_metavar_expr)] #![feature(map_try_insert)] #![feature(min_specialization)] diff --git a/compiler/rustc_data_structures/src/marker.rs b/compiler/rustc_data_structures/src/marker.rs index 4cacc269709..64c64bfa3c2 100644 --- a/compiler/rustc_data_structures/src/marker.rs +++ b/compiler/rustc_data_structures/src/marker.rs @@ -76,6 +76,7 @@ impl_dyn_send!( [crate::sync::RwLock<T> where T: DynSend] [crate::tagged_ptr::TaggedRef<'a, P, T> where 'a, P: Sync, T: Send + crate::tagged_ptr::Tag] [rustc_arena::TypedArena<T> where T: DynSend] + [hashbrown::HashTable<T> where T: DynSend] [indexmap::IndexSet<V, S> where V: DynSend, S: DynSend] [indexmap::IndexMap<K, V, S> where K: DynSend, V: DynSend, S: DynSend] [thin_vec::ThinVec<T> where T: DynSend] @@ -153,6 +154,7 @@ impl_dyn_sync!( [crate::tagged_ptr::TaggedRef<'a, P, T> where 'a, P: Sync, T: Sync + crate::tagged_ptr::Tag] [parking_lot::lock_api::Mutex<R, T> where R: DynSync, T: ?Sized + DynSend] [parking_lot::lock_api::RwLock<R, T> where R: DynSync, T: ?Sized + DynSend + DynSync] + [hashbrown::HashTable<T> where T: DynSync] [indexmap::IndexSet<V, S> where V: DynSync, S: DynSync] [indexmap::IndexMap<K, V, S> where K: DynSync, V: DynSync, S: DynSync] [smallvec::SmallVec<A> where A: smallvec::Array + DynSync] diff --git a/compiler/rustc_data_structures/src/obligation_forest/mod.rs b/compiler/rustc_data_structures/src/obligation_forest/mod.rs index ea3ac467340..f63b201742d 100644 --- a/compiler/rustc_data_structures/src/obligation_forest/mod.rs +++ b/compiler/rustc_data_structures/src/obligation_forest/mod.rs @@ -313,7 +313,7 @@ pub struct Error<O, E> { mod helper { use super::*; - pub type ObligationTreeIdGenerator = impl Iterator<Item = ObligationTreeId>; + pub(super) type ObligationTreeIdGenerator = impl Iterator<Item = ObligationTreeId>; impl<O: ForestObligation> ObligationForest<O> { #[cfg_attr(not(bootstrap), define_opaque(ObligationTreeIdGenerator))] pub fn new() -> ObligationForest<O> { 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, diff --git a/compiler/rustc_data_structures/src/sync.rs b/compiler/rustc_data_structures/src/sync.rs index a1cc75c4985..616a18a72ab 100644 --- a/compiler/rustc_data_structures/src/sync.rs +++ b/compiler/rustc_data_structures/src/sync.rs @@ -88,7 +88,7 @@ mod mode { // Whether thread safety might be enabled. #[inline] - pub fn might_be_dyn_thread_safe() -> bool { + pub(super) fn might_be_dyn_thread_safe() -> bool { DYN_THREAD_SAFE_MODE.load(Ordering::Relaxed) != DYN_NOT_THREAD_SAFE } diff --git a/compiler/rustc_data_structures/src/sync/parallel.rs b/compiler/rustc_data_structures/src/sync/parallel.rs index 1ba631b8623..8ef8a3f3585 100644 --- a/compiler/rustc_data_structures/src/sync/parallel.rs +++ b/compiler/rustc_data_structures/src/sync/parallel.rs @@ -46,7 +46,7 @@ pub fn parallel_guard<R>(f: impl FnOnce(&ParallelGuard) -> R) -> R { ret } -pub fn serial_join<A, B, RA, RB>(oper_a: A, oper_b: B) -> (RA, RB) +fn serial_join<A, B, RA, RB>(oper_a: A, oper_b: B) -> (RA, RB) where A: FnOnce() -> RA, B: FnOnce() -> RB, diff --git a/compiler/rustc_data_structures/src/tagged_ptr/tests.rs b/compiler/rustc_data_structures/src/tagged_ptr/tests.rs index 9c1e4cefa69..85b21a7c8ec 100644 --- a/compiler/rustc_data_structures/src/tagged_ptr/tests.rs +++ b/compiler/rustc_data_structures/src/tagged_ptr/tests.rs @@ -7,7 +7,7 @@ use crate::stable_hasher::{HashStable, StableHasher}; /// A tag type used in [`TaggedRef`] tests. #[derive(Copy, Clone, Debug, PartialEq, Eq)] -pub enum Tag2 { +enum Tag2 { B00 = 0b00, B01 = 0b01, B10 = 0b10, |