diff options
author | Jeffrey Vander Stoep <jeffv@google.com> | 2022-12-16 20:34:26 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2022-12-16 20:34:26 +0000 |
commit | 6e5a0be56336bd29697146229a6ed1c88818d2d5 (patch) | |
tree | 6d41e27eb07b7aec418151342e5cfb8c06902dd6 | |
parent | 52aea43df5d452c9d1e7bfdba7c7f18fa8d2a518 (diff) | |
parent | 5cc4bbeab3fb8966bb1fe609b70c50032e941375 (diff) | |
download | indexmap-6e5a0be56336bd29697146229a6ed1c88818d2d5.tar.gz |
Merge "Upgrade indexmap to 1.9.2" am: 2c5be766c5 am: 5cc4bbeab3
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/indexmap/+/2337864
Change-Id: Ie01fbd1206de5e9c794b5156029f33e1070705f9
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
-rw-r--r-- | .cargo_vcs_info.json | 6 | ||||
-rw-r--r-- | .github/workflows/ci.yml | 114 | ||||
-rw-r--r-- | .gitignore | 2 | ||||
-rw-r--r-- | .rustfmt.toml | 1 | ||||
-rw-r--r-- | Android.bp | 9 | ||||
-rw-r--r-- | Cargo.toml | 126 | ||||
-rw-r--r-- | Cargo.toml.orig | 65 | ||||
-rw-r--r-- | METADATA | 18 | ||||
-rw-r--r-- | RELEASES.md | 18 | ||||
-rw-r--r-- | build.rs | 8 | ||||
-rw-r--r-- | src/arbitrary.rs | 75 | ||||
-rw-r--r-- | src/lib.rs | 16 | ||||
-rw-r--r-- | src/macros.rs | 30 | ||||
-rw-r--r-- | src/map.rs | 95 | ||||
-rw-r--r-- | src/map/slice.rs | 487 | ||||
-rw-r--r-- | src/mutable_keys.rs | 42 | ||||
-rw-r--r-- | src/rayon/map.rs | 98 | ||||
-rw-r--r-- | src/rayon/set.rs | 32 | ||||
-rw-r--r-- | src/serde.rs | 8 | ||||
-rw-r--r-- | src/serde_seq.rs | 42 | ||||
-rw-r--r-- | src/set.rs | 54 | ||||
-rw-r--r-- | src/set/slice.rs | 282 | ||||
-rw-r--r-- | src/util.rs | 22 | ||||
-rw-r--r-- | test-nostd/Cargo.toml | 12 | ||||
-rw-r--r-- | test-nostd/src/lib.rs | 36 | ||||
-rw-r--r-- | test-serde/Cargo.toml | 13 | ||||
-rw-r--r-- | test-serde/src/lib.rs | 115 |
27 files changed, 453 insertions, 1373 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json new file mode 100644 index 0000000..6395e04 --- /dev/null +++ b/.cargo_vcs_info.json @@ -0,0 +1,6 @@ +{ + "git": { + "sha1": "4d52cf338c6ff9f742aac716f41b8a5497842f92" + }, + "path_in_vcs": "" +}
\ No newline at end of file diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml new file mode 100644 index 0000000..dcde8f4 --- /dev/null +++ b/.github/workflows/ci.yml @@ -0,0 +1,114 @@ +on: + push: + branches: [ master, indexmap-1.x ] + pull_request: + branches: [ master, indexmap-1.x ] + +name: Continuous integration + +env: + CARGO_TERM_COLOR: always + CARGO_INCREMENTAL: 0 + +jobs: + tests: + runs-on: ubuntu-latest + strategy: + matrix: + include: + - rust: 1.56.0 # MSRV + features: + - rust: stable + features: arbitrary + - rust: stable + features: quickcheck + - rust: stable + features: rayon + - rust: stable + features: rustc-rayon + - rust: stable + features: serde + - rust: stable + features: std + - rust: beta + features: + - rust: nightly + bench: test build benchmarks + - rust: nightly + features: test_low_transition_point + + steps: + - uses: actions/checkout@v2 + - uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: ${{ matrix.rust }} + override: true + - name: Tests + run: | + cargo build --verbose --features "${{ matrix.features }}" + cargo doc --verbose --features "${{ matrix.features }}" + cargo test --verbose --features "${{ matrix.features }}" + cargo test --release --verbose --features "${{ matrix.features }}" + - name: Tests (serde) + if: matrix.features == 'serde' + run: | + cargo test --verbose -p test-serde + - name: Test run benchmarks + if: matrix.bench != '' + run: cargo test -v --benches + + nostd_build: + runs-on: ubuntu-latest + strategy: + matrix: + include: + - rust: 1.56.0 + target: thumbv6m-none-eabi + - rust: stable + target: thumbv6m-none-eabi + + steps: + - uses: actions/checkout@v2 + - uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: ${{ matrix.rust }} + override: true + target: ${{ matrix.target }} + - name: Tests + run: | + cargo build -vv --target=${{ matrix.target }} + cargo build -v -p test-nostd --target=${{ matrix.target }} + + clippy: + runs-on: ubuntu-latest + strategy: + matrix: + rust: + - beta + steps: + - uses: actions/checkout@v2 + - uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: ${{ matrix.rust }} + override: true + components: clippy + - run: cargo clippy + + miri: + runs-on: ubuntu-latest + strategy: + matrix: + rust: + - nightly + steps: + - uses: actions/checkout@v2 + - uses: actions-rs/toolchain@v1 + with: + profile: minimal + toolchain: ${{ matrix.rust }} + override: true + components: miri + - run: cargo miri test diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..a9d37c5 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +target +Cargo.lock diff --git a/.rustfmt.toml b/.rustfmt.toml new file mode 100644 index 0000000..3a26366 --- /dev/null +++ b/.rustfmt.toml @@ -0,0 +1 @@ +edition = "2021" @@ -1,8 +1,6 @@ // This file is generated by cargo2android.py --run --device. // Do not modify this file as changes will be overridden on upgrade. - - package { default_applicable_licenses: ["external_rust_crates_indexmap_license"], } @@ -44,13 +42,10 @@ rust_library { host_supported: true, crate_name: "indexmap", cargo_env_compat: true, - cargo_pkg_version: "2.0.0-pre", + cargo_pkg_version: "1.9.2", srcs: ["src/lib.rs"], edition: "2021", - features: [ - "default", - "std", - ], + cfgs: ["has_std"], rustlibs: [ "libhashbrown", ], @@ -1,57 +1,107 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + [package] -name = "indexmap" edition = "2021" -version = "2.0.0-pre" -publish = false +rust-version = "1.56" +name = "indexmap" +version = "1.9.2" +description = "A hash table with consistent order and fast iteration." documentation = "https://docs.rs/indexmap/" -repository = "https://github.com/bluss/indexmap" +readme = "README.md" +keywords = [ + "hashmap", + "no_std", +] +categories = [ + "data-structures", + "no-std", +] license = "Apache-2.0 OR MIT" -description = "A hash table with consistent order and fast iteration." -keywords = ["hashmap", "no_std"] -categories = ["data-structures", "no-std"] -rust-version = "1.56" +repository = "https://github.com/bluss/indexmap" + +[package.metadata.release] +no-dev-version = true +tag-name = "{{version}}" + +[package.metadata.docs.rs] +features = [ + "arbitrary", + "quickcheck", + "serde-1", + "rayon", +] + +[profile.bench] +debug = true [lib] bench = false -[dependencies] -serde = { version = "1.0", optional = true, default-features = false } -rayon = { version = "1.4.1", optional = true } - -# Internal feature, only used when building as part of rustc, -# not part of the stable interface of this crate. -rustc-rayon = { version = "0.4", optional = true } +[dependencies.arbitrary] +version = "1.0" +optional = true +default-features = false [dependencies.hashbrown] version = "0.12" -default-features = false features = ["raw"] +default-features = false -[dev-dependencies] -itertools = "0.10" -rand = {version = "0.8", features = ["small_rng"] } -quickcheck = { version = "1.0", default-features = false } -fnv = "1.0" -lazy_static = "1.3" -fxhash = "0.2.1" -serde_derive = "1.0" +[dependencies.quickcheck] +version = "1.0" +optional = true +default-features = false -[features] -default = ["std"] -std = [] +[dependencies.rayon] +version = "1.4.1" +optional = true -# for testing only, of course -test_debug = [] +[dependencies.rustc-rayon] +version = "0.4" +optional = true -[profile.bench] -debug = true +[dependencies.serde] +version = "1.0" +optional = true +default-features = false -[package.metadata.release] -no-dev-version = true -tag-name = "{{version}}" +[dev-dependencies.fnv] +version = "1.0" -[package.metadata.docs.rs] -features = ["serde", "rayon"] +[dev-dependencies.fxhash] +version = "0.2.1" -[workspace] -members = ["test-nostd", "test-serde"] +[dev-dependencies.itertools] +version = "0.10" + +[dev-dependencies.lazy_static] +version = "1.3" + +[dev-dependencies.quickcheck] +version = "1.0" +default-features = false + +[dev-dependencies.rand] +version = "0.8" +features = ["small_rng"] + +[dev-dependencies.serde_derive] +version = "1.0" + +[build-dependencies.autocfg] +version = "1" + +[features] +serde-1 = ["serde"] +std = [] +test_debug = [] +test_low_transition_point = [] diff --git a/Cargo.toml.orig b/Cargo.toml.orig new file mode 100644 index 0000000..16b5c52 --- /dev/null +++ b/Cargo.toml.orig @@ -0,0 +1,65 @@ +[package] +name = "indexmap" +edition = "2021" +version = "1.9.2" +documentation = "https://docs.rs/indexmap/" +repository = "https://github.com/bluss/indexmap" +license = "Apache-2.0 OR MIT" +description = "A hash table with consistent order and fast iteration." +keywords = ["hashmap", "no_std"] +categories = ["data-structures", "no-std"] +rust-version = "1.56" + +[lib] +bench = false + +[build-dependencies] +autocfg = "1" + +[dependencies] +arbitrary = { version = "1.0", optional = true, default-features = false } +quickcheck = { version = "1.0", optional = true, default-features = false } +serde = { version = "1.0", optional = true, default-features = false } +rayon = { version = "1.4.1", optional = true } + +# Internal feature, only used when building as part of rustc, +# not part of the stable interface of this crate. +rustc-rayon = { version = "0.4", optional = true } + +[dependencies.hashbrown] +version = "0.12" +default-features = false +features = ["raw"] + +[dev-dependencies] +itertools = "0.10" +rand = {version = "0.8", features = ["small_rng"] } +quickcheck = { version = "1.0", default-features = false } +fnv = "1.0" +lazy_static = "1.3" +fxhash = "0.2.1" +serde_derive = "1.0" + +[features] +# Serialization with serde 1.0 +serde-1 = ["serde"] + +# Force the use of `std`, bypassing target detection. +std = [] + +# for testing only, of course +test_low_transition_point = [] +test_debug = [] + +[profile.bench] +debug = true + +[package.metadata.release] +no-dev-version = true +tag-name = "{{version}}" + +[package.metadata.docs.rs] +features = ["arbitrary", "quickcheck", "serde-1", "rayon"] + +[workspace] +members = ["test-nostd", "test-serde"] @@ -1,7 +1,9 @@ -name: "indexmap" -description: - "A pure-Rust hash table which preserves (in a limited sense) insertion order." +# This project was upgraded with external_updater. +# Usage: tools/external_updater/updater.sh update rust/crates/indexmap +# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md +name: "indexmap" +description: "A hash table with consistent order and fast iteration." third_party { url { type: HOMEPAGE @@ -9,9 +11,13 @@ third_party { } url { type: ARCHIVE - value: "https://github.com/bluss/indexmap" + value: "https://static.crates.io/crates/indexmap/indexmap-1.9.2.crate" } - version: "1.9.1" - last_upgrade_date { year: 2022 month: 6 day: 30 } + version: "1.9.2" license_type: NOTICE + last_upgrade_date { + year: 2022 + month: 12 + day: 12 + } } diff --git a/RELEASES.md b/RELEASES.md index 651f8b4..7c58be3 100644 --- a/RELEASES.md +++ b/RELEASES.md @@ -1,19 +1,7 @@ -- 2.0.0 (pending) +- 1.9.2 - - The `"std"` feature is no longer auto-detected. It is included in the - default feature set, or else can be enabled like any other Cargo feature. - - - The `"serde-1"` feature has been removed, leaving just the optional - `"serde"` dependency to be enabled like a feature itself. - - - `IndexMap::get_index_mut` now returns `Option<(&K, &mut V)>`, changing - the key part from `&mut K` to `&K`. There is also a new alternative - `MutableKeys::get_index_mut2` to access the former behavior. - - - The new `map::Slice<K, V>` and `set::Slice<T>` offer a linear view of maps - and sets, behaving a lot like normal `[(K, V)]` and `[T]` slices. Notably, - comparison traits like `Eq` only consider items in order, rather than hash - lookups, and slices even implement `Hash`. + - `IndexMap` and `IndexSet` both implement `arbitrary::Arbitrary<'_>` and + `quickcheck::Arbitrary` if those optional dependency features are enabled. - 1.9.1 diff --git a/build.rs b/build.rs new file mode 100644 index 0000000..9f9fa05 --- /dev/null +++ b/build.rs @@ -0,0 +1,8 @@ +fn main() { + // If "std" is explicitly requested, don't bother probing the target for it. + match std::env::var_os("CARGO_FEATURE_STD") { + Some(_) => autocfg::emit("has_std"), + None => autocfg::new().emit_sysroot_crate("std"), + } + autocfg::rerun_path("build.rs"); +} diff --git a/src/arbitrary.rs b/src/arbitrary.rs new file mode 100644 index 0000000..1347c8b --- /dev/null +++ b/src/arbitrary.rs @@ -0,0 +1,75 @@ +#[cfg(feature = "arbitrary")] +mod impl_arbitrary { + use crate::{IndexMap, IndexSet}; + use arbitrary::{Arbitrary, Result, Unstructured}; + use core::hash::{BuildHasher, Hash}; + + impl<'a, K, V, S> Arbitrary<'a> for IndexMap<K, V, S> + where + K: Arbitrary<'a> + Hash + Eq, + V: Arbitrary<'a>, + S: BuildHasher + Default, + { + fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> { + u.arbitrary_iter()?.collect() + } + + fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> { + u.arbitrary_take_rest_iter()?.collect() + } + } + + impl<'a, T, S> Arbitrary<'a> for IndexSet<T, S> + where + T: Arbitrary<'a> + Hash + Eq, + S: BuildHasher + Default, + { + fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> { + u.arbitrary_iter()?.collect() + } + + fn arbitrary_take_rest(u: Unstructured<'a>) -> Result<Self> { + u.arbitrary_take_rest_iter()?.collect() + } + } +} + +#[cfg(feature = "quickcheck")] +mod impl_quickcheck { + use crate::{IndexMap, IndexSet}; + use alloc::boxed::Box; + use alloc::vec::Vec; + use core::hash::{BuildHasher, Hash}; + use quickcheck::{Arbitrary, Gen}; + + impl<K, V, S> Arbitrary for IndexMap<K, V, S> + where + K: Arbitrary + Hash + Eq, + V: Arbitrary, + S: BuildHasher + Default + Clone + 'static, + { + fn arbitrary(g: &mut Gen) -> Self { + Self::from_iter(Vec::arbitrary(g)) + } + + fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { + let vec = Vec::from_iter(self.clone()); + Box::new(vec.shrink().map(Self::from_iter)) + } + } + + impl<T, S> Arbitrary for IndexSet<T, S> + where + T: Arbitrary + Hash + Eq, + S: BuildHasher + Default + Clone + 'static, + { + fn arbitrary(g: &mut Gen) -> Self { + Self::from_iter(Vec::arbitrary(g)) + } + + fn shrink(&self) -> Box<dyn Iterator<Item = Self>> { + let vec = Vec::from_iter(self.clone()); + Box::new(vec.shrink().map(Self::from_iter)) + } + } +} @@ -55,18 +55,19 @@ //! //! This version of indexmap requires Rust 1.56 or later. //! -//! The indexmap 2.x release series will use a carefully considered version -//! upgrade policy, where in a later 2.x version, we will raise the minimum +//! The indexmap 1.x release series will use a carefully considered version +//! upgrade policy, where in a later 1.x version, we will raise the minimum //! required Rust version. //! //! ## No Standard Library Targets //! -//! This crate supports being built without `std`, requiring `alloc` instead. -//! This is chosen by disabling the default "std" cargo feature, by adding -//! `default-features = false` to your dependency specification. +//! This crate supports being built without `std`, requiring +//! `alloc` instead. This is enabled automatically when it is detected that +//! `std` is not available. There is no crate feature to enable/disable to +//! trigger this. It can be tested by building for a std-less target. //! //! - Creating maps and sets using [`new`][IndexMap::new] and -//! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`. +//! [`with_capacity`][IndexMap::with_capacity] is unavailable without `std`. //! Use methods [`IndexMap::default`][def], //! [`with_hasher`][IndexMap::with_hasher], //! [`with_capacity_and_hasher`][IndexMap::with_capacity_and_hasher] instead. @@ -78,12 +79,13 @@ extern crate alloc; -#[cfg(feature = "std")] +#[cfg(has_std)] #[macro_use] extern crate std; use alloc::vec::{self, Vec}; +mod arbitrary; #[macro_use] mod macros; mod equivalent; diff --git a/src/macros.rs b/src/macros.rs index 889dbe7..ca26287 100644 --- a/src/macros.rs +++ b/src/macros.rs @@ -1,4 +1,4 @@ -#[cfg(feature = "std")] +#[cfg(has_std)] #[macro_export] /// Create an `IndexMap` from a list of key-value pairs /// @@ -19,22 +19,23 @@ /// assert_eq!(map.keys().next(), Some(&"a")); /// ``` macro_rules! indexmap { + (@single $($x:tt)*) => (()); + (@count $($rest:expr),*) => (<[()]>::len(&[$($crate::indexmap!(@single $rest)),*])); + ($($key:expr => $value:expr,)+) => { $crate::indexmap!($($key => $value),+) }; ($($key:expr => $value:expr),*) => { { - // Note: `stringify!($key)` is just here to consume the repetition, - // but we throw away that string literal during constant evaluation. - const CAP: usize = <[()]>::len(&[$({ stringify!($key); }),*]); - let mut map = $crate::IndexMap::with_capacity(CAP); + let _cap = $crate::indexmap!(@count $($key),*); + let mut _map = $crate::IndexMap::with_capacity(_cap); $( - map.insert($key, $value); + _map.insert($key, $value); )* - map + _map } }; } -#[cfg(feature = "std")] +#[cfg(has_std)] #[macro_export] /// Create an `IndexSet` from a list of values /// @@ -55,17 +56,18 @@ macro_rules! indexmap { /// assert_eq!(set.iter().next(), Some(&"a")); /// ``` macro_rules! indexset { + (@single $($x:tt)*) => (()); + (@count $($rest:expr),*) => (<[()]>::len(&[$($crate::indexset!(@single $rest)),*])); + ($($value:expr,)+) => { $crate::indexset!($($value),+) }; ($($value:expr),*) => { { - // Note: `stringify!($value)` is just here to consume the repetition, - // but we throw away that string literal during constant evaluation. - const CAP: usize = <[()]>::len(&[$({ stringify!($value); }),*]); - let mut set = $crate::IndexSet::with_capacity(CAP); + let _cap = $crate::indexset!(@count $($value),*); + let mut _set = $crate::IndexSet::with_capacity(_cap); $( - set.insert($value); + _set.insert($value); )* - set + _set } }; } @@ -2,9 +2,7 @@ //! pairs is independent of the hash values of the keys. mod core; -mod slice; -pub use self::slice::Slice; pub use crate::mutable_keys::MutableKeys; #[cfg(feature = "rayon")] @@ -17,14 +15,13 @@ use ::core::hash::{BuildHasher, Hash, Hasher}; use ::core::iter::FusedIterator; use ::core::ops::{Index, IndexMut, RangeBounds}; use ::core::slice::{Iter as SliceIter, IterMut as SliceIterMut}; -use alloc::boxed::Box; -#[cfg(feature = "std")] +#[cfg(has_std)] use std::collections::hash_map::RandomState; use self::core::IndexMapCore; use crate::equivalent::Equivalent; -use crate::util::{third, try_simplify_range}; +use crate::util::third; use crate::{Bucket, Entries, HashValue}; pub use self::core::{Entry, OccupiedEntry, VacantEntry}; @@ -70,12 +67,12 @@ pub use self::core::{Entry, OccupiedEntry, VacantEntry}; /// assert_eq!(letters[&'u'], 1); /// assert_eq!(letters.get(&'y'), None); /// ``` -#[cfg(feature = "std")] +#[cfg(has_std)] pub struct IndexMap<K, V, S = RandomState> { pub(crate) core: IndexMapCore<K, V>, hash_builder: S, } -#[cfg(not(feature = "std"))] +#[cfg(not(has_std))] pub struct IndexMap<K, V, S> { pub(crate) core: IndexMapCore<K, V>, hash_builder: S, @@ -143,7 +140,7 @@ where } } -#[cfg(feature = "std")] +#[cfg(has_std)] impl<K, V> IndexMap<K, V> { /// Create a new map. (Does not allocate.) #[inline] @@ -489,6 +486,21 @@ where } } + pub(crate) fn get_full_mut2_impl<Q: ?Sized>( + &mut self, + key: &Q, + ) -> Option<(usize, &mut K, &mut V)> + where + Q: Hash + Equivalent<K>, + { + if let Some(i) = self.get_index_of(key) { + let entry = &mut self.as_entries_mut()[i]; + Some((i, &mut entry.key, &mut entry.value)) + } else { + None + } + } + /// Remove the key-value pair equivalent to `key` and return /// its value. /// @@ -761,27 +773,6 @@ where } impl<K, V, S> IndexMap<K, V, S> { - /// Returns a slice of all the key-value pairs in the map. - /// - /// Computes in **O(1)** time. - pub fn as_slice(&self) -> &Slice<K, V> { - Slice::from_slice(self.as_entries()) - } - - /// Returns a mutable slice of all the key-value pairs in the map. - /// - /// Computes in **O(1)** time. - pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> { - Slice::from_mut_slice(self.as_entries_mut()) - } - - /// Converts into a boxed slice of all the key-value pairs in the map. - /// - /// Note that this will drop the inner hash table and any excess capacity. - pub fn into_boxed_slice(self) -> Box<Slice<K, V>> { - Slice::from_boxed(self.into_entries().into_boxed_slice()) - } - /// Get a key-value pair by index /// /// Valid indices are *0 <= index < self.len()* @@ -796,30 +787,8 @@ impl<K, V, S> IndexMap<K, V, S> { /// Valid indices are *0 <= index < self.len()* /// /// Computes in **O(1)** time. - pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { - self.as_entries_mut().get_mut(index).map(Bucket::ref_mut) - } - - /// Returns a slice of key-value pairs in the given range of indices. - /// - /// Valid indices are *0 <= index < self.len()* - /// - /// Computes in **O(1)** time. - pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Slice<K, V>> { - let entries = self.as_entries(); - let range = try_simplify_range(range, entries.len())?; - entries.get(range).map(Slice::from_slice) - } - - /// Returns a mutable slice of key-value pairs in the given range of indices. - /// - /// Valid indices are *0 <= index < self.len()* - /// - /// Computes in **O(1)** time. - pub fn get_range_mut<R: RangeBounds<usize>>(&mut self, range: R) -> Option<&mut Slice<K, V>> { - let entries = self.as_entries_mut(); - let range = try_simplify_range(range, entries.len())?; - entries.get_mut(range).map(Slice::from_mut_slice) + pub fn get_index_mut(&mut self, index: usize) -> Option<(&mut K, &mut V)> { + self.as_entries_mut().get_mut(index).map(Bucket::muts) } /// Get the first key-value pair @@ -1104,13 +1073,6 @@ pub struct Iter<'a, K, V> { iter: SliceIter<'a, Bucket<K, V>>, } -impl<'a, K, V> Iter<'a, K, V> { - /// Returns a slice of the remaining entries in the iterator. - pub fn as_slice(&self) -> &'a Slice<K, V> { - Slice::from_slice(self.iter.as_slice()) - } -} - impl<'a, K, V> Iterator for Iter<'a, K, V> { type Item = (&'a K, &'a V); @@ -1155,15 +1117,6 @@ pub struct IterMut<'a, K, V> { iter: SliceIterMut<'a, Bucket<K, V>>, } -impl<'a, K, V> IterMut<'a, K, V> { - /// Returns a slice of the remaining entries in the iterator. - /// - /// To avoid creating `&mut` references that alias, this is forced to consume the iterator. - pub fn into_slice(self) -> &'a mut Slice<K, V> { - Slice::from_mut_slice(self.iter.into_slice()) - } -} - impl<'a, K, V> Iterator for IterMut<'a, K, V> { type Item = (&'a K, &'a mut V); @@ -1468,7 +1421,7 @@ where } } -#[cfg(feature = "std")] +#[cfg(has_std)] impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V, RandomState> where K: Hash + Eq, @@ -1982,7 +1935,7 @@ mod tests { } #[test] - #[cfg(feature = "std")] + #[cfg(has_std)] fn from_array() { let map = IndexMap::from([(1, 2), (3, 4)]); let mut expected = IndexMap::new(); diff --git a/src/map/slice.rs b/src/map/slice.rs deleted file mode 100644 index 4b2029d..0000000 --- a/src/map/slice.rs +++ /dev/null @@ -1,487 +0,0 @@ -use super::{ - Bucket, Entries, IndexMap, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, Values, - ValuesMut, -}; -use crate::util::try_simplify_range; - -use alloc::boxed::Box; -use alloc::vec::Vec; -use core::cmp::Ordering; -use core::fmt; -use core::hash::{Hash, Hasher}; -use core::ops::{self, Bound, Index, IndexMut, RangeBounds}; - -/// A dynamically-sized slice of key-value pairs in an `IndexMap`. -/// -/// This supports indexed operations much like a `[(K, V)]` slice, -/// but not any hashed operations on the map keys. -/// -/// Unlike `IndexMap`, `Slice` does consider the order for `PartialEq` -/// and `Eq`, and it also implements `PartialOrd`, `Ord`, and `Hash`. -#[repr(transparent)] -pub struct Slice<K, V> { - pub(crate) entries: [Bucket<K, V>], -} - -// SAFETY: `Slice<K, V>` is a transparent wrapper around `[Bucket<K, V>]`, -// and reference lifetimes are bound together in function signatures. -#[allow(unsafe_code)] -impl<K, V> Slice<K, V> { - pub(super) fn from_slice(entries: &[Bucket<K, V>]) -> &Self { - unsafe { &*(entries as *const [Bucket<K, V>] as *const Self) } - } - - pub(super) fn from_mut_slice(entries: &mut [Bucket<K, V>]) -> &mut Self { - unsafe { &mut *(entries as *mut [Bucket<K, V>] as *mut Self) } - } - - pub(super) fn from_boxed(entries: Box<[Bucket<K, V>]>) -> Box<Self> { - unsafe { Box::from_raw(Box::into_raw(entries) as *mut Self) } - } - - fn into_boxed(self: Box<Self>) -> Box<[Bucket<K, V>]> { - unsafe { Box::from_raw(Box::into_raw(self) as *mut [Bucket<K, V>]) } - } -} - -impl<K, V> Slice<K, V> { - pub(crate) fn into_entries(self: Box<Self>) -> Vec<Bucket<K, V>> { - self.into_boxed().into_vec() - } - - /// Return the number of key-value pairs in the map slice. - #[inline] - pub fn len(&self) -> usize { - self.entries.len() - } - - /// Returns true if the map slice contains no elements. - #[inline] - pub fn is_empty(&self) -> bool { - self.entries.is_empty() - } - - /// Get a key-value pair by index. - /// - /// Valid indices are *0 <= index < self.len()* - pub fn get_index(&self, index: usize) -> Option<(&K, &V)> { - self.entries.get(index).map(Bucket::refs) - } - - /// Get a key-value pair by index, with mutable access to the value. - /// - /// Valid indices are *0 <= index < self.len()* - pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { - self.entries.get_mut(index).map(Bucket::ref_mut) - } - - /// Returns a slice of key-value pairs in the given range of indices. - /// - /// Valid indices are *0 <= index < self.len()* - pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Self> { - let range = try_simplify_range(range, self.entries.len())?; - self.entries.get(range).map(Slice::from_slice) - } - - /// Returns a mutable slice of key-value pairs in the given range of indices. - /// - /// Valid indices are *0 <= index < self.len()* - pub fn get_range_mut<R: RangeBounds<usize>>(&mut self, range: R) -> Option<&mut Self> { - let range = try_simplify_range(range, self.entries.len())?; - self.entries.get_mut(range).map(Slice::from_mut_slice) - } - - /// Get the first key-value pair. - pub fn first(&self) -> Option<(&K, &V)> { - self.entries.first().map(Bucket::refs) - } - - /// Get the first key-value pair, with mutable access to the value. - pub fn first_mut(&mut self) -> Option<(&K, &mut V)> { - self.entries.first_mut().map(Bucket::ref_mut) - } - - /// Get the last key-value pair. - pub fn last(&self) -> Option<(&K, &V)> { - self.entries.last().map(Bucket::refs) - } - - /// Get the last key-value pair, with mutable access to the value. - pub fn last_mut(&mut self) -> Option<(&K, &mut V)> { - self.entries.last_mut().map(Bucket::ref_mut) - } - - /// Divides one slice into two at an index. - /// - /// ***Panics*** if `index > len`. - pub fn split_at(&self, index: usize) -> (&Self, &Self) { - let (first, second) = self.entries.split_at(index); - (Self::from_slice(first), Self::from_slice(second)) - } - - /// Divides one mutable slice into two at an index. - /// - /// ***Panics*** if `index > len`. - pub fn split_at_mut(&mut self, index: usize) -> (&mut Self, &mut Self) { - let (first, second) = self.entries.split_at_mut(index); - (Self::from_mut_slice(first), Self::from_mut_slice(second)) - } - - /// Returns the first key-value pair and the rest of the slice, - /// or `None` if it is empty. - pub fn split_first(&self) -> Option<((&K, &V), &Self)> { - if let [first, rest @ ..] = &self.entries { - Some((first.refs(), Self::from_slice(rest))) - } else { - None - } - } - - /// Returns the first key-value pair and the rest of the slice, - /// with mutable access to the value, or `None` if it is empty. - pub fn split_first_mut(&mut self) -> Option<((&K, &mut V), &mut Self)> { - if let [first, rest @ ..] = &mut self.entries { - Some((first.ref_mut(), Self::from_mut_slice(rest))) - } else { - None - } - } - - /// Returns the last key-value pair and the rest of the slice, - /// or `None` if it is empty. - pub fn split_last(&self) -> Option<((&K, &V), &Self)> { - if let [rest @ .., last] = &self.entries { - Some((last.refs(), Self::from_slice(rest))) - } else { - None - } - } - - /// Returns the last key-value pair and the rest of the slice, - /// with mutable access to the value, or `None` if it is empty. - pub fn split_last_mut(&mut self) -> Option<((&K, &mut V), &mut Self)> { - if let [rest @ .., last] = &mut self.entries { - Some((last.ref_mut(), Self::from_mut_slice(rest))) - } else { - None - } - } - - /// Return an iterator over the key-value pairs of the map slice. - pub fn iter(&self) -> Iter<'_, K, V> { - Iter { - iter: self.entries.iter(), - } - } - - /// Return an iterator over the key-value pairs of the map slice. - pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { - IterMut { - iter: self.entries.iter_mut(), - } - } - - /// Return an iterator over the keys of the map slice. - pub fn keys(&self) -> Keys<'_, K, V> { - Keys { - iter: self.entries.iter(), - } - } - - /// Return an owning iterator over the keys of the map slice. - pub fn into_keys(self: Box<Self>) -> IntoKeys<K, V> { - IntoKeys { - iter: self.into_entries().into_iter(), - } - } - - /// Return an iterator over the values of the map slice. - pub fn values(&self) -> Values<'_, K, V> { - Values { - iter: self.entries.iter(), - } - } - - /// Return an iterator over mutable references to the the values of the map slice. - pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> { - ValuesMut { - iter: self.entries.iter_mut(), - } - } - - /// Return an owning iterator over the values of the map slice. - pub fn into_values(self: Box<Self>) -> IntoValues<K, V> { - IntoValues { - iter: self.into_entries().into_iter(), - } - } -} - -impl<'a, K, V> IntoIterator for &'a Slice<K, V> { - type IntoIter = Iter<'a, K, V>; - type Item = (&'a K, &'a V); - - fn into_iter(self) -> Self::IntoIter { - self.iter() - } -} - -impl<'a, K, V> IntoIterator for &'a mut Slice<K, V> { - type IntoIter = IterMut<'a, K, V>; - type Item = (&'a K, &'a mut V); - - fn into_iter(self) -> Self::IntoIter { - self.iter_mut() - } -} - -impl<K, V> IntoIterator for Box<Slice<K, V>> { - type IntoIter = IntoIter<K, V>; - type Item = (K, V); - - fn into_iter(self) -> Self::IntoIter { - IntoIter { - iter: self.into_entries().into_iter(), - } - } -} - -impl<K, V> Default for &'_ Slice<K, V> { - fn default() -> Self { - Slice::from_slice(&[]) - } -} - -impl<K, V> Default for &'_ mut Slice<K, V> { - fn default() -> Self { - Slice::from_mut_slice(&mut []) - } -} - -impl<K, V> Default for Box<Slice<K, V>> { - fn default() -> Self { - Slice::from_boxed(Box::default()) - } -} - -impl<K: Clone, V: Clone> Clone for Box<Slice<K, V>> { - fn clone(&self) -> Self { - Slice::from_boxed(self.entries.to_vec().into_boxed_slice()) - } -} - -impl<K: Copy, V: Copy> From<&Slice<K, V>> for Box<Slice<K, V>> { - fn from(slice: &Slice<K, V>) -> Self { - Slice::from_boxed(Box::from(&slice.entries)) - } -} - -impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Slice<K, V> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self).finish() - } -} - -impl<K: PartialEq, V: PartialEq> PartialEq for Slice<K, V> { - fn eq(&self, other: &Self) -> bool { - self.len() == other.len() && self.iter().eq(other) - } -} - -impl<K: Eq, V: Eq> Eq for Slice<K, V> {} - -impl<K: PartialOrd, V: PartialOrd> PartialOrd for Slice<K, V> { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - self.iter().partial_cmp(other) - } -} - -impl<K: Ord, V: Ord> Ord for Slice<K, V> { - fn cmp(&self, other: &Self) -> Ordering { - self.iter().cmp(other) - } -} - -impl<K: Hash, V: Hash> Hash for Slice<K, V> { - fn hash<H: Hasher>(&self, state: &mut H) { - self.len().hash(state); - for (key, value) in self { - key.hash(state); - value.hash(state); - } - } -} - -impl<K, V> Index<usize> for Slice<K, V> { - type Output = V; - - fn index(&self, index: usize) -> &V { - &self.entries[index].value - } -} - -impl<K, V> IndexMut<usize> for Slice<K, V> { - fn index_mut(&mut self, index: usize) -> &mut V { - &mut self.entries[index].value - } -} - -// We can't have `impl<I: RangeBounds<usize>> Index<I>` because that conflicts -// both upstream with `Index<usize>` and downstream with `Index<&Q>`. -// Instead, we repeat the implementations for all the core range types. -macro_rules! impl_index { - ($($range:ty),*) => {$( - impl<K, V, S> Index<$range> for IndexMap<K, V, S> { - type Output = Slice<K, V>; - - fn index(&self, range: $range) -> &Self::Output { - Slice::from_slice(&self.as_entries()[range]) - } - } - - impl<K, V, S> IndexMut<$range> for IndexMap<K, V, S> { - fn index_mut(&mut self, range: $range) -> &mut Self::Output { - Slice::from_mut_slice(&mut self.as_entries_mut()[range]) - } - } - - impl<K, V> Index<$range> for Slice<K, V> { - type Output = Slice<K, V>; - - fn index(&self, range: $range) -> &Self { - Self::from_slice(&self.entries[range]) - } - } - - impl<K, V> IndexMut<$range> for Slice<K, V> { - fn index_mut(&mut self, range: $range) -> &mut Self { - Self::from_mut_slice(&mut self.entries[range]) - } - } - )*} -} -impl_index!( - ops::Range<usize>, - ops::RangeFrom<usize>, - ops::RangeFull, - ops::RangeInclusive<usize>, - ops::RangeTo<usize>, - ops::RangeToInclusive<usize>, - (Bound<usize>, Bound<usize>) -); - -#[cfg(test)] -mod tests { - use super::*; - use alloc::vec::Vec; - - #[test] - fn slice_index() { - fn check( - vec_slice: &[(i32, i32)], - map_slice: &Slice<i32, i32>, - sub_slice: &Slice<i32, i32>, - ) { - assert_eq!(map_slice as *const _, sub_slice as *const _); - itertools::assert_equal( - vec_slice.iter().copied(), - map_slice.iter().map(|(&k, &v)| (k, v)), - ); - itertools::assert_equal(vec_slice.iter().map(|(k, _)| k), map_slice.keys()); - itertools::assert_equal(vec_slice.iter().map(|(_, v)| v), map_slice.values()); - } - - let vec: Vec<(i32, i32)> = (0..10).map(|i| (i, i * i)).collect(); - let map: IndexMap<i32, i32> = vec.iter().cloned().collect(); - let slice = map.as_slice(); - - // RangeFull - check(&vec[..], &map[..], &slice[..]); - - for i in 0usize..10 { - // Index - assert_eq!(vec[i].1, map[i]); - assert_eq!(vec[i].1, slice[i]); - assert_eq!(map[&(i as i32)], map[i]); - assert_eq!(map[&(i as i32)], slice[i]); - - // RangeFrom - check(&vec[i..], &map[i..], &slice[i..]); - - // RangeTo - check(&vec[..i], &map[..i], &slice[..i]); - - // RangeToInclusive - check(&vec[..=i], &map[..=i], &slice[..=i]); - - // (Bound<usize>, Bound<usize>) - let bounds = (Bound::Excluded(i), Bound::Unbounded); - check(&vec[i + 1..], &map[bounds], &slice[bounds]); - - for j in i..=10 { - // Range - check(&vec[i..j], &map[i..j], &slice[i..j]); - } - - for j in i..10 { - // RangeInclusive - check(&vec[i..=j], &map[i..=j], &slice[i..=j]); - } - } - } - - #[test] - fn slice_index_mut() { - fn check_mut( - vec_slice: &[(i32, i32)], - map_slice: &mut Slice<i32, i32>, - sub_slice: &mut Slice<i32, i32>, - ) { - assert_eq!(map_slice, sub_slice); - itertools::assert_equal( - vec_slice.iter().copied(), - map_slice.iter_mut().map(|(&k, &mut v)| (k, v)), - ); - itertools::assert_equal( - vec_slice.iter().map(|&(_, v)| v), - map_slice.values_mut().map(|&mut v| v), - ); - } - - let vec: Vec<(i32, i32)> = (0..10).map(|i| (i, i * i)).collect(); - let mut map: IndexMap<i32, i32> = vec.iter().cloned().collect(); - let mut map2 = map.clone(); - let slice = map2.as_mut_slice(); - - // RangeFull - check_mut(&vec[..], &mut map[..], &mut slice[..]); - - for i in 0usize..10 { - // IndexMut - assert_eq!(&mut map[i], &mut slice[i]); - - // RangeFrom - check_mut(&vec[i..], &mut map[i..], &mut slice[i..]); - - // RangeTo - check_mut(&vec[..i], &mut map[..i], &mut slice[..i]); - - // RangeToInclusive - check_mut(&vec[..=i], &mut map[..=i], &mut slice[..=i]); - - // (Bound<usize>, Bound<usize>) - let bounds = (Bound::Excluded(i), Bound::Unbounded); - check_mut(&vec[i + 1..], &mut map[bounds], &mut slice[bounds]); - - for j in i..=10 { - // Range - check_mut(&vec[i..j], &mut map[i..j], &mut slice[i..j]); - } - - for j in i..10 { - // RangeInclusive - check_mut(&vec[i..=j], &mut map[i..=j], &mut slice[i..=j]); - } - } - } -} diff --git a/src/mutable_keys.rs b/src/mutable_keys.rs index 7efc779..35a90c4 100644 --- a/src/mutable_keys.rs +++ b/src/mutable_keys.rs @@ -1,6 +1,8 @@ use core::hash::{BuildHasher, Hash}; -use super::{Bucket, Entries, Equivalent, IndexMap}; +use super::{Equivalent, IndexMap}; + +pub struct PrivateMarker {} /// Opt-in mutable access to keys. /// @@ -14,15 +16,11 @@ use super::{Bucket, Entries, Equivalent, IndexMap}; /// implementing PartialEq, Eq, or Hash incorrectly would be). /// /// `use` this trait to enable its methods for `IndexMap`. -/// -/// This trait is sealed and cannot be implemented for types outside this crate. -pub trait MutableKeys: private::Sealed { +pub trait MutableKeys { type Key; type Value; /// Return item index, mutable reference to key and value - /// - /// Computes in **O(1)** time (average). fn get_full_mut2<Q: ?Sized>( &mut self, key: &Q, @@ -30,13 +28,6 @@ pub trait MutableKeys: private::Sealed { where Q: Hash + Equivalent<Self::Key>; - /// Return mutable reference to key and value at an index. - /// - /// Valid indices are *0 <= index < self.len()* - /// - /// Computes in **O(1)** time. - fn get_index_mut2(&mut self, index: usize) -> Option<(&mut Self::Key, &mut Self::Value)>; - /// Scan through each key-value pair in the map and keep those where the /// closure `keep` returns `true`. /// @@ -47,6 +38,11 @@ pub trait MutableKeys: private::Sealed { fn retain2<F>(&mut self, keep: F) where F: FnMut(&mut Self::Key, &mut Self::Value) -> bool; + + /// This method is not useful in itself – it is there to “seal” the trait + /// for external implementation, so that we can add methods without + /// causing breaking changes. + fn __private_marker(&self) -> PrivateMarker; } /// Opt-in mutable access to keys. @@ -59,21 +55,11 @@ where { type Key = K; type Value = V; - fn get_full_mut2<Q: ?Sized>(&mut self, key: &Q) -> Option<(usize, &mut K, &mut V)> where Q: Hash + Equivalent<K>, { - if let Some(i) = self.get_index_of(key) { - let entry = &mut self.as_entries_mut()[i]; - Some((i, &mut entry.key, &mut entry.value)) - } else { - None - } - } - - fn get_index_mut2(&mut self, index: usize) -> Option<(&mut K, &mut V)> { - self.as_entries_mut().get_mut(index).map(Bucket::muts) + self.get_full_mut2_impl(key) } fn retain2<F>(&mut self, keep: F) @@ -82,10 +68,8 @@ where { self.retain_mut(keep) } -} - -mod private { - pub trait Sealed {} - impl<K, V, S> Sealed for super::IndexMap<K, V, S> {} + fn __private_marker(&self) -> PrivateMarker { + PrivateMarker {} + } } diff --git a/src/rayon/map.rs b/src/rayon/map.rs index 7559d54..8819f13 100644 --- a/src/rayon/map.rs +++ b/src/rayon/map.rs @@ -10,13 +10,11 @@ use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; use rayon::prelude::*; use crate::vec::Vec; -use alloc::boxed::Box; use core::cmp::Ordering; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::ops::RangeBounds; -use crate::map::Slice; use crate::Bucket; use crate::Entries; use crate::IndexMap; @@ -37,22 +35,6 @@ where } } -/// Requires crate feature `"rayon"`. -impl<K, V> IntoParallelIterator for Box<Slice<K, V>> -where - K: Send, - V: Send, -{ - type Item = (K, V); - type Iter = IntoParIter<K, V>; - - fn into_par_iter(self) -> Self::Iter { - IntoParIter { - entries: self.into_entries(), - } - } -} - /// A parallel owning iterator over the entries of a `IndexMap`. /// /// This `struct` is created by the [`into_par_iter`] method on [`IndexMap`] @@ -97,22 +79,6 @@ where } } -/// Requires crate feature `"rayon"`. -impl<'a, K, V> IntoParallelIterator for &'a Slice<K, V> -where - K: Sync, - V: Sync, -{ - type Item = (&'a K, &'a V); - type Iter = ParIter<'a, K, V>; - - fn into_par_iter(self) -> Self::Iter { - ParIter { - entries: &self.entries, - } - } -} - /// A parallel iterator over the entries of a `IndexMap`. /// /// This `struct` is created by the [`par_iter`] method on [`IndexMap`] @@ -163,22 +129,6 @@ where } } -/// Requires crate feature `"rayon"`. -impl<'a, K, V> IntoParallelIterator for &'a mut Slice<K, V> -where - K: Sync + Send, - V: Send, -{ - type Item = (&'a K, &'a mut V); - type Iter = ParIterMut<'a, K, V>; - - fn into_par_iter(self) -> Self::Iter { - ParIterMut { - entries: &mut self.entries, - } - } -} - /// A parallel mutable iterator over the entries of a `IndexMap`. /// /// This `struct` is created by the [`par_iter_mut`] method on [`IndexMap`] @@ -275,37 +225,6 @@ where } } -/// Parallel iterator methods and other parallel methods. -/// -/// The following methods **require crate feature `"rayon"`**. -/// -/// See also the `IntoParallelIterator` implementations. -impl<K, V> Slice<K, V> -where - K: Sync, - V: Sync, -{ - /// Return a parallel iterator over the keys of the map slice. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the slice is still preserved for operations like `reduce` and `collect`. - pub fn par_keys(&self) -> ParKeys<'_, K, V> { - ParKeys { - entries: &self.entries, - } - } - - /// Return a parallel iterator over the values of the map slice. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the slice is still preserved for operations like `reduce` and `collect`. - pub fn par_values(&self) -> ParValues<'_, K, V> { - ParValues { - entries: &self.entries, - } - } -} - impl<K, V, S> IndexMap<K, V, S> where K: Hash + Eq + Sync, @@ -412,23 +331,6 @@ where } } -/// Requires crate feature `"rayon"`. -impl<K, V> Slice<K, V> -where - K: Send, - V: Send, -{ - /// Return a parallel iterator over mutable references to the the values of the map slice. - /// - /// While parallel iterators can process items in any order, their relative order - /// in the slice is still preserved for operations like `reduce` and `collect`. - pub fn par_values_mut(&mut self) -> ParValuesMut<'_, K, V> { - ParValuesMut { - entries: &mut self.entries, - } - } -} - impl<K, V, S> IndexMap<K, V, S> where K: Hash + Eq + Send, diff --git a/src/rayon/set.rs b/src/rayon/set.rs index 0dc553f..6749dc0 100644 --- a/src/rayon/set.rs +++ b/src/rayon/set.rs @@ -10,13 +10,11 @@ use rayon::iter::plumbing::{Consumer, ProducerCallback, UnindexedConsumer}; use rayon::prelude::*; use crate::vec::Vec; -use alloc::boxed::Box; use core::cmp::Ordering; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::ops::RangeBounds; -use crate::set::Slice; use crate::Entries; use crate::IndexSet; @@ -37,21 +35,6 @@ where } } -/// Requires crate feature `"rayon"`. -impl<T> IntoParallelIterator for Box<Slice<T>> -where - T: Send, -{ - type Item = T; - type Iter = IntoParIter<T>; - - fn into_par_iter(self) -> Self::Iter { - IntoParIter { - entries: self.into_entries(), - } - } -} - /// A parallel owning iterator over the items of a `IndexSet`. /// /// This `struct` is created by the [`into_par_iter`] method on [`IndexSet`] @@ -95,21 +78,6 @@ where } } -/// Requires crate feature `"rayon"`. -impl<'a, T> IntoParallelIterator for &'a Slice<T> -where - T: Sync, -{ - type Item = &'a T; - type Iter = ParIter<'a, T>; - - fn into_par_iter(self) -> Self::Iter { - ParIter { - entries: &self.entries, - } - } -} - /// A parallel iterator over the items of a `IndexSet`. /// /// This `struct` is created by the [`par_iter`] method on [`IndexSet`] diff --git a/src/serde.rs b/src/serde.rs index d7473d3..c6dd6d5 100644 --- a/src/serde.rs +++ b/src/serde.rs @@ -10,7 +10,7 @@ use core::marker::PhantomData; use crate::IndexMap; -/// Requires crate feature `"serde"` +/// Requires crate feature `"serde"` or `"serde-1"` impl<K, V, S> Serialize for IndexMap<K, V, S> where K: Serialize + Hash + Eq, @@ -54,7 +54,7 @@ where } } -/// Requires crate feature `"serde"` +/// Requires crate feature `"serde"` or `"serde-1"` impl<'de, K, V, S> Deserialize<'de> for IndexMap<K, V, S> where K: Deserialize<'de> + Eq + Hash, @@ -85,7 +85,7 @@ where use crate::IndexSet; -/// Requires crate feature `"serde"` +/// Requires crate feature `"serde"` or `"serde-1"` impl<T, S> Serialize for IndexSet<T, S> where T: Serialize + Hash + Eq, @@ -127,7 +127,7 @@ where } } -/// Requires crate feature `"serde"` +/// Requires crate feature `"serde"` or `"serde-1"` impl<'de, T, S> Deserialize<'de> for IndexSet<T, S> where T: Deserialize<'de> + Eq + Hash, diff --git a/src/serde_seq.rs b/src/serde_seq.rs index 618e871..d326a02 100644 --- a/src/serde_seq.rs +++ b/src/serde_seq.rs @@ -18,7 +18,7 @@ //! } //! ``` //! -//! Requires crate feature `"serde"` +//! Requires crate feature `"serde"` or `"serde-1"` use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor}; use serde::ser::{Serialize, Serializer}; @@ -27,44 +27,8 @@ use core::fmt::{self, Formatter}; use core::hash::{BuildHasher, Hash}; use core::marker::PhantomData; -use crate::map::Slice as MapSlice; -use crate::set::Slice as SetSlice; use crate::IndexMap; -/// Serializes a `map::Slice` as an ordered sequence. -/// -/// This behaves like [`crate::serde_seq`] for `IndexMap`, serializing a sequence -/// of `(key, value)` pairs, rather than as a map that might not preserve order. -/// -/// Requires crate feature `"serde"` -impl<K, V> Serialize for MapSlice<K, V> -where - K: Serialize, - V: Serialize, -{ - fn serialize<T>(&self, serializer: T) -> Result<T::Ok, T::Error> - where - T: Serializer, - { - serializer.collect_seq(self) - } -} - -/// Serializes a `set::Slice` as an ordered sequence. -/// -/// Requires crate feature `"serde"` -impl<T> Serialize for SetSlice<T> -where - T: Serialize, -{ - fn serialize<Se>(&self, serializer: Se) -> Result<Se::Ok, Se::Error> - where - Se: Serializer, - { - serializer.collect_seq(self) - } -} - /// Serializes an `IndexMap` as an ordered sequence. /// /// This function may be used in a field attribute for deriving `Serialize`: @@ -80,7 +44,7 @@ where /// } /// ``` /// -/// Requires crate feature `"serde"` +/// Requires crate feature `"serde"` or `"serde-1"` pub fn serialize<K, V, S, T>(map: &IndexMap<K, V, S>, serializer: T) -> Result<T::Ok, T::Error> where K: Serialize + Hash + Eq, @@ -136,7 +100,7 @@ where /// } /// ``` /// -/// Requires crate feature `"serde"` +/// Requires crate feature `"serde"` or `"serde-1"` pub fn deserialize<'de, D, K, V, S>(deserializer: D) -> Result<IndexMap<K, V, S>, D::Error> where D: Deserializer<'de>, @@ -1,24 +1,18 @@ //! A hash set implemented using `IndexMap` -mod slice; - -pub use self::slice::Slice; - #[cfg(feature = "rayon")] pub use crate::rayon::set as rayon; -#[cfg(feature = "std")] +#[cfg(has_std)] use std::collections::hash_map::RandomState; -use crate::util::try_simplify_range; use crate::vec::{self, Vec}; -use alloc::boxed::Box; use core::cmp::Ordering; use core::fmt; use core::hash::{BuildHasher, Hash}; use core::iter::{Chain, FusedIterator}; use core::ops::{BitAnd, BitOr, BitXor, Index, RangeBounds, Sub}; -use core::slice::Iter as SliceIter; +use core::slice; use super::{Entries, Equivalent, IndexMap}; @@ -65,11 +59,11 @@ type Bucket<T> = super::Bucket<T, ()>; /// assert!(letters.contains(&'u')); /// assert!(!letters.contains(&'y')); /// ``` -#[cfg(feature = "std")] +#[cfg(has_std)] pub struct IndexSet<T, S = RandomState> { pub(crate) map: IndexMap<T, (), S>, } -#[cfg(not(feature = "std"))] +#[cfg(not(has_std))] pub struct IndexSet<T, S> { pub(crate) map: IndexMap<T, (), S>, } @@ -130,7 +124,7 @@ where } } -#[cfg(feature = "std")] +#[cfg(has_std)] impl<T> IndexSet<T> { /// Create a new set. (Does not allocate.) pub fn new() -> Self { @@ -657,20 +651,6 @@ where } impl<T, S> IndexSet<T, S> { - /// Returns a slice of all the values in the set. - /// - /// Computes in **O(1)** time. - pub fn as_slice(&self) -> &Slice<T> { - Slice::from_slice(self.as_entries()) - } - - /// Converts into a boxed slice of all the values in the set. - /// - /// Note that this will drop the inner hash table and any excess capacity. - pub fn into_boxed_slice(self) -> Box<Slice<T>> { - Slice::from_boxed(self.into_entries().into_boxed_slice()) - } - /// Get a value by index /// /// Valid indices are *0 <= index < self.len()* @@ -680,17 +660,6 @@ impl<T, S> IndexSet<T, S> { self.as_entries().get(index).map(Bucket::key_ref) } - /// Returns a slice of values in the given range of indices. - /// - /// Valid indices are *0 <= index < self.len()* - /// - /// Computes in **O(1)** time. - pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Slice<T>> { - let entries = self.as_entries(); - let range = try_simplify_range(range, entries.len())?; - entries.get(range).map(Slice::from_slice) - } - /// Get the first value /// /// Computes in **O(1)** time. @@ -836,14 +805,7 @@ impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { /// [`IndexSet`]: struct.IndexSet.html /// [`iter`]: struct.IndexSet.html#method.iter pub struct Iter<'a, T> { - iter: SliceIter<'a, Bucket<T>>, -} - -impl<'a, T> Iter<'a, T> { - /// Returns a slice of the remaining entries in the iterator. - pub fn as_slice(&self) -> &'a Slice<T> { - Slice::from_slice(self.iter.as_slice()) - } + iter: slice::Iter<'a, Bucket<T>>, } impl<'a, T> Iterator for Iter<'a, T> { @@ -947,7 +909,7 @@ where } } -#[cfg(feature = "std")] +#[cfg(has_std)] impl<T, const N: usize> From<[T; N]> for IndexSet<T, RandomState> where T: Eq + Hash, @@ -1940,7 +1902,7 @@ mod tests { } #[test] - #[cfg(feature = "std")] + #[cfg(has_std)] fn from_array() { let set1 = IndexSet::from([1, 2, 3, 4]); let set2: IndexSet<_> = [1, 2, 3, 4].into(); diff --git a/src/set/slice.rs b/src/set/slice.rs deleted file mode 100644 index 0924e8b..0000000 --- a/src/set/slice.rs +++ /dev/null @@ -1,282 +0,0 @@ -use super::{Bucket, Entries, IndexSet, IntoIter, Iter}; -use crate::util::try_simplify_range; - -use alloc::boxed::Box; -use alloc::vec::Vec; -use core::cmp::Ordering; -use core::fmt; -use core::hash::{Hash, Hasher}; -use core::ops::{self, Bound, Index, RangeBounds}; - -/// A dynamically-sized slice of values in an `IndexSet`. -/// -/// This supports indexed operations much like a `[T]` slice, -/// but not any hashed operations on the values. -/// -/// Unlike `IndexSet`, `Slice` does consider the order for `PartialEq` -/// and `Eq`, and it also implements `PartialOrd`, `Ord`, and `Hash`. -#[repr(transparent)] -pub struct Slice<T> { - pub(crate) entries: [Bucket<T>], -} - -// SAFETY: `Slice<T>` is a transparent wrapper around `[Bucket<T>]`, -// and reference lifetimes are bound together in function signatures. -#[allow(unsafe_code)] -impl<T> Slice<T> { - pub(super) fn from_slice(entries: &[Bucket<T>]) -> &Self { - unsafe { &*(entries as *const [Bucket<T>] as *const Self) } - } - - pub(super) fn from_boxed(entries: Box<[Bucket<T>]>) -> Box<Self> { - unsafe { Box::from_raw(Box::into_raw(entries) as *mut Self) } - } - - fn into_boxed(self: Box<Self>) -> Box<[Bucket<T>]> { - unsafe { Box::from_raw(Box::into_raw(self) as *mut [Bucket<T>]) } - } -} - -impl<T> Slice<T> { - pub(crate) fn into_entries(self: Box<Self>) -> Vec<Bucket<T>> { - self.into_boxed().into_vec() - } - - /// Return the number of elements in the set slice. - pub fn len(&self) -> usize { - self.entries.len() - } - - /// Returns true if the set slice contains no elements. - pub fn is_empty(&self) -> bool { - self.entries.is_empty() - } - - /// Get a value by index. - /// - /// Valid indices are *0 <= index < self.len()* - pub fn get_index(&self, index: usize) -> Option<&T> { - self.entries.get(index).map(Bucket::key_ref) - } - - /// Returns a slice of values in the given range of indices. - /// - /// Valid indices are *0 <= index < self.len()* - pub fn get_range<R: RangeBounds<usize>>(&self, range: R) -> Option<&Self> { - let range = try_simplify_range(range, self.entries.len())?; - self.entries.get(range).map(Self::from_slice) - } - - /// Get the first value. - pub fn first(&self) -> Option<&T> { - self.entries.first().map(Bucket::key_ref) - } - - /// Get the last value. - pub fn last(&self) -> Option<&T> { - self.entries.last().map(Bucket::key_ref) - } - - /// Divides one slice into two at an index. - /// - /// ***Panics*** if `index > len`. - pub fn split_at(&self, index: usize) -> (&Self, &Self) { - let (first, second) = self.entries.split_at(index); - (Self::from_slice(first), Self::from_slice(second)) - } - - /// Returns the first value and the rest of the slice, - /// or `None` if it is empty. - pub fn split_first(&self) -> Option<(&T, &Self)> { - if let [first, rest @ ..] = &self.entries { - Some((&first.key, Self::from_slice(rest))) - } else { - None - } - } - - /// Returns the last value and the rest of the slice, - /// or `None` if it is empty. - pub fn split_last(&self) -> Option<(&T, &Self)> { - if let [rest @ .., last] = &self.entries { - Some((&last.key, Self::from_slice(rest))) - } else { - None - } - } - - /// Return an iterator over the values of the set slice. - pub fn iter(&self) -> Iter<'_, T> { - Iter { - iter: self.entries.iter(), - } - } -} - -impl<'a, T> IntoIterator for &'a Slice<T> { - type IntoIter = Iter<'a, T>; - type Item = &'a T; - - fn into_iter(self) -> Self::IntoIter { - self.iter() - } -} - -impl<T> IntoIterator for Box<Slice<T>> { - type IntoIter = IntoIter<T>; - type Item = T; - - fn into_iter(self) -> Self::IntoIter { - IntoIter { - iter: self.into_entries().into_iter(), - } - } -} - -impl<T> Default for &'_ Slice<T> { - fn default() -> Self { - Slice::from_slice(&[]) - } -} - -impl<T> Default for Box<Slice<T>> { - fn default() -> Self { - Slice::from_boxed(Box::default()) - } -} - -impl<T: Clone> Clone for Box<Slice<T>> { - fn clone(&self) -> Self { - Slice::from_boxed(self.entries.to_vec().into_boxed_slice()) - } -} - -impl<T: Copy> From<&Slice<T>> for Box<Slice<T>> { - fn from(slice: &Slice<T>) -> Self { - Slice::from_boxed(Box::from(&slice.entries)) - } -} - -impl<T: fmt::Debug> fmt::Debug for Slice<T> { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_list().entries(self).finish() - } -} - -impl<T: PartialEq> PartialEq for Slice<T> { - fn eq(&self, other: &Self) -> bool { - self.len() == other.len() && self.iter().eq(other) - } -} - -impl<T: Eq> Eq for Slice<T> {} - -impl<T: PartialOrd> PartialOrd for Slice<T> { - fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - self.iter().partial_cmp(other) - } -} - -impl<T: Ord> Ord for Slice<T> { - fn cmp(&self, other: &Self) -> Ordering { - self.iter().cmp(other) - } -} - -impl<T: Hash> Hash for Slice<T> { - fn hash<H: Hasher>(&self, state: &mut H) { - self.len().hash(state); - for value in self { - value.hash(state); - } - } -} - -impl<T> Index<usize> for Slice<T> { - type Output = T; - - fn index(&self, index: usize) -> &Self::Output { - &self.entries[index].key - } -} - -// We can't have `impl<I: RangeBounds<usize>> Index<I>` because that conflicts with `Index<usize>`. -// Instead, we repeat the implementations for all the core range types. -macro_rules! impl_index { - ($($range:ty),*) => {$( - impl<T, S> Index<$range> for IndexSet<T, S> { - type Output = Slice<T>; - - fn index(&self, range: $range) -> &Self::Output { - Slice::from_slice(&self.as_entries()[range]) - } - } - - impl<T> Index<$range> for Slice<T> { - type Output = Self; - - fn index(&self, range: $range) -> &Self::Output { - Slice::from_slice(&self.entries[range]) - } - } - )*} -} -impl_index!( - ops::Range<usize>, - ops::RangeFrom<usize>, - ops::RangeFull, - ops::RangeInclusive<usize>, - ops::RangeTo<usize>, - ops::RangeToInclusive<usize>, - (Bound<usize>, Bound<usize>) -); - -#[cfg(test)] -mod tests { - use super::*; - use alloc::vec::Vec; - - #[test] - fn slice_index() { - fn check(vec_slice: &[i32], set_slice: &Slice<i32>, sub_slice: &Slice<i32>) { - assert_eq!(set_slice as *const _, sub_slice as *const _); - itertools::assert_equal(vec_slice, set_slice); - } - - let vec: Vec<i32> = (0..10).map(|i| i * i).collect(); - let set: IndexSet<i32> = vec.iter().cloned().collect(); - let slice = set.as_slice(); - - // RangeFull - check(&vec[..], &set[..], &slice[..]); - - for i in 0usize..10 { - // Index - assert_eq!(vec[i], set[i]); - assert_eq!(vec[i], slice[i]); - - // RangeFrom - check(&vec[i..], &set[i..], &slice[i..]); - - // RangeTo - check(&vec[..i], &set[..i], &slice[..i]); - - // RangeToInclusive - check(&vec[..=i], &set[..=i], &slice[..=i]); - - // (Bound<usize>, Bound<usize>) - let bounds = (Bound::Excluded(i), Bound::Unbounded); - check(&vec[i + 1..], &set[bounds], &slice[bounds]); - - for j in i..=10 { - // Range - check(&vec[i..j], &set[i..j], &slice[i..j]); - } - - for j in i..10 { - // RangeInclusive - check(&vec[i..=j], &set[i..=j], &slice[i..=j]); - } - } - } -} diff --git a/src/util.rs b/src/util.rs index 377ff51..a24dfaf 100644 --- a/src/util.rs +++ b/src/util.rs @@ -29,25 +29,3 @@ where } start..end } - -pub(crate) fn try_simplify_range<R>(range: R, len: usize) -> Option<Range<usize>> -where - R: RangeBounds<usize>, -{ - let start = match range.start_bound() { - Bound::Unbounded => 0, - Bound::Included(&i) if i <= len => i, - Bound::Excluded(&i) if i < len => i + 1, - _ => return None, - }; - let end = match range.end_bound() { - Bound::Unbounded => len, - Bound::Excluded(&i) if i <= len => i, - Bound::Included(&i) if i < len => i + 1, - _ => return None, - }; - if start > end { - return None; - } - Some(start..end) -} diff --git a/test-nostd/Cargo.toml b/test-nostd/Cargo.toml deleted file mode 100644 index 64d209a..0000000 --- a/test-nostd/Cargo.toml +++ /dev/null @@ -1,12 +0,0 @@ -[package] -name = "test-nostd" -version = "0.1.0" -publish = false -edition = "2021" - -[dependencies.indexmap] -path = ".." -default-features = false -features = ["serde"] - -[dev-dependencies] diff --git a/test-nostd/src/lib.rs b/test-nostd/src/lib.rs deleted file mode 100644 index 27bfe60..0000000 --- a/test-nostd/src/lib.rs +++ /dev/null @@ -1,36 +0,0 @@ -#![no_std] - -use core::hash::BuildHasherDefault; -use core::hash::Hasher; - -use indexmap::IndexMap; -use indexmap::IndexSet; - -#[derive(Default)] -struct BadHasher(u64); - -impl Hasher for BadHasher { - fn finish(&self) -> u64 { - self.0 - } - fn write(&mut self, bytes: &[u8]) { - for &byte in bytes { - self.0 += byte as u64 - } - } -} - -type Map<K, V> = IndexMap<K, V, BuildHasherDefault<BadHasher>>; -type Set<T> = IndexSet<T, BuildHasherDefault<BadHasher>>; - -pub fn test_compile() { - let mut map = Map::default(); - map.insert(1, 1); - map.insert(2, 4); - for (_, _) in map.iter() {} - - let _map2 = Map::from_iter(Some((1, 1))); - - let mut set = Set::default(); - set.insert("a"); -} diff --git a/test-serde/Cargo.toml b/test-serde/Cargo.toml deleted file mode 100644 index bf04c9f..0000000 --- a/test-serde/Cargo.toml +++ /dev/null @@ -1,13 +0,0 @@ -[package] -name = "test-serde" -version = "0.1.0" -publish = false -edition = "2021" - -[dependencies] - -[dev-dependencies] -fnv = "1.0" -indexmap = { path = "..", features = ["serde"] } -serde = { version = "1.0.99", features = ["derive"] } -serde_test = "1.0.99" diff --git a/test-serde/src/lib.rs b/test-serde/src/lib.rs deleted file mode 100644 index b78a752..0000000 --- a/test-serde/src/lib.rs +++ /dev/null @@ -1,115 +0,0 @@ -#![cfg(test)] - -use fnv::FnvBuildHasher; -use indexmap::{indexmap, indexset, IndexMap, IndexSet}; -use serde::{Deserialize, Serialize}; -use serde_test::{assert_tokens, Token}; - -#[test] -fn test_serde_map() { - let map = indexmap! { 1 => 2, 3 => 4 }; - assert_tokens( - &map, - &[ - Token::Map { len: Some(2) }, - Token::I32(1), - Token::I32(2), - Token::I32(3), - Token::I32(4), - Token::MapEnd, - ], - ); -} - -#[test] -fn test_serde_set() { - let set = indexset! { 1, 2, 3, 4 }; - assert_tokens( - &set, - &[ - Token::Seq { len: Some(4) }, - Token::I32(1), - Token::I32(2), - Token::I32(3), - Token::I32(4), - Token::SeqEnd, - ], - ); -} - -#[test] -fn test_serde_map_fnv_hasher() { - let mut map: IndexMap<i32, i32, FnvBuildHasher> = Default::default(); - map.insert(1, 2); - map.insert(3, 4); - assert_tokens( - &map, - &[ - Token::Map { len: Some(2) }, - Token::I32(1), - Token::I32(2), - Token::I32(3), - Token::I32(4), - Token::MapEnd, - ], - ); -} - -#[test] -fn test_serde_set_fnv_hasher() { - let mut set: IndexSet<i32, FnvBuildHasher> = Default::default(); - set.extend(1..5); - assert_tokens( - &set, - &[ - Token::Seq { len: Some(4) }, - Token::I32(1), - Token::I32(2), - Token::I32(3), - Token::I32(4), - Token::SeqEnd, - ], - ); -} - -#[test] -fn test_serde_seq_map() { - #[derive(Debug, Deserialize, Serialize)] - #[serde(transparent)] - struct SeqIndexMap { - #[serde(with = "indexmap::serde_seq")] - map: IndexMap<i32, i32>, - } - - impl PartialEq for SeqIndexMap { - fn eq(&self, other: &Self) -> bool { - // explicitly compare items in order - self.map.iter().eq(&other.map) - } - } - - let map = indexmap! { 1 => 2, 3 => 4, -1 => -2, -3 => -4 }; - assert_tokens( - &SeqIndexMap { map }, - &[ - Token::Seq { len: Some(4) }, - Token::Tuple { len: 2 }, - Token::I32(1), - Token::I32(2), - Token::TupleEnd, - Token::Tuple { len: 2 }, - Token::I32(3), - Token::I32(4), - Token::TupleEnd, - Token::Tuple { len: 2 }, - Token::I32(-1), - Token::I32(-2), - Token::TupleEnd, - Token::Tuple { len: 2 }, - Token::I32(-3), - Token::I32(-4), - Token::TupleEnd, - Token::SeqEnd, - ], - ); -} |