diff options
author | Joel Galenson <jgalenson@google.com> | 2021-08-12 21:01:24 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2021-08-12 21:01:24 +0000 |
commit | 3309edccc3675969720efdd9b8f15e7a86e8c918 (patch) | |
tree | d491e6133a10e7ac0f7aec3e5d2fe25cc87e92b7 | |
parent | 31fb06ec299af051eb2e5e7af53eaeac6932aee2 (diff) | |
parent | 48091efd682edfb00ce65c3f6d0bcdbf8947a27a (diff) | |
download | slab-3309edccc3675969720efdd9b8f15e7a86e8c918.tar.gz |
Upgrade rust/crates/slab to 0.4.4 am: bf78b2784b am: 48091efd68
Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/slab/+/1791008
Change-Id: I062d701b2b89928086d53e89ea6c2ca17acbe01e
-rw-r--r-- | .cargo_vcs_info.json | 2 | ||||
-rw-r--r-- | .clippy.toml | 1 | ||||
-rw-r--r-- | .github/workflows/ci.yml | 73 | ||||
-rw-r--r-- | Android.bp | 32 | ||||
-rw-r--r-- | CHANGELOG.md | 9 | ||||
-rw-r--r-- | Cargo.toml | 15 | ||||
-rw-r--r-- | Cargo.toml.orig | 11 | ||||
-rw-r--r-- | METADATA | 8 | ||||
-rw-r--r-- | README.md | 6 | ||||
-rw-r--r-- | src/lib.rs | 287 | ||||
-rw-r--r-- | src/serde.rs | 24 | ||||
-rw-r--r-- | tests/serde.rs | 15 | ||||
-rw-r--r-- | tests/slab.rs | 51 |
13 files changed, 295 insertions, 239 deletions
diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json index c04db22..820133c 100644 --- a/.cargo_vcs_info.json +++ b/.cargo_vcs_info.json @@ -1,5 +1,5 @@ { "git": { - "sha1": "c0bc5dc5cd55d54ae618f06cf4c7550c8bbccf76" + "sha1": "76d9ca4e0c0313c1eeafa691e11446906e2bb4a7" } } diff --git a/.clippy.toml b/.clippy.toml deleted file mode 100644 index f4b2f18..0000000 --- a/.clippy.toml +++ /dev/null @@ -1 +0,0 @@ -msrv = "1.27" diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml deleted file mode 100644 index 08eae51..0000000 --- a/.github/workflows/ci.yml +++ /dev/null @@ -1,73 +0,0 @@ -name: CI - -on: - pull_request: - branches: - - master - push: - branches: - - master - -env: - RUSTFLAGS: -Dwarnings - RUST_BACKTRACE: 1 - -jobs: - test: - strategy: - matrix: - rust: - - stable - - nightly - runs-on: ubuntu-latest - steps: - - uses: actions/checkout@v2 - - name: Install Rust - run: rustup update ${{ matrix.rust }} && rustup default ${{ matrix.rust }} - - name: Install cargo-hack - run: cargo install cargo-hack - - run: cargo hack build --feature-powerset --optional-deps --no-dev-deps - - run: cargo test --all-features - - minrust: - strategy: - matrix: - rust: - # This is the minimum supported Rust version of this crate. - - 1.27.0 - runs-on: ubuntu-latest - steps: - - uses: actions/checkout@v2 - - name: Install Rust - run: rustup update ${{ matrix.rust }} && rustup default ${{ matrix.rust }} - - run: cargo build - - no-std: - strategy: - matrix: - rust: - # This is the minimum supported Rust version for "no_std" - - 1.36.0 - runs-on: ubuntu-latest - steps: - - uses: actions/checkout@v2 - - name: Install Rust - run: rustup update ${{ matrix.rust }} && rustup default ${{ matrix.rust }} - - run: rustup target add thumbv7m-none-eabi - - run: cargo build --no-default-features --target thumbv7m-none-eabi - - clippy: - runs-on: ubuntu-latest - steps: - - uses: actions/checkout@v2 - - name: Install Rust - run: rustup update stable && rustup default stable - - run: cargo clippy --all-features - - rustfmt: - runs-on: ubuntu-latest - steps: - - uses: actions/checkout@v2 - - name: Install Rust - run: rustup update stable && rustup default stable - - run: cargo fmt --all -- --check @@ -23,7 +23,7 @@ rust_library { host_supported: true, crate_name: "slab", srcs: ["src/lib.rs"], - edition: "2015", + edition: "2018", features: [ "default", "std", @@ -37,12 +37,12 @@ rust_library { } rust_defaults { - name: "slab_defaults", + name: "slab_test_defaults", crate_name: "slab", srcs: ["src/lib.rs"], test_suites: ["general-tests"], auto_gen_config: true, - edition: "2015", + edition: "2018", features: [ "default", "std", @@ -55,7 +55,7 @@ rust_defaults { rust_test_host { name: "slab_host_test_src_lib", - defaults: ["slab_defaults"], + defaults: ["slab_test_defaults"], test_options: { unit_test: true, }, @@ -63,15 +63,15 @@ rust_test_host { rust_test { name: "slab_device_test_src_lib", - defaults: ["slab_defaults"], + defaults: ["slab_test_defaults"], } rust_defaults { - name: "slab_defaults_slab", + name: "slab_test_defaults_slab", crate_name: "slab", test_suites: ["general-tests"], auto_gen_config: true, - edition: "2015", + edition: "2018", features: [ "default", "std", @@ -85,7 +85,7 @@ rust_defaults { rust_test_host { name: "slab_host_test_tests_serde", - defaults: ["slab_defaults_slab"], + defaults: ["slab_test_defaults_slab"], srcs: ["tests/serde.rs"], test_options: { unit_test: true, @@ -94,13 +94,13 @@ rust_test_host { rust_test { name: "slab_device_test_tests_serde", - defaults: ["slab_defaults_slab"], + defaults: ["slab_test_defaults_slab"], srcs: ["tests/serde.rs"], } rust_test_host { name: "slab_host_test_tests_slab", - defaults: ["slab_defaults_slab"], + defaults: ["slab_test_defaults_slab"], srcs: ["tests/slab.rs"], test_options: { unit_test: true, @@ -109,15 +109,15 @@ rust_test_host { rust_test { name: "slab_device_test_tests_slab", - defaults: ["slab_defaults_slab"], + defaults: ["slab_test_defaults_slab"], srcs: ["tests/slab.rs"], } // dependent_library ["feature_list"] -// proc-macro2-1.0.27 "default,proc-macro" +// proc-macro2-1.0.28 "default,proc-macro" // quote-1.0.9 "default,proc-macro" -// serde-1.0.126 "default,derive,serde_derive,std" -// serde_derive-1.0.126 "default" -// serde_test-1.0.126 -// syn-1.0.72 "clone-impls,default,derive,parsing,printing,proc-macro,quote" +// serde-1.0.127 "default,derive,serde_derive,std" +// serde_derive-1.0.127 "default" +// serde_test-1.0.127 +// syn-1.0.74 "clone-impls,default,derive,parsing,printing,proc-macro,quote" // unicode-xid-0.2.2 "default" diff --git a/CHANGELOG.md b/CHANGELOG.md index 952e7d4..5b5edd8 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1,4 +1,11 @@ -# 0.4.3 (February 6, 2021) +# 0.4.4 (August 06, 2021) + +* Fix panic in `FromIterator` impl (#102) +* Fix compatibility with older clippy versions (#104) +* Add `try_remove` method (#89) +* Implement `ExactSizeIterator` and `FusedIterator` for iterators (#92) + +# 0.4.3 (April 20, 2021) * Add no_std support for Rust 1.36 and above (#71). * Add `get2_mut` and `get2_unchecked_mut` methods (#65). @@ -3,20 +3,21 @@ # When uploading crates to the registry Cargo will automatically # "normalize" Cargo.toml files for maximal compatibility # with all versions of Cargo and also rewrite `path` dependencies -# to registry (e.g., crates.io) dependencies +# to registry (e.g., crates.io) dependencies. # -# If you believe there's an error in this file please file an -# issue against the rust-lang/cargo repository. If you're -# editing this file be aware that the upstream Cargo.toml -# will likely look very different (and much more reasonable) +# 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] +edition = "2018" name = "slab" -version = "0.4.3" +version = "0.4.4" authors = ["Carl Lerche <me@carllerche.com>"] +exclude = ["/.*"] description = "Pre-allocated storage for a uniform data type" homepage = "https://github.com/tokio-rs/slab" -documentation = "https://docs.rs/slab/0.4.3/slab/" +documentation = "https://docs.rs/slab" readme = "README.md" keywords = ["slab", "allocator", "no_std"] categories = ["memory-management", "data-structures", "no-std"] diff --git a/Cargo.toml.orig b/Cargo.toml.orig index 7684a02..b017ada 100644 --- a/Cargo.toml.orig +++ b/Cargo.toml.orig @@ -5,20 +5,19 @@ name = "slab" # - Update version number # - README.md # - Update CHANGELOG.md -# - Update doc URL. -# - Cargo.toml -# - README.md # - Create git tag -version = "0.4.3" -license = "MIT" +version = "0.4.4" authors = ["Carl Lerche <me@carllerche.com>"] +edition = "2018" +license = "MIT" description = "Pre-allocated storage for a uniform data type" -documentation = "https://docs.rs/slab/0.4.3/slab/" +documentation = "https://docs.rs/slab" homepage = "https://github.com/tokio-rs/slab" repository = "https://github.com/tokio-rs/slab" readme = "README.md" keywords = ["slab", "allocator", "no_std"] categories = ["memory-management", "data-structures", "no-std"] +exclude = ["/.*"] [features] std = [] @@ -7,13 +7,13 @@ third_party { } url { type: ARCHIVE - value: "https://static.crates.io/crates/slab/slab-0.4.3.crate" + value: "https://static.crates.io/crates/slab/slab-0.4.4.crate" } - version: "0.4.3" + version: "0.4.4" license_type: NOTICE last_upgrade_date { year: 2021 - month: 6 - day: 8 + month: 8 + day: 9 } } @@ -10,7 +10,7 @@ Pre-allocated storage for a uniform data type. [ci-badge]: https://img.shields.io/github/workflow/status/tokio-rs/slab/CI/master [ci-url]: https://github.com/tokio-rs/slab/actions -[Documentation](https://docs.rs/slab/0.4.3/slab/) +[Documentation](https://docs.rs/slab) ## Usage @@ -18,14 +18,12 @@ To use `slab`, first add this to your `Cargo.toml`: ```toml [dependencies] -slab = "0.4.3" +slab = "0.4" ``` Next, add this to your crate: ```rust -extern crate slab; - use slab::Slab; let mut slab = Slab::new(); @@ -1,6 +1,14 @@ -#![warn(missing_docs, missing_debug_implementations)] -#![cfg_attr(test, warn(unreachable_pub))] #![cfg_attr(not(feature = "std"), no_std)] +#![warn( + missing_debug_implementations, + missing_docs, + rust_2018_idioms, + unreachable_pub +)] +#![doc(test( + no_crate_inject, + attr(deny(warnings, rust_2018_idioms), allow(dead_code, unused_variables)) +))] //! Pre-allocated storage for a uniform data type. //! @@ -105,24 +113,15 @@ #[cfg(not(feature = "std"))] extern crate alloc; #[cfg(feature = "std")] -extern crate core; +extern crate std as alloc; #[cfg(feature = "serde")] mod serde; -#[cfg(not(feature = "std"))] -use alloc::vec::Vec; - -#[cfg(not(feature = "std"))] -use alloc::vec; - -use core::iter::FromIterator; - +use alloc::vec::{self, Vec}; +use core::iter::{self, FromIterator, FusedIterator}; use core::{fmt, mem, ops, slice}; -#[cfg(feature = "std")] -use std::vec; - /// Pre-allocated storage for a uniform data type /// /// See the [module documentation] for more details. @@ -170,31 +169,34 @@ impl<T> Default for Slab<T> { /// assert_eq!("hello", slab[hello].1); /// ``` #[derive(Debug)] -pub struct VacantEntry<'a, T: 'a> { +pub struct VacantEntry<'a, T> { slab: &'a mut Slab<T>, key: usize, } /// A consuming iterator over the values stored in a `Slab` pub struct IntoIter<T> { - entries: vec::IntoIter<Entry<T>>, - curr: usize, + entries: iter::Enumerate<vec::IntoIter<Entry<T>>>, + len: usize, } /// An iterator over the values stored in the `Slab` -pub struct Iter<'a, T: 'a> { - entries: slice::Iter<'a, Entry<T>>, - curr: usize, +pub struct Iter<'a, T> { + entries: iter::Enumerate<slice::Iter<'a, Entry<T>>>, + len: usize, } /// A mutable iterator over the values stored in the `Slab` -pub struct IterMut<'a, T: 'a> { - entries: slice::IterMut<'a, Entry<T>>, - curr: usize, +pub struct IterMut<'a, T> { + entries: iter::Enumerate<slice::IterMut<'a, Entry<T>>>, + len: usize, } /// A draining iterator for `Slab` -pub struct Drain<'a, T: 'a>(vec::Drain<'a, Entry<T>>); +pub struct Drain<'a, T> { + inner: vec::Drain<'a, Entry<T>>, + len: usize, +} #[derive(Clone)] enum Entry<T> { @@ -304,7 +306,7 @@ impl<T> Slab<T> { /// more values. /// /// `reserve_exact` does nothing if the slab already has sufficient capacity - /// for `additional` more valus. If more capacity is required, a new segment + /// for `additional` more values. If more capacity is required, a new segment /// of memory will be allocated and all existing values will be copied into /// it. As such, if the slab is already very large, a call to `reserve` can /// end up being expensive. @@ -469,11 +471,11 @@ impl<T> Slab<T> { F: FnMut(&mut T, usize, usize) -> bool, { // If the closure unwinds, we need to restore a valid list of vacant entries - struct CleanupGuard<'a, T: 'a> { + struct CleanupGuard<'a, T> { slab: &'a mut Slab<T>, decrement: bool, } - impl<'a, T: 'a> Drop for CleanupGuard<'a, T> { + impl<T> Drop for CleanupGuard<'_, T> { fn drop(&mut self) { if self.decrement { // Value was popped and not pushed back on @@ -491,7 +493,7 @@ impl<T> Slab<T> { // While there are vacant entries while guard.slab.entries.len() > guard.slab.len { // Find a value that needs to be moved, - // by popping entries until we find an occopied one. + // by popping entries until we find an occupied one. // (entries cannot be empty because 0 is not greater than anything) if let Some(Entry::Occupied(mut value)) = guard.slab.entries.pop() { // Found one, now find a vacant entry to move it to @@ -598,10 +600,10 @@ impl<T> Slab<T> { /// assert_eq!(iterator.next(), Some((2, &2))); /// assert_eq!(iterator.next(), None); /// ``` - pub fn iter(&self) -> Iter<T> { + pub fn iter(&self) -> Iter<'_, T> { Iter { - entries: self.entries.iter(), - curr: 0, + entries: self.entries.iter().enumerate(), + len: self.len, } } @@ -630,10 +632,10 @@ impl<T> Slab<T> { /// assert_eq!(slab[key1], 2); /// assert_eq!(slab[key2], 1); /// ``` - pub fn iter_mut(&mut self) -> IterMut<T> { + pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut { - entries: self.entries.iter_mut(), - curr: 0, + entries: self.entries.iter_mut().enumerate(), + len: self.len, } } @@ -733,6 +735,8 @@ impl<T> Slab<T> { /// Return a reference to the value associated with the given key without /// performing bounds checking. /// + /// For a safe alternative see [`get`](Slab::get). + /// /// This function should be used with care. /// /// # Safety @@ -760,6 +764,8 @@ impl<T> Slab<T> { /// Return a mutable reference to the value associated with the given key /// without performing bounds checking. /// + /// For a safe alternative see [`get_mut`](Slab::get_mut). + /// /// This function should be used with care. /// /// # Safety @@ -791,6 +797,8 @@ impl<T> Slab<T> { /// given keys simultaneously without performing bounds checking and safety /// condition checking. /// + /// For a safe alternative see [`get2_mut`](Slab::get2_mut). + /// /// This function should be used with care. /// /// # Safety @@ -846,7 +854,7 @@ impl<T> Slab<T> { /// assert_eq!(slab.key_of(value), key); /// ``` /// - /// Values are not compared, so passing a reference to a different locaton + /// Values are not compared, so passing a reference to a different location /// will result in a panic: /// /// ```should_panic @@ -923,7 +931,7 @@ impl<T> Slab<T> { /// assert_eq!(hello, slab[hello].0); /// assert_eq!("hello", slab[hello].1); /// ``` - pub fn vacant_entry(&mut self) -> VacantEntry<T> { + pub fn vacant_entry(&mut self) -> VacantEntry<'_, T> { VacantEntry { key: self.next, slab: self, @@ -945,15 +953,12 @@ impl<T> Slab<T> { } } - /// Remove and return the value associated with the given key. + /// Tries to remove the value associated with the given key, + /// returning the value if the key existed. /// /// The key is then released and may be associated with future stored /// values. /// - /// # Panics - /// - /// Panics if `key` is not associated with a value. - /// /// # Examples /// /// ``` @@ -962,10 +967,10 @@ impl<T> Slab<T> { /// /// let hello = slab.insert("hello"); /// - /// assert_eq!(slab.remove(hello), "hello"); + /// assert_eq!(slab.try_remove(hello), Some("hello")); /// assert!(!slab.contains(hello)); /// ``` - pub fn remove(&mut self, key: usize) -> T { + pub fn try_remove(&mut self, key: usize) -> Option<T> { if let Some(entry) = self.entries.get_mut(key) { // Swap the entry at the provided value let prev = mem::replace(entry, Entry::Vacant(self.next)); @@ -974,7 +979,7 @@ impl<T> Slab<T> { Entry::Occupied(val) => { self.len -= 1; self.next = key; - return val; + return val.into(); } _ => { // Woops, the entry is actually vacant, restore the state @@ -982,7 +987,31 @@ impl<T> Slab<T> { } } } - panic!("invalid key"); + None + } + + /// Remove and return the value associated with the given key. + /// + /// The key is then released and may be associated with future stored + /// values. + /// + /// # Panics + /// + /// Panics if `key` is not associated with a value. + /// + /// # Examples + /// + /// ``` + /// # use slab::*; + /// let mut slab = Slab::new(); + /// + /// let hello = slab.insert("hello"); + /// + /// assert_eq!(slab.remove(hello), "hello"); + /// assert!(!slab.contains(hello)); + /// ``` + pub fn remove(&mut self, key: usize) -> T { + self.try_remove(key).expect("invalid key") } /// Return `true` if a value is associated with the given key. @@ -1074,10 +1103,14 @@ impl<T> Slab<T> { /// /// assert!(slab.is_empty()); /// ``` - pub fn drain(&mut self) -> Drain<T> { + pub fn drain(&mut self) -> Drain<'_, T> { + let old_len = self.len; self.len = 0; self.next = 0; - Drain(self.entries.drain(..)) + Drain { + inner: self.entries.drain(..), + len: old_len, + } } } @@ -1107,8 +1140,8 @@ impl<T> IntoIterator for Slab<T> { fn into_iter(self) -> IntoIter<T> { IntoIter { - entries: self.entries.into_iter(), - curr: 0, + entries: self.entries.into_iter().enumerate(), + len: self.len, } } } @@ -1170,6 +1203,7 @@ impl<T> FromIterator<(usize, T)> for Slab<T> { let mut slab = Self::with_capacity(iterator.size_hint().0); let mut vacant_list_broken = false; + let mut first_vacant_index = None; for (key, value) in iterator { if key < slab.entries.len() { // iterator is not sorted, might need to recreate vacant list @@ -1178,9 +1212,12 @@ impl<T> FromIterator<(usize, T)> for Slab<T> { slab.len += 1; } // if an element with this key already exists, replace it. - // This is consisent with HashMap and BtreeMap + // This is consistent with HashMap and BtreeMap slab.entries[key] = Entry::Occupied(value); } else { + if first_vacant_index.is_none() && slab.entries.len() < key { + first_vacant_index = Some(slab.entries.len()); + } // insert holes as necessary while slab.entries.len() < key { // add the entry to the start of the vacant list @@ -1193,11 +1230,20 @@ impl<T> FromIterator<(usize, T)> for Slab<T> { } } if slab.len == slab.entries.len() { - // no vacant enries, so next might not have been updated + // no vacant entries, so next might not have been updated slab.next = slab.entries.len(); } else if vacant_list_broken { slab.recreate_vacant_list(); + } else if let Some(first_vacant_index) = first_vacant_index { + let next = slab.entries.len(); + match &mut slab.entries[first_vacant_index] { + Entry::Vacant(n) => *n = next, + _ => unreachable!(), + } + } else { + unreachable!() } + slab } } @@ -1206,7 +1252,7 @@ impl<T> fmt::Debug for Slab<T> where T: fmt::Debug, { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { fmt.debug_struct("Slab") .field("len", &self.len) .field("cap", &self.capacity()) @@ -1218,40 +1264,37 @@ impl<T> fmt::Debug for IntoIter<T> where T: fmt::Debug, { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { fmt.debug_struct("Iter") - .field("curr", &self.curr) - .field("remaining", &self.entries.len()) + .field("remaining", &self.len) .finish() } } -impl<'a, T: 'a> fmt::Debug for Iter<'a, T> +impl<T> fmt::Debug for Iter<'_, T> where T: fmt::Debug, { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { fmt.debug_struct("Iter") - .field("curr", &self.curr) - .field("remaining", &self.entries.len()) + .field("remaining", &self.len) .finish() } } -impl<'a, T: 'a> fmt::Debug for IterMut<'a, T> +impl<T> fmt::Debug for IterMut<'_, T> where T: fmt::Debug, { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { fmt.debug_struct("IterMut") - .field("curr", &self.curr) - .field("remaining", &self.entries.len()) + .field("remaining", &self.len) .finish() } } -impl<'a, T: 'a> fmt::Debug for Drain<'a, T> { - fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result { +impl<T> fmt::Debug for Drain<'_, T> { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { fmt.debug_struct("Drain").finish() } } @@ -1321,137 +1364,173 @@ impl<'a, T> VacantEntry<'a, T> { impl<T> Iterator for IntoIter<T> { type Item = (usize, T); - fn next(&mut self) -> Option<(usize, T)> { - while let Some(entry) = self.entries.next() { - let curr = self.curr; - self.curr += 1; - + fn next(&mut self) -> Option<Self::Item> { + for (key, entry) in &mut self.entries { if let Entry::Occupied(v) = entry { - return Some((curr, v)); + self.len -= 1; + return Some((key, v)); } } + debug_assert_eq!(self.len, 0); None } fn size_hint(&self) -> (usize, Option<usize>) { - (0, Some(self.entries.len())) + (self.len, Some(self.len)) } } impl<T> DoubleEndedIterator for IntoIter<T> { - fn next_back(&mut self) -> Option<(usize, T)> { - while let Some(entry) = self.entries.next_back() { + fn next_back(&mut self) -> Option<Self::Item> { + while let Some((key, entry)) = self.entries.next_back() { if let Entry::Occupied(v) = entry { - let key = self.curr + self.entries.len(); + self.len -= 1; return Some((key, v)); } } + debug_assert_eq!(self.len, 0); None } } +impl<T> ExactSizeIterator for IntoIter<T> { + fn len(&self) -> usize { + self.len + } +} + +impl<T> FusedIterator for IntoIter<T> {} + // ===== Iter ===== impl<'a, T> Iterator for Iter<'a, T> { type Item = (usize, &'a T); - fn next(&mut self) -> Option<(usize, &'a T)> { - while let Some(entry) = self.entries.next() { - let curr = self.curr; - self.curr += 1; - + fn next(&mut self) -> Option<Self::Item> { + for (key, entry) in &mut self.entries { if let Entry::Occupied(ref v) = *entry { - return Some((curr, v)); + self.len -= 1; + return Some((key, v)); } } + debug_assert_eq!(self.len, 0); None } fn size_hint(&self) -> (usize, Option<usize>) { - (0, Some(self.entries.len())) + (self.len, Some(self.len)) } } -impl<'a, T> DoubleEndedIterator for Iter<'a, T> { - fn next_back(&mut self) -> Option<(usize, &'a T)> { - while let Some(entry) = self.entries.next_back() { +impl<T> DoubleEndedIterator for Iter<'_, T> { + fn next_back(&mut self) -> Option<Self::Item> { + while let Some((key, entry)) = self.entries.next_back() { if let Entry::Occupied(ref v) = *entry { - let key = self.curr + self.entries.len(); + self.len -= 1; return Some((key, v)); } } + debug_assert_eq!(self.len, 0); None } } +impl<T> ExactSizeIterator for Iter<'_, T> { + fn len(&self) -> usize { + self.len + } +} + +impl<T> FusedIterator for Iter<'_, T> {} + // ===== IterMut ===== impl<'a, T> Iterator for IterMut<'a, T> { type Item = (usize, &'a mut T); - fn next(&mut self) -> Option<(usize, &'a mut T)> { - while let Some(entry) = self.entries.next() { - let curr = self.curr; - self.curr += 1; - + fn next(&mut self) -> Option<Self::Item> { + for (key, entry) in &mut self.entries { if let Entry::Occupied(ref mut v) = *entry { - return Some((curr, v)); + self.len -= 1; + return Some((key, v)); } } + debug_assert_eq!(self.len, 0); None } fn size_hint(&self) -> (usize, Option<usize>) { - (0, Some(self.entries.len())) + (self.len, Some(self.len)) } } -impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { - fn next_back(&mut self) -> Option<(usize, &'a mut T)> { - while let Some(entry) = self.entries.next_back() { +impl<T> DoubleEndedIterator for IterMut<'_, T> { + fn next_back(&mut self) -> Option<Self::Item> { + while let Some((key, entry)) = self.entries.next_back() { if let Entry::Occupied(ref mut v) = *entry { - let key = self.curr + self.entries.len(); + self.len -= 1; return Some((key, v)); } } + debug_assert_eq!(self.len, 0); None } } +impl<T> ExactSizeIterator for IterMut<'_, T> { + fn len(&self) -> usize { + self.len + } +} + +impl<T> FusedIterator for IterMut<'_, T> {} + // ===== Drain ===== -impl<'a, T> Iterator for Drain<'a, T> { +impl<T> Iterator for Drain<'_, T> { type Item = T; - fn next(&mut self) -> Option<T> { - while let Some(entry) = self.0.next() { + fn next(&mut self) -> Option<Self::Item> { + for entry in &mut self.inner { if let Entry::Occupied(v) = entry { + self.len -= 1; return Some(v); } } + debug_assert_eq!(self.len, 0); None } fn size_hint(&self) -> (usize, Option<usize>) { - (0, Some(self.0.len())) + (self.len, Some(self.len)) } } -impl<'a, T> DoubleEndedIterator for Drain<'a, T> { - fn next_back(&mut self) -> Option<T> { - while let Some(entry) = self.0.next_back() { +impl<T> DoubleEndedIterator for Drain<'_, T> { + fn next_back(&mut self) -> Option<Self::Item> { + while let Some(entry) = self.inner.next_back() { if let Entry::Occupied(v) = entry { + self.len -= 1; return Some(v); } } + debug_assert_eq!(self.len, 0); None } } + +impl<T> ExactSizeIterator for Drain<'_, T> { + fn len(&self) -> usize { + self.len + } +} + +impl<T> FusedIterator for Drain<'_, T> {} diff --git a/src/serde.rs b/src/serde.rs index 4fb18e9..7ffe8e0 100644 --- a/src/serde.rs +++ b/src/serde.rs @@ -1,10 +1,8 @@ -extern crate serde; - use core::fmt; use core::marker::PhantomData; -use self::serde::de::{Deserialize, Deserializer, MapAccess, Visitor}; -use self::serde::ser::{Serialize, SerializeMap, Serializer}; +use serde::de::{Deserialize, Deserializer, MapAccess, Visitor}; +use serde::ser::{Serialize, SerializeMap, Serializer}; use super::{Entry, Slab}; @@ -33,7 +31,7 @@ where { type Value = Slab<T>; - fn expecting(&self, fmt: &mut fmt::Formatter) -> fmt::Result { + fn expecting(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { write!(fmt, "a map") } @@ -45,6 +43,7 @@ where // same as FromIterator impl let mut vacant_list_broken = false; + let mut first_vacant_index = None; while let Some((key, value)) = map.next_entry()? { if key < slab.entries.len() { // iterator is not sorted, might need to recreate vacant list @@ -53,9 +52,12 @@ where slab.len += 1; } // if an element with this key already exists, replace it. - // This is consisent with HashMap and BtreeMap + // This is consistent with HashMap and BtreeMap slab.entries[key] = Entry::Occupied(value); } else { + if first_vacant_index.is_none() && slab.entries.len() < key { + first_vacant_index = Some(slab.entries.len()); + } // insert holes as necessary while slab.entries.len() < key { // add the entry to the start of the vacant list @@ -68,10 +70,18 @@ where } } if slab.len == slab.entries.len() { - // no vacant enries, so next might not have been updated + // no vacant entries, so next might not have been updated slab.next = slab.entries.len(); } else if vacant_list_broken { slab.recreate_vacant_list(); + } else if let Some(first_vacant_index) = first_vacant_index { + let next = slab.entries.len(); + match &mut slab.entries[first_vacant_index] { + Entry::Vacant(n) => *n = next, + _ => unreachable!(), + } + } else { + unreachable!() } Ok(slab) diff --git a/tests/serde.rs b/tests/serde.rs index d8eb682..1d4a204 100644 --- a/tests/serde.rs +++ b/tests/serde.rs @@ -1,8 +1,5 @@ #![cfg(feature = "serde")] - -extern crate serde; -extern crate serde_test; -extern crate slab; +#![warn(rust_2018_idioms)] use serde::{Deserialize, Serialize}; use serde_test::{assert_tokens, Token}; @@ -14,10 +11,12 @@ struct SlabPartialEq<T>(Slab<T>); impl<T: PartialEq> PartialEq for SlabPartialEq<T> { fn eq(&self, other: &Self) -> bool { - self.0 - .iter() - .zip(other.0.iter()) - .all(|(this, other)| this.0 == other.0 && this.1 == other.1) + self.0.len() == other.0.len() + && self + .0 + .iter() + .zip(other.0.iter()) + .all(|(this, other)| this.0 == other.0 && this.1 == other.1) } } diff --git a/tests/slab.rs b/tests/slab.rs index 8ba3064..8b03c1e 100644 --- a/tests/slab.rs +++ b/tests/slab.rs @@ -1,4 +1,4 @@ -extern crate slab; +#![warn(rust_2018_idioms)] use slab::*; @@ -403,6 +403,36 @@ fn from_iterator_unordered() { assert_eq!(iter.next(), None); } +// https://github.com/tokio-rs/slab/issues/100 +#[test] +fn from_iterator_issue_100() { + let mut slab: slab::Slab<()> = vec![(1, ())].into_iter().collect(); + assert_eq!(slab.len(), 1); + assert_eq!(slab.insert(()), 0); + assert_eq!(slab.insert(()), 2); + assert_eq!(slab.insert(()), 3); + + let mut slab: slab::Slab<()> = vec![(1, ()), (2, ())].into_iter().collect(); + assert_eq!(slab.len(), 2); + assert_eq!(slab.insert(()), 0); + assert_eq!(slab.insert(()), 3); + assert_eq!(slab.insert(()), 4); + + let mut slab: slab::Slab<()> = vec![(1, ()), (3, ())].into_iter().collect(); + assert_eq!(slab.len(), 2); + assert_eq!(slab.insert(()), 2); + assert_eq!(slab.insert(()), 0); + assert_eq!(slab.insert(()), 4); + + let mut slab: slab::Slab<()> = vec![(0, ()), (2, ()), (3, ()), (5, ())] + .into_iter() + .collect(); + assert_eq!(slab.len(), 4); + assert_eq!(slab.insert(()), 4); + assert_eq!(slab.insert(()), 1); + assert_eq!(slab.insert(()), 6); +} + #[test] fn clear() { let mut slab = Slab::new(); @@ -413,9 +443,7 @@ fn clear() { // clear full slab.clear(); - - let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect(); - assert!(vals.is_empty()); + assert!(slab.is_empty()); assert_eq!(0, slab.len()); assert_eq!(4, slab.capacity()); @@ -429,9 +457,7 @@ fn clear() { // clear half-filled slab.clear(); - - let vals: Vec<_> = slab.iter().map(|(_, r)| *r).collect(); - assert!(vals.is_empty()); + assert!(slab.is_empty()); } #[test] @@ -661,3 +687,14 @@ fn drain_rev() { let vals: Vec<u64> = slab.drain().rev().collect(); assert_eq!(vals, (0..9).rev().collect::<Vec<u64>>()); } + +#[test] +fn try_remove() { + let mut slab = Slab::new(); + + let key = slab.insert(1); + + assert_eq!(slab.try_remove(key), Some(1)); + assert_eq!(slab.try_remove(key), None); + assert_eq!(slab.get(key), None); +} |