Snap for 10453563 from 4f9ba88634b7c5e310e5e590a72879ba726844c4 to mainline-media-swcodec-releaseaml_swc_341619000aml_swc_341513600aml_swc_341312300aml_swc_341312020aml_swc_341111000aml_swc_341011020aml_swc_340922010android14-mainline-media-swcodec-release

Change-Id: Iecc2bfb01229f2f6175400c5cedc72dcdfa1c93a

14 files changed, 486 insertions, 706 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 020e8b8..2810244 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,6 @@
 {
   "git": {
-    "sha1": "0531e100ef052fd49b2f465abf96cd88aea84692"
-  }
-}
+    "sha1": "dfc4a57278b79314b0c1892d6c3918f2e00e249b"
+  },
+  "path_in_vcs": ""
+}
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index be42217..5ce3172 100644
--- a/Android.bp
+++ b/Android.bp
@@ -41,28 +41,17 @@ license {
 
 rust_library {
     name: "liblinked_hash_map",
+    // has rustc warnings
     host_supported: true,
     crate_name: "linked_hash_map",
     cargo_env_compat: true,
-    cargo_pkg_version: "0.5.4",
+    cargo_pkg_version: "0.5.6",
     srcs: ["src/lib.rs"],
     edition: "2015",
-}
-
-rust_test {
-    name: "linked-hash-map_test_tests_test",
-    host_supported: true,
-    crate_name: "linked_hash_map",
-    cargo_env_compat: true,
-    cargo_pkg_version: "0.5.4",
-    srcs: ["tests/test.rs"],
-    test_suites: ["general-tests"],
-    auto_gen_config: true,
-    test_options: {
-        unit_test: true,
-    },
-    edition: "2015",
-    rustlibs: [
-        "liblinked_hash_map",
+    apex_available: [
+        "//apex_available:platform",
+        "//apex_available:anyapex",
     ],
+    product_available: true,
+    vendor_available: true,
 }
diff --git a/Cargo.toml b/Cargo.toml
index b2d5572..51deccd 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,18 +3,23 @@
 # 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]
 name = "linked-hash-map"
-version = "0.5.4"
-authors = ["Stepan Koltsov <stepan.koltsov@gmail.com>", "Andrew Paseltiner <apaseltiner@gmail.com>"]
-exclude = ["/.travis.yml", "/deploy-docs.sh"]
+version = "0.5.6"
+authors = [
+    "Stepan Koltsov <stepan.koltsov@gmail.com>",
+    "Andrew Paseltiner <apaseltiner@gmail.com>",
+]
+exclude = [
+    ".github",
+    "src/tests",
+]
 description = "A HashMap wrapper that holds key-value pairs in insertion order"
 homepage = "https://github.com/contain-rs/linked-hash-map"
 documentation = "https://docs.rs/linked-hash-map"
@@ -22,9 +27,6 @@ readme = "README.md"
 keywords = ["data-structures"]
 license = "MIT/Apache-2.0"
 repository = "https://github.com/contain-rs/linked-hash-map"
-[dependencies.clippy]
-version = "0.*"
-optional = true
 
 [dependencies.heapsize]
 version = "0.4"
@@ -34,11 +36,10 @@ optional = true
 version = "1.0"
 optional = true
 
-[dependencies.serde_test]
+[dev-dependencies.serde_test]
 version = "1.0"
-optional = true
 
 [features]
 heapsize_impl = ["heapsize"]
 nightly = []
-serde_impl = ["serde", "serde_test"]
+serde_impl = ["serde"]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index cb43704..4400e6e 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,7 +1,7 @@
 [package]
 
 name = "linked-hash-map"
-version = "0.5.4"
+version = "0.5.6"
 license = "MIT/Apache-2.0"
 description = "A HashMap wrapper that holds key-value pairs in insertion order"
 authors = [
@@ -14,15 +14,16 @@ homepage = "https://github.com/contain-rs/linked-hash-map"
 documentation = "https://docs.rs/linked-hash-map"
 keywords = ["data-structures"]
 readme = "README.md"
-exclude = ["/.travis.yml", "/deploy-docs.sh"]
+exclude = [".github", "src/tests"]
 
 [features]
 nightly = []
-serde_impl = ["serde", "serde_test"]
+serde_impl = ["serde"]
 heapsize_impl = ["heapsize"]
 
 [dependencies]
-clippy = { version = "0.*", optional = true }
 serde = { version = "1.0", optional = true }
-serde_test = { version = "1.0", optional = true }
 heapsize = { version = "0.4", optional = true }
+
+[dev-dependencies]
+serde_test = { version = "1.0" }
diff --git a/METADATA b/METADATA
index e3889bb..126b8e6 100644
--- a/METADATA
+++ b/METADATA
@@ -1,3 +1,7 @@
+# This project was upgraded with external_updater.
+# Usage: tools/external_updater/updater.sh update rust/crates/linked-hash-map
+# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md
+
 name: "linked-hash-map"
 description: "A HashMap wrapper that holds key-value pairs in insertion order"
 third_party {
@@ -7,13 +11,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/linked-hash-map/linked-hash-map-0.5.4.crate"
+    value: "https://static.crates.io/crates/linked-hash-map/linked-hash-map-0.5.6.crate"
   }
-  version: "0.5.4"
+  version: "0.5.6"
   license_type: NOTICE
   last_upgrade_date {
-    year: 2021
-    month: 2
-    day: 9
+    year: 2022
+    month: 12
+    day: 12
   }
 }
diff --git a/README.md b/README.md
index f93b6fc..31b40b3 100644
--- a/README.md
+++ b/README.md
@@ -1,9 +1,13 @@
+![Rust CI](https://github.com/contain-rs/linked-hash-map/workflows/Rust/badge.svg?branch=master) [![crates.io](https://img.shields.io/crates/v/linked-hash-map.svg)](https://crates.io/crates/linked-hash-map) [![](https://docs.rs/linked-hash-map/badge.svg)](https://docs.rs/linked-hash-map)
+
+
 **WARNING: THIS PROJECT IS IN MAINTENANCE MODE, DUE TO INSUFFICIENT MAINTAINER RESOURCES**
 
 It works fine, but will generally no longer be improved.
 
 We are currently only accepting changes which:
 
+* fix correctness issues
 * keep this compiling with the latest versions of Rust or its dependencies.
 * have minimal review requirements, such as documentation changes (so not totally new APIs).
 
diff --git a/TEST_MAPPING b/TEST_MAPPING
index 2c5b7a8..21fc7c0 100644
--- a/TEST_MAPPING
+++ b/TEST_MAPPING
@@ -4,15 +4,5 @@
     {
       "path": "external/rust/crates/lru-cache"
     }
-  ],
-  "presubmit": [
-    {
-      "name": "linked-hash-map_test_tests_test"
-    }
-  ],
-  "presubmit-rust": [
-    {
-      "name": "linked-hash-map_test_tests_test"
-    }
   ]
 }
diff --git a/cargo2android.json b/cargo2android.json
index d36fb44..6e26a5a 100644
--- a/cargo2android.json
+++ b/cargo2android.json
@@ -1,5 +1,4 @@
 {
   "device": true,
-  "run": true,
-  "tests": true
-}
\ No newline at end of file
+  "run": true
+}
diff --git a/src/heapsize.rs b/src/heapsize.rs
index 386b787..59f4629 100644
--- a/src/heapsize.rs
+++ b/src/heapsize.rs
@@ -1,9 +1,9 @@
 extern crate heapsize;
 
-use self::heapsize::{HeapSizeOf, heap_size_of};
-use std::hash::{Hash, BuildHasher};
+use self::heapsize::{heap_size_of, HeapSizeOf};
+use std::hash::{BuildHasher, Hash};
 
-use {LinkedHashMap, KeyRef, Node};
+use {KeyRef, LinkedHashMap, Node};
 
 impl<K> HeapSizeOf for KeyRef<K> {
     fn heap_size_of_children(&self) -> usize {
@@ -12,8 +12,9 @@ impl<K> HeapSizeOf for KeyRef<K> {
 }
 
 impl<K, V> HeapSizeOf for Node<K, V>
-    where K: HeapSizeOf,
-          V: HeapSizeOf
+where
+    K: HeapSizeOf,
+    V: HeapSizeOf,
 {
     fn heap_size_of_children(&self) -> usize {
         self.key.heap_size_of_children() + self.value.heap_size_of_children()
@@ -21,9 +22,10 @@ impl<K, V> HeapSizeOf for Node<K, V>
 }
 
 impl<K, V, S> HeapSizeOf for LinkedHashMap<K, V, S>
-    where K: HeapSizeOf + Hash + Eq,
-          V: HeapSizeOf,
-          S: BuildHasher
+where
+    K: HeapSizeOf + Hash + Eq,
+    V: HeapSizeOf,
+    S: BuildHasher,
 {
     fn heap_size_of_children(&self) -> usize {
         unsafe {
diff --git a/src/lib.rs b/src/lib.rs
index 2754217..d34d5ac 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -30,16 +30,14 @@
 #![forbid(missing_docs)]
 #![cfg_attr(all(feature = "nightly", test), feature(test))]
 
-#![cfg_attr(feature = "clippy", feature(plugin))]
-#![cfg_attr(feature = "clippy", plugin(clippy))]
-#![cfg_attr(feature = "clippy", deny(clippy))]
-
 // Optional Serde support
 #[cfg(feature = "serde_impl")]
 pub mod serde;
 // Optional Heapsize support
 #[cfg(feature = "heapsize_impl")]
 mod heapsize;
+#[cfg(test)]
+mod tests;
 
 use std::borrow::Borrow;
 use std::cmp::Ordering;
@@ -50,9 +48,11 @@ use std::iter;
 use std::marker;
 use std::mem;
 use std::ops::{Index, IndexMut};
-use std::ptr;
+use std::ptr::{self, addr_of_mut};
 
-struct KeyRef<K> { k: *const K }
+struct KeyRef<K> {
+    k: *const K,
+}
 
 struct Node<K, V> {
     next: *mut Node<K, V>,
@@ -76,7 +76,7 @@ impl<K: Hash> Hash for KeyRef<K> {
 
 impl<K: PartialEq> PartialEq for KeyRef<K> {
     fn eq(&self, other: &Self) -> bool {
-        unsafe{ (*self.k).eq(&*other.k) }
+        unsafe { (*self.k).eq(&*other.k) }
     }
 }
 
@@ -90,10 +90,15 @@ impl<K: Eq> Eq for KeyRef<K> {}
 struct Qey<Q: ?Sized>(Q);
 
 impl<Q: ?Sized> Qey<Q> {
-    fn from_ref(q: &Q) -> &Self { unsafe { mem::transmute(q) } }
+    fn from_ref(q: &Q) -> &Self {
+        unsafe { mem::transmute(q) }
+    }
 }
 
-impl<K, Q: ?Sized> Borrow<Qey<Q>> for KeyRef<K> where K: Borrow<Q> {
+impl<K, Q: ?Sized> Borrow<Qey<Q>> for KeyRef<K>
+where
+    K: Borrow<Q>,
+{
     fn borrow(&self) -> &Qey<Q> {
         Qey::from_ref(unsafe { (*self.k).borrow() })
     }
@@ -123,7 +128,9 @@ unsafe fn drop_empty_node<K, V>(the_box: *mut Node<K, V>) {
 
 impl<K: Hash + Eq, V> LinkedHashMap<K, V> {
     /// Creates a linked hash map.
-    pub fn new() -> Self { Self::with_map(HashMap::new()) }
+    pub fn new() -> Self {
+        Self::with_map(HashMap::new())
+    }
 
     /// Creates an empty linked hash map with the given initial capacity.
     pub fn with_capacity(capacity: usize) -> Self {
@@ -163,7 +170,7 @@ impl<K, V, S> LinkedHashMap<K, V, S> {
     fn clear_free_list(&mut self) {
         unsafe {
             let mut free = self.free;
-            while ! free.is_null() {
+            while !free.is_null() {
                 let next_free = (*free).next;
                 drop_empty_node(free);
                 free = next_free;
@@ -177,7 +184,7 @@ impl<K, V, S> LinkedHashMap<K, V, S> {
             // allocate the guard node if not present
             unsafe {
                 let node_layout = std::alloc::Layout::new::<Node<K, V>>();
-                self.head =  std::alloc::alloc(node_layout) as *mut Node<K, V>;
+                self.head = std::alloc::alloc(node_layout) as *mut Node<K, V>;
                 (*self.head).next = self.head;
                 (*self.head).prev = self.head;
             }
@@ -188,7 +195,7 @@ impl<K, V, S> LinkedHashMap<K, V, S> {
 impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     fn with_map(map: HashMap<KeyRef<K>, *mut Node<K, V>, S>) -> Self {
         LinkedHashMap {
-            map: map,
+            map,
             head: ptr::null_mut(),
             free: ptr::null_mut(),
         }
@@ -210,7 +217,9 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     /// # Panics
     ///
     /// Panics if the new allocation size overflows `usize.`
-    pub fn reserve(&mut self, additional: usize) { self.map.reserve(additional); }
+    pub fn reserve(&mut self, additional: usize) {
+        self.map.reserve(additional);
+    }
 
     /// Shrinks the capacity of the map as much as possible. It will drop down as much as possible
     /// while maintaining the internal rules and possibly leaving some space in accordance with the
@@ -242,7 +251,7 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     pub fn entry(&mut self, k: K) -> Entry<K, V, S> {
         let self_ptr: *mut Self = self;
 
-        if let Some(entry) = self.map.get_mut(&KeyRef{k: &k}) {
+        if let Some(entry) = self.map.get_mut(&KeyRef { k: &k }) {
             return Entry::Occupied(OccupiedEntry {
                 entry: *entry,
                 map: self_ptr,
@@ -250,10 +259,7 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
             });
         }
 
-        Entry::Vacant(VacantEntry {
-            key: k,
-            map: self,
-        })
+        Entry::Vacant(VacantEntry { key: k, map: self })
     }
 
     /// Returns an iterator visiting all entries in insertion order.
@@ -279,14 +285,14 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     /// assert_eq!(&17, map.get(&"a").unwrap());
     /// ```
     pub fn entries(&mut self) -> Entries<K, V, S> {
-        let head = if ! self.head.is_null() {
+        let head = if !self.head.is_null() {
             unsafe { (*self.head).prev }
         } else {
             ptr::null_mut()
         };
         Entries {
             map: self,
-            head: head,
+            head,
             remaining: self.len(),
             marker: marker::PhantomData,
         }
@@ -309,7 +315,7 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
         self.ensure_guard_node();
 
-        let (node, old_val) = match self.map.get(&KeyRef{k: &k}) {
+        let (node, old_val) = match self.map.get(&KeyRef { k: &k }) {
             Some(node) => {
                 let old_val = unsafe { ptr::replace(&mut (**node).value, v) };
                 (*node, Some(old_val))
@@ -337,7 +343,7 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
             }
             None => {
                 let keyref = unsafe { &(*node).key };
-                self.map.insert(KeyRef{k: keyref}, node);
+                self.map.insert(KeyRef { k: keyref }, node);
                 self.attach(node);
             }
         }
@@ -345,7 +351,11 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     }
 
     /// Checks if the map contains the given key.
-    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool where K: Borrow<Q>, Q: Eq + Hash {
+    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
+    where
+        K: Borrow<Q>,
+        Q: Eq + Hash,
+    {
         self.map.contains_key(Qey::from_ref(k))
     }
 
@@ -365,8 +375,14 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     /// assert_eq!(map.get(&1), Some(&"a"));
     /// assert_eq!(map.get(&2), Some(&"c"));
     /// ```
-    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> where K: Borrow<Q>, Q: Eq + Hash {
-        self.map.get(Qey::from_ref(k)).map(|e| unsafe { &(**e).value })
+    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
+    where
+        K: Borrow<Q>,
+        Q: Eq + Hash,
+    {
+        self.map
+            .get(Qey::from_ref(k))
+            .map(|e| unsafe { &(**e).value })
     }
 
     /// Returns the mutable reference corresponding to the key in the map.
@@ -383,8 +399,14 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     /// *map.get_mut(&1).unwrap() = "c";
     /// assert_eq!(map.get(&1), Some(&"c"));
     /// ```
-    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash {
-        self.map.get(Qey::from_ref(k)).map(|e| unsafe { &mut (**e).value })
+    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q>,
+        Q: Eq + Hash,
+    {
+        self.map
+            .get(Qey::from_ref(k))
+            .map(|e| unsafe { &mut (**e).value })
     }
 
     /// Returns the value corresponding to the key in the map.
@@ -406,12 +428,14 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     ///
     /// assert_eq!((&2, &"b"), map.iter().rev().next().unwrap());
     /// ```
-    pub fn get_refresh<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Eq + Hash {
+    pub fn get_refresh<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
+    where
+        K: Borrow<Q>,
+        Q: Eq + Hash,
+    {
         let (value, node_ptr_opt) = match self.map.get(Qey::from_ref(k)) {
             None => (None, None),
-            Some(node) => {
-                (Some(unsafe { &mut (**node).value }), Some(*node))
-            }
+            Some(node) => (Some(unsafe { &mut (**node).value }), Some(*node)),
         };
         if let Some(node_ptr) = node_ptr_opt {
             self.detach(node_ptr);
@@ -435,7 +459,11 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     /// assert_eq!(map.remove(&2), None);
     /// assert_eq!(map.len(), 0);
     /// ```
-    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> where K: Borrow<Q>, Q: Eq + Hash {
+    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
+    where
+        K: Borrow<Q>,
+        Q: Eq + Hash,
+    {
         let removed = self.map.remove(Qey::from_ref(k));
         removed.map(|node| {
             self.detach(node);
@@ -481,12 +509,14 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     #[inline]
     pub fn pop_front(&mut self) -> Option<(K, V)> {
         if self.is_empty() {
-            return None
+            return None;
         }
         let lru = unsafe { (*self.head).prev };
         self.detach(lru);
         self.map
-            .remove(&KeyRef{k: unsafe { &(*lru).key }})
+            .remove(&KeyRef {
+                k: unsafe { &(*lru).key },
+            })
             .map(|e| {
                 let e = *unsafe { Box::from_raw(e) };
                 (e.key, e.value)
@@ -507,11 +537,13 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     #[inline]
     pub fn front(&self) -> Option<(&K, &V)> {
         if self.is_empty() {
-            return None
+            return None;
         }
         let lru = unsafe { (*self.head).prev };
         self.map
-            .get(&KeyRef{k: unsafe { &(*lru).key }})
+            .get(&KeyRef {
+                k: unsafe { &(*lru).key },
+            })
             .map(|e| unsafe { (&(**e).key, &(**e).value) })
     }
 
@@ -531,12 +563,14 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     #[inline]
     pub fn pop_back(&mut self) -> Option<(K, V)> {
         if self.is_empty() {
-            return None
+            return None;
         }
         let mru = unsafe { (*self.head).next };
         self.detach(mru);
         self.map
-            .remove(&KeyRef{k: unsafe { &(*mru).key }})
+            .remove(&KeyRef {
+                k: unsafe { &(*mru).key },
+            })
             .map(|e| {
                 let e = *unsafe { Box::from_raw(e) };
                 (e.key, e.value)
@@ -555,21 +589,27 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     /// assert_eq!(map.back(), Some((&2, &20)));
     /// ```
     #[inline]
-    pub fn back(&mut self) -> Option<(&K, &V)> {
+    pub fn back(&self) -> Option<(&K, &V)> {
         if self.is_empty() {
-            return None
+            return None;
         }
         let mru = unsafe { (*self.head).next };
         self.map
-            .get(&KeyRef{k: unsafe { &(*mru).key }})
+            .get(&KeyRef {
+                k: unsafe { &(*mru).key },
+            })
             .map(|e| unsafe { (&(**e).key, &(**e).value) })
     }
 
     /// Returns the number of key-value pairs in the map.
-    pub fn len(&self) -> usize { self.map.len() }
+    pub fn len(&self) -> usize {
+        self.map.len()
+    }
 
     /// Returns whether the map is currently empty.
-    pub fn is_empty(&self) -> bool { self.len() == 0 }
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
 
     /// Returns a reference to the map's hasher.
     pub fn hasher(&self) -> &S {
@@ -580,7 +620,7 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
     pub fn clear(&mut self) {
         self.map.clear();
         // update the guard node if present
-        if ! self.head.is_null() {
+        if !self.head.is_null() {
             unsafe {
                 self.drop_entries();
                 (*self.head).prev = self.head;
@@ -614,7 +654,7 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
             unsafe { (*self.head).prev }
         };
         Iter {
-            head: head,
+            head,
             tail: self.head,
             remaining: self.len(),
             marker: marker::PhantomData,
@@ -648,13 +688,67 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
             unsafe { (*self.head).prev }
         };
         IterMut {
-            head: head,
+            head,
             tail: self.head,
             remaining: self.len(),
             marker: marker::PhantomData,
         }
     }
 
+    /// Clears the map, returning all key-value pairs as an iterator. Keeps the
+    /// allocated memory for reuse.
+    ///
+    /// If the returned iterator is dropped before being fully consumed, it
+    /// drops the remaining key-value pairs. The returned iterator keeps a
+    /// mutable borrow on the vector to optimize its implementation.
+    ///
+    /// Current performance implications (why to use this over into_iter()):
+    ///
+    /// * Clears the inner HashMap instead of dropping it
+    /// * Puts all drained nodes in the free-list instead of deallocating them
+    /// * Avoids deallocating the sentinel node
+    pub fn drain(&mut self) -> Drain<K, V> {
+        let len = self.len();
+        // Map should be empty now, regardless of current state
+        self.map.clear();
+        let (head, tail) = if len != 0 {
+            // This is basically the same as IntoIter's impl, but we don't
+            // deallocate/drop anything. Instead we make the sentinel head node
+            // point at itself (same state you get from removing the last element from a map),
+            // and then append the entire list to the free list. At this point all the entries
+            // have essentially been fed into mem::forget. The Drain iterator will then iterate
+            // over those nodes in the freelist (using  `len` to know where to stop) and `read`
+            // the values out of the nodes, "unforgetting" them.
+            //
+            // This design results in no observable consequences for mem::forgetting the
+            // drain iterator, because the drain iterator has no responsibility to "fix up"
+            // things during iteration/destruction. That said, you will effectively mem::forget
+            // any elements that weren't yielded yet.
+            unsafe {
+                debug_assert!(!self.head.is_null());
+                debug_assert!(!(*self.head).prev.is_null());
+                debug_assert!((*self.head).prev != self.head);
+                let head = (*self.head).prev;
+                let tail = (*self.head).next;
+                (*self.head).prev = self.head;
+                (*self.head).next = self.head;
+                (*head).next = self.free;
+                (*tail).prev = ptr::null_mut();
+                self.free = tail;
+                (head, tail)
+            }
+        } else {
+            (ptr::null_mut(), ptr::null_mut())
+        };
+
+        Drain {
+            head,
+            tail,
+            remaining: len,
+            marker: marker::PhantomData,
+        }
+    }
+
     /// Returns a double-ended iterator visiting all key in order of insertion.
     ///
     /// # Examples
@@ -699,7 +793,10 @@ impl<K: Hash + Eq, V, S: BuildHasher> LinkedHashMap<K, V, S> {
 }
 
 impl<'a, K, V, S, Q: ?Sized> Index<&'a Q> for LinkedHashMap<K, V, S>
-    where K: Hash + Eq + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
+where
+    K: Hash + Eq + Borrow<Q>,
+    S: BuildHasher,
+    Q: Eq + Hash,
 {
     type Output = V;
 
@@ -709,7 +806,10 @@ impl<'a, K, V, S, Q: ?Sized> Index<&'a Q> for LinkedHashMap<K, V, S>
 }
 
 impl<'a, K, V, S, Q: ?Sized> IndexMut<&'a Q> for LinkedHashMap<K, V, S>
-    where K: Hash + Eq + Borrow<Q>, S: BuildHasher, Q: Eq + Hash
+where
+    K: Hash + Eq + Borrow<Q>,
+    S: BuildHasher,
+    Q: Eq + Hash,
 {
     fn index_mut(&mut self, index: &'a Q) -> &mut V {
         self.get_mut(index).expect("no entry found for key")
@@ -725,11 +825,13 @@ impl<K: Hash + Eq + Clone, V: Clone, S: BuildHasher + Clone> Clone for LinkedHas
 }
 
 impl<K: Hash + Eq, V, S: BuildHasher + Default> Default for LinkedHashMap<K, V, S> {
-    fn default() -> Self { Self::with_hasher(S::default()) }
+    fn default() -> Self {
+        Self::with_hasher(S::default())
+    }
 }
 
 impl<K: Hash + Eq, V, S: BuildHasher> Extend<(K, V)> for LinkedHashMap<K, V, S> {
-    fn extend<I: IntoIterator<Item=(K, V)>>(&mut self, iter: I) {
+    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
         for (k, v) in iter {
             self.insert(k, v);
         }
@@ -737,7 +839,10 @@ impl<K: Hash + Eq, V, S: BuildHasher> Extend<(K, V)> for LinkedHashMap<K, V, S>
 }
 
 impl<'a, K, V, S> Extend<(&'a K, &'a V)> for LinkedHashMap<K, V, S>
-    where K: 'a + Hash + Eq + Copy, V: 'a + Copy, S: BuildHasher,
+where
+    K: 'a + Hash + Eq + Copy,
+    V: 'a + Copy,
+    S: BuildHasher,
 {
     fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
         for (&k, &v) in iter {
@@ -746,8 +851,10 @@ impl<'a, K, V, S> Extend<(&'a K, &'a V)> for LinkedHashMap<K, V, S>
     }
 }
 
-impl<K: Hash + Eq, V, S: BuildHasher + Default> iter::FromIterator<(K, V)> for LinkedHashMap<K, V, S> {
-    fn from_iter<I: IntoIterator<Item=(K, V)>>(iter: I) -> Self {
+impl<K: Hash + Eq, V, S: BuildHasher + Default> iter::FromIterator<(K, V)>
+    for LinkedHashMap<K, V, S>
+{
+    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
         let iter = iter.into_iter();
         let mut map = Self::with_capacity_and_hasher(iter.size_hint().0, S::default());
         map.extend(iter);
@@ -755,7 +862,9 @@ impl<K: Hash + Eq, V, S: BuildHasher + Default> iter::FromIterator<(K, V)> for L
     }
 }
 
-impl<A: fmt::Debug + Hash + Eq, B: fmt::Debug, S: BuildHasher> fmt::Debug for LinkedHashMap<A, B, S> {
+impl<A: fmt::Debug + Hash + Eq, B: fmt::Debug, S: BuildHasher> fmt::Debug
+    for LinkedHashMap<A, B, S>
+{
     /// Returns a string that lists the key-value pairs in insertion order.
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         f.debug_map().entries(self).finish()
@@ -770,7 +879,9 @@ impl<K: Hash + Eq, V: PartialEq, S: BuildHasher> PartialEq for LinkedHashMap<K,
 
 impl<K: Hash + Eq, V: Eq, S: BuildHasher> Eq for LinkedHashMap<K, V, S> {}
 
-impl<K: Hash + Eq + PartialOrd, V: PartialOrd, S: BuildHasher> PartialOrd for LinkedHashMap<K, V, S> {
+impl<K: Hash + Eq + PartialOrd, V: PartialOrd, S: BuildHasher> PartialOrd
+    for LinkedHashMap<K, V, S>
+{
     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
         self.iter().partial_cmp(other)
     }
@@ -799,7 +910,11 @@ impl<K: Hash + Eq + Ord, V: Ord, S: BuildHasher> Ord for LinkedHashMap<K, V, S>
 }
 
 impl<K: Hash + Eq, V: Hash, S: BuildHasher> Hash for LinkedHashMap<K, V, S> {
-    fn hash<H: Hasher>(&self, h: &mut H) { for e in self.iter() { e.hash(h); } }
+    fn hash<H: Hasher>(&self, h: &mut H) {
+        for e in self.iter() {
+            e.hash(h);
+        }
+    }
 }
 
 unsafe impl<K: Send, V: Send, S: Send> Send for LinkedHashMap<K, V, S> {}
@@ -844,6 +959,14 @@ pub struct IntoIter<K, V> {
     marker: marker::PhantomData<(K, V)>,
 }
 
+/// A draining insertion-order iterator over a `LinkedHashMap`'s entries.
+pub struct Drain<'a, K, V> {
+    head: *mut Node<K, V>,
+    tail: *mut Node<K, V>,
+    remaining: usize,
+    marker: marker::PhantomData<&'a mut (K, V)>,
+}
+
 /// An insertion-order iterator over a `LinkedHashMap`'s entries represented as
 /// an `OccupiedEntry`.
 pub struct Entries<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
@@ -853,38 +976,101 @@ pub struct Entries<'a, K: 'a, V: 'a, S: 'a = hash_map::RandomState> {
     marker: marker::PhantomData<(&'a K, &'a mut V, &'a S)>,
 }
 
-unsafe impl<'a, K, V> Send for Iter<'a, K, V> where K: Send, V: Send {}
+unsafe impl<'a, K, V> Send for Iter<'a, K, V>
+where
+    K: Send,
+    V: Send,
+{
+}
 
-unsafe impl<'a, K, V> Send for IterMut<'a, K, V> where K: Send, V: Send {}
+unsafe impl<'a, K, V> Send for IterMut<'a, K, V>
+where
+    K: Send,
+    V: Send,
+{
+}
 
-unsafe impl<K, V> Send for IntoIter<K, V> where K: Send, V: Send {}
+unsafe impl<'a, K, V> Send for Drain<'a, K, V>
+where
+    K: Send,
+    V: Send,
+{
+}
 
-unsafe impl<'a, K, V, S> Send for Entries<'a, K, V, S> where K: Send, V: Send, S: Send {}
+unsafe impl<K, V> Send for IntoIter<K, V>
+where
+    K: Send,
+    V: Send,
+{
+}
 
-unsafe impl<'a, K, V> Sync for Iter<'a, K, V> where K: Sync, V: Sync {}
+unsafe impl<'a, K, V, S> Send for Entries<'a, K, V, S>
+where
+    K: Send,
+    V: Send,
+    S: Send,
+{
+}
 
-unsafe impl<'a, K, V> Sync for IterMut<'a, K, V> where K: Sync, V: Sync {}
+unsafe impl<'a, K, V> Sync for Iter<'a, K, V>
+where
+    K: Sync,
+    V: Sync,
+{
+}
 
-unsafe impl<K, V> Sync for IntoIter<K, V> where K: Sync, V: Sync {}
+unsafe impl<'a, K, V> Sync for IterMut<'a, K, V>
+where
+    K: Sync,
+    V: Sync,
+{
+}
+
+unsafe impl<'a, K, V> Sync for Drain<'a, K, V>
+where
+    K: Sync,
+    V: Sync,
+{
+}
+unsafe impl<K, V> Sync for IntoIter<K, V>
+where
+    K: Sync,
+    V: Sync,
+{
+}
 
-unsafe impl<'a, K, V, S> Sync for Entries<'a, K, V, S> where K: Sync, V: Sync, S: Sync {}
+unsafe impl<'a, K, V, S> Sync for Entries<'a, K, V, S>
+where
+    K: Sync,
+    V: Sync,
+    S: Sync,
+{
+}
 
 impl<'a, K, V> Clone for Iter<'a, K, V> {
-    fn clone(&self) -> Self { Iter { ..*self } }
+    fn clone(&self) -> Self {
+        Iter { ..*self }
+    }
 }
 
-impl<K, V> Clone for IntoIter<K, V> where K: Clone, V: Clone {
+impl<K, V> Clone for IntoIter<K, V>
+where
+    K: Clone,
+    V: Clone,
+{
     fn clone(&self) -> Self {
         if self.remaining == 0 {
-            return IntoIter { ..*self }
+            return IntoIter { ..*self };
         }
 
         fn clone_node<K, V>(e: *mut Node<K, V>) -> *mut Node<K, V>
-            where K: Clone, V: Clone,
+        where
+            K: Clone,
+            V: Clone,
         {
-            Box::into_raw(Box::new(Node::new(
-                unsafe { (*e).key.clone() }, unsafe { (*e).value.clone() }
-            )))
+            Box::into_raw(Box::new(Node::new(unsafe { (*e).key.clone() }, unsafe {
+                (*e).value.clone()
+            })))
         }
 
         let mut cur = self.head;
@@ -900,8 +1086,8 @@ impl<K, V> Clone for IntoIter<K, V> where K: Clone, V: Clone {
         }
 
         IntoIter {
-            head: head,
-            tail: tail,
+            head,
+            tail,
             remaining: self.remaining,
             marker: marker::PhantomData,
         }
@@ -955,7 +1141,7 @@ impl<K, V> Iterator for IntoIter<K, V> {
 
     fn next(&mut self) -> Option<(K, V)> {
         if self.remaining == 0 {
-            return None
+            return None;
         }
         self.remaining -= 1;
         unsafe {
@@ -971,6 +1157,54 @@ impl<K, V> Iterator for IntoIter<K, V> {
     }
 }
 
+impl<'a, K, V> Iterator for Drain<'a, K, V> {
+    type Item = (K, V);
+
+    fn next(&mut self) -> Option<(K, V)> {
+        if self.remaining == 0 {
+            return None;
+        }
+        self.remaining -= 1;
+        unsafe {
+            let prev = (*self.head).prev;
+            // Read the values out, the node is in the free-list already so these will
+            // be treated as uninit memory.
+            let k = addr_of_mut!((*self.head).key).read();
+            let v = addr_of_mut!((*self.head).value).read();
+            self.head = prev;
+            Some((k, v))
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.remaining, Some(self.remaining))
+    }
+}
+
+impl<'a, K, V> DoubleEndedIterator for Drain<'a, K, V> {
+    fn next_back(&mut self) -> Option<(K, V)> {
+        if self.remaining == 0 {
+            return None;
+        }
+        self.remaining -= 1;
+        unsafe {
+            let next = (*self.tail).next;
+            // Read the values out, the node is in the free-list already so these will
+            // be treated as uninit memory.
+            let k = addr_of_mut!((*self.tail).key).read();
+            let v = addr_of_mut!((*self.tail).value).read();
+            self.tail = next;
+            Some((k, v))
+        }
+    }
+}
+
+impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
+    fn len(&self) -> usize {
+        self.remaining
+    }
+}
+
 impl<'a, K, V, S: BuildHasher> Iterator for Entries<'a, K, V, S> {
     type Item = OccupiedEntry<'a, K, V, S>;
 
@@ -1028,7 +1262,7 @@ impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
     fn next_back(&mut self) -> Option<(K, V)> {
         if self.remaining == 0 {
-            return None
+            return None;
         }
         self.remaining -= 1;
         unsafe {
@@ -1041,15 +1275,21 @@ impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
 }
 
 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
-    fn len(&self) -> usize { self.remaining }
+    fn len(&self) -> usize {
+        self.remaining
+    }
 }
 
 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
-    fn len(&self) -> usize { self.remaining }
+    fn len(&self) -> usize {
+        self.remaining
+    }
 }
 
 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
-    fn len(&self) -> usize { self.remaining }
+    fn len(&self) -> usize {
+        self.remaining
+    }
 }
 
 impl<K, V> Drop for IntoIter<K, V> {
@@ -1064,28 +1304,49 @@ impl<K, V> Drop for IntoIter<K, V> {
     }
 }
 
+impl<'a, K, V> Drop for Drain<'a, K, V> {
+    fn drop(&mut self) {
+        for _ in self {}
+    }
+}
+
 /// An insertion-order iterator over a `LinkedHashMap`'s keys.
 pub struct Keys<'a, K: 'a, V: 'a> {
     inner: Iter<'a, K, V>,
 }
 
 impl<'a, K, V> Clone for Keys<'a, K, V> {
-    fn clone(&self) -> Self { Keys { inner: self.inner.clone() } }
+    fn clone(&self) -> Self {
+        Keys {
+            inner: self.inner.clone(),
+        }
+    }
 }
 
 impl<'a, K, V> Iterator for Keys<'a, K, V> {
     type Item = &'a K;
 
-    #[inline] fn next(&mut self) -> Option<&'a K> { self.inner.next().map(|e| e.0) }
-    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
+    #[inline]
+    fn next(&mut self) -> Option<&'a K> {
+        self.inner.next().map(|e| e.0)
+    }
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
 }
 
 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
-    #[inline] fn next_back(&mut self) -> Option<&'a K> { self.inner.next_back().map(|e| e.0) }
+    #[inline]
+    fn next_back(&mut self) -> Option<&'a K> {
+        self.inner.next_back().map(|e| e.0)
+    }
 }
 
 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
-    fn len(&self) -> usize { self.inner.len() }
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
 }
 
 /// An insertion-order iterator over a `LinkedHashMap`'s values.
@@ -1094,34 +1355,53 @@ pub struct Values<'a, K: 'a, V: 'a> {
 }
 
 impl<'a, K, V> Clone for Values<'a, K, V> {
-    fn clone(&self) -> Self { Values { inner: self.inner.clone() } }
+    fn clone(&self) -> Self {
+        Values {
+            inner: self.inner.clone(),
+        }
+    }
 }
 
 impl<'a, K, V> Iterator for Values<'a, K, V> {
     type Item = &'a V;
 
-    #[inline] fn next(&mut self) -> Option<&'a V> { self.inner.next().map(|e| e.1) }
-    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.inner.size_hint() }
+    #[inline]
+    fn next(&mut self) -> Option<&'a V> {
+        self.inner.next().map(|e| e.1)
+    }
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
 }
 
 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
-    #[inline] fn next_back(&mut self) -> Option<&'a V> { self.inner.next_back().map(|e| e.1) }
+    #[inline]
+    fn next_back(&mut self) -> Option<&'a V> {
+        self.inner.next_back().map(|e| e.1)
+    }
 }
 
 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
-    fn len(&self) -> usize { self.inner.len() }
+    fn len(&self) -> usize {
+        self.inner.len()
+    }
 }
 
 impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a LinkedHashMap<K, V, S> {
     type Item = (&'a K, &'a V);
     type IntoIter = Iter<'a, K, V>;
-    fn into_iter(self) -> Iter<'a, K, V> { self.iter() }
+    fn into_iter(self) -> Iter<'a, K, V> {
+        self.iter()
+    }
 }
 
 impl<'a, K: Hash + Eq, V, S: BuildHasher> IntoIterator for &'a mut LinkedHashMap<K, V, S> {
     type Item = (&'a K, &'a mut V);
     type IntoIter = IterMut<'a, K, V>;
-    fn into_iter(self) -> IterMut<'a, K, V> { self.iter_mut() }
+    fn into_iter(self) -> IterMut<'a, K, V> {
+        self.iter_mut()
+    }
 }
 
 impl<K: Hash + Eq, V, S: BuildHasher> IntoIterator for LinkedHashMap<K, V, S> {
@@ -1140,12 +1420,14 @@ impl<K: Hash + Eq, V, S: BuildHasher> IntoIterator for LinkedHashMap<K, V, S> {
         }
         self.clear_free_list();
         // drop the HashMap but not the LinkedHashMap
-        unsafe { ptr::drop_in_place(&mut self.map); }
+        unsafe {
+            ptr::drop_in_place(&mut self.map);
+        }
         mem::forget(self);
 
         IntoIter {
-            head: head,
-            tail: tail,
+            head,
+            tail,
             remaining: len,
             marker: marker::PhantomData,
         }
@@ -1209,6 +1491,33 @@ impl<'a, K: Hash + Eq, V, S: BuildHasher> Entry<'a, K, V, S> {
             Entry::Vacant(entry) => entry.insert(default()),
         }
     }
+
+    /// Provides in-place mutable access to an occupied entry before any
+    /// potential inserts into the map.
+    pub fn and_modify<F>(self, f: F) -> Self
+    where
+        F: FnOnce(&mut V),
+    {
+        match self {
+            Entry::Occupied(mut entry) => {
+                f(entry.get_mut());
+                Entry::Occupied(entry)
+            }
+            Entry::Vacant(entry) => Entry::Vacant(entry),
+        }
+    }
+
+    /// Ensures a value is in the entry by inserting the default value if empty,
+    /// and returns a mutable reference to the value in the entry.
+    pub fn or_default(self) -> &'a mut V
+    where
+        V: Default,
+    {
+        match self {
+            Entry::Occupied(entry) => entry.into_mut(),
+            Entry::Vacant(entry) => entry.insert(V::default()),
+        }
+    }
 }
 
 impl<'a, K: Hash + Eq, V, S: BuildHasher> OccupiedEntry<'a, K, V, S> {
@@ -1303,47 +1612,7 @@ impl<'a, K: 'a + Hash + Eq, V: 'a, S: BuildHasher> VacantEntry<'a, K, V, S> {
 
         self.map.attach(node);
 
-        let ret = self.map.map.entry(KeyRef{k: keyref}).or_insert(node);
+        let ret = self.map.map.entry(KeyRef { k: keyref }).or_insert(node);
         unsafe { &mut (**ret).value }
     }
 }
-
-#[cfg(all(feature = "nightly", test))]
-mod bench {
-    extern crate test;
-
-    use super::LinkedHashMap;
-
-    #[bench]
-    fn not_recycled_cycling(b: &mut test::Bencher) {
-        let mut hash_map = LinkedHashMap::with_capacity(1000);
-        for i in 0usize..1000 {
-            hash_map.insert(i, i);
-        }
-        b.iter(|| {
-            for i in 0usize..1000 {
-                hash_map.remove(&i);
-            }
-            hash_map.clear_free_list();
-            for i in 0usize..1000 {
-                hash_map.insert(i, i);
-            }
-        })
-    }
-
-    #[bench]
-    fn recycled_cycling(b: &mut test::Bencher) {
-        let mut hash_map = LinkedHashMap::with_capacity(1000);
-        for i in 0usize..1000 {
-            hash_map.insert(i, i);
-        }
-        b.iter(|| {
-            for i in 0usize..1000 {
-                hash_map.remove(&i);
-            }
-            for i in 0usize..1000 {
-                hash_map.insert(i, i);
-            }
-        })
-    }
-}
diff --git a/src/serde.rs b/src/serde.rs
index 1062776..0690d11 100644
--- a/src/serde.rs
+++ b/src/serde.rs
@@ -3,28 +3,30 @@
 extern crate serde;
 
 use std::fmt::{Formatter, Result as FmtResult};
-use std::marker::PhantomData;
 use std::hash::{BuildHasher, Hash};
+use std::marker::PhantomData;
 
 use super::LinkedHashMap;
 
-use self::serde::{Serialize, Serializer, Deserialize, Deserializer};
+use self::serde::de::{Error, MapAccess, Visitor};
 use self::serde::ser::SerializeMap;
-use self::serde::de::{Visitor, MapAccess, Error};
+use self::serde::{Deserialize, Deserializer, Serialize, Serializer};
 
 impl<K, V, S> Serialize for LinkedHashMap<K, V, S>
-    where K: Serialize + Eq + Hash,
-          V: Serialize,
-          S: BuildHasher
+where
+    K: Serialize + Eq + Hash,
+    V: Serialize,
+    S: BuildHasher,
 {
     #[inline]
-    fn serialize<T>(&self, serializer:T) -> Result<T::Ok, T::Error>
-        where T: Serializer,
+    fn serialize<T>(&self, serializer: T) -> Result<T::Ok, T::Error>
+    where
+        T: Serializer,
     {
-        let mut map_serializer = try!(serializer.serialize_map(Some(self.len())));
+        let mut map_serializer = serializer.serialize_map(Some(self.len()))?;
         for (k, v) in self {
-            try!(map_serializer.serialize_key(k));
-            try!(map_serializer.serialize_value(v));
+            map_serializer.serialize_key(k)?;
+            map_serializer.serialize_value(v)?;
         }
         map_serializer.end()
     }
@@ -52,8 +54,9 @@ impl<K, V> Default for LinkedHashMapVisitor<K, V> {
 }
 
 impl<'de, K, V> Visitor<'de> for LinkedHashMapVisitor<K, V>
-    where K: Deserialize<'de> + Eq + Hash,
-          V: Deserialize<'de>,
+where
+    K: Deserialize<'de> + Eq + Hash,
+    V: Deserialize<'de>,
 {
     type Value = LinkedHashMap<K, V>;
 
@@ -63,14 +66,16 @@ impl<'de, K, V> Visitor<'de> for LinkedHashMapVisitor<K, V>
 
     #[inline]
     fn visit_unit<E>(self) -> Result<Self::Value, E>
-        where E: Error,
+    where
+        E: Error,
     {
         Ok(LinkedHashMap::new())
     }
 
     #[inline]
     fn visit_map<M>(self, mut map: M) -> Result<Self::Value, M::Error>
-        where M: MapAccess<'de>,
+    where
+        M: MapAccess<'de>,
     {
         let mut values = LinkedHashMap::with_capacity(map.size_hint().unwrap_or(0));
 
@@ -83,11 +88,13 @@ impl<'de, K, V> Visitor<'de> for LinkedHashMapVisitor<K, V>
 }
 
 impl<'de, K, V> Deserialize<'de> for LinkedHashMap<K, V>
-    where K: Deserialize<'de> + Eq + Hash,
-          V: Deserialize<'de>,
+where
+    K: Deserialize<'de> + Eq + Hash,
+    V: Deserialize<'de>,
 {
     fn deserialize<D>(deserializer: D) -> Result<LinkedHashMap<K, V>, D::Error>
-        where D: Deserializer<'de>,
+    where
+        D: Deserializer<'de>,
     {
         deserializer.deserialize_map(LinkedHashMapVisitor::new())
     }
diff --git a/tests/heapsize.rs b/tests/heapsize.rs
deleted file mode 100644
index 583c30e..0000000
--- a/tests/heapsize.rs
+++ /dev/null
@@ -1,23 +0,0 @@
-#![cfg(feature = "heapsize_impl")]
-
-extern crate heapsize;
-extern crate linked_hash_map;
-
-use linked_hash_map::LinkedHashMap;
-use heapsize::HeapSizeOf;
-
-#[test]
-fn empty() {
-    assert_eq!(LinkedHashMap::<String, String>::new().heap_size_of_children(), 0);
-}
-
-#[test]
-fn nonempty() {
-    let mut map = LinkedHashMap::new();
-    map.insert("hello".to_string(), "world".to_string());
-    map.insert("hola".to_string(), "mundo".to_string());
-    map.insert("bonjour".to_string(), "monde".to_string());
-    map.remove("hello");
-
-    assert!(map.heap_size_of_children() != 0);
-}
diff --git a/tests/serde.rs b/tests/serde.rs
deleted file mode 100644
index e6d5c6f..0000000
--- a/tests/serde.rs
+++ /dev/null
@@ -1,38 +0,0 @@
-#![cfg(feature = "serde_impl")]
-
-extern crate linked_hash_map;
-use linked_hash_map::LinkedHashMap;
-
-extern crate serde_test;
-use serde_test::{Token, assert_tokens};
-
-#[test]
-fn test_ser_de_empty() {
-    let map = LinkedHashMap::<char, u32>::new();
-
-    assert_tokens(&map, &[
-        Token::Map { len: Some(0) },
-        Token::MapEnd,
-    ]);
-}
-
-#[test]
-fn test_ser_de() {
-    let mut map = LinkedHashMap::new();
-    map.insert('b', 20);
-    map.insert('a', 10);
-    map.insert('c', 30);
-
-    assert_tokens(&map, &[
-        Token::Map { len: Some(3) },
-            Token::Char('b'),
-            Token::I32(20),
-
-            Token::Char('a'),
-            Token::I32(10),
-
-            Token::Char('c'),
-            Token::I32(30),
-        Token::MapEnd,
-    ]);
-}
diff --git a/tests/test.rs b/tests/test.rs
deleted file mode 100644
index 7f34b01..0000000
--- a/tests/test.rs
+++ /dev/null
@@ -1,426 +0,0 @@
-extern crate linked_hash_map;
-
-use linked_hash_map::{LinkedHashMap, Entry};
-
-fn assert_opt_eq<V: PartialEq>(opt: Option<&V>, v: V) {
-    assert!(opt.is_some());
-    assert!(opt.unwrap() == &v);
-}
-
-#[test]
-fn test_insert_and_get() {
-    let mut map = LinkedHashMap::new();
-    map.insert(1, 10);
-    map.insert(2, 20);
-    assert_opt_eq(map.get(&1), 10);
-    assert_opt_eq(map.get(&2), 20);
-    assert_eq!(map.len(), 2);
-}
-
-#[test]
-fn test_index() {
-    let mut map = LinkedHashMap::new();
-    map.insert(1, 10);
-    map.insert(2, 20);
-    assert_eq!(10, map[&1]);
-    map[&2] = 22;
-    assert_eq!(22, map[&2]);
-}
-
-#[test]
-fn test_insert_update() {
-    let mut map = LinkedHashMap::new();
-    map.insert("1".to_string(), vec![10, 10]);
-    map.insert("1".to_string(), vec![10, 19]);
-    assert_opt_eq(map.get(&"1".to_string()), vec![10, 19]);
-    assert_eq!(map.len(), 1);
-}
-
-#[test]
-fn test_entry_insert_vacant() {
-    let mut map = LinkedHashMap::new();
-    match map.entry("1".to_string()) {
-        Entry::Vacant(e) => {
-            assert_eq!(*e.insert(vec![10, 10]), vec![10, 10]);
-        }
-        _ => panic!("fail"),
-    }
-    assert!(map.contains_key("1"));
-    assert_eq!(map["1"], vec![10, 10]);
-
-    match map.entry("1".to_string()) {
-        Entry::Occupied(mut e) => {
-            assert_eq!(*e.get(), vec![10, 10]);
-            assert_eq!(e.insert(vec![10, 16]), vec![10, 10]);
-        }
-        _ => panic!("fail"),
-    }
-
-    assert!(map.contains_key("1"));
-    assert_eq!(map["1"], vec![10, 16]);
-
-    match map.entry("1".to_string()) {
-        Entry::Occupied(e) => {
-            assert_eq!(e.remove(), vec![10, 16]);
-        }
-        _ => panic!("fail"),
-    }
-}
-
-#[test]
-fn test_entries_replacing() {
-    let mut map = LinkedHashMap::new();
-    map.insert("a", 10);
-
-    {
-        let mut iter = map.entries();
-        let mut entry = iter.next().unwrap();
-        assert_eq!(entry.insert(20), 10);
-        assert!(iter.next().is_none());
-    }
-
-    assert_eq!(map["a"], 20);
-}
-
-#[test]
-fn test_entries_remove() {
-    let mut map = LinkedHashMap::new();
-    map.insert("a", 10);
-    map.insert("b", 20);
-    map.insert("c", 30);
-    map.insert("d", 40);
-
-    // remove middle
-    {
-        let mut iter = map.entries();
-        iter.next().unwrap();
-        let b = iter.next().unwrap();
-        assert_eq!(*b.key(), "b");
-        assert_eq!(b.remove(), 20);
-        assert_eq!(*iter.next().unwrap().key(), "c");
-    }
-
-    assert_eq!(map.len(), 3);
-    assert_eq!(map["a"], 10);
-    assert_eq!(map["c"], 30);
-    assert_eq!(map["d"], 40);
-
-    // remove first
-    {
-        let mut iter = map.entries();
-        let a = iter.next().unwrap();
-        assert_eq!(*a.key(), "a");
-        assert_eq!(a.remove(), 10);
-    }
-
-    assert_eq!(map.len(), 2);
-    assert_eq!(map["c"], 30);
-    assert_eq!(map["d"], 40);
-
-    // remove last
-    {
-        let mut iter = map.entries();
-        iter.next().unwrap();
-        let d = iter.next().unwrap();
-        assert_eq!(*d.key(), "d");
-        assert_eq!(d.remove(), 40);
-        assert!(iter.next().is_none());
-    }
-
-    assert_eq!(map.len(), 1);
-    assert_eq!(map["c"], 30);
-
-    // remove only
-    {
-        let mut iter = map.entries();
-        let c = iter.next().unwrap();
-        assert_eq!(*c.key(), "c");
-        assert_eq!(c.remove(), 30);
-    }
-
-    assert!(map.is_empty());
-}
-#[test]
-fn entries_insert() {
-    let mut map = LinkedHashMap::new();
-    map.insert(0, 0);
-    map.insert(1, 1);
-
-    let mut iter = map.entries();
-
-    iter.next().unwrap().insert(0);
-    iter.next().unwrap(); // 1
-    assert!(iter.next().is_none());
-}
-
-#[test]
-fn test_debug() {
-    let mut map = LinkedHashMap::new();
-    assert_eq!(format!("{:?}", map), "{}");
-    map.insert(1, 10);
-    map.insert(2, 20);
-    map.insert(3, 30);
-    assert_eq!(format!("{:?}", map), "{1: 10, 2: 20, 3: 30}");
-    map.insert(2, 22);
-    assert_eq!(format!("{:?}", map), "{1: 10, 3: 30, 2: 22}");
-    map.get(&3);
-    assert_eq!(format!("{:?}", map), "{1: 10, 3: 30, 2: 22}");
-    map.get_refresh(&mut 3);
-    assert_eq!(format!("{:?}", map), "{1: 10, 2: 22, 3: 30}");
-    map.clear();
-    assert_eq!(format!("{:?}", map), "{}");
-}
-
-#[test]
-fn test_remove() {
-    let mut map = LinkedHashMap::new();
-    map.insert(1, 10);
-    map.insert(2, 20);
-    map.insert(3, 30);
-    map.insert(4, 40);
-    map.insert(5, 50);
-    map.remove(&3);
-    map.remove(&4);
-    assert!(map.get(&3).is_none());
-    assert!(map.get(&4).is_none());
-    map.insert(6, 60);
-    map.insert(7, 70);
-    map.insert(8, 80);
-    assert_opt_eq(map.get(&6), 60);
-    assert_opt_eq(map.get(&7), 70);
-    assert_opt_eq(map.get(&8), 80);
-}
-
-
-#[test]
-fn test_pop() {
-    let mut map = LinkedHashMap::new();
-    map.insert(1, 10);
-    map.insert(2, 20);
-    map.insert(3, 30);
-    map.insert(4, 40);
-    map.insert(5, 50);
-    assert_eq!(map.pop_front(), Some((1, 10)));
-    assert!(map.get(&1).is_none());
-    assert_eq!(map.pop_back(), Some((5, 50)));
-    assert!(map.get(&5).is_none());
-    map.insert(6, 60);
-    map.insert(7, 70);
-    map.insert(8, 80);
-    assert_eq!(map.pop_front(), Some((2, 20)));
-    assert!(map.get(&2).is_none());
-    assert_eq!(map.pop_back(), Some((8, 80)));
-    assert!(map.get(&8).is_none());
-    map.insert(3, 30);
-    assert_eq!(map.pop_front(), Some((4, 40)));
-    assert!(map.get(&4).is_none());
-    assert_eq!(map.pop_back(), Some((3, 30)));
-    assert!(map.get(&3).is_none());
-}
-
-#[test]
-fn test_clear() {
-    let mut map = LinkedHashMap::new();
-    map.insert(1, 10);
-    map.insert(2, 20);
-    map.clear();
-    assert!(map.get(&1).is_none());
-    assert!(map.get(&2).is_none());
-    assert_eq!(format!("{:?}", map), "{}");
-}
-
-#[test]
-fn test_iter() {
-    let mut map = LinkedHashMap::new();
-
-    // empty iter
-    assert_eq!(None, map.iter().next());
-
-    map.insert("a", 10);
-    map.insert("b", 20);
-    map.insert("c", 30);
-
-    // regular iter
-    let mut iter = map.iter();
-    assert_eq!((&"a", &10), iter.next().unwrap());
-    assert_eq!((&"b", &20), iter.next().unwrap());
-    assert_eq!((&"c", &30), iter.next().unwrap());
-    assert_eq!(None, iter.next());
-    assert_eq!(None, iter.next());
-
-    // reversed iter
-    let mut rev_iter = map.iter().rev();
-    assert_eq!((&"c", &30), rev_iter.next().unwrap());
-    assert_eq!((&"b", &20), rev_iter.next().unwrap());
-    assert_eq!((&"a", &10), rev_iter.next().unwrap());
-    assert_eq!(None, rev_iter.next());
-    assert_eq!(None, rev_iter.next());
-
-    // mixed
-    let mut mixed_iter = map.iter();
-    assert_eq!((&"a", &10), mixed_iter.next().unwrap());
-    assert_eq!((&"c", &30), mixed_iter.next_back().unwrap());
-    assert_eq!((&"b", &20), mixed_iter.next().unwrap());
-    assert_eq!(None, mixed_iter.next());
-    assert_eq!(None, mixed_iter.next_back());
-}
-
-#[test]
-fn test_iter_mut() {
-    let mut map = LinkedHashMap::new();
-    map.insert("a", 10);
-    map.insert("c", 30);
-    map.insert("b", 20);
-
-    {
-        let mut iter = map.iter_mut();
-        let entry = iter.next().unwrap();
-        assert_eq!(&"a", entry.0);
-        *entry.1 = 17;
-
-        // reverse iterator
-        let mut iter = iter.rev();
-        let entry = iter.next().unwrap();
-        assert_eq!(&"b", entry.0);
-        *entry.1 = 23;
-
-        let entry = iter.next().unwrap();
-        assert_eq!(&"c", entry.0);
-        assert_eq!(None, iter.next());
-        assert_eq!(None, iter.next());
-    }
-
-    assert_eq!(17, map[&"a"]);
-    assert_eq!(23, map[&"b"]);
-}
-
-#[test]
-fn test_consuming_iter() {
-    let map = {
-        let mut map = LinkedHashMap::new();
-        map.insert("a", 10);
-        map.insert("c", 30);
-        map.insert("b", 20);
-        map
-    };
-
-    let mut iter = map.into_iter();
-    assert_eq!(Some(("a", 10)), iter.next());
-
-    let clone = iter.clone();
-    for iter in &mut [iter, clone] {
-        assert_eq!(Some(("b", 20)), iter.next_back());
-        assert_eq!(1, iter.len());
-        assert_eq!(Some(("c", 30)), iter.next());
-        assert_eq!(None, iter.next());
-    }
-}
-
-#[test]
-fn test_consuming_iter_empty() {
-    let map = LinkedHashMap::<&str, i32>::new();
-    let mut iter = map.into_iter();
-    assert_eq!(None, iter.next());
-    let mut clone = iter.clone();
-    assert_eq!(None, clone.next());
-}
-
-#[test]
-fn test_consuming_iter_with_free_list() {
-    let mut map = LinkedHashMap::new();
-    map.insert("a", 10);
-    map.insert("c", 30);
-    map.insert("b", 20);
-    map.remove("a");
-    map.remove("b");
-
-    let mut iter = map.into_iter();
-    assert_eq!(Some(("c", 30)), iter.next());
-    assert_eq!(None, iter.next());
-}
-
-#[test]
-fn test_into_iter_drop() {
-    struct Counter<'a>(&'a mut usize);
-
-    impl<'a> Drop for Counter<'a> {
-        fn drop(&mut self) {
-            *self.0 += 1;
-        }
-    }
-
-    let mut a = 0;
-    let mut b = 0;
-    let mut c = 0;
-
-    {
-        let mut map = LinkedHashMap::new();
-        map.insert("a", Counter(&mut a));
-        map.insert("b", Counter(&mut b));
-        map.insert("c", Counter(&mut c));
-
-        let mut iter = map.into_iter();
-        iter.next();
-        iter.next_back();
-    }
-
-    assert_eq!(a, 1);
-    assert_eq!(b, 1);
-    assert_eq!(c, 1);
-}
-
-#[test]
-fn test_borrow() {
-    #[derive(PartialEq, Eq, Hash)] struct Foo(Bar);
-    #[derive(PartialEq, Eq, Hash)] struct Bar(i32);
-
-    impl ::std::borrow::Borrow<Bar> for Foo {
-        fn borrow(&self) -> &Bar { &self.0 }
-    }
-
-    let mut map = LinkedHashMap::new();
-    map.insert(Foo(Bar(1)), "a");
-    map.insert(Foo(Bar(2)), "b");
-
-    assert!(map.contains_key(&Bar(1)));
-    assert!(map.contains_key(&Bar(2)));
-    assert!(map.contains_key(&Foo(Bar(1))));
-    assert!(map.contains_key(&Foo(Bar(2))));
-
-    assert_eq!(map.get(&Bar(1)), Some(&"a"));
-    assert_eq!(map.get(&Bar(2)), Some(&"b"));
-    assert_eq!(map.get(&Foo(Bar(1))), Some(&"a"));
-    assert_eq!(map.get(&Foo(Bar(2))), Some(&"b"));
-
-    assert_eq!(map.get_refresh(&Bar(1)), Some(&mut "a"));
-    assert_eq!(map.get_refresh(&Bar(2)), Some(&mut "b"));
-    assert_eq!(map.get_refresh(&Foo(Bar(1))), Some(&mut "a"));
-    assert_eq!(map.get_refresh(&Foo(Bar(2))), Some(&mut "b"));
-
-    assert_eq!(map.get_mut(&Bar(1)), Some(&mut "a"));
-    assert_eq!(map.get_mut(&Bar(2)), Some(&mut "b"));
-    assert_eq!(map.get_mut(&Foo(Bar(1))), Some(&mut "a"));
-    assert_eq!(map.get_mut(&Foo(Bar(2))), Some(&mut "b"));
-
-    assert_eq!(map[&Bar(1)], "a");
-    assert_eq!(map[&Bar(2)], "b");
-    assert_eq!(map[&Foo(Bar(1))], "a");
-    assert_eq!(map[&Foo(Bar(2))], "b");
-
-    assert_eq!(map.remove(&Bar(1)), Some("a"));
-    assert_eq!(map.remove(&Bar(2)), Some("b"));
-    assert_eq!(map.remove(&Foo(Bar(1))), None);
-    assert_eq!(map.remove(&Foo(Bar(2))), None);
-}
-
-#[test]
-fn test_send_sync() {
-    fn is_send_sync<T: Send + Sync>() {}
-
-    is_send_sync::<LinkedHashMap<u32, i32>>();
-    is_send_sync::<linked_hash_map::Iter<u32, i32>>();
-    is_send_sync::<linked_hash_map::IterMut<u32, i32>>();
-    is_send_sync::<linked_hash_map::IntoIter<u32, i32>>();
-    is_send_sync::<linked_hash_map::Keys<u32, i32>>();
-    is_send_sync::<linked_hash_map::Values<u32, i32>>();
-}