diff options
Diffstat (limited to 'vendor/dashmap')
25 files changed, 4432 insertions, 0 deletions
diff --git a/vendor/dashmap/.cargo-checksum.json b/vendor/dashmap/.cargo-checksum.json new file mode 100644 index 000000000..7d0daa971 --- /dev/null +++ b/vendor/dashmap/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"8f8a0060b2a6f95a4ba3f009e49a4f0a4c26ea5ba7fb02388ca5466d97c6ccfe","LICENSE":"16692e8cee4aa06e3913787497eba2d47c42002014136f5da67be6ee640e28a3","README.md":"e1114aed5dfbd2892f2d81881c46f8e17b9b4774344ad3feb55bd2c1a41384fd","rust-toolchain":"06dc4c395690e7d6ff8b92d8d265a8cf1c02cbca414e15352072e378fcb4171a","src/iter.rs":"dec9cc68374a0a176b5840e37da4e83d0493d7dca6f776dc926bf511c84e70db","src/iter_set.rs":"5327da951dc93d30b293aeb7a805666ee4b8e6364881348ab5d86b23c29a0e13","src/lib.rs":"ad0b2651810d4d286f11ce4effb800920eb4100ae6676f6141126e5488358007","src/lock.rs":"22b1013ee3cbd1598c26403552faf8e5b44fe98a8ff4c8812da15d57bdeee4b3","src/mapref/entry.rs":"ddcf788856330a4384ce987bb84ff36b494675b3b1f2460ae48376ac664491df","src/mapref/mod.rs":"15bd45cfc642a9e3e77bbfbf2d9fad9c5fac0ff6904214a3c501e262242ec8b0","src/mapref/multiple.rs":"17a87879229d78f75d71817d100aa0a210d764d6b66e4a05b17a3e092d17e306","src/mapref/one.rs":"ea46339e08c5033cf419c195e922e1ba6f606fc71c15ee31d1b3c38cfedfedcf","src/rayon/map.rs":"07315c9dd35437fd5e504a07fcbcd77f9ea19c892c32c1d60f27db5a6a26345b","src/rayon/set.rs":"21fe2ca8c58c8ff1bc753f5e2eb6131afd598211eea375f2ac7190cd0f9abcba","src/read_only.rs":"c846f8117800dbbb122bc0552021c5ac4ccfbf464bebe37f4b65e40b19baf260","src/serde.rs":"57bbf2b255de966cc9c54011429495cc5308a1f76906846b29e015f860b79559","src/set.rs":"80271aa0d8a32845afdef5a35f18e5cac6f0f5ab8d2a6b11b02cd123152c91d4","src/setref/mod.rs":"cc39e406a333dc6c04398f4b1336fb400e3a8360c387466d8a91f5d7f4ed40a7","src/setref/multiple.rs":"2270749e83f80dbb4761448f0629ecd02b0b4268f76834236d1167844e6d5e37","src/setref/one.rs":"69738583f2a160f3907e540277ccd88e0036406b3ead66b3d4015ddd938d6937","src/t.rs":"9b40ebfba22369813bf159ed60fa70e742ae72bfaec6aee91a716cba91cb8f0d","src/table.rs":"536a3b5775cbdbe436357c231e54e4e2ee4a5e1849872aa92335271b148845b4","src/try_result.rs":"81d1dd396f70b0aa2a6e1969851b706cbfdfb09c802ac9d33dcace882aa28dd1","src/util.rs":"7a8096a713cf04e60d6c9e38cd366314ed74472abab4bb8a3a9ed081a0e0301b"},"package":"3495912c9c1ccf2e18976439f4443f3fee0fd61f424ff99fde6a66b15ecb448f"}
\ No newline at end of file diff --git a/vendor/dashmap/Cargo.toml b/vendor/dashmap/Cargo.toml new file mode 100644 index 000000000..a03feb0ce --- /dev/null +++ b/vendor/dashmap/Cargo.toml @@ -0,0 +1,51 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2018" +rust-version = "1.59" +name = "dashmap" +version = "5.3.4" +authors = ["Acrimon <joel.wejdenstal@gmail.com>"] +description = "Blazing fast concurrent HashMap for Rust." +homepage = "https://github.com/xacrimon/dashmap" +documentation = "https://docs.rs/dashmap" +readme = "README.md" +keywords = ["atomic", "concurrent", "hashmap"] +categories = ["concurrency", "algorithms", "data-structures"] +license = "MIT" +repository = "https://github.com/xacrimon/dashmap" +[package.metadata.docs.rs] +features = ["rayon", "raw-api", "serde"] +[dependencies.cfg-if] +version = "1.0.0" + +[dependencies.hashbrown] +version = "0.12.0" +default-features = false + +[dependencies.lock_api] +version = "0.4.7" + +[dependencies.parking_lot_core] +version = "0.9.3" + +[dependencies.rayon] +version = "1.5.2" +optional = true + +[dependencies.serde] +version = "1.0.136" +features = ["derive"] +optional = true + +[features] +raw-api = [] diff --git a/vendor/dashmap/LICENSE b/vendor/dashmap/LICENSE new file mode 100644 index 000000000..5a8b9ef86 --- /dev/null +++ b/vendor/dashmap/LICENSE @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2019 Acrimon + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/vendor/dashmap/README.md b/vendor/dashmap/README.md new file mode 100644 index 000000000..580480f20 --- /dev/null +++ b/vendor/dashmap/README.md @@ -0,0 +1,63 @@ +# DashMap + +Blazingly fast concurrent map in Rust. + +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>>`. +To accomplish these goals, all methods take `&self` instead of modifying methods taking `&mut self`. +This allows you to put a DashMap in an `Arc<T>` and share it between threads while still being able to modify it. + +DashMap puts great effort into performance and aims to be as fast as possible. +If you have any suggestions or tips do not hesitate to open an issue or a PR. + +[](https://crates.io/crates/dashmap) + +[](https://docs.rs/dashmap) + +[](https://crates.io/crates/dashmap) + +[](https://crates.io/crates/dashmap) + +## Cargo features + +- `serde` - Enables serde support. + +- `raw-api` - Enables the unstable raw-shard api. + +- `rayon` - Enables rayon support. + +## Contributing + +DashMap gladly accepts contributions! +Do not hesitate to open issues or PR's. + +I will take a look as soon as I have time for it. + +That said I do not get paid (yet) to work on open-source. This means +that my time is limited and my work here comes after my personal life. + +## Performance + +A comprehensive benchmark suite including DashMap can be found [here](https://github.com/xacrimon/conc-map-bench). + +## Special thanks + +- [Jon Gjengset](https://github.com/jonhoo) + +- [Yato](https://github.com/RustyYato) + +- [Karl Bergström](https://github.com/kabergstrom) + +- [Dylan DPC](https://github.com/Dylan-DPC) + +- [Lokathor](https://github.com/Lokathor) + +- [namibj](https://github.com/namibj) + +## License + +This project is licensed under MIT. diff --git a/vendor/dashmap/rust-toolchain b/vendor/dashmap/rust-toolchain new file mode 100644 index 000000000..62d03d54d --- /dev/null +++ b/vendor/dashmap/rust-toolchain @@ -0,0 +1,4 @@ +[toolchain] +channel = "1.59" +components = [ "rustfmt", "clippy" ] +profile = "minimal" diff --git a/vendor/dashmap/src/iter.rs b/vendor/dashmap/src/iter.rs new file mode 100644 index 000000000..cc2f12ea8 --- /dev/null +++ b/vendor/dashmap/src/iter.rs @@ -0,0 +1,315 @@ +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 hashbrown::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>>, +} + +impl<'a, 'i, K: Clone + Hash + Eq, V: Clone, S: Clone + BuildHasher> Clone for Iter<'i, K, V, S> { + fn clone(&self) -> Self { + Iter::new(self.map) + } +} + +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 unsafe { 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/vendor/dashmap/src/iter_set.rs b/vendor/dashmap/src/iter_set.rs new file mode 100644 index 000000000..619a5b500 --- /dev/null +++ b/vendor/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/vendor/dashmap/src/lib.rs b/vendor/dashmap/src/lib.rs new file mode 100644 index 000000000..627b51381 --- /dev/null +++ b/vendor/dashmap/src/lib.rs @@ -0,0 +1,1370 @@ +#![allow(clippy::type_complexity)] + +pub mod iter; +pub mod iter_set; +mod lock; +pub mod mapref; +mod read_only; +#[cfg(feature = "serde")] +mod serde; +mod set; +pub mod setref; +mod t; +pub mod try_result; +mod util; + +#[cfg(feature = "rayon")] +pub mod rayon { + pub mod map; + pub mod set; +} + +#[cfg(not(feature = "raw-api"))] +use crate::lock::{RwLock, RwLockReadGuard, RwLockWriteGuard}; + +#[cfg(feature = "raw-api")] +pub use crate::lock::{RawRwLock, RwLock, RwLockReadGuard, RwLockWriteGuard}; + +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 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; +use try_result::TryResult; + +cfg_if! { + if #[cfg(feature = "raw-api")] { + pub use util::SharedValue; + } else { + use util::SharedValue; + } +} + +pub(crate) type HashMap<K, V, S> = hashbrown::HashMap<K, SharedValue<V>, S>; + +fn default_shard_amount() -> usize { + (std::thread::available_parallelism().map_or(1, usize::from) * 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()) + } + + /// Creates a new DashMap with a specified shard amount + /// + /// shard_amount should greater than 0 and be a power of two. + /// If a shard_amount which is not a power of two is provided, the function will panic. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let mappings = DashMap::with_shard_amount(32); + /// mappings.insert(2, 4); + /// mappings.insert(8, 16); + /// ``` + pub fn with_shard_amount(shard_amount: usize) -> Self { + Self::with_capacity_and_hasher_and_shard_amount(0, RandomState::default(), shard_amount) + } + + /// Creates a new DashMap with a specified capacity and shard amount. + /// + /// shard_amount should greater than 0 and be a power of two. + /// If a shard_amount which is not a power of two is provided, the function will panic. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// + /// let mappings = DashMap::with_capacity_and_shard_amount(32, 32); + /// mappings.insert(2, 4); + /// mappings.insert(8, 16); + /// ``` + pub fn with_capacity_and_shard_amount(capacity: usize, shard_amount: usize) -> Self { + Self::with_capacity_and_hasher_and_shard_amount( + capacity, + RandomState::default(), + shard_amount, + ) + } +} + +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(capacity: usize, hasher: S) -> Self { + Self::with_capacity_and_hasher_and_shard_amount(capacity, hasher, default_shard_amount()) + } + + /// Creates a new DashMap with a specified hasher and shard amount + /// + /// shard_amount should greater than 0 and be a power of two. + /// If a shard_amount which is not a power of two is provided, the function will panic. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let mappings = DashMap::with_hasher_and_shard_amount(s, 32); + /// mappings.insert(2, 4); + /// mappings.insert(8, 16); + /// ``` + pub fn with_hasher_and_shard_amount(hasher: S, shard_amount: usize) -> Self { + Self::with_capacity_and_hasher_and_shard_amount(0, hasher, shard_amount) + } + + /// Creates a new DashMap with a specified starting capacity, hasher and shard_amount. + /// + /// shard_amount should greater than 0 and be a power of two. + /// If a shard_amount which is not a power of two is provided, the function will panic. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// use std::collections::hash_map::RandomState; + /// + /// let s = RandomState::new(); + /// let mappings = DashMap::with_capacity_and_hasher_and_shard_amount(2, s, 32); + /// mappings.insert(2, 4); + /// mappings.insert(8, 16); + /// ``` + pub fn with_capacity_and_hasher_and_shard_amount( + mut capacity: usize, + hasher: S, + shard_amount: usize, + ) -> Self { + assert!(shard_amount > 0); + assert!(shard_amount.is_power_of_two()); + + 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) + } + + pub fn remove_if_mut<Q>(&self, key: &Q, f: impl FnOnce(&K, &mut V) -> bool) -> Option<(K, V)> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._remove_if_mut(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) + } + + /// Get an immutable reference to an entry in the map, if the shard is not locked. + /// If the shard is locked, the function will return [TryResult::Locked]. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// use dashmap::try_result::TryResult; + /// + /// let map = DashMap::new(); + /// map.insert("Johnny", 21); + /// + /// assert_eq!(*map.try_get("Johnny").unwrap(), 21); + /// + /// let _result1_locking = map.get_mut("Johnny"); + /// + /// let result2 = map.try_get("Johnny"); + /// assert!(result2.is_locked()); + /// ``` + pub fn try_get<Q>(&'a self, key: &Q) -> TryResult<Ref<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._try_get(key) + } + + /// Get a mutable reference to an entry in the map, if the shard is not locked. + /// If the shard is locked, the function will return [TryResult::Locked]. + /// + /// # Examples + /// + /// ``` + /// use dashmap::DashMap; + /// use dashmap::try_result::TryResult; + /// + /// let map = DashMap::new(); + /// map.insert("Johnny", 21); + /// + /// *map.try_get_mut("Johnny").unwrap() += 1; + /// assert_eq!(*map.get("Johnny").unwrap(), 22); + /// + /// let _result1_locking = map.get("Johnny"); + /// + /// let result2 = map.try_get_mut("Johnny"); + /// assert!(result2.is_locked()); + /// ``` + pub fn try_get_mut<Q>(&'a self, key: &Q) -> TryResult<RefMut<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._try_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); + } + + /// Scoped access into an item of 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 warehouse = DashMap::new(); + /// warehouse.insert(4267, ("Banana", 100)); + /// warehouse.insert(2359, ("Pear", 120)); + /// let fruit = warehouse.view(&4267, |_k, v| *v); + /// assert_eq!(fruit, Some(("Banana", 100))); + /// ``` + /// + /// # Panics + /// + /// If the given closure panics, then `view` will abort the process + pub fn view<Q, R>(&self, key: &Q, f: impl FnOnce(&K, &V) -> R) -> Option<R> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self._view(key, 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) + } + + /// Advanced entry API that tries to mimic `std::collections::HashMap`. + /// See the documentation on `dashmap::mapref::entry` for more details. + /// + /// Returns None if the shard is currently locked. + pub fn try_entry(&'a self, key: K) -> Option<Entry<'a, K, V, S>> { + self._try_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).data_ptr() + } + + 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() + } + + unsafe fn _try_yield_read_shard( + &'a self, + i: usize, + ) -> Option<RwLockReadGuard<'a, HashMap<K, V, S>>> { + debug_assert!(i < self.shards.len()); + + self.shards.get_unchecked(i).try_read() + } + + unsafe fn _try_yield_write_shard( + &'a self, + i: usize, + ) -> Option<RwLockWriteGuard<'a, HashMap<K, V, S>>> { + debug_assert!(i < self.shards.len()); + + self.shards.get_unchecked(i).try_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((kptr, vptr)) = shard.get_key_value(key) { + unsafe { + let kptr: *const K = kptr; + let vptr: *mut V = vptr.as_ptr(); + + if f(&*kptr, &mut *vptr) { + shard.remove_entry(key).map(|(k, v)| (k, v.into_inner())) + } else { + None + } + } + } else { + None + } + } + + fn _remove_if_mut<Q>(&self, key: &Q, f: impl FnOnce(&K, &mut 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((kptr, vptr)) = shard.get_key_value(key) { + unsafe { + let kptr: *const K = kptr; + let vptr: *mut V = vptr.as_ptr(); + + if f(&*kptr, &mut *vptr) { + 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: *const K = kptr; + let vptr: *const V = vptr.get(); + Some(Ref::new(shard, kptr, vptr)) + } + } 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: *const K = kptr; + let vptr: *mut V = vptr.as_ptr(); + Some(RefMut::new(shard, kptr, vptr)) + } + } else { + None + } + } + + fn _try_get<Q>(&'a self, key: &Q) -> TryResult<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 = match unsafe { self._try_yield_read_shard(idx) } { + Some(shard) => shard, + None => return TryResult::Locked, + }; + + if let Some((kptr, vptr)) = shard.get_key_value(key) { + unsafe { + let kptr: *const K = kptr; + let vptr: *const V = vptr.get(); + TryResult::Present(Ref::new(shard, kptr, vptr)) + } + } else { + TryResult::Absent + } + } + + fn _try_get_mut<Q>(&'a self, key: &Q) -> TryResult<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 = match unsafe { self._try_yield_write_shard(idx) } { + Some(shard) => shard, + None => return TryResult::Locked, + }; + + if let Some((kptr, vptr)) = shard.get_key_value(key) { + unsafe { + let kptr: *const K = kptr; + let vptr: *mut V = vptr.as_ptr(); + TryResult::Present(RefMut::new(shard, kptr, vptr)) + } + } else { + TryResult::Absent + } + } + + 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 _view<Q, R>(&self, key: &Q, f: impl FnOnce(&K, &V) -> R) -> Option<R> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized, + { + self.get(key).map(|r| { + let (k, v) = r.pair(); + f(k, v) + }) + } + + 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: *const K = kptr; + let vptr: *mut V = vptr.as_ptr(); + Entry::Occupied(OccupiedEntry::new(shard, key, (kptr, vptr))) + } + } else { + unsafe { Entry::Vacant(VacantEntry::new(shard, key)) } + } + } + + fn _try_entry(&'a self, key: K) -> Option<Entry<'a, K, V, S>> { + let hash = self.hash_usize(&key); + + let idx = self.determine_shard(hash); + + let shard = match unsafe { self._try_yield_write_shard(idx) } { + Some(shard) => shard, + None => return None, + }; + + if let Some((kptr, vptr)) = shard.get_key_value(&key) { + unsafe { + let kptr: *const K = kptr; + let vptr: *mut V = vptr.as_ptr(); + + Some(Entry::Occupied(OccupiedEntry::new( + shard, + key, + (kptr, vptr), + ))) + } + } else { + unsafe { Some(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, S: BuildHasher + Clone + Default> FromIterator<(K, V)> for DashMap<K, V, S> { + fn from_iter<I: IntoIterator<Item = (K, V)>>(intoiter: I) -> Self { + let mut map = DashMap::default(); + + 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()); + } + } + + #[test] + fn test_map_view() { + let dm = DashMap::new(); + + let vegetables: [String; 4] = [ + "Salad".to_string(), + "Beans".to_string(), + "Potato".to_string(), + "Tomato".to_string(), + ]; + + // Give it some values + dm.insert(0, "Banana".to_string()); + dm.insert(4, "Pear".to_string()); + dm.insert(9, "Potato".to_string()); + dm.insert(12, "Chicken".to_string()); + + let potato_vegetableness = dm.view(&9, |_, v| vegetables.contains(v)); + assert_eq!(potato_vegetableness, Some(true)); + + let chicken_vegetableness = dm.view(&12, |_, v| vegetables.contains(v)); + assert_eq!(chicken_vegetableness, Some(false)); + + let not_in_map = dm.view(&30, |_k, _v| false); + assert_eq!(not_in_map, None); + } + + #[test] + fn test_try_get() { + { + let map = DashMap::new(); + map.insert("Johnny", 21); + + assert_eq!(*map.try_get("Johnny").unwrap(), 21); + + let _result1_locking = map.get_mut("Johnny"); + + let result2 = map.try_get("Johnny"); + assert!(result2.is_locked()); + } + + { + let map = DashMap::new(); + map.insert("Johnny", 21); + + *map.try_get_mut("Johnny").unwrap() += 1; + assert_eq!(*map.get("Johnny").unwrap(), 22); + + let _result1_locking = map.get("Johnny"); + + let result2 = map.try_get_mut("Johnny"); + assert!(result2.is_locked()); + } + } +} diff --git a/vendor/dashmap/src/lock.rs b/vendor/dashmap/src/lock.rs new file mode 100644 index 000000000..f2c98c765 --- /dev/null +++ b/vendor/dashmap/src/lock.rs @@ -0,0 +1,300 @@ +use core::sync::atomic::{AtomicUsize, Ordering}; +use parking_lot_core::{ParkToken, SpinWait, UnparkToken}; + +pub type RwLock<T> = lock_api::RwLock<RawRwLock, T>; +pub type RwLockReadGuard<'a, T> = lock_api::RwLockReadGuard<'a, RawRwLock, T>; +pub type RwLockWriteGuard<'a, T> = lock_api::RwLockWriteGuard<'a, RawRwLock, T>; + +const READERS_PARKED: usize = 0b0001; +const WRITERS_PARKED: usize = 0b0010; +const ONE_READER: usize = 0b0100; +const ONE_WRITER: usize = !(READERS_PARKED | WRITERS_PARKED); + +pub struct RawRwLock { + state: AtomicUsize, +} + +unsafe impl lock_api::RawRwLock for RawRwLock { + #[allow(clippy::declare_interior_mutable_const)] + const INIT: Self = Self { + state: AtomicUsize::new(0), + }; + + type GuardMarker = lock_api::GuardNoSend; + + #[inline] + fn try_lock_exclusive(&self) -> bool { + self.state + .compare_exchange(0, ONE_WRITER, Ordering::Acquire, Ordering::Relaxed) + .is_ok() + } + + #[inline] + fn lock_exclusive(&self) { + if self + .state + .compare_exchange_weak(0, ONE_WRITER, Ordering::Acquire, Ordering::Relaxed) + .is_err() + { + self.lock_exclusive_slow(); + } + } + + #[inline] + unsafe fn unlock_exclusive(&self) { + if self + .state + .compare_exchange(ONE_WRITER, 0, Ordering::Release, Ordering::Relaxed) + .is_err() + { + self.unlock_exclusive_slow(); + } + } + + #[inline] + fn try_lock_shared(&self) -> bool { + self.try_lock_shared_fast() || self.try_lock_shared_slow() + } + + #[inline] + fn lock_shared(&self) { + if !self.try_lock_shared_fast() { + self.lock_shared_slow(); + } + } + + #[inline] + unsafe fn unlock_shared(&self) { + let state = self.state.fetch_sub(ONE_READER, Ordering::Release); + + if state == (ONE_READER | WRITERS_PARKED) { + self.unlock_shared_slow(); + } + } +} + +unsafe impl lock_api::RawRwLockDowngrade for RawRwLock { + #[inline] + unsafe fn downgrade(&self) { + let state = self + .state + .fetch_and(ONE_READER | WRITERS_PARKED, Ordering::Release); + if state & READERS_PARKED != 0 { + parking_lot_core::unpark_all((self as *const _ as usize) + 1, UnparkToken(0)); + } + } +} + +impl RawRwLock { + #[cold] + fn lock_exclusive_slow(&self) { + let mut acquire_with = 0; + loop { + let mut spin = SpinWait::new(); + let mut state = self.state.load(Ordering::Relaxed); + + loop { + while state & ONE_WRITER == 0 { + match self.state.compare_exchange_weak( + state, + state | ONE_WRITER | acquire_with, + Ordering::Acquire, + Ordering::Relaxed, + ) { + Ok(_) => return, + Err(e) => state = e, + } + } + + if state & WRITERS_PARKED == 0 { + if spin.spin() { + state = self.state.load(Ordering::Relaxed); + continue; + } + + if let Err(e) = self.state.compare_exchange_weak( + state, + state | WRITERS_PARKED, + Ordering::Relaxed, + Ordering::Relaxed, + ) { + state = e; + continue; + } + } + + let _ = unsafe { + parking_lot_core::park( + self as *const _ as usize, + || { + let state = self.state.load(Ordering::Relaxed); + (state & ONE_WRITER != 0) && (state & WRITERS_PARKED != 0) + }, + || {}, + |_, _| {}, + ParkToken(0), + None, + ) + }; + + acquire_with = WRITERS_PARKED; + break; + } + } + } + + #[cold] + fn unlock_exclusive_slow(&self) { + let state = self.state.load(Ordering::Relaxed); + assert_eq!(state & ONE_WRITER, ONE_WRITER); + + let mut parked = state & (READERS_PARKED | WRITERS_PARKED); + assert_ne!(parked, 0); + + if parked != (READERS_PARKED | WRITERS_PARKED) { + if let Err(new_state) = + self.state + .compare_exchange(state, 0, Ordering::Release, Ordering::Relaxed) + { + assert_eq!(new_state, ONE_WRITER | READERS_PARKED | WRITERS_PARKED); + parked = READERS_PARKED | WRITERS_PARKED; + } + } + + if parked == (READERS_PARKED | WRITERS_PARKED) { + self.state.store(WRITERS_PARKED, Ordering::Release); + parked = READERS_PARKED; + } + + if parked == READERS_PARKED { + return unsafe { + parking_lot_core::unpark_all((self as *const _ as usize) + 1, UnparkToken(0)); + }; + } + + assert_eq!(parked, WRITERS_PARKED); + unsafe { + parking_lot_core::unpark_one(self as *const _ as usize, |_| UnparkToken(0)); + } + } + + #[inline(always)] + fn try_lock_shared_fast(&self) -> bool { + let state = self.state.load(Ordering::Relaxed); + + if let Some(new_state) = state.checked_add(ONE_READER) { + if new_state & ONE_WRITER != ONE_WRITER { + return self + .state + .compare_exchange_weak(state, new_state, Ordering::Acquire, Ordering::Relaxed) + .is_ok(); + } + } + + false + } + + #[cold] + fn try_lock_shared_slow(&self) -> bool { + let mut state = self.state.load(Ordering::Relaxed); + + while let Some(new_state) = state.checked_add(ONE_READER) { + if new_state & ONE_WRITER == ONE_WRITER { + break; + } + + match self.state.compare_exchange_weak( + state, + new_state, + Ordering::Acquire, + Ordering::Relaxed, + ) { + Ok(_) => return true, + Err(e) => state = e, + } + } + + false + } + + #[cold] + fn lock_shared_slow(&self) { + loop { + let mut spin = SpinWait::new(); + let mut state = self.state.load(Ordering::Relaxed); + + loop { + let mut backoff = SpinWait::new(); + while let Some(new_state) = state.checked_add(ONE_READER) { + assert_ne!( + new_state & ONE_WRITER, + ONE_WRITER, + "reader count overflowed", + ); + + if self + .state + .compare_exchange_weak( + state, + new_state, + Ordering::Acquire, + Ordering::Relaxed, + ) + .is_ok() + { + return; + } + + backoff.spin_no_yield(); + state = self.state.load(Ordering::Relaxed); + } + + if state & READERS_PARKED == 0 { + if spin.spin() { + state = self.state.load(Ordering::Relaxed); + continue; + } + + if let Err(e) = self.state.compare_exchange_weak( + state, + state | READERS_PARKED, + Ordering::Relaxed, + Ordering::Relaxed, + ) { + state = e; + continue; + } + } + + let _ = unsafe { + parking_lot_core::park( + (self as *const _ as usize) + 1, + || { + let state = self.state.load(Ordering::Relaxed); + (state & ONE_WRITER == ONE_WRITER) && (state & READERS_PARKED != 0) + }, + || {}, + |_, _| {}, + ParkToken(0), + None, + ) + }; + + break; + } + } + } + + #[cold] + fn unlock_shared_slow(&self) { + if self + .state + .compare_exchange(WRITERS_PARKED, 0, Ordering::Relaxed, Ordering::Relaxed) + .is_ok() + { + unsafe { + parking_lot_core::unpark_one(self as *const _ as usize, |_| UnparkToken(0)); + } + } + } +} diff --git a/vendor/dashmap/src/mapref/entry.rs b/vendor/dashmap/src/mapref/entry.rs new file mode 100644 index 000000000..16a42ce77 --- /dev/null +++ b/vendor/dashmap/src/mapref/entry.rs @@ -0,0 +1,189 @@ +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 = RandomState> { + shard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + key: K, +} + +unsafe impl<'a, K: Eq + Hash + Sync, V: Sync, S: BuildHasher> Send for VacantEntry<'a, K, V, S> {} +unsafe impl<'a, K: Eq + Hash + Sync, V: 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) unsafe 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 = RandomState> { + shard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + elem: (*const K, *mut V), + key: K, +} + +unsafe impl<'a, K: Eq + Hash + Sync, V: Sync, S: BuildHasher> Send for OccupiedEntry<'a, K, V, S> {} +unsafe impl<'a, K: Eq + Hash + Sync, V: 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) unsafe fn new( + shard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + key: K, + elem: (*const K, *mut V), + ) -> Self { + Self { shard, elem, key } + } + + pub fn get(&self) -> &V { + unsafe { &*self.elem.1 } + } + + pub fn get_mut(&mut self) -> &mut V { + unsafe { &mut *self.elem.1 } + } + + pub fn insert(&mut self, value: V) -> V { + mem::replace(self.get_mut(), value) + } + + pub fn into_ref(self) -> RefMut<'a, K, V, S> { + unsafe { RefMut::new(self.shard, self.elem.0, self.elem.1) } + } + + pub fn into_key(self) -> K { + self.key + } + + pub fn key(&self) -> &K { + unsafe { &*self.elem.0 } + } + + pub fn remove(mut self) -> V { + let key = unsafe { &*self.elem.0 }; + self.shard.remove(key).unwrap().into_inner() + } + + pub fn remove_entry(mut self) -> (K, V) { + let key = unsafe { &*self.elem.0 }; + let (k, v) = self.shard.remove_entry(key).unwrap(); + (k, v.into_inner()) + } + + pub fn replace_entry(mut self, value: V) -> (K, V) { + let nk = self.key; + let key = unsafe { &*self.elem.0 }; + let (k, v) = self.shard.remove_entry(key).unwrap(); + self.shard.insert(nk, SharedValue::new(value)); + (k, v.into_inner()) + } +} diff --git a/vendor/dashmap/src/mapref/mod.rs b/vendor/dashmap/src/mapref/mod.rs new file mode 100644 index 000000000..8897547e0 --- /dev/null +++ b/vendor/dashmap/src/mapref/mod.rs @@ -0,0 +1,3 @@ +pub mod entry; +pub mod multiple; +pub mod one; diff --git a/vendor/dashmap/src/mapref/multiple.rs b/vendor/dashmap/src/mapref/multiple.rs new file mode 100644 index 000000000..53a8a7e58 --- /dev/null +++ b/vendor/dashmap/src/mapref/multiple.rs @@ -0,0 +1,107 @@ +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; + +pub struct RefMulti<'a, K, V, S = RandomState> { + _guard: Arc<RwLockReadGuard<'a, HashMap<K, V, S>>>, + k: *const K, + v: *const V, +} + +unsafe impl<'a, K: Eq + Hash + Sync, V: Sync, S: BuildHasher> Send for RefMulti<'a, K, V, S> {} +unsafe impl<'a, K: Eq + Hash + Sync, V: 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) unsafe fn new( + guard: Arc<RwLockReadGuard<'a, HashMap<K, V, S>>>, + k: *const K, + v: *const V, + ) -> Self { + Self { + _guard: guard, + k, + v, + } + } + + pub fn key(&self) -> &K { + self.pair().0 + } + + pub fn value(&self) -> &V { + self.pair().1 + } + + pub fn pair(&self) -> (&K, &V) { + unsafe { (&*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() + } +} + +pub struct RefMutMulti<'a, K, V, S = RandomState> { + _guard: Arc<RwLockWriteGuard<'a, HashMap<K, V, S>>>, + k: *const K, + v: *mut V, +} + +unsafe impl<'a, K: Eq + Hash + Sync, V: Sync, S: BuildHasher> Send for RefMutMulti<'a, K, V, S> {} +unsafe impl<'a, K: Eq + Hash + Sync, V: 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) unsafe fn new( + guard: Arc<RwLockWriteGuard<'a, HashMap<K, V, S>>>, + k: *const K, + v: *mut V, + ) -> Self { + Self { + _guard: guard, + k, + v, + } + } + + pub fn key(&self) -> &K { + self.pair().0 + } + + pub fn value(&self) -> &V { + self.pair().1 + } + + pub fn value_mut(&mut self) -> &mut V { + self.pair_mut().1 + } + + pub fn pair(&self) -> (&K, &V) { + unsafe { (&*self.k, &*self.v) } + } + + pub fn pair_mut(&mut self) -> (&K, &mut V) { + unsafe { (&*self.k, &mut *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/vendor/dashmap/src/mapref/one.rs b/vendor/dashmap/src/mapref/one.rs new file mode 100644 index 000000000..835e45cad --- /dev/null +++ b/vendor/dashmap/src/mapref/one.rs @@ -0,0 +1,321 @@ +use crate::lock::{RwLockReadGuard, RwLockWriteGuard}; +use crate::HashMap; +use core::hash::{BuildHasher, Hash}; +use core::ops::{Deref, DerefMut}; +use std::collections::hash_map::RandomState; +use std::fmt::{Debug, Formatter}; + +pub struct Ref<'a, K, V, S = RandomState> { + _guard: RwLockReadGuard<'a, HashMap<K, V, S>>, + k: *const K, + v: *const V, +} + +unsafe impl<'a, K: Eq + Hash + Sync, V: Sync, S: BuildHasher> Send for Ref<'a, K, V, S> {} +unsafe impl<'a, K: Eq + Hash + Sync, V: 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) unsafe fn new( + guard: RwLockReadGuard<'a, HashMap<K, V, S>>, + k: *const K, + v: *const V, + ) -> Self { + Self { + _guard: guard, + k, + v, + } + } + + pub fn key(&self) -> &K { + self.pair().0 + } + + pub fn value(&self) -> &V { + self.pair().1 + } + + pub fn pair(&self) -> (&K, &V) { + unsafe { (&*self.k, &*self.v) } + } + + pub fn map<F, T>(self, f: F) -> MappedRef<'a, K, V, T, S> + where + F: FnOnce(&V) -> &T, + { + MappedRef { + _guard: self._guard, + k: self.k, + v: f(unsafe { &*self.v }), + } + } + + pub fn try_map<F, T>(self, f: F) -> Result<MappedRef<'a, K, V, T, S>, Self> + where + F: FnOnce(&V) -> Option<&T>, + { + if let Some(v) = f(unsafe { &*self.v }) { + Ok(MappedRef { + _guard: self._guard, + k: self.k, + v, + }) + } else { + Err(self) + } + } +} + +impl<'a, K: Eq + Hash + Debug, V: Debug, S: BuildHasher> Debug for Ref<'a, K, V, S> { + fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { + f.debug_struct("Ref") + .field("k", &self.k) + .field("v", &self.v) + .finish() + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> Deref for Ref<'a, K, V, S> { + type Target = V; + + fn deref(&self) -> &V { + self.value() + } +} + +pub struct RefMut<'a, K, V, S = RandomState> { + guard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + k: *const K, + v: *mut V, +} + +unsafe impl<'a, K: Eq + Hash + Sync, V: Sync, S: BuildHasher> Send for RefMut<'a, K, V, S> {} +unsafe impl<'a, K: Eq + Hash + Sync, V: 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) unsafe fn new( + guard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + k: *const K, + v: *mut V, + ) -> Self { + Self { guard, k, v } + } + + pub fn key(&self) -> &K { + self.pair().0 + } + + pub fn value(&self) -> &V { + self.pair().1 + } + + pub fn value_mut(&mut self) -> &mut V { + self.pair_mut().1 + } + + pub fn pair(&self) -> (&K, &V) { + unsafe { (&*self.k, &*self.v) } + } + + pub fn pair_mut(&mut self) -> (&K, &mut V) { + unsafe { (&*self.k, &mut *self.v) } + } + + pub fn downgrade(self) -> Ref<'a, K, V, S> { + unsafe { Ref::new(RwLockWriteGuard::downgrade(self.guard), self.k, self.v) } + } + + pub fn map<F, T>(self, f: F) -> MappedRefMut<'a, K, V, T, S> + where + F: FnOnce(&mut V) -> &mut T, + { + MappedRefMut { + _guard: self.guard, + k: self.k, + v: f(unsafe { &mut *self.v }), + } + } + + pub fn try_map<F, T>(self, f: F) -> Result<MappedRefMut<'a, K, V, T, S>, Self> + where + F: FnOnce(&mut V) -> Option<&mut T>, + { + let v = match f(unsafe { &mut *(self.v as *mut _) }) { + Some(v) => v, + None => return Err(self), + }; + let guard = self.guard; + let k = self.k; + Ok(MappedRefMut { + _guard: guard, + k, + v, + }) + } +} + +impl<'a, K: Eq + Hash + Debug, V: Debug, S: BuildHasher> Debug for RefMut<'a, K, V, S> { + fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { + f.debug_struct("RefMut") + .field("k", &self.k) + .field("v", &self.v) + .finish() + } +} + +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() + } +} + +pub struct MappedRef<'a, K, V, T, S = RandomState> { + _guard: RwLockReadGuard<'a, HashMap<K, V, S>>, + k: *const K, + v: *const T, +} + +impl<'a, K: Eq + Hash, V, T, S: BuildHasher> MappedRef<'a, K, V, T, S> { + pub fn key(&self) -> &K { + self.pair().0 + } + + pub fn value(&self) -> &T { + self.pair().1 + } + + pub fn pair(&self) -> (&K, &T) { + unsafe { (&*self.k, &*self.v) } + } + + pub fn map<F, T2>(self, f: F) -> MappedRef<'a, K, V, T2, S> + where + F: FnOnce(&T) -> &T2, + { + MappedRef { + _guard: self._guard, + k: self.k, + v: f(unsafe { &*self.v }), + } + } + + pub fn try_map<F, T2>(self, f: F) -> Result<MappedRef<'a, K, V, T2, S>, Self> + where + F: FnOnce(&T) -> Option<&T2>, + { + let v = match f(unsafe { &*self.v }) { + Some(v) => v, + None => return Err(self), + }; + let guard = self._guard; + Ok(MappedRef { + _guard: guard, + k: self.k, + v, + }) + } +} + +impl<'a, K: Eq + Hash + Debug, V, T: Debug, S: BuildHasher> Debug for MappedRef<'a, K, V, T, S> { + fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { + f.debug_struct("MappedRef") + .field("k", &self.k) + .field("v", &self.v) + .finish() + } +} + +impl<'a, K: Eq + Hash, V, T, S: BuildHasher> Deref for MappedRef<'a, K, V, T, S> { + type Target = T; + + fn deref(&self) -> &T { + self.value() + } +} + +pub struct MappedRefMut<'a, K, V, T, S = RandomState> { + _guard: RwLockWriteGuard<'a, HashMap<K, V, S>>, + k: *const K, + v: *mut T, +} + +impl<'a, K: Eq + Hash, V, T, S: BuildHasher> MappedRefMut<'a, K, V, T, S> { + pub fn key(&self) -> &K { + self.pair().0 + } + + pub fn value(&self) -> &T { + self.pair().1 + } + + pub fn value_mut(&mut self) -> &mut T { + self.pair_mut().1 + } + + pub fn pair(&self) -> (&K, &T) { + unsafe { (&*self.k, &*self.v) } + } + + pub fn pair_mut(&mut self) -> (&K, &mut T) { + unsafe { (&*self.k, &mut *self.v) } + } + + pub fn map<F, T2>(self, f: F) -> MappedRefMut<'a, K, V, T2, S> + where + F: FnOnce(&mut T) -> &mut T2, + { + MappedRefMut { + _guard: self._guard, + k: self.k, + v: f(unsafe { &mut *self.v }), + } + } + + pub fn try_map<F, T2>(self, f: F) -> Result<MappedRefMut<'a, K, V, T2, S>, Self> + where + F: FnOnce(&mut T) -> Option<&mut T2>, + { + let v = match f(unsafe { &mut *(self.v as *mut _) }) { + Some(v) => v, + None => return Err(self), + }; + let guard = self._guard; + let k = self.k; + Ok(MappedRefMut { + _guard: guard, + k, + v, + }) + } +} + +impl<'a, K: Eq + Hash + Debug, V, T: Debug, S: BuildHasher> Debug for MappedRefMut<'a, K, V, T, S> { + fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { + f.debug_struct("MappedRefMut") + .field("k", &self.k) + .field("v", &self.v) + .finish() + } +} + +impl<'a, K: Eq + Hash, V, T, S: BuildHasher> Deref for MappedRefMut<'a, K, V, T, S> { + type Target = T; + + fn deref(&self) -> &T { + self.value() + } +} + +impl<'a, K: Eq + Hash, V, T, S: BuildHasher> DerefMut for MappedRefMut<'a, K, V, T, S> { + fn deref_mut(&mut self) -> &mut T { + self.value_mut() + } +} diff --git a/vendor/dashmap/src/rayon/map.rs b/vendor/dashmap/src/rayon/map.rs new file mode 100644 index 000000000..c0947cf6b --- /dev/null +++ b/vendor/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); + unsafe { 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); + unsafe { RefMutMulti::new(guard, k, v.get_mut()) } + }) + }) + .drive_unindexed(consumer) + } +} diff --git a/vendor/dashmap/src/rayon/set.rs b/vendor/dashmap/src/rayon/set.rs new file mode 100644 index 000000000..11c06ccbd --- /dev/null +++ b/vendor/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/vendor/dashmap/src/read_only.rs b/vendor/dashmap/src/read_only.rs new file mode 100644 index 000000000..c43947b2e --- /dev/null +++ b/vendor/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/vendor/dashmap/src/serde.rs b/vendor/dashmap/src/serde.rs new file mode 100644 index 000000000..df4fd2e48 --- /dev/null +++ b/vendor/dashmap/src/serde.rs @@ -0,0 +1,158 @@ +use crate::{DashMap, DashSet}; +use core::fmt; +use core::hash::{BuildHasher, 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, S> { + marker: PhantomData<fn() -> DashMap<K, V, S>>, +} + +impl<K, V, S> DashMapVisitor<K, V, S> +where + K: Eq + Hash, + S: BuildHasher + Clone, +{ + fn new() -> Self { + DashMapVisitor { + marker: PhantomData, + } + } +} + +impl<'de, K, V, S> Visitor<'de> for DashMapVisitor<K, V, S> +where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: BuildHasher + Clone + Default, +{ + type Value = DashMap<K, V, S>; + + 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_and_hasher(access.size_hint().unwrap_or(0), Default::default()); + + while let Some((key, value)) = access.next_entry()? { + map.insert(key, value); + } + + Ok(map) + } +} + +impl<'de, K, V, S> Deserialize<'de> for DashMap<K, V, S> +where + K: Deserialize<'de> + Eq + Hash, + V: Deserialize<'de>, + S: BuildHasher + Clone + Default, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + deserializer.deserialize_map(DashMapVisitor::<K, V, S>::new()) + } +} + +impl<K, V, H> Serialize for DashMap<K, V, H> +where + K: Serialize + Eq + Hash, + V: Serialize, + H: BuildHasher + Clone, +{ + 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, S> { + marker: PhantomData<fn() -> DashSet<K, S>>, +} + +impl<K, S> DashSetVisitor<K, S> +where + K: Eq + Hash, + S: BuildHasher + Clone, +{ + fn new() -> Self { + DashSetVisitor { + marker: PhantomData, + } + } +} + +impl<'de, K, S> Visitor<'de> for DashSetVisitor<K, S> +where + K: Deserialize<'de> + Eq + Hash, + S: BuildHasher + Clone + Default, +{ + type Value = DashSet<K, S>; + + 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_and_hasher(access.size_hint().unwrap_or(0), Default::default()); + + while let Some(key) = access.next_element()? { + map.insert(key); + } + + Ok(map) + } +} + +impl<'de, K, S> Deserialize<'de> for DashSet<K, S> +where + K: Deserialize<'de> + Eq + Hash, + S: BuildHasher + Clone + Default, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + deserializer.deserialize_seq(DashSetVisitor::<K, S>::new()) + } +} + +impl<K, H> Serialize for DashSet<K, H> +where + K: Serialize + Eq + Hash, + H: BuildHasher + Clone, +{ + 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/vendor/dashmap/src/set.rs b/vendor/dashmap/src/set.rs new file mode 100644 index 000000000..12445a994 --- /dev/null +++ b/vendor/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, S: BuildHasher + Clone + Default> FromIterator<K> for DashSet<K, S> { + fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self { + let mut set = DashSet::default(); + + 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/vendor/dashmap/src/setref/mod.rs b/vendor/dashmap/src/setref/mod.rs new file mode 100644 index 000000000..95ae8f47f --- /dev/null +++ b/vendor/dashmap/src/setref/mod.rs @@ -0,0 +1,2 @@ +pub mod multiple; +pub mod one; diff --git a/vendor/dashmap/src/setref/multiple.rs b/vendor/dashmap/src/setref/multiple.rs new file mode 100644 index 000000000..21e7ed4a7 --- /dev/null +++ b/vendor/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/vendor/dashmap/src/setref/one.rs b/vendor/dashmap/src/setref/one.rs new file mode 100644 index 000000000..0787187d8 --- /dev/null +++ b/vendor/dashmap/src/setref/one.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 Ref<'a, K, S = RandomState> { + inner: mapref::one::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/vendor/dashmap/src/t.rs b/vendor/dashmap/src/t.rs new file mode 100644 index 000000000..5e1fedccf --- /dev/null +++ b/vendor/dashmap/src/t.rs @@ -0,0 +1,134 @@ +//! 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::try_result::TryResult; +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>>; + + /// # Safety + /// + /// The index must not be out of bounds. + unsafe fn _try_yield_read_shard( + &'a self, + i: usize, + ) -> Option<RwLockReadGuard<'a, HashMap<K, V, S>>>; + + /// # Safety + /// + /// The index must not be out of bounds. + unsafe fn _try_yield_write_shard( + &'a self, + i: usize, + ) -> Option<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 _remove_if_mut<Q>(&self, key: &Q, f: impl FnOnce(&K, &mut 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 _try_get<Q>(&'a self, key: &Q) -> TryResult<Ref<'a, K, V, S>> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized; + + fn _try_get_mut<Q>(&'a self, key: &Q) -> TryResult<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 _view<Q, R>(&self, key: &Q, f: impl FnOnce(&K, &V) -> R) -> Option<R> + where + K: Borrow<Q>, + Q: Hash + Eq + ?Sized; + + fn _entry(&'a self, key: K) -> Entry<'a, K, V, S>; + + fn _try_entry(&'a self, key: K) -> Option<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/vendor/dashmap/src/table.rs b/vendor/dashmap/src/table.rs new file mode 100644 index 000000000..03acd76e2 --- /dev/null +++ b/vendor/dashmap/src/table.rs @@ -0,0 +1,81 @@ +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<S, K>(hasher: &S, key: &K) -> u64 +where + S: BuildHasher, + K: Hash, +{ + let mut hasher = hasher.build_hasher(); + key.hash(&mut hasher); + hasher.finish() +} + +struct Slot<K, V> { + data: AtomicU64, + pair: UnsafeCell<MaybeUninit<(K, V)>>, +} + +pub struct Table<K, V, S> { + hash: Arc<S>, + slots: Box<[Slot<K, V>]>, + mask: usize, +} + +impl<K, V, S> Table<K, V, S> +where + K: Eq + Hash, + S: BuildHasher, +{ + pub fn new(hasher: Arc<S>, 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::<Vec<_>>(); + + Table { + hash: hasher, + slots: slots.into_boxed_slice(), + mask: capacity - 1, + } + } + + pub fn get<Q>(&self, key: &Q) -> Option<*mut (K, V)> + where + K: Borrow<Q>, + 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; + } + } +} diff --git a/vendor/dashmap/src/try_result.rs b/vendor/dashmap/src/try_result.rs new file mode 100644 index 000000000..aa93d3b2c --- /dev/null +++ b/vendor/dashmap/src/try_result.rs @@ -0,0 +1,46 @@ +/// Represents the result of a non-blocking read from a [DashMap](crate::DashMap). +#[derive(Debug)] +pub enum TryResult<R> { + /// The value was present in the map, and the lock for the shard was successfully obtained. + Present(R), + /// The shard wasn't locked, and the value wasn't present in the map. + Absent, + /// The shard was locked. + Locked, +} + +impl<R> TryResult<R> { + /// Returns `true` if the value was present in the map, and the lock for the shard was successfully obtained. + pub fn is_present(&self) -> bool { + matches!(self, TryResult::Present(_)) + } + + /// Returns `true` if the shard wasn't locked, and the value wasn't present in the map. + pub fn is_absent(&self) -> bool { + matches!(self, TryResult::Absent) + } + + /// Returns `true` if the shard was locked. + pub fn is_locked(&self) -> bool { + matches!(self, TryResult::Locked) + } + + /// If `self` is [Present](TryResult::Present), returns the reference to the value in the map. + /// Panics if `self` is not [Present](TryResult::Present). + pub fn unwrap(self) -> R { + match self { + TryResult::Present(r) => r, + TryResult::Locked => panic!("Called unwrap() on TryResult::Locked"), + TryResult::Absent => panic!("Called unwrap() on TryResult::Absent"), + } + } + + /// If `self` is [Present](TryResult::Present), returns the reference to the value in the map. + /// If `self` is not [Present](TryResult::Present), returns `None`. + pub fn try_unwrap(self) -> Option<R> { + match self { + TryResult::Present(r) => Some(r), + _ => None, + } + } +} diff --git a/vendor/dashmap/src/util.rs b/vendor/dashmap/src/util.rs new file mode 100644 index 000000000..d84e37db9 --- /dev/null +++ b/vendor/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() + } + } +} |