From 20431706a863f92cb37dc512fef6e48d192aaf2c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:11:38 +0200 Subject: Merging upstream version 1.66.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/dashmap/src/lib.rs | 59 +++++++++++++++++++-- vendor/dashmap/src/rayon/map.rs | 4 +- vendor/dashmap/src/rayon/read_only.rs | 96 +++++++++++++++++++++++++++++++++++ vendor/dashmap/src/read_only.rs | 2 +- vendor/dashmap/src/table.rs | 81 ----------------------------- 5 files changed, 155 insertions(+), 87 deletions(-) create mode 100644 vendor/dashmap/src/rayon/read_only.rs delete mode 100644 vendor/dashmap/src/table.rs (limited to 'vendor/dashmap/src') diff --git a/vendor/dashmap/src/lib.rs b/vendor/dashmap/src/lib.rs index 627b51381..bf112d570 100644 --- a/vendor/dashmap/src/lib.rs +++ b/vendor/dashmap/src/lib.rs @@ -16,6 +16,7 @@ mod util; #[cfg(feature = "rayon")] pub mod rayon { pub mod map; + pub mod read_only; pub mod set; } @@ -35,6 +36,7 @@ use iter::{Iter, IterMut, OwningIter}; use mapref::entry::{Entry, OccupiedEntry, VacantEntry}; use mapref::multiple::RefMulti; use mapref::one::{Ref, RefMut}; +use once_cell::sync::OnceCell; pub use read_only::ReadOnlyView; pub use set::DashSet; use std::collections::hash_map::RandomState; @@ -51,8 +53,19 @@ cfg_if! { pub(crate) type HashMap = hashbrown::HashMap, S>; +// Temporary reimplementation of [`std::collections::TryReserveError`] +// util [`std::collections::TryReserveError`] stabilises. +// We cannot easily create `std::collections` error type from `hashbrown` error type +// without access to `TryReserveError::kind` method. +#[non_exhaustive] +#[derive(Clone, PartialEq, Eq, Debug)] +pub struct TryReserveError {} + fn default_shard_amount() -> usize { - (std::thread::available_parallelism().map_or(1, usize::from) * 4).next_power_of_two() + static DEFAULT_SHARD_AMOUNT: OnceCell = OnceCell::new(); + *DEFAULT_SHARD_AMOUNT.get_or_init(|| { + (std::thread::available_parallelism().map_or(1, usize::from) * 4).next_power_of_two() + }) } fn ncb(shard_amount: usize) -> usize { @@ -65,7 +78,7 @@ fn ncb(shard_amount: usize) -> usize { /// with some slight changes to handle concurrency. /// /// DashMap tries to be very simple to use and to be a direct replacement for `RwLock>`. -/// To accomplish these all methods take `&self` instead modifying methods taking `&mut self`. +/// To accomplish this, all methods take `&self` instead of modifying methods taking `&mut self`. /// This allows you to put a DashMap in an `Arc` and share it between threads while being able to modify it. /// /// Documentation mentioning locking behaviour acts in the reference frame of the calling thread. @@ -216,7 +229,7 @@ impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone> DashMap { /// Creates a new DashMap with a specified hasher and shard amount /// - /// shard_amount should greater than 0 and be a power of two. + /// shard_amount should be greater than 0 and a power of two. /// If a shard_amount which is not a power of two is provided, the function will panic. /// /// # Examples @@ -797,6 +810,24 @@ impl<'a, K: 'a + Eq + Hash, V: 'a, S: BuildHasher + Clone> DashMap { pub fn try_entry(&'a self, key: K) -> Option> { self._try_entry(key) } + + /// Advanced entry API that tries to mimic `std::collections::HashMap::try_reserve`. + /// Tries to reserve capacity for at least `shard * additional` + /// and may reserve more space to avoid frequent reallocations. + /// + /// # Errors + /// + /// If the capacity overflows, or the allocator reports a failure, then an error is returned. + // TODO: return std::collections::TryReserveError once std::collections::TryReserveErrorKind stabilises. + pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + for shard in self.shards.iter() { + shard + .write() + .try_reserve(additional) + .map_err(|_| TryReserveError {})?; + } + Ok(()) + } } impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher + Clone> Map<'a, K, V, S> @@ -1367,4 +1398,26 @@ mod tests { assert!(result2.is_locked()); } } + + #[test] + fn test_try_reserve() { + let mut map: DashMap = DashMap::new(); + // DashMap is empty and doesn't allocate memory + assert_eq!(map.capacity(), 0); + + map.try_reserve(10).unwrap(); + + // And now map can hold at least 10 elements + assert!(map.capacity() >= 10); + } + + #[test] + fn test_try_reserve_errors() { + let mut map: DashMap = DashMap::new(); + + match map.try_reserve(usize::MAX) { + Err(_) => {} + _ => panic!("should have raised CapacityOverflow error"), + } + } } diff --git a/vendor/dashmap/src/rayon/map.rs b/vendor/dashmap/src/rayon/map.rs index c0947cf6b..4fc0c43aa 100644 --- a/vendor/dashmap/src/rayon/map.rs +++ b/vendor/dashmap/src/rayon/map.rs @@ -80,7 +80,7 @@ where } pub struct OwningIter { - shards: Box<[RwLock>]>, + pub(super) shards: Box<[RwLock>]>, } impl ParallelIterator for OwningIter @@ -125,7 +125,7 @@ where } pub struct Iter<'a, K, V, S = RandomState> { - shards: &'a [RwLock>], + pub(super) shards: &'a [RwLock>], } impl<'a, K, V, S> ParallelIterator for Iter<'a, K, V, S> diff --git a/vendor/dashmap/src/rayon/read_only.rs b/vendor/dashmap/src/rayon/read_only.rs new file mode 100644 index 000000000..a11448cee --- /dev/null +++ b/vendor/dashmap/src/rayon/read_only.rs @@ -0,0 +1,96 @@ +use crate::mapref::multiple::RefMulti; +use crate::rayon::map::Iter; +use crate::ReadOnlyView; +use core::hash::{BuildHasher, Hash}; +use rayon::iter::IntoParallelIterator; + +impl IntoParallelIterator for ReadOnlyView +where + K: Send + Eq + Hash, + V: Send, + S: Send + Clone + BuildHasher, +{ + type Iter = super::map::OwningIter; + type Item = (K, V); + + fn into_par_iter(self) -> Self::Iter { + super::map::OwningIter { + shards: self.map.shards, + } + } +} + +// This impl also enables `IntoParallelRefIterator::par_iter` +impl<'a, K, V, S> IntoParallelIterator for &'a ReadOnlyView +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.map.shards, + } + } +} + +#[cfg(test)] +mod tests { + use crate::DashMap; + use rayon::iter::{IntoParallelIterator, IntoParallelRefIterator, ParallelIterator}; + + fn construct_sample_map() -> DashMap { + 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_par_iter() { + let map = construct_sample_map(); + + let view = map.clone().into_read_only(); + + view.par_iter().for_each(|entry| { + let key = *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_into_par_iter() { + let map = construct_sample_map(); + + let view = map.clone().into_read_only(); + + view.into_par_iter().for_each(|(key, value)| { + let map_entry = map.get(&key).unwrap(); + + assert_eq!(&key, map_entry.key()); + + assert_eq!(&value, map_entry.value()); + }); + } +} diff --git a/vendor/dashmap/src/read_only.rs b/vendor/dashmap/src/read_only.rs index c43947b2e..14582245b 100644 --- a/vendor/dashmap/src/read_only.rs +++ b/vendor/dashmap/src/read_only.rs @@ -7,7 +7,7 @@ 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 { - map: DashMap, + pub(crate) map: DashMap, } impl Clone for ReadOnlyView { diff --git a/vendor/dashmap/src/table.rs b/vendor/dashmap/src/table.rs deleted file mode 100644 index 03acd76e2..000000000 --- a/vendor/dashmap/src/table.rs +++ /dev/null @@ -1,81 +0,0 @@ -use super::u128::AtomicU128; -use std::borrow::Borrow; -use std::cell::UnsafeCell; -use std::hash::{BuildHasher, Hash, Hasher}; -use std::mem::MaybeUninit; -use std::sync::atomic::{AtomicU64, Ordering}; -use std::sync::{Arc, Mutex}; - -const TOMBSTONE_BIT: u64 = 1 << 63; -const ALLOCATED_BIT: u64 = 1 << 62; -const POINTER_MASK: u64 = 0x3FFFFFFFFFFFFFFF; - -fn hash(hasher: &S, key: &K) -> u64 -where - S: BuildHasher, - K: Hash, -{ - let mut hasher = hasher.build_hasher(); - key.hash(&mut hasher); - hasher.finish() -} - -struct Slot { - data: AtomicU64, - pair: UnsafeCell>, -} - -pub struct Table { - hash: Arc, - slots: Box<[Slot]>, - mask: usize, -} - -impl Table -where - K: Eq + Hash, - S: BuildHasher, -{ - pub fn new(hasher: Arc, capacity: usize) -> Self { - debug_assert!(capacity.is_power_of_two()); - let slots = (0..capacity) - .map(|_| Slot { - data: AtomicU64::new(0), - pair: UnsafeCell::new(MaybeUninit::uninit()), - }) - .collect::>(); - - Table { - hash: hasher, - slots: slots.into_boxed_slice(), - mask: capacity - 1, - } - } - - pub fn get(&self, key: &Q) -> Option<*mut (K, V)> - where - K: Borrow, - Q: Eq + Hash, - { - let hash = hash(&*self.hash, key); - let mut idx = hash as usize & self.mask; - let mut i = 0; - - loop { - let slot = &self.slots[idx]; - let data = slot.data.load(Ordering::Relaxed); - let ptr = (data & POINTER_MASK) as *mut (K, V); - if !ptr.is_null() { - let stored = unsafe { (*ptr).0.borrow() }; - if stored == key { - return Some(ptr); - } - } else if data & TOMBSTONE_BIT != TOMBSTONE_BIT || i > self.mask { - return None; - } - - idx = (idx + 1) & self.mask; - i += 1; - } - } -} -- cgit v1.2.3