diff options
Diffstat (limited to 'third_party/rust/dashmap/src')
| -rw-r--r-- | third_party/rust/dashmap/src/iter.rs | 309 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/iter_set.rs | 71 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/lib.rs | 993 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/lock.rs | 557 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/mapref/entry.rs | 198 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/mapref/mod.rs | 3 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/mapref/multiple.rs | 120 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/mapref/one.rs | 114 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/rayon/map.rs | 221 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/rayon/set.rs | 121 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/read_only.rs | 243 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/serde.rs | 148 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/set.rs | 458 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/setref/mod.rs | 2 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/setref/multiple.rs | 25 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/setref/one.rs | 29 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/t.rs | 95 | ||||
| -rw-r--r-- | third_party/rust/dashmap/src/util.rs | 102 |
18 files changed, 3809 insertions, 0 deletions
diff --git a/third_party/rust/dashmap/src/iter.rs b/third_party/rust/dashmap/src/iter.rs new file mode 100644 index 0000000000..e88c1cae1d --- /dev/null +++ b/third_party/rust/dashmap/src/iter.rs @@ -0,0 +1,309 @@ +use super::mapref::multiple::{RefMulti, RefMutMulti}; +use super::util; +use crate::lock::{RwLockReadGuard, RwLockWriteGuard}; +use crate::t::Map; +use crate::util::SharedValue; +use crate::{DashMap, HashMap}; +use core::hash::{BuildHasher, Hash}; +use core::mem; +use std::collections::hash_map; +use std::collections::hash_map::RandomState; +use std::sync::Arc; + +/// Iterator over a DashMap yielding key value pairs. +/// +/// # Examples +/// +/// ``` +/// use dashmap::DashMap; +/// +/// let map = DashMap::new(); +/// map.insert("hello", "world"); +/// map.insert("alex", "steve"); +/// let pairs: Vec<(&'static str, &'static str)> = map.into_iter().collect(); +/// assert_eq!(pairs.len(), 2); +/// ``` +pub struct OwningIter<K, V, S = RandomState> { + map: DashMap<K, V, S>, + shard_i: usize, + current: Option<GuardOwningIter<K, V>>, +} + +impl<K: Eq + Hash, V, S: BuildHasher + Clone> OwningIter<K, V, S> { + pub(crate) fn new(map: DashMap<K, V, S>) -> Self { + Self { + map, + shard_i: 0, + current: None, + } + } +} + +type GuardOwningIter<K, V> = hash_map::IntoIter<K, SharedValue<V>>; + +impl<K: Eq + Hash, V, S: BuildHasher + Clone> Iterator for OwningIter<K, V, S> { + type Item = (K, V); + + fn next(&mut self) -> Option<Self::Item> { + loop { + if let Some(current) = self.current.as_mut() { + if let Some((k, v)) = current.next() { + return Some((k, v.into_inner())); + } + } + + if self.shard_i == self.map._shard_count() { + return None; + } + + //let guard = unsafe { self.map._yield_read_shard(self.shard_i) }; + let mut shard_wl = unsafe { self.map._yield_write_shard(self.shard_i) }; + + let hasher = self.map._hasher(); + + let map = mem::replace(&mut *shard_wl, HashMap::with_hasher(hasher)); + + drop(shard_wl); + + let iter = map.into_iter(); + + //unsafe { ptr::write(&mut self.current, Some((arcee, iter))); } + self.current = Some(iter); + + self.shard_i += 1; + } + } +} + +unsafe impl<K, V, S> Send for OwningIter<K, V, S> +where + K: Eq + Hash + Send, + V: Send, + S: BuildHasher + Clone + Send, +{ +} + +unsafe impl<K, V, S> Sync for OwningIter<K, V, S> +where + K: Eq + Hash + Sync, + V: Sync, + S: BuildHasher + Clone + Sync, +{ +} + +type GuardIter<'a, K, V, S> = ( + Arc<RwLockReadGuard<'a, HashMap<K, V, S>>>, + hash_map::Iter<'a, K, SharedValue<V>>, +); + +type GuardIterMut<'a, K, V, S> = ( + Arc<RwLockWriteGuard<'a, HashMap<K, V, S>>>, + hash_map::IterMut<'a, K, SharedValue<V>>, +); + +/// Iterator over a DashMap yielding immutable references. +/// +/// # Examples +/// +/// ``` +/// use dashmap::DashMap; +/// +/// let map = DashMap::new(); +/// map.insert("hello", "world"); +/// assert_eq!(map.iter().count(), 1); +/// ``` +pub struct Iter<'a, K, V, S = RandomState, M = DashMap<K, V, S>> { + map: &'a M, + shard_i: usize, + current: Option<GuardIter<'a, K, V, S>>, +} + +unsafe impl<'a, 'i, K, V, S, M> Send for Iter<'i, K, V, S, M> +where + K: 'a + Eq + Hash + Send, + V: 'a + Send, + S: 'a + BuildHasher + Clone, + M: Map<'a, K, V, S>, +{ +} + +unsafe impl<'a, 'i, K, V, S, M> Sync for Iter<'i, K, V, S, M> +where + K: 'a + Eq + Hash + Sync, + V: 'a + Sync, + S: 'a + BuildHasher + Clone, + M: Map<'a, K, V, S>, +{ +} + +impl<'a, K: Eq + Hash, V, S: 'a + BuildHasher + Clone, M: Map<'a, K, V, S>> Iter<'a, K, V, S, M> { + pub(crate) fn new(map: &'a M) -> Self { + Self { + map, + shard_i: 0, + current: None, + } + } +} + +impl<'a, K: Eq + Hash, V, S: 'a + BuildHasher + Clone, M: Map<'a, K, V, S>> Iterator + for Iter<'a, K, V, S, M> +{ + type Item = RefMulti<'a, K, V, S>; + + fn next(&mut self) -> Option<Self::Item> { + loop { + if let Some(current) = self.current.as_mut() { + if let Some((k, v)) = current.1.next() { + let guard = current.0.clone(); + + return Some(RefMulti::new(guard, k, v.get())); + } + } + + if self.shard_i == self.map._shard_count() { + return None; + } + + let guard = unsafe { self.map._yield_read_shard(self.shard_i) }; + + let sref: &HashMap<K, V, S> = unsafe { util::change_lifetime_const(&*guard) }; + + let iter = sref.iter(); + + self.current = Some((Arc::new(guard), iter)); + + self.shard_i += 1; + } + } +} + +/// Iterator over a DashMap yielding mutable references. +/// +/// # Examples +/// +/// ``` +/// use dashmap::DashMap; +/// +/// let map = DashMap::new(); +/// map.insert("Johnny", 21); +/// map.iter_mut().for_each(|mut r| *r += 1); +/// assert_eq!(*map.get("Johnny").unwrap(), 22); +/// ``` +pub struct IterMut<'a, K, V, S = RandomState, M = DashMap<K, V, S>> { + map: &'a M, + shard_i: usize, + current: Option<GuardIterMut<'a, K, V, S>>, +} + +unsafe impl<'a, 'i, K, V, S, M> Send for IterMut<'i, K, V, S, M> +where + K: 'a + Eq + Hash + Send, + V: 'a + Send, + S: 'a + BuildHasher + Clone, + M: Map<'a, K, V, S>, +{ +} + +unsafe impl<'a, 'i, K, V, S, M> Sync for IterMut<'i, K, V, S, M> +where + K: 'a + Eq + Hash + Sync, + V: 'a + Sync, + S: 'a + BuildHasher + Clone, + M: Map<'a, K, V, S>, +{ +} + +impl<'a, K: Eq + Hash, V, S: 'a + BuildHasher + Clone, M: Map<'a, K, V, S>> + IterMut<'a, K, V, S, M> +{ + pub(crate) fn new(map: &'a M) -> Self { + Self { + map, + shard_i: 0, + current: None, + } + } +} + +impl<'a, K: Eq + Hash, V, S: 'a + BuildHasher + Clone, M: Map<'a, K, V, S>> Iterator + for IterMut<'a, K, V, S, M> +{ + type Item = RefMutMulti<'a, K, V, S>; + + fn next(&mut self) -> Option<Self::Item> { + loop { + if let Some(current) = self.current.as_mut() { + if let Some((k, v)) = current.1.next() { + let guard = current.0.clone(); + + unsafe { + let k = util::change_lifetime_const(k); + + let v = &mut *v.as_ptr(); + + return Some(RefMutMulti::new(guard, k, v)); + } + } + } + + if self.shard_i == self.map._shard_count() { + return None; + } + + let mut guard = unsafe { self.map._yield_write_shard(self.shard_i) }; + + let sref: &mut HashMap<K, V, S> = unsafe { util::change_lifetime_mut(&mut *guard) }; + + let iter = sref.iter_mut(); + + self.current = Some((Arc::new(guard), iter)); + + self.shard_i += 1; + } + } +} + +#[cfg(test)] +mod tests { + use crate::DashMap; + + #[test] + fn iter_mut_manual_count() { + let map = DashMap::new(); + + map.insert("Johnny", 21); + + assert_eq!(map.len(), 1); + + let mut c = 0; + + for shard in map.shards() { + c += shard.write().iter_mut().count(); + } + + assert_eq!(c, 1); + } + + #[test] + fn iter_mut_count() { + let map = DashMap::new(); + + map.insert("Johnny", 21); + + assert_eq!(map.len(), 1); + + assert_eq!(map.iter_mut().count(), 1); + } + + #[test] + fn iter_count() { + let map = DashMap::new(); + + map.insert("Johnny", 21); + + assert_eq!(map.len(), 1); + + assert_eq!(map.iter().count(), 1); + } +} diff --git a/third_party/rust/dashmap/src/iter_set.rs b/third_party/rust/dashmap/src/iter_set.rs new file mode 100644 index 0000000000..619a5b500e --- /dev/null +++ b/third_party/rust/dashmap/src/iter_set.rs @@ -0,0 +1,71 @@ +use crate::setref::multiple::RefMulti; +use crate::t::Map; +use core::hash::{BuildHasher, Hash}; + +pub struct OwningIter<K, S> { + inner: crate::iter::OwningIter<K, (), S>, +} + +impl<K: Eq + Hash, S: BuildHasher + Clone> OwningIter<K, S> { + pub(crate) fn new(inner: crate::iter::OwningIter<K, (), S>) -> Self { + Self { inner } + } +} + +impl<K: Eq + Hash, S: BuildHasher + Clone> Iterator for OwningIter<K, S> { + type Item = K; + + fn next(&mut self) -> Option<Self::Item> { + self.inner.next().map(|(k, _)| k) + } +} + +unsafe impl<K, S> Send for OwningIter<K, S> +where + K: Eq + Hash + Send, + S: BuildHasher + Clone + Send, +{ +} + +unsafe impl<K, S> Sync for OwningIter<K, S> +where + K: Eq + Hash + Sync, + S: BuildHasher + Clone + Sync, +{ +} + +pub struct Iter<'a, K, S, M> { + inner: crate::iter::Iter<'a, K, (), S, M>, +} + +unsafe impl<'a, 'i, K, S, M> Send for Iter<'i, K, S, M> +where + K: 'a + Eq + Hash + Send, + S: 'a + BuildHasher + Clone, + M: Map<'a, K, (), S>, +{ +} + +unsafe impl<'a, 'i, K, S, M> Sync for Iter<'i, K, S, M> +where + K: 'a + Eq + Hash + Sync, + S: 'a + BuildHasher + Clone, + M: Map<'a, K, (), S>, +{ +} + +impl<'a, K: Eq + Hash, S: 'a + BuildHasher + Clone, M: Map<'a, K, (), S>> Iter<'a, K, S, M> { + pub(crate) fn new(inner: crate::iter::Iter<'a, K, (), S, M>) -> Self { + Self { inner } + } +} + +impl<'a, K: Eq + Hash, S: 'a + BuildHasher + Clone, M: Map<'a, K, (), S>> Iterator + for Iter<'a, K, S, M> +{ + type Item = RefMulti<'a, K, S>; + + fn next(&mut self) -> Option<Self::Item> { + self.inner.next().map(RefMulti::new) + } +} diff --git a/third_party/rust/dashmap/src/lib.rs b/third_party/rust/dashmap/src/lib.rs new file mode 100644 index 0000000000..3507ece5f2 --- /dev/null +++ b/third_party/rust/dashmap/src/lib.rs @@ -0,0 +1,993 @@ +#![allow(clippy::type_complexity)] + +pub mod iter; +pub mod iter_set; +pub mod lock; +pub mod mapref; +mod read_only; +#[cfg(feature = "serde")] +mod serde; +mod set; +pub mod setref; +mod t; +mod util; + +#[cfg(feature = "rayon")] +pub mod rayon { + pub mod map; + pub mod set; +} + +use cfg_if::cfg_if; +use core::borrow::Borrow; +use core::fmt; +use core::hash::{BuildHasher, Hash, Hasher}; +use core::iter::FromIterator; +use core::ops::{BitAnd, BitOr, Shl, Shr, Sub}; +use iter::{Iter, IterMut, OwningIter}; +use lock::{RwLock, RwLockReadGuard, RwLockWriteGuard}; +use mapref::entry::{Entry, OccupiedEntry, VacantEntry}; +use mapref::multiple::RefMulti; +use mapref::one::{Ref, RefMut}; +pub use read_only::ReadOnlyView; +pub use set::DashSet; +use std::collections::hash_map::RandomState; +pub use t::Map; + +cfg_if! { + if #[cfg(feature = "raw-api")] { + pub use util::SharedValue; + } else { + use util::SharedValue; + } +} + +pub(crate) type HashMap<K, V, S> = std::collections::HashMap<K, SharedValue<V>, S>; + +fn shard_amount() -> usize { + (num_cpus::get() * 4).next_power_of_two() +} + +fn ncb(shard_amount: usize) -> usize { + shard_amount.trailing_zeros() as usize +} + +/// DashMap is an implementation of a concurrent associative array/hashmap in Rust. +/// +/// DashMap tries to implement an easy to use API similar to `std::collections::HashMap` +/// with some slight changes to handle concurrency. +/// +/// DashMap tries to be very simple to use and to be a direct replacement for `RwLock<HashMap<K, V, S>>`. +/// To accomplish these all methods take `&self` instead modifying methods taking `&mut self`. +/// This allows you to put a DashMap in an `Arc<T>` and share it between threads while being able to modify it. +/// +/// Documentation mentioning locking behaviour acts in the reference frame of the calling thread. +/// This means that it is safe to ignore it across multiple threads. +pub struct DashMap<K, V, S = RandomState> { + shift: usize, + shards: Box<[RwLock<HashMap<K, V, S>>]>, + hasher: S, +} + +impl<K: Eq + Hash + Clone, V: Clone, S: Clone> Clone for DashMap<K, V, S> { + fn clone(&self) -> Self { + let mut inner_shards = Vec::new(); + + for shard in self.shards.iter() { + let shard = shard.read(); + + inner_shards.push(RwLock::new((*shard).clone())); + } + + Self { + shift: self.shift, + shards: inner_shards.into_boxed_slice(), + hasher: self.hasher.clone(), + } + } +} + +impl<K, V, S> Default for DashMap<K, V, S> +where + K: Eq + Hash, + S: Default + BuildHasher + Clone, +{ + fn default() -> Self { + Self::with_hasher(Default::default()) + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a> DashMap<K, V, RandomState> { + /// Creates a new DashMap with a capacity of 0. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let reviews = DashMap::new(); + /// reviews.insert("Veloren", "What a fantastic game!"); + /// ``` + pub fn new() -> Self { + DashMap::with_hasher(RandomState::default()) + } + + /// Creates a new DashMap with a specified starting capacity. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let mappings = DashMap::with_capacity(2); + /// mappings.insert(2, 4); + /// mappings.insert(8, 16); + /// ``` + pub fn with_capacity(capacity: usize) -> Self { + DashMap::with_capacity_and_hasher(capacity, RandomState::default()) + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone> DashMap<K, V, S> { + /// Wraps this `DashMap` into a read-only view. This view allows to obtain raw references to the stored values. + pub fn into_read_only(self) -> ReadOnlyView<K, V, S> { + ReadOnlyView::new(self) + } + + /// Creates a new DashMap with a capacity of 0 and the provided hasher. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let reviews = DashMap::with_hasher(s); + /// reviews.insert("Veloren", "What a fantastic game!"); + /// ``` + pub fn with_hasher(hasher: S) -> Self { + Self::with_capacity_and_hasher(0, hasher) + } + + /// Creates a new DashMap with a specified starting capacity and hasher. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let mappings = DashMap::with_capacity_and_hasher(2, s); + /// mappings.insert(2, 4); + /// mappings.insert(8, 16); + /// ``` + pub fn with_capacity_and_hasher(mut capacity: usize, hasher: S) -> Self { + let shard_amount = shard_amount(); + let shift = util::ptr_size_bits() - ncb(shard_amount); + + if capacity != 0 { + capacity = (capacity + (shard_amount - 1)) & !(shard_amount - 1); + } + + let cps = capacity / shard_amount; + + let shards = (0..shard_amount) + .map(|_| RwLock::new(HashMap::with_capacity_and_hasher(cps, hasher.clone()))) + .collect(); + + Self { + shift, + shards, + hasher, + } + } + + /// Hash a given item to produce a usize. + /// Uses the provided or default HashBuilder. + pub fn hash_usize<T: Hash>(&self, item: &T) -> usize { + let mut hasher = self.hasher.build_hasher(); + + item.hash(&mut hasher); + + hasher.finish() as usize + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Allows you to peek at the inner shards that store your data. + /// You should probably not use this unless you know what you are doing. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let map = DashMap::<(), ()>::new(); + /// println!("Amount of shards: {}", map.shards().len()); + /// ``` + pub fn shards(&self) -> &[RwLock<HashMap<K, V, S>>] { + &self.shards + } + } else { + #[allow(dead_code)] + pub(crate) fn shards(&self) -> &[RwLock<HashMap<K, V, S>>] { + &self.shards + } + } + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Finds which shard a certain key is stored in. + /// You should probably not use this unless you know what you are doing. + /// Note that shard selection is dependent on the default or provided HashBuilder. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let map = DashMap::new(); + /// map.insert("coca-cola", 1.4); + /// println!("coca-cola is stored in shard: {}", map.determine_map("coca-cola")); + /// ``` + pub fn determine_map<Q>(&self, key: &Q) -> usize + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.hash_usize(&key); + self.determine_shard(hash) + } + } + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Finds which shard a certain hash is stored in. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let map: DashMap<i32, i32> = DashMap::new(); + /// let key = "key"; + /// let hash = map.hash_usize(&key); + /// println!("hash is stored in shard: {}", map.determine_shard(hash)); + /// ``` + pub fn determine_shard(&self, hash: usize) -> usize { + // Leave the high 7 bits for the HashBrown SIMD tag. + (hash << 7) >> self.shift + } + } else { + + pub(crate) fn determine_shard(&self, hash: usize) -> usize { + // Leave the high 7 bits for the HashBrown SIMD tag. + (hash << 7) >> self.shift + } + } + } + + /// Returns a reference to the map's [`BuildHasher`]. + /// + /// # Examples + /// + /// ```rust + /// use dashmap::DashMap; + /// use std::collections::hash_map::RandomState; + /// + /// let hasher = RandomState::new(); + /// let map: DashMap<i32, i32> = DashMap::new(); + /// let hasher: &RandomState = map.hasher(); + /// ``` + /// + /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html + pub fn hasher(&self) -> &S { + &self.hasher + } + + /// Inserts a key and a value into the map. Returns the old value associated with the key if there was one. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let map = DashMap::new(); + /// map.insert("I am the key!", "And I am the value!"); + /// ``` + pub fn insert(&self, key: K, value: V) -> Option<V> { + self._insert(key, value) + } + + /// Removes an entry from the map, returning the key and value if they existed in the map. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let soccer_team = DashMap::new(); + /// soccer_team.insert("Jack", "Goalie"); + /// assert_eq!(soccer_team.remove("Jack").unwrap().1, "Goalie"); + /// ``` + pub fn remove<Q>(&self, key: &Q) -> Option<(K, V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._remove(key) + } + + /// Removes an entry from the map, returning the key and value + /// if the entry existed and the provided conditional function returned true. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let soccer_team = DashMap::new(); + /// soccer_team.insert("Sam", "Forward"); + /// soccer_team.remove_if("Sam", |_, position| position == &"Goalie"); + /// assert!(soccer_team.contains_key("Sam")); + /// ``` + /// ``` + /// use dashmap::DashMap; + /// + /// let soccer_team = DashMap::new(); + /// soccer_team.insert("Sam", "Forward"); + /// soccer_team.remove_if("Sam", |_, position| position == &"Forward"); + /// assert!(!soccer_team.contains_key("Sam")); + /// ``` + pub fn remove_if<Q>(&self, key: &Q, f: impl FnOnce(&K, &V) -> bool) -> Option<(K, V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._remove_if(key, f) + } + + /// Creates an iterator over a DashMap yielding immutable references. + /// + /// **Locking behaviour:** May deadlock if called when holding a mutable reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let words = DashMap::new(); + /// words.insert("hello", "world"); + /// assert_eq!(words.iter().count(), 1); + /// ``` + pub fn iter(&'a self) -> Iter<'a, K, V, S, DashMap<K, V, S>> { + self._iter() + } + + /// Iterator over a DashMap yielding mutable references. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let map = DashMap::new(); + /// map.insert("Johnny", 21); + /// map.iter_mut().for_each(|mut r| *r += 1); + /// assert_eq!(*map.get("Johnny").unwrap(), 22); + /// ``` + pub fn iter_mut(&'a self) -> IterMut<'a, K, V, S, DashMap<K, V, S>> { + self._iter_mut() + } + + /// Get a immutable reference to an entry in the map + /// + /// **Locking behaviour:** May deadlock if called when holding a mutable reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let youtubers = DashMap::new(); + /// youtubers.insert("Bosnian Bill", 457000); + /// assert_eq!(*youtubers.get("Bosnian Bill").unwrap(), 457000); + /// ``` + pub fn get<Q>(&'a self, key: &Q) -> Option<Ref<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._get(key) + } + + /// Get a mutable reference to an entry in the map + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let class = DashMap::new(); + /// class.insert("Albin", 15); + /// *class.get_mut("Albin").unwrap() -= 1; + /// assert_eq!(*class.get("Albin").unwrap(), 14); + /// ``` + pub fn get_mut<Q>(&'a self, key: &Q) -> Option<RefMut<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._get_mut(key) + } + + /// Remove excess capacity to reduce memory usage. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + pub fn shrink_to_fit(&self) { + self._shrink_to_fit(); + } + + /// Retain elements that whose predicates return true + /// and discard elements whose predicates return false. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let people = DashMap::new(); + /// people.insert("Albin", 15); + /// people.insert("Jones", 22); + /// people.insert("Charlie", 27); + /// people.retain(|_, v| *v > 20); + /// assert_eq!(people.len(), 2); + /// ``` + pub fn retain(&self, f: impl FnMut(&K, &mut V) -> bool) { + self._retain(f); + } + + /// Fetches the total number of key-value pairs stored in the map. + /// + /// **Locking behaviour:** May deadlock if called when holding a mutable reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let people = DashMap::new(); + /// people.insert("Albin", 15); + /// people.insert("Jones", 22); + /// people.insert("Charlie", 27); + /// assert_eq!(people.len(), 3); + /// ``` + pub fn len(&self) -> usize { + self._len() + } + + /// Checks if the map is empty or not. + /// + /// **Locking behaviour:** May deadlock if called when holding a mutable reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let map = DashMap::<(), ()>::new(); + /// assert!(map.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self._is_empty() + } + + /// Removes all key-value pairs in the map. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let stats = DashMap::new(); + /// stats.insert("Goals", 4); + /// assert!(!stats.is_empty()); + /// stats.clear(); + /// assert!(stats.is_empty()); + /// ``` + pub fn clear(&self) { + self._clear(); + } + + /// Returns how many key-value pairs the map can store without reallocating. + /// + /// **Locking behaviour:** May deadlock if called when holding a mutable reference into the map. + pub fn capacity(&self) -> usize { + self._capacity() + } + + /// Modify a specific value according to a function. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let stats = DashMap::new(); + /// stats.insert("Goals", 4); + /// stats.alter("Goals", |_, v| v * 2); + /// assert_eq!(*stats.get("Goals").unwrap(), 8); + /// ``` + /// + /// # Panics + /// + /// If the given closure panics, then `alter` will abort the process + pub fn alter<Q>(&self, key: &Q, f: impl FnOnce(&K, V) -> V) + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._alter(key, f); + } + + /// Modify every value in the map according to a function. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let stats = DashMap::new(); + /// stats.insert("Wins", 4); + /// stats.insert("Losses", 2); + /// stats.alter_all(|_, v| v + 1); + /// assert_eq!(*stats.get("Wins").unwrap(), 5); + /// assert_eq!(*stats.get("Losses").unwrap(), 3); + /// ``` + /// + /// # Panics + /// + /// If the given closure panics, then `alter_all` will abort the process + pub fn alter_all(&self, f: impl FnMut(&K, V) -> V) { + self._alter_all(f); + } + + /// Checks if the map contains a specific key. + /// + /// **Locking behaviour:** May deadlock if called when holding a mutable reference into the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let team_sizes = DashMap::new(); + /// team_sizes.insert("Dakota Cherries", 23); + /// assert!(team_sizes.contains_key("Dakota Cherries")); + /// ``` + pub fn contains_key<Q>(&self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._contains_key(key) + } + + /// Advanced entry API that tries to mimic `std::collections::HashMap`. + /// See the documentation on `dashmap::mapref::entry` for more details. + /// + /// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map. + pub fn entry(&'a self, key: K) -> Entry<'a, K, V, S> { + self._entry(key) + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher + Clone> Map<'a, K, V, S> + for DashMap<K, V, S> +{ + fn _shard_count(&self) -> usize { + self.shards.len() + } + + unsafe fn _get_read_shard(&'a self, i: usize) -> &'a HashMap<K, V, S> { + debug_assert!(i < self.shards.len()); + + self.shards.get_unchecked(i).get() + } + + unsafe fn _yield_read_shard(&'a self, i: usize) -> RwLockReadGuard<'a, HashMap<K, V, S>> { + debug_assert!(i < self.shards.len()); + + self.shards.get_unchecked(i).read() + } + + unsafe fn _yield_write_shard(&'a self, i: usize) -> RwLockWriteGuard<'a, HashMap<K, V, S>> { + debug_assert!(i < self.shards.len()); + + self.shards.get_unchecked(i).write() + } + + fn _insert(&self, key: K, value: V) -> Option<V> { + let hash = self.hash_usize(&key); + + let idx = self.determine_shard(hash); + + let mut shard = unsafe { self._yield_write_shard(idx) }; + + shard + .insert(key, SharedValue::new(value)) + .map(|v| v.into_inner()) + } + + fn _remove<Q>(&self, key: &Q) -> Option<(K, V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.hash_usize(&key); + + let idx = self.determine_shard(hash); + + let mut shard = unsafe { self._yield_write_shard(idx) }; + + shard.remove_entry(key).map(|(k, v)| (k, v.into_inner())) + } + + fn _remove_if<Q>(&self, key: &Q, f: impl FnOnce(&K, &V) -> bool) -> Option<(K, V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.hash_usize(&key); + + let idx = self.determine_shard(hash); + + let mut shard = unsafe { self._yield_write_shard(idx) }; + + if let Some((k, v)) = shard.get_key_value(key) { + if f(k, v.get()) { + shard.remove_entry(key).map(|(k, v)| (k, v.into_inner())) + } else { + None + } + } else { + None + } + } + + fn _iter(&'a self) -> Iter<'a, K, V, S, DashMap<K, V, S>> { + Iter::new(self) + } + + fn _iter_mut(&'a self) -> IterMut<'a, K, V, S, DashMap<K, V, S>> { + IterMut::new(self) + } + + fn _get<Q>(&'a self, key: &Q) -> Option<Ref<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.hash_usize(&key); + + let idx = self.determine_shard(hash); + + let shard = unsafe { self._yield_read_shard(idx) }; + + if let Some((kptr, vptr)) = shard.get_key_value(key) { + unsafe { + let kptr = util::change_lifetime_const(kptr); + + let vptr = util::change_lifetime_const(vptr); + + Some(Ref::new(shard, kptr, vptr.get())) + } + } else { + None + } + } + + fn _get_mut<Q>(&'a self, key: &Q) -> Option<RefMut<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.hash_usize(&key); + + let idx = self.determine_shard(hash); + + let shard = unsafe { self._yield_write_shard(idx) }; + + if let Some((kptr, vptr)) = shard.get_key_value(key) { + unsafe { + let kptr = util::change_lifetime_const(kptr); + + let vptr = &mut *vptr.as_ptr(); + + Some(RefMut::new(shard, kptr, vptr)) + } + } else { + None + } + } + + fn _shrink_to_fit(&self) { + self.shards.iter().for_each(|s| s.write().shrink_to_fit()); + } + + fn _retain(&self, mut f: impl FnMut(&K, &mut V) -> bool) { + self.shards + .iter() + .for_each(|s| s.write().retain(|k, v| f(k, v.get_mut()))); + } + + fn _len(&self) -> usize { + self.shards.iter().map(|s| s.read().len()).sum() + } + + fn _capacity(&self) -> usize { + self.shards.iter().map(|s| s.read().capacity()).sum() + } + + fn _alter<Q>(&self, key: &Q, f: impl FnOnce(&K, V) -> V) + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + if let Some(mut r) = self.get_mut(key) { + util::map_in_place_2(r.pair_mut(), f); + } + } + + fn _alter_all(&self, mut f: impl FnMut(&K, V) -> V) { + self.shards.iter().for_each(|s| { + s.write() + .iter_mut() + .for_each(|(k, v)| util::map_in_place_2((k, v.get_mut()), &mut f)); + }); + } + + fn _entry(&'a self, key: K) -> Entry<'a, K, V, S> { + let hash = self.hash_usize(&key); + + let idx = self.determine_shard(hash); + + let shard = unsafe { self._yield_write_shard(idx) }; + + if let Some((kptr, vptr)) = shard.get_key_value(&key) { + unsafe { + let kptr = util::change_lifetime_const(kptr); + + let vptr = &mut *vptr.as_ptr(); + + Entry::Occupied(OccupiedEntry::new(shard, key, (kptr, vptr))) + } + } else { + Entry::Vacant(VacantEntry::new(shard, key)) + } + } + + fn _hasher(&self) -> S { + self.hasher.clone() + } +} + +impl<K: Eq + Hash + fmt::Debug, V: fmt::Debug, S: BuildHasher + Clone> fmt::Debug + for DashMap<K, V, S> +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let mut pmap = f.debug_map(); + + for r in self { + let (k, v) = r.pair(); + + pmap.entry(k, v); + } + + pmap.finish() + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone> Shl<(K, V)> for &'a DashMap<K, V, S> { + type Output = Option<V>; + + fn shl(self, pair: (K, V)) -> Self::Output { + self.insert(pair.0, pair.1) + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone, Q> Shr<&Q> for &'a DashMap<K, V, S> +where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, +{ + type Output = Ref<'a, K, V, S>; + + fn shr(self, key: &Q) -> Self::Output { + self.get(key).unwrap() + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone, Q> BitOr<&Q> for &'a DashMap<K, V, S> +where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, +{ + type Output = RefMut<'a, K, V, S>; + + fn bitor(self, key: &Q) -> Self::Output { + self.get_mut(key).unwrap() + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone, Q> Sub<&Q> for &'a DashMap<K, V, S> +where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, +{ + type Output = Option<(K, V)>; + + fn sub(self, key: &Q) -> Self::Output { + self.remove(key) + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone, Q> BitAnd<&Q> for &'a DashMap<K, V, S> +where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, +{ + type Output = bool; + + fn bitand(self, key: &Q) -> Self::Output { + self.contains_key(key) + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher + Clone> IntoIterator for DashMap<K, V, S> { + type Item = (K, V); + + type IntoIter = OwningIter<K, V, S>; + + fn into_iter(self) -> Self::IntoIter { + OwningIter::new(self) + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher + Clone> IntoIterator for &'a DashMap<K, V, S> { + type Item = RefMulti<'a, K, V, S>; + + type IntoIter = Iter<'a, K, V, S, DashMap<K, V, S>>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<K: Eq + Hash, V, S: BuildHasher + Clone> Extend<(K, V)> for DashMap<K, V, S> { + fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, intoiter: I) { + for pair in intoiter.into_iter() { + self.insert(pair.0, pair.1); + } + } +} + +impl<K: Eq + Hash, V> FromIterator<(K, V)> for DashMap<K, V, RandomState> { + fn from_iter<I: IntoIterator<Item = (K, V)>>(intoiter: I) -> Self { + let mut map = DashMap::new(); + + map.extend(intoiter); + + map + } +} + +#[cfg(test)] +mod tests { + use crate::DashMap; + use std::collections::hash_map::RandomState; + + #[test] + fn test_basic() { + let dm = DashMap::new(); + + dm.insert(0, 0); + + assert_eq!(dm.get(&0).unwrap().value(), &0); + } + + #[test] + fn test_default() { + let dm: DashMap<u32, u32> = DashMap::default(); + + dm.insert(0, 0); + + assert_eq!(dm.get(&0).unwrap().value(), &0); + } + + #[test] + fn test_multiple_hashes() { + let dm: DashMap<u32, u32> = DashMap::default(); + + for i in 0..100 { + dm.insert(0, i); + + dm.insert(i, i); + } + + for i in 1..100 { + let r = dm.get(&i).unwrap(); + + assert_eq!(i, *r.value()); + + assert_eq!(i, *r.key()); + } + + let r = dm.get(&0).unwrap(); + + assert_eq!(99, *r.value()); + } + + #[test] + fn test_more_complex_values() { + #[derive(Hash, PartialEq, Debug, Clone)] + + struct T0 { + s: String, + u: u8, + } + + let dm = DashMap::new(); + + let range = 0..10; + + for i in range { + let t = T0 { + s: i.to_string(), + u: i as u8, + }; + + dm.insert(i, t.clone()); + + assert_eq!(&t, dm.get(&i).unwrap().value()); + } + } + + #[test] + fn test_different_hashers_randomstate() { + let dm_hm_default: DashMap<u32, u32, RandomState> = + DashMap::with_hasher(RandomState::new()); + + for i in 0..10 { + dm_hm_default.insert(i, i); + + assert_eq!(i, *dm_hm_default.get(&i).unwrap().value()); + } + } +} diff --git a/third_party/rust/dashmap/src/lock.rs b/third_party/rust/dashmap/src/lock.rs new file mode 100644 index 0000000000..d27b413185 --- /dev/null +++ b/third_party/rust/dashmap/src/lock.rs @@ -0,0 +1,557 @@ +use core::cell::UnsafeCell; +use core::default::Default; +use core::fmt; +use core::marker::PhantomData; +use core::mem; +use core::ops::{Deref, DerefMut}; +use core::ptr::NonNull; +use core::sync::atomic::{spin_loop_hint as cpu_relax, AtomicUsize, Ordering}; + +pub struct RwLock<T: ?Sized> { + lock: AtomicUsize, + data: UnsafeCell<T>, +} + +const READER: usize = 1 << 2; + +const UPGRADED: usize = 1 << 1; + +const WRITER: usize = 1; + +#[derive(Debug)] +pub struct RwLockReadGuard<'a, T: 'a + ?Sized> { + lock: &'a AtomicUsize, + data: NonNull<T>, +} + +unsafe impl<'a, T: Send> Send for RwLockReadGuard<'a, T> {} + +unsafe impl<'a, T: Sync> Sync for RwLockReadGuard<'a, T> {} + +#[derive(Debug)] +pub struct RwLockWriteGuard<'a, T: 'a + ?Sized> { + lock: &'a AtomicUsize, + data: NonNull<T>, + #[doc(hidden)] + _invariant: PhantomData<&'a mut T>, +} + +unsafe impl<'a, T: Send> Send for RwLockWriteGuard<'a, T> {} + +unsafe impl<'a, T: Sync> Sync for RwLockWriteGuard<'a, T> {} + +#[derive(Debug)] +pub struct RwLockUpgradeableGuard<'a, T: 'a + ?Sized> { + lock: &'a AtomicUsize, + data: NonNull<T>, + #[doc(hidden)] + _invariant: PhantomData<&'a mut T>, +} + +unsafe impl<T: ?Sized + Send> Send for RwLock<T> {} + +unsafe impl<T: ?Sized + Send + Sync> Sync for RwLock<T> {} + +impl<T> RwLock<T> { + pub const fn new(user_data: T) -> RwLock<T> { + RwLock { + lock: AtomicUsize::new(0), + data: UnsafeCell::new(user_data), + } + } + + pub fn into_inner(self) -> T { + let RwLock { data, .. } = self; + + data.into_inner() + } +} + +impl<T: ?Sized> RwLock<T> { + pub fn read(&self) -> RwLockReadGuard<T> { + loop { + match self.try_read() { + Some(guard) => return guard, + None => cpu_relax(), + } + } + } + + pub fn try_read(&self) -> Option<RwLockReadGuard<T>> { + let value = self.lock.fetch_add(READER, Ordering::Acquire); + + // We check the UPGRADED bit here so that new readers are prevented when an UPGRADED lock is held. + // This helps reduce writer starvation. + if value & (WRITER | UPGRADED) != 0 { + // Lock is taken, undo. + self.lock.fetch_sub(READER, Ordering::Release); + + None + } else { + Some(RwLockReadGuard { + lock: &self.lock, + data: unsafe { NonNull::new_unchecked(self.data.get()) }, + }) + } + } + + /// # Safety + /// + /// This is only safe if the lock is currently locked in read mode and the number of readers is not 0. + pub unsafe fn force_read_decrement(&self) { + debug_assert!(self.lock.load(Ordering::Relaxed) & !WRITER > 0); + + self.lock.fetch_sub(READER, Ordering::Release); + } + + /// # Safety + /// + /// The lock must be locked in write mode. + pub unsafe fn force_write_unlock(&self) { + debug_assert_eq!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED), 0); + + self.lock.fetch_and(!(WRITER | UPGRADED), Ordering::Release); + } + + fn try_write_internal(&self, strong: bool) -> Option<RwLockWriteGuard<T>> { + if compare_exchange( + &self.lock, + 0, + WRITER, + Ordering::Acquire, + Ordering::Relaxed, + strong, + ) + .is_ok() + { + Some(RwLockWriteGuard { + lock: &self.lock, + data: unsafe { NonNull::new_unchecked(self.data.get()) }, + _invariant: PhantomData, + }) + } else { + None + } + } + + pub fn write(&self) -> RwLockWriteGuard<T> { + loop { + match self.try_write_internal(false) { + Some(guard) => return guard, + None => cpu_relax(), + } + } + } + + pub fn try_write(&self) -> Option<RwLockWriteGuard<T>> { + self.try_write_internal(true) + } + + pub fn upgradeable_read(&self) -> RwLockUpgradeableGuard<T> { + loop { + match self.try_upgradeable_read() { + Some(guard) => return guard, + None => cpu_relax(), + } + } + } + + pub fn try_upgradeable_read(&self) -> Option<RwLockUpgradeableGuard<T>> { + if self.lock.fetch_or(UPGRADED, Ordering::Acquire) & (WRITER | UPGRADED) == 0 { + Some(RwLockUpgradeableGuard { + lock: &self.lock, + data: unsafe { NonNull::new_unchecked(self.data.get()) }, + _invariant: PhantomData, + }) + } else { + None + } + } + + /// # Safety + /// Write locks may not be used in combination with this method. + pub unsafe fn get(&self) -> &T { + &*self.data.get() + } + + pub fn get_mut(&mut self) -> &mut T { + unsafe { &mut *self.data.get() } + } +} + +impl<T: ?Sized + fmt::Debug> fmt::Debug for RwLock<T> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match self.try_read() { + Some(guard) => write!(f, "RwLock {{ data: ") + .and_then(|()| (&*guard).fmt(f)) + .and_then(|()| write!(f, "}}")), + None => write!(f, "RwLock {{ <locked> }}"), + } + } +} + +impl<T: ?Sized + Default> Default for RwLock<T> { + fn default() -> RwLock<T> { + RwLock::new(Default::default()) + } +} + +impl<'rwlock, T: ?Sized> RwLockUpgradeableGuard<'rwlock, T> { + fn try_upgrade_internal(self, strong: bool) -> Result<RwLockWriteGuard<'rwlock, T>, Self> { + if compare_exchange( + &self.lock, + UPGRADED, + WRITER, + Ordering::Acquire, + Ordering::Relaxed, + strong, + ) + .is_ok() + { + let out = Ok(RwLockWriteGuard { + lock: &self.lock, + data: self.data, + _invariant: PhantomData, + }); + + mem::forget(self); + + out + } else { + Err(self) + } + } + + pub fn upgrade(mut self) -> RwLockWriteGuard<'rwlock, T> { + loop { + self = match self.try_upgrade_internal(false) { + Ok(guard) => return guard, + Err(e) => e, + }; + + cpu_relax(); + } + } + + pub fn try_upgrade(self) -> Result<RwLockWriteGuard<'rwlock, T>, Self> { + self.try_upgrade_internal(true) + } + + pub fn downgrade(self) -> RwLockReadGuard<'rwlock, T> { + self.lock.fetch_add(READER, Ordering::Acquire); + + RwLockReadGuard { + lock: &self.lock, + data: self.data, + } + } +} + +impl<'rwlock, T: ?Sized> RwLockWriteGuard<'rwlock, T> { + pub fn downgrade(self) -> RwLockReadGuard<'rwlock, T> { + self.lock.fetch_add(READER, Ordering::Acquire); + + RwLockReadGuard { + lock: &self.lock, + data: self.data, + } + } +} + +impl<'rwlock, T: ?Sized> Deref for RwLockReadGuard<'rwlock, T> { + type Target = T; + + fn deref(&self) -> &T { + unsafe { self.data.as_ref() } + } +} + +impl<'rwlock, T: ?Sized> Deref for RwLockUpgradeableGuard<'rwlock, T> { + type Target = T; + + fn deref(&self) -> &T { + unsafe { self.data.as_ref() } + } +} + +impl<'rwlock, T: ?Sized> Deref for RwLockWriteGuard<'rwlock, T> { + type Target = T; + + fn deref(&self) -> &T { + unsafe { self.data.as_ref() } + } +} + +impl<'rwlock, T: ?Sized> DerefMut for RwLockWriteGuard<'rwlock, T> { + fn deref_mut(&mut self) -> &mut T { + unsafe { self.data.as_mut() } + } +} + +impl<'rwlock, T: ?Sized> Drop for RwLockReadGuard<'rwlock, T> { + fn drop(&mut self) { + debug_assert!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED) > 0); + + self.lock.fetch_sub(READER, Ordering::Release); + } +} + +impl<'rwlock, T: ?Sized> Drop for RwLockUpgradeableGuard<'rwlock, T> { + fn drop(&mut self) { + debug_assert_eq!( + self.lock.load(Ordering::Relaxed) & (WRITER | UPGRADED), + UPGRADED + ); + + self.lock.fetch_sub(UPGRADED, Ordering::AcqRel); + } +} + +impl<'rwlock, T: ?Sized> Drop for RwLockWriteGuard<'rwlock, T> { + fn drop(&mut self) { + debug_assert_eq!(self.lock.load(Ordering::Relaxed) & WRITER, WRITER); + + self.lock.fetch_and(!(WRITER | UPGRADED), Ordering::Release); + } +} + +fn compare_exchange( + atomic: &AtomicUsize, + current: usize, + new: usize, + success: Ordering, + failure: Ordering, + strong: bool, +) -> Result<usize, usize> { + if strong { + atomic.compare_exchange(current, new, success, failure) + } else { + atomic.compare_exchange_weak(current, new, success, failure) + } +} + +#[cfg(test)] +mod tests { + use super::*; + use std::prelude::v1::*; + use std::sync::atomic::{AtomicUsize, Ordering}; + use std::sync::mpsc::channel; + use std::sync::Arc; + use std::thread; + + #[derive(Eq, PartialEq, Debug)] + struct NonCopy(i32); + + #[test] + fn smoke() { + let l = RwLock::new(()); + drop(l.read()); + drop(l.write()); + drop((l.read(), l.read())); + drop(l.write()); + } + + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn test_rw_arc() { + let arc = Arc::new(RwLock::new(0)); + let arc2 = arc.clone(); + let (tx, rx) = channel(); + + thread::spawn(move || { + let mut lock = arc2.write(); + + for _ in 0..10 { + let tmp = *lock; + *lock = -1; + thread::yield_now(); + *lock = tmp + 1; + } + + tx.send(()).unwrap(); + }); + + let mut children = Vec::new(); + + for _ in 0..5 { + let arc3 = arc.clone(); + + children.push(thread::spawn(move || { + let lock = arc3.read(); + assert!(*lock >= 0); + })); + } + + for r in children { + assert!(r.join().is_ok()); + } + + rx.recv().unwrap(); + let lock = arc.read(); + assert_eq!(*lock, 10); + } + + #[cfg(not(target_arch = "wasm32"))] + #[test] + fn test_rw_access_in_unwind() { + let arc = Arc::new(RwLock::new(1)); + let arc2 = arc.clone(); + + let _ = thread::spawn(move || { + struct Unwinder { + i: Arc<RwLock<isize>>, + } + + impl Drop for Unwinder { + fn drop(&mut self) { + let mut lock = self.i.write(); + + *lock += 1; + } + } + + let _u = Unwinder { i: arc2 }; + + panic!(); + }) + .join(); + + let lock = arc.read(); + assert_eq!(*lock, 2); + } + + #[test] + fn test_rwlock_unsized() { + let rw: &RwLock<[i32]> = &RwLock::new([1, 2, 3]); + + { + let b = &mut *rw.write(); + b[0] = 4; + b[2] = 5; + } + + let comp: &[i32] = &[4, 2, 5]; + + assert_eq!(&*rw.read(), comp); + } + + #[test] + fn test_rwlock_try_write() { + use std::mem::drop; + + let lock = RwLock::new(0isize); + let read_guard = lock.read(); + let write_result = lock.try_write(); + + match write_result { + None => (), + Some(_) => panic!("try_write should not succeed while read_guard is in scope"), + } + + drop(read_guard); + } + + #[test] + fn test_rw_try_read() { + let m = RwLock::new(0); + + mem::forget(m.write()); + + assert!(m.try_read().is_none()); + } + + #[test] + fn test_into_inner() { + let m = RwLock::new(NonCopy(10)); + + assert_eq!(m.into_inner(), NonCopy(10)); + } + + #[test] + fn test_into_inner_drop() { + struct Foo(Arc<AtomicUsize>); + + impl Drop for Foo { + fn drop(&mut self) { + self.0.fetch_add(1, Ordering::SeqCst); + } + } + + let num_drops = Arc::new(AtomicUsize::new(0)); + let m = RwLock::new(Foo(num_drops.clone())); + assert_eq!(num_drops.load(Ordering::SeqCst), 0); + + { + let _inner = m.into_inner(); + assert_eq!(num_drops.load(Ordering::SeqCst), 0); + } + + assert_eq!(num_drops.load(Ordering::SeqCst), 1); + } + + #[test] + fn test_force_read_decrement() { + let m = RwLock::new(()); + ::std::mem::forget(m.read()); + ::std::mem::forget(m.read()); + ::std::mem::forget(m.read()); + assert!(m.try_write().is_none()); + + unsafe { + m.force_read_decrement(); + m.force_read_decrement(); + } + + assert!(m.try_write().is_none()); + + unsafe { + m.force_read_decrement(); + } + + assert!(m.try_write().is_some()); + } + + #[test] + fn test_force_write_unlock() { + let m = RwLock::new(()); + + ::std::mem::forget(m.write()); + + assert!(m.try_read().is_none()); + + unsafe { + m.force_write_unlock(); + } + + assert!(m.try_read().is_some()); + } + + #[test] + fn test_upgrade_downgrade() { + let m = RwLock::new(()); + + { + let _r = m.read(); + let upg = m.try_upgradeable_read().unwrap(); + assert!(m.try_read().is_none()); + assert!(m.try_write().is_none()); + assert!(upg.try_upgrade().is_err()); + } + + { + let w = m.write(); + assert!(m.try_upgradeable_read().is_none()); + let _r = w.downgrade(); + assert!(m.try_upgradeable_read().is_some()); + assert!(m.try_read().is_some()); + assert!(m.try_write().is_none()); + } + + { + let _u = m.upgradeable_read(); + assert!(m.try_upgradeable_read().is_none()); + } + + assert!(m.try_upgradeable_read().unwrap().try_upgrade().is_ok()); + } +} diff --git a/third_party/rust/dashmap/src/mapref/entry.rs b/third_party/rust/dashmap/src/mapref/entry.rs new file mode 100644 index 0000000000..7a609ee61a --- /dev/null +++ b/third_party/rust/dashmap/src/mapref/entry.rs @@ -0,0 +1,198 @@ +use super::one::RefMut; +use crate::lock::RwLockWriteGuard; +use crate::util; +use crate::util::SharedValue; +use crate::HashMap; +use core::hash::{BuildHasher, Hash}; +use core::mem; +use core::ptr; +use std::collections::hash_map::RandomState; + +pub enum Entry<'a, K, V, S = RandomState> { + Occupied(OccupiedEntry<'a, K, V, S>), + Vacant(VacantEntry<'a, K, V, S>), +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> Entry<'a, K, V, S> { + /// Apply a function to the stored value if it exists. + pub fn and_modify(self, f: impl FnOnce(&mut V)) -> Self { + match self { + Entry::Occupied(mut entry) => { + f(entry.get_mut()); + + Entry::Occupied(entry) + } + + Entry::Vacant(entry) => Entry::Vacant(entry), + } + } + + /// Get the key of the entry. + pub fn key(&self) -> &K { + match *self { + Entry::Occupied(ref entry) => entry.key(), + Entry::Vacant(ref entry) => entry.key(), + } + } + + /// Into the key of the entry. + pub fn into_key(self) -> K { + match self { + Entry::Occupied(entry) => entry.into_key(), + Entry::Vacant(entry) => entry.into_key(), + } + } + + /// Return a mutable reference to the element if it exists, + /// otherwise insert the default and return a mutable reference to that. + pub fn or_default(self) -> RefMut<'a, K, V, S> + where + V: Default, + { + match self { + Entry::Occupied(entry) => entry.into_ref(), + Entry::Vacant(entry) => entry.insert(V::default()), + } + } + + /// Return a mutable reference to the element if it exists, + /// otherwise a provided value and return a mutable reference to that. + pub fn or_insert(self, value: V) -> RefMut<'a, K, V, S> { + match self { + Entry::Occupied(entry) => entry.into_ref(), + Entry::Vacant(entry) => entry.insert(value), + } + } + + /// Return a mutable reference to the element if it exists, + /// otherwise insert the result of a provided function and return a mutable reference to that. + pub fn or_insert_with(self, value: impl FnOnce() -> V) -> RefMut<'a, K, V, S> { + match self { + Entry::Occupied(entry) => entry.into_ref(), + Entry::Vacant(entry) => entry.insert(value()), + } + } + + pub fn or_try_insert_with<E>( + self, + value: impl FnOnce() -> Result<V, E>, + ) -> Result<RefMut<'a, K, V, S>, E> { + match self { + Entry::Occupied(entry) => Ok(entry.into_ref()), + Entry::Vacant(entry) => Ok(entry.insert(value()?)), + } + } +} + +pub struct VacantEntry<'a, K, V, S> { + shard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + key: K, +} + +unsafe impl<'a, K: Eq + Hash + Send, V: Send, S: BuildHasher> Send for VacantEntry<'a, K, V, S> {} + +unsafe impl<'a, K: Eq + Hash + Send + Sync, V: Send + Sync, S: BuildHasher> Sync + for VacantEntry<'a, K, V, S> +{ +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> VacantEntry<'a, K, V, S> { + pub(crate) fn new(shard: RwLockWriteGuard<'a, HashMap<K, V, S>>, key: K) -> Self { + Self { shard, key } + } + + pub fn insert(mut self, value: V) -> RefMut<'a, K, V, S> { + unsafe { + let c: K = ptr::read(&self.key); + + self.shard.insert(self.key, SharedValue::new(value)); + + let (k, v) = self.shard.get_key_value(&c).unwrap(); + + let k = util::change_lifetime_const(k); + + let v = &mut *v.as_ptr(); + + let r = RefMut::new(self.shard, k, v); + + mem::forget(c); + + r + } + } + + pub fn into_key(self) -> K { + self.key + } + + pub fn key(&self) -> &K { + &self.key + } +} + +pub struct OccupiedEntry<'a, K, V, S> { + shard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + elem: (&'a K, &'a mut V), + key: K, +} + +unsafe impl<'a, K: Eq + Hash + Send, V: Send, S: BuildHasher> Send for OccupiedEntry<'a, K, V, S> {} + +unsafe impl<'a, K: Eq + Hash + Send + Sync, V: Send + Sync, S: BuildHasher> Sync + for OccupiedEntry<'a, K, V, S> +{ +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> OccupiedEntry<'a, K, V, S> { + pub(crate) fn new( + shard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + key: K, + elem: (&'a K, &'a mut V), + ) -> Self { + Self { shard, elem, key } + } + + pub fn get(&self) -> &V { + self.elem.1 + } + + pub fn get_mut(&mut self) -> &mut V { + self.elem.1 + } + + pub fn insert(&mut self, value: V) -> V { + mem::replace(self.elem.1, value) + } + + pub fn into_ref(self) -> RefMut<'a, K, V, S> { + RefMut::new(self.shard, self.elem.0, self.elem.1) + } + + pub fn into_key(self) -> K { + self.key + } + + pub fn key(&self) -> &K { + self.elem.0 + } + + pub fn remove(mut self) -> V { + self.shard.remove(self.elem.0).unwrap().into_inner() + } + + pub fn remove_entry(mut self) -> (K, V) { + let (k, v) = self.shard.remove_entry(self.elem.0).unwrap(); + + (k, v.into_inner()) + } + + pub fn replace_entry(mut self, value: V) -> (K, V) { + let nk = self.key; + + let (k, v) = self.shard.remove_entry(self.elem.0).unwrap(); + + self.shard.insert(nk, SharedValue::new(value)); + + (k, v.into_inner()) + } +} diff --git a/third_party/rust/dashmap/src/mapref/mod.rs b/third_party/rust/dashmap/src/mapref/mod.rs new file mode 100644 index 0000000000..8897547e01 --- /dev/null +++ b/third_party/rust/dashmap/src/mapref/mod.rs @@ -0,0 +1,3 @@ +pub mod entry; +pub mod multiple; +pub mod one; diff --git a/third_party/rust/dashmap/src/mapref/multiple.rs b/third_party/rust/dashmap/src/mapref/multiple.rs new file mode 100644 index 0000000000..4d30aee46f --- /dev/null +++ b/third_party/rust/dashmap/src/mapref/multiple.rs @@ -0,0 +1,120 @@ +use crate::lock::{RwLockReadGuard, RwLockWriteGuard}; +use crate::HashMap; +use core::hash::BuildHasher; +use core::hash::Hash; +use core::ops::{Deref, DerefMut}; +use std::collections::hash_map::RandomState; +use std::sync::Arc; + +// -- Shared +pub struct RefMulti<'a, K, V, S = RandomState> { + _guard: Arc<RwLockReadGuard<'a, HashMap<K, V, S>>>, + k: &'a K, + v: &'a V, +} + +unsafe impl<'a, K: Eq + Hash + Send, V: Send, S: BuildHasher> Send for RefMulti<'a, K, V, S> {} + +unsafe impl<'a, K: Eq + Hash + Send + Sync, V: Send + Sync, S: BuildHasher> Sync + for RefMulti<'a, K, V, S> +{ +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> RefMulti<'a, K, V, S> { + pub(crate) fn new( + guard: Arc<RwLockReadGuard<'a, HashMap<K, V, S>>>, + k: &'a K, + v: &'a V, + ) -> Self { + Self { + _guard: guard, + k, + v, + } + } + + pub fn key(&self) -> &K { + self.k + } + + pub fn value(&self) -> &V { + self.v + } + + pub fn pair(&self) -> (&K, &V) { + (self.k, self.v) + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> Deref for RefMulti<'a, K, V, S> { + type Target = V; + + fn deref(&self) -> &V { + self.value() + } +} + +// -- +// -- Unique +pub struct RefMutMulti<'a, K, V, S = RandomState> { + _guard: Arc<RwLockWriteGuard<'a, HashMap<K, V, S>>>, + k: &'a K, + v: &'a mut V, +} + +unsafe impl<'a, K: Eq + Hash + Send, V: Send, S: BuildHasher> Send for RefMutMulti<'a, K, V, S> {} + +unsafe impl<'a, K: Eq + Hash + Send + Sync, V: Send + Sync, S: BuildHasher> Sync + for RefMutMulti<'a, K, V, S> +{ +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> RefMutMulti<'a, K, V, S> { + pub(crate) fn new( + guard: Arc<RwLockWriteGuard<'a, HashMap<K, V, S>>>, + k: &'a K, + v: &'a mut V, + ) -> Self { + Self { + _guard: guard, + k, + v, + } + } + + pub fn key(&self) -> &K { + self.k + } + + pub fn value(&self) -> &V { + self.v + } + + pub fn value_mut(&mut self) -> &mut V { + self.v + } + + pub fn pair(&self) -> (&K, &V) { + (self.k, self.v) + } + + pub fn pair_mut(&mut self) -> (&K, &mut V) { + (self.k, self.v) + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> Deref for RefMutMulti<'a, K, V, S> { + type Target = V; + + fn deref(&self) -> &V { + self.value() + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> DerefMut for RefMutMulti<'a, K, V, S> { + fn deref_mut(&mut self) -> &mut V { + self.value_mut() + } +} + +// -- diff --git a/third_party/rust/dashmap/src/mapref/one.rs b/third_party/rust/dashmap/src/mapref/one.rs new file mode 100644 index 0000000000..67c1706ef8 --- /dev/null +++ b/third_party/rust/dashmap/src/mapref/one.rs @@ -0,0 +1,114 @@ +use crate::lock::{RwLockReadGuard, RwLockWriteGuard}; +use crate::HashMap; +use core::hash::{BuildHasher, Hash}; +use core::ops::{Deref, DerefMut}; +use std::collections::hash_map::RandomState; + +// -- Shared +pub struct Ref<'a, K, V, S = RandomState> { + _guard: RwLockReadGuard<'a, HashMap<K, V, S>>, + k: &'a K, + v: &'a V, +} + +unsafe impl<'a, K: Eq + Hash + Send, V: Send, S: BuildHasher> Send for Ref<'a, K, V, S> {} + +unsafe impl<'a, K: Eq + Hash + Send + Sync, V: Send + Sync, S: BuildHasher> Sync + for Ref<'a, K, V, S> +{ +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> Ref<'a, K, V, S> { + pub(crate) fn new(guard: RwLockReadGuard<'a, HashMap<K, V, S>>, k: &'a K, v: &'a V) -> Self { + Self { + _guard: guard, + k, + v, + } + } + + pub fn key(&self) -> &K { + self.k + } + + pub fn value(&self) -> &V { + self.v + } + + pub fn pair(&self) -> (&K, &V) { + (self.k, self.v) + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> Deref for Ref<'a, K, V, S> { + type Target = V; + + fn deref(&self) -> &V { + self.value() + } +} + +// -- +// -- Unique +pub struct RefMut<'a, K, V, S = RandomState> { + guard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + k: &'a K, + v: &'a mut V, +} + +unsafe impl<'a, K: Eq + Hash + Send, V: Send, S: BuildHasher> Send for RefMut<'a, K, V, S> {} + +unsafe impl<'a, K: Eq + Hash + Send + Sync, V: Send + Sync, S: BuildHasher> Sync + for RefMut<'a, K, V, S> +{ +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> RefMut<'a, K, V, S> { + pub(crate) fn new( + guard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + k: &'a K, + v: &'a mut V, + ) -> Self { + Self { guard, k, v } + } + + pub fn key(&self) -> &K { + self.k + } + + pub fn value(&self) -> &V { + self.v + } + + pub fn value_mut(&mut self) -> &mut V { + self.v + } + + pub fn pair(&self) -> (&K, &V) { + (self.k, self.v) + } + + pub fn pair_mut(&mut self) -> (&K, &mut V) { + (self.k, self.v) + } + + pub fn downgrade(self) -> Ref<'a, K, V, S> { + Ref::new(self.guard.downgrade(), self.k, self.v) + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> Deref for RefMut<'a, K, V, S> { + type Target = V; + + fn deref(&self) -> &V { + self.value() + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> DerefMut for RefMut<'a, K, V, S> { + fn deref_mut(&mut self) -> &mut V { + self.value_mut() + } +} + +// -- diff --git a/third_party/rust/dashmap/src/rayon/map.rs b/third_party/rust/dashmap/src/rayon/map.rs new file mode 100644 index 0000000000..48fdeacf14 --- /dev/null +++ b/third_party/rust/dashmap/src/rayon/map.rs @@ -0,0 +1,221 @@ +use crate::lock::RwLock; +use crate::mapref::multiple::{RefMulti, RefMutMulti}; +use crate::util; +use crate::{DashMap, HashMap}; +use core::hash::{BuildHasher, Hash}; +use rayon::iter::plumbing::UnindexedConsumer; +use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator}; +use std::collections::hash_map::RandomState; +use std::sync::Arc; + +impl<K, V, S> ParallelExtend<(K, V)> for DashMap<K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + BuildHasher, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = (K, V)>, + { + (&*self).par_extend(par_iter); + } +} + +// Since we don't actually need mutability, we can implement this on a +// reference, similar to `io::Write for &File`. +impl<K, V, S> ParallelExtend<(K, V)> for &'_ DashMap<K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + BuildHasher, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = (K, V)>, + { + let &mut map = self; + par_iter.into_par_iter().for_each(move |(key, value)| { + map.insert(key, value); + }); + } +} + +impl<K, V, S> FromParallelIterator<(K, V)> for DashMap<K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + Default + BuildHasher, +{ + fn from_par_iter<I>(par_iter: I) -> Self + where + I: IntoParallelIterator<Item = (K, V)>, + { + let map = Self::default(); + (&map).par_extend(par_iter); + map + } +} + +// Implementation note: while the shards will iterate in parallel, we flatten +// sequentially within each shard (`flat_map_iter`), because the standard +// `HashMap` only implements `ParallelIterator` by collecting to a `Vec` first. +// There is real parallel support in the `hashbrown/rayon` feature, but we don't +// always use that map. + +impl<K, V, S> IntoParallelIterator for DashMap<K, V, S> +where + K: Send + Eq + Hash, + V: Send, + S: Send + Clone + BuildHasher, +{ + type Iter = OwningIter<K, V, S>; + type Item = (K, V); + + fn into_par_iter(self) -> Self::Iter { + OwningIter { + shards: self.shards, + } + } +} + +pub struct OwningIter<K, V, S = RandomState> { + shards: Box<[RwLock<HashMap<K, V, S>>]>, +} + +impl<K, V, S> ParallelIterator for OwningIter<K, V, S> +where + K: Send + Eq + Hash, + V: Send, + S: Send + Clone + BuildHasher, +{ + type Item = (K, V); + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + Vec::from(self.shards) + .into_par_iter() + .flat_map_iter(|shard| { + shard + .into_inner() + .into_iter() + .map(|(k, v)| (k, v.into_inner())) + }) + .drive_unindexed(consumer) + } +} + +// This impl also enables `IntoParallelRefIterator::par_iter` +impl<'a, K, V, S> IntoParallelIterator for &'a DashMap<K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + BuildHasher, +{ + type Iter = Iter<'a, K, V, S>; + type Item = RefMulti<'a, K, V, S>; + + fn into_par_iter(self) -> Self::Iter { + Iter { + shards: &self.shards, + } + } +} + +pub struct Iter<'a, K, V, S = RandomState> { + shards: &'a [RwLock<HashMap<K, V, S>>], +} + +impl<'a, K, V, S> ParallelIterator for Iter<'a, K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + BuildHasher, +{ + type Item = RefMulti<'a, K, V, S>; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.shards + .into_par_iter() + .flat_map_iter(|shard| { + let guard = shard.read(); + let sref: &'a HashMap<K, V, S> = unsafe { util::change_lifetime_const(&*guard) }; + + let guard = Arc::new(guard); + sref.iter().map(move |(k, v)| { + let guard = Arc::clone(&guard); + RefMulti::new(guard, k, v.get()) + }) + }) + .drive_unindexed(consumer) + } +} + +// This impl also enables `IntoParallelRefMutIterator::par_iter_mut` +impl<'a, K, V, S> IntoParallelIterator for &'a mut DashMap<K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + BuildHasher, +{ + type Iter = IterMut<'a, K, V, S>; + type Item = RefMutMulti<'a, K, V, S>; + + fn into_par_iter(self) -> Self::Iter { + IterMut { + shards: &self.shards, + } + } +} + +impl<'a, K, V, S> DashMap<K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + BuildHasher, +{ + // Unlike `IntoParallelRefMutIterator::par_iter_mut`, we only _need_ `&self`. + pub fn par_iter_mut(&self) -> IterMut<'_, K, V, S> { + IterMut { + shards: &self.shards, + } + } +} + +pub struct IterMut<'a, K, V, S = RandomState> { + shards: &'a [RwLock<HashMap<K, V, S>>], +} + +impl<'a, K, V, S> ParallelIterator for IterMut<'a, K, V, S> +where + K: Send + Sync + Eq + Hash, + V: Send + Sync, + S: Send + Sync + Clone + BuildHasher, +{ + type Item = RefMutMulti<'a, K, V, S>; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.shards + .into_par_iter() + .flat_map_iter(|shard| { + let mut guard = shard.write(); + let sref: &'a mut HashMap<K, V, S> = + unsafe { util::change_lifetime_mut(&mut *guard) }; + + let guard = Arc::new(guard); + sref.iter_mut().map(move |(k, v)| { + let guard = Arc::clone(&guard); + RefMutMulti::new(guard, k, v.get_mut()) + }) + }) + .drive_unindexed(consumer) + } +} diff --git a/third_party/rust/dashmap/src/rayon/set.rs b/third_party/rust/dashmap/src/rayon/set.rs new file mode 100644 index 0000000000..11c06ccbd1 --- /dev/null +++ b/third_party/rust/dashmap/src/rayon/set.rs @@ -0,0 +1,121 @@ +use crate::setref::multiple::RefMulti; +use crate::DashSet; +use core::hash::{BuildHasher, Hash}; +use rayon::iter::plumbing::UnindexedConsumer; +use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator}; +use std::collections::hash_map::RandomState; + +impl<K, S> ParallelExtend<K> for DashSet<K, S> +where + K: Send + Sync + Eq + Hash, + S: Send + Sync + Clone + BuildHasher, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = K>, + { + (&*self).par_extend(par_iter); + } +} + +// Since we don't actually need mutability, we can implement this on a +// reference, similar to `io::Write for &File`. +impl<K, S> ParallelExtend<K> for &'_ DashSet<K, S> +where + K: Send + Sync + Eq + Hash, + S: Send + Sync + Clone + BuildHasher, +{ + fn par_extend<I>(&mut self, par_iter: I) + where + I: IntoParallelIterator<Item = K>, + { + let &mut set = self; + par_iter.into_par_iter().for_each(move |key| { + set.insert(key); + }); + } +} + +impl<K, S> FromParallelIterator<K> for DashSet<K, S> +where + K: Send + Sync + Eq + Hash, + S: Send + Sync + Clone + Default + BuildHasher, +{ + fn from_par_iter<I>(par_iter: I) -> Self + where + I: IntoParallelIterator<Item = K>, + { + let set = Self::default(); + (&set).par_extend(par_iter); + set + } +} + +impl<K, S> IntoParallelIterator for DashSet<K, S> +where + K: Send + Eq + Hash, + S: Send + Clone + BuildHasher, +{ + type Iter = OwningIter<K, S>; + type Item = K; + + fn into_par_iter(self) -> Self::Iter { + OwningIter { + inner: self.inner.into_par_iter(), + } + } +} + +pub struct OwningIter<K, S = RandomState> { + inner: super::map::OwningIter<K, (), S>, +} + +impl<K, S> ParallelIterator for OwningIter<K, S> +where + K: Send + Eq + Hash, + S: Send + Clone + BuildHasher, +{ + type Item = K; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner.map(|(k, _)| k).drive_unindexed(consumer) + } +} + +// This impl also enables `IntoParallelRefIterator::par_iter` +impl<'a, K, S> IntoParallelIterator for &'a DashSet<K, S> +where + K: Send + Sync + Eq + Hash, + S: Send + Sync + Clone + BuildHasher, +{ + type Iter = Iter<'a, K, S>; + type Item = RefMulti<'a, K, S>; + + fn into_par_iter(self) -> Self::Iter { + Iter { + inner: (&self.inner).into_par_iter(), + } + } +} + +pub struct Iter<'a, K, S = RandomState> { + inner: super::map::Iter<'a, K, (), S>, +} + +impl<'a, K, S> ParallelIterator for Iter<'a, K, S> +where + K: Send + Sync + Eq + Hash, + S: Send + Sync + Clone + BuildHasher, +{ + type Item = RefMulti<'a, K, S>; + + fn drive_unindexed<C>(self, consumer: C) -> C::Result + where + C: UnindexedConsumer<Self::Item>, + { + self.inner.map(RefMulti::new).drive_unindexed(consumer) + } +} diff --git a/third_party/rust/dashmap/src/read_only.rs b/third_party/rust/dashmap/src/read_only.rs new file mode 100644 index 0000000000..b0e7a65e19 --- /dev/null +++ b/third_party/rust/dashmap/src/read_only.rs @@ -0,0 +1,243 @@ +use crate::t::Map; +use crate::{DashMap, HashMap}; +use core::borrow::Borrow; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use std::collections::hash_map::RandomState; + +/// A read-only view into a `DashMap`. Allows to obtain raw references to the stored values. +pub struct ReadOnlyView<K, V, S = RandomState> { + map: DashMap<K, V, S>, +} + +impl<K: Eq + Hash + Clone, V: Clone, S: Clone> Clone for ReadOnlyView<K, V, S> { + fn clone(&self) -> Self { + Self { + map: self.map.clone(), + } + } +} + +impl<K: Eq + Hash + fmt::Debug, V: fmt::Debug, S: BuildHasher + Clone> fmt::Debug + for ReadOnlyView<K, V, S> +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.map.fmt(f) + } +} + +impl<K, V, S> ReadOnlyView<K, V, S> { + pub(crate) fn new(map: DashMap<K, V, S>) -> Self { + Self { map } + } + + /// Consumes this `ReadOnlyView`, returning the underlying `DashMap`. + pub fn into_inner(self) -> DashMap<K, V, S> { + self.map + } +} + +impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone> ReadOnlyView<K, V, S> { + /// Returns the number of elements in the map. + pub fn len(&self) -> usize { + self.map.len() + } + + /// Returns `true` if the map contains no elements. + pub fn is_empty(&self) -> bool { + self.map.is_empty() + } + + /// Returns the number of elements the map can hold without reallocating. + pub fn capacity(&self) -> usize { + self.map.capacity() + } + + /// Returns `true` if the map contains a value for the specified key. + pub fn contains_key<Q>(&'a self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.map.hash_usize(&key); + + let idx = self.map.determine_shard(hash); + + let shard = unsafe { self.map._get_read_shard(idx) }; + + shard.contains_key(key) + } + + /// Returns a reference to the value corresponding to the key. + pub fn get<Q>(&'a self, key: &Q) -> Option<&'a V> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.map.hash_usize(&key); + + let idx = self.map.determine_shard(hash); + + let shard = unsafe { self.map._get_read_shard(idx) }; + + shard.get(key).map(|v| v.get()) + } + + /// Returns the key-value pair corresponding to the supplied key. + pub fn get_key_value<Q>(&'a self, key: &Q) -> Option<(&'a K, &'a V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + let hash = self.map.hash_usize(&key); + + let idx = self.map.determine_shard(hash); + + let shard = unsafe { self.map._get_read_shard(idx) }; + + shard.get_key_value(key).map(|(k, v)| (k, v.get())) + } + + fn shard_read_iter(&'a self) -> impl Iterator<Item = &'a HashMap<K, V, S>> + 'a { + (0..self.map._shard_count()) + .map(move |shard_i| unsafe { self.map._get_read_shard(shard_i) }) + } + + /// An iterator visiting all key-value pairs in arbitrary order. The iterator element type is `(&'a K, &'a V)`. + pub fn iter(&'a self) -> impl Iterator<Item = (&'a K, &'a V)> + 'a { + self.shard_read_iter() + .flat_map(|shard| shard.iter()) + .map(|(k, v)| (k, v.get())) + } + + /// An iterator visiting all keys in arbitrary order. The iterator element type is `&'a K`. + pub fn keys(&'a self) -> impl Iterator<Item = &'a K> + 'a { + self.shard_read_iter().flat_map(|shard| shard.keys()) + } + + /// An iterator visiting all values in arbitrary order. The iterator element type is `&'a V`. + pub fn values(&'a self) -> impl Iterator<Item = &'a V> + 'a { + self.shard_read_iter() + .flat_map(|shard| shard.values()) + .map(|v| v.get()) + } +} + +#[cfg(test)] + +mod tests { + + use crate::DashMap; + + fn construct_sample_map() -> DashMap<i32, String> { + let map = DashMap::new(); + + map.insert(1, "one".to_string()); + + map.insert(10, "ten".to_string()); + + map.insert(27, "twenty seven".to_string()); + + map.insert(45, "forty five".to_string()); + + map + } + + #[test] + + fn test_properties() { + let map = construct_sample_map(); + + let view = map.clone().into_read_only(); + + assert_eq!(view.is_empty(), map.is_empty()); + + assert_eq!(view.len(), map.len()); + + assert_eq!(view.capacity(), map.capacity()); + + let new_map = view.into_inner(); + + assert_eq!(new_map.is_empty(), map.is_empty()); + + assert_eq!(new_map.len(), map.len()); + + assert_eq!(new_map.capacity(), map.capacity()); + } + + #[test] + + fn test_get() { + let map = construct_sample_map(); + + let view = map.clone().into_read_only(); + + for key in map.iter().map(|entry| *entry.key()) { + assert!(view.contains_key(&key)); + + let map_entry = map.get(&key).unwrap(); + + assert_eq!(view.get(&key).unwrap(), map_entry.value()); + + let key_value: (&i32, &String) = view.get_key_value(&key).unwrap(); + + assert_eq!(key_value.0, map_entry.key()); + + assert_eq!(key_value.1, map_entry.value()); + } + } + + #[test] + + fn test_iters() { + let map = construct_sample_map(); + + let view = map.clone().into_read_only(); + + let mut visited_items = Vec::new(); + + for (key, value) in view.iter() { + map.contains_key(key); + + let map_entry = map.get(&key).unwrap(); + + assert_eq!(key, map_entry.key()); + + assert_eq!(value, map_entry.value()); + + visited_items.push((key, value)); + } + + let mut visited_keys = Vec::new(); + + for key in view.keys() { + map.contains_key(key); + + let map_entry = map.get(&key).unwrap(); + + assert_eq!(key, map_entry.key()); + + assert_eq!(view.get(key).unwrap(), map_entry.value()); + + visited_keys.push(key); + } + + let mut visited_values = Vec::new(); + + for value in view.values() { + visited_values.push(value); + } + + for entry in map.iter() { + let key = entry.key(); + + let value = entry.value(); + + assert!(visited_keys.contains(&key)); + + assert!(visited_values.contains(&value)); + + assert!(visited_items.contains(&(key, value))); + } + } +} diff --git a/third_party/rust/dashmap/src/serde.rs b/third_party/rust/dashmap/src/serde.rs new file mode 100644 index 0000000000..c0f2bb2c1b --- /dev/null +++ b/third_party/rust/dashmap/src/serde.rs @@ -0,0 +1,148 @@ +use crate::{DashMap, DashSet}; +use core::fmt; +use core::hash::Hash; +use core::marker::PhantomData; +use serde::de::{Deserialize, MapAccess, SeqAccess, Visitor}; +use serde::ser::{Serialize, SerializeMap, SerializeSeq, Serializer}; +use serde::Deserializer; + +pub struct DashMapVisitor<K, V> { + marker: PhantomData<fn() -> DashMap<K, V>>, +} + +impl<K, V> DashMapVisitor<K, V> +where + K: Eq + Hash, +{ + fn new() -> Self { + DashMapVisitor { + marker: PhantomData, + } + } +} + +impl<'de, K, V> Visitor<'de> for DashMapVisitor<K, V> +where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, +{ + type Value = DashMap<K, V>; + + fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str("a DashMap") + } + + fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error> + where + M: MapAccess<'de>, + { + let map = DashMap::with_capacity(access.size_hint().unwrap_or(0)); + + while let Some((key, value)) = access.next_entry()? { + map.insert(key, value); + } + + Ok(map) + } +} + +impl<'de, K, V> Deserialize<'de> for DashMap<K, V> +where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + deserializer.deserialize_map(DashMapVisitor::<K, V>::new()) + } +} + +impl<K, V> Serialize for DashMap<K, V> +where + K: Serialize + Eq + Hash, + V: Serialize, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut map = serializer.serialize_map(Some(self.len()))?; + + for ref_multi in self.iter() { + map.serialize_entry(ref_multi.key(), ref_multi.value())?; + } + + map.end() + } +} + +pub struct DashSetVisitor<K> { + marker: PhantomData<fn() -> DashSet<K>>, +} + +impl<K> DashSetVisitor<K> +where + K: Eq + Hash, +{ + fn new() -> Self { + DashSetVisitor { + marker: PhantomData, + } + } +} + +impl<'de, K> Visitor<'de> for DashSetVisitor<K> +where + K: Deserialize<'de> + Eq + Hash, +{ + type Value = DashSet<K>; + + fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str("a DashSet") + } + + fn visit_seq<M>(self, mut access: M) -> Result<Self::Value, M::Error> + where + M: SeqAccess<'de>, + { + let map = DashSet::with_capacity(access.size_hint().unwrap_or(0)); + + while let Some(key) = access.next_element()? { + map.insert(key); + } + + Ok(map) + } +} + +impl<'de, K> Deserialize<'de> for DashSet<K> +where + K: Deserialize<'de> + Eq + Hash, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + deserializer.deserialize_seq(DashSetVisitor::<K>::new()) + } +} + +impl<K> Serialize for DashSet<K> +where + K: Serialize + Eq + Hash, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + let mut seq = serializer.serialize_seq(Some(self.len()))?; + + for ref_multi in self.iter() { + seq.serialize_element(ref_multi.key())?; + } + + seq.end() + } +} diff --git a/third_party/rust/dashmap/src/set.rs b/third_party/rust/dashmap/src/set.rs new file mode 100644 index 0000000000..e4d77df108 --- /dev/null +++ b/third_party/rust/dashmap/src/set.rs @@ -0,0 +1,458 @@ +use crate::iter_set::{Iter, OwningIter}; +#[cfg(feature = "raw-api")] +use crate::lock::RwLock; +use crate::setref::one::Ref; +use crate::DashMap; +#[cfg(feature = "raw-api")] +use crate::HashMap; +use cfg_if::cfg_if; +use core::borrow::Borrow; +use core::fmt; +use core::hash::{BuildHasher, Hash}; +use core::iter::FromIterator; +use std::collections::hash_map::RandomState; + +/// DashSet is a thin wrapper around [`DashMap`] using `()` as the value type. It uses +/// methods and types which are more convenient to work with on a set. +/// +/// [`DashMap`]: struct.DashMap.html +pub struct DashSet<K, S = RandomState> { + pub(crate) inner: DashMap<K, (), S>, +} + +impl<K: Eq + Hash + fmt::Debug, S: BuildHasher + Clone> fmt::Debug for DashSet<K, S> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.inner, f) + } +} + +impl<K: Eq + Hash + Clone, S: Clone> Clone for DashSet<K, S> { + fn clone(&self) -> Self { + Self { + inner: self.inner.clone(), + } + } + + fn clone_from(&mut self, source: &Self) { + self.inner.clone_from(&source.inner) + } +} + +impl<K, S> Default for DashSet<K, S> +where + K: Eq + Hash, + S: Default + BuildHasher + Clone, +{ + fn default() -> Self { + Self::with_hasher(Default::default()) + } +} + +impl<'a, K: 'a + Eq + Hash> DashSet<K, RandomState> { + /// Creates a new DashSet with a capacity of 0. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let games = DashSet::new(); + /// games.insert("Veloren"); + /// ``` + pub fn new() -> Self { + Self::with_hasher(RandomState::default()) + } + + /// Creates a new DashMap with a specified starting capacity. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let numbers = DashSet::with_capacity(2); + /// numbers.insert(2); + /// numbers.insert(8); + /// ``` + pub fn with_capacity(capacity: usize) -> Self { + Self::with_capacity_and_hasher(capacity, RandomState::default()) + } +} + +impl<'a, K: 'a + Eq + Hash, S: BuildHasher + Clone> DashSet<K, S> { + /// Creates a new DashMap with a capacity of 0 and the provided hasher. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let games = DashSet::with_hasher(s); + /// games.insert("Veloren"); + /// ``` + pub fn with_hasher(hasher: S) -> Self { + Self::with_capacity_and_hasher(0, hasher) + } + + /// Creates a new DashMap with a specified starting capacity and hasher. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let numbers = DashSet::with_capacity_and_hasher(2, s); + /// numbers.insert(2); + /// numbers.insert(8); + /// ``` + pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self { + Self { + inner: DashMap::with_capacity_and_hasher(capacity, hasher), + } + } + + /// Hash a given item to produce a usize. + /// Uses the provided or default HashBuilder. + pub fn hash_usize<T: Hash>(&self, item: &T) -> usize { + self.inner.hash_usize(item) + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Allows you to peek at the inner shards that store your data. + /// You should probably not use this unless you know what you are doing. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set = DashSet::<()>::new(); + /// println!("Amount of shards: {}", set.shards().len()); + /// ``` + pub fn shards(&self) -> &[RwLock<HashMap<K, (), S>>] { + self.inner.shards() + } + } + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Finds which shard a certain key is stored in. + /// You should probably not use this unless you know what you are doing. + /// Note that shard selection is dependent on the default or provided HashBuilder. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set = DashSet::new(); + /// set.insert("coca-cola"); + /// println!("coca-cola is stored in shard: {}", set.determine_map("coca-cola")); + /// ``` + pub fn determine_map<Q>(&self, key: &Q) -> usize + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.determine_map(key) + } + } + } + + cfg_if! { + if #[cfg(feature = "raw-api")] { + /// Finds which shard a certain hash is stored in. + /// + /// Requires the `raw-api` feature to be enabled. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set: DashSet<i32> = DashSet::new(); + /// let key = "key"; + /// let hash = set.hash_usize(&key); + /// println!("hash is stored in shard: {}", set.determine_shard(hash)); + /// ``` + pub fn determine_shard(&self, hash: usize) -> usize { + self.inner.determine_shard(hash) + } + } + } + + /// Inserts a key into the set. Returns true if the key was not already in the set. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let set = DashSet::new(); + /// set.insert("I am the key!"); + /// ``` + pub fn insert(&self, key: K) -> bool { + self.inner.insert(key, ()).is_none() + } + + /// Removes an entry from the map, returning the key if it existed in the map. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let soccer_team = DashSet::new(); + /// soccer_team.insert("Jack"); + /// assert_eq!(soccer_team.remove("Jack").unwrap(), "Jack"); + /// ``` + pub fn remove<Q>(&self, key: &Q) -> Option<K> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.remove(key).map(|(k, _)| k) + } + + /// Removes an entry from the set, returning the key + /// if the entry existed and the provided conditional function returned true. + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let soccer_team = DashSet::new(); + /// soccer_team.insert("Sam"); + /// soccer_team.remove_if("Sam", |player| player.starts_with("Ja")); + /// assert!(soccer_team.contains("Sam")); + /// ``` + /// ``` + /// use dashmap::DashSet; + /// + /// let soccer_team = DashSet::new(); + /// soccer_team.insert("Sam"); + /// soccer_team.remove_if("Jacob", |player| player.starts_with("Ja")); + /// assert!(!soccer_team.contains("Jacob")); + /// ``` + pub fn remove_if<Q>(&self, key: &Q, f: impl FnOnce(&K) -> bool) -> Option<K> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + // TODO: Don't create another closure around f + self.inner.remove_if(key, |k, _| f(k)).map(|(k, _)| k) + } + + /// Creates an iterator over a DashMap yielding immutable references. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let words = DashSet::new(); + /// words.insert("hello"); + /// assert_eq!(words.iter().count(), 1); + /// ``` + pub fn iter(&'a self) -> Iter<'a, K, S, DashMap<K, (), S>> { + let iter = self.inner.iter(); + + Iter::new(iter) + } + + /// Get a reference to an entry in the set + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let youtubers = DashSet::new(); + /// youtubers.insert("Bosnian Bill"); + /// assert_eq!(*youtubers.get("Bosnian Bill").unwrap(), "Bosnian Bill"); + /// ``` + pub fn get<Q>(&'a self, key: &Q) -> Option<Ref<'a, K, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.get(key).map(Ref::new) + } + + /// Remove excess capacity to reduce memory usage. + pub fn shrink_to_fit(&self) { + self.inner.shrink_to_fit() + } + + /// Retain elements that whose predicates return true + /// and discard elements whose predicates return false. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Albin"); + /// people.insert("Jones"); + /// people.insert("Charlie"); + /// people.retain(|name| name.contains('i')); + /// assert_eq!(people.len(), 2); + /// ``` + pub fn retain(&self, mut f: impl FnMut(&K) -> bool) { + self.inner.retain(|k, _| f(k)) + } + + /// Fetches the total number of keys stored in the set. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Albin"); + /// people.insert("Jones"); + /// people.insert("Charlie"); + /// assert_eq!(people.len(), 3); + /// ``` + pub fn len(&self) -> usize { + self.inner.len() + } + + /// Checks if the set is empty or not. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let map = DashSet::<()>::new(); + /// assert!(map.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self.inner.is_empty() + } + + /// Removes all keys in the set. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Albin"); + /// assert!(!people.is_empty()); + /// people.clear(); + /// assert!(people.is_empty()); + /// ``` + pub fn clear(&self) { + self.inner.clear() + } + + /// Returns how many keys the set can store without reallocating. + pub fn capacity(&self) -> usize { + self.inner.capacity() + } + + /// Checks if the set contains a specific key. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashSet; + /// + /// let people = DashSet::new(); + /// people.insert("Dakota Cherries"); + /// assert!(people.contains("Dakota Cherries")); + /// ``` + pub fn contains<Q>(&self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.inner.contains_key(key) + } +} + +impl<'a, K: Eq + Hash, S: BuildHasher + Clone> IntoIterator for DashSet<K, S> { + type Item = K; + + type IntoIter = OwningIter<K, S>; + + fn into_iter(self) -> Self::IntoIter { + OwningIter::new(self.inner.into_iter()) + } +} + +impl<K: Eq + Hash, S: BuildHasher + Clone> Extend<K> for DashSet<K, S> { + fn extend<T: IntoIterator<Item = K>>(&mut self, iter: T) { + let iter = iter.into_iter().map(|k| (k, ())); + + self.inner.extend(iter) + } +} + +impl<K: Eq + Hash> FromIterator<K> for DashSet<K, RandomState> { + fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self { + let mut set = DashSet::new(); + + set.extend(iter); + + set + } +} + +#[cfg(test)] +mod tests { + use crate::DashSet; + + #[test] + fn test_basic() { + let set = DashSet::new(); + + set.insert(0); + + assert_eq!(set.get(&0).as_deref(), Some(&0)); + } + + #[test] + fn test_default() { + let set: DashSet<u32> = DashSet::default(); + + set.insert(0); + + assert_eq!(set.get(&0).as_deref(), Some(&0)); + } + + #[test] + fn test_multiple_hashes() { + let set = DashSet::<u32>::default(); + + for i in 0..100 { + assert!(set.insert(i)); + } + + for i in 0..100 { + assert!(!set.insert(i)); + } + + for i in 0..100 { + assert_eq!(Some(i), set.remove(&i)); + } + + for i in 0..100 { + assert_eq!(None, set.remove(&i)); + } + } +} diff --git a/third_party/rust/dashmap/src/setref/mod.rs b/third_party/rust/dashmap/src/setref/mod.rs new file mode 100644 index 0000000000..95ae8f47f2 --- /dev/null +++ b/third_party/rust/dashmap/src/setref/mod.rs @@ -0,0 +1,2 @@ +pub mod multiple; +pub mod one; diff --git a/third_party/rust/dashmap/src/setref/multiple.rs b/third_party/rust/dashmap/src/setref/multiple.rs new file mode 100644 index 0000000000..21e7ed4a70 --- /dev/null +++ b/third_party/rust/dashmap/src/setref/multiple.rs @@ -0,0 +1,25 @@ +use crate::mapref; +use core::hash::{BuildHasher, Hash}; +use core::ops::Deref; +use std::collections::hash_map::RandomState; +pub struct RefMulti<'a, K, S = RandomState> { + inner: mapref::multiple::RefMulti<'a, K, (), S>, +} + +impl<'a, K: Eq + Hash, S: BuildHasher> RefMulti<'a, K, S> { + pub(crate) fn new(inner: mapref::multiple::RefMulti<'a, K, (), S>) -> Self { + Self { inner } + } + + pub fn key(&self) -> &K { + self.inner.key() + } +} + +impl<'a, K: Eq + Hash, S: BuildHasher> Deref for RefMulti<'a, K, S> { + type Target = K; + + fn deref(&self) -> &K { + self.key() + } +} diff --git a/third_party/rust/dashmap/src/setref/one.rs b/third_party/rust/dashmap/src/setref/one.rs new file mode 100644 index 0000000000..ef03421563 --- /dev/null +++ b/third_party/rust/dashmap/src/setref/one.rs @@ -0,0 +1,29 @@ +use crate::mapref; +use core::hash::{BuildHasher, Hash}; +use core::ops::Deref; +use std::collections::hash_map::RandomState; +pub struct Ref<'a, K, S = RandomState> { + inner: mapref::one::Ref<'a, K, (), S>, +} + +unsafe impl<'a, K: Eq + Hash + Send, S: BuildHasher> Send for Ref<'a, K, S> {} + +unsafe impl<'a, K: Eq + Hash + Send + Sync, S: BuildHasher> Sync for Ref<'a, K, S> {} + +impl<'a, K: Eq + Hash, S: BuildHasher> Ref<'a, K, S> { + pub(crate) fn new(inner: mapref::one::Ref<'a, K, (), S>) -> Self { + Self { inner } + } + + pub fn key(&self) -> &K { + self.inner.key() + } +} + +impl<'a, K: Eq + Hash, S: BuildHasher> Deref for Ref<'a, K, S> { + type Target = K; + + fn deref(&self) -> &K { + self.key() + } +} diff --git a/third_party/rust/dashmap/src/t.rs b/third_party/rust/dashmap/src/t.rs new file mode 100644 index 0000000000..6c2e81a6cc --- /dev/null +++ b/third_party/rust/dashmap/src/t.rs @@ -0,0 +1,95 @@ +//! Central map trait to ease modifications and extensions down the road. + +use crate::iter::{Iter, IterMut}; +use crate::lock::{RwLockReadGuard, RwLockWriteGuard}; +use crate::mapref::entry::Entry; +use crate::mapref::one::{Ref, RefMut}; +use crate::HashMap; +use core::borrow::Borrow; +use core::hash::{BuildHasher, Hash}; + +/// Implementation detail that is exposed due to generic constraints in public types. +pub trait Map<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + Clone + BuildHasher> { + fn _shard_count(&self) -> usize; + + /// # Safety + /// + /// The index must not be out of bounds. + unsafe fn _get_read_shard(&'a self, i: usize) -> &'a HashMap<K, V, S>; + + /// # Safety + /// + /// The index must not be out of bounds. + unsafe fn _yield_read_shard(&'a self, i: usize) -> RwLockReadGuard<'a, HashMap<K, V, S>>; + + /// # Safety + /// + /// The index must not be out of bounds. + unsafe fn _yield_write_shard(&'a self, i: usize) -> RwLockWriteGuard<'a, HashMap<K, V, S>>; + + fn _insert(&self, key: K, value: V) -> Option<V>; + + fn _remove<Q>(&self, key: &Q) -> Option<(K, V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized; + + fn _remove_if<Q>(&self, key: &Q, f: impl FnOnce(&K, &V) -> bool) -> Option<(K, V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized; + + fn _iter(&'a self) -> Iter<'a, K, V, S, Self> + where + Self: Sized; + + fn _iter_mut(&'a self) -> IterMut<'a, K, V, S, Self> + where + Self: Sized; + + fn _get<Q>(&'a self, key: &Q) -> Option<Ref<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized; + + fn _get_mut<Q>(&'a self, key: &Q) -> Option<RefMut<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized; + + fn _shrink_to_fit(&self); + + fn _retain(&self, f: impl FnMut(&K, &mut V) -> bool); + + fn _len(&self) -> usize; + + fn _capacity(&self) -> usize; + + fn _alter<Q>(&self, key: &Q, f: impl FnOnce(&K, V) -> V) + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized; + + fn _alter_all(&self, f: impl FnMut(&K, V) -> V); + + fn _entry(&'a self, key: K) -> Entry<'a, K, V, S>; + + fn _hasher(&self) -> S; + + // provided + fn _clear(&self) { + self._retain(|_, _| false) + } + + fn _contains_key<Q>(&'a self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._get(key).is_some() + } + + fn _is_empty(&self) -> bool { + self._len() == 0 + } +} diff --git a/third_party/rust/dashmap/src/util.rs b/third_party/rust/dashmap/src/util.rs new file mode 100644 index 0000000000..d84e37db9b --- /dev/null +++ b/third_party/rust/dashmap/src/util.rs @@ -0,0 +1,102 @@ +//! This module is full of hackery and dark magic. +//! Either spend a day fixing it and quietly submit a PR or don't mention it to anybody. +use core::cell::UnsafeCell; +use core::{mem, ptr}; + +pub const fn ptr_size_bits() -> usize { + mem::size_of::<usize>() * 8 +} + +pub fn map_in_place_2<T, U, F: FnOnce(U, T) -> T>((k, v): (U, &mut T), f: F) { + unsafe { + // # Safety + // + // If the closure panics, we must abort otherwise we could double drop `T` + let _promote_panic_to_abort = AbortOnPanic; + + ptr::write(v, f(k, ptr::read(v))); + } +} + +/// # Safety +/// +/// Requires that you ensure the reference does not become invalid. +/// The object has to outlive the reference. +pub unsafe fn change_lifetime_const<'a, 'b, T>(x: &'a T) -> &'b T { + &*(x as *const T) +} + +/// # Safety +/// +/// Requires that you ensure the reference does not become invalid. +/// The object has to outlive the reference. +pub unsafe fn change_lifetime_mut<'a, 'b, T>(x: &'a mut T) -> &'b mut T { + &mut *(x as *mut T) +} + +/// A simple wrapper around `T` +/// +/// This is to prevent UB when using `HashMap::get_key_value`, because +/// `HashMap` doesn't expose an api to get the key and value, where +/// the value is a `&mut T`. +/// +/// See [#10](https://github.com/xacrimon/dashmap/issues/10) for details +/// +/// This type is meant to be an implementation detail, but must be exposed due to the `Dashmap::shards` +#[repr(transparent)] +pub struct SharedValue<T> { + value: UnsafeCell<T>, +} + +impl<T: Clone> Clone for SharedValue<T> { + fn clone(&self) -> Self { + let inner = self.get().clone(); + + Self { + value: UnsafeCell::new(inner), + } + } +} + +unsafe impl<T: Send> Send for SharedValue<T> {} + +unsafe impl<T: Sync> Sync for SharedValue<T> {} + +impl<T> SharedValue<T> { + /// Create a new `SharedValue<T>` + pub const fn new(value: T) -> Self { + Self { + value: UnsafeCell::new(value), + } + } + + /// Get a shared reference to `T` + pub fn get(&self) -> &T { + unsafe { &*self.value.get() } + } + + /// Get an unique reference to `T` + pub fn get_mut(&mut self) -> &mut T { + unsafe { &mut *self.value.get() } + } + + /// Unwraps the value + pub fn into_inner(self) -> T { + self.value.into_inner() + } + + /// Get a mutable raw pointer to the underlying value + pub(crate) fn as_ptr(&self) -> *mut T { + self.value.get() + } +} + +struct AbortOnPanic; + +impl Drop for AbortOnPanic { + fn drop(&mut self) { + if std::thread::panicking() { + std::process::abort() + } + } +} |