Revert "Update hashbrown to 0.12.0"
This reverts commit c77953dabfec89f29d3916be3f2d9c2f3066f1bb.
Reason for revert: Performance regression.
Bug: 223002010
Change-Id: I139eac2ddc94c81938ed40d96465dc8f7e4a88f1
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 44a683a..0eb3824 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,6 +1,5 @@
{
"git": {
- "sha1": "f3a242fb48e73df704d27c9722e30ebda5dd8e4f"
- },
- "path_in_vcs": ""
-}
\ No newline at end of file
+ "sha1": "bbb5d3bb1c23569c15e54c670bc0c3669ae3e7dc"
+ }
+}
diff --git a/Android.bp b/Android.bp
index d5530db..28b8053 100644
--- a/Android.bp
+++ b/Android.bp
@@ -39,12 +39,13 @@
rust_library {
name: "libhashbrown",
+ // has rustc warnings
host_supported: true,
crate_name: "hashbrown",
cargo_env_compat: true,
- cargo_pkg_version: "0.12.0",
+ cargo_pkg_version: "0.11.2",
srcs: ["src/lib.rs"],
- edition: "2021",
+ edition: "2018",
features: [
"ahash",
"default",
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 4637bd0..c88d3e0 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,41 +2,11 @@
All notable changes to this project will be documented in this file.
-The format is based on [Keep a Changelog](https://keepachangelog.com/)
-and this project adheres to [Semantic Versioning](https://semver.org/).
+The format is based on [Keep a Changelog](http://keepachangelog.com/)
+and this project adheres to [Semantic Versioning](http://semver.org/).
## [Unreleased]
-## [v0.12.0] - 2022-01-17
-
-## Added
-
-- Added `From<[T; N]>` and `From<[(K, V); N]>` for `HashSet` and `HashMap` respectively. (#297)
-- Added an `allocator()` getter to HashMap and HashSet. (#257)
-- Added `insert_unique_unchecked` to `HashMap` and `HashSet`. (#293)
-- Added `into_keys` and `into_values` to HashMap. (#295)
-- Implement `From<array>` on `HashSet` and `HashMap`. (#298)
-- Added `entry_ref` API to `HashMap`. (#201)
-
-## Changed
-
-- Bumped minimum Rust version to 1.56.1 and edition to 2021.
-- Use u64 for the GroupWord on WebAssembly. (#271)
-- Optimized `find`. (#279)
-- Made rehashing and resizing less generic to reduce compilation time. (#282)
-- Inlined small functions. (#283)
-- Use `BuildHasher::hash_one` when `feature = "nightly"` is enabled. (#292)
-- Relaxed the bounds on `Debug` for `HashSet`. (#296)
-- Rename `get_each_mut` to `get_many_mut` and align API with the stdlib. (#291)
-- Don't hash the key when searching in an empty table. (#305)
-
-## Fixed
-
-- Guard against allocations exceeding isize::MAX. (#268)
-- Made `RawTable::insert_no_grow` unsafe. (#254)
-- Inline `static_empty`. (#280)
-- Fixed trait bounds on Send/Sync impls. (#303)
-
## [v0.11.2] - 2021-03-25
## Fixed
@@ -337,8 +307,7 @@
- Initial release
-[Unreleased]: https://github.com/rust-lang/hashbrown/compare/v0.12.0...HEAD
-[v0.12.0]: https://github.com/rust-lang/hashbrown/compare/v0.11.2...v0.12.0
+[Unreleased]: https://github.com/rust-lang/hashbrown/compare/v0.11.2...HEAD
[v0.11.2]: https://github.com/rust-lang/hashbrown/compare/v0.11.1...v0.11.2
[v0.11.1]: https://github.com/rust-lang/hashbrown/compare/v0.11.0...v0.11.1
[v0.11.0]: https://github.com/rust-lang/hashbrown/compare/v0.10.0...v0.11.0
diff --git a/Cargo.toml b/Cargo.toml
index 134025a..02bd480 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,25 +3,25 @@
# When uploading crates to the registry Cargo will automatically
# "normalize" Cargo.toml files for maximal compatibility
# with all versions of Cargo and also rewrite `path` dependencies
-# to registry (e.g., crates.io) dependencies.
+# to registry (e.g., crates.io) dependencies
#
-# If you are reading this file be aware that the original Cargo.toml
-# will likely look very different (and much more reasonable).
-# See Cargo.toml.orig for the original contents.
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
[package]
-edition = "2021"
+edition = "2018"
name = "hashbrown"
-version = "0.12.0"
+version = "0.11.2"
authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
-exclude = [".github", "bors.toml", "/ci/*"]
+exclude = [".travis.yml", "bors.toml", "/ci/*"]
description = "A Rust port of Google's SwissTable hash map"
readme = "README.md"
keywords = ["hash", "no_std", "hashmap", "swisstable"]
categories = ["data-structures", "no-std"]
license = "Apache-2.0/MIT"
repository = "https://github.com/rust-lang/hashbrown"
-resolver = "2"
[package.metadata.docs.rs]
features = ["nightly", "rayon", "serde", "raw"]
[dependencies.ahash]
@@ -65,7 +65,7 @@
version = "1.4"
[dev-dependencies.rand]
-version = "0.8.3"
+version = "0.7.3"
features = ["small_rng"]
[dev-dependencies.rayon]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 922371b..a056c3c 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
[package]
name = "hashbrown"
-version = "0.12.0"
+version = "0.11.2"
authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
description = "A Rust port of Google's SwissTable hash map"
license = "Apache-2.0/MIT"
@@ -8,8 +8,8 @@
readme = "README.md"
keywords = ["hash", "no_std", "hashmap", "swisstable"]
categories = ["data-structures", "no-std"]
-exclude = [".github", "bors.toml", "/ci/*"]
-edition = "2021"
+exclude = [".travis.yml", "bors.toml", "/ci/*"]
+edition = "2018"
[dependencies]
# For the default hasher
@@ -29,7 +29,7 @@
[dev-dependencies]
lazy_static = "1.4"
-rand = { version = "0.8.3", features = ["small_rng"] }
+rand = { version = "0.7.3", features = ["small_rng"] }
rayon = "1.0"
fnv = "1.0.7"
serde_test = "1.0"
diff --git a/METADATA b/METADATA
index bcedcde..fa67d80 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/hashbrown/hashbrown-0.12.0.crate"
+ value: "https://static.crates.io/crates/hashbrown/hashbrown-0.11.2.crate"
}
- version: "0.12.0"
+ version: "0.11.2"
license_type: NOTICE
last_upgrade_date {
- year: 2022
- month: 3
+ year: 2021
+ month: 4
day: 1
}
}
diff --git a/README.md b/README.md
index 0b29cb5..86664c4 100644
--- a/README.md
+++ b/README.md
@@ -1,10 +1,10 @@
hashbrown
=========
-[](https://github.com/rust-lang/hashbrown/actions)
+[](https://travis-ci.com/rust-lang/hashbrown)
[](https://crates.io/crates/hashbrown)
[](https://docs.rs/hashbrown)
-[](https://github.com/rust-lang/hashbrown)
+[](https://github.com/rust-lang/hashbrown)
This crate is a Rust port of Google's high-performance [SwissTable] hash
map, adapted to make it a drop-in replacement for Rust's standard `HashMap`
@@ -114,8 +114,8 @@
Licensed under either of:
- * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or https://www.apache.org/licenses/LICENSE-2.0)
- * MIT license ([LICENSE-MIT](LICENSE-MIT) or https://opensource.org/licenses/MIT)
+ * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
+ * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
at your option.
diff --git a/benches/bench.rs b/benches/bench.rs
index c393b9a..568c513 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -38,7 +38,7 @@
type Item = usize;
fn next(&mut self) -> Option<usize> {
// Add 1 then multiply by some 32 bit prime.
- self.state = self.state.wrapping_add(1).wrapping_mul(3_787_392_781);
+ self.state = self.state.wrapping_add(1).wrapping_mul(3787392781);
Some(self.state)
}
}
diff --git a/benches/insert_unique_unchecked.rs b/benches/insert_unique_unchecked.rs
deleted file mode 100644
index 857ad18..0000000
--- a/benches/insert_unique_unchecked.rs
+++ /dev/null
@@ -1,32 +0,0 @@
-//! Compare `insert` and `insert_unique_unchecked` operations performance.
-
-#![feature(test)]
-
-extern crate test;
-
-use hashbrown::HashMap;
-use test::Bencher;
-
-#[bench]
-fn insert(b: &mut Bencher) {
- let keys: Vec<String> = (0..1000).map(|i| format!("xxxx{}yyyy", i)).collect();
- b.iter(|| {
- let mut m = HashMap::with_capacity(1000);
- for k in &keys {
- m.insert(k, k);
- }
- m
- });
-}
-
-#[bench]
-fn insert_unique_unchecked(b: &mut Bencher) {
- let keys: Vec<String> = (0..1000).map(|i| format!("xxxx{}yyyy", i)).collect();
- b.iter(|| {
- let mut m = HashMap::with_capacity(1000);
- for k in &keys {
- m.insert_unique_unchecked(k, k);
- }
- m
- });
-}
diff --git a/src/external_trait_impls/rayon/helpers.rs b/src/external_trait_impls/rayon/helpers.rs
index 070b08c..9382007 100644
--- a/src/external_trait_impls/rayon/helpers.rs
+++ b/src/external_trait_impls/rayon/helpers.rs
@@ -4,7 +4,6 @@
use rayon::iter::{IntoParallelIterator, ParallelIterator};
/// Helper for collecting parallel iterators to an intermediary
-#[allow(clippy::linkedlist)] // yes, we need linked list here for efficient appending!
pub(super) fn collect<I: IntoParallelIterator>(iter: I) -> (LinkedList<Vec<I::Item>>, usize) {
let list = iter
.into_par_iter()
diff --git a/src/external_trait_impls/rayon/map.rs b/src/external_trait_impls/rayon/map.rs
index 14d91c2..61b7380 100644
--- a/src/external_trait_impls/rayon/map.rs
+++ b/src/external_trait_impls/rayon/map.rs
@@ -512,7 +512,7 @@
where
H: Hasher,
{
- self.k.hash(state);
+ self.k.hash(state)
}
}
@@ -679,7 +679,7 @@
fn test_values_mut() {
let vec = vec![(1, 1), (2, 2), (3, 3)];
let mut map: HashMap<_, _> = vec.into_par_iter().collect();
- map.par_values_mut().for_each(|value| *value *= 2);
+ map.par_values_mut().for_each(|value| *value = (*value) * 2);
let values: Vec<_> = map.par_values().cloned().collect();
assert_eq!(values.len(), 3);
assert!(values.contains(&2));
diff --git a/src/external_trait_impls/rayon/raw.rs b/src/external_trait_impls/rayon/raw.rs
index 883303e..18da1ea 100644
--- a/src/external_trait_impls/rayon/raw.rs
+++ b/src/external_trait_impls/rayon/raw.rs
@@ -87,7 +87,7 @@
}
}
-impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for RawIntoParIter<T, A> {
+impl<T: Send, A: Allocator + Clone> ParallelIterator for RawIntoParIter<T, A> {
type Item = T;
#[cfg_attr(feature = "inline-more", inline)]
@@ -116,7 +116,7 @@
marker: PhantomData<&'a RawTable<T, A>>,
}
-unsafe impl<T: Send, A: Allocator + Clone> Send for RawParDrain<'_, T, A> {}
+unsafe impl<T, A: Allocator + Clone> Send for RawParDrain<'_, T, A> {}
impl<T, A: Allocator + Clone> RawParDrain<'_, T, A> {
#[cfg_attr(feature = "inline-more", inline)]
@@ -134,7 +134,7 @@
C: UnindexedConsumer<Self::Item>,
{
let _guard = guard(self.table, |table| unsafe {
- table.as_mut().clear_no_drop();
+ table.as_mut().clear_no_drop()
});
let iter = unsafe { self.table.as_ref().iter().iter };
mem::forget(self);
@@ -146,9 +146,7 @@
impl<T, A: Allocator + Clone> Drop for RawParDrain<'_, T, A> {
fn drop(&mut self) {
// If drive_unindexed is not called then simply clear the table.
- unsafe {
- self.table.as_mut().clear();
- }
+ unsafe { self.table.as_mut().clear() }
}
}
@@ -177,7 +175,7 @@
{
// Make sure to modify the iterator in-place so that any remaining
// elements are processed in our Drop impl.
- for item in &mut self.iter {
+ while let Some(item) = self.iter.next() {
folder = folder.consume(unsafe { item.read() });
if folder.full() {
return folder;
@@ -195,7 +193,7 @@
fn drop(&mut self) {
// Drop all remaining elements
if mem::needs_drop::<T>() {
- for item in &mut self.iter {
+ while let Some(item) = self.iter.next() {
unsafe {
item.drop();
}
diff --git a/src/external_trait_impls/serde.rs b/src/external_trait_impls/serde.rs
index 4d62dee..7816e78 100644
--- a/src/external_trait_impls/serde.rs
+++ b/src/external_trait_impls/serde.rs
@@ -161,7 +161,6 @@
deserializer.deserialize_seq(visitor)
}
- #[allow(clippy::missing_errors_doc)]
fn deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error>
where
D: Deserializer<'de>,
diff --git a/src/lib.rs b/src/lib.rs
index 701b6ea..b2d6584 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -21,8 +21,7 @@
allocator_api,
slice_ptr_get,
nonnull_slice_from_raw_parts,
- maybe_uninit_array_assume_init,
- build_hasher_simple_hash_one
+ maybe_uninit_array_assume_init
)
)]
#,
+/// [`HashMap::get_each_mut`], and [`HashMap::get_each_key_value_mut`].
+#[cfg(feature = "nightly")]
+#[derive(Clone, PartialEq, Eq, Debug)]
+pub enum UnavailableMutError {
+ /// The requested entry is not present in the table.
+ Absent,
+ /// The requested entry is present, but a mutable reference to it was already created and
+ /// returned from this call to `get_each_mut` or `get_each_key_value_mut`.
+ ///
+ /// Includes the index of the existing mutable reference in the returned array.
+ Duplicate(usize),
+}
+
/// Wrapper around `Bump` which allows it to be used as an allocator for
/// `HashMap`, `HashSet` and `RawTable`.
///
diff --git a/src/macros.rs b/src/macros.rs
index 4de6b5a..0279597 100644
--- a/src/macros.rs
+++ b/src/macros.rs
@@ -57,8 +57,8 @@
// default fn syntax for specialization changes in the future.
#[cfg(feature = "nightly")]
macro_rules! default_fn {
- (#[$($a:tt)*] $($tt:tt)*) => {
- #[$($a)*] default $($tt)*
+ ($($tt:tt)*) => {
+ default $($tt)*
}
}
#[cfg(not(feature = "nightly"))]
diff --git a/src/map.rs b/src/map.rs
index d0592cb..ab11288 100644
--- a/src/map.rs
+++ b/src/map.rs
@@ -1,11 +1,15 @@
use crate::raw::{Allocator, Bucket, Global, RawDrain, RawIntoIter, RawIter, RawTable};
use crate::TryReserveError;
+#[cfg(feature = "nightly")]
+use crate::UnavailableMutError;
use core::borrow::Borrow;
use core::fmt::{self, Debug};
use core::hash::{BuildHasher, Hash};
use core::iter::{FromIterator, FusedIterator};
use core::marker::PhantomData;
use core::mem;
+#[cfg(feature = "nightly")]
+use core::mem::MaybeUninit;
use core::ops::Index;
/// Default hasher for `HashMap`.
@@ -240,7 +244,6 @@
move |x| k.eq(x.borrow())
}
-#[cfg(not(feature = "nightly"))]
#[cfg_attr(feature = "inline-more", inline)]
pub(crate) fn make_hash<K, Q, S>(hash_builder: &S, val: &Q) -> u64
where
@@ -254,18 +257,6 @@
state.finish()
}
-#[cfg(feature = "nightly")]
-#[cfg_attr(feature = "inline-more", inline)]
-pub(crate) fn make_hash<K, Q, S>(hash_builder: &S, val: &Q) -> u64
-where
- K: Borrow<Q>,
- Q: Hash + ?Sized,
- S: BuildHasher,
-{
- hash_builder.hash_one(val)
-}
-
-#[cfg(not(feature = "nightly"))]
#[cfg_attr(feature = "inline-more", inline)]
pub(crate) fn make_insert_hash<K, S>(hash_builder: &S, val: &K) -> u64
where
@@ -278,16 +269,6 @@
state.finish()
}
-#[cfg(feature = "nightly")]
-#[cfg_attr(feature = "inline-more", inline)]
-pub(crate) fn make_insert_hash<K, S>(hash_builder: &S, val: &K) -> u64
-where
- K: Hash,
- S: BuildHasher,
-{
- hash_builder.hash_one(val)
-}
-
#[cfg(feature = "ahash")]
impl<K, V> HashMap<K, V, DefaultHashBuilder> {
/// Creates an empty `HashMap`.
@@ -414,12 +395,6 @@
}
impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> {
- /// Returns a reference to the underlying allocator.
- #[inline]
- pub fn allocator(&self) -> &A {
- self.table.allocator()
- }
-
/// Creates an empty `HashMap` which will use the given hash builder to hash
/// keys. It will be allocated with the given allocator.
///
@@ -798,52 +773,6 @@
pub fn clear(&mut self) {
self.table.clear();
}
-
- /// Creates a consuming iterator visiting all the keys in arbitrary order.
- /// The map cannot be used after calling this.
- /// The iterator element type is `K`.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map = HashMap::new();
- /// map.insert("a", 1);
- /// map.insert("b", 2);
- /// map.insert("c", 3);
- ///
- /// let vec: Vec<&str> = map.into_keys().collect();
- /// ```
- #[inline]
- pub fn into_keys(self) -> IntoKeys<K, V, A> {
- IntoKeys {
- inner: self.into_iter(),
- }
- }
-
- /// Creates a consuming iterator visiting all the values in arbitrary order.
- /// The map cannot be used after calling this.
- /// The iterator element type is `V`.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map = HashMap::new();
- /// map.insert("a", 1);
- /// map.insert("b", 2);
- /// map.insert("c", 3);
- ///
- /// let vec: Vec<i32> = map.into_values().collect();
- /// ```
- #[inline]
- pub fn into_values(self) -> IntoValues<K, V, A> {
- IntoValues {
- inner: self.into_iter(),
- }
- }
}
impl<K, V, S, A> HashMap<K, V, S, A>
@@ -986,46 +915,6 @@
}
}
- /// Gets the given key's corresponding entry by reference in the map for in-place manipulation.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut words: HashMap<String, usize> = HashMap::new();
- /// let source = ["poneyland", "horseyland", "poneyland", "poneyland"];
- /// for (i, &s) in source.iter().enumerate() {
- /// let counter = words.entry_ref(s).or_insert(0);
- /// *counter += 1;
- /// }
- ///
- /// assert_eq!(words["poneyland"], 3);
- /// assert_eq!(words["horseyland"], 1);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn entry_ref<'a, 'b, Q: ?Sized>(&'a mut self, key: &'b Q) -> EntryRef<'a, 'b, K, Q, V, S, A>
- where
- K: Borrow<Q>,
- Q: Hash + Eq,
- {
- let hash = make_hash::<K, Q, S>(&self.hash_builder, key);
- if let Some(elem) = self.table.find(hash, equivalent_key(key)) {
- EntryRef::Occupied(OccupiedEntryRef {
- hash,
- key: Some(KeyOrRef::Borrowed(key)),
- elem,
- table: self,
- })
- } else {
- EntryRef::Vacant(VacantEntryRef {
- hash,
- key: KeyOrRef::Borrowed(key),
- table: self,
- })
- }
- }
-
/// Returns a reference to the value corresponding to the key.
///
/// The key may be any borrowed form of the map's key type, but
@@ -1096,12 +985,8 @@
K: Borrow<Q>,
Q: Hash + Eq,
{
- if self.table.is_empty() {
- None
- } else {
- let hash = make_hash::<K, Q, S>(&self.hash_builder, k);
- self.table.get(hash, equivalent_key(k))
- }
+ let hash = make_hash::<K, Q, S>(&self.hash_builder, k);
+ self.table.get(hash, equivalent_key(k))
}
/// Returns the key-value pair corresponding to the supplied key, with a mutable reference to value.
@@ -1208,24 +1093,24 @@
K: Borrow<Q>,
Q: Hash + Eq,
{
- if self.table.is_empty() {
- None
- } else {
- let hash = make_hash::<K, Q, S>(&self.hash_builder, k);
- self.table.get_mut(hash, equivalent_key(k))
- }
+ let hash = make_hash::<K, Q, S>(&self.hash_builder, k);
+ self.table.get_mut(hash, equivalent_key(k))
}
/// Attempts to get mutable references to `N` values in the map at once.
///
- /// Returns an array of length `N` with the results of each query. For soundness, at most one
- /// mutable reference will be returned to any value. `None` will be returned if any of the
- /// keys are duplicates or missing.
+ /// Returns an array of length `N` with the results of each query. For soundness,
+ /// at most one mutable reference will be returned to any value. An
+ /// `Err(UnavailableMutError::Duplicate(i))` in the returned array indicates that a suitable
+ /// key-value pair exists, but a mutable reference to the value already occurs at index `i` in
+ /// the returned array.
+ ///
+ /// This method is available only if the `nightly` feature is enabled.
///
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
+ /// use hashbrown::{HashMap, UnavailableMutError};
///
/// let mut libraries = HashMap::new();
/// libraries.insert("Bodleian Library".to_string(), 1602);
@@ -1233,108 +1118,58 @@
/// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
/// libraries.insert("Library of Congress".to_string(), 1800);
///
- /// let got = libraries.get_many_mut([
+ /// let got = libraries.get_each_mut([
+ /// "Athenæum",
+ /// "New York Public Library",
/// "Athenæum",
/// "Library of Congress",
/// ]);
/// assert_eq!(
/// got,
- /// Some([
- /// &mut 1807,
- /// &mut 1800,
- /// ]),
+ /// [
+ /// Ok(&mut 1807),
+ /// Err(UnavailableMutError::Absent),
+ /// Err(UnavailableMutError::Duplicate(0)),
+ /// Ok(&mut 1800),
+ /// ]
/// );
- ///
- /// // Missing keys result in None
- /// let got = libraries.get_many_mut([
- /// "Athenæum",
- /// "New York Public Library",
- /// ]);
- /// assert_eq!(got, None);
- ///
- /// // Duplicate keys result in None
- /// let got = libraries.get_many_mut([
- /// "Athenæum",
- /// "Athenæum",
- /// ]);
- /// assert_eq!(got, None);
/// ```
- pub fn get_many_mut<Q: ?Sized, const N: usize>(&mut self, ks: [&Q; N]) -> Option<[&'_ mut V; N]>
- where
- K: Borrow<Q>,
- Q: Hash + Eq,
- {
- self.get_many_mut_inner(ks).map(|res| res.map(|(_, v)| v))
- }
-
- /// Attempts to get mutable references to `N` values in the map at once, without validating that
- /// the values are unique.
- ///
- /// 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`].
- ///
- /// # Safety
- ///
- /// Calling this method with overlapping keys is *[undefined behavior]* even if the resulting
- /// references are not used.
- ///
- /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut libraries = HashMap::new();
- /// libraries.insert("Bodleian Library".to_string(), 1602);
- /// libraries.insert("Athenæum".to_string(), 1807);
- /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
- /// libraries.insert("Library of Congress".to_string(), 1800);
- ///
- /// let got = libraries.get_many_mut([
- /// "Athenæum",
- /// "Library of Congress",
- /// ]);
- /// assert_eq!(
- /// got,
- /// Some([
- /// &mut 1807,
- /// &mut 1800,
- /// ]),
- /// );
- ///
- /// // Missing keys result in None
- /// let got = libraries.get_many_mut([
- /// "Athenæum",
- /// "New York Public Library",
- /// ]);
- /// assert_eq!(got, None);
- /// ```
- pub unsafe fn get_many_unchecked_mut<Q: ?Sized, const N: usize>(
+ #[cfg(feature = "nightly")]
+ pub fn get_each_mut<Q: ?Sized, const N: usize>(
&mut self,
ks: [&Q; N],
- ) -> Option<[&'_ mut V; N]>
+ ) -> [Result<&'_ mut V, UnavailableMutError>; N]
where
K: Borrow<Q>,
Q: Hash + Eq,
{
- self.get_many_unchecked_mut_inner(ks)
- .map(|res| res.map(|(_, v)| v))
+ let mut pairs = self.get_each_inner_mut(ks);
+ // TODO use `MaybeUninit::uninit_array` here instead once that's stable.
+ let mut out: [MaybeUninit<Result<&'_ mut V, UnavailableMutError>>; N] =
+ unsafe { MaybeUninit::uninit().assume_init() };
+ for i in 0..N {
+ out[i] = MaybeUninit::new(
+ mem::replace(&mut pairs[i], Err(UnavailableMutError::Absent)).map(|(_, v)| v),
+ );
+ }
+ unsafe { MaybeUninit::array_assume_init(out) }
}
/// Attempts to get mutable references to `N` values in the map at once, with immutable
/// references to the corresponding keys.
///
- /// Returns an array of length `N` with the results of each query. For soundness, at most one
- /// mutable reference will be returned to any value. `None` will be returned if any of the keys
- /// are duplicates or missing.
+ /// Returns an array of length `N` with the results of each query. For soundness,
+ /// at most one mutable reference will be returned to any value. An
+ /// `Err(UnavailableMutError::Duplicate(i))` in the returned array indicates that a suitable
+ /// key-value pair exists, but a mutable reference to the value already occurs at index `i` in
+ /// the returned array.
+ ///
+ /// This method is available only if the `nightly` feature is enabled.
///
/// # Examples
///
/// ```
- /// use hashbrown::HashMap;
+ /// use hashbrown::{HashMap, UnavailableMutError};
///
/// let mut libraries = HashMap::new();
/// libraries.insert("Bodleian Library".to_string(), 1602);
@@ -1342,127 +1177,49 @@
/// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
/// libraries.insert("Library of Congress".to_string(), 1800);
///
- /// let got = libraries.get_many_key_value_mut([
+ /// let got = libraries.get_each_key_value_mut([
/// "Bodleian Library",
/// "Herzogin-Anna-Amalia-Bibliothek",
+ /// "Herzogin-Anna-Amalia-Bibliothek",
+ /// "Gewandhaus",
/// ]);
/// assert_eq!(
/// got,
- /// Some([
- /// (&"Bodleian Library".to_string(), &mut 1602),
- /// (&"Herzogin-Anna-Amalia-Bibliothek".to_string(), &mut 1691),
- /// ]),
+ /// [
+ /// Ok((&"Bodleian Library".to_string(), &mut 1602)),
+ /// Ok((&"Herzogin-Anna-Amalia-Bibliothek".to_string(), &mut 1691)),
+ /// Err(UnavailableMutError::Duplicate(1)),
+ /// Err(UnavailableMutError::Absent),
+ /// ]
/// );
- /// // Missing keys result in None
- /// let got = libraries.get_many_key_value_mut([
- /// "Bodleian Library",
- /// "Gewandhaus",
- /// ]);
- /// assert_eq!(got, None);
- ///
- /// // Duplicate keys result in None
- /// let got = libraries.get_many_key_value_mut([
- /// "Bodleian Library",
- /// "Herzogin-Anna-Amalia-Bibliothek",
- /// "Herzogin-Anna-Amalia-Bibliothek",
- /// ]);
- /// assert_eq!(got, None);
/// ```
- pub fn get_many_key_value_mut<Q: ?Sized, const N: usize>(
+ #[cfg(feature = "nightly")]
+ pub fn get_each_key_value_mut<Q: ?Sized, const N: usize>(
&mut self,
ks: [&Q; N],
- ) -> Option<[(&'_ K, &'_ mut V); N]>
+ ) -> [Result<(&'_ K, &'_ mut V), UnavailableMutError>; N]
where
K: Borrow<Q>,
Q: Hash + Eq,
{
- self.get_many_mut_inner(ks)
- .map(|res| res.map(|(k, v)| (&*k, v)))
+ let mut pairs = self.get_each_inner_mut(ks);
+ // TODO use `MaybeUninit::uninit_array` here instead once that's stable.
+ let mut out: [MaybeUninit<Result<(&'_ K, &'_ mut V), UnavailableMutError>>; N] =
+ unsafe { MaybeUninit::uninit().assume_init() };
+ for i in 0..N {
+ out[i] = MaybeUninit::new(
+ mem::replace(&mut pairs[i], Err(UnavailableMutError::Absent))
+ .map(|(k, v)| (&*k, v)),
+ );
+ }
+ unsafe { MaybeUninit::array_assume_init(out) }
}
- /// Attempts to get mutable references to `N` values in the map at once, with immutable
- /// references to the corresponding keys, without validating that the values are unique.
- ///
- /// 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`].
- ///
- /// # Safety
- ///
- /// Calling this method with overlapping keys is *[undefined behavior]* even if the resulting
- /// references are not used.
- ///
- /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut libraries = HashMap::new();
- /// libraries.insert("Bodleian Library".to_string(), 1602);
- /// libraries.insert("Athenæum".to_string(), 1807);
- /// libraries.insert("Herzogin-Anna-Amalia-Bibliothek".to_string(), 1691);
- /// libraries.insert("Library of Congress".to_string(), 1800);
- ///
- /// let got = libraries.get_many_key_value_mut([
- /// "Bodleian Library",
- /// "Herzogin-Anna-Amalia-Bibliothek",
- /// ]);
- /// assert_eq!(
- /// got,
- /// Some([
- /// (&"Bodleian Library".to_string(), &mut 1602),
- /// (&"Herzogin-Anna-Amalia-Bibliothek".to_string(), &mut 1691),
- /// ]),
- /// );
- /// // Missing keys result in None
- /// let got = libraries.get_many_key_value_mut([
- /// "Bodleian Library",
- /// "Gewandhaus",
- /// ]);
- /// assert_eq!(got, None);
- /// ```
- pub unsafe fn get_many_key_value_unchecked_mut<Q: ?Sized, const N: usize>(
+ #[cfg(feature = "nightly")]
+ fn get_each_inner_mut<Q: ?Sized, const N: usize>(
&mut self,
ks: [&Q; N],
- ) -> Option<[(&'_ K, &'_ mut V); N]>
- where
- K: Borrow<Q>,
- Q: Hash + Eq,
- {
- self.get_many_unchecked_mut_inner(ks)
- .map(|res| res.map(|(k, v)| (&*k, v)))
- }
-
- fn get_many_mut_inner<Q: ?Sized, const N: usize>(
- &mut self,
- ks: [&Q; N],
- ) -> Option<[&'_ mut (K, V); N]>
- where
- K: Borrow<Q>,
- Q: Hash + Eq,
- {
- let hashes = self.build_hashes_inner(ks);
- self.table
- .get_many_mut(hashes, |i, (k, _)| ks[i].eq(k.borrow()))
- }
-
- unsafe fn get_many_unchecked_mut_inner<Q: ?Sized, const N: usize>(
- &mut self,
- ks: [&Q; N],
- ) -> Option<[&'_ mut (K, V); N]>
- where
- K: Borrow<Q>,
- Q: Hash + Eq,
- {
- let hashes = self.build_hashes_inner(ks);
- self.table
- .get_many_unchecked_mut(hashes, |i, (k, _)| ks[i].eq(k.borrow()))
- }
-
- fn build_hashes_inner<Q: ?Sized, const N: usize>(&self, ks: [&Q; N]) -> [u64; N]
+ ) -> [Result<&'_ mut (K, V), UnavailableMutError>; N]
where
K: Borrow<Q>,
Q: Hash + Eq,
@@ -1471,7 +1228,8 @@
for i in 0..N {
hashes[i] = make_hash::<K, Q, S>(&self.hash_builder, ks[i]);
}
- hashes
+ self.table
+ .get_each_mut(hashes, |i, (k, _)| ks[i].eq(k.borrow()))
}
/// Inserts a key-value pair into the map.
@@ -1511,36 +1269,6 @@
}
}
- /// Insert a key-value pair into the map without checking
- /// if the key already exists in the map.
- ///
- /// Returns a reference to the key and value just inserted.
- ///
- /// This operation is safe if a key does not exist in the map.
- ///
- /// However, if a key exists in the map already, the behavior is unspecified:
- /// this operation may panic, loop forever, or any following operation with the map
- /// may panic, loop forever or return arbitrary result.
- ///
- /// That said, this operation (and following operations) are guaranteed to
- /// not violate memory safety.
- ///
- /// This operation is faster than regular insert, because it does not perform
- /// lookup before insertion.
- ///
- /// 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.
- #[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);
- let bucket = self
- .table
- .insert(hash, (k, v), make_hasher::<K, _, V, S>(&self.hash_builder));
- let (k_ref, v_ref) = unsafe { bucket.as_mut() };
- (k_ref, v_ref)
- }
-
/// Tries to insert a key-value pair into the map, and returns
/// a mutable reference to the value in the entry.
///
@@ -1767,27 +1495,6 @@
}
}
-// The default hasher is used to match the std implementation signature
-#[cfg(feature = "ahash")]
-impl<K, V, A, const N: usize> From<[(K, V); N]> for HashMap<K, V, DefaultHashBuilder, A>
-where
- K: Eq + Hash,
- A: Default + Allocator + Clone,
-{
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let map1 = HashMap::from([(1, 2), (3, 4)]);
- /// let map2: HashMap<_, _> = [(1, 2), (3, 4)].into();
- /// assert_eq!(map1, map2);
- /// ```
- fn from(arr: [(K, V); N]) -> Self {
- arr.into_iter().collect()
- }
-}
-
/// An iterator over the entries of a `HashMap`.
///
/// This `struct` is created by the [`iter`] method on [`HashMap`]. See its
@@ -1868,88 +1575,6 @@
}
}
-/// An owning iterator over the keys of a `HashMap`.
-///
-/// This `struct` is created by the [`into_keys`] method on [`HashMap`].
-/// See its documentation for more.
-///
-/// [`into_keys`]: struct.HashMap.html#method.into_keys
-/// [`HashMap`]: struct.HashMap.html
-pub struct IntoKeys<K, V, A: Allocator + Clone = Global> {
- inner: IntoIter<K, V, A>,
-}
-
-impl<K, V, A: Allocator + Clone> Iterator for IntoKeys<K, V, A> {
- type Item = K;
-
- #[inline]
- fn next(&mut self) -> Option<K> {
- self.inner.next().map(|(k, _)| k)
- }
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.inner.size_hint()
- }
-}
-
-impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoKeys<K, V, A> {
- #[inline]
- fn len(&self) -> usize {
- self.inner.len()
- }
-}
-
-impl<K, V, A: Allocator + Clone> FusedIterator for IntoKeys<K, V, A> {}
-
-impl<K: Debug, V: Debug, A: Allocator + Clone> fmt::Debug for IntoKeys<K, V, A> {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_list()
- .entries(self.inner.iter().map(|(k, _)| k))
- .finish()
- }
-}
-
-/// An owning iterator over the values of a `HashMap`.
-///
-/// This `struct` is created by the [`into_values`] method on [`HashMap`].
-/// See its documentation for more.
-///
-/// [`into_values`]: struct.HashMap.html#method.into_values
-/// [`HashMap`]: struct.HashMap.html
-pub struct IntoValues<K, V, A: Allocator + Clone = Global> {
- inner: IntoIter<K, V, A>,
-}
-
-impl<K, V, A: Allocator + Clone> Iterator for IntoValues<K, V, A> {
- type Item = V;
-
- #[inline]
- fn next(&mut self) -> Option<V> {
- self.inner.next().map(|(_, v)| v)
- }
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.inner.size_hint()
- }
-}
-
-impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoValues<K, V, A> {
- #[inline]
- fn len(&self) -> usize {
- self.inner.len()
- }
-}
-
-impl<K, V, A: Allocator + Clone> FusedIterator for IntoValues<K, V, A> {}
-
-impl<K: Debug, V: Debug, A: Allocator + Clone> fmt::Debug for IntoValues<K, V, A> {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_list()
- .entries(self.inner.iter().map(|(k, _)| k))
- .finish()
- }
-}
-
/// An iterator over the keys of a `HashMap`.
///
/// This `struct` is created by the [`keys`] method on [`HashMap`]. See its
@@ -2061,7 +1686,7 @@
impl<T: Iterator> Drop for ConsumeAllOnDrop<'_, T> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
- self.0.for_each(drop);
+ self.0.for_each(drop)
}
}
@@ -2098,7 +1723,7 @@
F: FnMut(&K, &mut V) -> bool,
{
unsafe {
- for item in &mut self.iter {
+ while let Some(item) = self.iter.next() {
let &mut (ref key, ref mut value) = item.as_mut();
if f(key, value) {
return Some(self.table.remove(item));
@@ -2161,7 +1786,6 @@
where
K: Send,
V: Send,
- S: Send,
A: Send + Allocator + Clone,
{
}
@@ -2169,8 +1793,7 @@
where
K: Sync,
V: Sync,
- S: Sync,
- A: Sync + Allocator + Clone,
+ A: Send + Allocator + Clone,
{
}
@@ -2790,119 +2413,6 @@
}
}
-/// A view into a single entry in a map, which may either be vacant or occupied.
-///
-/// This `enum` is constructed from the [`entry_ref`] method on [`HashMap`].
-///
-/// [`HashMap`]: struct.HashMap.html
-/// [`entry_ref`]: struct.HashMap.html#method.entry_ref
-pub enum EntryRef<'a, 'b, K, Q: ?Sized, V, S, A = Global>
-where
- A: Allocator + Clone,
-{
- /// An occupied entry.
- Occupied(OccupiedEntryRef<'a, 'b, K, Q, V, S, A>),
-
- /// A vacant entry.
- Vacant(VacantEntryRef<'a, 'b, K, Q, V, S, A>),
-}
-
-impl<K: Borrow<Q>, Q: ?Sized + Debug, V: Debug, S, A: Allocator + Clone> Debug
- for EntryRef<'_, '_, K, Q, V, S, A>
-{
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- match *self {
- EntryRef::Vacant(ref v) => f.debug_tuple("EntryRef").field(v).finish(),
- EntryRef::Occupied(ref o) => f.debug_tuple("EntryRef").field(o).finish(),
- }
- }
-}
-
-enum KeyOrRef<'a, K, Q: ?Sized> {
- Borrowed(&'a Q),
- Owned(K),
-}
-
-impl<'a, K, Q: ?Sized> KeyOrRef<'a, K, Q> {
- fn into_owned(self) -> K
- where
- K: From<&'a Q>,
- {
- match self {
- Self::Borrowed(borrowed) => borrowed.into(),
- Self::Owned(owned) => owned,
- }
- }
-}
-
-impl<'a, K: Borrow<Q>, Q: ?Sized> AsRef<Q> for KeyOrRef<'a, K, Q> {
- fn as_ref(&self) -> &Q {
- match self {
- Self::Borrowed(borrowed) => borrowed,
- Self::Owned(owned) => owned.borrow(),
- }
- }
-}
-
-/// A view into an occupied entry in a `HashMap`.
-/// It is part of the [`EntryRef`] enum.
-///
-/// [`EntryRef`]: enum.EntryRef.html
-pub struct OccupiedEntryRef<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone = Global> {
- hash: u64,
- key: Option<KeyOrRef<'b, K, Q>>,
- elem: Bucket<(K, V)>,
- table: &'a mut HashMap<K, V, S, A>,
-}
-
-unsafe impl<'a, 'b, K, Q, V, S, A> Send for OccupiedEntryRef<'a, 'b, K, Q, V, S, A>
-where
- K: Send,
- Q: Sync + ?Sized,
- V: Send,
- S: Send,
- A: Send + Allocator + Clone,
-{
-}
-unsafe impl<'a, 'b, K, Q, V, S, A> Sync for OccupiedEntryRef<'a, 'b, K, Q, V, S, A>
-where
- K: Sync,
- Q: Sync + ?Sized,
- V: Sync,
- S: Sync,
- A: Sync + Allocator + Clone,
-{
-}
-
-impl<K: Borrow<Q>, Q: ?Sized + Debug, V: Debug, S, A: Allocator + Clone> Debug
- for OccupiedEntryRef<'_, '_, K, Q, V, S, A>
-{
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_struct("OccupiedEntryRef")
- .field("key", &self.key())
- .field("value", &self.get())
- .finish()
- }
-}
-
-/// A view into a vacant entry in a `HashMap`.
-/// It is part of the [`EntryRef`] enum.
-///
-/// [`EntryRef`]: enum.EntryRef.html
-pub struct VacantEntryRef<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone = Global> {
- hash: u64,
- key: KeyOrRef<'b, K, Q>,
- table: &'a mut HashMap<K, V, S, A>,
-}
-
-impl<K: Borrow<Q>, Q: ?Sized + Debug, V, S, A: Allocator + Clone> Debug
- for VacantEntryRef<'_, '_, K, Q, V, S, A>
-{
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- f.debug_tuple("VacantEntryRef").field(&self.key()).finish()
- }
-}
-
/// 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.
@@ -3852,689 +3362,6 @@
}
}
-impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> EntryRef<'a, 'b, K, Q, V, S, A> {
- /// Sets the value of the entry, and returns an OccupiedEntryRef.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// let entry = map.entry_ref("horseyland").insert(37);
- ///
- /// assert_eq!(entry.key(), "horseyland");
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(self, value: V) -> OccupiedEntryRef<'a, 'b, K, Q, V, S, A>
- where
- K: Hash + From<&'b Q>,
- S: BuildHasher,
- {
- match self {
- EntryRef::Occupied(mut entry) => {
- entry.insert(value);
- entry
- }
- EntryRef::Vacant(entry) => entry.insert_entry(value),
- }
- }
-
- /// Ensures a value is in the entry by inserting the default if empty, and returns
- /// a mutable reference to the value in the entry.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- ///
- /// map.entry_ref("poneyland").or_insert(3);
- /// assert_eq!(map["poneyland"], 3);
- ///
- /// *map.entry_ref("poneyland").or_insert(10) *= 2;
- /// assert_eq!(map["poneyland"], 6);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn or_insert(self, default: V) -> &'a mut V
- where
- K: Hash + From<&'b Q>,
- S: BuildHasher,
- {
- match self {
- EntryRef::Occupied(entry) => entry.into_mut(),
- EntryRef::Vacant(entry) => entry.insert(default),
- }
- }
-
- /// Ensures a value is in the entry by inserting the result of the default function if empty,
- /// and returns a mutable reference to the value in the entry.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, String> = HashMap::new();
- /// let s = "hoho".to_string();
- ///
- /// map.entry_ref("poneyland").or_insert_with(|| s);
- ///
- /// assert_eq!(map["poneyland"], "hoho".to_string());
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
- where
- K: Hash + From<&'b Q>,
- S: BuildHasher,
- {
- match self {
- EntryRef::Occupied(entry) => entry.into_mut(),
- EntryRef::Vacant(entry) => entry.insert(default()),
- }
- }
-
- /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
- /// This method allows for generating key-derived values for insertion by providing the default
- /// function a reference to the key that was moved during the `.entry_ref(key)` method call.
- ///
- /// The reference to the moved key is provided so that cloning or copying the key is
- /// unnecessary, unlike with `.or_insert_with(|| ... )`.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, usize> = HashMap::new();
- ///
- /// map.entry_ref("poneyland").or_insert_with_key(|key| key.chars().count());
- ///
- /// assert_eq!(map["poneyland"], 9);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn or_insert_with_key<F: FnOnce(&Q) -> V>(self, default: F) -> &'a mut V
- where
- K: Hash + Borrow<Q> + From<&'b Q>,
- S: BuildHasher,
- {
- match self {
- EntryRef::Occupied(entry) => entry.into_mut(),
- EntryRef::Vacant(entry) => {
- let value = default(entry.key.as_ref());
- entry.insert(value)
- }
- }
- }
-
- /// Returns a reference to this entry's key.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// assert_eq!(map.entry_ref("poneyland").key(), "poneyland");
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn key(&self) -> &Q
- where
- K: Borrow<Q>,
- {
- match *self {
- EntryRef::Occupied(ref entry) => entry.key(),
- EntryRef::Vacant(ref entry) => entry.key(),
- }
- }
-
- /// Provides in-place mutable access to an occupied entry before any
- /// potential inserts into the map.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- ///
- /// map.entry_ref("poneyland")
- /// .and_modify(|e| { *e += 1 })
- /// .or_insert(42);
- /// assert_eq!(map["poneyland"], 42);
- ///
- /// map.entry_ref("poneyland")
- /// .and_modify(|e| { *e += 1 })
- /// .or_insert(42);
- /// assert_eq!(map["poneyland"], 43);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn and_modify<F>(self, f: F) -> Self
- where
- F: FnOnce(&mut V),
- {
- match self {
- EntryRef::Occupied(mut entry) => {
- f(entry.get_mut());
- EntryRef::Occupied(entry)
- }
- EntryRef::Vacant(entry) => EntryRef::Vacant(entry),
- }
- }
-
- /// Provides shared access to the key and owned access to the value of
- /// an occupied entry and allows to replace or remove it based on the
- /// value of the returned option.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- ///
- /// let entry = map
- /// .entry_ref("poneyland")
- /// .and_replace_entry_with(|_k, _v| panic!());
- ///
- /// match entry {
- /// EntryRef::Vacant(e) => {
- /// assert_eq!(e.key(), "poneyland");
- /// }
- /// EntryRef::Occupied(_) => panic!(),
- /// }
- ///
- /// map.insert("poneyland".to_string(), 42);
- ///
- /// let entry = map
- /// .entry_ref("poneyland")
- /// .and_replace_entry_with(|k, v| {
- /// assert_eq!(k, "poneyland");
- /// assert_eq!(v, 42);
- /// Some(v + 1)
- /// });
- ///
- /// match entry {
- /// EntryRef::Occupied(e) => {
- /// assert_eq!(e.key(), "poneyland");
- /// assert_eq!(e.get(), &43);
- /// }
- /// EntryRef::Vacant(_) => panic!(),
- /// }
- ///
- /// assert_eq!(map["poneyland"], 43);
- ///
- /// let entry = map
- /// .entry_ref("poneyland")
- /// .and_replace_entry_with(|_k, _v| None);
- ///
- /// match entry {
- /// EntryRef::Vacant(e) => assert_eq!(e.key(), "poneyland"),
- /// EntryRef::Occupied(_) => panic!(),
- /// }
- ///
- /// assert!(!map.contains_key("poneyland"));
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn and_replace_entry_with<F>(self, f: F) -> Self
- where
- F: FnOnce(&Q, V) -> Option<V>,
- K: Borrow<Q>,
- {
- match self {
- EntryRef::Occupied(entry) => entry.replace_entry_with(f),
- EntryRef::Vacant(_) => self,
- }
- }
-}
-
-impl<'a, 'b, K, Q: ?Sized, V: Default, S, A: Allocator + Clone> EntryRef<'a, 'b, K, Q, V, S, A> {
- /// Ensures a value is in the entry by inserting the default value if empty,
- /// and returns a mutable reference to the value in the entry.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<&str, Option<u32>> = HashMap::new();
- /// map.entry("poneyland").or_default();
- ///
- /// assert_eq!(map["poneyland"], None);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn or_default(self) -> &'a mut V
- where
- K: Hash + From<&'b Q>,
- S: BuildHasher,
- {
- match self {
- EntryRef::Occupied(entry) => entry.into_mut(),
- EntryRef::Vacant(entry) => entry.insert(Default::default()),
- }
- }
-}
-
-impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> OccupiedEntryRef<'a, 'b, K, Q, V, S, A> {
- /// Gets a reference to the key in the entry.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// map.entry_ref("poneyland").or_insert(12);
- /// assert_eq!(map.entry_ref("poneyland").key(), "poneyland");
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn key(&self) -> &Q
- where
- K: Borrow<Q>,
- {
- unsafe { &self.elem.as_ref().0 }.borrow()
- }
-
- /// Take the ownership of the key and value from the map.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// map.entry_ref("poneyland").or_insert(12);
- ///
- /// if let EntryRef::Occupied(o) = map.entry_ref("poneyland") {
- /// // We delete the entry from the map.
- /// o.remove_entry();
- /// }
- ///
- /// assert_eq!(map.contains_key("poneyland"), false);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn remove_entry(self) -> (K, V) {
- unsafe { self.table.table.remove(self.elem) }
- }
-
- /// Gets a reference to the value in the entry.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// 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);
- /// }
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn get(&self) -> &V {
- unsafe { &self.elem.as_ref().1 }
- }
-
- /// Gets a mutable reference to the value in the entry.
- ///
- /// If you need a reference to the `OccupiedEntryRef` which may outlive the
- /// destruction of the `EntryRef` value, see [`into_mut`].
- ///
- /// [`into_mut`]: #method.into_mut
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// map.entry_ref("poneyland").or_insert(12);
- ///
- /// assert_eq!(map["poneyland"], 12);
- /// if let EntryRef::Occupied(mut o) = map.entry_ref("poneyland") {
- /// *o.get_mut() += 10;
- /// assert_eq!(*o.get(), 22);
- ///
- /// // We can use the same Entry multiple times.
- /// *o.get_mut() += 2;
- /// }
- ///
- /// assert_eq!(map["poneyland"], 24);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn get_mut(&mut self) -> &mut V {
- unsafe { &mut self.elem.as_mut().1 }
- }
-
- /// Converts the OccupiedEntryRef into a mutable reference to the value in the entry
- /// with a lifetime bound to the map itself.
- ///
- /// If you need multiple references to the `OccupiedEntryRef`, see [`get_mut`].
- ///
- /// [`get_mut`]: #method.get_mut
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// 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;
- /// }
- ///
- /// assert_eq!(map["poneyland"], 22);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn into_mut(self) -> &'a mut V {
- unsafe { &mut self.elem.as_mut().1 }
- }
-
- /// Sets the value of the entry, and returns the entry's old value.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// map.entry_ref("poneyland").or_insert(12);
- ///
- /// if let EntryRef::Occupied(mut o) = map.entry_ref("poneyland") {
- /// assert_eq!(o.insert(15), 12);
- /// }
- ///
- /// assert_eq!(map["poneyland"], 15);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(&mut self, mut value: V) -> V {
- let old_value = self.get_mut();
- mem::swap(&mut value, old_value);
- value
- }
-
- /// Takes the value out of the entry, and returns it.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// 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.remove(), 12);
- /// }
- ///
- /// assert_eq!(map.contains_key("poneyland"), false);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn remove(self) -> V {
- self.remove_entry().1
- }
-
- /// Replaces the entry, returning the old key and value. The new key in the hash map will be
- /// the key used to create this entry.
- ///
- /// # Panics
- ///
- /// Will panic if this OccupiedEntry was created through [`EntryRef::insert`].
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::hash_map::{EntryRef, HashMap};
- /// use std::rc::Rc;
- ///
- /// let mut map: HashMap<Rc<str>, u32> = HashMap::new();
- /// map.insert(Rc::from("Stringthing"), 15);
- ///
- /// 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);
- /// }
- ///
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn replace_entry(self, value: V) -> (K, V)
- where
- K: From<&'b Q>,
- {
- let entry = unsafe { self.elem.as_mut() };
-
- let old_key = mem::replace(&mut entry.0, self.key.unwrap().into_owned());
- let old_value = mem::replace(&mut entry.1, value);
-
- (old_key, old_value)
- }
-
- /// Replaces the key in the hash map with the key used to create this entry.
- ///
- /// # Panics
- ///
- /// Will panic if this OccupiedEntry was created through [`Entry::insert`].
- ///
- /// # Examples
- ///
- /// ```
- /// 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();
- ///
- /// // Initialise known strings, run program, etc.
- ///
- /// reclaim_memory(&mut map, &known_strings);
- ///
- /// 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`.
- /// entry.replace_key();
- /// }
- /// }
- /// }
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn replace_key(self) -> K
- where
- K: From<&'b Q>,
- {
- let entry = unsafe { self.elem.as_mut() };
- mem::replace(&mut entry.0, self.key.unwrap().into_owned())
- }
-
- /// 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::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// map.insert("poneyland".to_string(), 42);
- ///
- /// let entry = match map.entry_ref("poneyland") {
- /// EntryRef::Occupied(e) => {
- /// e.replace_entry_with(|k, v| {
- /// assert_eq!(k, "poneyland");
- /// assert_eq!(v, 42);
- /// Some(v + 1)
- /// })
- /// }
- /// EntryRef::Vacant(_) => panic!(),
- /// };
- ///
- /// match entry {
- /// EntryRef::Occupied(e) => {
- /// assert_eq!(e.key(), "poneyland");
- /// assert_eq!(e.get(), &43);
- /// }
- /// EntryRef::Vacant(_) => panic!(),
- /// }
- ///
- /// assert_eq!(map["poneyland"], 43);
- ///
- /// let entry = match map.entry_ref("poneyland") {
- /// EntryRef::Occupied(e) => e.replace_entry_with(|_k, _v| None),
- /// EntryRef::Vacant(_) => panic!(),
- /// };
- ///
- /// match entry {
- /// EntryRef::Vacant(e) => {
- /// assert_eq!(e.key(), "poneyland");
- /// }
- /// EntryRef::Occupied(_) => panic!(),
- /// }
- ///
- /// assert!(!map.contains_key("poneyland"));
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn replace_entry_with<F>(self, f: F) -> EntryRef<'a, 'b, K, Q, V, S, A>
- where
- F: FnOnce(&Q, V) -> Option<V>,
- K: Borrow<Q>,
- {
- unsafe {
- let mut spare_key = None;
-
- self.table
- .table
- .replace_bucket_with(self.elem.clone(), |(key, value)| {
- if let Some(new_value) = f(key.borrow(), value) {
- Some((key, new_value))
- } else {
- spare_key = Some(KeyOrRef::Owned(key));
- None
- }
- });
-
- if let Some(key) = spare_key {
- EntryRef::Vacant(VacantEntryRef {
- hash: self.hash,
- key,
- table: self.table,
- })
- } else {
- EntryRef::Occupied(self)
- }
- }
- }
-}
-
-impl<'a, 'b, K, Q: ?Sized, V, S, A: Allocator + Clone> VacantEntryRef<'a, 'b, K, Q, V, S, A> {
- /// Gets a reference to the key that would be used when inserting a value
- /// through the `VacantEntryRef`.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// let key: &str = "poneyland";
- /// assert_eq!(map.entry_ref(key).key(), "poneyland");
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn key(&self) -> &Q
- where
- K: Borrow<Q>,
- {
- self.key.as_ref()
- }
-
- /// Take ownership of the key.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// let key: &str = "poneyland";
- ///
- /// if let EntryRef::Vacant(v) = map.entry_ref(key) {
- /// v.into_key();
- /// }
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn into_key(self) -> K
- where
- K: From<&'b Q>,
- {
- self.key.into_owned()
- }
-
- /// Sets the value of the entry with the VacantEntryRef's key,
- /// and returns a mutable reference to it.
- ///
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashMap;
- /// use hashbrown::hash_map::EntryRef;
- ///
- /// let mut map: HashMap<String, u32> = HashMap::new();
- /// let key: &str = "poneyland";
- ///
- /// if let EntryRef::Vacant(o) = map.entry_ref(key) {
- /// o.insert(37);
- /// }
- /// assert_eq!(map["poneyland"], 37);
- /// ```
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(self, value: V) -> &'a mut V
- where
- K: Hash + From<&'b Q>,
- S: BuildHasher,
- {
- let table = &mut self.table.table;
- let entry = table.insert_entry(
- self.hash,
- (self.key.into_owned(), value),
- make_hasher::<K, _, V, S>(&self.table.hash_builder),
- );
- &mut entry.1
- }
-
- #[cfg_attr(feature = "inline-more", inline)]
- fn insert_entry(self, value: V) -> OccupiedEntryRef<'a, 'b, K, Q, V, S, A>
- where
- K: Hash + From<&'b Q>,
- S: BuildHasher,
- {
- let elem = self.table.table.insert(
- self.hash,
- (self.key.into_owned(), value),
- make_hasher::<K, _, V, S>(&self.table.hash_builder),
- );
- OccupiedEntryRef {
- hash: self.hash,
- key: None,
- elem,
- table: self.table,
- }
- }
-}
-
impl<K, V, S, A> FromIterator<(K, V)> for HashMap<K, V, S, A>
where
K: Eq + Hash,
@@ -4673,8 +3500,8 @@
mod test_map {
use super::DefaultHashBuilder;
use super::Entry::{Occupied, Vacant};
- use super::EntryRef;
use super::{HashMap, RawEntryMut};
+ use crate::TryReserveError::*;
use rand::{rngs::SmallRng, Rng, SeedableRng};
use std::borrow::ToOwned;
use std::cell::RefCell;
@@ -4743,7 +3570,6 @@
assert_eq!(m.len(), 1);
assert!(m.insert(2, 4).is_none());
assert_eq!(m.len(), 2);
- #[allow(clippy::redundant_clone)]
let m2 = m.clone();
assert_eq!(*m2.get(&1).unwrap(), 2);
assert_eq!(*m2.get(&2).unwrap(), 4);
@@ -4897,7 +3723,6 @@
}
});
- #[allow(clippy::let_underscore_drop)] // kind-of a false positive
for _ in half.by_ref() {}
DROP_VECTOR.with(|v| {
@@ -4935,17 +3760,6 @@
}
#[test]
- fn test_empty_entry_ref() {
- let mut m: HashMap<std::string::String, bool> = HashMap::new();
- match m.entry_ref("poneyland") {
- EntryRef::Occupied(_) => panic!(),
- EntryRef::Vacant(_) => {}
- }
- assert!(*m.entry_ref("poneyland").or_insert(true));
- assert_eq!(m.len(), 1);
- }
-
- #[test]
fn test_empty_iter() {
let mut m: HashMap<i32, bool> = HashMap::new();
assert_eq!(m.drain().next(), None);
@@ -5075,18 +3889,6 @@
}
#[test]
- fn test_insert_unique_unchecked() {
- let mut map = HashMap::new();
- let (k1, v1) = map.insert_unique_unchecked(10, 11);
- assert_eq!((&10, &mut 11), (k1, v1));
- let (k2, v2) = map.insert_unique_unchecked(20, 21);
- assert_eq!((&20, &mut 21), (k2, v2));
- assert_eq!(Some(&11), map.get(&10));
- assert_eq!(Some(&21), map.get(&20));
- assert_eq!(None, map.get(&30));
- }
-
- #[test]
fn test_is_empty() {
let mut m = HashMap::with_capacity(4);
assert!(m.insert(1, 2).is_none());
@@ -5132,7 +3934,7 @@
fn test_keys() {
let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
let map: HashMap<_, _> = vec.into_iter().collect();
- let keys: Vec<_> = map.keys().copied().collect();
+ let keys: Vec<_> = map.keys().cloned().collect();
assert_eq!(keys.len(), 3);
assert!(keys.contains(&1));
assert!(keys.contains(&2));
@@ -5143,7 +3945,7 @@
fn test_values() {
let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
let map: HashMap<_, _> = vec.into_iter().collect();
- let values: Vec<_> = map.values().copied().collect();
+ let values: Vec<_> = map.values().cloned().collect();
assert_eq!(values.len(), 3);
assert!(values.contains(&'a'));
assert!(values.contains(&'b'));
@@ -5155,9 +3957,9 @@
let vec = vec![(1, 1), (2, 2), (3, 3)];
let mut map: HashMap<_, _> = vec.into_iter().collect();
for value in map.values_mut() {
- *value *= 2;
+ *value = (*value) * 2
}
- let values: Vec<_> = map.values().copied().collect();
+ let values: Vec<_> = map.values().cloned().collect();
assert_eq!(values.len(), 3);
assert!(values.contains(&2));
assert!(values.contains(&4));
@@ -5165,30 +3967,6 @@
}
#[test]
- fn test_into_keys() {
- let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
- let map: HashMap<_, _> = vec.into_iter().collect();
- let keys: Vec<_> = map.into_keys().collect();
-
- assert_eq!(keys.len(), 3);
- assert!(keys.contains(&1));
- assert!(keys.contains(&2));
- assert!(keys.contains(&3));
- }
-
- #[test]
- fn test_into_values() {
- let vec = vec![(1, 'a'), (2, 'b'), (3, 'c')];
- let map: HashMap<_, _> = vec.into_iter().collect();
- let values: Vec<_> = map.into_values().collect();
-
- assert_eq!(values.len(), 3);
- assert!(values.contains(&'a'));
- assert!(values.contains(&'b'));
- assert!(values.contains(&'c'));
- }
-
- #[test]
fn test_find() {
let mut m = HashMap::new();
assert!(m.get(&1).is_none());
@@ -5346,7 +4124,7 @@
fn test_from_iter() {
let xs = [(1, 1), (2, 2), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
- let map: HashMap<_, _> = xs.iter().copied().collect();
+ let map: HashMap<_, _> = xs.iter().cloned().collect();
for &(k, v) in &xs {
assert_eq!(map.get(&k), Some(&v));
@@ -5359,7 +4137,7 @@
fn test_size_hint() {
let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
- let map: HashMap<_, _> = xs.iter().copied().collect();
+ let map: HashMap<_, _> = xs.iter().cloned().collect();
let mut iter = map.iter();
@@ -5372,7 +4150,7 @@
fn test_iter_len() {
let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
- let map: HashMap<_, _> = xs.iter().copied().collect();
+ let map: HashMap<_, _> = xs.iter().cloned().collect();
let mut iter = map.iter();
@@ -5385,7 +4163,7 @@
fn test_mut_size_hint() {
let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
- let mut map: HashMap<_, _> = xs.iter().copied().collect();
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
let mut iter = map.iter_mut();
@@ -5398,7 +4176,7 @@
fn test_iter_mut_len() {
let xs = [(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
- let mut map: HashMap<_, _> = xs.iter().copied().collect();
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
let mut iter = map.iter_mut();
@@ -5427,7 +4205,6 @@
map.insert(2, 1);
map.insert(3, 4);
- #[allow(clippy::no_effect)] // false positive lint
map[&4];
}
@@ -5435,7 +4212,7 @@
fn test_entry() {
let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
- let mut map: HashMap<_, _> = xs.iter().copied().collect();
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
// Existing key (insert)
match map.entry(1) {
@@ -5482,63 +4259,6 @@
}
#[test]
- fn test_entry_ref() {
- let xs = [
- ("One".to_owned(), 10),
- ("Two".to_owned(), 20),
- ("Three".to_owned(), 30),
- ("Four".to_owned(), 40),
- ("Five".to_owned(), 50),
- ("Six".to_owned(), 60),
- ];
-
- let mut map: HashMap<_, _> = xs.iter().cloned().collect();
-
- // Existing key (insert)
- match map.entry_ref("One") {
- EntryRef::Vacant(_) => unreachable!(),
- EntryRef::Occupied(mut view) => {
- assert_eq!(view.get(), &10);
- assert_eq!(view.insert(100), 10);
- }
- }
- assert_eq!(map.get("One").unwrap(), &100);
- assert_eq!(map.len(), 6);
-
- // Existing key (update)
- match map.entry_ref("Two") {
- EntryRef::Vacant(_) => unreachable!(),
- EntryRef::Occupied(mut view) => {
- let v = view.get_mut();
- let new_v = (*v) * 10;
- *v = new_v;
- }
- }
- assert_eq!(map.get("Two").unwrap(), &200);
- assert_eq!(map.len(), 6);
-
- // Existing key (take)
- match map.entry_ref("Three") {
- EntryRef::Vacant(_) => unreachable!(),
- EntryRef::Occupied(view) => {
- assert_eq!(view.remove(), 30);
- }
- }
- assert_eq!(map.get("Three"), None);
- assert_eq!(map.len(), 5);
-
- // Inexistent key (insert)
- match map.entry_ref("Ten") {
- EntryRef::Occupied(_) => unreachable!(),
- EntryRef::Vacant(view) => {
- assert_eq!(*view.insert(1000), 1000);
- }
- }
- assert_eq!(map.get("Ten").unwrap(), &1000);
- assert_eq!(map.len(), 6);
- }
-
- #[test]
fn test_entry_take_doesnt_corrupt() {
#![allow(deprecated)] //rand
// Test for #19292
@@ -5551,18 +4271,18 @@
let mut m = HashMap::new();
let mut rng = {
- let seed = u64::from_le_bytes(*b"testseed");
- SmallRng::seed_from_u64(seed)
+ let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
+ SmallRng::from_seed(seed)
};
// Populate the map with some items.
for _ in 0..50 {
- let x = rng.gen_range(-10..10);
+ let x = rng.gen_range(-10, 10);
m.insert(x, ());
}
for _ in 0..1000 {
- let x = rng.gen_range(-10..10);
+ let x = rng.gen_range(-10, 10);
match m.entry(x) {
Vacant(_) => {}
Occupied(e) => {
@@ -5575,44 +4295,6 @@
}
#[test]
- fn test_entry_ref_take_doesnt_corrupt() {
- #![allow(deprecated)] //rand
- // Test for #19292
- fn check(m: &HashMap<std::string::String, ()>) {
- for k in m.keys() {
- assert!(m.contains_key(k), "{} is in keys() but not in the map?", k);
- }
- }
-
- let mut m = HashMap::new();
-
- let mut rng = {
- let seed = u64::from_le_bytes(*b"testseed");
- SmallRng::seed_from_u64(seed)
- };
-
- // Populate the map with some items.
- for _ in 0..50 {
- let mut x = std::string::String::with_capacity(1);
- x.push(rng.gen_range('a'..='z'));
- m.insert(x, ());
- }
-
- for _ in 0..1000 {
- let mut x = std::string::String::with_capacity(1);
- x.push(rng.gen_range('a'..='z'));
- match m.entry_ref(x.as_str()) {
- EntryRef::Vacant(_) => {}
- EntryRef::Occupied(e) => {
- e.remove();
- }
- }
-
- check(&m);
- }
- }
-
- #[test]
fn test_extend_ref() {
let mut a = HashMap::new();
a.insert(1, "one");
@@ -5659,11 +4341,11 @@
let key = "hello there";
let value = "value goes here";
assert!(a.is_empty());
- a.insert(key, value);
+ a.insert(key.clone(), value.clone());
assert_eq!(a.len(), 1);
assert_eq!(a[key], value);
- match a.entry(key) {
+ match a.entry(key.clone()) {
Vacant(_) => panic!(),
Occupied(e) => assert_eq!(key, *e.key()),
}
@@ -5672,53 +4354,17 @@
}
#[test]
- fn test_occupied_entry_ref_key() {
- let mut a = HashMap::new();
- let key = "hello there";
- let value = "value goes here";
- assert!(a.is_empty());
- a.insert(key.to_owned(), value);
- assert_eq!(a.len(), 1);
- assert_eq!(a[key], value);
-
- match a.entry_ref(key) {
- EntryRef::Vacant(_) => panic!(),
- EntryRef::Occupied(e) => assert_eq!(key, e.key()),
- }
- assert_eq!(a.len(), 1);
- assert_eq!(a[key], value);
- }
-
- #[test]
fn test_vacant_entry_key() {
let mut a = HashMap::new();
let key = "hello there";
let value = "value goes here";
assert!(a.is_empty());
- match a.entry(key) {
+ match a.entry(key.clone()) {
Occupied(_) => panic!(),
Vacant(e) => {
assert_eq!(key, *e.key());
- e.insert(value);
- }
- }
- assert_eq!(a.len(), 1);
- assert_eq!(a[key], value);
- }
-
- #[test]
- fn test_vacant_entry_ref_key() {
- let mut a: HashMap<std::string::String, &str> = HashMap::new();
- let key = "hello there";
- let value = "value goes here";
-
- assert!(a.is_empty());
- match a.entry_ref(key) {
- EntryRef::Occupied(_) => panic!(),
- EntryRef::Vacant(e) => {
- assert_eq!(key, e.key());
- e.insert(value);
+ e.insert(value.clone());
}
}
assert_eq!(a.len(), 1);
@@ -5769,49 +4415,6 @@
}
#[test]
- fn test_occupied_entry_ref_replace_entry_with() {
- let mut a: HashMap<std::string::String, &str> = HashMap::new();
-
- let key = "a key";
- let value = "an initial value";
- let new_value = "a new value";
-
- let entry = a.entry_ref(key).insert(value).replace_entry_with(|k, v| {
- assert_eq!(k, key);
- assert_eq!(v, value);
- Some(new_value)
- });
-
- match entry {
- EntryRef::Occupied(e) => {
- assert_eq!(e.key(), key);
- assert_eq!(e.get(), &new_value);
- }
- EntryRef::Vacant(_) => panic!(),
- }
-
- assert_eq!(a[key], new_value);
- assert_eq!(a.len(), 1);
-
- let entry = match a.entry_ref(key) {
- EntryRef::Occupied(e) => e.replace_entry_with(|k, v| {
- assert_eq!(k, key);
- assert_eq!(v, new_value);
- None
- }),
- EntryRef::Vacant(_) => panic!(),
- };
-
- match entry {
- EntryRef::Vacant(e) => assert_eq!(e.key(), key),
- EntryRef::Occupied(_) => panic!(),
- }
-
- assert!(!a.contains_key(key));
- assert_eq!(a.len(), 0);
- }
-
- #[test]
fn test_entry_and_replace_entry_with() {
let mut a = HashMap::new();
@@ -5861,55 +4464,6 @@
}
#[test]
- fn test_entry_ref_and_replace_entry_with() {
- let mut a = HashMap::new();
-
- let key = "a key";
- let value = "an initial value";
- let new_value = "a new value";
-
- let entry = a.entry_ref(key).and_replace_entry_with(|_, _| panic!());
-
- match entry {
- EntryRef::Vacant(e) => assert_eq!(e.key(), key),
- EntryRef::Occupied(_) => panic!(),
- }
-
- a.insert(key.to_owned(), value);
-
- let entry = a.entry_ref(key).and_replace_entry_with(|k, v| {
- assert_eq!(k, key);
- assert_eq!(v, value);
- Some(new_value)
- });
-
- match entry {
- EntryRef::Occupied(e) => {
- assert_eq!(e.key(), key);
- assert_eq!(e.get(), &new_value);
- }
- EntryRef::Vacant(_) => panic!(),
- }
-
- assert_eq!(a[key], new_value);
- assert_eq!(a.len(), 1);
-
- let entry = a.entry_ref(key).and_replace_entry_with(|k, v| {
- assert_eq!(k, key);
- assert_eq!(v, new_value);
- None
- });
-
- match entry {
- EntryRef::Vacant(e) => assert_eq!(e.key(), key),
- EntryRef::Occupied(_) => panic!(),
- }
-
- assert!(!a.contains_key(key));
- assert_eq!(a.len(), 0);
- }
-
- #[test]
fn test_raw_occupied_entry_replace_entry_with() {
let mut a = HashMap::new();
@@ -6027,56 +4581,24 @@
let mut m = HashMap::new();
let mut rng = {
- let seed = u64::from_le_bytes(*b"testseed");
- SmallRng::seed_from_u64(seed)
+ let seed = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
+ SmallRng::from_seed(seed)
};
// Populate the map with some items.
for _ in 0..50 {
- let x = rng.gen_range(-10..10);
+ let x = rng.gen_range(-10, 10);
m.insert(x, ());
}
for _ in 0..1000 {
- let x = rng.gen_range(-10..10);
+ let x = rng.gen_range(-10, 10);
m.entry(x).and_replace_entry_with(|_, _| None);
check(&m);
}
}
#[test]
- fn test_replace_entry_ref_with_doesnt_corrupt() {
- #![allow(deprecated)] //rand
- // Test for #19292
- fn check(m: &HashMap<std::string::String, ()>) {
- for k in m.keys() {
- assert!(m.contains_key(k), "{} is in keys() but not in the map?", k);
- }
- }
-
- let mut m = HashMap::new();
-
- let mut rng = {
- let seed = u64::from_le_bytes(*b"testseed");
- SmallRng::seed_from_u64(seed)
- };
-
- // Populate the map with some items.
- for _ in 0..50 {
- let mut x = std::string::String::with_capacity(1);
- x.push(rng.gen_range('a'..='z'));
- m.insert(x, ());
- }
-
- for _ in 0..1000 {
- let mut x = std::string::String::with_capacity(1);
- x.push(rng.gen_range('a'..='z'));
- m.entry_ref(x.as_str()).and_replace_entry_with(|_, _| None);
- check(&m);
- }
- }
-
- #[test]
fn test_retain() {
let mut map: HashMap<i32, i32> = (0..100).map(|x| (x, x * 10)).collect();
@@ -6107,27 +4629,21 @@
#[test]
#[cfg_attr(miri, ignore)] // FIXME: no OOM signalling (https://github.com/rust-lang/miri/issues/613)
fn test_try_reserve() {
- use crate::TryReserveError::{AllocError, CapacityOverflow};
+ let mut empty_bytes: HashMap<u8, u8> = HashMap::new();
const MAX_USIZE: usize = usize::MAX;
- let mut empty_bytes: HashMap<u8, u8> = HashMap::new();
-
if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
} else {
panic!("usize::MAX should trigger an overflow!");
}
- if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE / 16) {
+ if let Err(AllocError { .. }) = empty_bytes.try_reserve(MAX_USIZE / 8) {
} else {
// This may succeed if there is enough free memory. Attempt to
- // allocate a few more hashmaps to ensure the allocation will fail.
+ // allocate a second hashmap to ensure the allocation will fail.
let mut empty_bytes2: HashMap<u8, u8> = HashMap::new();
- let _ = empty_bytes2.try_reserve(MAX_USIZE / 16);
- let mut empty_bytes3: HashMap<u8, u8> = HashMap::new();
- let _ = empty_bytes3.try_reserve(MAX_USIZE / 16);
- let mut empty_bytes4: HashMap<u8, u8> = HashMap::new();
- if let Err(AllocError { .. }) = empty_bytes4.try_reserve(MAX_USIZE / 16) {
+ if let Err(AllocError { .. }) = empty_bytes2.try_reserve(MAX_USIZE / 8) {
} else {
panic!("usize::MAX / 8 should trigger an OOM!");
}
@@ -6138,9 +4654,9 @@
fn test_raw_entry() {
use super::RawEntryMut::{Occupied, Vacant};
- let xs = [(1_i32, 10_i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
+ let xs = [(1i32, 10i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
- let mut map: HashMap<_, _> = xs.iter().copied().collect();
+ let mut map: HashMap<_, _> = xs.iter().cloned().collect();
let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 {
super::make_insert_hash::<i32, _>(map.hasher(), &k)
@@ -6213,7 +4729,7 @@
// Ensure all lookup methods produce equivalent results.
for k in 0..12 {
let hash = compute_hash(&map, k);
- let v = map.get(&k).copied();
+ let v = map.get(&k).cloned();
let kv = v.as_ref().map(|v| (&k, v));
assert_eq!(map.raw_entry().from_key(&k), kv);
@@ -6283,6 +4799,8 @@
#[test]
#[cfg(feature = "raw")]
fn test_into_iter_refresh() {
+ use core::hash::{BuildHasher, Hash, Hasher};
+
#[cfg(miri)]
const N: usize = 32;
#[cfg(not(miri))]
@@ -6290,13 +4808,13 @@
let mut rng = rand::thread_rng();
for n in 0..N {
- let mut map = HashMap::new();
+ let mut m = HashMap::new();
for i in 0..n {
- assert!(map.insert(i, 2 * i).is_none());
+ assert!(m.insert(i, 2 * i).is_none());
}
- let hash_builder = map.hasher().clone();
+ let hasher = m.hasher().clone();
- let mut it = unsafe { map.table.iter() };
+ let mut it = unsafe { m.table.iter() };
assert_eq!(it.len(), n);
let mut i = 0;
@@ -6305,21 +4823,23 @@
loop {
// occasionally remove some elements
if i < n && rng.gen_bool(0.1) {
- let hash_value = super::make_insert_hash(&hash_builder, &i);
+ let mut hsh = hasher.build_hasher();
+ i.hash(&mut hsh);
+ let hash = hsh.finish();
unsafe {
- let e = map.table.find(hash_value, |q| q.0.eq(&i));
+ let e = m.table.find(hash, |q| q.0.eq(&i));
if let Some(e) = e {
it.reflect_remove(&e);
- let t = map.table.remove(e);
+ let t = m.table.remove(e);
removed.push(t);
left -= 1;
} else {
assert!(removed.contains(&(i, 2 * i)), "{} not in {:?}", i, removed);
- let e = map.table.insert(
- hash_value,
+ let e = m.table.insert(
+ hash,
(i, 2 * i),
- super::make_hasher::<usize, _, usize, _>(&hash_builder),
+ super::make_hasher::<usize, _, usize, _>(&hasher),
);
it.reflect_insert(&e);
if let Some(p) = removed.iter().position(|e| e == &(i, 2 * i)) {
@@ -6337,14 +4857,14 @@
assert!(i < n);
let t = unsafe { e.unwrap().as_ref() };
assert!(!removed.contains(t));
- let (key, value) = t;
- assert_eq!(*value, 2 * key);
+ let (k, v) = t;
+ assert_eq!(*v, 2 * k);
i += 1;
}
assert!(i <= n);
// just for safety:
- assert_eq!(map.table.len(), left);
+ assert_eq!(m.table.len(), left);
}
}
@@ -6366,38 +4886,37 @@
const EMPTY_MAP: HashMap<u32, std::string::String, MyHasher> =
HashMap::with_hasher(MyHasher);
- let mut map = EMPTY_MAP;
+ let mut map = EMPTY_MAP.clone();
map.insert(17, "seventeen".to_owned());
assert_eq!("seventeen", map[&17]);
}
#[test]
+ #[cfg(feature = "nightly")]
fn test_get_each_mut() {
+ use crate::UnavailableMutError::*;
+
let mut map = HashMap::new();
map.insert("foo".to_owned(), 0);
map.insert("bar".to_owned(), 10);
map.insert("baz".to_owned(), 20);
map.insert("qux".to_owned(), 30);
- let xs = map.get_many_mut(["foo", "qux"]);
- assert_eq!(xs, Some([&mut 0, &mut 30]));
-
- let xs = map.get_many_mut(["foo", "dud"]);
- assert_eq!(xs, None);
-
- let xs = map.get_many_mut(["foo", "foo"]);
- assert_eq!(xs, None);
-
- let ys = map.get_many_key_value_mut(["bar", "baz"]);
+ let xs = map.get_each_mut(["foo", "dud", "foo", "qux"]);
assert_eq!(
- ys,
- Some([(&"bar".to_owned(), &mut 10), (&"baz".to_owned(), &mut 20),]),
+ xs,
+ [Ok(&mut 0), Err(Absent), Err(Duplicate(0)), Ok(&mut 30)]
);
- let ys = map.get_many_key_value_mut(["bar", "dip"]);
- assert_eq!(ys, None);
-
- let ys = map.get_many_key_value_mut(["baz", "baz"]);
- assert_eq!(ys, None);
+ let ys = map.get_each_key_value_mut(["bar", "baz", "baz", "dip"]);
+ assert_eq!(
+ ys,
+ [
+ Ok((&"bar".to_owned(), &mut 10)),
+ Ok((&"baz".to_owned(), &mut 20)),
+ Err(Duplicate(1)),
+ Err(Absent),
+ ]
+ );
}
}
diff --git a/src/raw/alloc.rs b/src/raw/alloc.rs
index 76fe1e9..de6c455 100644
--- a/src/raw/alloc.rs
+++ b/src/raw/alloc.rs
@@ -33,7 +33,6 @@
use crate::alloc::alloc::{alloc, dealloc, Layout};
use core::ptr::NonNull;
- #[allow(clippy::missing_safety_doc)] // not exposed outside of this crate
pub unsafe trait Allocator {
fn allocate(&self, layout: Layout) -> Result<NonNull<u8>, ()>;
unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
@@ -48,7 +47,7 @@
}
#[inline]
unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
- dealloc(ptr.as_ptr(), layout);
+ dealloc(ptr.as_ptr(), layout)
}
}
impl Default for Global {
diff --git a/src/raw/bitmask.rs b/src/raw/bitmask.rs
index 7d4f9fc..99b2d53 100644
--- a/src/raw/bitmask.rs
+++ b/src/raw/bitmask.rs
@@ -106,7 +106,7 @@
}
}
-/// Iterator over the contents of a `BitMask`, returning the indices of set
+/// Iterator over the contents of a `BitMask`, returning the indicies of set
/// bits.
pub struct BitMaskIter(BitMask);
diff --git a/src/raw/generic.rs b/src/raw/generic.rs
index b4d31e6..ef066e8 100644
--- a/src/raw/generic.rs
+++ b/src/raw/generic.rs
@@ -9,14 +9,12 @@
target_pointer_width = "64",
target_arch = "aarch64",
target_arch = "x86_64",
- target_arch = "wasm32",
))]
type GroupWord = u64;
#[cfg(all(
target_pointer_width = "32",
not(target_arch = "aarch64"),
not(target_arch = "x86_64"),
- not(target_arch = "wasm32"),
))]
type GroupWord = u32;
@@ -39,7 +37,7 @@
#[derive(Copy, Clone)]
pub struct Group(GroupWord);
-// We perform all operations in the native endianness, and convert to
+// We perform all operations in the native endianess, and convert to
// little-endian just before creating a BitMask. The can potentially
// enable the compiler to eliminate unnecessary byte swaps if we are
// only checking whether a BitMask is empty.
@@ -52,7 +50,6 @@
/// value for an empty hash table.
///
/// This is guaranteed to be aligned to the group size.
- #[inline]
pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
#[repr(C)]
struct AlignedBytes {
@@ -106,7 +103,7 @@
#[inline]
pub fn match_byte(self, byte: u8) -> BitMask {
// This algorithm is derived from
- // https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
+ // http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
let cmp = self.0 ^ repeat(byte);
BitMask((cmp.wrapping_sub(repeat(0x01)) & !cmp & repeat(0x80)).to_le())
}
diff --git a/src/raw/mod.rs b/src/raw/mod.rs
index fce54d9..3ae6980 100644
--- a/src/raw/mod.rs
+++ b/src/raw/mod.rs
@@ -1,13 +1,16 @@
use crate::alloc::alloc::{handle_alloc_error, Layout};
use crate::scopeguard::guard;
use crate::TryReserveError;
+#[cfg(feature = "nightly")]
+use crate::UnavailableMutError;
+use core::hint;
use core::iter::FusedIterator;
use core::marker::PhantomData;
use core::mem;
use core::mem::ManuallyDrop;
+#[cfg(feature = "nightly")]
use core::mem::MaybeUninit;
use core::ptr::NonNull;
-use core::{hint, ptr};
cfg_if! {
// Use the SSE2 implementation if possible: it allows us to scan 16 buckets
@@ -56,7 +59,7 @@
#[inline]
fn likely(b: bool) -> bool {
if !b {
- cold();
+ cold()
}
b
}
@@ -64,18 +67,18 @@
#[inline]
fn unlikely(b: bool) -> bool {
if b {
- cold();
+ cold()
}
b
}
#[cfg(feature = "nightly")]
-#[inline]
+#[cfg_attr(feature = "inline-more", inline)]
unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
to.offset_from(from) as usize
}
#[cfg(not(feature = "nightly"))]
-#[inline]
+#[cfg_attr(feature = "inline-more", inline)]
unsafe fn offset_from<T>(to: *const T, from: *const T) -> usize {
(to as usize - from as usize) / mem::size_of::<T>()
}
@@ -208,7 +211,7 @@
// Any overflows will have been caught by the checked_mul. Also, any
// rounding errors from the division above will be cleaned up by
- // next_power_of_two (which can't overflow because of the previous division).
+ // next_power_of_two (which can't overflow because of the previous divison).
Some(adjusted_cap.next_power_of_two())
}
@@ -289,14 +292,14 @@
unsafe impl<T> Send for Bucket<T> {}
impl<T> Clone for Bucket<T> {
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Self { ptr: self.ptr }
}
}
impl<T> Bucket<T> {
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
unsafe fn from_base_index(base: NonNull<T>, index: usize) -> Self {
let ptr = if mem::size_of::<T>() == 0 {
// won't overflow because index must be less than length
@@ -308,7 +311,7 @@
ptr: NonNull::new_unchecked(ptr),
}
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
unsafe fn to_base_index(&self, base: NonNull<T>) -> usize {
if mem::size_of::<T>() == 0 {
self.ptr.as_ptr() as usize - 1
@@ -316,7 +319,7 @@
offset_from(base.as_ptr(), self.ptr.as_ptr())
}
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub fn as_ptr(&self) -> *mut T {
if mem::size_of::<T>() == 0 {
// Just return an arbitrary ZST pointer which is properly aligned
@@ -325,7 +328,7 @@
unsafe { self.ptr.as_ptr().sub(1) }
}
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
unsafe fn next_n(&self, offset: usize) -> Self {
let ptr = if mem::size_of::<T>() == 0 {
(self.ptr.as_ptr() as usize + offset) as *mut T
@@ -340,24 +343,23 @@
pub unsafe fn drop(&self) {
self.as_ptr().drop_in_place();
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn read(&self) -> T {
self.as_ptr().read()
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn write(&self, val: T) {
self.as_ptr().write(val);
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn as_ref<'a>(&self) -> &'a T {
&*self.as_ptr()
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn as_mut<'a>(&self) -> &'a mut T {
&mut *self.as_ptr()
}
- #[cfg(feature = "raw")]
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn copy_from_nonoverlapping(&self, other: &Self) {
self.as_ptr().copy_from_nonoverlapping(other.as_ptr(), 1);
}
@@ -396,7 +398,7 @@
/// In effect this returns a table with exactly 1 bucket. However we can
/// leave the data pointer dangling since that bucket is never written to
/// due to our load factor forcing us to always have at least 1 free bucket.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub const fn new() -> Self {
Self {
table: RawTableInner::new_in(Global),
@@ -425,7 +427,7 @@
/// In effect this returns a table with exactly 1 bucket. However we can
/// leave the data pointer dangling since that bucket is never written to
/// due to our load factor forcing us to always have at least 1 free bucket.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub fn new_in(alloc: A) -> Self {
Self {
table: RawTableInner::new_in(alloc),
@@ -490,39 +492,33 @@
}
}
- /// Returns a reference to the underlying allocator.
- #[inline]
- pub fn allocator(&self) -> &A {
- &self.table.alloc
- }
-
/// Deallocates the table without dropping any entries.
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn free_buckets(&mut self) {
- self.table.free_buckets(TableLayout::new::<T>());
+ self.table.free_buckets(TableLayout::new::<T>())
}
/// Returns pointer to one past last element of data table.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn data_end(&self) -> NonNull<T> {
NonNull::new_unchecked(self.table.ctrl.as_ptr().cast())
}
/// Returns pointer to start of data table.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
#[cfg(feature = "nightly")]
pub unsafe fn data_start(&self) -> *mut T {
self.data_end().as_ptr().wrapping_sub(self.buckets())
}
/// Returns the index of a bucket from a `Bucket`.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn bucket_index(&self, bucket: &Bucket<T>) -> usize {
bucket.to_base_index(self.data_end())
}
/// Returns a pointer to an element in the table.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn bucket(&self, index: usize) -> Bucket<T> {
debug_assert_ne!(self.table.bucket_mask, 0);
debug_assert!(index < self.buckets());
@@ -534,7 +530,7 @@
#[deprecated(since = "0.8.1", note = "use erase or remove instead")]
pub unsafe fn erase_no_drop(&mut self, item: &Bucket<T>) {
let index = self.bucket_index(item);
- self.table.erase(index);
+ self.table.erase(index)
}
/// Erases an element from the table, dropping it in place.
@@ -554,9 +550,7 @@
pub fn erase_entry(&mut self, hash: u64, eq: impl FnMut(&T) -> bool) -> bool {
// Avoid `Option::map` because it bloats LLVM IR.
if let Some(bucket) = self.find(hash, eq) {
- unsafe {
- self.erase(bucket);
- }
+ unsafe { self.erase(bucket) };
true
} else {
false
@@ -585,7 +579,7 @@
/// Marks all table buckets as empty without dropping their contents.
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear_no_drop(&mut self) {
- self.table.clear_no_drop();
+ self.table.clear_no_drop()
}
/// Removes all elements from the table without freeing the backing memory.
@@ -599,7 +593,7 @@
}
unsafe fn drop_elements(&mut self) {
- if mem::needs_drop::<T>() && !self.is_empty() {
+ if mem::needs_drop::<T>() && self.len() != 0 {
for item in self.iter() {
item.drop();
}
@@ -630,7 +624,7 @@
if min_buckets < self.buckets() {
// Fast path if the table is empty
if self.table.items == 0 {
- *self = Self::with_capacity_in(min_size, self.table.alloc.clone());
+ *self = Self::with_capacity_in(min_size, self.table.alloc.clone())
} else {
// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
if self
@@ -682,21 +676,105 @@
hasher: impl Fn(&T) -> u64,
fallibility: Fallibility,
) -> Result<(), TryReserveError> {
- unsafe {
- self.table.reserve_rehash_inner(
- additional,
- &|table, index| hasher(table.bucket::<T>(index).as_ref()),
+ // Avoid `Option::ok_or_else` because it bloats LLVM IR.
+ let new_items = match self.table.items.checked_add(additional) {
+ Some(new_items) => new_items,
+ None => return Err(fallibility.capacity_overflow()),
+ };
+ let full_capacity = bucket_mask_to_capacity(self.table.bucket_mask);
+ if new_items <= full_capacity / 2 {
+ // Rehash in-place without re-allocating if we have plenty of spare
+ // capacity that is locked up due to DELETED entries.
+ self.rehash_in_place(hasher);
+ Ok(())
+ } else {
+ // Otherwise, conservatively resize to at least the next size up
+ // to avoid churning deletes into frequent rehashes.
+ self.resize(
+ usize::max(new_items, full_capacity + 1),
+ hasher,
fallibility,
- TableLayout::new::<T>(),
- if mem::needs_drop::<T>() {
- Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T)))
- } else {
- None
- },
)
}
}
+ /// Rehashes the contents of the table in place (i.e. without changing the
+ /// allocation).
+ ///
+ /// If `hasher` panics then some the table's contents may be lost.
+ fn rehash_in_place(&mut self, hasher: impl Fn(&T) -> u64) {
+ unsafe {
+ // If the hash function panics then properly clean up any elements
+ // that we haven't rehashed yet. We unfortunately can't preserve the
+ // element since we lost their hash and have no way of recovering it
+ // without risking another panic.
+ self.table.prepare_rehash_in_place();
+
+ let mut guard = guard(&mut self.table, move |self_| {
+ if mem::needs_drop::<T>() {
+ for i in 0..self_.buckets() {
+ if *self_.ctrl(i) == DELETED {
+ self_.set_ctrl(i, EMPTY);
+ self_.bucket::<T>(i).drop();
+ self_.items -= 1;
+ }
+ }
+ }
+ self_.growth_left = bucket_mask_to_capacity(self_.bucket_mask) - self_.items;
+ });
+
+ // At this point, DELETED elements are elements that we haven't
+ // rehashed yet. Find them and re-insert them at their ideal
+ // position.
+ 'outer: for i in 0..guard.buckets() {
+ if *guard.ctrl(i) != DELETED {
+ continue;
+ }
+
+ 'inner: loop {
+ // Hash the current item
+ let item = guard.bucket(i);
+ let hash = hasher(item.as_ref());
+
+ // Search for a suitable place to put it
+ let new_i = guard.find_insert_slot(hash);
+
+ // Probing works by scanning through all of the control
+ // bytes in groups, which may not be aligned to the group
+ // size. If both the new and old position fall within the
+ // same unaligned group, then there is no benefit in moving
+ // it and we can just continue to the next item.
+ if likely(guard.is_in_same_group(i, new_i, hash)) {
+ guard.set_ctrl_h2(i, hash);
+ continue 'outer;
+ }
+
+ // We are moving the current item to a new position. Write
+ // our H2 to the control byte of the new position.
+ let prev_ctrl = guard.replace_ctrl_h2(new_i, hash);
+ if prev_ctrl == EMPTY {
+ guard.set_ctrl(i, EMPTY);
+ // If the target slot is empty, simply move the current
+ // element into the new slot and clear the old control
+ // byte.
+ guard.bucket(new_i).copy_from_nonoverlapping(&item);
+ continue 'outer;
+ } else {
+ // If the target slot is occupied, swap the two elements
+ // and then continue processing the element that we just
+ // swapped into the old slot.
+ debug_assert_eq!(prev_ctrl, DELETED);
+ mem::swap(guard.bucket(new_i).as_mut(), item.as_mut());
+ continue 'inner;
+ }
+ }
+ }
+
+ guard.growth_left = bucket_mask_to_capacity(guard.bucket_mask) - guard.items;
+ mem::forget(guard);
+ }
+ }
+
/// Allocates a new table of a different size and moves the contents of the
/// current table into it.
fn resize(
@@ -706,12 +784,30 @@
fallibility: Fallibility,
) -> Result<(), TryReserveError> {
unsafe {
- self.table.resize_inner(
- capacity,
- &|table, index| hasher(table.bucket::<T>(index).as_ref()),
- fallibility,
- TableLayout::new::<T>(),
- )
+ let mut new_table =
+ self.table
+ .prepare_resize(TableLayout::new::<T>(), capacity, fallibility)?;
+
+ // Copy all elements to the new table.
+ for item in self.iter() {
+ // This may panic.
+ let hash = hasher(item.as_ref());
+
+ // We can use a simpler version of insert() here since:
+ // - there are no DELETED entries.
+ // - we know there is enough space in the table.
+ // - all elements are unique.
+ let (index, _) = new_table.prepare_insert_slot(hash);
+ new_table.bucket(index).copy_from_nonoverlapping(&item);
+ }
+
+ // We successfully copied all elements without panicking. Now replace
+ // self with the new table. The old table will have its memory freed but
+ // the items will not be dropped (since they have been moved into the
+ // new table).
+ mem::swap(&mut self.table, &mut new_table);
+
+ Ok(())
}
}
@@ -776,17 +872,19 @@
/// This does not check if the given element already exists in the table.
#[cfg_attr(feature = "inline-more", inline)]
#[cfg(any(feature = "raw", feature = "rustc-internal-api"))]
- pub unsafe fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> {
- let (index, old_ctrl) = self.table.prepare_insert_slot(hash);
- let bucket = self.table.bucket(index);
+ pub fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> {
+ unsafe {
+ let (index, old_ctrl) = self.table.prepare_insert_slot(hash);
+ let bucket = self.table.bucket(index);
- // If we are replacing a DELETED entry then we don't need to update
- // the load counter.
- self.table.growth_left -= special_is_empty(old_ctrl) as usize;
+ // If we are replacing a DELETED entry then we don't need to update
+ // the load counter.
+ self.table.growth_left -= special_is_empty(old_ctrl) as usize;
- bucket.write(value);
- self.table.items += 1;
- bucket
+ bucket.write(value);
+ self.table.items += 1;
+ bucket
+ }
}
/// Temporary removes a bucket, applying the given function to the removed
@@ -819,14 +917,14 @@
/// Searches for an element in the table.
#[inline]
pub fn find(&self, hash: u64, mut eq: impl FnMut(&T) -> bool) -> Option<Bucket<T>> {
- let result = self.table.find_inner(hash, &mut |index| unsafe {
- eq(self.bucket(index).as_ref())
- });
-
- // Avoid `Option::map` because it bloats LLVM IR.
- match result {
- Some(index) => Some(unsafe { self.bucket(index) }),
- None => None,
+ unsafe {
+ for bucket in self.iter_hash(hash) {
+ let elm = bucket.as_ref();
+ if likely(eq(elm)) {
+ return Some(bucket);
+ }
+ }
+ None
}
}
@@ -852,84 +950,79 @@
/// Attempts to get mutable references to `N` entries in the table at once.
///
- /// Returns an array of length `N` with the results of each query.
- ///
- /// At most one mutable reference will be returned to any entry. `None` will be returned if any
- /// of the hashes are duplicates. `None` will be returned if the hash is not found.
+ /// Returns an array of length `N` with the results of each query. For soundness,
+ /// at most one mutable reference will be returned to any entry. An
+ /// `Err(UnavailableMutError::Duplicate(i))` in the returned array indicates that a suitable
+ /// entry exists, but a mutable reference to it already occurs at index `i` in the returned
+ /// array.
///
/// The `eq` argument should be a closure such that `eq(i, k)` returns true if `k` is equal to
/// the `i`th key to be looked up.
- pub fn get_many_mut<const N: usize>(
- &mut self,
- hashes: [u64; N],
- eq: impl FnMut(usize, &T) -> bool,
- ) -> Option<[&'_ mut T; N]> {
- unsafe {
- let ptrs = self.get_many_mut_pointers(hashes, eq)?;
-
- for (i, &cur) in ptrs.iter().enumerate() {
- if ptrs[..i].iter().any(|&prev| ptr::eq::<T>(prev, cur)) {
- return None;
- }
- }
- // All bucket are distinct from all previous buckets so we're clear to return the result
- // of the lookup.
-
- // TODO use `MaybeUninit::array_assume_init` here instead once that's stable.
- Some(mem::transmute_copy(&ptrs))
- }
- }
-
- pub unsafe fn get_many_unchecked_mut<const N: usize>(
- &mut self,
- hashes: [u64; N],
- eq: impl FnMut(usize, &T) -> bool,
- ) -> Option<[&'_ mut T; N]> {
- let ptrs = self.get_many_mut_pointers(hashes, eq)?;
- Some(mem::transmute_copy(&ptrs))
- }
-
- unsafe fn get_many_mut_pointers<const N: usize>(
+ ///
+ /// This method is available only if the `nightly` feature is enabled.
+ #[cfg(feature = "nightly")]
+ pub fn get_each_mut<const N: usize>(
&mut self,
hashes: [u64; N],
mut eq: impl FnMut(usize, &T) -> bool,
- ) -> Option<[*mut T; N]> {
+ ) -> [Result<&'_ mut T, UnavailableMutError>; N] {
+ // Collect the requested buckets.
// TODO use `MaybeUninit::uninit_array` here instead once that's stable.
- let mut outs: MaybeUninit<[*mut T; N]> = MaybeUninit::uninit();
- let outs_ptr = outs.as_mut_ptr();
+ let mut buckets: [MaybeUninit<Option<Bucket<T>>>; N] =
+ unsafe { MaybeUninit::uninit().assume_init() };
+ for i in 0..N {
+ buckets[i] = MaybeUninit::new(self.find(hashes[i], |k| eq(i, k)));
+ }
+ let buckets: [Option<Bucket<T>>; N] = unsafe { MaybeUninit::array_assume_init(buckets) };
- for (i, &hash) in hashes.iter().enumerate() {
- let cur = self.find(hash, |k| eq(i, k))?;
- *(*outs_ptr).get_unchecked_mut(i) = cur.as_mut();
+ // Walk through the buckets, checking for duplicates and building up the output array.
+ // TODO use `MaybeUninit::uninit_array` here instead once that's stable.
+ let mut out: [MaybeUninit<Result<&'_ mut T, UnavailableMutError>>; N] =
+ unsafe { MaybeUninit::uninit().assume_init() };
+ for i in 0..N {
+ out[i] = MaybeUninit::new(
+ #[allow(clippy::never_loop)]
+ 'outer: loop {
+ for j in 0..i {
+ match (&buckets[j], &buckets[i]) {
+ // These two buckets are the same, and we can't safely return a second
+ // mutable reference to the same entry.
+ (Some(prev), Some(cur)) if prev.as_ptr() == cur.as_ptr() => {
+ break 'outer Err(UnavailableMutError::Duplicate(j));
+ }
+ _ => {}
+ }
+ }
+ // This bucket is distinct from all previous buckets (or it doesn't exist), so
+ // we're clear to return the result of the lookup.
+ break match &buckets[i] {
+ None => Err(UnavailableMutError::Absent),
+ Some(bkt) => unsafe { Ok(bkt.as_mut()) },
+ };
+ },
+ )
}
- // TODO use `MaybeUninit::array_assume_init` here instead once that's stable.
- Some(outs.assume_init())
+ unsafe { MaybeUninit::array_assume_init(out) }
}
/// Returns the number of elements the map can hold without reallocating.
///
/// This number is a lower bound; the table might be able to hold
/// more, but is guaranteed to be able to hold at least this many.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub fn capacity(&self) -> usize {
self.table.items + self.table.growth_left
}
/// Returns the number of elements in the table.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub fn len(&self) -> usize {
self.table.items
}
- /// Returns `true` if the table contains no elements.
- #[inline]
- pub fn is_empty(&self) -> bool {
- self.len() == 0
- }
-
/// Returns the number of buckets in the table.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub fn buckets(&self) -> usize {
self.table.bucket_mask + 1
}
@@ -938,7 +1031,7 @@
/// the caller to ensure that the `RawTable` outlives the `RawIter`.
/// Because we cannot make the `next` method unsafe on the `RawIter`
/// struct, we have to make the `iter` method unsafe.
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn iter(&self) -> RawIter<T> {
let data = Bucket::from_base_index(self.data_end(), 0);
RawIter {
@@ -949,15 +1042,12 @@
/// Returns an iterator over occupied buckets that could match a given hash.
///
- /// `RawTable` only stores 7 bits of the hash value, so this iterator may
- /// return items that have a hash value different than the one provided. You
- /// should always validate the returned values before using them.
+ /// In rare cases, the iterator may return a bucket with a different hash.
///
/// It is up to the caller to ensure that the `RawTable` outlives the
/// `RawIterHash`. Because we cannot make the `next` method unsafe on the
/// `RawIterHash` struct, we have to make the `iter_hash` method unsafe.
#[cfg_attr(feature = "inline-more", inline)]
- #[cfg(feature = "raw")]
pub unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<'_, T, A> {
RawIterHash::new(self, hash)
}
@@ -1031,21 +1121,11 @@
}
}
-unsafe impl<T, A: Allocator + Clone> Send for RawTable<T, A>
-where
- T: Send,
- A: Send,
-{
-}
-unsafe impl<T, A: Allocator + Clone> Sync for RawTable<T, A>
-where
- T: Sync,
- A: Sync,
-{
-}
+unsafe impl<T, A: Allocator + Clone> Send for RawTable<T, A> where T: Send {}
+unsafe impl<T, A: Allocator + Clone> Sync for RawTable<T, A> where T: Sync {}
impl<A> RawTableInner<A> {
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
const fn new_in(alloc: A) -> Self {
Self {
// Be careful to cast the entire slice to a raw pointer.
@@ -1074,15 +1154,6 @@
None => return Err(fallibility.capacity_overflow()),
};
- // We need an additional check to ensure that the allocation doesn't
- // exceed `isize::MAX`. We can skip this check on 64-bit systems since
- // such allocations will never succeed anyways.
- //
- // This mirrors what Vec does in the standard library.
- if mem::size_of::<usize>() < 8 && layout.size() > isize::MAX as usize {
- return Err(fallibility.capacity_overflow());
- }
-
let ptr: NonNull<u8> = match do_alloc(&alloc, layout) {
Ok(block) => block.cast(),
Err(_) => return Err(fallibility.alloc_err(layout)),
@@ -1150,7 +1221,7 @@
// EMPTY entries. These will unfortunately trigger a
// match, but once masked may point to a full bucket that
// is already occupied. We detect this situation here and
- // perform a second scan starting at the beginning of the
+ // perform a second scan starting at the begining of the
// table. This second scan is guaranteed to find an empty
// slot (due to the load factor) before hitting the trailing
// control bytes (containing EMPTY).
@@ -1169,32 +1240,6 @@
}
}
- /// Searches for an element in the table. This uses dynamic dispatch to reduce the amount of
- /// code generated, but it is eliminated by LLVM optimizations.
- #[inline]
- fn find_inner(&self, hash: u64, eq: &mut dyn FnMut(usize) -> bool) -> Option<usize> {
- let h2_hash = h2(hash);
- let mut probe_seq = self.probe_seq(hash);
-
- loop {
- let group = unsafe { Group::load(self.ctrl(probe_seq.pos)) };
-
- for bit in group.match_byte(h2_hash) {
- let index = (probe_seq.pos + bit) & self.bucket_mask;
-
- if likely(eq(index)) {
- return Some(index);
- }
- }
-
- if likely(group.match_empty().any_bit_set()) {
- return None;
- }
-
- probe_seq.move_next(self.bucket_mask);
- }
- }
-
#[allow(clippy::mut_mut)]
#[inline]
unsafe fn prepare_rehash_in_place(&mut self) {
@@ -1218,22 +1263,14 @@
}
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
unsafe fn bucket<T>(&self, index: usize) -> Bucket<T> {
debug_assert_ne!(self.bucket_mask, 0);
debug_assert!(index < self.buckets());
Bucket::from_base_index(self.data_end(), index)
}
- #[inline]
- unsafe fn bucket_ptr(&self, index: usize, size_of: usize) -> *mut u8 {
- debug_assert_ne!(self.bucket_mask, 0);
- debug_assert!(index < self.buckets());
- let base: *mut u8 = self.data_end().as_ptr();
- base.sub((index + 1) * size_of)
- }
-
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
unsafe fn data_end<T>(&self) -> NonNull<T> {
NonNull::new_unchecked(self.ctrl.as_ptr().cast())
}
@@ -1285,7 +1322,7 @@
/// the end of the array.
#[inline]
unsafe fn set_ctrl_h2(&self, index: usize, hash: u64) {
- self.set_ctrl(index, h2(hash));
+ self.set_ctrl(index, h2(hash))
}
#[inline]
@@ -1378,179 +1415,6 @@
}))
}
- /// Reserves or rehashes to make room for `additional` more elements.
- ///
- /// This uses dynamic dispatch to reduce the amount of
- /// code generated, but it is eliminated by LLVM optimizations when inlined.
- #[allow(clippy::inline_always)]
- #[inline(always)]
- unsafe fn reserve_rehash_inner(
- &mut self,
- additional: usize,
- hasher: &dyn Fn(&mut Self, usize) -> u64,
- fallibility: Fallibility,
- layout: TableLayout,
- drop: Option<fn(*mut u8)>,
- ) -> Result<(), TryReserveError> {
- // Avoid `Option::ok_or_else` because it bloats LLVM IR.
- let new_items = match self.items.checked_add(additional) {
- Some(new_items) => new_items,
- None => return Err(fallibility.capacity_overflow()),
- };
- let full_capacity = bucket_mask_to_capacity(self.bucket_mask);
- if new_items <= full_capacity / 2 {
- // Rehash in-place without re-allocating if we have plenty of spare
- // capacity that is locked up due to DELETED entries.
- self.rehash_in_place(hasher, layout.size, drop);
- Ok(())
- } else {
- // Otherwise, conservatively resize to at least the next size up
- // to avoid churning deletes into frequent rehashes.
- self.resize_inner(
- usize::max(new_items, full_capacity + 1),
- hasher,
- fallibility,
- layout,
- )
- }
- }
-
- /// Allocates a new table of a different size and moves the contents of the
- /// current table into it.
- ///
- /// This uses dynamic dispatch to reduce the amount of
- /// code generated, but it is eliminated by LLVM optimizations when inlined.
- #[allow(clippy::inline_always)]
- #[inline(always)]
- unsafe fn resize_inner(
- &mut self,
- capacity: usize,
- hasher: &dyn Fn(&mut Self, usize) -> u64,
- fallibility: Fallibility,
- layout: TableLayout,
- ) -> Result<(), TryReserveError> {
- let mut new_table = self.prepare_resize(layout, capacity, fallibility)?;
-
- // Copy all elements to the new table.
- for i in 0..self.buckets() {
- if !is_full(*self.ctrl(i)) {
- continue;
- }
-
- // This may panic.
- let hash = hasher(self, i);
-
- // We can use a simpler version of insert() here since:
- // - there are no DELETED entries.
- // - we know there is enough space in the table.
- // - all elements are unique.
- let (index, _) = new_table.prepare_insert_slot(hash);
-
- ptr::copy_nonoverlapping(
- self.bucket_ptr(i, layout.size),
- new_table.bucket_ptr(index, layout.size),
- layout.size,
- );
- }
-
- // We successfully copied all elements without panicking. Now replace
- // self with the new table. The old table will have its memory freed but
- // the items will not be dropped (since they have been moved into the
- // new table).
- mem::swap(self, &mut new_table);
-
- Ok(())
- }
-
- /// Rehashes the contents of the table in place (i.e. without changing the
- /// allocation).
- ///
- /// If `hasher` panics then some the table's contents may be lost.
- ///
- /// This uses dynamic dispatch to reduce the amount of
- /// code generated, but it is eliminated by LLVM optimizations when inlined.
- #[allow(clippy::inline_always)]
- #[cfg_attr(feature = "inline-more", inline(always))]
- #[cfg_attr(not(feature = "inline-more"), inline)]
- unsafe fn rehash_in_place(
- &mut self,
- hasher: &dyn Fn(&mut Self, usize) -> u64,
- size_of: usize,
- drop: Option<fn(*mut u8)>,
- ) {
- // If the hash function panics then properly clean up any elements
- // that we haven't rehashed yet. We unfortunately can't preserve the
- // element since we lost their hash and have no way of recovering it
- // without risking another panic.
- self.prepare_rehash_in_place();
-
- let mut guard = guard(self, move |self_| {
- if let Some(drop) = drop {
- for i in 0..self_.buckets() {
- if *self_.ctrl(i) == DELETED {
- self_.set_ctrl(i, EMPTY);
- drop(self_.bucket_ptr(i, size_of));
- self_.items -= 1;
- }
- }
- }
- self_.growth_left = bucket_mask_to_capacity(self_.bucket_mask) - self_.items;
- });
-
- // At this point, DELETED elements are elements that we haven't
- // rehashed yet. Find them and re-insert them at their ideal
- // position.
- 'outer: for i in 0..guard.buckets() {
- if *guard.ctrl(i) != DELETED {
- continue;
- }
-
- let i_p = guard.bucket_ptr(i, size_of);
-
- 'inner: loop {
- // Hash the current item
- let hash = hasher(*guard, i);
-
- // Search for a suitable place to put it
- let new_i = guard.find_insert_slot(hash);
- let new_i_p = guard.bucket_ptr(new_i, size_of);
-
- // Probing works by scanning through all of the control
- // bytes in groups, which may not be aligned to the group
- // size. If both the new and old position fall within the
- // same unaligned group, then there is no benefit in moving
- // it and we can just continue to the next item.
- if likely(guard.is_in_same_group(i, new_i, hash)) {
- guard.set_ctrl_h2(i, hash);
- continue 'outer;
- }
-
- // We are moving the current item to a new position. Write
- // our H2 to the control byte of the new position.
- let prev_ctrl = guard.replace_ctrl_h2(new_i, hash);
- if prev_ctrl == EMPTY {
- guard.set_ctrl(i, EMPTY);
- // If the target slot is empty, simply move the current
- // element into the new slot and clear the old control
- // byte.
- ptr::copy_nonoverlapping(i_p, new_i_p, size_of);
- continue 'outer;
- } else {
- // If the target slot is occupied, swap the two elements
- // and then continue processing the element that we just
- // swapped into the old slot.
- debug_assert_eq!(prev_ctrl, DELETED);
- ptr::swap_nonoverlapping(i_p, new_i_p, size_of);
- continue 'inner;
- }
- }
- }
-
- guard.growth_left = bucket_mask_to_capacity(guard.bucket_mask) - guard.items;
-
- mem::forget(guard);
- }
-
#[inline]
unsafe fn free_buckets(&mut self, table_layout: TableLayout) {
// Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
@@ -1590,7 +1454,7 @@
//
// Note that in this context `leading_zeros` refers to the bytes at the
// end of a group, while `trailing_zeros` refers to the bytes at the
- // beginning of a group.
+ // begining of a group.
let ctrl = if empty_before.leading_zeros() + empty_after.trailing_zeros() >= Group::WIDTH {
DELETED
} else {
@@ -1660,7 +1524,7 @@
self.clone_from_spec(source, |self_| {
// We need to leave the table in an empty state.
- self_.clear_no_drop();
+ self_.clear_no_drop()
});
}
}
@@ -1672,8 +1536,8 @@
unsafe fn clone_from_spec(&mut self, source: &Self, on_panic: impl FnMut(&mut Self));
}
impl<T: Clone, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
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);
}
@@ -1710,7 +1574,7 @@
// to make sure we drop only the elements that have been
// cloned so far.
let mut guard = guard((0, &mut *self), |(index, self_)| {
- if mem::needs_drop::<T>() && !self_.is_empty() {
+ if mem::needs_drop::<T>() && self_.len() != 0 {
for i in 0..=*index {
if is_full(*self_.table.ctrl(i)) {
self_.bucket(i).drop();
@@ -1786,7 +1650,7 @@
}
impl<T, A: Allocator + Clone + Default> Default for RawTable<T, A> {
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
fn default() -> Self {
Self::new_in(Default::default())
}
@@ -1960,7 +1824,7 @@
}
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
// We don't have an item count, so just guess based on the range size.
(
@@ -2007,7 +1871,7 @@
/// For the iterator to remain valid, this method must be called once
/// for each insert before `next` is called again.
///
- /// This method does not guarantee that an insertion of a bucket with a greater
+ /// This method does not guarantee that an insertion of a bucket witha greater
/// index than the last one yielded will be reflected in the iterator.
///
/// This method should be called _after_ the given insert is made.
@@ -2059,7 +1923,7 @@
// If it did, we're done.
// - Otherwise, update the iterator cached group so that it won't
// yield a to-be-removed bucket, or _will_ yield a to-be-added bucket.
- // We'll also need to update the item count accordingly.
+ // We'll also need ot update the item count accordingly.
if let Some(index) = self.iter.current_group.lowest_set_bit() {
let next_bucket = self.iter.data.next_n(index);
if b.as_ptr() > next_bucket.as_ptr() {
@@ -2142,7 +2006,7 @@
}
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
(self.items, Some(self.items))
}
@@ -2166,18 +2030,8 @@
}
}
-unsafe impl<T, A: Allocator + Clone> Send for RawIntoIter<T, A>
-where
- T: Send,
- A: Send,
-{
-}
-unsafe impl<T, A: Allocator + Clone> Sync for RawIntoIter<T, A>
-where
- T: Sync,
- A: Sync,
-{
-}
+unsafe impl<T, A: Allocator + Clone> Send for RawIntoIter<T, A> where T: Send {}
+unsafe impl<T, A: Allocator + Clone> Sync for RawIntoIter<T, A> where T: Sync {}
#[cfg(feature = "nightly")]
unsafe impl<#[may_dangle] T, A: Allocator + Clone> Drop for RawIntoIter<T, A> {
@@ -2218,7 +2072,7 @@
unsafe { Some(self.iter.next()?.read()) }
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
@@ -2249,18 +2103,8 @@
}
}
-unsafe impl<T, A: Allocator + Copy> Send for RawDrain<'_, T, A>
-where
- T: Send,
- A: Send,
-{
-}
-unsafe impl<T, A: Allocator + Copy> Sync for RawDrain<'_, T, A>
-where
- T: Sync,
- A: Sync,
-{
-}
+unsafe impl<T, A: Allocator + Copy> Send for RawDrain<'_, T, A> where T: Send {}
+unsafe impl<T, A: Allocator + Copy> Sync for RawDrain<'_, T, A> where T: Sync {}
impl<T, A: Allocator + Clone> Drop for RawDrain<'_, T, A> {
#[cfg_attr(feature = "inline-more", inline)]
@@ -2292,7 +2136,7 @@
}
}
- #[inline]
+ #[cfg_attr(feature = "inline-more", inline)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
@@ -2303,9 +2147,7 @@
/// Iterator over occupied buckets that could match a given hash.
///
-/// `RawTable` only stores 7 bits of the hash value, so this iterator may return
-/// items that have a hash value different than the one provided. You should
-/// always validate the returned values before using them.
+/// In rare cases, the iterator may return a bucket with a different hash.
pub struct RawIterHash<'a, T, A: Allocator + Clone = Global> {
inner: RawIterHashInner<'a, A>,
_marker: PhantomData<T>,
@@ -2328,7 +2170,6 @@
impl<'a, T, A: Allocator + Clone> RawIterHash<'a, T, A> {
#[cfg_attr(feature = "inline-more", inline)]
- #[cfg(feature = "raw")]
fn new(table: &'a RawTable<T, A>, hash: u64) -> Self {
RawIterHash {
inner: RawIterHashInner::new(&table.table, hash),
@@ -2338,7 +2179,6 @@
}
impl<'a, A: Allocator + Clone> RawIterHashInner<'a, A> {
#[cfg_attr(feature = "inline-more", inline)]
- #[cfg(feature = "raw")]
fn new(table: &'a RawTableInner<A>, hash: u64) -> Self {
unsafe {
let h2_hash = h2(hash);
@@ -2395,20 +2235,6 @@
mod test_map {
use super::*;
- fn rehash_in_place<T>(table: &mut RawTable<T>, hasher: impl Fn(&T) -> u64) {
- unsafe {
- table.table.rehash_in_place(
- &|table, index| hasher(table.bucket::<T>(index).as_ref()),
- mem::size_of::<T>(),
- if mem::needs_drop::<T>() {
- Some(mem::transmute(ptr::drop_in_place::<T> as unsafe fn(*mut T)))
- } else {
- None
- },
- );
- }
- }
-
#[test]
fn rehash() {
let mut table = RawTable::new();
@@ -2424,7 +2250,7 @@
assert!(table.find(i + 100, |x| *x == i + 100).is_none());
}
- rehash_in_place(&mut table, hasher);
+ table.rehash_in_place(hasher);
for i in 0..100 {
unsafe {
diff --git a/src/raw/sse2.rs b/src/raw/sse2.rs
index a0bf6da..eed9684 100644
--- a/src/raw/sse2.rs
+++ b/src/raw/sse2.rs
@@ -28,7 +28,6 @@
/// value for an empty hash table.
///
/// This is guaranteed to be aligned to the group size.
- #[inline]
#[allow(clippy::items_after_statements)]
pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
#[repr(C)]
diff --git a/src/rustc_entry.rs b/src/rustc_entry.rs
index 465db47..1793c4a 100644
--- a/src/rustc_entry.rs
+++ b/src/rustc_entry.rs
@@ -574,10 +574,8 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert(self, value: V) -> &'a mut V {
- unsafe {
- let bucket = self.table.insert_no_grow(self.hash, (self.key, value));
- &mut bucket.as_mut().1
- }
+ let bucket = self.table.insert_no_grow(self.hash, (self.key, value));
+ unsafe { &mut bucket.as_mut().1 }
}
/// Sets the value of the entry with the RustcVacantEntry's key,
@@ -598,7 +596,7 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert_entry(self, value: V) -> RustcOccupiedEntry<'a, K, V, A> {
- let bucket = unsafe { self.table.insert_no_grow(self.hash, (self.key, value)) };
+ let bucket = self.table.insert_no_grow(self.hash, (self.key, value));
RustcOccupiedEntry {
key: None,
elem: bucket,
diff --git a/src/scopeguard.rs b/src/scopeguard.rs
index ccdc0c5..4e9bf04 100644
--- a/src/scopeguard.rs
+++ b/src/scopeguard.rs
@@ -44,6 +44,6 @@
{
#[inline]
fn drop(&mut self) {
- (self.dropfn)(&mut self.value);
+ (self.dropfn)(&mut self.value)
}
}
diff --git a/src/set.rs b/src/set.rs
index bb83054..d59183b 100644
--- a/src/set.rs
+++ b/src/set.rs
@@ -378,7 +378,7 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear(&mut self) {
- self.map.clear();
+ self.map.clear()
}
}
@@ -454,12 +454,6 @@
where
A: Allocator + Clone,
{
- /// Returns a reference to the underlying allocator.
- #[inline]
- pub fn allocator(&self) -> &A {
- self.map.allocator()
- }
-
/// Creates a new empty hash set which will use the given hasher to hash
/// keys.
///
@@ -559,7 +553,7 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn reserve(&mut self, additional: usize) {
- self.map.reserve(additional);
+ self.map.reserve(additional)
}
/// Tries to reserve capacity for at least `additional` more elements to be inserted
@@ -601,7 +595,7 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn shrink_to_fit(&mut self) {
- self.map.shrink_to_fit();
+ self.map.shrink_to_fit()
}
/// Shrinks the capacity of the set with a lower limit. It will drop
@@ -627,7 +621,7 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn shrink_to(&mut self, min_capacity: usize) {
- self.map.shrink_to(min_capacity);
+ self.map.shrink_to(min_capacity)
}
/// Visits the values representing the difference,
@@ -991,30 +985,6 @@
self.map.insert(value, ()).is_none()
}
- /// Insert a value the set without checking if the value already exists in the set.
- ///
- /// Returns a reference to the value just inserted.
- ///
- /// This operation is safe if a value does not exist in the set.
- ///
- /// However, if a value exists in the set already, the behavior is unspecified:
- /// this operation may panic, loop forever, or any following operation with the set
- /// may panic, loop forever or return arbitrary result.
- ///
- /// That said, this operation (and following operations) are guaranteed to
- /// not violate memory safety.
- ///
- /// This operation is faster than regular insert, because it does not perform
- /// lookup before insertion.
- ///
- /// This operation is useful during initial population of the set.
- /// For example, when constructing a set from another set, we know
- /// that values are unique.
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn insert_unique_unchecked(&mut self, value: T) -> &T {
- self.map.insert_unique_unchecked(value, ()).0
- }
-
/// Adds a value to the set, replacing the existing value, if any, that is equal to the given
/// one. Returns the replaced value.
///
@@ -1128,7 +1098,8 @@
impl<T, S, A> fmt::Debug for HashSet<T, S, A>
where
- T: fmt::Debug,
+ T: Eq + Hash + fmt::Debug,
+ S: BuildHasher,
A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
@@ -1159,27 +1130,6 @@
}
}
-// The default hasher is used to match the std implementation signature
-#[cfg(feature = "ahash")]
-impl<T, A, const N: usize> From<[T; N]> for HashSet<T, DefaultHashBuilder, A>
-where
- T: Eq + Hash,
- A: Default + Allocator + Clone,
-{
- /// # Examples
- ///
- /// ```
- /// use hashbrown::HashSet;
- ///
- /// let set1 = HashSet::from([1, 2, 3, 4]);
- /// let set2: HashSet<_> = [1, 2, 3, 4].into();
- /// assert_eq!(set1, set2);
- /// ```
- fn from(arr: [T; N]) -> Self {
- arr.into_iter().collect()
- }
-}
-
impl<T, S, A> Extend<T> for HashSet<T, S, A>
where
T: Eq + Hash,
@@ -1212,7 +1162,7 @@
{
#[cfg_attr(feature = "inline-more", inline)]
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
- self.extend(iter.into_iter().copied());
+ self.extend(iter.into_iter().cloned());
}
#[inline]
@@ -2013,7 +1963,7 @@
let expected = [3, 5, 11, 77];
for x in a.intersection(&b) {
assert!(expected.contains(x));
- i += 1;
+ i += 1
}
assert_eq!(i, expected.len());
}
@@ -2036,7 +1986,7 @@
let expected = [1, 5, 11];
for x in a.difference(&b) {
assert!(expected.contains(x));
- i += 1;
+ i += 1
}
assert_eq!(i, expected.len());
}
@@ -2062,7 +2012,7 @@
let expected = [-2, 1, 5, 11, 14, 22];
for x in a.symmetric_difference(&b) {
assert!(expected.contains(x));
- i += 1;
+ i += 1
}
assert_eq!(i, expected.len());
}
@@ -2092,7 +2042,7 @@
let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
for x in a.union(&b) {
assert!(expected.contains(x));
- i += 1;
+ i += 1
}
assert_eq!(i, expected.len());
}
@@ -2118,7 +2068,7 @@
fn test_from_iter() {
let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
- let set: HashSet<_> = xs.iter().copied().collect();
+ let set: HashSet<_> = xs.iter().cloned().collect();
for x in &xs {
assert!(set.contains(x));
@@ -2280,7 +2230,7 @@
#[test]
fn test_retain() {
let xs = [1, 2, 3, 4, 5, 6];
- let mut set: HashSet<i32> = xs.iter().copied().collect();
+ let mut set: HashSet<i32> = xs.iter().cloned().collect();
set.retain(|&k| k % 2 == 0);
assert_eq!(set.len(), 3);
assert!(set.contains(&2));
@@ -2322,7 +2272,7 @@
const EMPTY_SET: HashSet<u32, MyHasher> = HashSet::with_hasher(MyHasher);
- let mut set = EMPTY_SET;
+ let mut set = EMPTY_SET.clone();
set.insert(19);
assert!(set.contains(&19));
}
diff --git a/tests/rayon.rs b/tests/rayon.rs
index 8c603c5..39b4770 100644
--- a/tests/rayon.rs
+++ b/tests/rayon.rs
@@ -269,20 +269,20 @@
let mut map_seq = MAP_EXISTING_EMPTY.clone();
let mut map_par = MAP_EXISTING_EMPTY.clone();
- map_seq.extend(MAP_EXTENSION_EMPTY.iter().copied());
- map_par.par_extend(MAP_EXTENSION_EMPTY.par_iter().copied());
+ map_seq.extend(MAP_EXTENSION_EMPTY.iter().cloned());
+ map_par.par_extend(MAP_EXTENSION_EMPTY.par_iter().cloned());
assert_eq3!(map_seq, map_par, expected);
}
#[test]
fn map_seq_par_equivalence_existing_empty_extend() {
- let expected = MAP_EXTENSION.iter().copied().collect::<HashMap<_, _>>();
+ let expected = MAP_EXTENSION.iter().cloned().collect::<HashMap<_, _>>();
let mut map_seq = MAP_EXISTING_EMPTY.clone();
let mut map_par = MAP_EXISTING_EMPTY.clone();
- map_seq.extend(MAP_EXTENSION.iter().copied());
- map_par.par_extend(MAP_EXTENSION.par_iter().copied());
+ map_seq.extend(MAP_EXTENSION.iter().cloned());
+ map_par.par_extend(MAP_EXTENSION.par_iter().cloned());
assert_eq3!(map_seq, map_par, expected);
}
@@ -293,8 +293,8 @@
let mut map_seq = MAP_EXISTING.clone();
let mut map_par = MAP_EXISTING.clone();
- map_seq.extend(MAP_EXTENSION_EMPTY.iter().copied());
- map_par.par_extend(MAP_EXTENSION_EMPTY.par_iter().copied());
+ map_seq.extend(MAP_EXTENSION_EMPTY.iter().cloned());
+ map_par.par_extend(MAP_EXTENSION_EMPTY.par_iter().cloned());
assert_eq3!(map_seq, map_par, expected);
}
@@ -305,8 +305,8 @@
let mut map_seq = MAP_EXISTING.clone();
let mut map_par = MAP_EXISTING.clone();
- map_seq.extend(MAP_EXTENSION.iter().copied());
- map_par.par_extend(MAP_EXTENSION.par_iter().copied());
+ map_seq.extend(MAP_EXTENSION.iter().cloned());
+ map_par.par_extend(MAP_EXTENSION.par_iter().cloned());
assert_eq3!(map_seq, map_par, expected);
}
@@ -423,20 +423,20 @@
let mut set_seq = SET_EXISTING_EMPTY.clone();
let mut set_par = SET_EXISTING_EMPTY.clone();
- set_seq.extend(SET_EXTENSION_EMPTY.iter().copied());
- set_par.par_extend(SET_EXTENSION_EMPTY.par_iter().copied());
+ set_seq.extend(SET_EXTENSION_EMPTY.iter().cloned());
+ set_par.par_extend(SET_EXTENSION_EMPTY.par_iter().cloned());
assert_eq3!(set_seq, set_par, expected);
}
#[test]
fn set_seq_par_equivalence_existing_empty_extend() {
- let expected = SET_EXTENSION.iter().copied().collect::<HashSet<_>>();
+ let expected = SET_EXTENSION.iter().cloned().collect::<HashSet<_>>();
let mut set_seq = SET_EXISTING_EMPTY.clone();
let mut set_par = SET_EXISTING_EMPTY.clone();
- set_seq.extend(SET_EXTENSION.iter().copied());
- set_par.par_extend(SET_EXTENSION.par_iter().copied());
+ set_seq.extend(SET_EXTENSION.iter().cloned());
+ set_par.par_extend(SET_EXTENSION.par_iter().cloned());
assert_eq3!(set_seq, set_par, expected);
}
@@ -447,8 +447,8 @@
let mut set_seq = SET_EXISTING.clone();
let mut set_par = SET_EXISTING.clone();
- set_seq.extend(SET_EXTENSION_EMPTY.iter().copied());
- set_par.par_extend(SET_EXTENSION_EMPTY.par_iter().copied());
+ set_seq.extend(SET_EXTENSION_EMPTY.iter().cloned());
+ set_par.par_extend(SET_EXTENSION_EMPTY.par_iter().cloned());
assert_eq3!(set_seq, set_par, expected);
}
@@ -459,37 +459,37 @@
let mut set_seq = SET_EXISTING.clone();
let mut set_par = SET_EXISTING.clone();
- set_seq.extend(SET_EXTENSION.iter().copied());
- set_par.par_extend(SET_EXTENSION.par_iter().copied());
+ set_seq.extend(SET_EXTENSION.iter().cloned());
+ set_par.par_extend(SET_EXTENSION.par_iter().cloned());
assert_eq3!(set_seq, set_par, expected);
}
lazy_static! {
- static ref SET_A: HashSet<char> = ['a', 'b', 'c', 'd'].iter().copied().collect();
- static ref SET_B: HashSet<char> = ['a', 'b', 'e', 'f'].iter().copied().collect();
- static ref SET_DIFF_AB: HashSet<char> = ['c', 'd'].iter().copied().collect();
- static ref SET_DIFF_BA: HashSet<char> = ['e', 'f'].iter().copied().collect();
- static ref SET_SYMM_DIFF_AB: HashSet<char> = ['c', 'd', 'e', 'f'].iter().copied().collect();
- static ref SET_INTERSECTION_AB: HashSet<char> = ['a', 'b'].iter().copied().collect();
+ static ref SET_A: HashSet<char> = ['a', 'b', 'c', 'd'].iter().cloned().collect();
+ static ref SET_B: HashSet<char> = ['a', 'b', 'e', 'f'].iter().cloned().collect();
+ static ref SET_DIFF_AB: HashSet<char> = ['c', 'd'].iter().cloned().collect();
+ static ref SET_DIFF_BA: HashSet<char> = ['e', 'f'].iter().cloned().collect();
+ static ref SET_SYMM_DIFF_AB: HashSet<char> = ['c', 'd', 'e', 'f'].iter().cloned().collect();
+ static ref SET_INTERSECTION_AB: HashSet<char> = ['a', 'b'].iter().cloned().collect();
static ref SET_UNION_AB: HashSet<char> =
- ['a', 'b', 'c', 'd', 'e', 'f'].iter().copied().collect();
+ ['a', 'b', 'c', 'd', 'e', 'f'].iter().cloned().collect();
}
#[test]
fn set_seq_par_equivalence_difference() {
- let diff_ab_seq = SET_A.difference(&*SET_B).copied().collect::<HashSet<_>>();
+ let diff_ab_seq = SET_A.difference(&*SET_B).cloned().collect::<HashSet<_>>();
let diff_ab_par = SET_A
.par_difference(&*SET_B)
- .copied()
+ .cloned()
.collect::<HashSet<_>>();
assert_eq3!(diff_ab_seq, diff_ab_par, *SET_DIFF_AB);
- let diff_ba_seq = SET_B.difference(&*SET_A).copied().collect::<HashSet<_>>();
+ let diff_ba_seq = SET_B.difference(&*SET_A).cloned().collect::<HashSet<_>>();
let diff_ba_par = SET_B
.par_difference(&*SET_A)
- .copied()
+ .cloned()
.collect::<HashSet<_>>();
assert_eq3!(diff_ba_seq, diff_ba_par, *SET_DIFF_BA);
@@ -499,11 +499,11 @@
fn set_seq_par_equivalence_symmetric_difference() {
let symm_diff_ab_seq = SET_A
.symmetric_difference(&*SET_B)
- .copied()
+ .cloned()
.collect::<HashSet<_>>();
let symm_diff_ab_par = SET_A
.par_symmetric_difference(&*SET_B)
- .copied()
+ .cloned()
.collect::<HashSet<_>>();
assert_eq3!(symm_diff_ab_seq, symm_diff_ab_par, *SET_SYMM_DIFF_AB);
@@ -511,10 +511,10 @@
#[test]
fn set_seq_par_equivalence_intersection() {
- let intersection_ab_seq = SET_A.intersection(&*SET_B).copied().collect::<HashSet<_>>();
+ let intersection_ab_seq = SET_A.intersection(&*SET_B).cloned().collect::<HashSet<_>>();
let intersection_ab_par = SET_A
.par_intersection(&*SET_B)
- .copied()
+ .cloned()
.collect::<HashSet<_>>();
assert_eq3!(
@@ -526,8 +526,8 @@
#[test]
fn set_seq_par_equivalence_union() {
- let union_ab_seq = SET_A.union(&*SET_B).copied().collect::<HashSet<_>>();
- let union_ab_par = SET_A.par_union(&*SET_B).copied().collect::<HashSet<_>>();
+ let union_ab_seq = SET_A.union(&*SET_B).cloned().collect::<HashSet<_>>();
+ let union_ab_par = SET_A.par_union(&*SET_B).cloned().collect::<HashSet<_>>();
assert_eq3!(union_ab_seq, union_ab_par, *SET_UNION_AB);
}
diff --git a/tests/set.rs b/tests/set.rs
index 5ae1ec9..3fc0717 100644
--- a/tests/set.rs
+++ b/tests/set.rs
@@ -2,33 +2,29 @@
use hashbrown::HashSet;
use rand::{distributions::Alphanumeric, rngs::SmallRng, Rng, SeedableRng};
-use std::iter;
#[test]
fn test_hashset_insert_remove() {
let mut m: HashSet<Vec<char>> = HashSet::new();
- let seed = u64::from_le_bytes(*b"testseed");
+ //let num: u32 = 4096;
+ //let tx: Vec<Vec<u8>> = (0..num).map(|i| (i..(16 + i)).collect()).collect();
+ let seed: [u8; 16] = [
+ 130, 220, 246, 217, 111, 124, 221, 189, 190, 234, 121, 93, 67, 95, 100, 43,
+ ];
- let rng = &mut SmallRng::seed_from_u64(seed);
- let tx: Vec<Vec<char>> = iter::repeat_with(|| {
- rng.sample_iter(&Alphanumeric)
- .take(32)
- .map(char::from)
- .collect()
- })
- .take(4096)
- .collect();
+ let rng = &mut SmallRng::from_seed(seed);
+ let tx: Vec<Vec<char>> = (0..4096)
+ .map(|_| (rng.sample_iter(&Alphanumeric).take(32).collect()))
+ .collect();
- // more readable with explicit `true` / `false`
- #[allow(clippy::bool_assert_comparison)]
for _ in 0..32 {
- for x in &tx {
- assert_eq!(m.contains(x), false);
- assert_eq!(m.insert(x.clone()), true);
+ for i in 0..4096 {
+ assert_eq!(m.contains(&tx[i].clone()), false);
+ assert_eq!(m.insert(tx[i].clone()), true);
}
- for (i, x) in tx.iter().enumerate() {
- println!("removing {} {:?}", i, x);
- assert_eq!(m.remove(x), true);
+ for i in 0..4096 {
+ println!("removing {} {:?}", i, tx[i]);
+ assert_eq!(m.remove(&tx[i]), true);
}
}
}
