Import the dashmap crate
Doc: https://docs.google.com/document/d/1nQBHLo9wNRFdcnB6tpjGjZgOXS8OC--AMg7je59A3yY/edit?usp=sharing
Third-Party Import of: https://static.crates.io/crates/dashmap/dashmap-5.5.3.crate
Request Document: go/android3p
For CL Reviewers: go/android3p#cl-review
For Build Team: go/ab-third-party-imports
Bug: http://b/328273370
Test: m libdashmap dashmap_test_src_lib
Change-Id: I1e5af9a86aa1c3aabf99be8387e8ea774ef2db49
diff --git a/Android.bp b/Android.bp
new file mode 100644
index 0000000..e510112
--- /dev/null
+++ b/Android.bp
@@ -0,0 +1,48 @@
+// This file is generated by cargo_embargo.
+// Do not modify this file as changes will be overridden on upgrade.
+
+// TODO: Add license.
+rust_test {
+ name: "dashmap_test_src_lib",
+ host_supported: true,
+ crate_name: "dashmap",
+ cargo_env_compat: true,
+ cargo_pkg_version: "5.5.3",
+ srcs: ["src/lib.rs"],
+ test_suites: ["general-tests"],
+ auto_gen_config: true,
+ test_options: {
+ unit_test: true,
+ },
+ edition: "2018",
+ rustlibs: [
+ "libcfg_if",
+ "libhashbrown",
+ "liblock_api",
+ "libonce_cell",
+ "libparking_lot_core",
+ ],
+}
+
+rust_library {
+ name: "libdashmap",
+ host_supported: true,
+ crate_name: "dashmap",
+ cargo_env_compat: true,
+ cargo_pkg_version: "5.5.3",
+ srcs: ["src/lib.rs"],
+ edition: "2018",
+ rustlibs: [
+ "libcfg_if",
+ "libhashbrown",
+ "liblock_api",
+ "libonce_cell",
+ "libparking_lot_core",
+ ],
+ apex_available: [
+ "//apex_available:platform",
+ "//apex_available:anyapex",
+ ],
+ product_available: true,
+ vendor_available: true,
+}
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..cb7480b
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,73 @@
+# 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.65"
+name = "dashmap"
+version = "5.5.3"
+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.arbitrary]
+version = "1.3.0"
+optional = true
+
+[dependencies.cfg-if]
+version = "1.0.0"
+
+[dependencies.hashbrown]
+version = "0.14.0"
+default-features = false
+
+[dependencies.lock_api]
+version = "0.4.10"
+
+[dependencies.once_cell]
+version = "1.18.0"
+
+[dependencies.parking_lot_core]
+version = "0.9.8"
+
+[dependencies.rayon]
+version = "1.7.0"
+optional = true
+
+[dependencies.serde]
+version = "1.0.188"
+features = ["derive"]
+optional = true
+
+[features]
+inline = ["hashbrown/inline-more"]
+raw-api = []
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..602ea9c
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,31 @@
+[package]
+name = "dashmap"
+version = "5.5.3"
+authors = ["Acrimon <joel.wejdenstal@gmail.com>"]
+edition = "2018"
+rust-version = "1.65"
+license = "MIT"
+repository = "https://github.com/xacrimon/dashmap"
+homepage = "https://github.com/xacrimon/dashmap"
+description = "Blazing fast concurrent HashMap for Rust."
+readme = "README.md"
+documentation = "https://docs.rs/dashmap"
+keywords = ["atomic", "concurrent", "hashmap"]
+categories = ["concurrency", "algorithms", "data-structures"]
+
+[features]
+raw-api = []
+inline = ["hashbrown/inline-more"]
+
+[dependencies]
+lock_api = "0.4.10"
+parking_lot_core = "0.9.8"
+hashbrown = { version = "0.14.0", default-features = false }
+serde = { version = "1.0.188", optional = true, features = ["derive"] }
+cfg-if = "1.0.0"
+rayon = { version = "1.7.0", optional = true }
+once_cell = "1.18.0"
+arbitrary = { version = "1.3.0", optional = true }
+
+[package.metadata.docs.rs]
+features = ["rayon", "raw-api", "serde"]
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..5a8b9ef
--- /dev/null
+++ b/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/METADATA b/METADATA
new file mode 100644
index 0000000..e63fbc9
--- /dev/null
+++ b/METADATA
@@ -0,0 +1,20 @@
+name: "dashmap"
+description: "Blazing fast concurrent HashMap for Rust."
+third_party {
+ identifier {
+ type: "crates.io"
+ value: "dashmap"
+ }
+ identifier {
+ type: "Archive"
+ value: "https://static.crates.io/crates/dashmap/dashmap-5.5.3.crate"
+ primary_source: true
+ }
+ version: "5.5.3"
+ license_type: NOTICE
+ last_upgrade_date {
+ year: 2024
+ month: 3
+ day: 6
+ }
+}
diff --git a/MODULE_LICENSE_MIT b/MODULE_LICENSE_MIT
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/MODULE_LICENSE_MIT
diff --git a/OWNERS b/OWNERS
new file mode 100644
index 0000000..5a2b844
--- /dev/null
+++ b/OWNERS
@@ -0,0 +1 @@
+include platform/prebuilts/rust:main:/OWNERS
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..2eb721e
--- /dev/null
+++ b/README.md
@@ -0,0 +1,67 @@
+# 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.
+
+- `inline` - Enables `inline-more` feature from the `hashbrown` crate. Can lead to better performance, but with the cost of longer compile-time.
+
+- `arbitrary` - Enables support for the `arbitrary` crate.
+
+## 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/cargo_embargo.json b/cargo_embargo.json
new file mode 100644
index 0000000..c8842d1
--- /dev/null
+++ b/cargo_embargo.json
@@ -0,0 +1,4 @@
+{
+ "run_cargo": false,
+ "tests": true
+}
diff --git a/rust-toolchain.toml b/rust-toolchain.toml
new file mode 100644
index 0000000..a32876a
--- /dev/null
+++ b/rust-toolchain.toml
@@ -0,0 +1,4 @@
+[toolchain]
+channel = "1.65"
+components = ["rustfmt", "clippy"]
+profile = "minimal"
diff --git a/src/arbitrary.rs b/src/arbitrary.rs
new file mode 100644
index 0000000..a760964
--- /dev/null
+++ b/src/arbitrary.rs
@@ -0,0 +1,13 @@
+use arbitrary::{Arbitrary, Unstructured};
+use core::hash::BuildHasher;
+
+impl<'a, K, V, S> Arbitrary<'a> for crate::DashMap<K, V, S>
+where
+ K: Eq + std::hash::Hash + Arbitrary<'a>,
+ V: Arbitrary<'a>,
+ S: Default + BuildHasher + Clone,
+{
+ fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
+ u.arbitrary_iter()?.collect()
+ }
+}
diff --git a/src/iter.rs b/src/iter.rs
new file mode 100644
index 0000000..ce50e73
--- /dev/null
+++ b/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<'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/src/iter_set.rs b/src/iter_set.rs
new file mode 100644
index 0000000..619a5b5
--- /dev/null
+++ b/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/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..34e5d8b
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,1465 @@
+#![allow(clippy::type_complexity)]
+
+#[cfg(feature = "arbitrary")]
+mod arbitrary;
+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 read_only;
+ 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};
+use once_cell::sync::OnceCell;
+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>;
+
+// Temporary reimplementation of [`std::collections::TryReserveError`]
+// util [`std::collections::TryReserveError`] stabilises.
+// We cannot easily create `std::collections` error type from `hashbrown` error type
+// without access to `TryReserveError::kind` method.
+#[non_exhaustive]
+#[derive(Clone, PartialEq, Eq, Debug)]
+pub struct TryReserveError {}
+
+fn default_shard_amount() -> usize {
+ static DEFAULT_SHARD_AMOUNT: OnceCell<usize> = OnceCell::new();
+ *DEFAULT_SHARD_AMOUNT.get_or_init(|| {
+ (std::thread::available_parallelism().map_or(1, usize::from) * 4).next_power_of_two()
+ })
+}
+
+fn ncb(shard_amount: usize) -> usize {
+ 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 this, 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 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 be greater than 0 and a power of two.
+ /// If a shard_amount which is not a power of two is provided, the function will panic.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// 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 > 1);
+ 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
+ }
+
+ /// Provides mutable access to 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;
+ /// use dashmap::SharedValue;
+ ///
+ /// let mut map = DashMap::<i32, &'static str>::new();
+ /// let shard_ind = map.determine_map(&42);
+ /// map.shards_mut()[shard_ind].get_mut().insert(42, SharedValue::new("forty two"));
+ /// assert_eq!(*map.get(&42).unwrap(), "forty two");
+ /// ```
+ pub fn shards_mut(&mut self) -> &mut [RwLock<HashMap<K, V, S>>] {
+ &mut self.shards
+ }
+
+ /// Consumes this `DashMap` and returns the inner shards.
+ /// You should probably not use this unless you know what you are doing.
+ ///
+ /// Requires the `raw-api` feature to be enabled.
+ ///
+ /// See [`DashMap::shards()`] and [`DashMap::shards_mut()`] for more information.
+ pub fn into_shards(self) -> Box<[RwLock<HashMap<K, V, S>>]> {
+ self.shards
+ }
+ } else {
+ #[allow(dead_code)]
+ pub(crate) fn shards(&self) -> &[RwLock<HashMap<K, V, S>>] {
+ &self.shards
+ }
+
+ #[allow(dead_code)]
+ pub(crate) fn shards_mut(&mut self) -> &mut [RwLock<HashMap<K, V, S>>] {
+ &mut self.shards
+ }
+
+ #[allow(dead_code)]
+ pub(crate) fn into_shards(self) -> Box<[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 an 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)
+ }
+
+ /// Advanced entry API that tries to mimic `std::collections::HashMap::try_reserve`.
+ /// Tries to reserve capacity for at least `shard * additional`
+ /// and may reserve more space to avoid frequent reallocations.
+ ///
+ /// # Errors
+ ///
+ /// If the capacity overflows, or the allocator reports a failure, then an error is returned.
+ // TODO: return std::collections::TryReserveError once std::collections::TryReserveErrorKind stabilises.
+ pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
+ for shard in self.shards.iter() {
+ shard
+ .write()
+ .try_reserve(additional)
+ .map_err(|_| TryReserveError {})?;
+ }
+ Ok(())
+ }
+}
+
+impl<'a, K: 'a + Eq + Hash, V: 'a, S: 'a + BuildHasher + Clone> Map<'a, K, V, S>
+ 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<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());
+ }
+ }
+
+ #[test]
+ fn test_try_reserve() {
+ let mut map: DashMap<i32, i32> = DashMap::new();
+ // DashMap is empty and doesn't allocate memory
+ assert_eq!(map.capacity(), 0);
+
+ map.try_reserve(10).unwrap();
+
+ // And now map can hold at least 10 elements
+ assert!(map.capacity() >= 10);
+ }
+
+ #[test]
+ fn test_try_reserve_errors() {
+ let mut map: DashMap<i32, i32> = DashMap::new();
+
+ match map.try_reserve(usize::MAX) {
+ Err(_) => {}
+ _ => panic!("should have raised CapacityOverflow error"),
+ }
+ }
+}
diff --git a/src/lock.rs b/src/lock.rs
new file mode 100644
index 0000000..f2c98c7
--- /dev/null
+++ b/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/src/mapref/entry.rs b/src/mapref/entry.rs
new file mode 100644
index 0000000..e9e6b91
--- /dev/null
+++ b/src/mapref/entry.rs
@@ -0,0 +1,278 @@
+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()?)),
+ }
+ }
+
+ /// Sets the value of the entry, and returns a reference to the inserted value.
+ pub fn insert(self, value: V) -> RefMut<'a, K, V, S> {
+ match self {
+ Entry::Occupied(mut entry) => {
+ entry.insert(value);
+ entry.into_ref()
+ }
+ Entry::Vacant(entry) => entry.insert(value),
+ }
+ }
+
+ /// Sets the value of the entry, and returns an OccupiedEntry.
+ ///
+ /// If you are not interested in the occupied entry,
+ /// consider [`insert`] as it doesn't need to clone the key.
+ ///
+ /// [`insert`]: Entry::insert
+ pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S>
+ where
+ K: Clone,
+ {
+ match self {
+ Entry::Occupied(mut entry) => {
+ entry.insert(value);
+ entry
+ }
+ Entry::Vacant(entry) => entry.insert_entry(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
+ }
+ }
+
+ /// Sets the value of the entry with the VacantEntry’s key, and returns an OccupiedEntry.
+ pub fn insert_entry(mut self, value: V) -> OccupiedEntry<'a, K, V, S>
+ where
+ K: Clone,
+ {
+ unsafe {
+ self.shard.insert(self.key.clone(), SharedValue::new(value));
+
+ let (k, v) = self.shard.get_key_value(&self.key).unwrap();
+
+ let kptr: *const K = k;
+ let vptr: *mut V = v.as_ptr();
+ OccupiedEntry::new(self.shard, self.key, (kptr, vptr))
+ }
+ }
+
+ 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())
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::DashMap;
+
+ use super::*;
+
+ #[test]
+ fn test_insert_entry_into_vacant() {
+ let map: DashMap<u32, u32> = DashMap::new();
+
+ let entry = map.entry(1);
+
+ assert!(matches!(entry, Entry::Vacant(_)));
+
+ let entry = entry.insert_entry(2);
+
+ assert_eq!(*entry.get(), 2);
+
+ drop(entry);
+
+ assert_eq!(*map.get(&1).unwrap(), 2);
+ }
+
+ #[test]
+ fn test_insert_entry_into_occupied() {
+ let map: DashMap<u32, u32> = DashMap::new();
+
+ map.insert(1, 1000);
+
+ let entry = map.entry(1);
+
+ assert!(matches!(&entry, Entry::Occupied(entry) if *entry.get() == 1000));
+
+ let entry = entry.insert_entry(2);
+
+ assert_eq!(*entry.get(), 2);
+
+ drop(entry);
+
+ assert_eq!(*map.get(&1).unwrap(), 2);
+ }
+}
diff --git a/src/mapref/mod.rs b/src/mapref/mod.rs
new file mode 100644
index 0000000..8897547
--- /dev/null
+++ b/src/mapref/mod.rs
@@ -0,0 +1,3 @@
+pub mod entry;
+pub mod multiple;
+pub mod one;
diff --git a/src/mapref/multiple.rs b/src/mapref/multiple.rs
new file mode 100644
index 0000000..53a8a7e
--- /dev/null
+++ b/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/src/mapref/one.rs b/src/mapref/one.rs
new file mode 100644
index 0000000..fd38530
--- /dev/null
+++ b/src/mapref/one.rs
@@ -0,0 +1,335 @@
+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()
+ }
+}
+
+impl<'a, K: Eq + Hash, V, T: std::fmt::Display> std::fmt::Display for MappedRef<'a, K, V, T> {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ std::fmt::Display::fmt(self.value(), f)
+ }
+}
+
+impl<'a, K: Eq + Hash, V, T: AsRef<TDeref>, TDeref: ?Sized> AsRef<TDeref>
+ for MappedRef<'a, K, V, T>
+{
+ fn as_ref(&self) -> &TDeref {
+ self.value().as_ref()
+ }
+}
+
+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/src/rayon/map.rs b/src/rayon/map.rs
new file mode 100644
index 0000000..ab45e61
--- /dev/null
+++ b/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> {
+ pub(super) 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> {
+ pub(super) 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<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/src/rayon/read_only.rs b/src/rayon/read_only.rs
new file mode 100644
index 0000000..a11448c
--- /dev/null
+++ b/src/rayon/read_only.rs
@@ -0,0 +1,96 @@
+use crate::mapref::multiple::RefMulti;
+use crate::rayon::map::Iter;
+use crate::ReadOnlyView;
+use core::hash::{BuildHasher, Hash};
+use rayon::iter::IntoParallelIterator;
+
+impl<K, V, S> IntoParallelIterator for ReadOnlyView<K, V, S>
+where
+ K: Send + Eq + Hash,
+ V: Send,
+ S: Send + Clone + BuildHasher,
+{
+ type Iter = super::map::OwningIter<K, V, S>;
+ type Item = (K, V);
+
+ fn into_par_iter(self) -> Self::Iter {
+ super::map::OwningIter {
+ shards: self.map.shards,
+ }
+ }
+}
+
+// This impl also enables `IntoParallelRefIterator::par_iter`
+impl<'a, K, V, S> IntoParallelIterator for &'a ReadOnlyView<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.map.shards,
+ }
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use crate::DashMap;
+ use rayon::iter::{IntoParallelIterator, IntoParallelRefIterator, ParallelIterator};
+
+ 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_par_iter() {
+ let map = construct_sample_map();
+
+ let view = map.clone().into_read_only();
+
+ view.par_iter().for_each(|entry| {
+ let key = *entry.key();
+
+ assert!(view.contains_key(&key));
+
+ let map_entry = map.get(&key).unwrap();
+
+ assert_eq!(view.get(&key).unwrap(), map_entry.value());
+
+ let key_value: (&i32, &String) = view.get_key_value(&key).unwrap();
+
+ assert_eq!(key_value.0, map_entry.key());
+
+ assert_eq!(key_value.1, map_entry.value());
+ });
+ }
+
+ #[test]
+ fn test_into_par_iter() {
+ let map = construct_sample_map();
+
+ let view = map.clone().into_read_only();
+
+ view.into_par_iter().for_each(|(key, value)| {
+ let map_entry = map.get(&key).unwrap();
+
+ assert_eq!(&key, map_entry.key());
+
+ assert_eq!(&value, map_entry.value());
+ });
+ }
+}
diff --git a/src/rayon/set.rs b/src/rayon/set.rs
new file mode 100644
index 0000000..11c06cc
--- /dev/null
+++ b/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/src/read_only.rs b/src/read_only.rs
new file mode 100644
index 0000000..42ee443
--- /dev/null
+++ b/src/read_only.rs
@@ -0,0 +1,271 @@
+use crate::lock::RwLock;
+use crate::t::Map;
+use crate::{DashMap, HashMap};
+use cfg_if::cfg_if;
+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> {
+ pub(crate) 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_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().into_read_only();
+ /// println!("Amount of shards: {}", map.shards().len());
+ /// ```
+ pub fn shards(&self) -> &[RwLock<HashMap<K, V, S>>] {
+ &self.map.shards
+ }
+ } else {
+ #[allow(dead_code)]
+ pub(crate) fn shards(&self) -> &[RwLock<HashMap<K, V, S>>] {
+ &self.map.shards
+ }
+ }
+ }
+}
+
+#[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/src/serde.rs b/src/serde.rs
new file mode 100644
index 0000000..6abeb06
--- /dev/null
+++ b/src/serde.rs
@@ -0,0 +1,215 @@
+use crate::{mapref, setref, 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()
+ }
+}
+
+macro_rules! serialize_impl {
+ () => {
+ fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
+ where
+ Ser: serde::Serializer,
+ {
+ std::ops::Deref::deref(self).serialize(serializer)
+ }
+ };
+}
+
+// Map
+impl<'a, K: Eq + Hash, V: Serialize, S: BuildHasher> Serialize
+ for mapref::multiple::RefMulti<'a, K, V, S>
+{
+ serialize_impl! {}
+}
+
+impl<'a, K: Eq + Hash, V: Serialize, S: BuildHasher> Serialize
+ for mapref::multiple::RefMutMulti<'a, K, V, S>
+{
+ serialize_impl! {}
+}
+
+impl<'a, K: Eq + Hash, V: Serialize, S: BuildHasher> Serialize for mapref::one::Ref<'a, K, V, S> {
+ serialize_impl! {}
+}
+
+impl<'a, K: Eq + Hash, V: Serialize, S: BuildHasher> Serialize
+ for mapref::one::RefMut<'a, K, V, S>
+{
+ serialize_impl! {}
+}
+
+impl<'a, K: Eq + Hash, V, T: Serialize, S: BuildHasher> Serialize
+ for mapref::one::MappedRef<'a, K, V, T, S>
+{
+ serialize_impl! {}
+}
+
+impl<'a, K: Eq + Hash, V, T: Serialize, S: BuildHasher> Serialize
+ for mapref::one::MappedRefMut<'a, K, V, T, S>
+{
+ serialize_impl! {}
+}
+
+// Set
+impl<'a, V: Hash + Eq + Serialize, S: BuildHasher> Serialize
+ for setref::multiple::RefMulti<'a, V, S>
+{
+ serialize_impl! {}
+}
+
+impl<'a, V: Hash + Eq + Serialize, S: BuildHasher> Serialize for setref::one::Ref<'a, V, S> {
+ serialize_impl! {}
+}
diff --git a/src/set.rs b/src/set.rs
new file mode 100644
index 0000000..1a56177
--- /dev/null
+++ b/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<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/src/setref/mod.rs b/src/setref/mod.rs
new file mode 100644
index 0000000..95ae8f4
--- /dev/null
+++ b/src/setref/mod.rs
@@ -0,0 +1,2 @@
+pub mod multiple;
+pub mod one;
diff --git a/src/setref/multiple.rs b/src/setref/multiple.rs
new file mode 100644
index 0000000..21e7ed4
--- /dev/null
+++ b/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/src/setref/one.rs b/src/setref/one.rs
new file mode 100644
index 0000000..0787187
--- /dev/null
+++ b/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/src/t.rs b/src/t.rs
new file mode 100644
index 0000000..5e1fedc
--- /dev/null
+++ b/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/src/try_result.rs b/src/try_result.rs
new file mode 100644
index 0000000..aa93d3b
--- /dev/null
+++ b/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/src/util.rs b/src/util.rs
new file mode 100644
index 0000000..d84e37d
--- /dev/null
+++ b/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()
+ }
+ }
+}
