diff options
| author | Charisee <chiw@google.com> | 2022-07-26 20:13:28 +0000 |
|---|---|---|
| committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2022-07-26 20:13:28 +0000 |
| commit | a12885877ea4e729733a9e627daabfd63a6789a9 (patch) | |
| tree | 24b2766a350531ab6326c2ac8645cf4fb251f677 | |
| parent | b17da3b606d334b56b682f435beb1b0bea29df12 (diff) | |
| parent | 514ca9f4d27c7802ae05c21f2575643daf0396bd (diff) | |
| download | hashbrown-a12885877ea4e729733a9e627daabfd63a6789a9.tar.gz | |
Updating hashbrown crate am: 18967b9e40 am: 65783bf1b0 am: 4773b3a582 am: 4bc17a4c59 am: 514ca9f4d2
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/hashbrown/+/2163166
Change-Id: I87df93550be6abf83c7eb7333d3da62cc4d2f53d
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
| -rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
| -rw-r--r-- | Android.bp | 79 | ||||
| -rw-r--r-- | CHANGELOG.md | 25 | ||||
| -rw-r--r-- | Cargo.toml | 4 | ||||
| -rw-r--r-- | Cargo.toml.orig | 4 | ||||
| -rw-r--r-- | METADATA | 6 | ||||
| -rw-r--r-- | cargo2android.json | 7 | ||||
| -rw-r--r-- | src/macros.rs | 1 | ||||
| -rw-r--r-- | src/map.rs | 2255 | ||||
| -rw-r--r-- | src/raw/alloc.rs | 8 | ||||
| -rw-r--r-- | src/raw/mod.rs | 164 | ||||
| -rw-r--r-- | src/rustc_entry.rs | 12 | ||||
| -rw-r--r-- | src/scopeguard.rs | 27 | ||||
| -rw-r--r-- | src/set.rs | 441 |
14 files changed, 2740 insertions, 295 deletions
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 @@ -37,92 +37,25 @@ license { ], } -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 @@ and this project adheres to [Semantic Versioning](https://semver.org/). ## [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 @@ This release was _yanked_ due to a breaking change for users of `no-default-feat - 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 @@ -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 @@ keywords = ["hash", "no_std", "hashmap", "swisstable"] 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 @@ -7,13 +7,13 @@ third_party { } 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` ($( @@ -300,6 +300,8 @@ impl<K, V> HashMap<K, V, DefaultHashBuilder> { /// ``` /// 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 @@ impl<K, V> HashMap<K, V, DefaultHashBuilder> { /// ``` /// 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 @@ impl<K, V, S> HashMap<K, V, S> { /// 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 @@ impl<K, V, S> HashMap<K, V, S> { /// /// 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 @@ impl<K, V, S> HashMap<K, V, S> { /// /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// ``` /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// *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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// *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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { } } - /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ where /// ``` /// 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 @@ where /// /// ``` /// 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 @@ where /// *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 @@ where /// 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 @@ where /// 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 @@ where /// /// 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 @@ where /// 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 @@ where /// /// ``` /// 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 @@ where } /// 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 @@ where /// 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 @@ where } /// 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 @@ where /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// 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 @@ impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> { /// `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 @@ where 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 @@ where /// # 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 @@ where } } -/// 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 @@ impl<K: Debug, V: Debug> fmt::Debug for Iter<'_, K, V> { } } -/// 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 @@ impl<K, V> IterMut<'_, K, V> { } } -/// 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 @@ impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> { } } -/// 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 @@ impl<K: Debug, V: Debug, A: Allocator + Clone> fmt::Debug for IntoKeys<K, V, A> } } -/// 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 @@ impl<K, V: Debug, A: Allocator + Clone> fmt::Debug for IntoValues<K, V, A> { } } -/// 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 @@ impl<K: Debug, V> fmt::Debug for Keys<'_, K, V> { } } -/// 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 @@ impl<K, V: Debug> fmt::Debug for Values<'_, K, V> { } } -/// 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 @@ impl<K, V, A: Allocator + Clone> Drain<'_, K, V, A> { } } -/// 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 @@ impl<K, V, A: Allocator + Clone> DrainFilterInner<'_, K, V, A> { } } -/// 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 @@ pub struct ValuesMut<'a, K, V> { /// 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 @@ pub struct RawEntryBuilderMut<'a, K, V, S, A: Allocator + Clone = Global> { /// [`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 @@ pub enum RawEntryMut<'a, K, V, S, A: Allocator + Clone = Global> { /// 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 @@ where /// 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 @@ pub struct RawVacantEntryMut<'a, K, V, S, A: Allocator + Clone = Global> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> { } /// 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> { } 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> RawEntryBuilderMut<'a, K, V, S, A> { } 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilder<'a, K, V, S, A> { 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilder<'a, K, V, S, A> { } } - /// 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> RawEntryMut<'a, K, V, S, A> { 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> { } /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> { } /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> { /// 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> RawOccupiedEntryMut<'a, K, V, S, A> { 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 @@ 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 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 @@ impl<'a, K, V, S, A: Allocator + Clone> RawVacantEntryMut<'a, K, V, S, A> { } /// 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 @@ impl<K, V, S, A: Allocator + Clone> Debug for RawEntryBuilder<'_, K, V, S, A> { /// /// [`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 @@ impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for Entry<'_, K, V, S, A /// 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 @@ impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for OccupiedEntry<'_, K, /// 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 @@ impl<K: Debug, V, S, A: Allocator + Clone> Debug for VacantEntry<'_, K, V, S, A> } } -/// 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 @@ impl<'a, K: Borrow<Q>, Q: ?Sized> AsRef<Q> for KeyOrRef<'a, K, Q> { /// 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 @@ impl<K: Borrow<Q>, Q: ?Sized + Debug, V: Debug, S, A: Allocator + Clone> Debug /// 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 @@ impl<K: Borrow<Q>, Q: ?Sized + Debug, V, S, A: Allocator + Clone> Debug /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> IntoIterator for &'a HashMap<K, V, S, A> 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 @@ impl<'a, K, V, S, A: Allocator + Clone> IntoIterator for &'a mut HashMap<K, V, S 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 @@ impl<K, V, S, A: Allocator + Clone> IntoIterator for HashMap<K, V, S, A> { /// ``` /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> Entry<'a, K, V, S, A> { /// /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> Entry<'a, K, V, S, A> { /// ``` /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> Entry<'a, K, V, S, A> { /// /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> Entry<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V: Default, S, A: Allocator + Clone> Entry<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// # 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { } /// Take the ownership of the key and value from the map. + /// Keeps the allocated memory for reuse. /// /// # Examples /// @@ -3475,14 +5179,20 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// # 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// # 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 @@ impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> { /// 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); + /// + /// 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())); + /// } + /// + /// assert!( + /// keys_one.iter().all(|key| Rc::strong_count(key) == 2) + /// && keys_two.iter().all(|key| Rc::strong_count(key) == 1) + /// ); /// - /// // Initialise known strings, run program, etc. + /// reclaim_memory(&mut map, &keys_two); /// - /// reclaim_memory(&mut map, &known_strings); + /// 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>, 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`. + /// 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 @@ impl<'a, K, V, S, A: Allocator + Clone> VacantEntry<'a, K, V, S, A> { /// # 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 @@ impl<'a, K, V, S, A: Allocator + Clone> VacantEntry<'a, K, V, S, A> { } #[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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> EntryRef<'a, 'b, K, Q, V, /// /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> EntryRef<'a, 'b, K, Q, V, /// ``` /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> EntryRef<'a, 'b, K, Q, V, /// /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> EntryRef<'a, 'b, K, Q, V, /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V: Default, S, A: Allocator + Clone> EntryRef<'a, 'b, /// ``` /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// # 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, } /// Take the ownership of the key and value from the map. + /// Keeps the allocated memory for reuse. /// /// # Examples /// @@ -4144,14 +5910,20 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// # 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, /// 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); + /// + /// 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); + /// } + /// + /// assert!(keys.iter().all(|key| Rc::strong_count(key) == 2)); /// - /// // Initialise known strings, run program, etc. + /// // 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); /// - /// reclaim_memory(&mut map, &known_strings); + /// assert!(keys.iter().all(|key| Rc::strong_count(key) == 1)); /// - /// 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`. + /// 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 @@ impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> VacantEntryRef<'a, 'b, K, /// # 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 @@ where 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 @@ where } } +/// 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 @@ where 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 @@ where } } +/// 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 @@ mod test_map { } #[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 @@ mod test_map { } #[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 @@ mod test_map { 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 @@ mod test_map { 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 @@ mod inner { #[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 @@ fn unlikely(b: bool) -> bool { 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 @@ impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> { 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(), - }, - ); - - new_table.clone_from_spec(self, |new_table| { - // We need to free the memory allocated for the new table. + // 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(), + }; + + // 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 @@ impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> { *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 @@ impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> { ); } - 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 @@ impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> { /// 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: Copy, A: Allocator + Clone> RawTableClone for RawTable<T, A> { } 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 @@ impl<T: Clone, A: Allocator + Clone> RawTable<T, A> { } } } - - // 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 @@ impl<T> RawIterRange<T> { } } } + + /// # 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 @@ impl<T> Iterator for RawIterRange<T> { #[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 @@ impl<T> Iterator for RawIter<T> { #[cfg_attr(feature = "inline-more", inline)] fn next(&mut self) -> Option<Bucket<T>> { - if let Some(b) = self.iter.next() { + // 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; - 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 } + + 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 @@ where /// 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 @@ impl<'a, K, V, A: Allocator + Clone> RustcEntry<'a, K, V, A> { /// 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 @@ impl<'a, K, V, A: Allocator + Clone> RustcOccupiedEntry<'a, K, V, A> { /// 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 @@ where 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), @@ -902,6 +902,47 @@ where .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 @@ where } } +/// 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> { |