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

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
diff --git a/Android.bp b/Android.bp
index 0cbfb13..07b0af9 100644
--- a/Android.bp
+++ b/Android.bp
@@ -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).
diff --git a/Cargo.toml b/Cargo.toml
index 4f06c72..218805d 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -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 = []
diff --git a/METADATA b/METADATA
index e855e3b..b037efe 100644
--- a/METADATA
+++ b/METADATA
@@ -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
   }
 }
diff --git a/README.md b/README.md
index 4373961..edbbe03 100644
--- a/README.md
+++ b/README.md
@@ -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();
diff --git a/src/lib.rs b/src/lib.rs
index 6b433af..d277547 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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);
+}