Updating hashbrown crate am: 18967b9e40 am: 65783bf1b0 am: 4773b3a582
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/hashbrown/+/2163166
Change-Id: I9731cae6e99fe02d2fc4339e371358f9faed06a0
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 112a41c..7e8a5bb 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,6 +1,6 @@
{
"git": {
- "sha1": "fe06a93d7cba6241e636696fbf5634d8b3e65bb0"
+ "sha1": "1d2c1a81d1b53285decbd64410a21a90112613d7"
},
"path_in_vcs": ""
}
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index 03c21e3..9a78fe9 100644
--- a/Android.bp
+++ b/Android.bp
@@ -37,92 +37,25 @@
],
}
-rust_test {
- name: "hashbrown_test_src_lib",
- host_supported: true,
- crate_name: "hashbrown",
- cargo_env_compat: true,
- cargo_pkg_version: "0.12.1",
- srcs: ["src/lib.rs"],
- test_suites: ["general-tests"],
- auto_gen_config: true,
- test_options: {
- unit_test: true,
- },
- edition: "2021",
- features: [
- "ahash",
- "default",
- "inline-more",
- ],
- rustlibs: [
- "libahash",
- "libfnv",
- "liblazy_static",
- "librand",
- "librayon",
- "libserde_test",
- ],
-}
-
-rust_defaults {
- name: "hashbrown_test_defaults",
- crate_name: "hashbrown",
- cargo_env_compat: true,
- cargo_pkg_version: "0.12.1",
- test_suites: ["general-tests"],
- auto_gen_config: true,
- edition: "2021",
- features: [
- "ahash",
- "default",
- "inline-more",
- ],
- rustlibs: [
- "libahash",
- "libfnv",
- "libhashbrown",
- "liblazy_static",
- "librand",
- "librayon",
- "libserde_test",
- ],
-}
-
-rust_test {
- name: "hashbrown_test_tests_hasher",
- defaults: ["hashbrown_test_defaults"],
- host_supported: true,
- srcs: ["tests/hasher.rs"],
- test_options: {
- unit_test: true,
- },
-}
-
-rust_test {
- name: "hashbrown_test_tests_set",
- defaults: ["hashbrown_test_defaults"],
- host_supported: true,
- srcs: ["tests/set.rs"],
- test_options: {
- unit_test: true,
- },
-}
-
rust_library {
name: "libhashbrown",
host_supported: true,
crate_name: "hashbrown",
cargo_env_compat: true,
- cargo_pkg_version: "0.12.1",
+ cargo_pkg_version: "0.12.3",
srcs: ["src/lib.rs"],
edition: "2021",
features: [
"ahash",
"default",
"inline-more",
+ "raw",
],
rustlibs: [
"libahash",
],
+ apex_available: [
+ "//apex_available:platform",
+ "//apex_available:anyapex",
+ ],
}
diff --git a/CHANGELOG.md b/CHANGELOG.md
index ac1bb4b..3354b54 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,7 +7,26 @@
## [Unreleased]
-## [v0.12.0] - 2022-05-02
+## [v0.12.3] - 2022-07-17
+
+## Fixed
+
+- Fixed double-drop in `RawTable::clone_from`. (#348)
+
+## [v0.12.2] - 2022-07-09
+
+## Added
+
+- Added `Entry` API for `HashSet`. (#342)
+- Added `Extend<&'a (K, V)> for HashMap<K, V, S, A>`. (#340)
+- Added length-based short-circuiting for hash table iteration. (#338)
+- Added a function to access the `RawTable` of a `HashMap`. (#335)
+
+## Changed
+
+- Edited `do_alloc` to reduce LLVM IR generated. (#341)
+
+## [v0.12.1] - 2022-05-02
## Fixed
@@ -344,7 +363,9 @@
- Initial release
-[Unreleased]: https://github.com/rust-lang/hashbrown/compare/v0.12.1...HEAD
+[Unreleased]: https://github.com/rust-lang/hashbrown/compare/v0.12.3...HEAD
+[v0.12.3]: https://github.com/rust-lang/hashbrown/compare/v0.12.2...v0.12.3
+[v0.12.2]: https://github.com/rust-lang/hashbrown/compare/v0.12.1...v0.12.2
[v0.12.1]: https://github.com/rust-lang/hashbrown/compare/v0.12.0...v0.12.1
[v0.12.0]: https://github.com/rust-lang/hashbrown/compare/v0.11.2...v0.12.0
[v0.11.2]: https://github.com/rust-lang/hashbrown/compare/v0.11.1...v0.11.2
diff --git a/Cargo.toml b/Cargo.toml
index 6bc1ff4..fb130d2 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,9 +11,9 @@
[package]
edition = "2021"
-rust-version = "1.56.1"
+rust-version = "1.56.0"
name = "hashbrown"
-version = "0.12.1"
+version = "0.12.3"
authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
exclude = [
".github",
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 2a6b180..7c1625e 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
[package]
name = "hashbrown"
-version = "0.12.1"
+version = "0.12.3"
authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
description = "A Rust port of Google's SwissTable hash map"
license = "MIT OR Apache-2.0"
@@ -10,7 +10,7 @@
categories = ["data-structures", "no-std"]
exclude = [".github", "/ci/*"]
edition = "2021"
-rust-version = "1.56.1"
+rust-version = "1.56.0"
[dependencies]
# For the default hasher
diff --git a/METADATA b/METADATA
index 4410ede..ac50a7a 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/hashbrown/hashbrown-0.12.1.crate"
+ value: "https://static.crates.io/crates/hashbrown/hashbrown-0.12.3.crate"
}
- version: "0.12.1"
+ version: "0.12.3"
license_type: NOTICE
last_upgrade_date {
year: 2022
month: 7
- day: 5
+ day: 25
}
}
diff --git a/cargo2android.json b/cargo2android.json
index 41494dc..ee68753 100644
--- a/cargo2android.json
+++ b/cargo2android.json
@@ -1,6 +1,5 @@
{
"device": true,
- "patch": "patches/Android.bp.patch",
- "run": true,
- "tests": true
-}
+ "features": "ahash,default,inline-more,raw",
+ "run": true
+}
\ No newline at end of file
diff --git a/src/macros.rs b/src/macros.rs
index 4de6b5a..f8ef917 100644
--- a/src/macros.rs
+++ b/src/macros.rs
@@ -1,4 +1,5 @@
// See the cfg-if crate.
+#[allow(unused_macro_rules)]
macro_rules! cfg_if {
// match if/else chains with a final `else`
($(
diff --git a/src/map.rs b/src/map.rs
index 98324b5..a5d3ccb 100644
--- a/src/map.rs
+++ b/src/map.rs
@@ -300,6 +300,8 @@
/// ```
/// use hashbrown::HashMap;
/// let mut map: HashMap<&str, i32> = HashMap::new();
+ /// assert_eq!(map.len(), 0);
+ /// assert_eq!(map.capacity(), 0);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn new() -> Self {
@@ -316,6 +318,8 @@
/// ```
/// use hashbrown::HashMap;
/// let mut map: HashMap<&str, i32> = HashMap::with_capacity(10);
+ /// assert_eq!(map.len(), 0);
+ /// assert!(map.capacity() >= 10);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn with_capacity(capacity: usize) -> Self {
@@ -348,7 +352,8 @@
/// Creates an empty `HashMap` which will use the given hash builder to hash
/// keys.
///
- /// The created map has the default initial capacity.
+ /// The hash map is initially created with a capacity of 0, so it will not
+ /// allocate until it is first inserted into.
///
/// Warning: `hash_builder` is normally randomly generated, and
/// is designed to allow HashMaps to be resistant to attacks that
@@ -366,10 +371,13 @@
///
/// let s = DefaultHashBuilder::default();
/// let mut map = HashMap::with_hasher(s);
+ /// assert_eq!(map.len(), 0);
+ /// assert_eq!(map.capacity(), 0);
+ ///
/// map.insert(1, 2);
/// ```
///
- /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
+ /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
#[cfg_attr(feature = "inline-more", inline)]
pub const fn with_hasher(hash_builder: S) -> Self {
Self {
@@ -400,10 +408,13 @@
///
/// let s = DefaultHashBuilder::default();
/// let mut map = HashMap::with_capacity_and_hasher(10, s);
+ /// assert_eq!(map.len(), 0);
+ /// assert!(map.capacity() >= 10);
+ ///
/// map.insert(1, 2);
/// ```
///
- /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
+ /// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
#[cfg_attr(feature = "inline-more", inline)]
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
Self {
@@ -506,6 +517,7 @@
/// ```
/// use hashbrown::HashMap;
/// let map: HashMap<i32, i32> = HashMap::with_capacity(100);
+ /// assert_eq!(map.len(), 0);
/// assert!(map.capacity() >= 100);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
@@ -525,10 +537,20 @@
/// map.insert("a", 1);
/// map.insert("b", 2);
/// map.insert("c", 3);
+ /// assert_eq!(map.len(), 3);
+ /// let mut vec: Vec<&str> = Vec::new();
///
/// for key in map.keys() {
/// println!("{}", key);
+ /// vec.push(*key);
/// }
+ ///
+ /// // The `Keys` iterator produces keys in arbitrary order, so the
+ /// // keys must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, ["a", "b", "c"]);
+ ///
+ /// assert_eq!(map.len(), 3);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn keys(&self) -> Keys<'_, K, V> {
@@ -547,10 +569,20 @@
/// map.insert("a", 1);
/// map.insert("b", 2);
/// map.insert("c", 3);
+ /// assert_eq!(map.len(), 3);
+ /// let mut vec: Vec<i32> = Vec::new();
///
/// for val in map.values() {
/// println!("{}", val);
+ /// vec.push(*val);
/// }
+ ///
+ /// // The `Values` iterator produces values in arbitrary order, so the
+ /// // values must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [1, 2, 3]);
+ ///
+ /// assert_eq!(map.len(), 3);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn values(&self) -> Values<'_, K, V> {
@@ -575,9 +607,20 @@
/// *val = *val + 10;
/// }
///
+ /// assert_eq!(map.len(), 3);
+ /// let mut vec: Vec<i32> = Vec::new();
+ ///
/// for val in map.values() {
/// println!("{}", val);
+ /// vec.push(*val);
/// }
+ ///
+ /// // The `Values` iterator produces values in arbitrary order, so the
+ /// // values must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [11, 12, 13]);
+ ///
+ /// assert_eq!(map.len(), 3);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
@@ -598,10 +641,20 @@
/// map.insert("a", 1);
/// map.insert("b", 2);
/// map.insert("c", 3);
+ /// assert_eq!(map.len(), 3);
+ /// let mut vec: Vec<(&str, i32)> = Vec::new();
///
/// for (key, val) in map.iter() {
/// println!("key: {} val: {}", key, val);
+ /// vec.push((*key, *val));
/// }
+ ///
+ /// // The `Iter` iterator produces items in arbitrary order, so the
+ /// // items must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [("a", 1), ("b", 2), ("c", 3)]);
+ ///
+ /// assert_eq!(map.len(), 3);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter(&self) -> Iter<'_, K, V> {
@@ -633,9 +686,20 @@
/// *val *= 2;
/// }
///
+ /// assert_eq!(map.len(), 3);
+ /// let mut vec: Vec<(&str, i32)> = Vec::new();
+ ///
/// for (key, val) in &map {
/// println!("key: {} val: {}", key, val);
+ /// vec.push((*key, *val));
/// }
+ ///
+ /// // The `Iter` iterator produces items in arbitrary order, so the
+ /// // items must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [("a", 2), ("b", 4), ("c", 6)]);
+ ///
+ /// assert_eq!(map.len(), 3);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
@@ -691,6 +755,10 @@
/// Clears the map, returning all key-value pairs as an iterator. Keeps the
/// allocated memory for reuse.
///
+ /// If the returned iterator is dropped before being fully consumed, it
+ /// drops the remaining key-value pairs. The returned iterator keeps a
+ /// mutable borrow on the vector to optimize its implementation.
+ ///
/// # Examples
///
/// ```
@@ -699,12 +767,27 @@
/// let mut a = HashMap::new();
/// a.insert(1, "a");
/// a.insert(2, "b");
+ /// let capacity_before_drain = a.capacity();
///
/// for (k, v) in a.drain().take(1) {
/// assert!(k == 1 || k == 2);
/// assert!(v == "a" || v == "b");
/// }
///
+ /// // As we can see, the map is empty and contains no element.
+ /// assert!(a.is_empty() && a.len() == 0);
+ /// // But map capacity is equal to old one.
+ /// assert_eq!(a.capacity(), capacity_before_drain);
+ ///
+ /// let mut a = HashMap::new();
+ /// a.insert(1, "a");
+ /// a.insert(2, "b");
+ ///
+ /// { // Iterator is dropped without being consumed.
+ /// let d = a.drain();
+ /// }
+ ///
+ /// // But the map is empty even if we do not use Drain iterator.
/// assert!(a.is_empty());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
@@ -714,9 +797,11 @@
}
}
- /// Retains only the elements specified by the predicate.
+ /// Retains only the elements specified by the predicate. Keeps the
+ /// allocated memory for reuse.
///
- /// In other words, remove all pairs `(k, v)` such that `f(&k,&mut v)` returns `false`.
+ /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.
+ /// The elements are visited in unsorted (and unspecified) order.
///
/// # Examples
///
@@ -724,8 +809,19 @@
/// use hashbrown::HashMap;
///
/// let mut map: HashMap<i32, i32> = (0..8).map(|x|(x, x*10)).collect();
+ /// assert_eq!(map.len(), 8);
+ /// let capacity_before_retain = map.capacity();
+ ///
/// map.retain(|&k, _| k % 2 == 0);
+ ///
+ /// // We can see, that the number of elements inside map is changed.
/// assert_eq!(map.len(), 4);
+ /// // But map capacity is equal to old one.
+ /// assert_eq!(map.capacity(), capacity_before_retain);
+ ///
+ /// let mut vec: Vec<(i32, i32)> = map.iter().map(|(&k, &v)| (k, v)).collect();
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [(0, 0), (2, 20), (4, 40), (6, 60)]);
/// ```
pub fn retain<F>(&mut self, mut f: F)
where
@@ -745,18 +841,28 @@
/// Drains elements which are true under the given predicate,
/// and returns an iterator over the removed items.
///
- /// In other words, move all pairs `(k, v)` such that `f(&k,&mut v)` returns `true` out
+ /// In other words, move all pairs `(k, v)` such that `f(&k, &mut v)` returns `true` out
/// into another iterator.
///
+ /// Note that `drain_filter` lets you mutate every value in the filter closure, regardless of
+ /// whether you choose to keep or remove it.
+ ///
/// When the returned DrainedFilter is dropped, any remaining elements that satisfy
/// the predicate are dropped from the table.
///
+ /// It is unspecified how many more elements will be subjected to the closure
+ /// if a panic occurs in the closure, or a panic occurs while dropping an element,
+ /// or if the `DrainFilter` value is leaked.
+ ///
+ /// Keeps the allocated memory for reuse.
+ ///
/// # Examples
///
/// ```
/// use hashbrown::HashMap;
///
/// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
+ /// let capacity_before_drain_filter = map.capacity();
/// let drained: HashMap<i32, i32> = map.drain_filter(|k, _v| k % 2 == 0).collect();
///
/// let mut evens = drained.keys().cloned().collect::<Vec<_>>();
@@ -766,6 +872,18 @@
///
/// assert_eq!(evens, vec![0, 2, 4, 6]);
/// assert_eq!(odds, vec![1, 3, 5, 7]);
+ /// // Map capacity is equal to old one.
+ /// assert_eq!(map.capacity(), capacity_before_drain_filter);
+ ///
+ /// let mut map: HashMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
+ ///
+ /// { // Iterator is dropped without being consumed.
+ /// let d = map.drain_filter(|k, _v| k % 2 != 0);
+ /// }
+ ///
+ /// // But the map lens have been reduced by half
+ /// // even if we do not use DrainFilter iterator.
+ /// assert_eq!(map.len(), 4);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, K, V, F, A>
@@ -791,8 +909,14 @@
///
/// let mut a = HashMap::new();
/// a.insert(1, "a");
+ /// let capacity_before_clear = a.capacity();
+ ///
/// a.clear();
+ ///
+ /// // Map is empty.
/// assert!(a.is_empty());
+ /// // But map capacity is equal to old one.
+ /// assert_eq!(a.capacity(), capacity_before_clear);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear(&mut self) {
@@ -813,7 +937,12 @@
/// map.insert("b", 2);
/// map.insert("c", 3);
///
- /// let vec: Vec<&str> = map.into_keys().collect();
+ /// let mut vec: Vec<&str> = map.into_keys().collect();
+ ///
+ /// // The `IntoKeys` iterator produces keys in arbitrary order, so the
+ /// // keys must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, ["a", "b", "c"]);
/// ```
#[inline]
pub fn into_keys(self) -> IntoKeys<K, V, A> {
@@ -836,7 +965,12 @@
/// map.insert("b", 2);
/// map.insert("c", 3);
///
- /// let vec: Vec<i32> = map.into_values().collect();
+ /// let mut vec: Vec<i32> = map.into_values().collect();
+ ///
+ /// // The `IntoValues` iterator produces values in arbitrary order, so
+ /// // the values must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [1, 2, 3]);
/// ```
#[inline]
pub fn into_values(self) -> IntoValues<K, V, A> {
@@ -867,7 +1001,13 @@
/// ```
/// use hashbrown::HashMap;
/// let mut map: HashMap<&str, i32> = HashMap::new();
+ /// // Map is empty and doesn't allocate memory
+ /// assert_eq!(map.capacity(), 0);
+ ///
/// map.reserve(10);
+ ///
+ /// // And now map can hold at least 10 elements
+ /// assert!(map.capacity() >= 10);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn reserve(&mut self, additional: usize) {
@@ -888,8 +1028,36 @@
///
/// ```
/// use hashbrown::HashMap;
+ ///
/// let mut map: HashMap<&str, isize> = HashMap::new();
+ /// // Map is empty and doesn't allocate memory
+ /// assert_eq!(map.capacity(), 0);
+ ///
/// map.try_reserve(10).expect("why is the test harness OOMing on 10 bytes?");
+ ///
+ /// // And now map can hold at least 10 elements
+ /// assert!(map.capacity() >= 10);
+ /// ```
+ /// If the capacity overflows, or the allocator reports a failure, then an error
+ /// is returned:
+ /// ```
+ /// # fn test() {
+ /// use hashbrown::HashMap;
+ /// use hashbrown::TryReserveError;
+ /// let mut map: HashMap<i32, i32> = HashMap::new();
+ ///
+ /// match map.try_reserve(usize::MAX) {
+ /// Err(error) => match error {
+ /// TryReserveError::CapacityOverflow => {}
+ /// _ => panic!("TryReserveError::AllocError ?"),
+ /// },
+ /// _ => panic!(),
+ /// }
+ /// # }
+ /// # fn main() {
+ /// # #[cfg(not(miri))]
+ /// # test()
+ /// # }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
@@ -1188,6 +1356,8 @@
/// *x = "b";
/// }
/// assert_eq!(map[&1], "b");
+ ///
+ /// assert_eq!(map.get_mut(&2), None);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
@@ -1273,7 +1443,7 @@
/// Returns an array of length `N` with the results of each query. `None` will be returned if
/// any of the keys are missing.
///
- /// For a safe alternative see [`get_many_mut`].
+ /// For a safe alternative see [`get_many_mut`](`HashMap::get_many_mut`).
///
/// # Safety
///
@@ -1386,7 +1556,7 @@
/// Returns an array of length `N` with the results of each query. `None` will be returned if
/// any of the keys are missing.
///
- /// For a safe alternative see [`get_many_key_value_mut`].
+ /// For a safe alternative see [`get_many_key_value_mut`](`HashMap::get_many_key_value_mut`).
///
/// # Safety
///
@@ -1480,11 +1650,12 @@
///
/// If the map did have this key present, the value is updated, and the old
/// value is returned. The key is not updated, though; this matters for
- /// types that can be `==` without being identical. See the [module-level
- /// documentation] for more.
+ /// types that can be `==` without being identical. See the [`std::collections`]
+ /// [module-level documentation] for more.
///
/// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None
- /// [module-level documentation]: index.html#insert-and-complex-keys
+ /// [`std::collections`]: https://doc.rust-lang.org/std/collections/index.html
+ /// [module-level documentation]: https://doc.rust-lang.org/std/collections/index.html#insert-and-complex-keys
///
/// # Examples
///
@@ -1531,6 +1702,35 @@
/// This operation is useful during initial population of the map.
/// For example, when constructing a map from another map, we know
/// that keys are unique.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ ///
+ /// let mut map1 = HashMap::new();
+ /// assert_eq!(map1.insert(1, "a"), None);
+ /// assert_eq!(map1.insert(2, "b"), None);
+ /// assert_eq!(map1.insert(3, "c"), None);
+ /// assert_eq!(map1.len(), 3);
+ ///
+ /// let mut map2 = HashMap::new();
+ ///
+ /// for (key, value) in map1.into_iter() {
+ /// map2.insert_unique_unchecked(key, value);
+ /// }
+ ///
+ /// let (key, value) = map2.insert_unique_unchecked(4, "d");
+ /// assert_eq!(key, &4);
+ /// assert_eq!(value, &mut "d");
+ /// *value = "e";
+ ///
+ /// assert_eq!(map2[&1], "a");
+ /// assert_eq!(map2[&2], "b");
+ /// assert_eq!(map2[&3], "c");
+ /// assert_eq!(map2[&4], "e");
+ /// assert_eq!(map2.len(), 4);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert_unique_unchecked(&mut self, k: K, v: V) -> (&K, &mut V) {
let hash = make_insert_hash::<K, S>(&self.hash_builder, &k);
@@ -1555,14 +1755,19 @@
///
/// ```
/// use hashbrown::HashMap;
+ /// use hashbrown::hash_map::OccupiedError;
///
/// let mut map = HashMap::new();
/// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
///
- /// let err = map.try_insert(37, "b").unwrap_err();
- /// assert_eq!(err.entry.key(), &37);
- /// assert_eq!(err.entry.get(), &"a");
- /// assert_eq!(err.value, "b");
+ /// match map.try_insert(37, "b") {
+ /// Err(OccupiedError { entry, value }) => {
+ /// assert_eq!(entry.key(), &37);
+ /// assert_eq!(entry.get(), &"a");
+ /// assert_eq!(value, "b");
+ /// }
+ /// _ => panic!()
+ /// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn try_insert(
@@ -1577,7 +1782,7 @@
}
/// Removes a key from the map, returning the value at the key if the key
- /// was previously in the map.
+ /// was previously in the map. Keeps the allocated memory for reuse.
///
/// The key may be any borrowed form of the map's key type, but
/// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
@@ -1592,9 +1797,17 @@
/// use hashbrown::HashMap;
///
/// let mut map = HashMap::new();
+ /// // The map is empty
+ /// assert!(map.is_empty() && map.capacity() == 0);
+ ///
/// map.insert(1, "a");
+ /// let capacity_before_remove = map.capacity();
+ ///
/// assert_eq!(map.remove(&1), Some("a"));
/// assert_eq!(map.remove(&1), None);
+ ///
+ /// // Now map holds none elements but capacity is equal to the old one
+ /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
@@ -1610,7 +1823,7 @@
}
/// Removes a key from the map, returning the stored key and value if the
- /// key was previously in the map.
+ /// key was previously in the map. Keeps the allocated memory for reuse.
///
/// The key may be any borrowed form of the map's key type, but
/// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
@@ -1625,9 +1838,17 @@
/// use hashbrown::HashMap;
///
/// let mut map = HashMap::new();
+ /// // The map is empty
+ /// assert!(map.is_empty() && map.capacity() == 0);
+ ///
/// map.insert(1, "a");
+ /// let capacity_before_remove = map.capacity();
+ ///
/// assert_eq!(map.remove_entry(&1), Some((1, "a")));
/// assert_eq!(map.remove(&1), None);
+ ///
+ /// // Now map hold none elements but capacity is equal to the old one
+ /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
@@ -1672,6 +1893,72 @@
/// so that the map now contains keys which compare equal, search may start
/// acting erratically, with two keys randomly masking each other. Implementations
/// are free to assume this doesn't happen (within the limits of memory-safety).
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map = HashMap::new();
+ /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// // Existing key (insert and update)
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => unreachable!(),
+ /// RawEntryMut::Occupied(mut view) => {
+ /// assert_eq!(view.get(), &100);
+ /// let v = view.get_mut();
+ /// let new_v = (*v) * 10;
+ /// *v = new_v;
+ /// assert_eq!(view.insert(1111), 1000);
+ /// }
+ /// }
+ ///
+ /// assert_eq!(map[&"a"], 1111);
+ /// assert_eq!(map.len(), 3);
+ ///
+ /// // Existing key (take)
+ /// let hash = compute_hash(map.hasher(), &"c");
+ /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"c") {
+ /// RawEntryMut::Vacant(_) => unreachable!(),
+ /// RawEntryMut::Occupied(view) => {
+ /// assert_eq!(view.remove_entry(), ("c", 300));
+ /// }
+ /// }
+ /// assert_eq!(map.raw_entry().from_key(&"c"), None);
+ /// assert_eq!(map.len(), 2);
+ ///
+ /// // Nonexistent key (insert and update)
+ /// let key = "d";
+ /// let hash = compute_hash(map.hasher(), &key);
+ /// match map.raw_entry_mut().from_hash(hash, |q| *q == key) {
+ /// RawEntryMut::Occupied(_) => unreachable!(),
+ /// RawEntryMut::Vacant(view) => {
+ /// let (k, value) = view.insert("d", 4000);
+ /// assert_eq!((*k, *value), ("d", 4000));
+ /// *value = 40000;
+ /// }
+ /// }
+ /// assert_eq!(map[&"d"], 40000);
+ /// assert_eq!(map.len(), 3);
+ ///
+ /// match map.raw_entry_mut().from_hash(hash, |q| *q == key) {
+ /// RawEntryMut::Vacant(_) => unreachable!(),
+ /// RawEntryMut::Occupied(view) => {
+ /// assert_eq!(view.remove_entry(), ("d", 40000));
+ /// }
+ /// }
+ /// assert_eq!(map.get(&"d"), None);
+ /// assert_eq!(map.len(), 2);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S, A> {
RawEntryBuilderMut { map: self }
@@ -1692,10 +1979,100 @@
/// `get` should be preferred.
///
/// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.extend([("a", 100), ("b", 200), ("c", 300)]);
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// for k in ["a", "b", "c", "d", "e", "f"] {
+ /// let hash = compute_hash(map.hasher(), k);
+ /// let v = map.get(&k).cloned();
+ /// let kv = v.as_ref().map(|v| (&k, v));
+ ///
+ /// println!("Key: {} and value: {:?}", k, v);
+ ///
+ /// assert_eq!(map.raw_entry().from_key(&k), kv);
+ /// assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv);
+ /// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
+ /// }
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S, A> {
RawEntryBuilder { map: self }
}
+
+ /// Returns a mutable reference to the [`RawTable`] used underneath [`HashMap`].
+ /// This function is only available if the `raw` feature of the crate is enabled.
+ ///
+ /// # Note
+ ///
+ /// Calling the function safe, but using raw hash table API's may require
+ /// unsafe functions or blocks.
+ ///
+ /// `RawTable` API gives the lowest level of control under the map that can be useful
+ /// for extending the HashMap's API, but may lead to *[undefined behavior]*.
+ ///
+ /// [`HashMap`]: struct.HashMap.html
+ /// [`RawTable`]: raw/struct.RawTable.html
+ /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.extend([("a", 10), ("b", 20), ("c", 30)]);
+ /// assert_eq!(map.len(), 3);
+ ///
+ /// // Let's imagine that we have a value and a hash of the key, but not the key itself.
+ /// // However, if you want to remove the value from the map by hash and value, and you
+ /// // know exactly that the value is unique, then you can create a function like this:
+ /// fn remove_by_hash<K, V, S, F>(
+ /// map: &mut HashMap<K, V, S>,
+ /// hash: u64,
+ /// is_match: F,
+ /// ) -> Option<(K, V)>
+ /// where
+ /// F: Fn(&(K, V)) -> bool,
+ /// {
+ /// let raw_table = map.raw_table();
+ /// match raw_table.find(hash, is_match) {
+ /// Some(bucket) => Some(unsafe { raw_table.remove(bucket) }),
+ /// None => None,
+ /// }
+ /// }
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// let hash = compute_hash(map.hasher(), "a");
+ /// assert_eq!(remove_by_hash(&mut map, hash, |(_, v)| *v == 10), Some(("a", 10)));
+ /// assert_eq!(map.get(&"a"), None);
+ /// assert_eq!(map.len(), 2);
+ /// ```
+ #[cfg(feature = "raw")]
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn raw_table(&mut self) -> &mut RawTable<(K, V), A> {
+ &mut self.table
+ }
}
impl<K, V, S, A> PartialEq for HashMap<K, V, S, A>
@@ -1741,6 +2118,20 @@
A: Default + Allocator + Clone,
{
/// Creates an empty `HashMap<K, V, S, A>`, with the `Default` value for the hasher and allocator.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ /// use std::collections::hash_map::RandomState;
+ ///
+ /// // You can specify all types of HashMap, including hasher and allocator.
+ /// // Created map is empty and don't allocate memory
+ /// let map: HashMap<u32, String> = Default::default();
+ /// assert_eq!(map.capacity(), 0);
+ /// let map: HashMap<u32, String, RandomState> = HashMap::default();
+ /// assert_eq!(map.capacity(), 0);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
fn default() -> Self {
Self::with_hasher_in(Default::default(), Default::default())
@@ -1761,6 +2152,17 @@
/// # Panics
///
/// Panics if the key is not present in the `HashMap`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ ///
+ /// let map: HashMap<_, _> = [("a", "One"), ("b", "Two")].into();
+ ///
+ /// assert_eq!(map[&"a"], "One");
+ /// assert_eq!(map[&"b"], "Two");
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
fn index(&self, key: &Q) -> &V {
self.get(key).expect("no entry found for key")
@@ -1788,13 +2190,34 @@
}
}
-/// An iterator over the entries of a `HashMap`.
+/// An iterator over the entries of a `HashMap` in arbitrary order.
+/// The iterator element type is `(&'a K, &'a V)`.
///
/// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
/// documentation for more.
///
/// [`iter`]: struct.HashMap.html#method.iter
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let map: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut iter = map.iter();
+/// let mut vec = vec![iter.next(), iter.next(), iter.next()];
+///
+/// // The `Iter` iterator produces items in arbitrary order, so the
+/// // items must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some((&1, &"a")), Some((&2, &"b")), Some((&3, &"c"))]);
+///
+/// // It is fused iterator
+/// assert_eq!(iter.next(), None);
+/// assert_eq!(iter.next(), None);
+/// ```
pub struct Iter<'a, K, V> {
inner: RawIter<(K, V)>,
marker: PhantomData<(&'a K, &'a V)>,
@@ -1817,13 +2240,33 @@
}
}
-/// A mutable iterator over the entries of a `HashMap`.
+/// A mutable iterator over the entries of a `HashMap` in arbitrary order.
+/// The iterator element type is `(&'a K, &'a mut V)`.
///
/// This `struct` is created by the [`iter_mut`] method on [`HashMap`]. See its
/// documentation for more.
///
/// [`iter_mut`]: struct.HashMap.html#method.iter_mut
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let mut map: HashMap<_, _> = [(1, "One".to_owned()), (2, "Two".into())].into();
+///
+/// let mut iter = map.iter_mut();
+/// iter.next().map(|(_, v)| v.push_str(" Mississippi"));
+/// iter.next().map(|(_, v)| v.push_str(" Mississippi"));
+///
+/// // It is fused iterator
+/// assert_eq!(iter.next(), None);
+/// assert_eq!(iter.next(), None);
+///
+/// assert_eq!(map.get(&1).unwrap(), &"One Mississippi".to_owned());
+/// assert_eq!(map.get(&2).unwrap(), &"Two Mississippi".to_owned());
+/// ```
pub struct IterMut<'a, K, V> {
inner: RawIter<(K, V)>,
// To ensure invariance with respect to V
@@ -1846,13 +2289,36 @@
}
}
-/// An owning iterator over the entries of a `HashMap`.
+/// An owning iterator over the entries of a `HashMap` in arbitrary order.
+/// The iterator element type is `(K, V)`.
///
/// This `struct` is created by the [`into_iter`] method on [`HashMap`]
-/// (provided by the `IntoIterator` trait). See its documentation for more.
+/// (provided by the [`IntoIterator`] trait). See its documentation for more.
+/// The map cannot be used after calling that method.
///
/// [`into_iter`]: struct.HashMap.html#method.into_iter
/// [`HashMap`]: struct.HashMap.html
+/// [`IntoIterator`]: https://doc.rust-lang.org/core/iter/trait.IntoIterator.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let map: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut iter = map.into_iter();
+/// let mut vec = vec![iter.next(), iter.next(), iter.next()];
+///
+/// // The `IntoIter` iterator produces items in arbitrary order, so the
+/// // items must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some((1, "a")), Some((2, "b")), Some((3, "c"))]);
+///
+/// // It is fused iterator
+/// assert_eq!(iter.next(), None);
+/// assert_eq!(iter.next(), None);
+/// ```
pub struct IntoIter<K, V, A: Allocator + Clone = Global> {
inner: RawIntoIter<(K, V), A>,
}
@@ -1868,13 +2334,35 @@
}
}
-/// An owning iterator over the keys of a `HashMap`.
+/// An owning iterator over the keys of a `HashMap` in arbitrary order.
+/// The iterator element type is `K`.
///
/// This `struct` is created by the [`into_keys`] method on [`HashMap`].
/// See its documentation for more.
+/// The map cannot be used after calling that method.
///
/// [`into_keys`]: struct.HashMap.html#method.into_keys
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let map: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut keys = map.into_keys();
+/// let mut vec = vec![keys.next(), keys.next(), keys.next()];
+///
+/// // The `IntoKeys` iterator produces keys in arbitrary order, so the
+/// // keys must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some(1), Some(2), Some(3)]);
+///
+/// // It is fused iterator
+/// assert_eq!(keys.next(), None);
+/// assert_eq!(keys.next(), None);
+/// ```
pub struct IntoKeys<K, V, A: Allocator + Clone = Global> {
inner: IntoIter<K, V, A>,
}
@@ -1909,13 +2397,34 @@
}
}
-/// An owning iterator over the values of a `HashMap`.
+/// An owning iterator over the values of a `HashMap` in arbitrary order.
+/// The iterator element type is `V`.
///
/// This `struct` is created by the [`into_values`] method on [`HashMap`].
-/// See its documentation for more.
+/// See its documentation for more. The map cannot be used after calling that method.
///
/// [`into_values`]: struct.HashMap.html#method.into_values
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let map: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut values = map.into_values();
+/// let mut vec = vec![values.next(), values.next(), values.next()];
+///
+/// // The `IntoValues` iterator produces values in arbitrary order, so
+/// // the values must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some("a"), Some("b"), Some("c")]);
+///
+/// // It is fused iterator
+/// assert_eq!(values.next(), None);
+/// assert_eq!(values.next(), None);
+/// ```
pub struct IntoValues<K, V, A: Allocator + Clone = Global> {
inner: IntoIter<K, V, A>,
}
@@ -1950,13 +2459,34 @@
}
}
-/// An iterator over the keys of a `HashMap`.
+/// An iterator over the keys of a `HashMap` in arbitrary order.
+/// The iterator element type is `&'a K`.
///
/// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
/// documentation for more.
///
/// [`keys`]: struct.HashMap.html#method.keys
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let map: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut keys = map.keys();
+/// let mut vec = vec![keys.next(), keys.next(), keys.next()];
+///
+/// // The `Keys` iterator produces keys in arbitrary order, so the
+/// // keys must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some(&1), Some(&2), Some(&3)]);
+///
+/// // It is fused iterator
+/// assert_eq!(keys.next(), None);
+/// assert_eq!(keys.next(), None);
+/// ```
pub struct Keys<'a, K, V> {
inner: Iter<'a, K, V>,
}
@@ -1977,13 +2507,34 @@
}
}
-/// An iterator over the values of a `HashMap`.
+/// An iterator over the values of a `HashMap` in arbitrary order.
+/// The iterator element type is `&'a V`.
///
/// This `struct` is created by the [`values`] method on [`HashMap`]. See its
/// documentation for more.
///
/// [`values`]: struct.HashMap.html#method.values
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let map: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut values = map.values();
+/// let mut vec = vec![values.next(), values.next(), values.next()];
+///
+/// // The `Values` iterator produces values in arbitrary order, so the
+/// // values must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some(&"a"), Some(&"b"), Some(&"c")]);
+///
+/// // It is fused iterator
+/// assert_eq!(values.next(), None);
+/// assert_eq!(values.next(), None);
+/// ```
pub struct Values<'a, K, V> {
inner: Iter<'a, K, V>,
}
@@ -2004,13 +2555,34 @@
}
}
-/// A draining iterator over the entries of a `HashMap`.
+/// A draining iterator over the entries of a `HashMap` in arbitrary
+/// order. The iterator element type is `(K, V)`.
///
/// This `struct` is created by the [`drain`] method on [`HashMap`]. See its
/// documentation for more.
///
/// [`drain`]: struct.HashMap.html#method.drain
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let mut map: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut drain_iter = map.drain();
+/// let mut vec = vec![drain_iter.next(), drain_iter.next(), drain_iter.next()];
+///
+/// // The `Drain` iterator produces items in arbitrary order, so the
+/// // items must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some((1, "a")), Some((2, "b")), Some((3, "c"))]);
+///
+/// // It is fused iterator
+/// assert_eq!(drain_iter.next(), None);
+/// assert_eq!(drain_iter.next(), None);
+/// ```
pub struct Drain<'a, K, V, A: Allocator + Clone = Global> {
inner: RawDrain<'a, (K, V), A>,
}
@@ -2026,13 +2598,37 @@
}
}
-/// A draining iterator over entries of a `HashMap` which don't satisfy the predicate `f`.
+/// A draining iterator over entries of a `HashMap` which don't satisfy the predicate
+/// `f(&k, &mut v)` in arbitrary order. The iterator element type is `(K, V)`.
///
/// This `struct` is created by the [`drain_filter`] method on [`HashMap`]. See its
/// documentation for more.
///
/// [`drain_filter`]: struct.HashMap.html#method.drain_filter
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let mut map: HashMap<i32, &str> = [(1, "a"), (2, "b"), (3, "c")].into();
+///
+/// let mut drain_filter = map.drain_filter(|k, _v| k % 2 != 0);
+/// let mut vec = vec![drain_filter.next(), drain_filter.next()];
+///
+/// // The `DrainFilter` iterator produces items in arbitrary order, so the
+/// // items must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [Some((1, "a")),Some((3, "c"))]);
+///
+/// // It is fused iterator
+/// assert_eq!(drain_filter.next(), None);
+/// assert_eq!(drain_filter.next(), None);
+/// drop(drain_filter);
+///
+/// assert_eq!(map.len(), 1);
+/// ```
pub struct DrainFilter<'a, K, V, F, A: Allocator + Clone = Global>
where
F: FnMut(&K, &mut V) -> bool,
@@ -2109,13 +2705,33 @@
}
}
-/// A mutable iterator over the values of a `HashMap`.
+/// A mutable iterator over the values of a `HashMap` in arbitrary order.
+/// The iterator element type is `&'a mut V`.
///
/// This `struct` is created by the [`values_mut`] method on [`HashMap`]. See its
/// documentation for more.
///
/// [`values_mut`]: struct.HashMap.html#method.values_mut
/// [`HashMap`]: struct.HashMap.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::HashMap;
+///
+/// let mut map: HashMap<_, _> = [(1, "One".to_owned()), (2, "Two".into())].into();
+///
+/// let mut values = map.values_mut();
+/// values.next().map(|v| v.push_str(" Mississippi"));
+/// values.next().map(|v| v.push_str(" Mississippi"));
+///
+/// // It is fused iterator
+/// assert_eq!(values.next(), None);
+/// assert_eq!(values.next(), None);
+///
+/// assert_eq!(map.get(&1).unwrap(), &"One Mississippi".to_owned());
+/// assert_eq!(map.get(&2).unwrap(), &"Two Mississippi".to_owned());
+/// ```
pub struct ValuesMut<'a, K, V> {
inner: IterMut<'a, K, V>,
}
@@ -2125,6 +2741,56 @@
/// See the [`HashMap::raw_entry_mut`] docs for usage examples.
///
/// [`HashMap::raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{RawEntryBuilderMut, RawEntryMut::Vacant, RawEntryMut::Occupied};
+/// use hashbrown::HashMap;
+/// use core::hash::{BuildHasher, Hash};
+///
+/// let mut map = HashMap::new();
+/// map.extend([(1, 11), (2, 12), (3, 13), (4, 14), (5, 15), (6, 16)]);
+/// assert_eq!(map.len(), 6);
+///
+/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+/// use core::hash::Hasher;
+/// let mut state = hash_builder.build_hasher();
+/// key.hash(&mut state);
+/// state.finish()
+/// }
+///
+/// let builder: RawEntryBuilderMut<_, _, _> = map.raw_entry_mut();
+///
+/// // Existing key
+/// match builder.from_key(&6) {
+/// Vacant(_) => unreachable!(),
+/// Occupied(view) => assert_eq!(view.get(), &16),
+/// }
+///
+/// for key in 0..12 {
+/// let hash = compute_hash(map.hasher(), &key);
+/// let value = map.get(&key).cloned();
+/// let key_value = value.as_ref().map(|v| (&key, v));
+///
+/// println!("Key: {} and value: {:?}", key, value);
+///
+/// match map.raw_entry_mut().from_key(&key) {
+/// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value),
+/// Vacant(_) => assert_eq!(value, None),
+/// }
+/// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &key) {
+/// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value),
+/// Vacant(_) => assert_eq!(value, None),
+/// }
+/// match map.raw_entry_mut().from_hash(hash, |q| *q == key) {
+/// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value),
+/// Vacant(_) => assert_eq!(value, None),
+/// }
+/// }
+///
+/// assert_eq!(map.len(), 6);
+/// ```
pub struct RawEntryBuilderMut<'a, K, V, S, A: Allocator + Clone = Global> {
map: &'a mut HashMap<K, V, S, A>,
}
@@ -2140,10 +2806,107 @@
/// [`Entry`]: enum.Entry.html
/// [`raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
/// [`RawEntryBuilderMut`]: struct.RawEntryBuilderMut.html
+///
+/// # Examples
+///
+/// ```
+/// use core::hash::{BuildHasher, Hash};
+/// use hashbrown::hash_map::{HashMap, RawEntryMut, RawOccupiedEntryMut};
+///
+/// let mut map = HashMap::new();
+/// map.extend([('a', 1), ('b', 2), ('c', 3)]);
+/// assert_eq!(map.len(), 3);
+///
+/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+/// use core::hash::Hasher;
+/// let mut state = hash_builder.build_hasher();
+/// key.hash(&mut state);
+/// state.finish()
+/// }
+///
+/// // Existing key (insert)
+/// let raw: RawEntryMut<_, _, _> = map.raw_entry_mut().from_key(&'a');
+/// let _raw_o: RawOccupiedEntryMut<_, _, _> = raw.insert('a', 10);
+/// assert_eq!(map.len(), 3);
+///
+/// // Nonexistent key (insert)
+/// map.raw_entry_mut().from_key(&'d').insert('d', 40);
+/// assert_eq!(map.len(), 4);
+///
+/// // Existing key (or_insert)
+/// let hash = compute_hash(map.hasher(), &'b');
+/// let kv = map
+/// .raw_entry_mut()
+/// .from_key_hashed_nocheck(hash, &'b')
+/// .or_insert('b', 20);
+/// assert_eq!(kv, (&mut 'b', &mut 2));
+/// *kv.1 = 20;
+/// assert_eq!(map.len(), 4);
+///
+/// // Nonexistent key (or_insert)
+/// let hash = compute_hash(map.hasher(), &'e');
+/// let kv = map
+/// .raw_entry_mut()
+/// .from_key_hashed_nocheck(hash, &'e')
+/// .or_insert('e', 50);
+/// assert_eq!(kv, (&mut 'e', &mut 50));
+/// assert_eq!(map.len(), 5);
+///
+/// // Existing key (or_insert_with)
+/// let hash = compute_hash(map.hasher(), &'c');
+/// let kv = map
+/// .raw_entry_mut()
+/// .from_hash(hash, |q| q == &'c')
+/// .or_insert_with(|| ('c', 30));
+/// assert_eq!(kv, (&mut 'c', &mut 3));
+/// *kv.1 = 30;
+/// assert_eq!(map.len(), 5);
+///
+/// // Nonexistent key (or_insert_with)
+/// let hash = compute_hash(map.hasher(), &'f');
+/// let kv = map
+/// .raw_entry_mut()
+/// .from_hash(hash, |q| q == &'f')
+/// .or_insert_with(|| ('f', 60));
+/// assert_eq!(kv, (&mut 'f', &mut 60));
+/// assert_eq!(map.len(), 6);
+///
+/// println!("Our HashMap: {:?}", map);
+///
+/// let mut vec: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
+/// // The `Iter` iterator produces items in arbitrary order, so the
+/// // items must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [('a', 10), ('b', 20), ('c', 30), ('d', 40), ('e', 50), ('f', 60)]);
+/// ```
pub enum RawEntryMut<'a, K, V, S, A: Allocator + Clone = Global> {
/// An occupied entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::{hash_map::RawEntryMut, HashMap};
+ /// let mut map: HashMap<_, _> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => unreachable!(),
+ /// RawEntryMut::Occupied(_) => { }
+ /// }
+ /// ```
Occupied(RawOccupiedEntryMut<'a, K, V, S, A>),
/// A vacant entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::{hash_map::RawEntryMut, HashMap};
+ /// let mut map: HashMap<&str, i32> = HashMap::new();
+ ///
+ /// match map.raw_entry_mut().from_key("a") {
+ /// RawEntryMut::Occupied(_) => unreachable!(),
+ /// RawEntryMut::Vacant(_) => { }
+ /// }
+ /// ```
Vacant(RawVacantEntryMut<'a, K, V, S, A>),
}
@@ -2151,6 +2914,62 @@
/// It is part of the [`RawEntryMut`] enum.
///
/// [`RawEntryMut`]: enum.RawEntryMut.html
+///
+/// # Examples
+///
+/// ```
+/// use core::hash::{BuildHasher, Hash};
+/// use hashbrown::hash_map::{HashMap, RawEntryMut, RawOccupiedEntryMut};
+///
+/// let mut map = HashMap::new();
+/// map.extend([("a", 10), ("b", 20), ("c", 30)]);
+///
+/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+/// use core::hash::Hasher;
+/// let mut state = hash_builder.build_hasher();
+/// key.hash(&mut state);
+/// state.finish()
+/// }
+///
+/// let _raw_o: RawOccupiedEntryMut<_, _, _> = map.raw_entry_mut().from_key(&"a").insert("a", 100);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (insert and update)
+/// match map.raw_entry_mut().from_key(&"a") {
+/// RawEntryMut::Vacant(_) => unreachable!(),
+/// RawEntryMut::Occupied(mut view) => {
+/// assert_eq!(view.get(), &100);
+/// let v = view.get_mut();
+/// let new_v = (*v) * 10;
+/// *v = new_v;
+/// assert_eq!(view.insert(1111), 1000);
+/// }
+/// }
+///
+/// assert_eq!(map[&"a"], 1111);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (take)
+/// let hash = compute_hash(map.hasher(), &"c");
+/// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"c") {
+/// RawEntryMut::Vacant(_) => unreachable!(),
+/// RawEntryMut::Occupied(view) => {
+/// assert_eq!(view.remove_entry(), ("c", 30));
+/// }
+/// }
+/// assert_eq!(map.raw_entry().from_key(&"c"), None);
+/// assert_eq!(map.len(), 2);
+///
+/// let hash = compute_hash(map.hasher(), &"b");
+/// match map.raw_entry_mut().from_hash(hash, |q| *q == "b") {
+/// RawEntryMut::Vacant(_) => unreachable!(),
+/// RawEntryMut::Occupied(view) => {
+/// assert_eq!(view.remove_entry(), ("b", 20));
+/// }
+/// }
+/// assert_eq!(map.get(&"b"), None);
+/// assert_eq!(map.len(), 1);
+/// ```
pub struct RawOccupiedEntryMut<'a, K, V, S, A: Allocator + Clone = Global> {
elem: Bucket<(K, V)>,
table: &'a mut RawTable<(K, V), A>,
@@ -2178,6 +2997,50 @@
/// It is part of the [`RawEntryMut`] enum.
///
/// [`RawEntryMut`]: enum.RawEntryMut.html
+///
+/// # Examples
+///
+/// ```
+/// use core::hash::{BuildHasher, Hash};
+/// use hashbrown::hash_map::{HashMap, RawEntryMut, RawVacantEntryMut};
+///
+/// let mut map = HashMap::<&str, i32>::new();
+///
+/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+/// use core::hash::Hasher;
+/// let mut state = hash_builder.build_hasher();
+/// key.hash(&mut state);
+/// state.finish()
+/// }
+///
+/// let raw_v: RawVacantEntryMut<_, _, _> = match map.raw_entry_mut().from_key(&"a") {
+/// RawEntryMut::Vacant(view) => view,
+/// RawEntryMut::Occupied(_) => unreachable!(),
+/// };
+/// raw_v.insert("a", 10);
+/// assert!(map[&"a"] == 10 && map.len() == 1);
+///
+/// // Nonexistent key (insert and update)
+/// let hash = compute_hash(map.hasher(), &"b");
+/// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"b") {
+/// RawEntryMut::Occupied(_) => unreachable!(),
+/// RawEntryMut::Vacant(view) => {
+/// let (k, value) = view.insert("b", 2);
+/// assert_eq!((*k, *value), ("b", 2));
+/// *value = 20;
+/// }
+/// }
+/// assert!(map[&"b"] == 20 && map.len() == 2);
+///
+/// let hash = compute_hash(map.hasher(), &"c");
+/// match map.raw_entry_mut().from_hash(hash, |q| *q == "c") {
+/// RawEntryMut::Occupied(_) => unreachable!(),
+/// RawEntryMut::Vacant(view) => {
+/// assert_eq!(view.insert("c", 30), (&mut "c", &mut 30));
+/// }
+/// }
+/// assert!(map[&"c"] == 30 && map.len() == 3);
+/// ```
pub struct RawVacantEntryMut<'a, K, V, S, A: Allocator + Clone = Global> {
table: &'a mut RawTable<(K, V), A>,
hash_builder: &'a S,
@@ -2188,12 +3051,53 @@
/// See the [`HashMap::raw_entry`] docs for usage examples.
///
/// [`HashMap::raw_entry`]: struct.HashMap.html#method.raw_entry
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{HashMap, RawEntryBuilder};
+/// use core::hash::{BuildHasher, Hash};
+///
+/// let mut map = HashMap::new();
+/// map.extend([(1, 10), (2, 20), (3, 30)]);
+///
+/// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+/// use core::hash::Hasher;
+/// let mut state = hash_builder.build_hasher();
+/// key.hash(&mut state);
+/// state.finish()
+/// }
+///
+/// for k in 0..6 {
+/// let hash = compute_hash(map.hasher(), &k);
+/// let v = map.get(&k).cloned();
+/// let kv = v.as_ref().map(|v| (&k, v));
+///
+/// println!("Key: {} and value: {:?}", k, v);
+/// let builder: RawEntryBuilder<_, _, _> = map.raw_entry();
+/// assert_eq!(builder.from_key(&k), kv);
+/// assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv);
+/// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
+/// }
+/// ```
pub struct RawEntryBuilder<'a, K, V, S, A: Allocator + Clone = Global> {
map: &'a HashMap<K, V, S, A>,
}
impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> {
/// Creates a `RawEntryMut` from the given key.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// let key = "a";
+ /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_key(&key);
+ /// entry.insert(key, 100);
+ /// assert_eq!(map[&"a"], 100);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S, A>
@@ -2207,6 +3111,27 @@
}
/// Creates a `RawEntryMut` from the given key and its hash.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// let key = "a";
+ /// let hash = compute_hash(map.hasher(), &key);
+ /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_key_hashed_nocheck(hash, &key);
+ /// entry.insert(key, 100);
+ /// assert_eq!(map[&"a"], 100);
+ /// ```
#[inline]
#[allow(clippy::wrong_self_convention)]
pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S, A>
@@ -2219,7 +3144,28 @@
}
impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> {
- /// Creates a `RawEntryMut` from the given hash.
+ /// Creates a `RawEntryMut` from the given hash and matching function.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// let key = "a";
+ /// let hash = compute_hash(map.hasher(), &key);
+ /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_hash(hash, |k| k == &key);
+ /// entry.insert(key, 100);
+ /// assert_eq!(map[&"a"], 100);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S, A>
@@ -2249,7 +3195,17 @@
}
impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilder<'a, K, V, S, A> {
- /// Access an entry by key.
+ /// Access an immutable entry by key.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ ///
+ /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ /// let key = "a";
+ /// assert_eq!(map.raw_entry().from_key(&key), Some((&"a", &100)));
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
pub fn from_key<Q: ?Sized>(self, k: &Q) -> Option<(&'a K, &'a V)>
@@ -2262,7 +3218,26 @@
self.from_key_hashed_nocheck(hash, k)
}
- /// Access an entry by a key and its hash.
+ /// Access an immutable entry by a key and its hash.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::HashMap;
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ /// let key = "a";
+ /// let hash = compute_hash(map.hasher(), &key);
+ /// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &key), Some((&"a", &100)));
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)>
@@ -2284,7 +3259,26 @@
}
}
- /// Access an entry by hash.
+ /// Access an immutable entry by hash and matching function.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::HashMap;
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ /// let key = "a";
+ /// let hash = compute_hash(map.hasher(), &key);
+ /// assert_eq!(map.raw_entry().from_hash(hash, |k| k == &key), Some((&"a", &100)));
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)>
@@ -2491,12 +3485,50 @@
impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> {
/// Gets a reference to the key in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => assert_eq!(o.key(), &"a")
+ /// }
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn key(&self) -> &K {
unsafe { &self.elem.as_ref().0 }
}
/// Gets a mutable reference to the key in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ /// use std::rc::Rc;
+ ///
+ /// let key_one = Rc::new("a");
+ /// let key_two = Rc::new("a");
+ ///
+ /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
+ /// map.insert(key_one.clone(), 10);
+ ///
+ /// assert_eq!(map[&key_one], 10);
+ /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
+ ///
+ /// match map.raw_entry_mut().from_key(&key_one) {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(mut o) => {
+ /// *o.key_mut() = key_two.clone();
+ /// }
+ /// }
+ /// assert_eq!(map[&key_two], 10);
+ /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn key_mut(&mut self) -> &mut K {
unsafe { &mut self.elem.as_mut().0 }
@@ -2504,12 +3536,52 @@
/// Converts the entry into a mutable reference to the key in the entry
/// with a lifetime bound to the map itself.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ /// use std::rc::Rc;
+ ///
+ /// let key_one = Rc::new("a");
+ /// let key_two = Rc::new("a");
+ ///
+ /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
+ /// map.insert(key_one.clone(), 10);
+ ///
+ /// assert_eq!(map[&key_one], 10);
+ /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
+ ///
+ /// let inside_key: &mut Rc<&str>;
+ ///
+ /// match map.raw_entry_mut().from_key(&key_one) {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => inside_key = o.into_key(),
+ /// }
+ /// *inside_key = key_two.clone();
+ ///
+ /// assert_eq!(map[&key_two], 10);
+ /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn into_key(self) -> &'a mut K {
unsafe { &mut self.elem.as_mut().0 }
}
/// Gets a reference to the value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => assert_eq!(o.get(), &100),
+ /// }
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn get(&self) -> &V {
unsafe { &self.elem.as_ref().1 }
@@ -2517,20 +3589,66 @@
/// Converts the OccupiedEntry into a mutable reference to the value in the entry
/// with a lifetime bound to the map itself.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// let value: &mut u32;
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => value = o.into_mut(),
+ /// }
+ /// *value += 900;
+ ///
+ /// assert_eq!(map[&"a"], 1000);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn into_mut(self) -> &'a mut V {
unsafe { &mut self.elem.as_mut().1 }
}
/// Gets a mutable reference to the value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(mut o) => *o.get_mut() += 900,
+ /// }
+ ///
+ /// assert_eq!(map[&"a"], 1000);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn get_mut(&mut self) -> &mut V {
unsafe { &mut self.elem.as_mut().1 }
}
/// Gets a reference to the key and value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => assert_eq!(o.get_key_value(), (&"a", &100)),
+ /// }
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn get_key_value(&mut self) -> (&K, &V) {
+ pub fn get_key_value(&self) -> (&K, &V) {
unsafe {
let &(ref key, ref value) = self.elem.as_ref();
(key, value)
@@ -2538,6 +3656,33 @@
}
/// Gets a mutable reference to the key and value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ /// use std::rc::Rc;
+ ///
+ /// let key_one = Rc::new("a");
+ /// let key_two = Rc::new("a");
+ ///
+ /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
+ /// map.insert(key_one.clone(), 10);
+ ///
+ /// assert_eq!(map[&key_one], 10);
+ /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
+ ///
+ /// match map.raw_entry_mut().from_key(&key_one) {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(mut o) => {
+ /// let (inside_key, inside_value) = o.get_key_value_mut();
+ /// *inside_key = key_two.clone();
+ /// *inside_value = 100;
+ /// }
+ /// }
+ /// assert_eq!(map[&key_two], 100);
+ /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) {
unsafe {
@@ -2548,6 +3693,37 @@
/// Converts the OccupiedEntry into a mutable reference to the key and value in the entry
/// with a lifetime bound to the map itself.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ /// use std::rc::Rc;
+ ///
+ /// let key_one = Rc::new("a");
+ /// let key_two = Rc::new("a");
+ ///
+ /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
+ /// map.insert(key_one.clone(), 10);
+ ///
+ /// assert_eq!(map[&key_one], 10);
+ /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
+ ///
+ /// let inside_key: &mut Rc<&str>;
+ /// let inside_value: &mut u32;
+ /// match map.raw_entry_mut().from_key(&key_one) {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => {
+ /// let tuple = o.into_key_value();
+ /// inside_key = tuple.0;
+ /// inside_value = tuple.1;
+ /// }
+ /// }
+ /// *inside_key = key_two.clone();
+ /// *inside_value = 100;
+ /// assert_eq!(map[&key_two], 100);
+ /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn into_key_value(self) -> (&'a mut K, &'a mut V) {
unsafe {
@@ -2557,24 +3733,93 @@
}
/// Sets the value of the entry, and returns the entry's old value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(mut o) => assert_eq!(o.insert(1000), 100),
+ /// }
+ ///
+ /// assert_eq!(map[&"a"], 1000);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert(&mut self, value: V) -> V {
mem::replace(self.get_mut(), value)
}
/// Sets the value of the entry, and returns the entry's old value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ /// use std::rc::Rc;
+ ///
+ /// let key_one = Rc::new("a");
+ /// let key_two = Rc::new("a");
+ ///
+ /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new();
+ /// map.insert(key_one.clone(), 10);
+ ///
+ /// assert_eq!(map[&key_one], 10);
+ /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
+ ///
+ /// match map.raw_entry_mut().from_key(&key_one) {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(mut o) => {
+ /// let old_key = o.insert_key(key_two.clone());
+ /// assert!(Rc::ptr_eq(&old_key, &key_one));
+ /// }
+ /// }
+ /// assert_eq!(map[&key_two], 10);
+ /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert_key(&mut self, key: K) -> K {
mem::replace(self.key_mut(), key)
}
/// Takes the value out of the entry, and returns it.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => assert_eq!(o.remove(), 100),
+ /// }
+ /// assert_eq!(map.get(&"a"), None);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove(self) -> V {
self.remove_entry().1
}
/// Take the ownership of the key and value from the map.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => assert_eq!(o.remove_entry(), ("a", 100)),
+ /// }
+ /// assert_eq!(map.get(&"a"), None);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove_entry(self) -> (K, V) {
unsafe { self.table.remove(self.elem) }
@@ -2583,6 +3828,36 @@
/// Provides shared access to the key and owned access to the value of
/// the entry and allows to replace or remove it based on the
/// value of the returned option.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// let raw_entry = match map.raw_entry_mut().from_key(&"a") {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => o.replace_entry_with(|k, v| {
+ /// assert_eq!(k, &"a");
+ /// assert_eq!(v, 100);
+ /// Some(v + 900)
+ /// }),
+ /// };
+ /// let raw_entry = match raw_entry {
+ /// RawEntryMut::Vacant(_) => panic!(),
+ /// RawEntryMut::Occupied(o) => o.replace_entry_with(|k, v| {
+ /// assert_eq!(k, &"a");
+ /// assert_eq!(v, 1000);
+ /// None
+ /// }),
+ /// };
+ /// match raw_entry {
+ /// RawEntryMut::Vacant(_) => { },
+ /// RawEntryMut::Occupied(_) => panic!(),
+ /// };
+ /// assert_eq!(map.get(&"a"), None);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn replace_entry_with<F>(self, f: F) -> RawEntryMut<'a, K, V, S, A>
where
@@ -2610,6 +3885,21 @@
impl<'a, K, V, S, A: Allocator + Clone> RawVacantEntryMut<'a, K, V, S, A> {
/// Sets the value of the entry with the VacantEntry's key,
/// and returns a mutable reference to it.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.raw_entry_mut().from_key(&"c") {
+ /// RawEntryMut::Occupied(_) => panic!(),
+ /// RawEntryMut::Vacant(v) => assert_eq!(v.insert("c", 300), (&mut "c", &mut 300)),
+ /// }
+ ///
+ /// assert_eq!(map[&"c"], 300);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V)
where
@@ -2622,6 +3912,34 @@
/// Sets the value of the entry with the VacantEntry's key,
/// and returns a mutable reference to it.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ ///
+ /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into();
+ /// let key = "c";
+ /// let hash = compute_hash(map.hasher(), &key);
+ ///
+ /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &key) {
+ /// RawEntryMut::Occupied(_) => panic!(),
+ /// RawEntryMut::Vacant(v) => assert_eq!(
+ /// v.insert_hashed_nocheck(hash, key, 300),
+ /// (&mut "c", &mut 300)
+ /// ),
+ /// }
+ ///
+ /// assert_eq!(map[&"c"], 300);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::shadow_unrelated)]
pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V)
@@ -2638,6 +3956,41 @@
}
/// Set the value of an entry with a custom hasher function.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use core::hash::{BuildHasher, Hash};
+ /// use hashbrown::hash_map::{HashMap, RawEntryMut};
+ ///
+ /// fn make_hasher<K, S>(hash_builder: &S) -> impl Fn(&K) -> u64 + '_
+ /// where
+ /// K: Hash + ?Sized,
+ /// S: BuildHasher,
+ /// {
+ /// move |key: &K| {
+ /// use core::hash::Hasher;
+ /// let mut state = hash_builder.build_hasher();
+ /// key.hash(&mut state);
+ /// state.finish()
+ /// }
+ /// }
+ ///
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// let key = "a";
+ /// let hash_builder = map.hasher().clone();
+ /// let hash = make_hasher(&hash_builder)(&key);
+ ///
+ /// match map.raw_entry_mut().from_hash(hash, |q| q == &key) {
+ /// RawEntryMut::Occupied(_) => panic!(),
+ /// RawEntryMut::Vacant(v) => assert_eq!(
+ /// v.insert_with_hasher(hash, key, 100, make_hasher(&hash_builder)),
+ /// (&mut "a", &mut 100)
+ /// ),
+ /// }
+ /// map.extend([("b", 200), ("c", 300), ("d", 400), ("e", 500), ("f", 600)]);
+ /// assert_eq!(map[&"a"], 100);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert_with_hasher<H>(
self,
@@ -2717,14 +4070,75 @@
///
/// [`HashMap`]: struct.HashMap.html
/// [`entry`]: struct.HashMap.html#method.entry
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{Entry, HashMap, OccupiedEntry};
+///
+/// let mut map = HashMap::new();
+/// map.extend([("a", 10), ("b", 20), ("c", 30)]);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (insert)
+/// let entry: Entry<_, _, _> = map.entry("a");
+/// let _raw_o: OccupiedEntry<_, _, _> = entry.insert(1);
+/// assert_eq!(map.len(), 3);
+/// // Nonexistent key (insert)
+/// map.entry("d").insert(4);
+///
+/// // Existing key (or_insert)
+/// let v = map.entry("b").or_insert(2);
+/// assert_eq!(std::mem::replace(v, 2), 20);
+/// // Nonexistent key (or_insert)
+/// map.entry("e").or_insert(5);
+///
+/// // Existing key (or_insert_with)
+/// let v = map.entry("c").or_insert_with(|| 3);
+/// assert_eq!(std::mem::replace(v, 3), 30);
+/// // Nonexistent key (or_insert_with)
+/// map.entry("f").or_insert_with(|| 6);
+///
+/// println!("Our HashMap: {:?}", map);
+///
+/// let mut vec: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect();
+/// // The `Iter` iterator produces items in arbitrary order, so the
+/// // items must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, [("a", 1), ("b", 2), ("c", 3), ("d", 4), ("e", 5), ("f", 6)]);
+/// ```
pub enum Entry<'a, K, V, S, A = Global>
where
A: Allocator + Clone,
{
/// An occupied entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{Entry, HashMap};
+ /// let mut map: HashMap<_, _> = [("a", 100), ("b", 200)].into();
+ ///
+ /// match map.entry("a") {
+ /// Entry::Vacant(_) => unreachable!(),
+ /// Entry::Occupied(_) => { }
+ /// }
+ /// ```
Occupied(OccupiedEntry<'a, K, V, S, A>),
/// A vacant entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{Entry, HashMap};
+ /// let mut map: HashMap<&str, i32> = HashMap::new();
+ ///
+ /// match map.entry("a") {
+ /// Entry::Occupied(_) => unreachable!(),
+ /// Entry::Vacant(_) => { }
+ /// }
+ /// ```
Vacant(VacantEntry<'a, K, V, S, A>),
}
@@ -2741,6 +4155,42 @@
/// It is part of the [`Entry`] enum.
///
/// [`Entry`]: enum.Entry.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{Entry, HashMap, OccupiedEntry};
+///
+/// let mut map = HashMap::new();
+/// map.extend([("a", 10), ("b", 20), ("c", 30)]);
+///
+/// let _entry_o: OccupiedEntry<_, _, _> = map.entry("a").insert(100);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (insert and update)
+/// match map.entry("a") {
+/// Entry::Vacant(_) => unreachable!(),
+/// Entry::Occupied(mut view) => {
+/// assert_eq!(view.get(), &100);
+/// let v = view.get_mut();
+/// *v *= 10;
+/// assert_eq!(view.insert(1111), 1000);
+/// }
+/// }
+///
+/// assert_eq!(map[&"a"], 1111);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (take)
+/// match map.entry("c") {
+/// Entry::Vacant(_) => unreachable!(),
+/// Entry::Occupied(view) => {
+/// assert_eq!(view.remove_entry(), ("c", 30));
+/// }
+/// }
+/// assert_eq!(map.get(&"c"), None);
+/// assert_eq!(map.len(), 2);
+/// ```
pub struct OccupiedEntry<'a, K, V, S, A: Allocator + Clone = Global> {
hash: u64,
key: Option<K>,
@@ -2778,6 +4228,32 @@
/// It is part of the [`Entry`] enum.
///
/// [`Entry`]: enum.Entry.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{Entry, HashMap, VacantEntry};
+///
+/// let mut map = HashMap::<&str, i32>::new();
+///
+/// let entry_v: VacantEntry<_, _, _> = match map.entry("a") {
+/// Entry::Vacant(view) => view,
+/// Entry::Occupied(_) => unreachable!(),
+/// };
+/// entry_v.insert(10);
+/// assert!(map[&"a"] == 10 && map.len() == 1);
+///
+/// // Nonexistent key (insert and update)
+/// match map.entry("b") {
+/// Entry::Occupied(_) => unreachable!(),
+/// Entry::Vacant(view) => {
+/// let value = view.insert(2);
+/// assert_eq!(*value, 2);
+/// *value = 20;
+/// }
+/// }
+/// assert!(map[&"b"] == 20 && map.len() == 2);
+/// ```
pub struct VacantEntry<'a, K, V, S, A: Allocator + Clone = Global> {
hash: u64,
key: K,
@@ -2790,20 +4266,90 @@
}
}
-/// A view into a single entry in a map, which may either be vacant or occupied.
+/// A view into a single entry in a map, which may either be vacant or occupied,
+/// with any borrowed form of the map's key type.
+///
///
/// This `enum` is constructed from the [`entry_ref`] method on [`HashMap`].
///
+/// [`Hash`] and [`Eq`] on the borrowed form of the map's key type *must* match those
+/// for the key type. It also require that key may be constructed from the borrowed
+/// form through the [`From`] trait.
+///
/// [`HashMap`]: struct.HashMap.html
/// [`entry_ref`]: struct.HashMap.html#method.entry_ref
+/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
+/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
+/// [`From`]: https://doc.rust-lang.org/std/convert/trait.From.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{EntryRef, HashMap, OccupiedEntryRef};
+///
+/// let mut map = HashMap::new();
+/// map.extend([("a".to_owned(), 10), ("b".into(), 20), ("c".into(), 30)]);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (insert)
+/// let key = String::from("a");
+/// let entry: EntryRef<_, _, _, _> = map.entry_ref(&key);
+/// let _raw_o: OccupiedEntryRef<_, _, _, _> = entry.insert(1);
+/// assert_eq!(map.len(), 3);
+/// // Nonexistent key (insert)
+/// map.entry_ref("d").insert(4);
+///
+/// // Existing key (or_insert)
+/// let v = map.entry_ref("b").or_insert(2);
+/// assert_eq!(std::mem::replace(v, 2), 20);
+/// // Nonexistent key (or_insert)
+/// map.entry_ref("e").or_insert(5);
+///
+/// // Existing key (or_insert_with)
+/// let v = map.entry_ref("c").or_insert_with(|| 3);
+/// assert_eq!(std::mem::replace(v, 3), 30);
+/// // Nonexistent key (or_insert_with)
+/// map.entry_ref("f").or_insert_with(|| 6);
+///
+/// println!("Our HashMap: {:?}", map);
+///
+/// for (key, value) in ["a", "b", "c", "d", "e", "f"].into_iter().zip(1..=6) {
+/// assert_eq!(map[key], value)
+/// }
+/// assert_eq!(map.len(), 6);
+/// ```
pub enum EntryRef<'a, 'b, K, Q: ?Sized, V, S, A = Global>
where
A: Allocator + Clone,
{
/// An occupied entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{EntryRef, HashMap};
+ /// let mut map: HashMap<_, _> = [("a".to_owned(), 100), ("b".into(), 200)].into();
+ ///
+ /// match map.entry_ref("a") {
+ /// EntryRef::Vacant(_) => unreachable!(),
+ /// EntryRef::Occupied(_) => { }
+ /// }
+ /// ```
Occupied(OccupiedEntryRef<'a, 'b, K, Q, V, S, A>),
/// A vacant entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::{EntryRef, HashMap};
+ /// let mut map: HashMap<String, i32> = HashMap::new();
+ ///
+ /// match map.entry_ref("a") {
+ /// EntryRef::Occupied(_) => unreachable!(),
+ /// EntryRef::Vacant(_) => { }
+ /// }
+ /// ```
Vacant(VacantEntryRef<'a, 'b, K, Q, V, S, A>),
}
@@ -2848,6 +4394,43 @@
/// It is part of the [`EntryRef`] enum.
///
/// [`EntryRef`]: enum.EntryRef.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{EntryRef, HashMap, OccupiedEntryRef};
+///
+/// let mut map = HashMap::new();
+/// map.extend([("a".to_owned(), 10), ("b".into(), 20), ("c".into(), 30)]);
+///
+/// let key = String::from("a");
+/// let _entry_o: OccupiedEntryRef<_, _, _, _> = map.entry_ref(&key).insert(100);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (insert and update)
+/// match map.entry_ref("a") {
+/// EntryRef::Vacant(_) => unreachable!(),
+/// EntryRef::Occupied(mut view) => {
+/// assert_eq!(view.get(), &100);
+/// let v = view.get_mut();
+/// *v *= 10;
+/// assert_eq!(view.insert(1111), 1000);
+/// }
+/// }
+///
+/// assert_eq!(map["a"], 1111);
+/// assert_eq!(map.len(), 3);
+///
+/// // Existing key (take)
+/// match map.entry_ref("c") {
+/// EntryRef::Vacant(_) => unreachable!(),
+/// EntryRef::Occupied(view) => {
+/// assert_eq!(view.remove_entry(), ("c".to_owned(), 30));
+/// }
+/// }
+/// assert_eq!(map.get("c"), None);
+/// assert_eq!(map.len(), 2);
+/// ```
pub struct OccupiedEntryRef<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone = Global> {
hash: u64,
key: Option<KeyOrRef<'b, K, Q>>,
@@ -2889,6 +4472,32 @@
/// It is part of the [`EntryRef`] enum.
///
/// [`EntryRef`]: enum.EntryRef.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{EntryRef, HashMap, VacantEntryRef};
+///
+/// let mut map = HashMap::<String, i32>::new();
+///
+/// let entry_v: VacantEntryRef<_, _, _, _> = match map.entry_ref("a") {
+/// EntryRef::Vacant(view) => view,
+/// EntryRef::Occupied(_) => unreachable!(),
+/// };
+/// entry_v.insert(10);
+/// assert!(map["a"] == 10 && map.len() == 1);
+///
+/// // Nonexistent key (insert and update)
+/// match map.entry_ref("b") {
+/// EntryRef::Occupied(_) => unreachable!(),
+/// EntryRef::Vacant(view) => {
+/// let value = view.insert(2);
+/// assert_eq!(*value, 2);
+/// *value = 20;
+/// }
+/// }
+/// assert!(map["b"] == 20 && map.len() == 2);
+/// ```
pub struct VacantEntryRef<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone = Global> {
hash: u64,
key: KeyOrRef<'b, K, Q>,
@@ -2906,6 +4515,27 @@
/// The error returned by [`try_insert`](HashMap::try_insert) when the key already exists.
///
/// Contains the occupied entry, and the value that was not inserted.
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_map::{HashMap, OccupiedError};
+///
+/// let mut map: HashMap<_, _> = [("a", 10), ("b", 20)].into();
+///
+/// // try_insert method returns mutable reference to the value if keys are vacant,
+/// // but if the map did have key present, nothing is updated, and the provided
+/// // value is returned inside `Err(_)` variant
+/// match map.try_insert("a", 100) {
+/// Err(OccupiedError { mut entry, value }) => {
+/// assert_eq!(entry.key(), &"a");
+/// assert_eq!(value, 100);
+/// assert_eq!(entry.insert(100), 10)
+/// }
+/// _ => unreachable!(),
+/// }
+/// assert_eq!(map[&"a"], 100);
+/// ```
pub struct OccupiedError<'a, K, V, S, A: Allocator + Clone = Global> {
/// The entry in the map that was already occupied.
pub entry: OccupiedEntry<'a, K, V, S, A>,
@@ -2941,6 +4571,28 @@
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
+ /// Creates an iterator over the entries of a `HashMap` in arbitrary order.
+ /// The iterator element type is `(&'a K, &'a V)`.
+ ///
+ /// Return the same `Iter` struct as by the [`iter`] method on [`HashMap`].
+ ///
+ /// [`iter`]: struct.HashMap.html#method.iter
+ /// [`HashMap`]: struct.HashMap.html
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ /// let map_one: HashMap<_, _> = [(1, "a"), (2, "b"), (3, "c")].into();
+ /// let mut map_two = HashMap::new();
+ ///
+ /// for (key, value) in &map_one {
+ /// println!("Key: {}, Value: {}", key, value);
+ /// map_two.insert_unique_unchecked(*key, *value);
+ /// }
+ ///
+ /// assert_eq!(map_one, map_two);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
fn into_iter(self) -> Iter<'a, K, V> {
self.iter()
@@ -2951,6 +4603,33 @@
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
+ /// Creates an iterator over the entries of a `HashMap` in arbitrary order
+ /// with mutable references to the values. The iterator element type is
+ /// `(&'a K, &'a mut V)`.
+ ///
+ /// Return the same `IterMut` struct as by the [`iter_mut`] method on
+ /// [`HashMap`].
+ ///
+ /// [`iter_mut`]: struct.HashMap.html#method.iter_mut
+ /// [`HashMap`]: struct.HashMap.html
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ /// let mut map: HashMap<_, _> = [("a", 1), ("b", 2), ("c", 3)].into();
+ ///
+ /// for (key, value) in &mut map {
+ /// println!("Key: {}, Value: {}", key, value);
+ /// *value *= 2;
+ /// }
+ ///
+ /// let mut vec = map.iter().collect::<Vec<_>>();
+ /// // The `Iter` iterator produces items in arbitrary order, so the
+ /// // items must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [(&"a", &2), (&"b", &4), (&"c", &6)]);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
fn into_iter(self) -> IterMut<'a, K, V> {
self.iter_mut()
@@ -2970,13 +4649,14 @@
/// ```
/// use hashbrown::HashMap;
///
- /// let mut map = HashMap::new();
- /// map.insert("a", 1);
- /// map.insert("b", 2);
- /// map.insert("c", 3);
+ /// let map: HashMap<_, _> = [("a", 1), ("b", 2), ("c", 3)].into();
///
/// // Not possible with .iter()
- /// let vec: Vec<(&str, i32)> = map.into_iter().collect();
+ /// let mut vec: Vec<(&str, i32)> = map.into_iter().collect();
+ /// // The `IntoIter` iterator produces items in arbitrary order, so
+ /// // the items must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [("a", 1), ("b", 2), ("c", 3)]);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
fn into_iter(self) -> IntoIter<K, V, A> {
@@ -3226,9 +4906,11 @@
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
///
+ /// // nonexistent key
/// map.entry("poneyland").or_insert(3);
/// assert_eq!(map["poneyland"], 3);
///
+ /// // existing key
/// *map.entry("poneyland").or_insert(10) *= 2;
/// assert_eq!(map["poneyland"], 6);
/// ```
@@ -3252,12 +4934,15 @@
/// ```
/// use hashbrown::HashMap;
///
- /// let mut map: HashMap<&str, String> = HashMap::new();
- /// let s = "hoho".to_string();
+ /// let mut map: HashMap<&str, u32> = HashMap::new();
///
- /// map.entry("poneyland").or_insert_with(|| s);
+ /// // nonexistent key
+ /// map.entry("poneyland").or_insert_with(|| 3);
+ /// assert_eq!(map["poneyland"], 3);
///
- /// assert_eq!(map["poneyland"], "hoho".to_string());
+ /// // existing key
+ /// *map.entry("poneyland").or_insert_with(|| 10) *= 2;
+ /// assert_eq!(map["poneyland"], 6);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
@@ -3285,9 +4970,13 @@
///
/// let mut map: HashMap<&str, usize> = HashMap::new();
///
+ /// // nonexistent key
/// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
- ///
/// assert_eq!(map["poneyland"], 9);
+ ///
+ /// // existing key
+ /// *map.entry("poneyland").or_insert_with_key(|key| key.chars().count() * 10) *= 2;
+ /// assert_eq!(map["poneyland"], 18);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V
@@ -3312,7 +5001,11 @@
/// use hashbrown::HashMap;
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// map.entry("poneyland").or_insert(3);
+ /// // existing key
/// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+ /// // nonexistent key
+ /// assert_eq!(map.entry("horseland").key(), &"horseland");
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn key(&self) -> &K {
@@ -3432,9 +5125,15 @@
/// use hashbrown::HashMap;
///
/// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
- /// map.entry("poneyland").or_default();
///
+ /// // nonexistent key
+ /// map.entry("poneyland").or_default();
/// assert_eq!(map["poneyland"], None);
+ ///
+ /// map.insert("horseland", Some(3));
+ ///
+ /// // existing key
+ /// assert_eq!(map.entry("horseland").or_default(), &mut Some(3));
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn or_default(self) -> &'a mut V
@@ -3455,11 +5154,15 @@
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
+ /// use hashbrown::hash_map::{Entry, HashMap};
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
/// map.entry("poneyland").or_insert(12);
- /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
+ ///
+ /// match map.entry("poneyland") {
+ /// Entry::Vacant(_) => panic!(),
+ /// Entry::Occupied(entry) => assert_eq!(entry.key(), &"poneyland"),
+ /// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn key(&self) -> &K {
@@ -3467,6 +5170,7 @@
}
/// Take the ownership of the key and value from the map.
+ /// Keeps the allocated memory for reuse.
///
/// # Examples
///
@@ -3475,14 +5179,20 @@
/// use hashbrown::hash_map::Entry;
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// // The map is empty
+ /// assert!(map.is_empty() && map.capacity() == 0);
+ ///
/// map.entry("poneyland").or_insert(12);
+ /// let capacity_before_remove = map.capacity();
///
/// if let Entry::Occupied(o) = map.entry("poneyland") {
/// // We delete the entry from the map.
- /// o.remove_entry();
+ /// assert_eq!(o.remove_entry(), ("poneyland", 12));
/// }
///
/// assert_eq!(map.contains_key("poneyland"), false);
+ /// // Now map hold none elements but capacity is equal to the old one
+ /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove_entry(self) -> (K, V) {
@@ -3500,8 +5210,9 @@
/// let mut map: HashMap<&str, u32> = HashMap::new();
/// map.entry("poneyland").or_insert(12);
///
- /// if let Entry::Occupied(o) = map.entry("poneyland") {
- /// assert_eq!(o.get(), &12);
+ /// match map.entry("poneyland") {
+ /// Entry::Vacant(_) => panic!(),
+ /// Entry::Occupied(entry) => assert_eq!(entry.get(), &12),
/// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
@@ -3551,16 +5262,19 @@
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::Entry;
+ /// use hashbrown::hash_map::{Entry, HashMap};
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
/// map.entry("poneyland").or_insert(12);
///
/// assert_eq!(map["poneyland"], 12);
- /// if let Entry::Occupied(o) = map.entry("poneyland") {
- /// *o.into_mut() += 10;
+ ///
+ /// let value: &mut u32;
+ /// match map.entry("poneyland") {
+ /// Entry::Occupied(entry) => value = entry.into_mut(),
+ /// Entry::Vacant(_) => panic!(),
/// }
+ /// *value += 10;
///
/// assert_eq!(map["poneyland"], 22);
/// ```
@@ -3587,13 +5301,12 @@
/// assert_eq!(map["poneyland"], 15);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(&mut self, mut value: V) -> V {
- let old_value = self.get_mut();
- mem::swap(&mut value, old_value);
- value
+ pub fn insert(&mut self, value: V) -> V {
+ mem::replace(self.get_mut(), value)
}
/// Takes the value out of the entry, and returns it.
+ /// Keeps the allocated memory for reuse.
///
/// # Examples
///
@@ -3602,13 +5315,19 @@
/// use hashbrown::hash_map::Entry;
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
+ /// // The map is empty
+ /// assert!(map.is_empty() && map.capacity() == 0);
+ ///
/// map.entry("poneyland").or_insert(12);
+ /// let capacity_before_remove = map.capacity();
///
/// if let Entry::Occupied(o) = map.entry("poneyland") {
/// assert_eq!(o.remove(), 12);
/// }
///
/// assert_eq!(map.contains_key("poneyland"), false);
+ /// // Now map hold none elements but capacity is equal to the old one
+ /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove(self) -> V {
@@ -3625,19 +5344,26 @@
/// # Examples
///
/// ```
- /// use hashbrown::hash_map::{Entry, HashMap};
- /// use std::rc::Rc;
+ /// use hashbrown::hash_map::{Entry, HashMap};
+ /// use std::rc::Rc;
///
- /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
- /// map.insert(Rc::new("Stringthing".to_string()), 15);
+ /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
+ /// let key_one = Rc::new("Stringthing".to_string());
+ /// let key_two = Rc::new("Stringthing".to_string());
///
- /// let my_key = Rc::new("Stringthing".to_string());
+ /// map.insert(key_one.clone(), 15);
+ /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
///
- /// if let Entry::Occupied(entry) = map.entry(my_key) {
- /// // Also replace the key with a handle to our other key.
- /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16);
- /// }
+ /// match map.entry(key_two.clone()) {
+ /// Entry::Occupied(entry) => {
+ /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16);
+ /// assert!(Rc::ptr_eq(&key_one, &old_key) && old_value == 15);
+ /// }
+ /// Entry::Vacant(_) => panic!(),
+ /// }
///
+ /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
+ /// assert_eq!(map[&"Stringthing".to_owned()], 16);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn replace_entry(self, value: V) -> (K, V) {
@@ -3661,17 +5387,33 @@
/// use hashbrown::hash_map::{Entry, HashMap};
/// use std::rc::Rc;
///
- /// let mut map: HashMap<Rc<String>, u32> = HashMap::new();
- /// let mut known_strings: Vec<Rc<String>> = Vec::new();
+ /// let mut map: HashMap<Rc<String>, usize> = HashMap::with_capacity(6);
+ /// let mut keys_one: Vec<Rc<String>> = Vec::with_capacity(6);
+ /// let mut keys_two: Vec<Rc<String>> = Vec::with_capacity(6);
///
- /// // Initialise known strings, run program, etc.
+ /// for (value, key) in ["a", "b", "c", "d", "e", "f"].into_iter().enumerate() {
+ /// let rc_key = Rc::new(key.to_owned());
+ /// keys_one.push(rc_key.clone());
+ /// map.insert(rc_key.clone(), value);
+ /// keys_two.push(Rc::new(key.to_owned()));
+ /// }
///
- /// reclaim_memory(&mut map, &known_strings);
+ /// assert!(
+ /// keys_one.iter().all(|key| Rc::strong_count(key) == 2)
+ /// && keys_two.iter().all(|key| Rc::strong_count(key) == 1)
+ /// );
///
- /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) {
- /// for s in known_strings {
- /// if let Entry::Occupied(entry) = map.entry(s.clone()) {
- /// // Replaces the entry's key with our version of it in `known_strings`.
+ /// reclaim_memory(&mut map, &keys_two);
+ ///
+ /// assert!(
+ /// keys_one.iter().all(|key| Rc::strong_count(key) == 1)
+ /// && keys_two.iter().all(|key| Rc::strong_count(key) == 2)
+ /// );
+ ///
+ /// fn reclaim_memory(map: &mut HashMap<Rc<String>, usize>, keys: &[Rc<String>]) {
+ /// for key in keys {
+ /// if let Entry::Occupied(entry) = map.entry(key.clone()) {
+ /// // Replaces the entry's key with our version of it in `keys`.
/// entry.replace_key();
/// }
/// }
@@ -3785,13 +5527,13 @@
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::Entry;
+ /// use hashbrown::hash_map::{Entry, HashMap};
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
///
- /// if let Entry::Vacant(v) = map.entry("poneyland") {
- /// v.into_key();
+ /// match map.entry("poneyland") {
+ /// Entry::Occupied(_) => panic!(),
+ /// Entry::Vacant(v) => assert_eq!(v.into_key(), "poneyland"),
/// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
@@ -3831,7 +5573,7 @@
}
#[cfg_attr(feature = "inline-more", inline)]
- fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
+ pub(crate) fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
where
K: Hash,
S: BuildHasher,
@@ -3888,9 +5630,11 @@
///
/// let mut map: HashMap<String, u32> = HashMap::new();
///
+ /// // nonexistent key
/// map.entry_ref("poneyland").or_insert(3);
/// assert_eq!(map["poneyland"], 3);
///
+ /// // existing key
/// *map.entry_ref("poneyland").or_insert(10) *= 2;
/// assert_eq!(map["poneyland"], 6);
/// ```
@@ -3914,12 +5658,15 @@
/// ```
/// use hashbrown::HashMap;
///
- /// let mut map: HashMap<String, String> = HashMap::new();
- /// let s = "hoho".to_string();
+ /// let mut map: HashMap<String, u32> = HashMap::new();
///
- /// map.entry_ref("poneyland").or_insert_with(|| s);
+ /// // nonexistent key
+ /// map.entry_ref("poneyland").or_insert_with(|| 3);
+ /// assert_eq!(map["poneyland"], 3);
///
- /// assert_eq!(map["poneyland"], "hoho".to_string());
+ /// // existing key
+ /// *map.entry_ref("poneyland").or_insert_with(|| 10) *= 2;
+ /// assert_eq!(map["poneyland"], 6);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
@@ -3947,9 +5694,13 @@
///
/// let mut map: HashMap<String, usize> = HashMap::new();
///
+ /// // nonexistent key
/// map.entry_ref("poneyland").or_insert_with_key(|key| key.chars().count());
- ///
/// assert_eq!(map["poneyland"], 9);
+ ///
+ /// // existing key
+ /// *map.entry_ref("poneyland").or_insert_with_key(|key| key.chars().count() * 10) *= 2;
+ /// assert_eq!(map["poneyland"], 18);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn or_insert_with_key<F: FnOnce(&Q) -> V>(self, default: F) -> &'a mut V
@@ -3974,7 +5725,11 @@
/// use hashbrown::HashMap;
///
/// let mut map: HashMap<String, u32> = HashMap::new();
+ /// map.entry_ref("poneyland").or_insert(3);
+ /// // existing key
/// assert_eq!(map.entry_ref("poneyland").key(), "poneyland");
+ /// // nonexistent key
+ /// assert_eq!(map.entry_ref("horseland").key(), "horseland");
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn key(&self) -> &Q
@@ -4097,10 +5852,16 @@
/// ```
/// use hashbrown::HashMap;
///
- /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
- /// map.entry("poneyland").or_default();
+ /// let mut map: HashMap<String, Option<u32>> = HashMap::new();
///
+ /// // nonexistent key
+ /// map.entry_ref("poneyland").or_default();
/// assert_eq!(map["poneyland"], None);
+ ///
+ /// map.insert("horseland".to_string(), Some(3));
+ ///
+ /// // existing key
+ /// assert_eq!(map.entry_ref("horseland").or_default(), &mut Some(3));
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn or_default(self) -> &'a mut V
@@ -4121,11 +5882,15 @@
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
+ /// use hashbrown::hash_map::{EntryRef, HashMap};
///
/// let mut map: HashMap<String, u32> = HashMap::new();
/// map.entry_ref("poneyland").or_insert(12);
- /// assert_eq!(map.entry_ref("poneyland").key(), "poneyland");
+ ///
+ /// match map.entry_ref("poneyland") {
+ /// EntryRef::Vacant(_) => panic!(),
+ /// EntryRef::Occupied(entry) => assert_eq!(entry.key(), "poneyland"),
+ /// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn key(&self) -> &Q
@@ -4136,6 +5901,7 @@
}
/// Take the ownership of the key and value from the map.
+ /// Keeps the allocated memory for reuse.
///
/// # Examples
///
@@ -4144,14 +5910,20 @@
/// use hashbrown::hash_map::EntryRef;
///
/// let mut map: HashMap<String, u32> = HashMap::new();
+ /// // The map is empty
+ /// assert!(map.is_empty() && map.capacity() == 0);
+ ///
/// map.entry_ref("poneyland").or_insert(12);
+ /// let capacity_before_remove = map.capacity();
///
/// if let EntryRef::Occupied(o) = map.entry_ref("poneyland") {
/// // We delete the entry from the map.
- /// o.remove_entry();
+ /// assert_eq!(o.remove_entry(), ("poneyland".to_owned(), 12));
/// }
///
/// assert_eq!(map.contains_key("poneyland"), false);
+ /// // Now map hold none elements but capacity is equal to the old one
+ /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove_entry(self) -> (K, V) {
@@ -4169,8 +5941,9 @@
/// let mut map: HashMap<String, u32> = HashMap::new();
/// map.entry_ref("poneyland").or_insert(12);
///
- /// if let EntryRef::Occupied(o) = map.entry_ref("poneyland") {
- /// assert_eq!(o.get(), &12);
+ /// match map.entry_ref("poneyland") {
+ /// EntryRef::Vacant(_) => panic!(),
+ /// EntryRef::Occupied(entry) => assert_eq!(entry.get(), &12),
/// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
@@ -4220,16 +5993,17 @@
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
+ /// use hashbrown::hash_map::{EntryRef, HashMap};
///
/// let mut map: HashMap<String, u32> = HashMap::new();
/// map.entry_ref("poneyland").or_insert(12);
///
- /// assert_eq!(map["poneyland"], 12);
- /// if let EntryRef::Occupied(o) = map.entry_ref("poneyland") {
- /// *o.into_mut() += 10;
+ /// let value: &mut u32;
+ /// match map.entry_ref("poneyland") {
+ /// EntryRef::Occupied(entry) => value = entry.into_mut(),
+ /// EntryRef::Vacant(_) => panic!(),
/// }
+ /// *value += 10;
///
/// assert_eq!(map["poneyland"], 22);
/// ```
@@ -4256,13 +6030,12 @@
/// assert_eq!(map["poneyland"], 15);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(&mut self, mut value: V) -> V {
- let old_value = self.get_mut();
- mem::swap(&mut value, old_value);
- value
+ pub fn insert(&mut self, value: V) -> V {
+ mem::replace(self.get_mut(), value)
}
/// Takes the value out of the entry, and returns it.
+ /// Keeps the allocated memory for reuse.
///
/// # Examples
///
@@ -4271,13 +6044,19 @@
/// use hashbrown::hash_map::EntryRef;
///
/// let mut map: HashMap<String, u32> = HashMap::new();
+ /// // The map is empty
+ /// assert!(map.is_empty() && map.capacity() == 0);
+ ///
/// map.entry_ref("poneyland").or_insert(12);
+ /// let capacity_before_remove = map.capacity();
///
/// if let EntryRef::Occupied(o) = map.entry_ref("poneyland") {
/// assert_eq!(o.remove(), 12);
/// }
///
/// assert_eq!(map.contains_key("poneyland"), false);
+ /// // Now map hold none elements but capacity is equal to the old one
+ /// assert!(map.len() == 0 && map.capacity() == capacity_before_remove);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn remove(self) -> V {
@@ -4298,13 +6077,21 @@
/// use std::rc::Rc;
///
/// let mut map: HashMap<Rc<str>, u32> = HashMap::new();
- /// map.insert(Rc::from("Stringthing"), 15);
+ /// let key: Rc<str> = Rc::from("Stringthing");
///
- /// if let EntryRef::Occupied(entry) = map.entry_ref("Stringthing") {
- /// // Also replace the key with a handle to our other key.
- /// let (old_key, old_value): (Rc<str>, u32) = entry.replace_entry(16);
+ /// map.insert(key.clone(), 15);
+ /// assert_eq!(Rc::strong_count(&key), 2);
+ ///
+ /// match map.entry_ref("Stringthing") {
+ /// EntryRef::Occupied(entry) => {
+ /// let (old_key, old_value): (Rc<str>, u32) = entry.replace_entry(16);
+ /// assert!(Rc::ptr_eq(&key, &old_key) && old_value == 15);
+ /// }
+ /// EntryRef::Vacant(_) => panic!(),
/// }
///
+ /// assert_eq!(Rc::strong_count(&key), 1);
+ /// assert_eq!(map["Stringthing"], 16);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn replace_entry(self, value: V) -> (K, V)
@@ -4331,17 +6118,27 @@
/// use hashbrown::hash_map::{EntryRef, HashMap};
/// use std::rc::Rc;
///
- /// let mut map: HashMap<Rc<str>, u32> = HashMap::new();
- /// let mut known_strings: Vec<Rc<str>> = Vec::new();
+ /// let mut map: HashMap<Rc<str>, usize> = HashMap::with_capacity(6);
+ /// let mut keys: Vec<Rc<str>> = Vec::with_capacity(6);
///
- /// // Initialise known strings, run program, etc.
+ /// for (value, key) in ["a", "b", "c", "d", "e", "f"].into_iter().enumerate() {
+ /// let rc_key: Rc<str> = Rc::from(key);
+ /// keys.push(rc_key.clone());
+ /// map.insert(rc_key.clone(), value);
+ /// }
///
- /// reclaim_memory(&mut map, &known_strings);
+ /// assert!(keys.iter().all(|key| Rc::strong_count(key) == 2));
///
- /// fn reclaim_memory(map: &mut HashMap<Rc<str>, u32>, known_strings: &[Rc<str>] ) {
- /// for s in known_strings {
- /// if let EntryRef::Occupied(entry) = map.entry_ref(s.as_ref()) {
- /// // Replaces the entry's key with our version of it in `known_strings`.
+ /// // It doesn't matter that we kind of use a vector with the same keys,
+ /// // because all keys will be newly created from the references
+ /// reclaim_memory(&mut map, &keys);
+ ///
+ /// assert!(keys.iter().all(|key| Rc::strong_count(key) == 1));
+ ///
+ /// fn reclaim_memory(map: &mut HashMap<Rc<str>, usize>, keys: &[Rc<str>]) {
+ /// for key in keys {
+ /// if let EntryRef::Occupied(entry) = map.entry_ref(key.as_ref()) {
+ /// /// Replaces the entry's key with our version of it in `keys`.
/// entry.replace_key();
/// }
/// }
@@ -4463,14 +6260,14 @@
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
+ /// use hashbrown::hash_map::{EntryRef, HashMap};
///
/// let mut map: HashMap<String, u32> = HashMap::new();
/// let key: &str = "poneyland";
///
- /// if let EntryRef::Vacant(v) = map.entry_ref(key) {
- /// v.into_key();
+ /// match map.entry_ref(key) {
+ /// EntryRef::Occupied(_) => panic!(),
+ /// EntryRef::Vacant(v) => assert_eq!(v.into_key(), "poneyland".to_owned()),
/// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
@@ -4559,6 +6356,41 @@
S: BuildHasher,
A: Allocator + Clone,
{
+ /// Inserts all new key-values from the iterator to existing `HashMap<K, V, S, A>`.
+ /// Replace values with existing keys with new values returned from the iterator.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, 100);
+ ///
+ /// let some_iter = [(1, 1), (2, 2)].into_iter();
+ /// map.extend(some_iter);
+ /// // Replace values with existing keys with new values returned from the iterator.
+ /// // So that the map.get(&1) doesn't return Some(&100).
+ /// assert_eq!(map.get(&1), Some(&1));
+ ///
+ /// let some_vec: Vec<_> = vec![(3, 3), (4, 4)];
+ /// map.extend(some_vec);
+ ///
+ /// let some_arr = [(5, 5), (6, 6)];
+ /// map.extend(some_arr);
+ /// let old_map_len = map.len();
+ ///
+ /// // You can also extend from another HashMap
+ /// let mut new_map = HashMap::new();
+ /// new_map.extend(map);
+ /// assert_eq!(new_map.len(), old_map_len);
+ ///
+ /// let mut vec: Vec<_> = new_map.into_iter().collect();
+ /// // The `IntoIter` iterator produces items in arbitrary order, so the
+ /// // items must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
// Keys may be already present or show multiple times in the iterator.
@@ -4599,6 +6431,8 @@
}
}
+/// Inserts all new key-values from the iterator and replaces values with existing
+/// keys with new values returned from the iterator.
impl<'a, K, V, S, A> Extend<(&'a K, &'a V)> for HashMap<K, V, S, A>
where
K: Eq + Hash + Copy,
@@ -4606,6 +6440,44 @@
S: BuildHasher,
A: Allocator + Clone,
{
+ /// Inserts all new key-values from the iterator to existing `HashMap<K, V, S, A>`.
+ /// Replace values with existing keys with new values returned from the iterator.
+ /// The keys and values must implement [`Copy`] trait.
+ ///
+ /// [`Copy`]: https://doc.rust-lang.org/core/marker/trait.Copy.html
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, 100);
+ ///
+ /// let arr = [(1, 1), (2, 2)];
+ /// let some_iter = arr.iter().map(|&(k, v)| (k, v));
+ /// map.extend(some_iter);
+ /// // Replace values with existing keys with new values returned from the iterator.
+ /// // So that the map.get(&1) doesn't return Some(&100).
+ /// assert_eq!(map.get(&1), Some(&1));
+ ///
+ /// let some_vec: Vec<_> = vec![(3, 3), (4, 4)];
+ /// map.extend(some_vec.iter().map(|&(k, v)| (k, v)));
+ ///
+ /// let some_arr = [(5, 5), (6, 6)];
+ /// map.extend(some_arr.iter().map(|&(k, v)| (k, v)));
+ ///
+ /// // You can also extend from another HashMap
+ /// let mut new_map = HashMap::new();
+ /// new_map.extend(&map);
+ /// assert_eq!(new_map, map);
+ ///
+ /// let mut vec: Vec<_> = new_map.into_iter().collect();
+ /// // The `IntoIter` iterator produces items in arbitrary order, so the
+ /// // items must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]);
+ /// ```
#[cfg_attr(feature = "inline-more", inline)]
fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
@@ -4624,6 +6496,66 @@
}
}
+/// Inserts all new key-values from the iterator and replaces values with existing
+/// keys with new values returned from the iterator.
+impl<'a, K, V, S, A> Extend<&'a (K, V)> for HashMap<K, V, S, A>
+where
+ K: Eq + Hash + Copy,
+ V: Copy,
+ S: BuildHasher,
+ A: Allocator + Clone,
+{
+ /// Inserts all new key-values from the iterator to existing `HashMap<K, V, S, A>`.
+ /// Replace values with existing keys with new values returned from the iterator.
+ /// The keys and values must implement [`Copy`] trait.
+ ///
+ /// [`Copy`]: https://doc.rust-lang.org/core/marker/trait.Copy.html
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_map::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// map.insert(1, 100);
+ ///
+ /// let arr = [(1, 1), (2, 2)];
+ /// let some_iter = arr.iter();
+ /// map.extend(some_iter);
+ /// // Replace values with existing keys with new values returned from the iterator.
+ /// // So that the map.get(&1) doesn't return Some(&100).
+ /// assert_eq!(map.get(&1), Some(&1));
+ ///
+ /// let some_vec: Vec<_> = vec![(3, 3), (4, 4)];
+ /// map.extend(&some_vec);
+ ///
+ /// let some_arr = [(5, 5), (6, 6)];
+ /// map.extend(&some_arr);
+ ///
+ /// let mut vec: Vec<_> = map.into_iter().collect();
+ /// // The `IntoIter` iterator produces items in arbitrary order, so the
+ /// // items must be sorted to test them against a sorted array.
+ /// vec.sort_unstable();
+ /// assert_eq!(vec, [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)]);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn extend<T: IntoIterator<Item = &'a (K, V)>>(&mut self, iter: T) {
+ self.extend(iter.into_iter().map(|&(key, value)| (key, value)));
+ }
+
+ #[inline]
+ #[cfg(feature = "nightly")]
+ fn extend_one(&mut self, &(k, v): &'a (K, V)) {
+ self.insert(k, v);
+ }
+
+ #[inline]
+ #[cfg(feature = "nightly")]
+ fn extend_reserve(&mut self, additional: usize) {
+ Extend::<(K, V)>::extend_reserve(self, additional);
+ }
+}
+
#[allow(dead_code)]
fn assert_covariance() {
fn map_key<'new>(v: HashMap<&'static str, u8>) -> HashMap<&'new str, u8> {
@@ -5611,7 +7543,7 @@
}
#[test]
- fn test_extend_ref() {
+ fn test_extend_ref_k_ref_v() {
let mut a = HashMap::new();
a.insert(1, "one");
let mut b = HashMap::new();
@@ -5627,6 +7559,37 @@
}
#[test]
+ fn test_extend_ref_kv_tuple() {
+ use std::ops::AddAssign;
+ let mut a = HashMap::new();
+ a.insert(0, 0);
+
+ fn create_arr<T: AddAssign<T> + Copy, const N: usize>(start: T, step: T) -> [(T, T); N] {
+ let mut outs: [(T, T); N] = [(start, start); N];
+ let mut element = step;
+ outs.iter_mut().skip(1).for_each(|(k, v)| {
+ *k += element;
+ *v += element;
+ element += step;
+ });
+ outs
+ }
+
+ let for_iter: Vec<_> = (0..100).map(|i| (i, i)).collect();
+ let iter = for_iter.iter();
+ let vec: Vec<_> = (100..200).map(|i| (i, i)).collect();
+ a.extend(iter);
+ a.extend(&vec);
+ a.extend(&create_arr::<i32, 100>(200, 1));
+
+ assert_eq!(a.len(), 300);
+
+ for item in 0..300 {
+ assert_eq!(a[&item], item);
+ }
+ }
+
+ #[test]
fn test_capacity_not_less_than_len() {
let mut a = HashMap::new();
let mut item = 0;
@@ -6219,15 +8182,15 @@
assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv);
match map.raw_entry_mut().from_key(&k) {
- Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
+ Occupied(o) => assert_eq!(Some(o.get_key_value()), kv),
Vacant(_) => assert_eq!(v, None),
}
match map.raw_entry_mut().from_key_hashed_nocheck(hash, &k) {
- Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
+ Occupied(o) => assert_eq!(Some(o.get_key_value()), kv),
Vacant(_) => assert_eq!(v, None),
}
match map.raw_entry_mut().from_hash(hash, |q| *q == k) {
- Occupied(mut o) => assert_eq!(Some(o.get_key_value()), kv),
+ Occupied(o) => assert_eq!(Some(o.get_key_value()), kv),
Vacant(_) => assert_eq!(v, None),
}
}
@@ -6398,4 +8361,48 @@
let ys = map.get_many_key_value_mut(["baz", "baz"]);
assert_eq!(ys, None);
}
+
+ #[test]
+ #[should_panic = "panic in drop"]
+ fn test_clone_from_double_drop() {
+ #[derive(Clone)]
+ struct CheckedDrop {
+ panic_in_drop: bool,
+ dropped: bool,
+ }
+ impl Drop for CheckedDrop {
+ fn drop(&mut self) {
+ if self.panic_in_drop {
+ self.dropped = true;
+ panic!("panic in drop");
+ }
+ if self.dropped {
+ panic!("double drop");
+ }
+ self.dropped = true;
+ }
+ }
+ const DISARMED: CheckedDrop = CheckedDrop {
+ panic_in_drop: false,
+ dropped: false,
+ };
+ const ARMED: CheckedDrop = CheckedDrop {
+ panic_in_drop: true,
+ dropped: false,
+ };
+
+ let mut map1 = HashMap::new();
+ map1.insert(1, DISARMED);
+ map1.insert(2, DISARMED);
+ map1.insert(3, DISARMED);
+ map1.insert(4, DISARMED);
+
+ let mut map2 = HashMap::new();
+ map2.insert(1, DISARMED);
+ map2.insert(2, ARMED);
+ map2.insert(3, DISARMED);
+ map2.insert(4, DISARMED);
+
+ map2.clone_from(&map1);
+ }
}
diff --git a/src/raw/alloc.rs b/src/raw/alloc.rs
index 76fe1e9..ba09ea9 100644
--- a/src/raw/alloc.rs
+++ b/src/raw/alloc.rs
@@ -8,10 +8,10 @@
#[allow(clippy::map_err_ignore)]
pub fn do_alloc<A: Allocator>(alloc: &A, layout: Layout) -> Result<NonNull<u8>, ()> {
- alloc
- .allocate(layout)
- .map(|ptr| ptr.as_non_null_ptr())
- .map_err(|_| ())
+ match alloc.allocate(layout) {
+ Ok(ptr) => Ok(ptr.as_non_null_ptr()),
+ Err(_) => Err(()),
+ }
}
#[cfg(feature = "bumpalo")]
diff --git a/src/raw/mod.rs b/src/raw/mod.rs
index 5fe0a72..211b818 100644
--- a/src/raw/mod.rs
+++ b/src/raw/mod.rs
@@ -1,5 +1,5 @@
use crate::alloc::alloc::{handle_alloc_error, Layout};
-use crate::scopeguard::guard;
+use crate::scopeguard::{guard, ScopeGuard};
use crate::TryReserveError;
use core::iter::FusedIterator;
use core::marker::PhantomData;
@@ -69,16 +69,10 @@
b
}
-#[cfg(feature = "nightly")]
#[inline]
unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
to.offset_from(from) as usize
}
-#[cfg(not(feature = "nightly"))]
-#[inline]
-unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
- (to as usize - from as usize) / mem::size_of::<T>()
-}
/// Whether memory allocation errors should return an error or abort.
#[derive(Copy, Clone)]
@@ -1608,25 +1602,27 @@
Self::new_in(self.table.alloc.clone())
} else {
unsafe {
- let mut new_table = ManuallyDrop::new(
- // Avoid `Result::ok_or_else` because it bloats LLVM IR.
- match Self::new_uninitialized(
- self.table.alloc.clone(),
- self.table.buckets(),
- Fallibility::Infallible,
- ) {
- Ok(table) => table,
- Err(_) => hint::unreachable_unchecked(),
- },
- );
+ // Avoid `Result::ok_or_else` because it bloats LLVM IR.
+ let new_table = match Self::new_uninitialized(
+ self.table.alloc.clone(),
+ self.table.buckets(),
+ Fallibility::Infallible,
+ ) {
+ Ok(table) => table,
+ Err(_) => hint::unreachable_unchecked(),
+ };
- new_table.clone_from_spec(self, |new_table| {
- // We need to free the memory allocated for the new table.
+ // If cloning fails then we need to free the allocation for the
+ // new table. However we don't run its drop since its control
+ // bytes are not initialized yet.
+ let mut guard = guard(ManuallyDrop::new(new_table), |new_table| {
new_table.free_buckets();
});
- // Return the newly created table.
- ManuallyDrop::into_inner(new_table)
+ guard.clone_from_spec(self);
+
+ // Disarm the scope guard and return the newly created table.
+ ManuallyDrop::into_inner(ScopeGuard::into_inner(guard))
}
}
}
@@ -1636,19 +1632,30 @@
*self = Self::new_in(self.table.alloc.clone());
} else {
unsafe {
- // First, drop all our elements without clearing the control bytes.
- self.drop_elements();
+ // Make sure that if any panics occurs, we clear the table and
+ // leave it in an empty state.
+ let mut self_ = guard(self, |self_| {
+ self_.clear_no_drop();
+ });
+
+ // First, drop all our elements without clearing the control
+ // bytes. If this panics then the scope guard will clear the
+ // table, leaking any elements that were not dropped yet.
+ //
+ // This leak is unavoidable: we can't try dropping more elements
+ // since this could lead to another panic and abort the process.
+ self_.drop_elements();
// If necessary, resize our table to match the source.
- if self.buckets() != source.buckets() {
+ if self_.buckets() != source.buckets() {
// Skip our drop by using ptr::write.
- if !self.table.is_empty_singleton() {
- self.free_buckets();
+ if !self_.table.is_empty_singleton() {
+ self_.free_buckets();
}
- (self as *mut Self).write(
+ (&mut **self_ as *mut Self).write(
// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
match Self::new_uninitialized(
- self.table.alloc.clone(),
+ self_.table.alloc.clone(),
source.buckets(),
Fallibility::Infallible,
) {
@@ -1658,10 +1665,10 @@
);
}
- self.clone_from_spec(source, |self_| {
- // We need to leave the table in an empty state.
- self_.clear_no_drop();
- });
+ self_.clone_from_spec(source);
+
+ // Disarm the scope guard if cloning was successful.
+ ScopeGuard::into_inner(self_);
}
}
}
@@ -1669,20 +1676,20 @@
/// Specialization of `clone_from` for `Copy` types
trait RawTableClone {
- unsafe fn clone_from_spec(&mut self, source: &Self, on_panic: impl FnMut(&mut Self));
+ unsafe fn clone_from_spec(&mut self, source: &Self);
}
impl<T: Clone, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
default_fn! {
#[cfg_attr(feature = "inline-more", inline)]
- unsafe fn clone_from_spec(&mut self, source: &Self, on_panic: impl FnMut(&mut Self)) {
- self.clone_from_impl(source, on_panic);
+ unsafe fn clone_from_spec(&mut self, source: &Self) {
+ self.clone_from_impl(source);
}
}
}
#[cfg(feature = "nightly")]
impl<T: Copy, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
- unsafe fn clone_from_spec(&mut self, source: &Self, _on_panic: impl FnMut(&mut Self)) {
+ unsafe fn clone_from_spec(&mut self, source: &Self) {
source
.table
.ctrl(0)
@@ -1697,9 +1704,12 @@
}
impl<T: Clone, A: Allocator + Clone> RawTable<T, A> {
- /// Common code for clone and clone_from. Assumes `self.buckets() == source.buckets()`.
+ /// Common code for clone and clone_from. Assumes:
+ /// - `self.buckets() == source.buckets()`.
+ /// - Any existing elements have been dropped.
+ /// - The control bytes are not initialized yet.
#[cfg_attr(feature = "inline-more", inline)]
- unsafe fn clone_from_impl(&mut self, source: &Self, mut on_panic: impl FnMut(&mut Self)) {
+ unsafe fn clone_from_impl(&mut self, source: &Self) {
// Copy the control bytes unchanged. We do this in a single pass
source
.table
@@ -1717,11 +1727,6 @@
}
}
}
-
- // Depending on whether we were called from clone or clone_from, we
- // either need to free the memory for the destination table or just
- // clear the control bytes.
- on_panic(self_);
});
for from in source.iter() {
@@ -1913,6 +1918,32 @@
}
}
}
+
+ /// # Safety
+ /// If DO_CHECK_PTR_RANGE is false, caller must ensure that we never try to iterate
+ /// after yielding all elements.
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn next_impl<const DO_CHECK_PTR_RANGE: bool>(&mut self) -> Option<Bucket<T>> {
+ loop {
+ if let Some(index) = self.current_group.lowest_set_bit() {
+ self.current_group = self.current_group.remove_lowest_bit();
+ return Some(self.data.next_n(index));
+ }
+
+ if DO_CHECK_PTR_RANGE && self.next_ctrl >= self.end {
+ return None;
+ }
+
+ // We might read past self.end up to the next group boundary,
+ // but this is fine because it only occurs on tables smaller
+ // than the group size where the trailing control bytes are all
+ // EMPTY. On larger tables self.end is guaranteed to be aligned
+ // to the group size (since tables are power-of-two sized).
+ self.current_group = Group::load_aligned(self.next_ctrl).match_full();
+ self.data = self.data.next_n(Group::WIDTH);
+ self.next_ctrl = self.next_ctrl.add(Group::WIDTH);
+ }
+ }
}
// We make raw iterators unconditionally Send and Sync, and let the PhantomData
@@ -1938,25 +1969,8 @@
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<Bucket<T>> {
unsafe {
- loop {
- if let Some(index) = self.current_group.lowest_set_bit() {
- self.current_group = self.current_group.remove_lowest_bit();
- return Some(self.data.next_n(index));
- }
-
- if self.next_ctrl >= self.end {
- return None;
- }
-
- // We might read past self.end up to the next group boundary,
- // but this is fine because it only occurs on tables smaller
- // than the group size where the trailing control bytes are all
- // EMPTY. On larger tables self.end is guaranteed to be aligned
- // to the group size (since tables are power-of-two sized).
- self.current_group = Group::load_aligned(self.next_ctrl).match_full();
- self.data = self.data.next_n(Group::WIDTH);
- self.next_ctrl = self.next_ctrl.add(Group::WIDTH);
- }
+ // SAFETY: We set checker flag to true.
+ self.next_impl::<true>()
}
}
@@ -2134,16 +2148,22 @@
#[cfg_attr(feature = "inline-more", inline)]
fn next(&mut self) -> Option<Bucket<T>> {
- if let Some(b) = self.iter.next() {
- self.items -= 1;
- Some(b)
- } else {
- // We don't check against items == 0 here to allow the
- // compiler to optimize away the item count entirely if the
- // iterator length is never queried.
- debug_assert_eq!(self.items, 0);
- None
+ // Inner iterator iterates over buckets
+ // so it can do unnecessary work if we already yielded all items.
+ if self.items == 0 {
+ return None;
}
+
+ let nxt = unsafe {
+ // SAFETY: We check number of items to yield using `items` field.
+ self.iter.next_impl::<false>()
+ };
+
+ if nxt.is_some() {
+ self.items -= 1;
+ }
+
+ nxt
}
#[inline]
diff --git a/src/rustc_entry.rs b/src/rustc_entry.rs
index 465db47..2e84595 100644
--- a/src/rustc_entry.rs
+++ b/src/rustc_entry.rs
@@ -56,10 +56,10 @@
/// A view into a single entry in a map, which may either be vacant or occupied.
///
-/// This `enum` is constructed from the [`entry`] method on [`HashMap`].
+/// This `enum` is constructed from the [`rustc_entry`] method on [`HashMap`].
///
/// [`HashMap`]: struct.HashMap.html
-/// [`entry`]: struct.HashMap.html#method.rustc_entry
+/// [`rustc_entry`]: struct.HashMap.html#method.rustc_entry
pub enum RustcEntry<'a, K, V, A = Global>
where
A: Allocator + Clone,
@@ -145,7 +145,7 @@
/// use hashbrown::HashMap;
///
/// let mut map: HashMap<&str, u32> = HashMap::new();
- /// let entry = map.entry("horseyland").insert(37);
+ /// let entry = map.rustc_entry("horseyland").insert(37);
///
/// assert_eq!(entry.key(), &"horseyland");
/// ```
@@ -431,10 +431,8 @@
/// assert_eq!(map["poneyland"], 15);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(&mut self, mut value: V) -> V {
- let old_value = self.get_mut();
- mem::swap(&mut value, old_value);
- value
+ pub fn insert(&mut self, value: V) -> V {
+ mem::replace(self.get_mut(), value)
}
/// Takes the value out of the entry, and returns it.
diff --git a/src/scopeguard.rs b/src/scopeguard.rs
index ccdc0c5..f85e6ab 100644
--- a/src/scopeguard.rs
+++ b/src/scopeguard.rs
@@ -1,5 +1,9 @@
// Extracted from the scopeguard crate
-use core::ops::{Deref, DerefMut};
+use core::{
+ mem,
+ ops::{Deref, DerefMut},
+ ptr,
+};
pub struct ScopeGuard<T, F>
where
@@ -17,6 +21,27 @@
ScopeGuard { dropfn, value }
}
+impl<T, F> ScopeGuard<T, F>
+where
+ F: FnMut(&mut T),
+{
+ #[inline]
+ pub fn into_inner(guard: Self) -> T {
+ // Cannot move out of Drop-implementing types, so
+ // ptr::read the value and forget the guard.
+ unsafe {
+ let value = ptr::read(&guard.value);
+ // read the closure so that it is dropped, and assign it to a local
+ // variable to ensure that it is only dropped after the guard has
+ // been forgotten. (In case the Drop impl of the closure, or that
+ // of any consumed captured variable, panics).
+ let _dropfn = ptr::read(&guard.dropfn);
+ mem::forget(guard);
+ value
+ }
+ }
+}
+
impl<T, F> Deref for ScopeGuard<T, F>
where
F: FnMut(&mut T),
diff --git a/src/set.rs b/src/set.rs
index bb83054..2a4dcea 100644
--- a/src/set.rs
+++ b/src/set.rs
@@ -902,6 +902,47 @@
.0
}
+ /// Gets the given value's corresponding entry in the set for in-place manipulation.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_set::Entry::*;
+ ///
+ /// let mut singles = HashSet::new();
+ /// let mut dupes = HashSet::new();
+ ///
+ /// for ch in "a short treatise on fungi".chars() {
+ /// if let Vacant(dupe_entry) = dupes.entry(ch) {
+ /// // We haven't already seen a duplicate, so
+ /// // check if we've at least seen it once.
+ /// match singles.entry(ch) {
+ /// Vacant(single_entry) => {
+ /// // We found a new character for the first time.
+ /// single_entry.insert()
+ /// }
+ /// Occupied(single_entry) => {
+ /// // We've already seen this once, "move" it to dupes.
+ /// single_entry.remove();
+ /// dupe_entry.insert();
+ /// }
+ /// }
+ /// }
+ /// }
+ ///
+ /// assert!(!singles.contains(&'t') && dupes.contains(&'t'));
+ /// assert!(singles.contains(&'u') && !dupes.contains(&'u'));
+ /// assert!(!singles.contains(&'v') && !dupes.contains(&'v'));
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn entry(&mut self, value: T) -> Entry<'_, T, S, A> {
+ match self.map.entry(value) {
+ map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
+ map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
+ }
+ }
+
/// Returns `true` if `self` has no elements in common with `other`.
/// This is equivalent to checking for an empty intersection.
///
@@ -1846,6 +1887,406 @@
}
}
+/// A view into a single entry in a set, which may either be vacant or occupied.
+///
+/// This `enum` is constructed from the [`entry`] method on [`HashSet`].
+///
+/// [`HashSet`]: struct.HashSet.html
+/// [`entry`]: struct.HashSet.html#method.entry
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_set::{Entry, HashSet, OccupiedEntry};
+///
+/// let mut set = HashSet::new();
+/// set.extend(["a", "b", "c"]);
+/// assert_eq!(set.len(), 3);
+///
+/// // Existing value (insert)
+/// let entry: Entry<_, _> = set.entry("a");
+/// let _raw_o: OccupiedEntry<_, _> = entry.insert();
+/// assert_eq!(set.len(), 3);
+/// // Nonexistent value (insert)
+/// set.entry("d").insert();
+///
+/// // Existing value (or_insert)
+/// set.entry("b").or_insert();
+/// // Nonexistent value (or_insert)
+/// set.entry("e").or_insert();
+///
+/// println!("Our HashSet: {:?}", set);
+///
+/// let mut vec: Vec<_> = set.iter().copied().collect();
+/// // The `Iter` iterator produces items in arbitrary order, so the
+/// // items must be sorted to test them against a sorted array.
+/// vec.sort_unstable();
+/// assert_eq!(vec, ["a", "b", "c", "d", "e"]);
+/// ```
+pub enum Entry<'a, T, S, A = Global>
+where
+ A: Allocator + Clone,
+{
+ /// An occupied entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_set::{Entry, HashSet};
+ /// let mut set: HashSet<_> = ["a", "b"].into();
+ ///
+ /// match set.entry("a") {
+ /// Entry::Vacant(_) => unreachable!(),
+ /// Entry::Occupied(_) => { }
+ /// }
+ /// ```
+ Occupied(OccupiedEntry<'a, T, S, A>),
+
+ /// A vacant entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_set::{Entry, HashSet};
+ /// let mut set: HashSet<&str> = HashSet::new();
+ ///
+ /// match set.entry("a") {
+ /// Entry::Occupied(_) => unreachable!(),
+ /// Entry::Vacant(_) => { }
+ /// }
+ /// ```
+ Vacant(VacantEntry<'a, T, S, A>),
+}
+
+impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for Entry<'_, T, S, A> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match *self {
+ Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
+ Entry::Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
+ }
+ }
+}
+
+/// A view into an occupied entry in a `HashSet`.
+/// It is part of the [`Entry`] enum.
+///
+/// [`Entry`]: enum.Entry.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_set::{Entry, HashSet, OccupiedEntry};
+///
+/// let mut set = HashSet::new();
+/// set.extend(["a", "b", "c"]);
+///
+/// let _entry_o: OccupiedEntry<_, _> = set.entry("a").insert();
+/// assert_eq!(set.len(), 3);
+///
+/// // Existing key
+/// match set.entry("a") {
+/// Entry::Vacant(_) => unreachable!(),
+/// Entry::Occupied(view) => {
+/// assert_eq!(view.get(), &"a");
+/// }
+/// }
+///
+/// assert_eq!(set.len(), 3);
+///
+/// // Existing key (take)
+/// match set.entry("c") {
+/// Entry::Vacant(_) => unreachable!(),
+/// Entry::Occupied(view) => {
+/// assert_eq!(view.remove(), "c");
+/// }
+/// }
+/// assert_eq!(set.get(&"c"), None);
+/// assert_eq!(set.len(), 2);
+/// ```
+pub struct OccupiedEntry<'a, T, S, A: Allocator + Clone = Global> {
+ inner: map::OccupiedEntry<'a, T, (), S, A>,
+}
+
+impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for OccupiedEntry<'_, T, S, A> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("OccupiedEntry")
+ .field("value", self.get())
+ .finish()
+ }
+}
+
+/// A view into a vacant entry in a `HashSet`.
+/// It is part of the [`Entry`] enum.
+///
+/// [`Entry`]: enum.Entry.html
+///
+/// # Examples
+///
+/// ```
+/// use hashbrown::hash_set::{Entry, HashSet, VacantEntry};
+///
+/// let mut set = HashSet::<&str>::new();
+///
+/// let entry_v: VacantEntry<_, _> = match set.entry("a") {
+/// Entry::Vacant(view) => view,
+/// Entry::Occupied(_) => unreachable!(),
+/// };
+/// entry_v.insert();
+/// assert!(set.contains("a") && set.len() == 1);
+///
+/// // Nonexistent key (insert)
+/// match set.entry("b") {
+/// Entry::Vacant(view) => view.insert(),
+/// Entry::Occupied(_) => unreachable!(),
+/// }
+/// assert!(set.contains("b") && set.len() == 2);
+/// ```
+pub struct VacantEntry<'a, T, S, A: Allocator + Clone = Global> {
+ inner: map::VacantEntry<'a, T, (), S, A>,
+}
+
+impl<T: fmt::Debug, S, A: Allocator + Clone> fmt::Debug for VacantEntry<'_, T, S, A> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_tuple("VacantEntry").field(self.get()).finish()
+ }
+}
+
+impl<'a, T, S, A: Allocator + Clone> Entry<'a, T, S, A> {
+ /// Sets the value of the entry, and returns an OccupiedEntry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ /// let entry = set.entry("horseyland").insert();
+ ///
+ /// assert_eq!(entry.get(), &"horseyland");
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn insert(self) -> OccupiedEntry<'a, T, S, A>
+ where
+ T: Hash,
+ S: BuildHasher,
+ {
+ match self {
+ Entry::Occupied(entry) => entry,
+ Entry::Vacant(entry) => entry.insert_entry(),
+ }
+ }
+
+ /// Ensures a value is in the entry by inserting if it was vacant.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ ///
+ /// // nonexistent key
+ /// set.entry("poneyland").or_insert();
+ /// assert!(set.contains("poneyland"));
+ ///
+ /// // existing key
+ /// set.entry("poneyland").or_insert();
+ /// assert!(set.contains("poneyland"));
+ /// assert_eq!(set.len(), 1);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn or_insert(self)
+ where
+ T: Hash,
+ S: BuildHasher,
+ {
+ if let Entry::Vacant(entry) = self {
+ entry.insert();
+ }
+ }
+
+ /// Returns a reference to this entry's value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ /// set.entry("poneyland").or_insert();
+ /// // existing key
+ /// assert_eq!(set.entry("poneyland").get(), &"poneyland");
+ /// // nonexistent key
+ /// assert_eq!(set.entry("horseland").get(), &"horseland");
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn get(&self) -> &T {
+ match *self {
+ Entry::Occupied(ref entry) => entry.get(),
+ Entry::Vacant(ref entry) => entry.get(),
+ }
+ }
+}
+
+impl<T, S, A: Allocator + Clone> OccupiedEntry<'_, T, S, A> {
+ /// Gets a reference to the value in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_set::{Entry, HashSet};
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ /// set.entry("poneyland").or_insert();
+ ///
+ /// match set.entry("poneyland") {
+ /// Entry::Vacant(_) => panic!(),
+ /// Entry::Occupied(entry) => assert_eq!(entry.get(), &"poneyland"),
+ /// }
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn get(&self) -> &T {
+ self.inner.key()
+ }
+
+ /// Takes the value out of the entry, and returns it.
+ /// Keeps the allocated memory for reuse.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_set::Entry;
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ /// // The set is empty
+ /// assert!(set.is_empty() && set.capacity() == 0);
+ ///
+ /// set.entry("poneyland").or_insert();
+ /// let capacity_before_remove = set.capacity();
+ ///
+ /// if let Entry::Occupied(o) = set.entry("poneyland") {
+ /// assert_eq!(o.remove(), "poneyland");
+ /// }
+ ///
+ /// assert_eq!(set.contains("poneyland"), false);
+ /// // Now set hold none elements but capacity is equal to the old one
+ /// assert!(set.len() == 0 && set.capacity() == capacity_before_remove);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn remove(self) -> T {
+ self.inner.remove_entry().0
+ }
+
+ /// Replaces the entry, returning the old value. The new value in the hash map will be
+ /// the value used to create this entry.
+ ///
+ /// # Panics
+ ///
+ /// Will panic if this OccupiedEntry was created through [`Entry::insert`].
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_set::{Entry, HashSet};
+ /// use std::rc::Rc;
+ ///
+ /// let mut set: HashSet<Rc<String>> = HashSet::new();
+ /// let key_one = Rc::new("Stringthing".to_string());
+ /// let key_two = Rc::new("Stringthing".to_string());
+ ///
+ /// set.insert(key_one.clone());
+ /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1);
+ ///
+ /// match set.entry(key_two.clone()) {
+ /// Entry::Occupied(entry) => {
+ /// let old_key: Rc<String> = entry.replace();
+ /// assert!(Rc::ptr_eq(&key_one, &old_key));
+ /// }
+ /// Entry::Vacant(_) => panic!(),
+ /// }
+ ///
+ /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2);
+ /// assert!(set.contains(&"Stringthing".to_owned()));
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn replace(self) -> T {
+ self.inner.replace_key()
+ }
+}
+
+impl<'a, T, S, A: Allocator + Clone> VacantEntry<'a, T, S, A> {
+ /// Gets a reference to the value that would be used when inserting
+ /// through the `VacantEntry`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ /// assert_eq!(set.entry("poneyland").get(), &"poneyland");
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn get(&self) -> &T {
+ self.inner.key()
+ }
+
+ /// Take ownership of the value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::hash_set::{Entry, HashSet};
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ ///
+ /// match set.entry("poneyland") {
+ /// Entry::Occupied(_) => panic!(),
+ /// Entry::Vacant(v) => assert_eq!(v.into_value(), "poneyland"),
+ /// }
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn into_value(self) -> T {
+ self.inner.into_key()
+ }
+
+ /// Sets the value of the entry with the VacantEntry's value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_set::Entry;
+ ///
+ /// let mut set: HashSet<&str> = HashSet::new();
+ ///
+ /// if let Entry::Vacant(o) = set.entry("poneyland") {
+ /// o.insert();
+ /// }
+ /// assert!(set.contains("poneyland"));
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn insert(self)
+ where
+ T: Hash,
+ S: BuildHasher,
+ {
+ self.inner.insert(());
+ }
+
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn insert_entry(self) -> OccupiedEntry<'a, T, S, A>
+ where
+ T: Hash,
+ S: BuildHasher,
+ {
+ OccupiedEntry {
+ inner: self.inner.insert_entry(()),
+ }
+ }
+}
+
#[allow(dead_code)]
fn assert_covariance() {
fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
