Snap for 7259849 from f9fb091d441bdc0462e9104e659f8a6c89b23b08 to sc-release
Change-Id: I08b163c4c5cd7f0571f0c9375d5f449640fa0737
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 845b5e7..0eb3824 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
{
"git": {
- "sha1": "34c11891e13fa3c0d08b0540e869aace9d347c26"
+ "sha1": "bbb5d3bb1c23569c15e54c670bc0c3669ae3e7dc"
}
}
diff --git a/Android.bp b/Android.bp
index f4b72d6..73e0c70 100644
--- a/Android.bp
+++ b/Android.bp
@@ -1,4 +1,5 @@
// This file is generated by cargo2android.py --device --run --dependencies.
+// Do not modify this file as changes will be overridden on upgrade.
package {
default_applicable_licenses: ["external_rust_crates_hashbrown_license"],
@@ -53,4 +54,9 @@
}
// dependent_library ["feature_list"]
-// ahash-0.4.6
+// ahash-0.7.2 "folded_multiply,runtime-rng,specialize"
+// cfg-if-1.0.0
+// getrandom-0.2.2
+// libc-0.2.92 "default,std"
+// once_cell-1.7.2 "alloc,race,unstable"
+// version_check-0.9.3
diff --git a/CHANGELOG.md b/CHANGELOG.md
index b6eb671..c88d3e0 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -7,6 +7,50 @@
## [Unreleased]
+## [v0.11.2] - 2021-03-25
+
+## Fixed
+
+- Added missing allocator type parameter to `HashMap`'s and `HashSet`'s `Clone` impls. (#252)
+
+## [v0.11.1] - 2021-03-20
+
+## Fixed
+
+- Added missing `pub` modifier to `BumpWrapper`. (#251)
+
+## [v0.11.0] - 2021-03-14
+
+## Added
+- Added safe `try_insert_no_grow` method to `RawTable`. (#229)
+- Added support for `bumpalo` as an allocator without the `nightly` feature. (#231)
+- Implemented `Default` for `RawTable`. (#237)
+- Added new safe methods `RawTable::get_each_mut`, `HashMap::get_each_mut`, and
+ `HashMap::get_each_key_value_mut`. (#239)
+- Added `From<HashMap<T, ()>>` for `HashSet<T>`. (#235)
+- Added `try_insert` method to `HashMap`. (#247)
+
+## Changed
+- The minimum Rust version has been bumped to 1.49.0. (#230)
+- Significantly improved compilation times by reducing the amount of generated IR. (#205)
+
+## Removed
+- We no longer re-export the unstable allocator items from the standard library, nor the stable shims approximating the same. (#227)
+- Removed hasher specialization support from `aHash`, which was resulting in inconsistent hashes being generated for a key. (#248)
+
+## Fixed
+- Fixed union length comparison. (#228)
+
+## ~~[v0.10.0] - 2021-01-16~~
+
+This release was _yanked_ due to inconsistent hashes being generated with the `nightly` feature. (#248)
+
+## Changed
+- Parametrized `RawTable`, `HashSet` and `HashMap` over an allocator. (#133)
+- Improved branch prediction hints on stable. (#209)
+- Optimized hashing of primitive types with AHash using specialization. (#207)
+- Only instantiate `RawTable`'s reserve functions once per key-value. (#204)
+
## [v0.9.1] - 2020-09-28
## Added
@@ -263,7 +307,11 @@
- Initial release
-[Unreleased]: https://github.com/rust-lang/hashbrown/compare/v0.9.1...HEAD
+[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
+[v0.10.0]: https://github.com/rust-lang/hashbrown/compare/v0.9.1...v0.10.0
[v0.9.1]: https://github.com/rust-lang/hashbrown/compare/v0.9.0...v0.9.1
[v0.9.0]: https://github.com/rust-lang/hashbrown/compare/v0.8.2...v0.9.0
[v0.8.2]: https://github.com/rust-lang/hashbrown/compare/v0.8.1...v0.8.2
diff --git a/Cargo.toml b/Cargo.toml
index 7be0341..02bd480 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -13,7 +13,7 @@
[package]
edition = "2018"
name = "hashbrown"
-version = "0.9.1"
+version = "0.11.2"
authors = ["Amanieu d'Antras <amanieu@gmail.com>"]
exclude = [".travis.yml", "bors.toml", "/ci/*"]
description = "A Rust port of Google's SwissTable hash map"
@@ -25,7 +25,7 @@
[package.metadata.docs.rs]
features = ["nightly", "rayon", "serde", "raw"]
[dependencies.ahash]
-version = "0.4.4"
+version = "0.7.0"
optional = true
default-features = false
@@ -34,6 +34,10 @@
optional = true
package = "rustc-std-workspace-alloc"
+[dependencies.bumpalo]
+version = "3.5.0"
+optional = true
+
[dependencies.compiler_builtins]
version = "0.1.2"
optional = true
@@ -54,8 +58,11 @@
[dev-dependencies.doc-comment]
version = "0.3.1"
+[dev-dependencies.fnv]
+version = "1.0.7"
+
[dev-dependencies.lazy_static]
-version = "1.2"
+version = "1.4"
[dev-dependencies.rand]
version = "0.7.3"
@@ -64,9 +71,6 @@
[dev-dependencies.rayon]
version = "1.0"
-[dev-dependencies.rustc-hash]
-version = "=1.0"
-
[dev-dependencies.serde_test]
version = "1.0"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 21bd5c2..a056c3c 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,6 +1,6 @@
[package]
name = "hashbrown"
-version = "0.9.1"
+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"
@@ -13,7 +13,7 @@
[dependencies]
# For the default hasher
-ahash = { version = "0.4.4", optional = true, default-features = false }
+ahash = { version = "0.7.0", default-features = false, optional = true }
# For external trait impls
rayon = { version = "1.0", optional = true }
@@ -24,11 +24,14 @@
compiler_builtins = { version = "0.1.2", optional = true }
alloc = { version = "1.0.0", optional = true, package = "rustc-std-workspace-alloc" }
+# Optional support for bumpalo
+bumpalo = { version = "3.5.0", optional = true }
+
[dev-dependencies]
-lazy_static = "1.2"
+lazy_static = "1.4"
rand = { version = "0.7.3", features = ["small_rng"] }
rayon = "1.0"
-rustc-hash = "=1.0"
+fnv = "1.0.7"
serde_test = "1.0"
doc-comment = "0.3.1"
diff --git a/METADATA b/METADATA
index b3d1a7c..fa67d80 100644
--- a/METADATA
+++ b/METADATA
@@ -7,13 +7,13 @@
}
url {
type: ARCHIVE
- value: "https://static.crates.io/crates/hashbrown/hashbrown-0.9.1.crate"
+ value: "https://static.crates.io/crates/hashbrown/hashbrown-0.11.2.crate"
}
- version: "0.9.1"
+ version: "0.11.2"
license_type: NOTICE
last_upgrade_date {
- year: 2020
- month: 11
- day: 9
+ year: 2021
+ month: 4
+ day: 1
}
}
diff --git a/README.md b/README.md
index 2e43171..86664c4 100644
--- a/README.md
+++ b/README.md
@@ -4,7 +4,7 @@
[](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`
@@ -26,7 +26,8 @@
## Features
- Drop-in replacement for the standard library `HashMap` and `HashSet` types.
-- Uses `AHash` as the default hasher, which is much faster than SipHash.
+- Uses [AHash](https://github.com/tkaitchuck/aHash) as the default hasher, which is much faster than SipHash.
+ However, AHash does *not provide the same level of HashDoS resistance* as SipHash, so if that is important to you, you might want to consider using a different hasher.
- Around 2x faster than the previous standard library `HashMap`.
- Lower memory usage: only 1 byte of overhead per entry instead of 8.
- Compatible with `#[no_std]` (but requires a global allocator with the `alloc` crate).
@@ -37,47 +38,46 @@
Compared to the previous implementation of `std::collections::HashMap` (Rust 1.35).
-With the hashbrown default AHash hasher (not HashDoS-resistant):
+With the hashbrown default AHash hasher:
-```text
- name oldstdhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup
- insert_ahash_highbits 20,846 7,397 -13,449 -64.52% x 2.82
- insert_ahash_random 20,515 7,796 -12,719 -62.00% x 2.63
- insert_ahash_serial 21,668 7,264 -14,404 -66.48% x 2.98
- insert_erase_ahash_highbits 29,570 17,498 -12,072 -40.83% x 1.69
- insert_erase_ahash_random 39,569 17,474 -22,095 -55.84% x 2.26
- insert_erase_ahash_serial 32,073 17,332 -14,741 -45.96% x 1.85
- iter_ahash_highbits 1,572 2,087 515 32.76% x 0.75
- iter_ahash_random 1,609 2,074 465 28.90% x 0.78
- iter_ahash_serial 2,293 2,120 -173 -7.54% x 1.08
- lookup_ahash_highbits 3,460 4,403 943 27.25% x 0.79
- lookup_ahash_random 6,377 3,911 -2,466 -38.67% x 1.63
- lookup_ahash_serial 3,629 3,586 -43 -1.18% x 1.01
- lookup_fail_ahash_highbits 5,286 3,411 -1,875 -35.47% x 1.55
- lookup_fail_ahash_random 12,365 4,171 -8,194 -66.27% x 2.96
- lookup_fail_ahash_serial 4,902 3,240 -1,662 -33.90% x 1.51
-```
+| name | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | speedup |
+|:------------------------|:-------------------:|------------------:|:------------:|---------:|---------|
+| insert_ahash_highbits | 18,865 | 8,020 | -10,845 | -57.49% | x 2.35 |
+| insert_ahash_random | 19,711 | 8,019 | -11,692 | -59.32% | x 2.46 |
+| insert_ahash_serial | 19,365 | 6,463 | -12,902 | -66.63% | x 3.00 |
+| insert_erase_ahash_highbits | 51,136 | 17,916 | -33,220 | -64.96% | x 2.85 |
+| insert_erase_ahash_random | 51,157 | 17,688 | -33,469 | -65.42% | x 2.89 |
+| insert_erase_ahash_serial | 45,479 | 14,895 | -30,584 | -67.25% | x 3.05 |
+| iter_ahash_highbits | 1,399 | 1,092 | -307 | -21.94% | x 1.28 |
+| iter_ahash_random | 1,586 | 1,059 | -527 | -33.23% | x 1.50 |
+| iter_ahash_serial | 3,168 | 1,079 | -2,089 | -65.94% | x 2.94 |
+| lookup_ahash_highbits | 32,351 | 4,792 | -27,559 | -85.19% | x 6.75 |
+| lookup_ahash_random | 17,419 | 4,817 | -12,602 | -72.35% | x 3.62 |
+| lookup_ahash_serial | 15,254 | 3,606 | -11,648 | -76.36% | x 4.23 |
+| lookup_fail_ahash_highbits | 21,187 | 4,369 | -16,818 | -79.38% | x 4.85 |
+| lookup_fail_ahash_random | 21,550 | 4,395 | -17,155 | -79.61% | x 4.90 |
+| lookup_fail_ahash_serial | 19,450 | 3,176 | -16,274 | -83.67% | x 6.12 |
-With the libstd default SipHash hasher (HashDoS-resistant):
-```text
- name oldstdhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup
- insert_std_highbits 32,598 20,199 -12,399 -38.04% x 1.61
- insert_std_random 29,824 20,760 -9,064 -30.39% x 1.44
- insert_std_serial 33,151 17,256 -15,895 -47.95% x 1.92
- insert_erase_std_highbits 74,731 48,735 -25,996 -34.79% x 1.53
- insert_erase_std_random 73,828 47,649 -26,179 -35.46% x 1.55
- insert_erase_std_serial 73,864 40,147 -33,717 -45.65% x 1.84
- iter_std_highbits 1,518 2,264 746 49.14% x 0.67
- iter_std_random 1,502 2,414 912 60.72% x 0.62
- iter_std_serial 6,361 2,118 -4,243 -66.70% x 3.00
- lookup_std_highbits 21,705 16,962 -4,743 -21.85% x 1.28
- lookup_std_random 21,654 17,158 -4,496 -20.76% x 1.26
- lookup_std_serial 18,726 14,509 -4,217 -22.52% x 1.29
- lookup_fail_std_highbits 25,852 17,323 -8,529 -32.99% x 1.49
- lookup_fail_std_random 25,913 17,760 -8,153 -31.46% x 1.46
- lookup_fail_std_serial 22,648 14,839 -7,809 -34.48% x 1.53
-```
+With the libstd default SipHash hasher:
+
+|name | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | speedup |
+|:------------------------|:-------------------:|------------------:|:------------:|---------:|---------|
+|insert_std_highbits |19,216 |16,885 | -2,331 | -12.13% | x 1.14 |
+|insert_std_random |19,179 |17,034 | -2,145 | -11.18% | x 1.13 |
+|insert_std_serial |19,462 |17,493 | -1,969 | -10.12% | x 1.11 |
+|insert_erase_std_highbits |50,825 |35,847 | -14,978 | -29.47% | x 1.42 |
+|insert_erase_std_random |51,448 |35,392 | -16,056 | -31.21% | x 1.45 |
+|insert_erase_std_serial |87,711 |38,091 | -49,620 | -56.57% | x 2.30 |
+|iter_std_highbits |1,378 |1,159 | -219 | -15.89% | x 1.19 |
+|iter_std_random |1,395 |1,132 | -263 | -18.85% | x 1.23 |
+|iter_std_serial |1,704 |1,105 | -599 | -35.15% | x 1.54 |
+|lookup_std_highbits |17,195 |13,642 | -3,553 | -20.66% | x 1.26 |
+|lookup_std_random |17,181 |13,773 | -3,408 | -19.84% | x 1.25 |
+|lookup_std_serial |15,483 |13,651 | -1,832 | -11.83% | x 1.13 |
+|lookup_fail_std_highbits |20,926 |13,474 | -7,452 | -35.61% | x 1.55 |
+|lookup_fail_std_random |21,766 |13,505 | -8,261 | -37.95% | x 1.61 |
+|lookup_fail_std_serial |19,336 |13,519 | -5,817 | -30.08% | x 1.43 |
## Usage
@@ -85,7 +85,7 @@
```toml
[dependencies]
-hashbrown = "0.9"
+hashbrown = "0.11"
```
Then:
@@ -96,19 +96,19 @@
let mut map = HashMap::new();
map.insert(1, "one");
```
-
+## Flags
This crate has the following Cargo features:
-- `nightly`: Enables nightly-only features: `#[may_dangle]`.
+- `nightly`: Enables nightly-only features including: `#[may_dangle]`.
- `serde`: Enables serde serialization support.
- `rayon`: Enables rayon parallel iterator support.
- `raw`: Enables access to the experimental and unsafe `RawTable` API.
- `inline-more`: Adds inline hints to most functions, improving run-time performance at the cost
of compilation time. (enabled by default)
+- `bumpalo`: Provides a `BumpWrapper` type which allows `bumpalo` to be used for memory allocation.
- `ahash`: Compiles with ahash as default hasher. (enabled by default)
-- `ahash-compile-time-rng`: Activates the `compile-time-rng` feature of ahash, to increase the
- DOS-resistance, but can result in issues for `no_std` builds. More details in
- [issue#124](https://github.com/rust-lang/hashbrown/issues/124). (enabled by default)
+- `ahash-compile-time-rng`: Activates the `compile-time-rng` feature of ahash. For targets with no random number generator
+this pre-generates seeds at compile time and embeds them as constants. See [aHash's documentation](https://github.com/tkaitchuck/aHash#flags) (disabled by default)
## License
diff --git a/TEST_MAPPING b/TEST_MAPPING
new file mode 100644
index 0000000..e707449
--- /dev/null
+++ b/TEST_MAPPING
@@ -0,0 +1,11 @@
+// Generated by update_crate_tests.py for tests that depend on this crate.
+{
+ "presubmit": [
+ {
+ "name": "keystore2_test"
+ },
+ {
+ "name": "vpnprofilestore_test"
+ }
+ ]
+}
diff --git a/benches/bench.rs b/benches/bench.rs
index 771e716..568c513 100644
--- a/benches/bench.rs
+++ b/benches/bench.rs
@@ -9,8 +9,11 @@
use test::{black_box, Bencher};
use hashbrown::hash_map::DefaultHashBuilder;
-use hashbrown::HashMap;
-use std::collections::hash_map::RandomState;
+use hashbrown::{HashMap, HashSet};
+use std::{
+ collections::hash_map::RandomState,
+ sync::atomic::{self, AtomicUsize},
+};
const SIZE: usize = 1000;
@@ -40,6 +43,20 @@
}
}
+// Just an arbitrary side effect to make the maps not shortcircuit to the non-dropping path
+// when dropping maps/entries (most real world usages likely have drop in the key or value)
+lazy_static::lazy_static! {
+ static ref SIDE_EFFECT: AtomicUsize = AtomicUsize::new(0);
+}
+
+#[derive(Clone)]
+struct DropType(usize);
+impl Drop for DropType {
+ fn drop(&mut self) {
+ SIDE_EFFECT.fetch_add(self.0, atomic::Ordering::SeqCst);
+ }
+}
+
macro_rules! bench_suite {
($bench_macro:ident, $bench_ahash_serial:ident, $bench_std_serial:ident,
$bench_ahash_highbits:ident, $bench_std_highbits:ident,
@@ -69,10 +86,11 @@
b.iter(|| {
m.clear();
for i in ($keydist).take(SIZE) {
- m.insert(i, i);
+ m.insert(i, (DropType(i), [i; 20]));
}
black_box(&mut m);
- })
+ });
+ eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
}
};
}
@@ -87,13 +105,38 @@
insert_std_random
);
+macro_rules! bench_grow_insert {
+ ($name:ident, $maptype:ident, $keydist:expr) => {
+ #[bench]
+ fn $name(b: &mut Bencher) {
+ b.iter(|| {
+ let mut m = $maptype::default();
+ for i in ($keydist).take(SIZE) {
+ m.insert(i, DropType(i));
+ }
+ black_box(&mut m);
+ })
+ }
+ };
+}
+
+bench_suite!(
+ bench_grow_insert,
+ grow_insert_ahash_serial,
+ grow_insert_std_serial,
+ grow_insert_ahash_highbits,
+ grow_insert_std_highbits,
+ grow_insert_ahash_random,
+ grow_insert_std_random
+);
+
macro_rules! bench_insert_erase {
($name:ident, $maptype:ident, $keydist:expr) => {
#[bench]
fn $name(b: &mut Bencher) {
let mut base = $maptype::default();
for i in ($keydist).take(SIZE) {
- base.insert(i, i);
+ base.insert(i, DropType(i));
}
let skip = $keydist.skip(SIZE);
b.iter(|| {
@@ -103,11 +146,12 @@
// While keeping the size constant,
// replace the first keydist with the second.
for (add, remove) in (&mut add_iter).zip(&mut remove_iter).take(SIZE) {
- m.insert(add, add);
+ m.insert(add, DropType(add));
black_box(m.remove(&remove));
}
black_box(m);
- })
+ });
+ eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
}
};
}
@@ -128,14 +172,15 @@
fn $name(b: &mut Bencher) {
let mut m = $maptype::default();
for i in $keydist.take(SIZE) {
- m.insert(i, i);
+ m.insert(i, DropType(i));
}
b.iter(|| {
for i in $keydist.take(SIZE) {
black_box(m.get(&i));
}
- })
+ });
+ eprintln!("{}", SIDE_EFFECT.load(atomic::Ordering::SeqCst));
}
};
}
@@ -157,7 +202,7 @@
let mut m = $maptype::default();
let mut iter = $keydist;
for i in (&mut iter).take(SIZE) {
- m.insert(i, i);
+ m.insert(i, DropType(i));
}
b.iter(|| {
@@ -185,7 +230,7 @@
fn $name(b: &mut Bencher) {
let mut m = $maptype::default();
for i in ($keydist).take(SIZE) {
- m.insert(i, i);
+ m.insert(i, DropType(i));
}
b.iter(|| {
@@ -211,7 +256,7 @@
fn clone_small(b: &mut Bencher) {
let mut m = HashMap::new();
for i in 0..10 {
- m.insert(i, i);
+ m.insert(i, DropType(i));
}
b.iter(|| {
@@ -224,7 +269,7 @@
let mut m = HashMap::new();
let mut m2 = HashMap::new();
for i in 0..10 {
- m.insert(i, i);
+ m.insert(i, DropType(i));
}
b.iter(|| {
@@ -237,7 +282,7 @@
fn clone_large(b: &mut Bencher) {
let mut m = HashMap::new();
for i in 0..1000 {
- m.insert(i, i);
+ m.insert(i, DropType(i));
}
b.iter(|| {
@@ -250,7 +295,7 @@
let mut m = HashMap::new();
let mut m2 = HashMap::new();
for i in 0..1000 {
- m.insert(i, i);
+ m.insert(i, DropType(i));
}
b.iter(|| {
@@ -258,3 +303,29 @@
black_box(&mut m2);
})
}
+
+#[bench]
+fn rehash_in_place(b: &mut Bencher) {
+ b.iter(|| {
+ let mut set = HashSet::new();
+
+ // Each loop triggers one rehash
+ for _ in 0..10 {
+ for i in 0..224 {
+ set.insert(i);
+ }
+
+ assert_eq!(
+ set.capacity(),
+ 224,
+ "The set must be at or close to capacity to trigger a re hashing"
+ );
+
+ for i in 100..1400 {
+ set.remove(&(i - 100));
+ set.insert(i);
+ }
+ set.clear();
+ }
+ });
+}
diff --git a/src/external_trait_impls/rayon/map.rs b/src/external_trait_impls/rayon/map.rs
index 334f8bb..61b7380 100644
--- a/src/external_trait_impls/rayon/map.rs
+++ b/src/external_trait_impls/rayon/map.rs
@@ -1,8 +1,11 @@
//! Rayon extensions for `HashMap`.
+use super::raw::{RawIntoParIter, RawParDrain, RawParIter};
use crate::hash_map::HashMap;
+use crate::raw::{Allocator, Global};
use core::fmt;
use core::hash::{BuildHasher, Hash};
+use core::marker::PhantomData;
use rayon::iter::plumbing::UnindexedConsumer;
use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator};
@@ -15,11 +18,12 @@
/// [`par_iter`]: /hashbrown/struct.HashMap.html#method.par_iter
/// [`HashMap`]: /hashbrown/struct.HashMap.html
/// [`IntoParallelRefIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefIterator.html
-pub struct ParIter<'a, K, V, S> {
- map: &'a HashMap<K, V, S>,
+pub struct ParIter<'a, K, V> {
+ inner: RawParIter<(K, V)>,
+ marker: PhantomData<(&'a K, &'a V)>,
}
-impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParIter<'a, K, V, S> {
+impl<'a, K: Sync, V: Sync> ParallelIterator for ParIter<'a, K, V> {
type Item = (&'a K, &'a V);
#[cfg_attr(feature = "inline-more", inline)]
@@ -27,7 +31,7 @@
where
C: UnindexedConsumer<Self::Item>,
{
- unsafe { self.map.table.par_iter() }
+ self.inner
.map(|x| unsafe {
let r = x.as_ref();
(&r.0, &r.1)
@@ -36,16 +40,23 @@
}
}
-impl<K, V, S> Clone for ParIter<'_, K, V, S> {
+impl<K, V> Clone for ParIter<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
- ParIter { map: self.map }
+ Self {
+ inner: self.inner.clone(),
+ marker: PhantomData,
+ }
}
}
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParIter<'_, K, V, S> {
+impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIter<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- self.map.iter().fmt(f)
+ let iter = unsafe { self.inner.iter() }.map(|x| unsafe {
+ let r = x.as_ref();
+ (&r.0, &r.1)
+ });
+ f.debug_list().entries(iter).finish()
}
}
@@ -56,11 +67,12 @@
///
/// [`par_keys`]: /hashbrown/struct.HashMap.html#method.par_keys
/// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParKeys<'a, K, V, S> {
- map: &'a HashMap<K, V, S>,
+pub struct ParKeys<'a, K, V> {
+ inner: RawParIter<(K, V)>,
+ marker: PhantomData<(&'a K, &'a V)>,
}
-impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParKeys<'a, K, V, S> {
+impl<'a, K: Sync, V: Sync> ParallelIterator for ParKeys<'a, K, V> {
type Item = &'a K;
#[cfg_attr(feature = "inline-more", inline)]
@@ -68,22 +80,26 @@
where
C: UnindexedConsumer<Self::Item>,
{
- unsafe { self.map.table.par_iter() }
+ self.inner
.map(|x| unsafe { &x.as_ref().0 })
.drive_unindexed(consumer)
}
}
-impl<K, V, S> Clone for ParKeys<'_, K, V, S> {
+impl<K, V> Clone for ParKeys<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
- ParKeys { map: self.map }
+ Self {
+ inner: self.inner.clone(),
+ marker: PhantomData,
+ }
}
}
-impl<K: fmt::Debug + Eq + Hash, V, S: BuildHasher> fmt::Debug for ParKeys<'_, K, V, S> {
+impl<K: fmt::Debug + Eq + Hash, V> fmt::Debug for ParKeys<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- self.map.keys().fmt(f)
+ let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().0 });
+ f.debug_list().entries(iter).finish()
}
}
@@ -94,11 +110,12 @@
///
/// [`par_values`]: /hashbrown/struct.HashMap.html#method.par_values
/// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParValues<'a, K, V, S> {
- map: &'a HashMap<K, V, S>,
+pub struct ParValues<'a, K, V> {
+ inner: RawParIter<(K, V)>,
+ marker: PhantomData<(&'a K, &'a V)>,
}
-impl<'a, K: Sync, V: Sync, S: Sync> ParallelIterator for ParValues<'a, K, V, S> {
+impl<'a, K: Sync, V: Sync> ParallelIterator for ParValues<'a, K, V> {
type Item = &'a V;
#[cfg_attr(feature = "inline-more", inline)]
@@ -106,22 +123,26 @@
where
C: UnindexedConsumer<Self::Item>,
{
- unsafe { self.map.table.par_iter() }
+ self.inner
.map(|x| unsafe { &x.as_ref().1 })
.drive_unindexed(consumer)
}
}
-impl<K, V, S> Clone for ParValues<'_, K, V, S> {
+impl<K, V> Clone for ParValues<'_, K, V> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
- ParValues { map: self.map }
+ Self {
+ inner: self.inner.clone(),
+ marker: PhantomData,
+ }
}
}
-impl<K: Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParValues<'_, K, V, S> {
+impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValues<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- self.map.values().fmt(f)
+ let iter = unsafe { self.inner.iter() }.map(|x| unsafe { &x.as_ref().1 });
+ f.debug_list().entries(iter).finish()
}
}
@@ -134,11 +155,12 @@
/// [`par_iter_mut`]: /hashbrown/struct.HashMap.html#method.par_iter_mut
/// [`HashMap`]: /hashbrown/struct.HashMap.html
/// [`IntoParallelRefMutIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefMutIterator.html
-pub struct ParIterMut<'a, K, V, S> {
- map: &'a mut HashMap<K, V, S>,
+pub struct ParIterMut<'a, K, V> {
+ inner: RawParIter<(K, V)>,
+ marker: PhantomData<(&'a K, &'a mut V)>,
}
-impl<'a, K: Send + Sync, V: Send, S: Send> ParallelIterator for ParIterMut<'a, K, V, S> {
+impl<'a, K: Sync, V: Send> ParallelIterator for ParIterMut<'a, K, V> {
type Item = (&'a K, &'a mut V);
#[cfg_attr(feature = "inline-more", inline)]
@@ -146,7 +168,7 @@
where
C: UnindexedConsumer<Self::Item>,
{
- unsafe { self.map.table.par_iter() }
+ self.inner
.map(|x| unsafe {
let r = x.as_mut();
(&r.0, &mut r.1)
@@ -155,11 +177,13 @@
}
}
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug
- for ParIterMut<'_, K, V, S>
-{
+impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug> fmt::Debug for ParIterMut<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- self.map.iter().fmt(f)
+ ParIter {
+ inner: self.inner.clone(),
+ marker: PhantomData,
+ }
+ .fmt(f)
}
}
@@ -170,11 +194,12 @@
///
/// [`par_values_mut`]: /hashbrown/struct.HashMap.html#method.par_values_mut
/// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParValuesMut<'a, K, V, S> {
- map: &'a mut HashMap<K, V, S>,
+pub struct ParValuesMut<'a, K, V> {
+ inner: RawParIter<(K, V)>,
+ marker: PhantomData<(&'a K, &'a mut V)>,
}
-impl<'a, K: Send, V: Send, S: Send> ParallelIterator for ParValuesMut<'a, K, V, S> {
+impl<'a, K: Sync, V: Send> ParallelIterator for ParValuesMut<'a, K, V> {
type Item = &'a mut V;
#[cfg_attr(feature = "inline-more", inline)]
@@ -182,15 +207,19 @@
where
C: UnindexedConsumer<Self::Item>,
{
- unsafe { self.map.table.par_iter() }
+ self.inner
.map(|x| unsafe { &mut x.as_mut().1 })
.drive_unindexed(consumer)
}
}
-impl<K: Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for ParValuesMut<'_, K, V, S> {
+impl<K: Eq + Hash, V: fmt::Debug> fmt::Debug for ParValuesMut<'_, K, V> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- self.map.values().fmt(f)
+ ParValues {
+ inner: self.inner.clone(),
+ marker: PhantomData,
+ }
+ .fmt(f)
}
}
@@ -203,11 +232,11 @@
/// [`into_par_iter`]: /hashbrown/struct.HashMap.html#method.into_par_iter
/// [`HashMap`]: /hashbrown/struct.HashMap.html
/// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html
-pub struct IntoParIter<K, V, S> {
- map: HashMap<K, V, S>,
+pub struct IntoParIter<K, V, A: Allocator + Clone = Global> {
+ inner: RawIntoParIter<(K, V), A>,
}
-impl<K: Send, V: Send, S: Send> ParallelIterator for IntoParIter<K, V, S> {
+impl<K: Send, V: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<K, V, A> {
type Item = (K, V);
#[cfg_attr(feature = "inline-more", inline)]
@@ -215,13 +244,19 @@
where
C: UnindexedConsumer<Self::Item>,
{
- self.map.table.into_par_iter().drive_unindexed(consumer)
+ self.inner.drive_unindexed(consumer)
}
}
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for IntoParIter<K, V, S> {
+impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug
+ for IntoParIter<K, V, A>
+{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- self.map.iter().fmt(f)
+ ParIter {
+ inner: unsafe { self.inner.par_iter() },
+ marker: PhantomData,
+ }
+ .fmt(f)
}
}
@@ -232,11 +267,11 @@
///
/// [`par_drain`]: /hashbrown/struct.HashMap.html#method.par_drain
/// [`HashMap`]: /hashbrown/struct.HashMap.html
-pub struct ParDrain<'a, K, V, S> {
- map: &'a mut HashMap<K, V, S>,
+pub struct ParDrain<'a, K, V, A: Allocator + Clone = Global> {
+ inner: RawParDrain<'a, (K, V), A>,
}
-impl<K: Send, V: Send, S: Send> ParallelIterator for ParDrain<'_, K, V, S> {
+impl<K: Send, V: Send, A: Allocator + Clone + Sync> ParallelIterator for ParDrain<'_, K, V, A> {
type Item = (K, V);
#[cfg_attr(feature = "inline-more", inline)]
@@ -244,52 +279,68 @@
where
C: UnindexedConsumer<Self::Item>,
{
- self.map.table.par_drain().drive_unindexed(consumer)
+ self.inner.drive_unindexed(consumer)
}
}
-impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug
- for ParDrain<'_, K, V, S>
+impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, A: Allocator + Clone> fmt::Debug
+ for ParDrain<'_, K, V, A>
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- self.map.iter().fmt(f)
+ ParIter {
+ inner: unsafe { self.inner.par_iter() },
+ marker: PhantomData,
+ }
+ .fmt(f)
}
}
-impl<K: Sync, V: Sync, S: Sync> HashMap<K, V, S> {
+impl<K: Sync, V: Sync, S, A: Allocator + Clone> HashMap<K, V, S, A> {
/// Visits (potentially in parallel) immutably borrowed keys in an arbitrary order.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_keys(&self) -> ParKeys<'_, K, V, S> {
- ParKeys { map: self }
+ pub fn par_keys(&self) -> ParKeys<'_, K, V> {
+ ParKeys {
+ inner: unsafe { self.table.par_iter() },
+ marker: PhantomData,
+ }
}
/// Visits (potentially in parallel) immutably borrowed values in an arbitrary order.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_values(&self) -> ParValues<'_, K, V, S> {
- ParValues { map: self }
+ pub fn par_values(&self) -> ParValues<'_, K, V> {
+ ParValues {
+ inner: unsafe { self.table.par_iter() },
+ marker: PhantomData,
+ }
}
}
-impl<K: Send, V: Send, S: Send> HashMap<K, V, S> {
+impl<K: Send, V: Send, S, A: Allocator + Clone> HashMap<K, V, S, A> {
/// Visits (potentially in parallel) mutably borrowed values in an arbitrary order.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V, S> {
- ParValuesMut { map: self }
+ pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> {
+ ParValuesMut {
+ inner: unsafe { self.table.par_iter() },
+ marker: PhantomData,
+ }
}
/// Consumes (potentially in parallel) all values in an arbitrary order,
/// while preserving the map's allocated memory for reuse.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_drain(&mut self) -> ParDrain<'_, K, V, S> {
- ParDrain { map: self }
+ pub fn par_drain(&mut self) -> ParDrain<'_, K, V, A> {
+ ParDrain {
+ inner: self.table.par_drain(),
+ }
}
}
-impl<K, V, S> HashMap<K, V, S>
+impl<K, V, S, A> HashMap<K, V, S, A>
where
K: Eq + Hash + Sync,
V: PartialEq + Sync,
S: BuildHasher + Sync,
+ A: Allocator + Clone + Sync,
{
/// Returns `true` if the map is equal to another,
/// i.e. both maps contain the same keys mapped to the same values.
@@ -303,33 +354,47 @@
}
}
-impl<K: Send, V: Send, S: Send> IntoParallelIterator for HashMap<K, V, S> {
+impl<K: Send, V: Send, S, A: Allocator + Clone + Send> IntoParallelIterator
+ for HashMap<K, V, S, A>
+{
type Item = (K, V);
- type Iter = IntoParIter<K, V, S>;
+ type Iter = IntoParIter<K, V, A>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_par_iter(self) -> Self::Iter {
- IntoParIter { map: self }
+ IntoParIter {
+ inner: self.table.into_par_iter(),
+ }
}
}
-impl<'a, K: Sync, V: Sync, S: Sync> IntoParallelIterator for &'a HashMap<K, V, S> {
+impl<'a, K: Sync, V: Sync, S, A: Allocator + Clone> IntoParallelIterator
+ for &'a HashMap<K, V, S, A>
+{
type Item = (&'a K, &'a V);
- type Iter = ParIter<'a, K, V, S>;
+ type Iter = ParIter<'a, K, V>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_par_iter(self) -> Self::Iter {
- ParIter { map: self }
+ ParIter {
+ inner: unsafe { self.table.par_iter() },
+ marker: PhantomData,
+ }
}
}
-impl<'a, K: Send + Sync, V: Send, S: Send> IntoParallelIterator for &'a mut HashMap<K, V, S> {
+impl<'a, K: Sync, V: Send, S, A: Allocator + Clone> IntoParallelIterator
+ for &'a mut HashMap<K, V, S, A>
+{
type Item = (&'a K, &'a mut V);
- type Iter = ParIterMut<'a, K, V, S>;
+ type Iter = ParIterMut<'a, K, V>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_par_iter(self) -> Self::Iter {
- ParIterMut { map: self }
+ ParIterMut {
+ inner: unsafe { self.table.par_iter() },
+ marker: PhantomData,
+ }
}
}
@@ -337,7 +402,7 @@
/// hashmap. If multiple pairs correspond to the same key, then the
/// ones produced earlier in the parallel iterator will be
/// overwritten, just as with a sequential iterator.
-impl<K, V, S> FromParallelIterator<(K, V)> for HashMap<K, V, S>
+impl<K, V, S> FromParallelIterator<(K, V)> for HashMap<K, V, S, Global>
where
K: Eq + Hash + Send,
V: Send,
@@ -354,11 +419,12 @@
}
/// Extend a hash map with items from a parallel iterator.
-impl<K, V, S> ParallelExtend<(K, V)> for HashMap<K, V, S>
+impl<K, V, S, A> ParallelExtend<(K, V)> for HashMap<K, V, S, A>
where
K: Eq + Hash + Send,
V: Send,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn par_extend<I>(&mut self, par_iter: I)
where
@@ -369,11 +435,12 @@
}
/// Extend a hash map with copied items from a parallel iterator.
-impl<'a, K, V, S> ParallelExtend<(&'a K, &'a V)> for HashMap<K, V, S>
+impl<'a, K, V, S, A> ParallelExtend<(&'a K, &'a V)> for HashMap<K, V, S, A>
where
K: Copy + Eq + Hash + Sync,
V: Copy + Sync,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn par_extend<I>(&mut self, par_iter: I)
where
@@ -384,12 +451,13 @@
}
// This is equal to the normal `HashMap` -- no custom advantage.
-fn extend<K, V, S, I>(map: &mut HashMap<K, V, S>, par_iter: I)
+fn extend<K, V, S, A, I>(map: &mut HashMap<K, V, S, A>, par_iter: I)
where
K: Eq + Hash,
S: BuildHasher,
I: IntoParallelIterator,
- HashMap<K, V, S>: Extend<I::Item>,
+ A: Allocator + Clone,
+ HashMap<K, V, S, A>: Extend<I::Item>,
{
let (list, len) = super::helpers::collect(par_iter);
diff --git a/src/external_trait_impls/rayon/raw.rs b/src/external_trait_impls/rayon/raw.rs
index 1bd2c17..18da1ea 100644
--- a/src/external_trait_impls/rayon/raw.rs
+++ b/src/external_trait_impls/rayon/raw.rs
@@ -1,5 +1,5 @@
use crate::raw::Bucket;
-use crate::raw::{RawIter, RawIterRange, RawTable};
+use crate::raw::{Allocator, Global, RawIter, RawIterRange, RawTable};
use crate::scopeguard::guard;
use alloc::alloc::dealloc;
use core::marker::PhantomData;
@@ -15,6 +15,22 @@
iter: RawIterRange<T>,
}
+impl<T> RawParIter<T> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub(super) unsafe fn iter(&self) -> RawIterRange<T> {
+ self.iter.clone()
+ }
+}
+
+impl<T> Clone for RawParIter<T> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn clone(&self) -> Self {
+ Self {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
impl<T> From<RawIter<T>> for RawParIter<T> {
fn from(it: RawIter<T>) -> Self {
RawParIter { iter: it.iter }
@@ -60,11 +76,18 @@
}
/// Parallel iterator which consumes a table and returns elements.
-pub struct RawIntoParIter<T> {
- table: RawTable<T>,
+pub struct RawIntoParIter<T, A: Allocator + Clone = Global> {
+ table: RawTable<T, A>,
}
-impl<T: Send> ParallelIterator for RawIntoParIter<T> {
+impl<T, A: Allocator + Clone> RawIntoParIter<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub(super) unsafe fn par_iter(&self) -> RawParIter<T> {
+ self.table.par_iter()
+ }
+}
+
+impl<T: Send, A: Allocator + Clone> ParallelIterator for RawIntoParIter<T, A> {
type Item = T;
#[cfg_attr(feature = "inline-more", inline)]
@@ -73,7 +96,7 @@
C: UnindexedConsumer<Self::Item>,
{
let iter = unsafe { self.table.iter().iter };
- let _guard = guard(self.table.into_alloc(), |alloc| {
+ let _guard = guard(self.table.into_allocation(), |alloc| {
if let Some((ptr, layout)) = *alloc {
unsafe {
dealloc(ptr.as_ptr(), layout);
@@ -86,16 +109,23 @@
}
/// Parallel iterator which consumes elements without freeing the table storage.
-pub struct RawParDrain<'a, T> {
+pub struct RawParDrain<'a, T, A: Allocator + Clone = Global> {
// We don't use a &'a mut RawTable<T> because we want RawParDrain to be
// covariant over T.
- table: NonNull<RawTable<T>>,
- marker: PhantomData<&'a RawTable<T>>,
+ table: NonNull<RawTable<T, A>>,
+ marker: PhantomData<&'a RawTable<T, A>>,
}
-unsafe impl<T> Send for RawParDrain<'_, T> {}
+unsafe impl<T, A: Allocator + Clone> Send for RawParDrain<'_, T, A> {}
-impl<T: Send> ParallelIterator for RawParDrain<'_, T> {
+impl<T, A: Allocator + Clone> RawParDrain<'_, T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub(super) unsafe fn par_iter(&self) -> RawParIter<T> {
+ self.table.as_ref().par_iter()
+ }
+}
+
+impl<T: Send, A: Allocator + Clone> ParallelIterator for RawParDrain<'_, T, A> {
type Item = T;
#[cfg_attr(feature = "inline-more", inline)]
@@ -113,7 +143,7 @@
}
}
-impl<T> Drop for RawParDrain<'_, T> {
+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() }
@@ -172,7 +202,7 @@
}
}
-impl<T> RawTable<T> {
+impl<T, A: Allocator + Clone> RawTable<T, A> {
/// Returns a parallel iterator over the elements in a `RawTable`.
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn par_iter(&self) -> RawParIter<T> {
@@ -183,14 +213,14 @@
/// Returns a parallel iterator over the elements in a `RawTable`.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn into_par_iter(self) -> RawIntoParIter<T> {
+ pub fn into_par_iter(self) -> RawIntoParIter<T, A> {
RawIntoParIter { table: self }
}
/// Returns a parallel iterator which consumes all elements of a `RawTable`
/// without freeing its memory allocation.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_drain(&mut self) -> RawParDrain<'_, T> {
+ pub fn par_drain(&mut self) -> RawParDrain<'_, T, A> {
RawParDrain {
table: NonNull::from(self),
marker: PhantomData,
diff --git a/src/external_trait_impls/rayon/set.rs b/src/external_trait_impls/rayon/set.rs
index 53d2660..ee4f6e6 100644
--- a/src/external_trait_impls/rayon/set.rs
+++ b/src/external_trait_impls/rayon/set.rs
@@ -1,6 +1,8 @@
//! Rayon extensions for `HashSet`.
+use super::map;
use crate::hash_set::HashSet;
+use crate::raw::{Allocator, Global};
use core::hash::{BuildHasher, Hash};
use rayon::iter::plumbing::UnindexedConsumer;
use rayon::iter::{FromParallelIterator, IntoParallelIterator, ParallelExtend, ParallelIterator};
@@ -14,22 +16,18 @@
/// [`into_par_iter`]: /hashbrown/struct.HashSet.html#method.into_par_iter
/// [`HashSet`]: /hashbrown/struct.HashSet.html
/// [`IntoParallelIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelIterator.html
-pub struct IntoParIter<T, S> {
- set: HashSet<T, S>,
+pub struct IntoParIter<T, A: Allocator + Clone = Global> {
+ inner: map::IntoParIter<T, (), A>,
}
-impl<T: Send, S: Send> ParallelIterator for IntoParIter<T, S> {
+impl<T: Send, A: Allocator + Clone + Send> ParallelIterator for IntoParIter<T, A> {
type Item = T;
fn drive_unindexed<C>(self, consumer: C) -> C::Result
where
C: UnindexedConsumer<Self::Item>,
{
- self.set
- .map
- .into_par_iter()
- .map(|(k, _)| k)
- .drive_unindexed(consumer)
+ self.inner.map(|(k, _)| k).drive_unindexed(consumer)
}
}
@@ -40,22 +38,18 @@
///
/// [`par_drain`]: /hashbrown/struct.HashSet.html#method.par_drain
/// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParDrain<'a, T, S> {
- set: &'a mut HashSet<T, S>,
+pub struct ParDrain<'a, T, A: Allocator + Clone = Global> {
+ inner: map::ParDrain<'a, T, (), A>,
}
-impl<T: Send, S: Send> ParallelIterator for ParDrain<'_, T, S> {
+impl<T: Send, A: Allocator + Clone + Send + Sync> ParallelIterator for ParDrain<'_, T, A> {
type Item = T;
fn drive_unindexed<C>(self, consumer: C) -> C::Result
where
C: UnindexedConsumer<Self::Item>,
{
- self.set
- .map
- .par_drain()
- .map(|(k, _)| k)
- .drive_unindexed(consumer)
+ self.inner.map(|(k, _)| k).drive_unindexed(consumer)
}
}
@@ -68,18 +62,18 @@
/// [`par_iter`]: /hashbrown/struct.HashSet.html#method.par_iter
/// [`HashSet`]: /hashbrown/struct.HashSet.html
/// [`IntoParallelRefIterator`]: https://docs.rs/rayon/1.0/rayon/iter/trait.IntoParallelRefIterator.html
-pub struct ParIter<'a, T, S> {
- set: &'a HashSet<T, S>,
+pub struct ParIter<'a, T> {
+ inner: map::ParKeys<'a, T, ()>,
}
-impl<'a, T: Sync, S: Sync> ParallelIterator for ParIter<'a, T, S> {
+impl<'a, T: Sync> ParallelIterator for ParIter<'a, T> {
type Item = &'a T;
fn drive_unindexed<C>(self, consumer: C) -> C::Result
where
C: UnindexedConsumer<Self::Item>,
{
- self.set.map.par_keys().drive_unindexed(consumer)
+ self.inner.drive_unindexed(consumer)
}
}
@@ -91,15 +85,16 @@
///
/// [`par_difference`]: /hashbrown/struct.HashSet.html#method.par_difference
/// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParDifference<'a, T, S> {
- a: &'a HashSet<T, S>,
- b: &'a HashSet<T, S>,
+pub struct ParDifference<'a, T, S, A: Allocator + Clone = Global> {
+ a: &'a HashSet<T, S, A>,
+ b: &'a HashSet<T, S, A>,
}
-impl<'a, T, S> ParallelIterator for ParDifference<'a, T, S>
+impl<'a, T, S, A> ParallelIterator for ParDifference<'a, T, S, A>
where
T: Eq + Hash + Sync,
S: BuildHasher + Sync,
+ A: Allocator + Clone + Sync,
{
type Item = &'a T;
@@ -123,15 +118,16 @@
///
/// [`par_symmetric_difference`]: /hashbrown/struct.HashSet.html#method.par_symmetric_difference
/// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParSymmetricDifference<'a, T, S> {
- a: &'a HashSet<T, S>,
- b: &'a HashSet<T, S>,
+pub struct ParSymmetricDifference<'a, T, S, A: Allocator + Clone = Global> {
+ a: &'a HashSet<T, S, A>,
+ b: &'a HashSet<T, S, A>,
}
-impl<'a, T, S> ParallelIterator for ParSymmetricDifference<'a, T, S>
+impl<'a, T, S, A> ParallelIterator for ParSymmetricDifference<'a, T, S, A>
where
T: Eq + Hash + Sync,
S: BuildHasher + Sync,
+ A: Allocator + Clone + Sync,
{
type Item = &'a T;
@@ -154,15 +150,16 @@
///
/// [`par_intersection`]: /hashbrown/struct.HashSet.html#method.par_intersection
/// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParIntersection<'a, T, S> {
- a: &'a HashSet<T, S>,
- b: &'a HashSet<T, S>,
+pub struct ParIntersection<'a, T, S, A: Allocator + Clone = Global> {
+ a: &'a HashSet<T, S, A>,
+ b: &'a HashSet<T, S, A>,
}
-impl<'a, T, S> ParallelIterator for ParIntersection<'a, T, S>
+impl<'a, T, S, A> ParallelIterator for ParIntersection<'a, T, S, A>
where
T: Eq + Hash + Sync,
S: BuildHasher + Sync,
+ A: Allocator + Clone + Sync,
{
type Item = &'a T;
@@ -184,15 +181,16 @@
///
/// [`par_union`]: /hashbrown/struct.HashSet.html#method.par_union
/// [`HashSet`]: /hashbrown/struct.HashSet.html
-pub struct ParUnion<'a, T, S> {
- a: &'a HashSet<T, S>,
- b: &'a HashSet<T, S>,
+pub struct ParUnion<'a, T, S, A: Allocator + Clone = Global> {
+ a: &'a HashSet<T, S, A>,
+ b: &'a HashSet<T, S, A>,
}
-impl<'a, T, S> ParallelIterator for ParUnion<'a, T, S>
+impl<'a, T, S, A> ParallelIterator for ParUnion<'a, T, S, A>
where
T: Eq + Hash + Sync,
S: BuildHasher + Sync,
+ A: Allocator + Clone + Sync,
{
type Item = &'a T;
@@ -200,22 +198,37 @@
where
C: UnindexedConsumer<Self::Item>,
{
- self.a
+ // We'll iterate one set in full, and only the remaining difference from the other.
+ // Use the smaller set for the difference in order to reduce hash lookups.
+ let (smaller, larger) = if self.a.len() <= self.b.len() {
+ (self.a, self.b)
+ } else {
+ (self.b, self.a)
+ };
+ larger
.into_par_iter()
- .chain(self.b.par_difference(self.a))
+ .chain(smaller.par_difference(larger))
.drive_unindexed(consumer)
}
}
-impl<T, S> HashSet<T, S>
+impl<T, S, A> HashSet<T, S, A>
where
T: Eq + Hash + Sync,
S: BuildHasher + Sync,
+ A: Allocator + Clone + Sync,
{
+ /// Visits (potentially in parallel) the values representing the union,
+ /// i.e. all the values in `self` or `other`, without duplicates.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn par_union<'a>(&'a self, other: &'a Self) -> ParUnion<'a, T, S, A> {
+ ParUnion { a: self, b: other }
+ }
+
/// Visits (potentially in parallel) the values representing the difference,
/// i.e. the values that are in `self` but not in `other`.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_difference<'a>(&'a self, other: &'a Self) -> ParDifference<'a, T, S> {
+ pub fn par_difference<'a>(&'a self, other: &'a Self) -> ParDifference<'a, T, S, A> {
ParDifference { a: self, b: other }
}
@@ -225,24 +238,17 @@
pub fn par_symmetric_difference<'a>(
&'a self,
other: &'a Self,
- ) -> ParSymmetricDifference<'a, T, S> {
+ ) -> ParSymmetricDifference<'a, T, S, A> {
ParSymmetricDifference { a: self, b: other }
}
/// Visits (potentially in parallel) the values representing the
/// intersection, i.e. the values that are both in `self` and `other`.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_intersection<'a>(&'a self, other: &'a Self) -> ParIntersection<'a, T, S> {
+ pub fn par_intersection<'a>(&'a self, other: &'a Self) -> ParIntersection<'a, T, S, A> {
ParIntersection { a: self, b: other }
}
- /// Visits (potentially in parallel) the values representing the union,
- /// i.e. all the values in `self` or `other`, without duplicates.
- #[cfg_attr(feature = "inline-more", inline)]
- pub fn par_union<'a>(&'a self, other: &'a Self) -> ParUnion<'a, T, S> {
- ParUnion { a: self, b: other }
- }
-
/// Returns `true` if `self` has no elements in common with `other`.
/// This is equivalent to checking for an empty intersection.
///
@@ -280,41 +286,47 @@
}
}
-impl<T, S> HashSet<T, S>
+impl<T, S, A> HashSet<T, S, A>
where
T: Eq + Hash + Send,
- S: BuildHasher + Send,
+ A: Allocator + Clone + Send,
{
/// Consumes (potentially in parallel) all values in an arbitrary order,
/// while preserving the set's allocated memory for reuse.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn par_drain(&mut self) -> ParDrain<'_, T, S> {
- ParDrain { set: self }
+ pub fn par_drain(&mut self) -> ParDrain<'_, T, A> {
+ ParDrain {
+ inner: self.map.par_drain(),
+ }
}
}
-impl<T: Send, S: Send> IntoParallelIterator for HashSet<T, S> {
+impl<T: Send, S, A: Allocator + Clone + Send> IntoParallelIterator for HashSet<T, S, A> {
type Item = T;
- type Iter = IntoParIter<T, S>;
+ type Iter = IntoParIter<T, A>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_par_iter(self) -> Self::Iter {
- IntoParIter { set: self }
+ IntoParIter {
+ inner: self.map.into_par_iter(),
+ }
}
}
-impl<'a, T: Sync, S: Sync> IntoParallelIterator for &'a HashSet<T, S> {
+impl<'a, T: Sync, S, A: Allocator + Clone> IntoParallelIterator for &'a HashSet<T, S, A> {
type Item = &'a T;
- type Iter = ParIter<'a, T, S>;
+ type Iter = ParIter<'a, T>;
#[cfg_attr(feature = "inline-more", inline)]
fn into_par_iter(self) -> Self::Iter {
- ParIter { set: self }
+ ParIter {
+ inner: self.map.par_keys(),
+ }
}
}
/// Collect values from a parallel iterator into a hashset.
-impl<T, S> FromParallelIterator<T> for HashSet<T, S>
+impl<T, S> FromParallelIterator<T> for HashSet<T, S, Global>
where
T: Eq + Hash + Send,
S: BuildHasher + Default,
@@ -330,7 +342,7 @@
}
/// Extend a hash set with items from a parallel iterator.
-impl<T, S> ParallelExtend<T> for HashSet<T, S>
+impl<T, S> ParallelExtend<T> for HashSet<T, S, Global>
where
T: Eq + Hash + Send,
S: BuildHasher,
@@ -344,7 +356,7 @@
}
/// Extend a hash set with copied items from a parallel iterator.
-impl<'a, T, S> ParallelExtend<&'a T> for HashSet<T, S>
+impl<'a, T, S> ParallelExtend<&'a T> for HashSet<T, S, Global>
where
T: 'a + Copy + Eq + Hash + Sync,
S: BuildHasher,
@@ -358,12 +370,13 @@
}
// This is equal to the normal `HashSet` -- no custom advantage.
-fn extend<T, S, I>(set: &mut HashSet<T, S>, par_iter: I)
+fn extend<T, S, I, A>(set: &mut HashSet<T, S, A>, par_iter: I)
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
I: IntoParallelIterator,
- HashSet<T, S>: Extend<I::Item>,
+ HashSet<T, S, A>: Extend<I::Item>,
{
let (list, len) = super::helpers::collect(par_iter);
diff --git a/src/lib.rs b/src/lib.rs
index 3aff40a..b2d6584 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -12,13 +12,25 @@
#![no_std]
#![cfg_attr(
feature = "nightly",
- feature(test, core_intrinsics, dropck_eyepatch, min_specialization, extend_one)
+ feature(
+ test,
+ core_intrinsics,
+ dropck_eyepatch,
+ min_specialization,
+ extend_one,
+ allocator_api,
+ slice_ptr_get,
+ nonnull_slice_from_raw_parts,
+ maybe_uninit_array_assume_init
+ )
)]
#![allow(
clippy::doc_markdown,
clippy::module_name_repetitions,
clippy::must_use_candidate,
- clippy::option_if_let_else
+ clippy::option_if_let_else,
+ clippy::redundant_else,
+ clippy::manual_map
)]
#![warn(missing_docs)]
#![warn(rust_2018_idioms)]
@@ -48,6 +60,11 @@
pub use inner::*;
#[cfg(feature = "rayon")]
+ /// [rayon]-based parallel iterator types for hash maps.
+ /// You will rarely need to interact with it directly unless you have need
+ /// to name one of the iterator types.
+ ///
+ /// [rayon]: https://docs.rs/rayon/1.0/rayon
pub mod rayon {
pub use crate::external_trait_impls::rayon::raw::*;
}
@@ -110,3 +127,35 @@
layout: alloc::alloc::Layout,
},
}
+
+/// The error type for [`RawTable::get_each_mut`](crate::raw::RawTable::get_each_mut),
+/// [`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`.
+///
+/// `Bump` can be used directly without this wrapper on nightly if you enable
+/// the `allocator-api` feature of the `bumpalo` crate.
+#[cfg(feature = "bumpalo")]
+#[derive(Clone, Copy, Debug)]
+pub struct BumpWrapper<'a>(pub &'a bumpalo::Bump);
+
+#[cfg(feature = "bumpalo")]
+#[test]
+fn test_bumpalo() {
+ use bumpalo::Bump;
+ let bump = Bump::new();
+ let mut map = HashMap::new_in(BumpWrapper(&bump));
+ map.insert(0, 1);
+}
diff --git a/src/map.rs b/src/map.rs
index 1ccba31..ab11288 100644
--- a/src/map.rs
+++ b/src/map.rs
@@ -1,11 +1,15 @@
-use crate::raw::{Bucket, RawDrain, RawIntoIter, RawIter, RawTable};
+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, Hasher};
+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`.
@@ -185,12 +189,12 @@
/// .iter().cloned().collect();
/// // use the values stored in map
/// ```
-pub struct HashMap<K, V, S = DefaultHashBuilder> {
+pub struct HashMap<K, V, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
pub(crate) hash_builder: S,
- pub(crate) table: RawTable<(K, V)>,
+ pub(crate) table: RawTable<(K, V), A>,
}
-impl<K: Clone, V: Clone, S: Clone> Clone for HashMap<K, V, S> {
+impl<K: Clone, V: Clone, S: Clone, A: Allocator + Clone> Clone for HashMap<K, V, S, A> {
fn clone(&self) -> Self {
HashMap {
hash_builder: self.hash_builder.clone(),
@@ -206,8 +210,60 @@
}
}
+/// Ensures that a single closure type across uses of this which, in turn prevents multiple
+/// instances of any functions like RawTable::reserve from being generated
#[cfg_attr(feature = "inline-more", inline)]
-pub(crate) fn make_hash<K: Hash + ?Sized>(hash_builder: &impl BuildHasher, val: &K) -> u64 {
+pub(crate) fn make_hasher<K, Q, V, S>(hash_builder: &S) -> impl Fn(&(Q, V)) -> u64 + '_
+where
+ K: Borrow<Q>,
+ Q: Hash,
+ S: BuildHasher,
+{
+ move |val| make_hash::<K, Q, S>(hash_builder, &val.0)
+}
+
+/// Ensures that a single closure type across uses of this which, in turn prevents multiple
+/// instances of any functions like RawTable::reserve from being generated
+#[cfg_attr(feature = "inline-more", inline)]
+fn equivalent_key<Q, K, V>(k: &Q) -> impl Fn(&(K, V)) -> bool + '_
+where
+ K: Borrow<Q>,
+ Q: ?Sized + Eq,
+{
+ move |x| k.eq(x.0.borrow())
+}
+
+/// Ensures that a single closure type across uses of this which, in turn prevents multiple
+/// instances of any functions like RawTable::reserve from being generated
+#[cfg_attr(feature = "inline-more", inline)]
+fn equivalent<Q, K>(k: &Q) -> impl Fn(&K) -> bool + '_
+where
+ K: Borrow<Q>,
+ Q: ?Sized + Eq,
+{
+ move |x| k.eq(x.borrow())
+}
+
+#[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,
+{
+ use core::hash::Hasher;
+ let mut state = hash_builder.build_hasher();
+ val.hash(&mut state);
+ state.finish()
+}
+
+#[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,
+{
+ use core::hash::Hasher;
let mut state = hash_builder.build_hasher();
val.hash(&mut state);
state.finish()
@@ -248,6 +304,27 @@
}
}
+#[cfg(feature = "ahash")]
+impl<K, V, A: Allocator + Clone> HashMap<K, V, DefaultHashBuilder, A> {
+ /// Creates an empty `HashMap` using the given allocator.
+ ///
+ /// The hash map is initially created with a capacity of 0, so it will not allocate until it
+ /// is first inserted into.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn new_in(alloc: A) -> Self {
+ Self::with_hasher_in(DefaultHashBuilder::default(), alloc)
+ }
+
+ /// Creates an empty `HashMap` with the specified capacity using the given allocator.
+ ///
+ /// The hash map will be able to hold at least `capacity` elements without
+ /// reallocating. If `capacity` is 0, the hash map will not allocate.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
+ Self::with_capacity_and_hasher_in(capacity, DefaultHashBuilder::default(), alloc)
+ }
+}
+
impl<K, V, S> HashMap<K, V, S> {
/// Creates an empty `HashMap` which will use the given hash builder to hash
/// keys.
@@ -315,6 +392,65 @@
table: RawTable::with_capacity(capacity),
}
}
+}
+
+impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> {
+ /// Creates an empty `HashMap` which will use the given hash builder to hash
+ /// keys. It will be allocated with the given allocator.
+ ///
+ /// The created map has the default initial capacity.
+ ///
+ /// Warning: `hash_builder` is normally randomly generated, and
+ /// is designed to allow HashMaps to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut map = HashMap::with_hasher(s);
+ /// map.insert(1, 2);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_hasher_in(hash_builder: S, alloc: A) -> Self {
+ Self {
+ hash_builder,
+ table: RawTable::new_in(alloc),
+ }
+ }
+
+ /// Creates an empty `HashMap` with the specified capacity, using `hash_builder`
+ /// to hash the keys. It will be allocated with the given allocator.
+ ///
+ /// The hash map will be able to hold at least `capacity` elements without
+ /// reallocating. If `capacity` is 0, the hash map will not allocate.
+ ///
+ /// Warning: `hash_builder` is normally randomly generated, and
+ /// is designed to allow HashMaps to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut map = HashMap::with_capacity_and_hasher(10, s);
+ /// map.insert(1, 2);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_capacity_and_hasher_in(capacity: usize, hash_builder: S, alloc: A) -> Self {
+ Self {
+ hash_builder,
+ table: RawTable::with_capacity_in(capacity, alloc),
+ }
+ }
/// Returns a reference to the map's [`BuildHasher`].
///
@@ -547,7 +683,7 @@
/// assert!(a.is_empty());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn drain(&mut self) -> Drain<'_, K, V> {
+ pub fn drain(&mut self) -> Drain<'_, K, V, A> {
Drain {
inner: self.table.drain(),
}
@@ -607,7 +743,7 @@
/// assert_eq!(odds, vec![1, 3, 5, 7]);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, K, V, F>
+ pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, K, V, F, A>
where
F: FnMut(&K, &mut V) -> bool,
{
@@ -639,10 +775,11 @@
}
}
-impl<K, V, S> HashMap<K, V, S>
+impl<K, V, S, A> HashMap<K, V, S, A>
where
K: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
/// Reserves capacity for at least `additional` more elements to be inserted
/// in the `HashMap`. The collection may reserve more space to avoid
@@ -663,9 +800,8 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn reserve(&mut self, additional: usize) {
- let hash_builder = &self.hash_builder;
self.table
- .reserve(additional, |x| make_hash(hash_builder, &x.0));
+ .reserve(additional, make_hasher::<K, _, V, S>(&self.hash_builder));
}
/// Tries to reserve capacity for at least `additional` more elements to be inserted
@@ -686,9 +822,8 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
- let hash_builder = &self.hash_builder;
self.table
- .try_reserve(additional, |x| make_hash(hash_builder, &x.0))
+ .try_reserve(additional, make_hasher::<K, _, V, S>(&self.hash_builder))
}
/// Shrinks the capacity of the map as much as possible. It will drop
@@ -709,8 +844,8 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn shrink_to_fit(&mut self) {
- let hash_builder = &self.hash_builder;
- self.table.shrink_to(0, |x| make_hash(hash_builder, &x.0));
+ self.table
+ .shrink_to(0, make_hasher::<K, _, V, S>(&self.hash_builder));
}
/// Shrinks the capacity of the map with a lower limit. It will drop
@@ -738,9 +873,8 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn shrink_to(&mut self, min_capacity: usize) {
- let hash_builder = &self.hash_builder;
self.table
- .shrink_to(min_capacity, |x| make_hash(hash_builder, &x.0));
+ .shrink_to(min_capacity, make_hasher::<K, _, V, S>(&self.hash_builder));
}
/// Gets the given key's corresponding entry in the map for in-place manipulation.
@@ -763,9 +897,9 @@
/// assert_eq!(letters.get(&'y'), None);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S> {
- let hash = make_hash(&self.hash_builder, &key);
- if let Some(elem) = self.table.find(hash, |q| q.0.eq(&key)) {
+ pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S, A> {
+ let hash = make_insert_hash::<K, S>(&self.hash_builder, &key);
+ if let Some(elem) = self.table.find(hash, equivalent_key(&key)) {
Entry::Occupied(OccupiedEntry {
hash,
key: Some(key),
@@ -851,8 +985,8 @@
K: Borrow<Q>,
Q: Hash + Eq,
{
- let hash = make_hash(&self.hash_builder, k);
- self.table.get(hash, |x| k.eq(x.0.borrow()))
+ 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.
@@ -959,8 +1093,143 @@
K: Borrow<Q>,
Q: Hash + Eq,
{
- let hash = make_hash(&self.hash_builder, k);
- self.table.get_mut(hash, |x| k.eq(x.0.borrow()))
+ 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. 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, UnavailableMutError};
+ ///
+ /// 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_each_mut([
+ /// "Athenæum",
+ /// "New York Public Library",
+ /// "Athenæum",
+ /// "Library of Congress",
+ /// ]);
+ /// assert_eq!(
+ /// got,
+ /// [
+ /// Ok(&mut 1807),
+ /// Err(UnavailableMutError::Absent),
+ /// Err(UnavailableMutError::Duplicate(0)),
+ /// Ok(&mut 1800),
+ /// ]
+ /// );
+ /// ```
+ #[cfg(feature = "nightly")]
+ pub fn get_each_mut<Q: ?Sized, const N: usize>(
+ &mut self,
+ ks: [&Q; N],
+ ) -> [Result<&'_ mut V, UnavailableMutError>; N]
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ 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. 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, UnavailableMutError};
+ ///
+ /// 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_each_key_value_mut([
+ /// "Bodleian Library",
+ /// "Herzogin-Anna-Amalia-Bibliothek",
+ /// "Herzogin-Anna-Amalia-Bibliothek",
+ /// "Gewandhaus",
+ /// ]);
+ /// assert_eq!(
+ /// got,
+ /// [
+ /// Ok((&"Bodleian Library".to_string(), &mut 1602)),
+ /// Ok((&"Herzogin-Anna-Amalia-Bibliothek".to_string(), &mut 1691)),
+ /// Err(UnavailableMutError::Duplicate(1)),
+ /// Err(UnavailableMutError::Absent),
+ /// ]
+ /// );
+ /// ```
+ #[cfg(feature = "nightly")]
+ pub fn get_each_key_value_mut<Q: ?Sized, const N: usize>(
+ &mut self,
+ ks: [&Q; N],
+ ) -> [Result<(&'_ K, &'_ mut V), UnavailableMutError>; N]
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ 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) }
+ }
+
+ #[cfg(feature = "nightly")]
+ fn get_each_inner_mut<Q: ?Sized, const N: usize>(
+ &mut self,
+ ks: [&Q; N],
+ ) -> [Result<&'_ mut (K, V), UnavailableMutError>; N]
+ where
+ K: Borrow<Q>,
+ Q: Hash + Eq,
+ {
+ let mut hashes = [0_u64; N];
+ for i in 0..N {
+ hashes[i] = make_hash::<K, Q, S>(&self.hash_builder, ks[i]);
+ }
+ self.table
+ .get_each_mut(hashes, |i, (k, _)| ks[i].eq(k.borrow()))
}
/// Inserts a key-value pair into the map.
@@ -990,17 +1259,51 @@
/// ```
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert(&mut self, k: K, v: V) -> Option<V> {
- let hash = make_hash(&self.hash_builder, &k);
- if let Some((_, item)) = self.table.get_mut(hash, |x| k.eq(&x.0)) {
+ let hash = make_insert_hash::<K, S>(&self.hash_builder, &k);
+ if let Some((_, item)) = self.table.get_mut(hash, equivalent_key(&k)) {
Some(mem::replace(item, v))
} else {
- let hash_builder = &self.hash_builder;
self.table
- .insert(hash, (k, v), |x| make_hash(hash_builder, &x.0));
+ .insert(hash, (k, v), make_hasher::<K, _, V, S>(&self.hash_builder));
None
}
}
+ /// Tries to insert a key-value pair into the map, and returns
+ /// a mutable reference to the value in the entry.
+ ///
+ /// # Errors
+ ///
+ /// If the map already had this key present, nothing is updated, and
+ /// an error containing the occupied entry and the value is returned.
+ ///
+ /// # Examples
+ ///
+ /// Basic usage:
+ ///
+ /// ```
+ /// use hashbrown::HashMap;
+ ///
+ /// let mut map = HashMap::new();
+ /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
+ ///
+ /// let err = map.try_insert(37, "b").unwrap_err();
+ /// assert_eq!(err.entry.key(), &37);
+ /// assert_eq!(err.entry.get(), &"a");
+ /// assert_eq!(err.value, "b");
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn try_insert(
+ &mut self,
+ key: K,
+ value: V,
+ ) -> Result<&mut V, OccupiedError<'_, K, V, S, A>> {
+ match self.entry(key) {
+ Entry::Occupied(entry) => Err(OccupiedError { entry, value }),
+ Entry::Vacant(entry) => Ok(entry.insert(value)),
+ }
+ }
+
/// Removes a key from the map, returning the value at the key if the key
/// was previously in the map.
///
@@ -1060,12 +1363,12 @@
K: Borrow<Q>,
Q: Hash + Eq,
{
- let hash = make_hash(&self.hash_builder, &k);
- self.table.remove_entry(hash, |x| k.eq(x.0.borrow()))
+ let hash = make_hash::<K, Q, S>(&self.hash_builder, k);
+ self.table.remove_entry(hash, equivalent_key(k))
}
}
-impl<K, V, S> HashMap<K, V, S> {
+impl<K, V, S, A: Allocator + Clone> HashMap<K, V, S, A> {
/// Creates a raw entry builder for the HashMap.
///
/// Raw entries provide the lowest level of control for searching and
@@ -1098,7 +1401,7 @@
/// acting erratically, with two keys randomly masking each other. Implementations
/// are free to assume this doesn't happen (within the limits of memory-safety).
#[cfg_attr(feature = "inline-more", inline)]
- pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
+ pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S, A> {
RawEntryBuilderMut { map: self }
}
@@ -1118,16 +1421,17 @@
///
/// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
+ pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S, A> {
RawEntryBuilder { map: self }
}
}
-impl<K, V, S> PartialEq for HashMap<K, V, S>
+impl<K, V, S, A> PartialEq for HashMap<K, V, S, A>
where
K: Eq + Hash,
V: PartialEq,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn eq(&self, other: &Self) -> bool {
if self.len() != other.len() {
@@ -1139,40 +1443,44 @@
}
}
-impl<K, V, S> Eq for HashMap<K, V, S>
+impl<K, V, S, A> Eq for HashMap<K, V, S, A>
where
K: Eq + Hash,
V: Eq,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<K, V, S> Debug for HashMap<K, V, S>
+impl<K, V, S, A> Debug for HashMap<K, V, S, A>
where
K: Debug,
V: Debug,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
-impl<K, V, S> Default for HashMap<K, V, S>
+impl<K, V, S, A> Default for HashMap<K, V, S, A>
where
S: Default,
+ A: Default + Allocator + Clone,
{
- /// Creates an empty `HashMap<K, V, S>`, with the `Default` value for the hasher.
+ /// Creates an empty `HashMap<K, V, S, A>`, with the `Default` value for the hasher and allocator.
#[cfg_attr(feature = "inline-more", inline)]
fn default() -> Self {
- Self::with_hasher(Default::default())
+ Self::with_hasher_in(Default::default(), Default::default())
}
}
-impl<K, Q: ?Sized, V, S> Index<&Q> for HashMap<K, V, S>
+impl<K, Q: ?Sized, V, S, A> Index<&Q> for HashMap<K, V, S, A>
where
K: Eq + Hash + Borrow<Q>,
Q: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Output = V;
@@ -1252,11 +1560,11 @@
///
/// [`into_iter`]: struct.HashMap.html#method.into_iter
/// [`HashMap`]: struct.HashMap.html
-pub struct IntoIter<K, V> {
- inner: RawIntoIter<(K, V)>,
+pub struct IntoIter<K, V, A: Allocator + Clone = Global> {
+ inner: RawIntoIter<(K, V), A>,
}
-impl<K, V> IntoIter<K, V> {
+impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> {
/// Returns a iterator of references over the remaining items.
#[cfg_attr(feature = "inline-more", inline)]
pub(super) fn iter(&self) -> Iter<'_, K, V> {
@@ -1328,11 +1636,11 @@
///
/// [`drain`]: struct.HashMap.html#method.drain
/// [`HashMap`]: struct.HashMap.html
-pub struct Drain<'a, K, V> {
- inner: RawDrain<'a, (K, V)>,
+pub struct Drain<'a, K, V, A: Allocator + Clone = Global> {
+ inner: RawDrain<'a, (K, V), A>,
}
-impl<K, V> Drain<'_, K, V> {
+impl<K, V, A: Allocator + Clone> Drain<'_, K, V, A> {
/// Returns a iterator of references over the remaining items.
#[cfg_attr(feature = "inline-more", inline)]
pub(super) fn iter(&self) -> Iter<'_, K, V> {
@@ -1350,17 +1658,18 @@
///
/// [`drain_filter`]: struct.HashMap.html#method.drain_filter
/// [`HashMap`]: struct.HashMap.html
-pub struct DrainFilter<'a, K, V, F>
+pub struct DrainFilter<'a, K, V, F, A: Allocator + Clone = Global>
where
F: FnMut(&K, &mut V) -> bool,
{
f: F,
- inner: DrainFilterInner<'a, K, V>,
+ inner: DrainFilterInner<'a, K, V, A>,
}
-impl<'a, K, V, F> Drop for DrainFilter<'a, K, V, F>
+impl<'a, K, V, F, A> Drop for DrainFilter<'a, K, V, F, A>
where
F: FnMut(&K, &mut V) -> bool,
+ A: Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
@@ -1381,9 +1690,10 @@
}
}
-impl<K, V, F> Iterator for DrainFilter<'_, K, V, F>
+impl<K, V, F, A> Iterator for DrainFilter<'_, K, V, F, A>
where
F: FnMut(&K, &mut V) -> bool,
+ A: Allocator + Clone,
{
type Item = (K, V);
@@ -1401,12 +1711,12 @@
impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
/// Portions of `DrainFilter` shared with `set::DrainFilter`
-pub(super) struct DrainFilterInner<'a, K, V> {
+pub(super) struct DrainFilterInner<'a, K, V, A: Allocator + Clone> {
pub iter: RawIter<(K, V)>,
- pub table: &'a mut RawTable<(K, V)>,
+ pub table: &'a mut RawTable<(K, V), A>,
}
-impl<K, V> DrainFilterInner<'_, K, V> {
+impl<K, V, A: Allocator + Clone> DrainFilterInner<'_, K, V, A> {
#[cfg_attr(feature = "inline-more", inline)]
pub(super) fn next<F>(&mut self, f: &mut F) -> Option<(K, V)>
where
@@ -1440,8 +1750,8 @@
/// See the [`HashMap::raw_entry_mut`] docs for usage examples.
///
/// [`HashMap::raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
-pub struct RawEntryBuilderMut<'a, K, V, S> {
- map: &'a mut HashMap<K, V, S>,
+pub struct RawEntryBuilderMut<'a, K, V, S, A: Allocator + Clone = Global> {
+ map: &'a mut HashMap<K, V, S, A>,
}
/// A view into a single entry in a map, which may either be vacant or occupied.
@@ -1455,35 +1765,35 @@
/// [`Entry`]: enum.Entry.html
/// [`raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut
/// [`RawEntryBuilderMut`]: struct.RawEntryBuilderMut.html
-pub enum RawEntryMut<'a, K, V, S> {
+pub enum RawEntryMut<'a, K, V, S, A: Allocator + Clone = Global> {
/// An occupied entry.
- Occupied(RawOccupiedEntryMut<'a, K, V, S>),
+ Occupied(RawOccupiedEntryMut<'a, K, V, S, A>),
/// A vacant entry.
- Vacant(RawVacantEntryMut<'a, K, V, S>),
+ Vacant(RawVacantEntryMut<'a, K, V, S, A>),
}
/// A view into an occupied entry in a `HashMap`.
/// It is part of the [`RawEntryMut`] enum.
///
/// [`RawEntryMut`]: enum.RawEntryMut.html
-pub struct RawOccupiedEntryMut<'a, K, V, S> {
+pub struct RawOccupiedEntryMut<'a, K, V, S, A: Allocator + Clone = Global> {
elem: Bucket<(K, V)>,
- table: &'a mut RawTable<(K, V)>,
+ table: &'a mut RawTable<(K, V), A>,
hash_builder: &'a S,
}
-unsafe impl<K, V, S> Send for RawOccupiedEntryMut<'_, K, V, S>
+unsafe impl<K, V, S, A> Send for RawOccupiedEntryMut<'_, K, V, S, A>
where
K: Send,
V: Send,
- S: Sync,
+ A: Send + Allocator + Clone,
{
}
-unsafe impl<K, V, S> Sync for RawOccupiedEntryMut<'_, K, V, S>
+unsafe impl<K, V, S, A> Sync for RawOccupiedEntryMut<'_, K, V, S, A>
where
K: Sync,
V: Sync,
- S: Sync,
+ A: Send + Allocator + Clone,
{
}
@@ -1491,8 +1801,8 @@
/// It is part of the [`RawEntryMut`] enum.
///
/// [`RawEntryMut`]: enum.RawEntryMut.html
-pub struct RawVacantEntryMut<'a, K, V, S> {
- table: &'a mut RawTable<(K, V)>,
+pub struct RawVacantEntryMut<'a, K, V, S, A: Allocator + Clone = Global> {
+ table: &'a mut RawTable<(K, V), A>,
hash_builder: &'a S,
}
@@ -1501,42 +1811,41 @@
/// See the [`HashMap::raw_entry`] docs for usage examples.
///
/// [`HashMap::raw_entry`]: struct.HashMap.html#method.raw_entry
-pub struct RawEntryBuilder<'a, K, V, S> {
- map: &'a HashMap<K, V, S>,
+pub struct RawEntryBuilder<'a, K, V, S, A: Allocator + Clone = Global> {
+ map: &'a HashMap<K, V, S, A>,
}
-impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> {
/// Creates a `RawEntryMut` from the given key.
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
- pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S>
+ pub fn from_key<Q: ?Sized>(self, k: &Q) -> RawEntryMut<'a, K, V, S, A>
where
S: BuildHasher,
K: Borrow<Q>,
Q: Hash + Eq,
{
- let mut hasher = self.map.hash_builder.build_hasher();
- k.hash(&mut hasher);
- self.from_key_hashed_nocheck(hasher.finish(), k)
+ let hash = make_hash::<K, Q, S>(&self.map.hash_builder, k);
+ self.from_key_hashed_nocheck(hash, k)
}
/// Creates a `RawEntryMut` from the given key and its hash.
#[inline]
#[allow(clippy::wrong_self_convention)]
- pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S>
+ pub fn from_key_hashed_nocheck<Q: ?Sized>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S, A>
where
K: Borrow<Q>,
Q: Eq,
{
- self.from_hash(hash, |q| q.borrow().eq(k))
+ self.from_hash(hash, equivalent(k))
}
}
-impl<'a, K, V, S> RawEntryBuilderMut<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilderMut<'a, K, V, S, A> {
/// Creates a `RawEntryMut` from the given hash.
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
- pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S>
+ pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S, A>
where
for<'b> F: FnMut(&'b K) -> bool,
{
@@ -1544,7 +1853,7 @@
}
#[cfg_attr(feature = "inline-more", inline)]
- fn search<F>(self, hash: u64, mut is_match: F) -> RawEntryMut<'a, K, V, S>
+ fn search<F>(self, hash: u64, mut is_match: F) -> RawEntryMut<'a, K, V, S, A>
where
for<'b> F: FnMut(&'b K) -> bool,
{
@@ -1562,7 +1871,7 @@
}
}
-impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> RawEntryBuilder<'a, K, V, S, A> {
/// Access an entry by key.
#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::wrong_self_convention)]
@@ -1572,9 +1881,8 @@
K: Borrow<Q>,
Q: Hash + Eq,
{
- let mut hasher = self.map.hash_builder.build_hasher();
- k.hash(&mut hasher);
- self.from_key_hashed_nocheck(hasher.finish(), k)
+ let hash = make_hash::<K, Q, S>(&self.map.hash_builder, k);
+ self.from_key_hashed_nocheck(hash, k)
}
/// Access an entry by a key and its hash.
@@ -1585,7 +1893,7 @@
K: Borrow<Q>,
Q: Eq,
{
- self.from_hash(hash, |q| q.borrow().eq(k))
+ self.from_hash(hash, equivalent(k))
}
#[cfg_attr(feature = "inline-more", inline)]
@@ -1610,7 +1918,7 @@
}
}
-impl<'a, K, V, S> RawEntryMut<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> RawEntryMut<'a, K, V, S, A> {
/// Sets the value of the entry, and returns a RawOccupiedEntryMut.
///
/// # Examples
@@ -1624,7 +1932,7 @@
/// assert_eq!(entry.remove_entry(), ("horseyland", 37));
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S>
+ pub fn insert(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A>
where
K: Hash,
S: BuildHasher,
@@ -1804,7 +2112,7 @@
}
}
-impl<'a, K, V, S> RawOccupiedEntryMut<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> RawOccupiedEntryMut<'a, K, V, S, A> {
/// Gets a reference to the key in the entry.
#[cfg_attr(feature = "inline-more", inline)]
pub fn key(&self) -> &K {
@@ -1899,7 +2207,7 @@
/// the entry and allows to replace or remove it based on the
/// value of the returned option.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn replace_entry_with<F>(self, f: F) -> RawEntryMut<'a, K, V, S>
+ pub fn replace_entry_with<F>(self, f: F) -> RawEntryMut<'a, K, V, S, A>
where
F: FnOnce(&K, V) -> Option<V>,
{
@@ -1922,7 +2230,7 @@
}
}
-impl<'a, K, V, S> RawVacantEntryMut<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> RawVacantEntryMut<'a, K, V, S, A> {
/// Sets the value of the entry with the VacantEntry's key,
/// and returns a mutable reference to it.
#[cfg_attr(feature = "inline-more", inline)]
@@ -1931,9 +2239,8 @@
K: Hash,
S: BuildHasher,
{
- let mut hasher = self.hash_builder.build_hasher();
- key.hash(&mut hasher);
- self.insert_hashed_nocheck(hasher.finish(), key, value)
+ let hash = make_insert_hash::<K, S>(self.hash_builder, &key);
+ self.insert_hashed_nocheck(hash, key, value)
}
/// Sets the value of the entry with the VacantEntry's key,
@@ -1945,8 +2252,12 @@
K: Hash,
S: BuildHasher,
{
- let hash_builder = self.hash_builder;
- self.insert_with_hasher(hash, key, value, |k| make_hash(hash_builder, k))
+ let &mut (ref mut k, ref mut v) = self.table.insert_entry(
+ hash,
+ (key, value),
+ make_hasher::<K, _, V, S>(self.hash_builder),
+ );
+ (k, v)
}
/// Set the value of an entry with a custom hasher function.
@@ -1968,18 +2279,17 @@
}
#[cfg_attr(feature = "inline-more", inline)]
- fn insert_entry(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S>
+ fn insert_entry(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A>
where
K: Hash,
S: BuildHasher,
{
- let hash_builder = self.hash_builder;
- let mut hasher = self.hash_builder.build_hasher();
- key.hash(&mut hasher);
-
- let elem = self.table.insert(hasher.finish(), (key, value), |k| {
- make_hash(hash_builder, &k.0)
- });
+ let hash = make_insert_hash::<K, S>(self.hash_builder, &key);
+ let elem = self.table.insert(
+ hash,
+ (key, value),
+ make_hasher::<K, _, V, S>(self.hash_builder),
+ );
RawOccupiedEntryMut {
elem,
table: self.table,
@@ -1988,13 +2298,13 @@
}
}
-impl<K, V, S> Debug for RawEntryBuilderMut<'_, K, V, S> {
+impl<K, V, S, A: Allocator + Clone> Debug for RawEntryBuilderMut<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("RawEntryBuilder").finish()
}
}
-impl<K: Debug, V: Debug, S> Debug for RawEntryMut<'_, K, V, S> {
+impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for RawEntryMut<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match *self {
RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(),
@@ -2003,7 +2313,7 @@
}
}
-impl<K: Debug, V: Debug, S> Debug for RawOccupiedEntryMut<'_, K, V, S> {
+impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for RawOccupiedEntryMut<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("RawOccupiedEntryMut")
.field("key", self.key())
@@ -2012,13 +2322,13 @@
}
}
-impl<K, V, S> Debug for RawVacantEntryMut<'_, K, V, S> {
+impl<K, V, S, A: Allocator + Clone> Debug for RawVacantEntryMut<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("RawVacantEntryMut").finish()
}
}
-impl<K, V, S> Debug for RawEntryBuilder<'_, K, V, S> {
+impl<K, V, S, A: Allocator + Clone> Debug for RawEntryBuilder<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("RawEntryBuilder").finish()
}
@@ -2030,15 +2340,18 @@
///
/// [`HashMap`]: struct.HashMap.html
/// [`entry`]: struct.HashMap.html#method.entry
-pub enum Entry<'a, K, V, S> {
+pub enum Entry<'a, K, V, S, A = Global>
+where
+ A: Allocator + Clone,
+{
/// An occupied entry.
- Occupied(OccupiedEntry<'a, K, V, S>),
+ Occupied(OccupiedEntry<'a, K, V, S, A>),
/// A vacant entry.
- Vacant(VacantEntry<'a, K, V, S>),
+ Vacant(VacantEntry<'a, K, V, S, A>),
}
-impl<K: Debug, V: Debug, S> Debug for Entry<'_, K, V, S> {
+impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for Entry<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match *self {
Entry::Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
@@ -2051,29 +2364,31 @@
/// It is part of the [`Entry`] enum.
///
/// [`Entry`]: enum.Entry.html
-pub struct OccupiedEntry<'a, K, V, S> {
+pub struct OccupiedEntry<'a, K, V, S, A: Allocator + Clone = Global> {
hash: u64,
key: Option<K>,
elem: Bucket<(K, V)>,
- table: &'a mut HashMap<K, V, S>,
+ table: &'a mut HashMap<K, V, S, A>,
}
-unsafe impl<K, V, S> Send for OccupiedEntry<'_, K, V, S>
+unsafe impl<K, V, S, A> Send for OccupiedEntry<'_, K, V, S, A>
where
K: Send,
V: Send,
S: Send,
+ A: Send + Allocator + Clone,
{
}
-unsafe impl<K, V, S> Sync for OccupiedEntry<'_, K, V, S>
+unsafe impl<K, V, S, A> Sync for OccupiedEntry<'_, K, V, S, A>
where
K: Sync,
V: Sync,
S: Sync,
+ A: Sync + Allocator + Clone,
{
}
-impl<K: Debug, V: Debug, S> Debug for OccupiedEntry<'_, K, V, S> {
+impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for OccupiedEntry<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("OccupiedEntry")
.field("key", self.key())
@@ -2086,19 +2401,53 @@
/// It is part of the [`Entry`] enum.
///
/// [`Entry`]: enum.Entry.html
-pub struct VacantEntry<'a, K, V, S> {
+pub struct VacantEntry<'a, K, V, S, A: Allocator + Clone = Global> {
hash: u64,
key: K,
- table: &'a mut HashMap<K, V, S>,
+ table: &'a mut HashMap<K, V, S, A>,
}
-impl<K: Debug, V, S> Debug for VacantEntry<'_, K, V, S> {
+impl<K: Debug, V, S, A: Allocator + Clone> Debug for VacantEntry<'_, K, V, S, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("VacantEntry").field(self.key()).finish()
}
}
-impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> {
+/// 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.
+pub struct OccupiedError<'a, K, V, S, A: Allocator + Clone = Global> {
+ /// The entry in the map that was already occupied.
+ pub entry: OccupiedEntry<'a, K, V, S, A>,
+ /// The value which was not inserted, because the entry was already occupied.
+ pub value: V,
+}
+
+impl<K: Debug, V: Debug, S, A: Allocator + Clone> Debug for OccupiedError<'_, K, V, S, A> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_struct("OccupiedError")
+ .field("key", self.entry.key())
+ .field("old_value", self.entry.get())
+ .field("new_value", &self.value)
+ .finish()
+ }
+}
+
+impl<'a, K: Debug, V: Debug, S, A: Allocator + Clone> fmt::Display
+ for OccupiedError<'a, K, V, S, A>
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(
+ f,
+ "failed to insert {:?}, key {:?} already exists with value {:?}",
+ self.value,
+ self.entry.key(),
+ self.entry.get(),
+ )
+ }
+}
+
+impl<'a, K, V, S, A: Allocator + Clone> IntoIterator for &'a HashMap<K, V, S, A> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
@@ -2108,7 +2457,7 @@
}
}
-impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> IntoIterator for &'a mut HashMap<K, V, S, A> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V>;
@@ -2118,9 +2467,9 @@
}
}
-impl<K, V, S> IntoIterator for HashMap<K, V, S> {
+impl<K, V, S, A: Allocator + Clone> IntoIterator for HashMap<K, V, S, A> {
type Item = (K, V);
- type IntoIter = IntoIter<K, V>;
+ type IntoIter = IntoIter<K, V, A>;
/// Creates a consuming iterator, that is, one that moves each key-value
/// pair out of the map in arbitrary order. The map cannot be used after
@@ -2140,7 +2489,7 @@
/// let vec: Vec<(&str, i32)> = map.into_iter().collect();
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- fn into_iter(self) -> IntoIter<K, V> {
+ fn into_iter(self) -> IntoIter<K, V, A> {
IntoIter {
inner: self.table.into_iter(),
}
@@ -2212,7 +2561,7 @@
}
}
-impl<K, V> Iterator for IntoIter<K, V> {
+impl<K, V, A: Allocator + Clone> Iterator for IntoIter<K, V, A> {
type Item = (K, V);
#[cfg_attr(feature = "inline-more", inline)]
@@ -2224,15 +2573,15 @@
self.inner.size_hint()
}
}
-impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, V, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
-impl<K, V> FusedIterator for IntoIter<K, V> {}
+impl<K, V, A: Allocator + Clone> FusedIterator for IntoIter<K, V, A> {}
-impl<K: Debug, V: Debug> fmt::Debug for IntoIter<K, V> {
+impl<K: Debug, V: Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, V, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
@@ -2320,7 +2669,7 @@
}
}
-impl<'a, K, V> Iterator for Drain<'a, K, V> {
+impl<'a, K, V, A: Allocator + Clone> Iterator for Drain<'a, K, V, A> {
type Item = (K, V);
#[cfg_attr(feature = "inline-more", inline)]
@@ -2332,25 +2681,26 @@
self.inner.size_hint()
}
}
-impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
+impl<K, V, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, V, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.inner.len()
}
}
-impl<K, V> FusedIterator for Drain<'_, K, V> {}
+impl<K, V, A: Allocator + Clone> FusedIterator for Drain<'_, K, V, A> {}
-impl<K, V> fmt::Debug for Drain<'_, K, V>
+impl<K, V, A> fmt::Debug for Drain<'_, K, V, A>
where
K: fmt::Debug,
V: fmt::Debug,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
-impl<'a, K, V, S> Entry<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> Entry<'a, K, V, S, A> {
/// Sets the value of the entry, and returns an OccupiedEntry.
///
/// # Examples
@@ -2364,7 +2714,7 @@
/// assert_eq!(entry.key(), &"horseyland");
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V, S>
+ pub fn insert(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
where
K: Hash,
S: BuildHasher,
@@ -2433,9 +2783,12 @@
}
}
- /// Ensures a value is in the entry by inserting, if empty, the result of the default function,
- /// which takes the key as its argument, and returns a mutable reference to the value in the
- /// entry.
+ /// 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(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
///
@@ -2581,7 +2934,7 @@
}
}
-impl<'a, K, V: Default, S> Entry<'a, K, V, S> {
+impl<'a, K, V: Default, S, A: Allocator + Clone> Entry<'a, K, 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.
///
@@ -2608,7 +2961,7 @@
}
}
-impl<'a, K, V, S> OccupiedEntry<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> OccupiedEntry<'a, K, V, S, A> {
/// Gets a reference to the key in the entry.
///
/// # Examples
@@ -2777,6 +3130,10 @@
/// 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 [`Entry::insert`].
+ ///
/// # Examples
///
/// ```
@@ -2806,6 +3163,10 @@
/// 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
///
/// ```
@@ -2883,7 +3244,7 @@
/// assert!(!map.contains_key("poneyland"));
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn replace_entry_with<F>(self, f: F) -> Entry<'a, K, V, S>
+ pub fn replace_entry_with<F>(self, f: F) -> Entry<'a, K, V, S, A>
where
F: FnOnce(&K, V) -> Option<V>,
{
@@ -2914,7 +3275,7 @@
}
}
-impl<'a, K, V, S> VacantEntry<'a, K, V, S> {
+impl<'a, K, V, S, A: Allocator + Clone> VacantEntry<'a, K, V, S, A> {
/// Gets a reference to the key that would be used when inserting a value
/// through the `VacantEntry`.
///
@@ -2972,24 +3333,26 @@
K: Hash,
S: BuildHasher,
{
- let hash_builder = &self.table.hash_builder;
let table = &mut self.table.table;
- let entry = table.insert_entry(self.hash, (self.key, value), |x| {
- make_hash(hash_builder, &x.0)
- });
+ let entry = table.insert_entry(
+ self.hash,
+ (self.key, 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) -> OccupiedEntry<'a, K, V, S>
+ fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, S, A>
where
K: Hash,
S: BuildHasher,
{
- let hash_builder = &self.table.hash_builder;
- let elem = self.table.table.insert(self.hash, (self.key, value), |x| {
- make_hash(hash_builder, &x.0)
- });
+ let elem = self.table.table.insert(
+ self.hash,
+ (self.key, value),
+ make_hasher::<K, _, V, S>(&self.table.hash_builder),
+ );
OccupiedEntry {
hash: self.hash,
key: None,
@@ -2999,15 +3362,17 @@
}
}
-impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S>
+impl<K, V, S, A> FromIterator<(K, V)> for HashMap<K, V, S, A>
where
K: Eq + Hash,
S: BuildHasher + Default,
+ A: Default + Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
let iter = iter.into_iter();
- let mut map = Self::with_capacity_and_hasher(iter.size_hint().0, S::default());
+ let mut map =
+ Self::with_capacity_and_hasher_in(iter.size_hint().0, S::default(), A::default());
iter.for_each(|(k, v)| {
map.insert(k, v);
});
@@ -3017,10 +3382,11 @@
/// Inserts all new key-values from the iterator and replaces values with existing
/// keys with new values returned from the iterator.
-impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S>
+impl<K, V, S, A> Extend<(K, V)> for HashMap<K, V, S, A>
where
K: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
@@ -3062,11 +3428,12 @@
}
}
-impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S>
+impl<'a, K, V, S, A> Extend<(&'a K, &'a V)> for HashMap<K, V, S, A>
where
K: Eq + Hash + Copy,
V: Copy,
S: BuildHasher,
+ A: Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
@@ -3100,10 +3467,14 @@
fn iter_val<'a, 'new>(v: Iter<'a, u8, &'static str>) -> Iter<'a, u8, &'new str> {
v
}
- fn into_iter_key<'new>(v: IntoIter<&'static str, u8>) -> IntoIter<&'new str, u8> {
+ fn into_iter_key<'new, A: Allocator + Clone>(
+ v: IntoIter<&'static str, u8, A>,
+ ) -> IntoIter<&'new str, u8, A> {
v
}
- fn into_iter_val<'new>(v: IntoIter<u8, &'static str>) -> IntoIter<u8, &'new str> {
+ fn into_iter_val<'new, A: Allocator + Clone>(
+ v: IntoIter<u8, &'static str, A>,
+ ) -> IntoIter<u8, &'new str, A> {
v
}
fn keys_key<'a, 'new>(v: Keys<'a, &'static str, u8>) -> Keys<'a, &'new str, u8> {
@@ -3132,6 +3503,7 @@
use super::{HashMap, RawEntryMut};
use crate::TryReserveError::*;
use rand::{rngs::SmallRng, Rng, SeedableRng};
+ use std::borrow::ToOwned;
use std::cell::RefCell;
use std::usize;
use std::vec::Vec;
@@ -4287,11 +4659,7 @@
let mut map: HashMap<_, _> = xs.iter().cloned().collect();
let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 {
- use core::hash::{BuildHasher, Hash, Hasher};
-
- let mut hasher = map.hasher().build_hasher();
- k.hash(&mut hasher);
- hasher.finish()
+ super::make_insert_hash::<i32, _>(map.hasher(), &k)
};
// Existing key (insert)
@@ -4468,9 +4836,11 @@
left -= 1;
} else {
assert!(removed.contains(&(i, 2 * i)), "{} not in {:?}", i, removed);
- let e = m
- .table
- .insert(hash, (i, 2 * i), |x| super::make_hash(&hasher, &x.0));
+ let e = m.table.insert(
+ hash,
+ (i, 2 * i),
+ super::make_hasher::<usize, _, usize, _>(&hasher),
+ );
it.reflect_insert(&e);
if let Some(p) = removed.iter().position(|e| e == &(i, 2 * i)) {
removed.swap_remove(p);
@@ -4501,7 +4871,6 @@
#[test]
fn test_const_with_hasher() {
use core::hash::BuildHasher;
- use std::borrow::ToOwned;
use std::collections::hash_map::DefaultHasher;
#[derive(Clone)]
@@ -4521,4 +4890,33 @@
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_each_mut(["foo", "dud", "foo", "qux"]);
+ assert_eq!(
+ xs,
+ [Ok(&mut 0), Err(Absent), Err(Duplicate(0)), Ok(&mut 30)]
+ );
+
+ 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
new file mode 100644
index 0000000..de6c455
--- /dev/null
+++ b/src/raw/alloc.rs
@@ -0,0 +1,72 @@
+pub(crate) use self::inner::{do_alloc, Allocator, Global};
+
+#[cfg(feature = "nightly")]
+mod inner {
+ use crate::alloc::alloc::Layout;
+ pub use crate::alloc::alloc::{Allocator, Global};
+ use core::ptr::NonNull;
+
+ #[allow(clippy::map_err_ignore)]
+ pub fn do_alloc<A: Allocator>(alloc: &A, layout: Layout) -> Result<NonNull<u8>, ()> {
+ alloc
+ .allocate(layout)
+ .map(|ptr| ptr.as_non_null_ptr())
+ .map_err(|_| ())
+ }
+
+ #[cfg(feature = "bumpalo")]
+ unsafe impl Allocator for crate::BumpWrapper<'_> {
+ #[inline]
+ fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, core::alloc::AllocError> {
+ match self.0.try_alloc_layout(layout) {
+ Ok(ptr) => Ok(NonNull::slice_from_raw_parts(ptr, layout.size())),
+ Err(_) => Err(core::alloc::AllocError),
+ }
+ }
+ #[inline]
+ unsafe fn deallocate(&self, _ptr: NonNull<u8>, _layout: Layout) {}
+ }
+}
+
+#[cfg(not(feature = "nightly"))]
+mod inner {
+ use crate::alloc::alloc::{alloc, dealloc, Layout};
+ use core::ptr::NonNull;
+
+ pub unsafe trait Allocator {
+ fn allocate(&self, layout: Layout) -> Result<NonNull<u8>, ()>;
+ unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
+ }
+
+ #[derive(Copy, Clone)]
+ pub struct Global;
+ unsafe impl Allocator for Global {
+ #[inline]
+ fn allocate(&self, layout: Layout) -> Result<NonNull<u8>, ()> {
+ unsafe { NonNull::new(alloc(layout)).ok_or(()) }
+ }
+ #[inline]
+ unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
+ dealloc(ptr.as_ptr(), layout)
+ }
+ }
+ impl Default for Global {
+ #[inline]
+ fn default() -> Self {
+ Global
+ }
+ }
+
+ pub fn do_alloc<A: Allocator>(alloc: &A, layout: Layout) -> Result<NonNull<u8>, ()> {
+ alloc.allocate(layout)
+ }
+
+ #[cfg(feature = "bumpalo")]
+ unsafe impl Allocator for crate::BumpWrapper<'_> {
+ #[allow(clippy::map_err_ignore)]
+ fn allocate(&self, layout: Layout) -> Result<NonNull<u8>, ()> {
+ self.0.try_alloc_layout(layout).map_err(|_| ())
+ }
+ unsafe fn deallocate(&self, _ptr: NonNull<u8>, _layout: Layout) {}
+ }
+}
diff --git a/src/raw/generic.rs b/src/raw/generic.rs
index 26f8c58..ef066e8 100644
--- a/src/raw/generic.rs
+++ b/src/raw/generic.rs
@@ -55,7 +55,7 @@
struct AlignedBytes {
_align: [Group; 0],
bytes: [u8; Group::WIDTH],
- };
+ }
const ALIGNED_BYTES: AlignedBytes = AlignedBytes {
_align: [],
bytes: [EMPTY; Group::WIDTH],
@@ -67,7 +67,7 @@
#[inline]
#[allow(clippy::cast_ptr_alignment)] // unaligned load
pub unsafe fn load(ptr: *const u8) -> Self {
- Group(ptr::read_unaligned(ptr as *const _))
+ Group(ptr::read_unaligned(ptr.cast()))
}
/// Loads a group of bytes starting at the given address, which must be
@@ -77,7 +77,7 @@
pub unsafe fn load_aligned(ptr: *const u8) -> Self {
// FIXME: use align_offset once it stabilizes
debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
- Group(ptr::read(ptr as *const _))
+ Group(ptr::read(ptr.cast()))
}
/// Stores the group of bytes to the given address, which must be
@@ -87,7 +87,7 @@
pub unsafe fn store_aligned(self, ptr: *mut u8) {
// FIXME: use align_offset once it stabilizes
debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
- ptr::write(ptr as *mut _, self.0);
+ ptr::write(ptr.cast(), self.0);
}
/// Returns a `BitMask` indicating all bytes in the group which *may*
diff --git a/src/raw/mod.rs b/src/raw/mod.rs
index 32fec98..3ae6980 100644
--- a/src/raw/mod.rs
+++ b/src/raw/mod.rs
@@ -1,12 +1,15 @@
-use crate::alloc::alloc::{alloc, dealloc, handle_alloc_error};
+use crate::alloc::alloc::{handle_alloc_error, Layout};
use crate::scopeguard::guard;
use crate::TryReserveError;
-use core::alloc::Layout;
+#[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;
cfg_if! {
@@ -32,6 +35,9 @@
}
}
+mod alloc;
+pub(crate) use self::alloc::{do_alloc, Allocator, Global};
+
mod bitmask;
use self::bitmask::{BitMask, BitMaskIter};
@@ -41,14 +47,28 @@
// consistently improves performance by 10-15%.
#[cfg(feature = "nightly")]
use core::intrinsics::{likely, unlikely};
+
+// On stable we can use #[cold] to get a equivalent effect: this attributes
+// suggests that the function is unlikely to be called
+#[cfg(not(feature = "nightly"))]
+#[inline]
+#[cold]
+fn cold() {}
+
#[cfg(not(feature = "nightly"))]
#[inline]
fn likely(b: bool) -> bool {
+ if !b {
+ cold()
+ }
b
}
#[cfg(not(feature = "nightly"))]
#[inline]
fn unlikely(b: bool) -> bool {
+ if b {
+ cold()
+ }
b
}
@@ -145,27 +165,22 @@
/// Proof that the probe will visit every group in the table:
/// <https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/>
struct ProbeSeq {
- bucket_mask: usize,
pos: usize,
stride: usize,
}
-impl Iterator for ProbeSeq {
- type Item = usize;
-
+impl ProbeSeq {
#[inline]
- fn next(&mut self) -> Option<usize> {
+ fn move_next(&mut self, bucket_mask: usize) {
// We should have found an empty bucket by now and ended the probe.
debug_assert!(
- self.stride <= self.bucket_mask,
+ self.stride <= bucket_mask,
"Went past end of probe sequence"
);
- let result = self.pos;
self.stride += Group::WIDTH;
self.pos += self.stride;
- self.pos &= self.bucket_mask;
- Some(result)
+ self.pos &= bucket_mask;
}
}
@@ -214,30 +229,39 @@
}
}
-/// Returns a Layout which describes the allocation required for a hash table,
-/// and the offset of the control bytes in the allocation.
-/// (the offset is also one past last element of buckets)
-///
-/// Returns `None` if an overflow occurs.
-#[cfg_attr(feature = "inline-more", inline)]
-#[cfg(feature = "nightly")]
-fn calculate_layout<T>(buckets: usize) -> Option<(Layout, usize)> {
- debug_assert!(buckets.is_power_of_two());
+/// Helper which allows the max calculation for ctrl_align to be statically computed for each T
+/// while keeping the rest of `calculate_layout_for` independent of `T`
+#[derive(Copy, Clone)]
+struct TableLayout {
+ size: usize,
+ ctrl_align: usize,
+}
- // Array of buckets
- let data = Layout::array::<T>(buckets).ok()?;
+impl TableLayout {
+ #[inline]
+ fn new<T>() -> Self {
+ let layout = Layout::new::<T>();
+ Self {
+ size: layout.size(),
+ ctrl_align: usize::max(layout.align(), Group::WIDTH),
+ }
+ }
- // Array of control bytes. This must be aligned to the group size.
- //
- // We add `Group::WIDTH` control bytes at the end of the array which
- // replicate the bytes at the start of the array and thus avoids the need to
- // perform bounds-checking while probing.
- //
- // There is no possible overflow here since buckets is a power of two and
- // Group::WIDTH is a small number.
- let ctrl = unsafe { Layout::from_size_align_unchecked(buckets + Group::WIDTH, Group::WIDTH) };
+ #[inline]
+ fn calculate_layout_for(self, buckets: usize) -> Option<(Layout, usize)> {
+ debug_assert!(buckets.is_power_of_two());
- data.extend(ctrl).ok()
+ let TableLayout { size, ctrl_align } = self;
+ // Manual layout calculation since Layout methods are not yet stable.
+ let ctrl_offset =
+ size.checked_mul(buckets)?.checked_add(ctrl_align - 1)? & !(ctrl_align - 1);
+ let len = ctrl_offset.checked_add(buckets + Group::WIDTH)?;
+
+ Some((
+ unsafe { Layout::from_size_align_unchecked(len, ctrl_align) },
+ ctrl_offset,
+ ))
+ }
}
/// Returns a Layout which describes the allocation required for a hash table,
@@ -246,22 +270,8 @@
///
/// Returns `None` if an overflow occurs.
#[cfg_attr(feature = "inline-more", inline)]
-#[cfg(not(feature = "nightly"))]
fn calculate_layout<T>(buckets: usize) -> Option<(Layout, usize)> {
- debug_assert!(buckets.is_power_of_two());
-
- // Manual layout calculation since Layout methods are not yet stable.
- let ctrl_align = usize::max(mem::align_of::<T>(), Group::WIDTH);
- let ctrl_offset = mem::size_of::<T>()
- .checked_mul(buckets)?
- .checked_add(ctrl_align - 1)?
- & !(ctrl_align - 1);
- let len = ctrl_offset.checked_add(buckets + Group::WIDTH)?;
-
- Some((
- unsafe { Layout::from_size_align_unchecked(len, ctrl_align) },
- ctrl_offset,
- ))
+ TableLayout::new::<T>().calculate_layout_for(buckets)
}
/// A reference to a hash table bucket containing a `T`.
@@ -310,12 +320,12 @@
}
}
#[cfg_attr(feature = "inline-more", inline)]
- pub unsafe fn as_ptr(&self) -> *mut T {
+ pub fn as_ptr(&self) -> *mut T {
if mem::size_of::<T>() == 0 {
// Just return an arbitrary ZST pointer which is properly aligned
mem::align_of::<T>() as *mut T
} else {
- self.ptr.as_ptr().sub(1)
+ unsafe { self.ptr.as_ptr().sub(1) }
}
}
#[cfg_attr(feature = "inline-more", inline)]
@@ -356,7 +366,15 @@
}
/// A raw hash table with an unsafe API.
-pub struct RawTable<T> {
+pub struct RawTable<T, A: Allocator + Clone = Global> {
+ table: RawTableInner<A>,
+ // Tell dropck that we own instances of T.
+ marker: PhantomData<T>,
+}
+
+/// Non-generic part of `RawTable` which allows functions to be instantiated only once regardless
+/// of how many different key-value types are used.
+struct RawTableInner<A> {
// Mask to get an index from a hash value. The value is one less than the
// number of buckets in the table.
bucket_mask: usize,
@@ -371,11 +389,10 @@
// Number of elements in the table, only really used by len()
items: usize,
- // Tell dropck that we own instances of T.
- marker: PhantomData<T>,
+ alloc: A,
}
-impl<T> RawTable<T> {
+impl<T> RawTable<T, Global> {
/// Creates a new empty hash table without allocating any memory.
///
/// In effect this returns a table with exactly 1 bucket. However we can
@@ -384,11 +401,36 @@
#[cfg_attr(feature = "inline-more", inline)]
pub const fn new() -> Self {
Self {
- // Be careful to cast the entire slice to a raw pointer.
- ctrl: unsafe { NonNull::new_unchecked(Group::static_empty() as *const _ as *mut u8) },
- bucket_mask: 0,
- items: 0,
- growth_left: 0,
+ table: RawTableInner::new_in(Global),
+ marker: PhantomData,
+ }
+ }
+
+ /// Attempts to allocate a new hash table with at least enough capacity
+ /// for inserting the given number of elements without reallocating.
+ #[cfg(feature = "raw")]
+ pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
+ Self::try_with_capacity_in(capacity, Global)
+ }
+
+ /// Allocates a new hash table with at least enough capacity for inserting
+ /// the given number of elements without reallocating.
+ pub fn with_capacity(capacity: usize) -> Self {
+ Self::with_capacity_in(capacity, Global)
+ }
+}
+
+impl<T, A: Allocator + Clone> RawTable<T, A> {
+ /// Creates a new empty hash table without allocating any memory, using the
+ /// given allocator.
+ ///
+ /// 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.
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn new_in(alloc: A) -> Self {
+ Self {
+ table: RawTableInner::new_in(alloc),
marker: PhantomData,
}
}
@@ -398,26 +440,19 @@
/// The control bytes are left uninitialized.
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn new_uninitialized(
+ alloc: A,
buckets: usize,
- fallability: Fallibility,
+ fallibility: Fallibility,
) -> Result<Self, TryReserveError> {
debug_assert!(buckets.is_power_of_two());
- // Avoid `Option::ok_or_else` because it bloats LLVM IR.
- let (layout, ctrl_offset) = match calculate_layout::<T>(buckets) {
- Some(lco) => lco,
- None => return Err(fallability.capacity_overflow()),
- };
- let ptr = match NonNull::new(alloc(layout)) {
- Some(ptr) => ptr,
- None => return Err(fallability.alloc_err(layout)),
- };
- let ctrl = NonNull::new_unchecked(ptr.as_ptr().add(ctrl_offset));
Ok(Self {
- ctrl,
- bucket_mask: buckets - 1,
- items: 0,
- growth_left: bucket_mask_to_capacity(buckets - 1),
+ table: RawTableInner::new_uninitialized(
+ alloc,
+ TableLayout::new::<T>(),
+ buckets,
+ fallibility,
+ )?,
marker: PhantomData,
})
}
@@ -425,38 +460,33 @@
/// Attempts to allocate a new hash table with at least enough capacity
/// for inserting the given number of elements without reallocating.
fn fallible_with_capacity(
+ alloc: A,
capacity: usize,
- fallability: Fallibility,
+ fallibility: Fallibility,
) -> Result<Self, TryReserveError> {
- if capacity == 0 {
- Ok(Self::new())
- } else {
- unsafe {
- // Avoid `Option::ok_or_else` because it bloats LLVM IR.
- let buckets = match capacity_to_buckets(capacity) {
- Some(buckets) => buckets,
- None => return Err(fallability.capacity_overflow()),
- };
- let result = Self::new_uninitialized(buckets, fallability)?;
- result.ctrl(0).write_bytes(EMPTY, result.num_ctrl_bytes());
-
- Ok(result)
- }
- }
+ Ok(Self {
+ table: RawTableInner::fallible_with_capacity(
+ alloc,
+ TableLayout::new::<T>(),
+ capacity,
+ fallibility,
+ )?,
+ marker: PhantomData,
+ })
}
- /// Attempts to allocate a new hash table with at least enough capacity
- /// for inserting the given number of elements without reallocating.
+ /// Attempts to allocate a new hash table using the given allocator, with at least enough
+ /// capacity for inserting the given number of elements without reallocating.
#[cfg(feature = "raw")]
- pub fn try_with_capacity(capacity: usize) -> Result<Self, TryReserveError> {
- Self::fallible_with_capacity(capacity, Fallibility::Fallible)
+ pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> {
+ Self::fallible_with_capacity(alloc, capacity, Fallibility::Fallible)
}
- /// Allocates a new hash table with at least enough capacity for inserting
- /// the given number of elements without reallocating.
- pub fn with_capacity(capacity: usize) -> Self {
+ /// Allocates a new hash table using the given allocator, with at least enough capacity for
+ /// inserting the given number of elements without reallocating.
+ pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
- match Self::fallible_with_capacity(capacity, Fallibility::Infallible) {
+ match Self::fallible_with_capacity(alloc, capacity, Fallibility::Infallible) {
Ok(capacity) => capacity,
Err(_) => unsafe { hint::unreachable_unchecked() },
}
@@ -465,18 +495,13 @@
/// Deallocates the table without dropping any entries.
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn free_buckets(&mut self) {
- // Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
- let (layout, ctrl_offset) = match calculate_layout::<T>(self.buckets()) {
- Some(lco) => lco,
- None => hint::unreachable_unchecked(),
- };
- dealloc(self.ctrl.as_ptr().sub(ctrl_offset), layout);
+ self.table.free_buckets(TableLayout::new::<T>())
}
/// Returns pointer to one past last element of data table.
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn data_end(&self) -> NonNull<T> {
- NonNull::new_unchecked(self.ctrl.as_ptr() as *mut T)
+ NonNull::new_unchecked(self.table.ctrl.as_ptr().cast())
}
/// Returns pointer to start of data table.
@@ -492,17 +517,10 @@
bucket.to_base_index(self.data_end())
}
- /// Returns a pointer to a control byte.
- #[cfg_attr(feature = "inline-more", inline)]
- unsafe fn ctrl(&self, index: usize) -> *mut u8 {
- debug_assert!(index < self.num_ctrl_bytes());
- self.ctrl.as_ptr().add(index)
- }
-
/// Returns a pointer to an element in the table.
#[cfg_attr(feature = "inline-more", inline)]
pub unsafe fn bucket(&self, index: usize) -> Bucket<T> {
- debug_assert_ne!(self.bucket_mask, 0);
+ debug_assert_ne!(self.table.bucket_mask, 0);
debug_assert!(index < self.buckets());
Bucket::from_base_index(self.data_end(), index)
}
@@ -512,27 +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);
- debug_assert!(is_full(*self.ctrl(index)));
- let index_before = index.wrapping_sub(Group::WIDTH) & self.bucket_mask;
- let empty_before = Group::load(self.ctrl(index_before)).match_empty();
- let empty_after = Group::load(self.ctrl(index)).match_empty();
-
- // If we are inside a continuous block of Group::WIDTH full or deleted
- // cells then a probe window may have seen a full block when trying to
- // insert. We therefore need to keep that block non-empty so that
- // lookups will continue searching to the next probe window.
- //
- // 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
- // begining of a group.
- let ctrl = if empty_before.leading_zeros() + empty_after.trailing_zeros() >= Group::WIDTH {
- DELETED
- } else {
- self.growth_left += 1;
- EMPTY
- };
- self.set_ctrl(index, ctrl);
- self.items -= 1;
+ self.table.erase(index)
}
/// Erases an element from the table, dropping it in place.
@@ -578,109 +576,26 @@
}
}
- /// Returns an iterator for a probe sequence on the table.
- ///
- /// This iterator never terminates, but is guaranteed to visit each bucket
- /// group exactly once. The loop using `probe_seq` must terminate upon
- /// reaching a group containing an empty bucket.
- #[cfg_attr(feature = "inline-more", inline)]
- fn probe_seq(&self, hash: u64) -> ProbeSeq {
- ProbeSeq {
- bucket_mask: self.bucket_mask,
- pos: h1(hash) & self.bucket_mask,
- stride: 0,
- }
- }
-
- /// Sets a control byte, and possibly also the replicated control byte at
- /// the end of the array.
- #[cfg_attr(feature = "inline-more", inline)]
- unsafe fn set_ctrl(&self, index: usize, ctrl: u8) {
- // Replicate the first Group::WIDTH control bytes at the end of
- // the array without using a branch:
- // - If index >= Group::WIDTH then index == index2.
- // - Otherwise index2 == self.bucket_mask + 1 + index.
- //
- // The very last replicated control byte is never actually read because
- // we mask the initial index for unaligned loads, but we write it
- // anyways because it makes the set_ctrl implementation simpler.
- //
- // If there are fewer buckets than Group::WIDTH then this code will
- // replicate the buckets at the end of the trailing group. For example
- // with 2 buckets and a group size of 4, the control bytes will look
- // like this:
- //
- // Real | Replicated
- // ---------------------------------------------
- // | [A] | [B] | [EMPTY] | [EMPTY] | [A] | [B] |
- // ---------------------------------------------
- let index2 = ((index.wrapping_sub(Group::WIDTH)) & self.bucket_mask) + Group::WIDTH;
-
- *self.ctrl(index) = ctrl;
- *self.ctrl(index2) = ctrl;
- }
-
- /// Searches for an empty or deleted bucket which is suitable for inserting
- /// a new element.
- ///
- /// There must be at least 1 empty bucket in the table.
- #[cfg_attr(feature = "inline-more", inline)]
- fn find_insert_slot(&self, hash: u64) -> usize {
- for pos in self.probe_seq(hash) {
- unsafe {
- let group = Group::load(self.ctrl(pos));
- if let Some(bit) = group.match_empty_or_deleted().lowest_set_bit() {
- let result = (pos + bit) & self.bucket_mask;
-
- // In tables smaller than the group width, trailing control
- // bytes outside the range of the table are filled with
- // 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 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).
- if unlikely(is_full(*self.ctrl(result))) {
- debug_assert!(self.bucket_mask < Group::WIDTH);
- debug_assert_ne!(pos, 0);
- return Group::load_aligned(self.ctrl(0))
- .match_empty_or_deleted()
- .lowest_set_bit_nonzero();
- } else {
- return result;
- }
- }
- }
- }
-
- // probe_seq never returns.
- unreachable!();
- }
-
/// Marks all table buckets as empty without dropping their contents.
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear_no_drop(&mut self) {
- if !self.is_empty_singleton() {
- unsafe {
- self.ctrl(0).write_bytes(EMPTY, self.num_ctrl_bytes());
- }
- }
- self.items = 0;
- self.growth_left = bucket_mask_to_capacity(self.bucket_mask);
+ self.table.clear_no_drop()
}
/// Removes all elements from the table without freeing the backing memory.
#[cfg_attr(feature = "inline-more", inline)]
pub fn clear(&mut self) {
// Ensure that the table is reset even if one of the drops panic
- let self_ = guard(self, |self_| self_.clear_no_drop());
+ let mut self_ = guard(self, |self_| self_.clear_no_drop());
+ unsafe {
+ self_.drop_elements();
+ }
+ }
- if mem::needs_drop::<T>() && self_.len() != 0 {
- unsafe {
- for item in self_.iter() {
- item.drop();
- }
+ unsafe fn drop_elements(&mut self) {
+ if mem::needs_drop::<T>() && self.len() != 0 {
+ for item in self.iter() {
+ item.drop();
}
}
}
@@ -690,9 +605,9 @@
pub fn shrink_to(&mut self, min_size: usize, hasher: impl Fn(&T) -> u64) {
// Calculate the minimal number of elements that we need to reserve
// space for.
- let min_size = usize::max(self.items, min_size);
+ let min_size = usize::max(self.table.items, min_size);
if min_size == 0 {
- *self = Self::new();
+ *self = Self::new_in(self.table.alloc.clone());
return;
}
@@ -708,8 +623,8 @@
// If we have more buckets than we need, shrink the table.
if min_buckets < self.buckets() {
// Fast path if the table is empty
- if self.items == 0 {
- *self = Self::with_capacity(min_size)
+ if self.table.items == 0 {
+ *self = Self::with_capacity_in(min_size, self.table.alloc.clone())
} else {
// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
if self
@@ -726,7 +641,7 @@
/// without reallocation.
#[cfg_attr(feature = "inline-more", inline)]
pub fn reserve(&mut self, additional: usize, hasher: impl Fn(&T) -> u64) {
- if additional > self.growth_left {
+ if additional > self.table.growth_left {
// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
if self
.reserve_rehash(additional, hasher, Fallibility::Infallible)
@@ -745,7 +660,7 @@
additional: usize,
hasher: impl Fn(&T) -> u64,
) -> Result<(), TryReserveError> {
- if additional > self.growth_left {
+ if additional > self.table.growth_left {
self.reserve_rehash(additional, hasher, Fallibility::Fallible)
} else {
Ok(())
@@ -759,14 +674,14 @@
&mut self,
additional: usize,
hasher: impl Fn(&T) -> u64,
- fallability: Fallibility,
+ fallibility: Fallibility,
) -> Result<(), TryReserveError> {
// Avoid `Option::ok_or_else` because it bloats LLVM IR.
- let new_items = match self.items.checked_add(additional) {
+ let new_items = match self.table.items.checked_add(additional) {
Some(new_items) => new_items,
- None => return Err(fallability.capacity_overflow()),
+ None => return Err(fallibility.capacity_overflow()),
};
- let full_capacity = bucket_mask_to_capacity(self.bucket_mask);
+ 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.
@@ -778,7 +693,7 @@
self.resize(
usize::max(new_items, full_capacity + 1),
hasher,
- fallability,
+ fallibility,
)
}
}
@@ -789,35 +704,18 @@
/// If `hasher` panics then some the table's contents may be lost.
fn rehash_in_place(&mut self, hasher: impl Fn(&T) -> u64) {
unsafe {
- // Bulk convert all full control bytes to DELETED, and all DELETED
- // control bytes to EMPTY. This effectively frees up all buckets
- // containing a DELETED entry.
- for i in (0..self.buckets()).step_by(Group::WIDTH) {
- let group = Group::load_aligned(self.ctrl(i));
- let group = group.convert_special_to_empty_and_full_to_deleted();
- group.store_aligned(self.ctrl(i));
- }
-
- // Fix up the trailing control bytes. See the comments in set_ctrl
- // for the handling of tables smaller than the group width.
- if self.buckets() < Group::WIDTH {
- self.ctrl(0)
- .copy_to(self.ctrl(Group::WIDTH), self.buckets());
- } else {
- self.ctrl(0)
- .copy_to(self.ctrl(self.buckets()), Group::WIDTH);
- }
-
// 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.
- let mut guard = guard(self, |self_| {
+ 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(i).drop();
+ self_.bucket::<T>(i).drop();
self_.items -= 1;
}
}
@@ -832,6 +730,7 @@
if *guard.ctrl(i) != DELETED {
continue;
}
+
'inner: loop {
// Hash the current item
let item = guard.bucket(i);
@@ -845,25 +744,19 @@
// 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.
- let probe_index = |pos: usize| {
- (pos.wrapping_sub(guard.probe_seq(hash).pos) & guard.bucket_mask)
- / Group::WIDTH
- };
- if likely(probe_index(i) == probe_index(new_i)) {
- guard.set_ctrl(i, h2(hash));
+ 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.ctrl(new_i);
- guard.set_ctrl(new_i, h2(hash));
-
+ 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.set_ctrl(i, EMPTY);
guard.bucket(new_i).copy_from_nonoverlapping(&item);
continue 'outer;
} else {
@@ -888,27 +781,12 @@
&mut self,
capacity: usize,
hasher: impl Fn(&T) -> u64,
- fallability: Fallibility,
+ fallibility: Fallibility,
) -> Result<(), TryReserveError> {
unsafe {
- debug_assert!(self.items <= capacity);
-
- // Allocate and initialize the new table.
- let mut new_table = Self::fallible_with_capacity(capacity, fallability)?;
- new_table.growth_left -= self.items;
- new_table.items = self.items;
-
- // The hash function may panic, in which case we simply free the new
- // table without dropping any elements that may have been copied into
- // it.
- //
- // This guard is also used to free the old table on success, see
- // the comment at the bottom of this function.
- let mut new_table = guard(ManuallyDrop::new(new_table), |new_table| {
- if !new_table.is_empty_singleton() {
- new_table.free_buckets();
- }
- });
+ 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() {
@@ -919,8 +797,7 @@
// - there are no DELETED entries.
// - we know there is enough space in the table.
// - all elements are unique.
- let index = new_table.find_insert_slot(hash);
- new_table.set_ctrl(index, h2(hash));
+ let (index, _) = new_table.prepare_insert_slot(hash);
new_table.bucket(index).copy_from_nonoverlapping(&item);
}
@@ -928,7 +805,7 @@
// 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);
+ mem::swap(&mut self.table, &mut new_table);
Ok(())
}
@@ -940,26 +817,46 @@
#[cfg_attr(feature = "inline-more", inline)]
pub fn insert(&mut self, hash: u64, value: T, hasher: impl Fn(&T) -> u64) -> Bucket<T> {
unsafe {
- let mut index = self.find_insert_slot(hash);
+ let mut index = self.table.find_insert_slot(hash);
// We can avoid growing the table once we have reached our load
// factor if we are replacing a tombstone. This works since the
// number of EMPTY slots does not change in this case.
- let old_ctrl = *self.ctrl(index);
- if unlikely(self.growth_left == 0 && special_is_empty(old_ctrl)) {
+ let old_ctrl = *self.table.ctrl(index);
+ if unlikely(self.table.growth_left == 0 && special_is_empty(old_ctrl)) {
self.reserve(1, hasher);
- index = self.find_insert_slot(hash);
+ index = self.table.find_insert_slot(hash);
}
+ self.table.record_item_insert_at(index, old_ctrl, hash);
+
let bucket = self.bucket(index);
- self.growth_left -= special_is_empty(old_ctrl) as usize;
- self.set_ctrl(index, h2(hash));
bucket.write(value);
- self.items += 1;
bucket
}
}
+ /// Attempts to insert a new element without growing the table and return its raw bucket.
+ ///
+ /// Returns an `Err` containing the given element if inserting it would require growing the
+ /// table.
+ ///
+ /// This does not check if the given element already exists in the table.
+ #[cfg(feature = "raw")]
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn try_insert_no_grow(&mut self, hash: u64, value: T) -> Result<Bucket<T>, T> {
+ unsafe {
+ match self.table.prepare_insert_no_grow(hash) {
+ Ok(index) => {
+ let bucket = self.bucket(index);
+ bucket.write(value);
+ Ok(bucket)
+ }
+ Err(()) => Err(value),
+ }
+ }
+ }
+
/// Inserts a new element into the table, and returns a mutable reference to it.
///
/// This does not check if the given element already exists in the table.
@@ -977,17 +874,15 @@
#[cfg(any(feature = "raw", feature = "rustc-internal-api"))]
pub fn insert_no_grow(&mut self, hash: u64, value: T) -> Bucket<T> {
unsafe {
- let index = self.find_insert_slot(hash);
- let bucket = self.bucket(index);
+ 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.
- let old_ctrl = *self.ctrl(index);
- self.growth_left -= special_is_empty(old_ctrl) as usize;
+ self.table.growth_left -= special_is_empty(old_ctrl) as usize;
- self.set_ctrl(index, h2(hash));
bucket.write(value);
- self.items += 1;
+ self.table.items += 1;
bucket
}
}
@@ -1004,14 +899,14 @@
F: FnOnce(T) -> Option<T>,
{
let index = self.bucket_index(&bucket);
- let old_ctrl = *self.ctrl(index);
+ let old_ctrl = *self.table.ctrl(index);
debug_assert!(is_full(old_ctrl));
- let old_growth_left = self.growth_left;
+ let old_growth_left = self.table.growth_left;
let item = self.remove(bucket);
if let Some(new_item) = f(item) {
- self.growth_left = old_growth_left;
- self.set_ctrl(index, old_ctrl);
- self.items += 1;
+ self.table.growth_left = old_growth_left;
+ self.table.set_ctrl(index, old_ctrl);
+ self.table.items += 1;
self.bucket(index).write(new_item);
true
} else {
@@ -1053,38 +948,83 @@
}
}
+ /// 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. 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.
+ ///
+ /// 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,
+ ) -> [Result<&'_ mut T, UnavailableMutError>; N] {
+ // Collect the requested buckets.
+ // TODO use `MaybeUninit::uninit_array` here instead once that's stable.
+ 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) };
+
+ // 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()) },
+ };
+ },
+ )
+ }
+
+ 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.
#[cfg_attr(feature = "inline-more", inline)]
pub fn capacity(&self) -> usize {
- self.items + self.growth_left
+ self.table.items + self.table.growth_left
}
/// Returns the number of elements in the table.
#[cfg_attr(feature = "inline-more", inline)]
pub fn len(&self) -> usize {
- self.items
+ self.table.items
}
/// Returns the number of buckets in the table.
#[cfg_attr(feature = "inline-more", inline)]
pub fn buckets(&self) -> usize {
- self.bucket_mask + 1
- }
-
- /// Returns the number of control bytes in the table.
- #[cfg_attr(feature = "inline-more", inline)]
- fn num_ctrl_bytes(&self) -> usize {
- self.bucket_mask + 1 + Group::WIDTH
- }
-
- /// Returns whether this table points to the empty singleton with a capacity
- /// of 0.
- #[cfg_attr(feature = "inline-more", inline)]
- fn is_empty_singleton(&self) -> bool {
- self.bucket_mask == 0
+ self.table.bucket_mask + 1
}
/// Returns an iterator over every element in the table. It is up to
@@ -1095,8 +1035,8 @@
pub unsafe fn iter(&self) -> RawIter<T> {
let data = Bucket::from_base_index(self.data_end(), 0);
RawIter {
- iter: RawIterRange::new(self.ctrl.as_ptr(), data, self.buckets()),
- items: self.items,
+ iter: RawIterRange::new(self.table.ctrl.as_ptr(), data, self.table.buckets()),
+ items: self.table.items,
}
}
@@ -1108,14 +1048,14 @@
/// `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)]
- pub unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<'_, T> {
+ pub unsafe fn iter_hash(&self, hash: u64) -> RawIterHash<'_, T, A> {
RawIterHash::new(self, hash)
}
/// Returns an iterator which removes all elements from the table without
/// freeing the memory.
#[cfg_attr(feature = "inline-more", inline)]
- pub fn drain(&mut self) -> RawDrain<'_, T> {
+ pub fn drain(&mut self) -> RawDrain<'_, T, A> {
unsafe {
let iter = self.iter();
self.drain_iter_from(iter)
@@ -1130,11 +1070,11 @@
/// It is up to the caller to ensure that the iterator is valid for this
/// `RawTable` and covers all items that remain in the table.
#[cfg_attr(feature = "inline-more", inline)]
- pub unsafe fn drain_iter_from(&mut self, iter: RawIter<T>) -> RawDrain<'_, T> {
+ pub unsafe fn drain_iter_from(&mut self, iter: RawIter<T>) -> RawDrain<'_, T, A> {
debug_assert_eq!(iter.len(), self.len());
RawDrain {
iter,
- table: ManuallyDrop::new(mem::replace(self, Self::new())),
+ table: ManuallyDrop::new(mem::replace(self, Self::new_in(self.table.alloc.clone()))),
orig_table: NonNull::from(self),
marker: PhantomData,
}
@@ -1146,31 +1086,33 @@
///
/// It is up to the caller to ensure that the iterator is valid for this
/// `RawTable` and covers all items that remain in the table.
- pub unsafe fn into_iter_from(self, iter: RawIter<T>) -> RawIntoIter<T> {
+ pub unsafe fn into_iter_from(self, iter: RawIter<T>) -> RawIntoIter<T, A> {
debug_assert_eq!(iter.len(), self.len());
- let alloc = self.into_alloc();
+ let alloc = self.table.alloc.clone();
+ let allocation = self.into_allocation();
RawIntoIter {
iter,
- alloc,
+ allocation,
marker: PhantomData,
+ alloc,
}
}
/// Converts the table into a raw allocation. The contents of the table
/// should be dropped using a `RawIter` before freeing the allocation.
#[cfg_attr(feature = "inline-more", inline)]
- pub(crate) fn into_alloc(self) -> Option<(NonNull<u8>, Layout)> {
- let alloc = if self.is_empty_singleton() {
+ pub(crate) fn into_allocation(self) -> Option<(NonNull<u8>, Layout)> {
+ let alloc = if self.table.is_empty_singleton() {
None
} else {
// Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
- let (layout, ctrl_offset) = match calculate_layout::<T>(self.buckets()) {
+ let (layout, ctrl_offset) = match calculate_layout::<T>(self.table.buckets()) {
Some(lco) => lco,
None => unsafe { hint::unreachable_unchecked() },
};
Some((
- unsafe { NonNull::new_unchecked(self.ctrl.as_ptr().sub(ctrl_offset)) },
+ unsafe { NonNull::new_unchecked(self.table.ctrl.as_ptr().sub(ctrl_offset)) },
layout,
))
};
@@ -1179,18 +1121,364 @@
}
}
-unsafe impl<T> Send for RawTable<T> where T: Send {}
-unsafe impl<T> Sync for RawTable<T> where T: 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<T: Clone> Clone for RawTable<T> {
+impl<A> RawTableInner<A> {
+ #[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.
+ ctrl: unsafe { NonNull::new_unchecked(Group::static_empty() as *const _ as *mut u8) },
+ bucket_mask: 0,
+ items: 0,
+ growth_left: 0,
+ alloc,
+ }
+ }
+}
+
+impl<A: Allocator + Clone> RawTableInner<A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn new_uninitialized(
+ alloc: A,
+ table_layout: TableLayout,
+ buckets: usize,
+ fallibility: Fallibility,
+ ) -> Result<Self, TryReserveError> {
+ debug_assert!(buckets.is_power_of_two());
+
+ // Avoid `Option::ok_or_else` because it bloats LLVM IR.
+ let (layout, ctrl_offset) = match table_layout.calculate_layout_for(buckets) {
+ Some(lco) => lco,
+ None => 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)),
+ };
+
+ let ctrl = NonNull::new_unchecked(ptr.as_ptr().add(ctrl_offset));
+ Ok(Self {
+ ctrl,
+ bucket_mask: buckets - 1,
+ items: 0,
+ growth_left: bucket_mask_to_capacity(buckets - 1),
+ alloc,
+ })
+ }
+
+ #[inline]
+ fn fallible_with_capacity(
+ alloc: A,
+ table_layout: TableLayout,
+ capacity: usize,
+ fallibility: Fallibility,
+ ) -> Result<Self, TryReserveError> {
+ if capacity == 0 {
+ Ok(Self::new_in(alloc))
+ } else {
+ unsafe {
+ let buckets =
+ capacity_to_buckets(capacity).ok_or_else(|| fallibility.capacity_overflow())?;
+
+ let result = Self::new_uninitialized(alloc, table_layout, buckets, fallibility)?;
+ result.ctrl(0).write_bytes(EMPTY, result.num_ctrl_bytes());
+
+ Ok(result)
+ }
+ }
+ }
+
+ /// Searches for an empty or deleted bucket which is suitable for inserting
+ /// a new element and sets the hash for that slot.
+ ///
+ /// There must be at least 1 empty bucket in the table.
+ #[inline]
+ unsafe fn prepare_insert_slot(&self, hash: u64) -> (usize, u8) {
+ let index = self.find_insert_slot(hash);
+ let old_ctrl = *self.ctrl(index);
+ self.set_ctrl_h2(index, hash);
+ (index, old_ctrl)
+ }
+
+ /// Searches for an empty or deleted bucket which is suitable for inserting
+ /// a new element.
+ ///
+ /// There must be at least 1 empty bucket in the table.
+ #[inline]
+ fn find_insert_slot(&self, hash: u64) -> usize {
+ let mut probe_seq = self.probe_seq(hash);
+ loop {
+ unsafe {
+ let group = Group::load(self.ctrl(probe_seq.pos));
+ if let Some(bit) = group.match_empty_or_deleted().lowest_set_bit() {
+ let result = (probe_seq.pos + bit) & self.bucket_mask;
+
+ // In tables smaller than the group width, trailing control
+ // bytes outside the range of the table are filled with
+ // 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 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).
+ if unlikely(is_full(*self.ctrl(result))) {
+ debug_assert!(self.bucket_mask < Group::WIDTH);
+ debug_assert_ne!(probe_seq.pos, 0);
+ return Group::load_aligned(self.ctrl(0))
+ .match_empty_or_deleted()
+ .lowest_set_bit_nonzero();
+ }
+
+ return result;
+ }
+ }
+ probe_seq.move_next(self.bucket_mask);
+ }
+ }
+
+ #[allow(clippy::mut_mut)]
+ #[inline]
+ unsafe fn prepare_rehash_in_place(&mut self) {
+ // Bulk convert all full control bytes to DELETED, and all DELETED
+ // control bytes to EMPTY. This effectively frees up all buckets
+ // containing a DELETED entry.
+ for i in (0..self.buckets()).step_by(Group::WIDTH) {
+ let group = Group::load_aligned(self.ctrl(i));
+ let group = group.convert_special_to_empty_and_full_to_deleted();
+ group.store_aligned(self.ctrl(i));
+ }
+
+ // Fix up the trailing control bytes. See the comments in set_ctrl
+ // for the handling of tables smaller than the group width.
+ if self.buckets() < Group::WIDTH {
+ self.ctrl(0)
+ .copy_to(self.ctrl(Group::WIDTH), self.buckets());
+ } else {
+ self.ctrl(0)
+ .copy_to(self.ctrl(self.buckets()), Group::WIDTH);
+ }
+ }
+
+ #[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)
+ }
+
+ #[cfg_attr(feature = "inline-more", inline)]
+ unsafe fn data_end<T>(&self) -> NonNull<T> {
+ NonNull::new_unchecked(self.ctrl.as_ptr().cast())
+ }
+
+ /// Returns an iterator-like object for a probe sequence on the table.
+ ///
+ /// This iterator never terminates, but is guaranteed to visit each bucket
+ /// group exactly once. The loop using `probe_seq` must terminate upon
+ /// reaching a group containing an empty bucket.
+ #[inline]
+ fn probe_seq(&self, hash: u64) -> ProbeSeq {
+ ProbeSeq {
+ pos: h1(hash) & self.bucket_mask,
+ stride: 0,
+ }
+ }
+
+ /// Returns the index of a bucket for which a value must be inserted if there is enough rooom
+ /// in the table, otherwise returns error
+ #[cfg(feature = "raw")]
+ #[inline]
+ unsafe fn prepare_insert_no_grow(&mut self, hash: u64) -> Result<usize, ()> {
+ let index = self.find_insert_slot(hash);
+ let old_ctrl = *self.ctrl(index);
+ if unlikely(self.growth_left == 0 && special_is_empty(old_ctrl)) {
+ Err(())
+ } else {
+ self.record_item_insert_at(index, old_ctrl, hash);
+ Ok(index)
+ }
+ }
+
+ #[inline]
+ unsafe fn record_item_insert_at(&mut self, index: usize, old_ctrl: u8, hash: u64) {
+ self.growth_left -= special_is_empty(old_ctrl) as usize;
+ self.set_ctrl_h2(index, hash);
+ self.items += 1;
+ }
+
+ #[inline]
+ fn is_in_same_group(&self, i: usize, new_i: usize, hash: u64) -> bool {
+ let probe_seq_pos = self.probe_seq(hash).pos;
+ let probe_index =
+ |pos: usize| (pos.wrapping_sub(probe_seq_pos) & self.bucket_mask) / Group::WIDTH;
+ probe_index(i) == probe_index(new_i)
+ }
+
+ /// Sets a control byte to the hash, and possibly also the replicated control byte at
+ /// the end of the array.
+ #[inline]
+ unsafe fn set_ctrl_h2(&self, index: usize, hash: u64) {
+ self.set_ctrl(index, h2(hash))
+ }
+
+ #[inline]
+ unsafe fn replace_ctrl_h2(&self, index: usize, hash: u64) -> u8 {
+ let prev_ctrl = *self.ctrl(index);
+ self.set_ctrl_h2(index, hash);
+ prev_ctrl
+ }
+
+ /// Sets a control byte, and possibly also the replicated control byte at
+ /// the end of the array.
+ #[inline]
+ unsafe fn set_ctrl(&self, index: usize, ctrl: u8) {
+ // Replicate the first Group::WIDTH control bytes at the end of
+ // the array without using a branch:
+ // - If index >= Group::WIDTH then index == index2.
+ // - Otherwise index2 == self.bucket_mask + 1 + index.
+ //
+ // The very last replicated control byte is never actually read because
+ // we mask the initial index for unaligned loads, but we write it
+ // anyways because it makes the set_ctrl implementation simpler.
+ //
+ // If there are fewer buckets than Group::WIDTH then this code will
+ // replicate the buckets at the end of the trailing group. For example
+ // with 2 buckets and a group size of 4, the control bytes will look
+ // like this:
+ //
+ // Real | Replicated
+ // ---------------------------------------------
+ // | [A] | [B] | [EMPTY] | [EMPTY] | [A] | [B] |
+ // ---------------------------------------------
+ let index2 = ((index.wrapping_sub(Group::WIDTH)) & self.bucket_mask) + Group::WIDTH;
+
+ *self.ctrl(index) = ctrl;
+ *self.ctrl(index2) = ctrl;
+ }
+
+ /// Returns a pointer to a control byte.
+ #[inline]
+ unsafe fn ctrl(&self, index: usize) -> *mut u8 {
+ debug_assert!(index < self.num_ctrl_bytes());
+ self.ctrl.as_ptr().add(index)
+ }
+
+ #[inline]
+ fn buckets(&self) -> usize {
+ self.bucket_mask + 1
+ }
+
+ #[inline]
+ fn num_ctrl_bytes(&self) -> usize {
+ self.bucket_mask + 1 + Group::WIDTH
+ }
+
+ #[inline]
+ fn is_empty_singleton(&self) -> bool {
+ self.bucket_mask == 0
+ }
+
+ #[allow(clippy::mut_mut)]
+ #[inline]
+ unsafe fn prepare_resize(
+ &self,
+ table_layout: TableLayout,
+ capacity: usize,
+ fallibility: Fallibility,
+ ) -> Result<crate::scopeguard::ScopeGuard<Self, impl FnMut(&mut Self)>, TryReserveError> {
+ debug_assert!(self.items <= capacity);
+
+ // Allocate and initialize the new table.
+ let mut new_table = RawTableInner::fallible_with_capacity(
+ self.alloc.clone(),
+ table_layout,
+ capacity,
+ fallibility,
+ )?;
+ new_table.growth_left -= self.items;
+ new_table.items = self.items;
+
+ // The hash function may panic, in which case we simply free the new
+ // table without dropping any elements that may have been copied into
+ // it.
+ //
+ // This guard is also used to free the old table on success, see
+ // the comment at the bottom of this function.
+ Ok(guard(new_table, move |self_| {
+ if !self_.is_empty_singleton() {
+ self_.free_buckets(table_layout);
+ }
+ }))
+ }
+
+ #[inline]
+ unsafe fn free_buckets(&mut self, table_layout: TableLayout) {
+ // Avoid `Option::unwrap_or_else` because it bloats LLVM IR.
+ let (layout, ctrl_offset) = match table_layout.calculate_layout_for(self.buckets()) {
+ Some(lco) => lco,
+ None => hint::unreachable_unchecked(),
+ };
+ self.alloc.deallocate(
+ NonNull::new_unchecked(self.ctrl.as_ptr().sub(ctrl_offset)),
+ layout,
+ );
+ }
+
+ /// Marks all table buckets as empty without dropping their contents.
+ #[inline]
+ fn clear_no_drop(&mut self) {
+ if !self.is_empty_singleton() {
+ unsafe {
+ self.ctrl(0).write_bytes(EMPTY, self.num_ctrl_bytes());
+ }
+ }
+ self.items = 0;
+ self.growth_left = bucket_mask_to_capacity(self.bucket_mask);
+ }
+
+ #[inline]
+ unsafe fn erase(&mut self, index: usize) {
+ debug_assert!(is_full(*self.ctrl(index)));
+ let index_before = index.wrapping_sub(Group::WIDTH) & self.bucket_mask;
+ let empty_before = Group::load(self.ctrl(index_before)).match_empty();
+ let empty_after = Group::load(self.ctrl(index)).match_empty();
+
+ // If we are inside a continuous block of Group::WIDTH full or deleted
+ // cells then a probe window may have seen a full block when trying to
+ // insert. We therefore need to keep that block non-empty so that
+ // lookups will continue searching to the next probe window.
+ //
+ // 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
+ // begining of a group.
+ let ctrl = if empty_before.leading_zeros() + empty_after.trailing_zeros() >= Group::WIDTH {
+ DELETED
+ } else {
+ self.growth_left += 1;
+ EMPTY
+ };
+ self.set_ctrl(index, ctrl);
+ self.items -= 1;
+ }
+}
+
+impl<T: Clone, A: Allocator + Clone> Clone for RawTable<T, A> {
fn clone(&self) -> Self {
- if self.is_empty_singleton() {
- Self::new()
+ if self.table.is_empty_singleton() {
+ Self::new_in(self.table.alloc.clone())
} else {
unsafe {
let mut new_table = ManuallyDrop::new(
// Avoid `Result::ok_or_else` because it bloats LLVM IR.
- match Self::new_uninitialized(self.buckets(), Fallibility::Infallible) {
+ match Self::new_uninitialized(
+ self.table.alloc.clone(),
+ self.table.buckets(),
+ Fallibility::Infallible,
+ ) {
Ok(table) => table,
Err(_) => hint::unreachable_unchecked(),
},
@@ -1208,26 +1496,26 @@
}
fn clone_from(&mut self, source: &Self) {
- if source.is_empty_singleton() {
- *self = Self::new();
+ if source.table.is_empty_singleton() {
+ *self = Self::new_in(self.table.alloc.clone());
} else {
unsafe {
// First, drop all our elements without clearing the control bytes.
- if mem::needs_drop::<T>() && self.len() != 0 {
- for item in self.iter() {
- item.drop();
- }
- }
+ self.drop_elements();
// If necessary, resize our table to match the source.
if self.buckets() != source.buckets() {
// Skip our drop by using ptr::write.
- if !self.is_empty_singleton() {
+ if !self.table.is_empty_singleton() {
self.free_buckets();
}
(self as *mut Self).write(
// Avoid `Result::unwrap_or_else` because it bloats LLVM IR.
- match Self::new_uninitialized(source.buckets(), Fallibility::Infallible) {
+ match Self::new_uninitialized(
+ self.table.alloc.clone(),
+ source.buckets(),
+ Fallibility::Infallible,
+ ) {
Ok(table) => table,
Err(_) => hint::unreachable_unchecked(),
},
@@ -1247,7 +1535,7 @@
trait RawTableClone {
unsafe fn clone_from_spec(&mut self, source: &Self, on_panic: impl FnMut(&mut Self));
}
-impl<T: Clone> RawTableClone for RawTable<T> {
+impl<T: Clone, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
default_fn! {
unsafe fn clone_from_spec(&mut self, source: &Self, on_panic: impl FnMut(&mut Self)) {
@@ -1256,29 +1544,31 @@
}
}
#[cfg(feature = "nightly")]
-impl<T: Copy> RawTableClone for RawTable<T> {
+impl<T: Copy, A: Allocator + Clone> RawTableClone for RawTable<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn clone_from_spec(&mut self, source: &Self, _on_panic: impl FnMut(&mut Self)) {
source
+ .table
.ctrl(0)
- .copy_to_nonoverlapping(self.ctrl(0), self.num_ctrl_bytes());
+ .copy_to_nonoverlapping(self.table.ctrl(0), self.table.num_ctrl_bytes());
source
.data_start()
- .copy_to_nonoverlapping(self.data_start(), self.buckets());
+ .copy_to_nonoverlapping(self.data_start(), self.table.buckets());
- self.items = source.items;
- self.growth_left = source.growth_left;
+ self.table.items = source.table.items;
+ self.table.growth_left = source.table.growth_left;
}
}
-impl<T: Clone> RawTable<T> {
+impl<T: Clone, A: Allocator + Clone> RawTable<T, A> {
/// Common code for clone and clone_from. Assumes `self.buckets() == source.buckets()`.
#[cfg_attr(feature = "inline-more", inline)]
unsafe fn clone_from_impl(&mut self, source: &Self, mut on_panic: impl FnMut(&mut Self)) {
// Copy the control bytes unchanged. We do this in a single pass
source
+ .table
.ctrl(0)
- .copy_to_nonoverlapping(self.ctrl(0), self.num_ctrl_bytes());
+ .copy_to_nonoverlapping(self.table.ctrl(0), self.table.num_ctrl_bytes());
// The cloning of elements may panic, in which case we need
// to make sure we drop only the elements that have been
@@ -1286,7 +1576,7 @@
let mut guard = guard((0, &mut *self), |(index, self_)| {
if mem::needs_drop::<T>() && self_.len() != 0 {
for i in 0..=*index {
- if is_full(*self_.ctrl(i)) {
+ if is_full(*self_.table.ctrl(i)) {
self_.bucket(i).drop();
}
}
@@ -1310,8 +1600,8 @@
// Successfully cloned all items, no need to clean up.
mem::forget(guard);
- self.items = source.items;
- self.growth_left = source.growth_left;
+ self.table.items = source.table.items;
+ self.table.growth_left = source.table.growth_left;
}
/// Variant of `clone_from` to use when a hasher is available.
@@ -1321,8 +1611,8 @@
// elements one by one. We don't do this if we have the same number of
// buckets as the source since we can just copy the contents directly
// in that case.
- if self.buckets() != source.buckets()
- && bucket_mask_to_capacity(self.bucket_mask) >= source.len()
+ if self.table.buckets() != source.table.buckets()
+ && bucket_mask_to_capacity(self.table.bucket_mask) >= source.len()
{
self.clear();
@@ -1343,8 +1633,7 @@
// - there are no DELETED entries.
// - we know there is enough space in the table.
// - all elements are unique.
- let index = guard_self.find_insert_slot(hash);
- guard_self.set_ctrl(index, h2(hash));
+ let (index, _) = guard_self.table.prepare_insert_slot(hash);
guard_self.bucket(index).write(item);
}
}
@@ -1352,53 +1641,52 @@
// Successfully cloned all items, no need to clean up.
mem::forget(guard_self);
- self.items = source.items;
- self.growth_left -= source.items;
+ self.table.items = source.table.items;
+ self.table.growth_left -= source.table.items;
} else {
self.clone_from(source);
}
}
}
+impl<T, A: Allocator + Clone + Default> Default for RawTable<T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn default() -> Self {
+ Self::new_in(Default::default())
+ }
+}
+
#[cfg(feature = "nightly")]
-unsafe impl<#[may_dangle] T> Drop for RawTable<T> {
+unsafe impl<#[may_dangle] T, A: Allocator + Clone> Drop for RawTable<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
- if !self.is_empty_singleton() {
+ if !self.table.is_empty_singleton() {
unsafe {
- if mem::needs_drop::<T>() && self.len() != 0 {
- for item in self.iter() {
- item.drop();
- }
- }
+ self.drop_elements();
self.free_buckets();
}
}
}
}
#[cfg(not(feature = "nightly"))]
-impl<T> Drop for RawTable<T> {
+impl<T, A: Allocator + Clone> Drop for RawTable<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
- if !self.is_empty_singleton() {
+ if !self.table.is_empty_singleton() {
unsafe {
- if mem::needs_drop::<T>() && self.len() != 0 {
- for item in self.iter() {
- item.drop();
- }
- }
+ self.drop_elements();
self.free_buckets();
}
}
}
}
-impl<T> IntoIterator for RawTable<T> {
+impl<T, A: Allocator + Clone> IntoIterator for RawTable<T, A> {
type Item = T;
- type IntoIter = RawIntoIter<T>;
+ type IntoIter = RawIntoIter<T, A>;
#[cfg_attr(feature = "inline-more", inline)]
- fn into_iter(self) -> RawIntoIter<T> {
+ fn into_iter(self) -> RawIntoIter<T, A> {
unsafe {
let iter = self.iter();
self.into_iter_from(iter)
@@ -1681,6 +1969,14 @@
}
}
}
+
+ unsafe fn drop_elements(&mut self) {
+ if mem::needs_drop::<T>() && self.len() != 0 {
+ for item in self {
+ item.drop();
+ }
+ }
+ }
}
impl<T> Clone for RawIter<T> {
@@ -1720,62 +2016,55 @@
impl<T> FusedIterator for RawIter<T> {}
/// Iterator which consumes a table and returns elements.
-pub struct RawIntoIter<T> {
+pub struct RawIntoIter<T, A: Allocator + Clone = Global> {
iter: RawIter<T>,
- alloc: Option<(NonNull<u8>, Layout)>,
+ allocation: Option<(NonNull<u8>, Layout)>,
marker: PhantomData<T>,
+ alloc: A,
}
-impl<T> RawIntoIter<T> {
+impl<T, A: Allocator + Clone> RawIntoIter<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter(&self) -> RawIter<T> {
self.iter.clone()
}
}
-unsafe impl<T> Send for RawIntoIter<T> where T: Send {}
-unsafe impl<T> Sync for RawIntoIter<T> where T: 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> Drop for RawIntoIter<T> {
+unsafe impl<#[may_dangle] T, A: Allocator + Clone> Drop for RawIntoIter<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
unsafe {
// Drop all remaining elements
- if mem::needs_drop::<T>() && self.iter.len() != 0 {
- while let Some(item) = self.iter.next() {
- item.drop();
- }
- }
+ self.iter.drop_elements();
// Free the table
- if let Some((ptr, layout)) = self.alloc {
- dealloc(ptr.as_ptr(), layout);
+ if let Some((ptr, layout)) = self.allocation {
+ self.alloc.deallocate(ptr, layout);
}
}
}
}
#[cfg(not(feature = "nightly"))]
-impl<T> Drop for RawIntoIter<T> {
+impl<T, A: Allocator + Clone> Drop for RawIntoIter<T, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
unsafe {
// Drop all remaining elements
- if mem::needs_drop::<T>() && self.iter.len() != 0 {
- while let Some(item) = self.iter.next() {
- item.drop();
- }
- }
+ self.iter.drop_elements();
// Free the table
- if let Some((ptr, layout)) = self.alloc {
- dealloc(ptr.as_ptr(), layout);
+ if let Some((ptr, layout)) = self.allocation {
+ self.alloc.deallocate(ptr, layout);
}
}
}
}
-impl<T> Iterator for RawIntoIter<T> {
+impl<T, A: Allocator + Clone> Iterator for RawIntoIter<T, A> {
type Item = T;
#[cfg_attr(feature = "inline-more", inline)]
@@ -1789,44 +2078,40 @@
}
}
-impl<T> ExactSizeIterator for RawIntoIter<T> {}
-impl<T> FusedIterator for RawIntoIter<T> {}
+impl<T, A: Allocator + Clone> ExactSizeIterator for RawIntoIter<T, A> {}
+impl<T, A: Allocator + Clone> FusedIterator for RawIntoIter<T, A> {}
/// Iterator which consumes elements without freeing the table storage.
-pub struct RawDrain<'a, T> {
+pub struct RawDrain<'a, T, A: Allocator + Clone = Global> {
iter: RawIter<T>,
// The table is moved into the iterator for the duration of the drain. This
// ensures that an empty table is left if the drain iterator is leaked
// without dropping.
- table: ManuallyDrop<RawTable<T>>,
- orig_table: NonNull<RawTable<T>>,
+ table: ManuallyDrop<RawTable<T, A>>,
+ orig_table: NonNull<RawTable<T, A>>,
// We don't use a &'a mut RawTable<T> because we want RawDrain to be
// covariant over T.
- marker: PhantomData<&'a RawTable<T>>,
+ marker: PhantomData<&'a RawTable<T, A>>,
}
-impl<T> RawDrain<'_, T> {
+impl<T, A: Allocator + Clone> RawDrain<'_, T, A> {
#[cfg_attr(feature = "inline-more", inline)]
pub fn iter(&self) -> RawIter<T> {
self.iter.clone()
}
}
-unsafe impl<T> Send for RawDrain<'_, T> where T: Send {}
-unsafe impl<T> Sync for RawDrain<'_, T> where T: 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> Drop for RawDrain<'_, T> {
+impl<T, A: Allocator + Clone> Drop for RawDrain<'_, T, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn drop(&mut self) {
unsafe {
// Drop all remaining elements. Note that this may panic.
- if mem::needs_drop::<T>() && self.iter.len() != 0 {
- while let Some(item) = self.iter.next() {
- item.drop();
- }
- }
+ self.iter.drop_elements();
// Reset the contents of the table now that all elements have been
// dropped.
@@ -1840,7 +2125,7 @@
}
}
-impl<T> Iterator for RawDrain<'_, T> {
+impl<T, A: Allocator + Clone> Iterator for RawDrain<'_, T, A> {
type Item = T;
#[cfg_attr(feature = "inline-more", inline)]
@@ -1857,14 +2142,19 @@
}
}
-impl<T> ExactSizeIterator for RawDrain<'_, T> {}
-impl<T> FusedIterator for RawDrain<'_, T> {}
+impl<T, A: Allocator + Clone> ExactSizeIterator for RawDrain<'_, T, A> {}
+impl<T, A: Allocator + Clone> FusedIterator for RawDrain<'_, T, A> {}
/// Iterator over occupied buckets that could match a given hash.
///
/// In rare cases, the iterator may return a bucket with a different hash.
-pub struct RawIterHash<'a, T> {
- table: &'a RawTable<T>,
+pub struct RawIterHash<'a, T, A: Allocator + Clone = Global> {
+ inner: RawIterHashInner<'a, A>,
+ _marker: PhantomData<T>,
+}
+
+struct RawIterHashInner<'a, A: Allocator + Clone> {
+ table: &'a RawTableInner<A>,
// The top 7 bits of the hash.
h2_hash: u8,
@@ -1872,28 +2162,34 @@
// The sequence of groups to probe in the search.
probe_seq: ProbeSeq,
- // The current group and its position.
- pos: usize,
group: Group,
// The elements within the group with a matching h2-hash.
bitmask: BitMaskIter,
}
-impl<'a, T> RawIterHash<'a, T> {
- fn new(table: &'a RawTable<T>, hash: u64) -> Self {
+impl<'a, T, A: Allocator + Clone> RawIterHash<'a, T, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn new(table: &'a RawTable<T, A>, hash: u64) -> Self {
+ RawIterHash {
+ inner: RawIterHashInner::new(&table.table, hash),
+ _marker: PhantomData,
+ }
+ }
+}
+impl<'a, A: Allocator + Clone> RawIterHashInner<'a, A> {
+ #[cfg_attr(feature = "inline-more", inline)]
+ fn new(table: &'a RawTableInner<A>, hash: u64) -> Self {
unsafe {
let h2_hash = h2(hash);
- let mut probe_seq = table.probe_seq(hash);
- let pos = probe_seq.next().unwrap();
- let group = Group::load(table.ctrl(pos));
+ let probe_seq = table.probe_seq(hash);
+ let group = Group::load(table.ctrl(probe_seq.pos));
let bitmask = group.match_byte(h2_hash).into_iter();
- RawIterHash {
+ RawIterHashInner {
table,
h2_hash,
probe_seq,
- pos,
group,
bitmask,
}
@@ -1901,24 +2197,66 @@
}
}
-impl<'a, T> Iterator for RawIterHash<'a, T> {
+impl<'a, T, A: Allocator + Clone> Iterator for RawIterHash<'a, T, A> {
type Item = Bucket<T>;
fn next(&mut self) -> Option<Bucket<T>> {
unsafe {
+ match self.inner.next() {
+ Some(index) => Some(self.inner.table.bucket(index)),
+ None => None,
+ }
+ }
+ }
+}
+
+impl<'a, A: Allocator + Clone> Iterator for RawIterHashInner<'a, A> {
+ type Item = usize;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ unsafe {
loop {
if let Some(bit) = self.bitmask.next() {
- let index = (self.pos + bit) & self.table.bucket_mask;
- let bucket = self.table.bucket(index);
- return Some(bucket);
+ let index = (self.probe_seq.pos + bit) & self.table.bucket_mask;
+ return Some(index);
}
if likely(self.group.match_empty().any_bit_set()) {
return None;
}
- self.pos = self.probe_seq.next().unwrap();
- self.group = Group::load(self.table.ctrl(self.pos));
+ self.probe_seq.move_next(self.table.bucket_mask);
+ self.group = Group::load(self.table.ctrl(self.probe_seq.pos));
self.bitmask = self.group.match_byte(self.h2_hash).into_iter();
}
}
}
}
+
+#[cfg(test)]
+mod test_map {
+ use super::*;
+
+ #[test]
+ fn rehash() {
+ let mut table = RawTable::new();
+ let hasher = |i: &u64| *i;
+ for i in 0..100 {
+ table.insert(i, i, hasher);
+ }
+
+ for i in 0..100 {
+ unsafe {
+ assert_eq!(table.find(i, |x| *x == i).map(|b| b.read()), Some(i));
+ }
+ assert!(table.find(i + 100, |x| *x == i + 100).is_none());
+ }
+
+ table.rehash_in_place(hasher);
+
+ for i in 0..100 {
+ unsafe {
+ assert_eq!(table.find(i, |x| *x == i).map(|b| b.read()), Some(i));
+ }
+ assert!(table.find(i + 100, |x| *x == i + 100).is_none());
+ }
+ }
+}
diff --git a/src/raw/sse2.rs b/src/raw/sse2.rs
index a27bc09..eed9684 100644
--- a/src/raw/sse2.rs
+++ b/src/raw/sse2.rs
@@ -28,12 +28,13 @@
/// value for an empty hash table.
///
/// This is guaranteed to be aligned to the group size.
+ #[allow(clippy::items_after_statements)]
pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
#[repr(C)]
struct AlignedBytes {
_align: [Group; 0],
bytes: [u8; Group::WIDTH],
- };
+ }
const ALIGNED_BYTES: AlignedBytes = AlignedBytes {
_align: [],
bytes: [EMPTY; Group::WIDTH],
@@ -45,7 +46,7 @@
#[inline]
#[allow(clippy::cast_ptr_alignment)] // unaligned load
pub unsafe fn load(ptr: *const u8) -> Self {
- Group(x86::_mm_loadu_si128(ptr as *const _))
+ Group(x86::_mm_loadu_si128(ptr.cast()))
}
/// Loads a group of bytes starting at the given address, which must be
@@ -55,7 +56,7 @@
pub unsafe fn load_aligned(ptr: *const u8) -> Self {
// FIXME: use align_offset once it stabilizes
debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
- Group(x86::_mm_load_si128(ptr as *const _))
+ Group(x86::_mm_load_si128(ptr.cast()))
}
/// Stores the group of bytes to the given address, which must be
@@ -65,7 +66,7 @@
pub unsafe fn store_aligned(self, ptr: *mut u8) {
// FIXME: use align_offset once it stabilizes
debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
- x86::_mm_store_si128(ptr as *mut _, self.0);
+ x86::_mm_store_si128(ptr.cast(), self.0);
}
/// Returns a `BitMask` indicating all bytes in the group which have
diff --git a/src/rustc_entry.rs b/src/rustc_entry.rs
index b6ea7bc..1793c4a 100644
--- a/src/rustc_entry.rs
+++ b/src/rustc_entry.rs
@@ -1,14 +1,15 @@
use self::RustcEntry::*;
-use crate::map::{make_hash, Drain, HashMap, IntoIter, Iter, IterMut};
-use crate::raw::{Bucket, RawTable};
+use crate::map::{make_insert_hash, Drain, HashMap, IntoIter, Iter, IterMut};
+use crate::raw::{Allocator, Bucket, Global, RawTable};
use core::fmt::{self, Debug};
use core::hash::{BuildHasher, Hash};
use core::mem;
-impl<K, V, S> HashMap<K, V, S>
+impl<K, V, S, A> HashMap<K, V, S, A>
where
K: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
/// Gets the given key's corresponding entry in the map for in-place manipulation.
///
@@ -30,8 +31,8 @@
/// assert_eq!(letters.get(&'y'), None);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn rustc_entry(&mut self, key: K) -> RustcEntry<'_, K, V> {
- let hash = make_hash(&self.hash_builder, &key);
+ pub fn rustc_entry(&mut self, key: K) -> RustcEntry<'_, K, V, A> {
+ let hash = make_insert_hash(&self.hash_builder, &key);
if let Some(elem) = self.table.find(hash, |q| q.0.eq(&key)) {
RustcEntry::Occupied(RustcOccupiedEntry {
key: Some(key),
@@ -59,15 +60,18 @@
///
/// [`HashMap`]: struct.HashMap.html
/// [`entry`]: struct.HashMap.html#method.rustc_entry
-pub enum RustcEntry<'a, K, V> {
+pub enum RustcEntry<'a, K, V, A = Global>
+where
+ A: Allocator + Clone,
+{
/// An occupied entry.
- Occupied(RustcOccupiedEntry<'a, K, V>),
+ Occupied(RustcOccupiedEntry<'a, K, V, A>),
/// A vacant entry.
- Vacant(RustcVacantEntry<'a, K, V>),
+ Vacant(RustcVacantEntry<'a, K, V, A>),
}
-impl<K: Debug, V: Debug> Debug for RustcEntry<'_, K, V> {
+impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for RustcEntry<'_, K, V, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match *self {
Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
@@ -80,26 +84,31 @@
/// It is part of the [`RustcEntry`] enum.
///
/// [`RustcEntry`]: enum.RustcEntry.html
-pub struct RustcOccupiedEntry<'a, K, V> {
+pub struct RustcOccupiedEntry<'a, K, V, A = Global>
+where
+ A: Allocator + Clone,
+{
key: Option<K>,
elem: Bucket<(K, V)>,
- table: &'a mut RawTable<(K, V)>,
+ table: &'a mut RawTable<(K, V), A>,
}
-unsafe impl<K, V> Send for RustcOccupiedEntry<'_, K, V>
+unsafe impl<K, V, A> Send for RustcOccupiedEntry<'_, K, V, A>
where
K: Send,
V: Send,
+ A: Allocator + Clone + Send,
{
}
-unsafe impl<K, V> Sync for RustcOccupiedEntry<'_, K, V>
+unsafe impl<K, V, A> Sync for RustcOccupiedEntry<'_, K, V, A>
where
K: Sync,
V: Sync,
+ A: Allocator + Clone + Sync,
{
}
-impl<K: Debug, V: Debug> Debug for RustcOccupiedEntry<'_, K, V> {
+impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for RustcOccupiedEntry<'_, K, V, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("OccupiedEntry")
.field("key", self.key())
@@ -112,19 +121,22 @@
/// It is part of the [`RustcEntry`] enum.
///
/// [`RustcEntry`]: enum.RustcEntry.html
-pub struct RustcVacantEntry<'a, K, V> {
+pub struct RustcVacantEntry<'a, K, V, A = Global>
+where
+ A: Allocator + Clone,
+{
hash: u64,
key: K,
- table: &'a mut RawTable<(K, V)>,
+ table: &'a mut RawTable<(K, V), A>,
}
-impl<K: Debug, V> Debug for RustcVacantEntry<'_, K, V> {
+impl<K: Debug, V, A: Allocator + Clone> Debug for RustcVacantEntry<'_, K, V, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("VacantEntry").field(self.key()).finish()
}
}
-impl<'a, K, V> RustcEntry<'a, K, V> {
+impl<'a, K, V, A: Allocator + Clone> RustcEntry<'a, K, V, A> {
/// Sets the value of the entry, and returns a RustcOccupiedEntry.
///
/// # Examples
@@ -137,7 +149,7 @@
///
/// assert_eq!(entry.key(), &"horseyland");
/// ```
- pub fn insert(self, value: V) -> RustcOccupiedEntry<'a, K, V> {
+ pub fn insert(self, value: V) -> RustcOccupiedEntry<'a, K, V, A> {
match self {
Vacant(entry) => entry.insert_entry(value),
Occupied(mut entry) => {
@@ -253,7 +265,7 @@
}
}
-impl<'a, K, V: Default> RustcEntry<'a, K, V> {
+impl<'a, K, V: Default, A: Allocator + Clone> RustcEntry<'a, K, V, 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.
///
@@ -281,7 +293,7 @@
}
}
-impl<'a, K, V> RustcOccupiedEntry<'a, K, V> {
+impl<'a, K, V, A: Allocator + Clone> RustcOccupiedEntry<'a, K, V, A> {
/// Gets a reference to the key in the entry.
///
/// # Examples
@@ -508,7 +520,7 @@
}
}
-impl<'a, K, V> RustcVacantEntry<'a, K, V> {
+impl<'a, K, V, A: Allocator + Clone> RustcVacantEntry<'a, K, V, A> {
/// Gets a reference to the key that would be used when inserting a value
/// through the `RustcVacantEntry`.
///
@@ -583,7 +595,7 @@
/// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn insert_entry(self, value: V) -> RustcOccupiedEntry<'a, K, V> {
+ pub fn insert_entry(self, value: V) -> RustcOccupiedEntry<'a, K, V, A> {
let bucket = self.table.insert_no_grow(self.hash, (self.key, value));
RustcOccupiedEntry {
key: None,
diff --git a/src/scopeguard.rs b/src/scopeguard.rs
index 32c9694..4e9bf04 100644
--- a/src/scopeguard.rs
+++ b/src/scopeguard.rs
@@ -9,7 +9,7 @@
value: T,
}
-#[cfg_attr(feature = "inline-more", inline)]
+#[inline]
pub fn guard<T, F>(value: T, dropfn: F) -> ScopeGuard<T, F>
where
F: FnMut(&mut T),
@@ -22,7 +22,7 @@
F: FnMut(&mut T),
{
type Target = T;
- #[cfg_attr(feature = "inline-more", inline)]
+ #[inline]
fn deref(&self) -> &T {
&self.value
}
@@ -32,7 +32,7 @@
where
F: FnMut(&mut T),
{
- #[cfg_attr(feature = "inline-more", inline)]
+ #[inline]
fn deref_mut(&mut self) -> &mut T {
&mut self.value
}
@@ -42,7 +42,7 @@
where
F: FnMut(&mut T),
{
- #[cfg_attr(feature = "inline-more", inline)]
+ #[inline]
fn drop(&mut self) {
(self.dropfn)(&mut self.value)
}
diff --git a/src/set.rs b/src/set.rs
index b8460fd..d59183b 100644
--- a/src/set.rs
+++ b/src/set.rs
@@ -8,6 +8,7 @@
use core::ops::{BitAnd, BitOr, BitXor, Sub};
use super::map::{self, ConsumeAllOnDrop, DefaultHashBuilder, DrainFilterInner, HashMap, Keys};
+use crate::raw::{Allocator, Global};
// Future Optimization (FIXME!)
// =============================
@@ -71,7 +72,7 @@
/// ```
///
/// The easiest way to use `HashSet` with a custom type is to derive
-/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`], this will in the
+/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`]. This will in the
/// future be implied by [`Eq`].
///
/// ```
@@ -111,11 +112,11 @@
/// [`HashMap`]: struct.HashMap.html
/// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
/// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
-pub struct HashSet<T, S = DefaultHashBuilder> {
- pub(crate) map: HashMap<T, (), S>,
+pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator + Clone = Global> {
+ pub(crate) map: HashMap<T, (), S, A>,
}
-impl<T: Clone, S: Clone> Clone for HashSet<T, S> {
+impl<T: Clone, S: Clone, A: Allocator + Clone> Clone for HashSet<T, S, A> {
fn clone(&self) -> Self {
HashSet {
map: self.map.clone(),
@@ -167,73 +168,47 @@
}
}
-impl<T, S> HashSet<T, S> {
- /// Creates a new empty hash set which will use the given hasher to hash
- /// keys.
+#[cfg(feature = "ahash")]
+impl<T: Hash + Eq, A: Allocator + Clone> HashSet<T, DefaultHashBuilder, A> {
+ /// Creates an empty `HashSet`.
///
- /// The hash set is also created with the default initial capacity.
- ///
- /// Warning: `hasher` is normally randomly generated, and
- /// is designed to allow `HashSet`s to be resistant to attacks that
- /// cause many collisions and very poor performance. Setting it
- /// manually using this function can expose a DoS attack vector.
- ///
- /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
- /// the HashMap to be useful, see its documentation for details.
- ///
+ /// The hash set is initially created with a capacity of 0, so it will not allocate until it
+ /// is first inserted into.
///
/// # Examples
///
/// ```
/// use hashbrown::HashSet;
- /// use hashbrown::hash_map::DefaultHashBuilder;
- ///
- /// let s = DefaultHashBuilder::default();
- /// let mut set = HashSet::with_hasher(s);
- /// set.insert(2);
+ /// let set: HashSet<i32> = HashSet::new();
/// ```
- ///
- /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
#[cfg_attr(feature = "inline-more", inline)]
- pub const fn with_hasher(hasher: S) -> Self {
+ pub fn new_in(alloc: A) -> Self {
Self {
- map: HashMap::with_hasher(hasher),
+ map: HashMap::new_in(alloc),
}
}
- /// Creates an empty `HashSet` with the specified capacity, using
- /// `hasher` to hash the keys.
+ /// Creates an empty `HashSet` with the specified capacity.
///
/// The hash set will be able to hold at least `capacity` elements without
/// reallocating. If `capacity` is 0, the hash set will not allocate.
///
- /// Warning: `hasher` is normally randomly generated, and
- /// is designed to allow `HashSet`s to be resistant to attacks that
- /// cause many collisions and very poor performance. Setting it
- /// manually using this function can expose a DoS attack vector.
- ///
- /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
- /// the HashMap to be useful, see its documentation for details.
- ///
/// # Examples
///
/// ```
/// use hashbrown::HashSet;
- /// use hashbrown::hash_map::DefaultHashBuilder;
- ///
- /// let s = DefaultHashBuilder::default();
- /// let mut set = HashSet::with_capacity_and_hasher(10, s);
- /// set.insert(1);
+ /// let set: HashSet<i32> = HashSet::with_capacity(10);
+ /// assert!(set.capacity() >= 10);
/// ```
- ///
- /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
#[cfg_attr(feature = "inline-more", inline)]
- pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
+ pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
Self {
- map: HashMap::with_capacity_and_hasher(capacity, hasher),
+ map: HashMap::with_capacity_in(capacity, alloc),
}
}
+}
+impl<T, S, A: Allocator + Clone> HashSet<T, S, A> {
/// Returns the number of elements the set can hold without reallocating.
///
/// # Examples
@@ -323,7 +298,7 @@
/// assert!(set.is_empty());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn drain(&mut self) -> Drain<'_, T> {
+ pub fn drain(&mut self) -> Drain<'_, T, A> {
Drain {
iter: self.map.drain(),
}
@@ -376,7 +351,7 @@
/// assert_eq!(odds, vec![1, 3, 5, 7]);
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, T, F>
+ pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, T, F, A>
where
F: FnMut(&T) -> bool,
{
@@ -405,6 +380,134 @@
pub fn clear(&mut self) {
self.map.clear()
}
+}
+
+impl<T, S> HashSet<T, S, Global> {
+ /// Creates a new empty hash set which will use the given hasher to hash
+ /// keys.
+ ///
+ /// The hash set is also created with the default initial capacity.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
+ /// the HashMap to be useful, see its documentation for details.
+ ///
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_hasher(s);
+ /// set.insert(2);
+ /// ```
+ ///
+ /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub const fn with_hasher(hasher: S) -> Self {
+ Self {
+ map: HashMap::with_hasher(hasher),
+ }
+ }
+
+ /// Creates an empty `HashSet` with the specified capacity, using
+ /// `hasher` to hash the keys.
+ ///
+ /// The hash set will be able to hold at least `capacity` elements without
+ /// reallocating. If `capacity` is 0, the hash set will not allocate.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// The `hash_builder` passed should implement the [`BuildHasher`] trait for
+ /// the HashMap to be useful, see its documentation for details.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_capacity_and_hasher(10, s);
+ /// set.insert(1);
+ /// ```
+ ///
+ /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
+ Self {
+ map: HashMap::with_capacity_and_hasher(capacity, hasher),
+ }
+ }
+}
+
+impl<T, S, A> HashSet<T, S, A>
+where
+ A: Allocator + Clone,
+{
+ /// Creates a new empty hash set which will use the given hasher to hash
+ /// keys.
+ ///
+ /// The hash set is also created with the default initial capacity.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_hasher(s);
+ /// set.insert(2);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
+ Self {
+ map: HashMap::with_hasher_in(hasher, alloc),
+ }
+ }
+
+ /// Creates an empty `HashSet` with the specified capacity, using
+ /// `hasher` to hash the keys.
+ ///
+ /// The hash set will be able to hold at least `capacity` elements without
+ /// reallocating. If `capacity` is 0, the hash set will not allocate.
+ ///
+ /// Warning: `hasher` is normally randomly generated, and
+ /// is designed to allow `HashSet`s to be resistant to attacks that
+ /// cause many collisions and very poor performance. Setting it
+ /// manually using this function can expose a DoS attack vector.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use hashbrown::HashSet;
+ /// use hashbrown::hash_map::DefaultHashBuilder;
+ ///
+ /// let s = DefaultHashBuilder::default();
+ /// let mut set = HashSet::with_capacity_and_hasher(10, s);
+ /// set.insert(1);
+ /// ```
+ #[cfg_attr(feature = "inline-more", inline)]
+ pub fn with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self {
+ Self {
+ map: HashMap::with_capacity_and_hasher_in(capacity, hasher, alloc),
+ }
+ }
/// Returns a reference to the set's [`BuildHasher`].
///
@@ -426,10 +529,11 @@
}
}
-impl<T, S> HashSet<T, S>
+impl<T, S, A> HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
/// Reserves capacity for at least `additional` more elements to be inserted
/// in the `HashSet`. The collection may reserve more space to avoid
@@ -544,7 +648,7 @@
/// assert_eq!(diff, [4].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S> {
+ pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S, A> {
Difference {
iter: self.iter(),
other,
@@ -573,7 +677,7 @@
/// assert_eq!(diff1, [1, 4].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S> {
+ pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S, A> {
SymmetricDifference {
iter: self.difference(other).chain(other.difference(self)),
}
@@ -598,7 +702,7 @@
/// assert_eq!(intersection, [2, 3].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S> {
+ pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S, A> {
let (smaller, larger) = if self.len() <= other.len() {
(self, other)
} else {
@@ -629,8 +733,10 @@
/// assert_eq!(union, [1, 2, 3, 4].iter().collect());
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S> {
- let (smaller, larger) = if self.len() >= other.len() {
+ pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S, A> {
+ // We'll iterate one set in full, and only the remaining difference from the other.
+ // Use the smaller set for the difference in order to reduce hash lookups.
+ let (smaller, larger) = if self.len() <= other.len() {
(self, other)
} else {
(other, self)
@@ -967,10 +1073,11 @@
}
}
-impl<T, S> PartialEq for HashSet<T, S>
+impl<T, S, A> PartialEq for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn eq(&self, other: &Self) -> bool {
if self.len() != other.len() {
@@ -981,40 +1088,53 @@
}
}
-impl<T, S> Eq for HashSet<T, S>
+impl<T, S, A> Eq for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for HashSet<T, S>
+impl<T, S, A> fmt::Debug for HashSet<T, S, A>
where
T: Eq + Hash + fmt::Debug,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_set().entries(self.iter()).finish()
}
}
-impl<T, S> FromIterator<T> for HashSet<T, S>
+impl<T, S, A> From<HashMap<T, (), S, A>> for HashSet<T, S, A>
+where
+ A: Allocator + Clone,
+{
+ fn from(map: HashMap<T, (), S, A>) -> Self {
+ Self { map }
+ }
+}
+
+impl<T, S, A> FromIterator<T> for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher + Default,
+ A: Default + Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
- let mut set = Self::with_hasher(Default::default());
+ let mut set = Self::with_hasher_in(Default::default(), Default::default());
set.extend(iter);
set
}
}
-impl<T, S> Extend<T> for HashSet<T, S>
+impl<T, S, A> Extend<T> for HashSet<T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
@@ -1034,10 +1154,11 @@
}
}
-impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
+impl<'a, T, S, A> Extend<&'a T> for HashSet<T, S, A>
where
T: 'a + Eq + Hash + Copy,
S: BuildHasher,
+ A: Allocator + Clone,
{
#[cfg_attr(feature = "inline-more", inline)]
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
@@ -1057,9 +1178,10 @@
}
}
-impl<T, S> Default for HashSet<T, S>
+impl<T, S, A> Default for HashSet<T, S, A>
where
S: Default,
+ A: Default + Allocator + Clone,
{
/// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
#[cfg_attr(feature = "inline-more", inline)]
@@ -1070,10 +1192,11 @@
}
}
-impl<T, S> BitOr<&HashSet<T, S>> for &HashSet<T, S>
+impl<T, S, A> BitOr<&HashSet<T, S, A>> for &HashSet<T, S, A>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
+ A: Allocator + Clone,
{
type Output = HashSet<T, S>;
@@ -1097,15 +1220,16 @@
/// }
/// assert_eq!(i, expected.len());
/// ```
- fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ fn bitor(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
self.union(rhs).cloned().collect()
}
}
-impl<T, S> BitAnd<&HashSet<T, S>> for &HashSet<T, S>
+impl<T, S, A> BitAnd<&HashSet<T, S, A>> for &HashSet<T, S, A>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
+ A: Allocator + Clone,
{
type Output = HashSet<T, S>;
@@ -1129,7 +1253,7 @@
/// }
/// assert_eq!(i, expected.len());
/// ```
- fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
+ fn bitand(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S> {
self.intersection(rhs).cloned().collect()
}
}
@@ -1216,8 +1340,8 @@
///
/// [`HashSet`]: struct.HashSet.html
/// [`into_iter`]: struct.HashSet.html#method.into_iter
-pub struct IntoIter<K> {
- iter: map::IntoIter<K, ()>,
+pub struct IntoIter<K, A: Allocator + Clone = Global> {
+ iter: map::IntoIter<K, (), A>,
}
/// A draining iterator over the items of a `HashSet`.
@@ -1227,8 +1351,8 @@
///
/// [`HashSet`]: struct.HashSet.html
/// [`drain`]: struct.HashSet.html#method.drain
-pub struct Drain<'a, K> {
- iter: map::Drain<'a, K, ()>,
+pub struct Drain<'a, K, A: Allocator + Clone = Global> {
+ iter: map::Drain<'a, K, (), A>,
}
/// A draining iterator over entries of a `HashSet` which don't satisfy the predicate `f`.
@@ -1238,12 +1362,12 @@
///
/// [`drain_filter`]: struct.HashSet.html#method.drain_filter
/// [`HashSet`]: struct.HashSet.html
-pub struct DrainFilter<'a, K, F>
+pub struct DrainFilter<'a, K, F, A: Allocator + Clone = Global>
where
F: FnMut(&K) -> bool,
{
f: F,
- inner: DrainFilterInner<'a, K, ()>,
+ inner: DrainFilterInner<'a, K, (), A>,
}
/// A lazy iterator producing elements in the intersection of `HashSet`s.
@@ -1253,11 +1377,11 @@
///
/// [`HashSet`]: struct.HashSet.html
/// [`intersection`]: struct.HashSet.html#method.intersection
-pub struct Intersection<'a, T, S> {
+pub struct Intersection<'a, T, S, A: Allocator + Clone = Global> {
// iterator of the first set
iter: Iter<'a, T>,
// the second set
- other: &'a HashSet<T, S>,
+ other: &'a HashSet<T, S, A>,
}
/// A lazy iterator producing elements in the difference of `HashSet`s.
@@ -1267,11 +1391,11 @@
///
/// [`HashSet`]: struct.HashSet.html
/// [`difference`]: struct.HashSet.html#method.difference
-pub struct Difference<'a, T, S> {
+pub struct Difference<'a, T, S, A: Allocator + Clone = Global> {
// iterator of the first set
iter: Iter<'a, T>,
// the second set
- other: &'a HashSet<T, S>,
+ other: &'a HashSet<T, S, A>,
}
/// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
@@ -1281,8 +1405,8 @@
///
/// [`HashSet`]: struct.HashSet.html
/// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference
-pub struct SymmetricDifference<'a, T, S> {
- iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
+pub struct SymmetricDifference<'a, T, S, A: Allocator + Clone = Global> {
+ iter: Chain<Difference<'a, T, S, A>, Difference<'a, T, S, A>>,
}
/// A lazy iterator producing elements in the union of `HashSet`s.
@@ -1292,11 +1416,11 @@
///
/// [`HashSet`]: struct.HashSet.html
/// [`union`]: struct.HashSet.html#method.union
-pub struct Union<'a, T, S> {
- iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
+pub struct Union<'a, T, S, A: Allocator + Clone = Global> {
+ iter: Chain<Iter<'a, T>, Difference<'a, T, S, A>>,
}
-impl<'a, T, S> IntoIterator for &'a HashSet<T, S> {
+impl<'a, T, S, A: Allocator + Clone> IntoIterator for &'a HashSet<T, S, A> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
@@ -1306,9 +1430,9 @@
}
}
-impl<T, S> IntoIterator for HashSet<T, S> {
+impl<T, S, A: Allocator + Clone> IntoIterator for HashSet<T, S, A> {
type Item = T;
- type IntoIter = IntoIter<T>;
+ type IntoIter = IntoIter<T, A>;
/// Creates a consuming iterator, that is, one that moves each value out
/// of the set in arbitrary order. The set cannot be used after calling
@@ -1331,7 +1455,7 @@
/// }
/// ```
#[cfg_attr(feature = "inline-more", inline)]
- fn into_iter(self) -> IntoIter<T> {
+ fn into_iter(self) -> IntoIter<T, A> {
IntoIter {
iter: self.map.into_iter(),
}
@@ -1372,7 +1496,7 @@
}
}
-impl<K> Iterator for IntoIter<K> {
+impl<K, A: Allocator + Clone> Iterator for IntoIter<K, A> {
type Item = K;
#[cfg_attr(feature = "inline-more", inline)]
@@ -1388,22 +1512,22 @@
self.iter.size_hint()
}
}
-impl<K> ExactSizeIterator for IntoIter<K> {
+impl<K, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.iter.len()
}
}
-impl<K> FusedIterator for IntoIter<K> {}
+impl<K, A: Allocator + Clone> FusedIterator for IntoIter<K, A> {}
-impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
+impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoIter<K, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let entries_iter = self.iter.iter().map(|(k, _)| k);
f.debug_list().entries(entries_iter).finish()
}
}
-impl<K> Iterator for Drain<'_, K> {
+impl<K, A: Allocator + Clone> Iterator for Drain<'_, K, A> {
type Item = K;
#[cfg_attr(feature = "inline-more", inline)]
@@ -1419,22 +1543,22 @@
self.iter.size_hint()
}
}
-impl<K> ExactSizeIterator for Drain<'_, K> {
+impl<K, A: Allocator + Clone> ExactSizeIterator for Drain<'_, K, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn len(&self) -> usize {
self.iter.len()
}
}
-impl<K> FusedIterator for Drain<'_, K> {}
+impl<K, A: Allocator + Clone> FusedIterator for Drain<'_, K, A> {}
-impl<K: fmt::Debug> fmt::Debug for Drain<'_, K> {
+impl<K: fmt::Debug, A: Allocator + Clone> fmt::Debug for Drain<'_, K, A> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let entries_iter = self.iter.iter().map(|(k, _)| k);
f.debug_list().entries(entries_iter).finish()
}
}
-impl<'a, K, F> Drop for DrainFilter<'a, K, F>
+impl<'a, K, F, A: Allocator + Clone> Drop for DrainFilter<'a, K, F, A>
where
F: FnMut(&K) -> bool,
{
@@ -1448,7 +1572,7 @@
}
}
-impl<K, F> Iterator for DrainFilter<'_, K, F>
+impl<K, F, A: Allocator + Clone> Iterator for DrainFilter<'_, K, F, A>
where
F: FnMut(&K) -> bool,
{
@@ -1467,9 +1591,12 @@
}
}
-impl<K, F> FusedIterator for DrainFilter<'_, K, F> where F: FnMut(&K) -> bool {}
+impl<K, F, A: Allocator + Clone> FusedIterator for DrainFilter<'_, K, F, A> where
+ F: FnMut(&K) -> bool
+{
+}
-impl<T, S> Clone for Intersection<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for Intersection<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Intersection {
@@ -1479,10 +1606,11 @@
}
}
-impl<'a, T, S> Iterator for Intersection<'a, T, S>
+impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1503,24 +1631,26 @@
}
}
-impl<T, S> fmt::Debug for Intersection<'_, T, S>
+impl<T, S, A> fmt::Debug for Intersection<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<T, S> FusedIterator for Intersection<'_, T, S>
+impl<T, S, A> FusedIterator for Intersection<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> Clone for Difference<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for Difference<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Difference {
@@ -1530,10 +1660,11 @@
}
}
-impl<'a, T, S> Iterator for Difference<'a, T, S>
+impl<'a, T, S, A> Iterator for Difference<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1554,24 +1685,26 @@
}
}
-impl<T, S> FusedIterator for Difference<'_, T, S>
+impl<T, S, A> FusedIterator for Difference<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for Difference<'_, T, S>
+impl<T, S, A> fmt::Debug for Difference<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<T, S> Clone for SymmetricDifference<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for SymmetricDifference<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
SymmetricDifference {
@@ -1580,10 +1713,11 @@
}
}
-impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
+impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1597,24 +1731,26 @@
}
}
-impl<T, S> FusedIterator for SymmetricDifference<'_, T, S>
+impl<T, S, A> FusedIterator for SymmetricDifference<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for SymmetricDifference<'_, T, S>
+impl<T, S, A> fmt::Debug for SymmetricDifference<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<T, S> Clone for Union<'_, T, S> {
+impl<T, S, A: Allocator + Clone> Clone for Union<'_, T, S, A> {
#[cfg_attr(feature = "inline-more", inline)]
fn clone(&self) -> Self {
Union {
@@ -1623,27 +1759,30 @@
}
}
-impl<T, S> FusedIterator for Union<'_, T, S>
+impl<T, S, A> FusedIterator for Union<'_, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
}
-impl<T, S> fmt::Debug for Union<'_, T, S>
+impl<T, S, A> fmt::Debug for Union<'_, T, S, A>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
-impl<'a, T, S> Iterator for Union<'a, T, S>
+impl<'a, T, S, A> Iterator for Union<'a, T, S, A>
where
T: Eq + Hash,
S: BuildHasher,
+ A: Allocator + Clone,
{
type Item = &'a T;
@@ -1665,30 +1804,34 @@
fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
v
}
- fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
+ fn into_iter<'new, A: Allocator + Clone>(
+ v: IntoIter<&'static str, A>,
+ ) -> IntoIter<&'new str, A> {
v
}
- fn difference<'a, 'new>(
- v: Difference<'a, &'static str, DefaultHashBuilder>,
- ) -> Difference<'a, &'new str, DefaultHashBuilder> {
+ fn difference<'a, 'new, A: Allocator + Clone>(
+ v: Difference<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> Difference<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn symmetric_difference<'a, 'new>(
- v: SymmetricDifference<'a, &'static str, DefaultHashBuilder>,
- ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder> {
+ fn symmetric_difference<'a, 'new, A: Allocator + Clone>(
+ v: SymmetricDifference<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn intersection<'a, 'new>(
- v: Intersection<'a, &'static str, DefaultHashBuilder>,
- ) -> Intersection<'a, &'new str, DefaultHashBuilder> {
+ fn intersection<'a, 'new, A: Allocator + Clone>(
+ v: Intersection<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> Intersection<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn union<'a, 'new>(
- v: Union<'a, &'static str, DefaultHashBuilder>,
- ) -> Union<'a, &'new str, DefaultHashBuilder> {
+ fn union<'a, 'new, A: Allocator + Clone>(
+ v: Union<'a, &'static str, DefaultHashBuilder, A>,
+ ) -> Union<'a, &'new str, DefaultHashBuilder, A> {
v
}
- fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
+ fn drain<'new, A: Allocator + Clone>(
+ d: Drain<'static, &'static str, A>,
+ ) -> Drain<'new, &'new str, A> {
d
}
}
@@ -1905,6 +2048,23 @@
}
#[test]
+ fn test_from_map() {
+ let mut a = crate::HashMap::new();
+ a.insert(1, ());
+ a.insert(2, ());
+ a.insert(3, ());
+ a.insert(4, ());
+
+ let a: HashSet<_> = a.into();
+
+ assert_eq!(a.len(), 4);
+ assert!(a.contains(&1));
+ assert!(a.contains(&2));
+ assert!(a.contains(&3));
+ assert!(a.contains(&4));
+ }
+
+ #[test]
fn test_from_iter() {
let xs = [1, 2, 2, 3, 4, 5, 6, 7, 8, 9];
@@ -2116,4 +2276,24 @@
set.insert(19);
assert!(set.contains(&19));
}
+
+ #[test]
+ fn rehash_in_place() {
+ let mut set = HashSet::new();
+
+ for i in 0..224 {
+ set.insert(i);
+ }
+
+ assert_eq!(
+ set.capacity(),
+ 224,
+ "The set must be at or close to capacity to trigger a re hashing"
+ );
+
+ for i in 100..1400 {
+ set.remove(&(i - 100));
+ set.insert(i);
+ }
+ }
}
diff --git a/tests/serde.rs b/tests/serde.rs
index 570bf70..a642348 100644
--- a/tests/serde.rs
+++ b/tests/serde.rs
@@ -1,24 +1,24 @@
#![cfg(feature = "serde")]
use core::hash::BuildHasherDefault;
+use fnv::FnvHasher;
use hashbrown::{HashMap, HashSet};
-use rustc_hash::FxHasher;
use serde_test::{assert_tokens, Token};
-// We use FxHash for this test because we rely on the ordering
-type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
-type FxHashSet<T> = HashSet<T, BuildHasherDefault<FxHasher>>;
+// We use FnvHash for this test because we rely on the ordering
+type FnvHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FnvHasher>>;
+type FnvHashSet<T> = HashSet<T, BuildHasherDefault<FnvHasher>>;
#[test]
fn map_serde_tokens_empty() {
- let map = FxHashMap::<char, u32>::default();
+ let map = FnvHashMap::<char, u32>::default();
assert_tokens(&map, &[Token::Map { len: Some(0) }, Token::MapEnd]);
}
#[test]
fn map_serde_tokens() {
- let mut map = FxHashMap::default();
+ let mut map = FnvHashMap::default();
map.insert('b', 20);
map.insert('a', 10);
map.insert('c', 30);
@@ -29,10 +29,10 @@
Token::Map { len: Some(3) },
Token::Char('a'),
Token::I32(10),
- Token::Char('b'),
- Token::I32(20),
Token::Char('c'),
Token::I32(30),
+ Token::Char('b'),
+ Token::I32(20),
Token::MapEnd,
],
);
@@ -40,14 +40,14 @@
#[test]
fn set_serde_tokens_empty() {
- let set = FxHashSet::<u32>::default();
+ let set = FnvHashSet::<u32>::default();
assert_tokens(&set, &[Token::Seq { len: Some(0) }, Token::SeqEnd]);
}
#[test]
fn set_serde_tokens() {
- let mut set = FxHashSet::default();
+ let mut set = FnvHashSet::default();
set.insert(20);
set.insert(10);
set.insert(30);
@@ -56,9 +56,9 @@
&set,
&[
Token::Seq { len: Some(3) },
+ Token::I32(30),
Token::I32(20),
Token::I32(10),
- Token::I32(30),
Token::SeqEnd,
],
);
