Snap for 10453563 from 4f9ba88634b7c5e310e5e590a72879ba726844c4 to mainline-permission-release
Change-Id: I054deea721445f72ff903fef1f1d7e7437324fa6
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 @@
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 @@
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 @@
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 @@
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 @@
}
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 @@
+ [](https://crates.io/crates/linked-hash-map) [](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, 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, 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::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: 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 @@
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 @@
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 @@
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 @@
// 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: 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 @@
/// # 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 @@
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 @@
});
}
- 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 @@
/// 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 @@
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 @@
}
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 @@
}
/// 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 @@
/// 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 @@
/// *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 @@
///
/// 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 @@
/// 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 @@
#[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 @@
#[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 @@
#[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 @@
/// 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 @@
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 @@
unsafe { (*self.head).prev }
};
Iter {
- head: head,
+ head,
tail: self.head,
remaining: self.len(),
marker: marker::PhantomData,
@@ -648,13 +688,67 @@
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<'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> 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, 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<'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<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<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: 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, 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 @@
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 @@
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 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, S> Send for Entries<'a, K, V, S> where K: Send, V: Send, S: Send {}
-
-unsafe impl<'a, K, V> Sync for Iter<'a, 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<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 {}
-
-impl<'a, K, V> Clone for Iter<'a, K, V> {
- fn clone(&self) -> Self { Iter { ..*self } }
+unsafe impl<'a, K, V> Send for Iter<'a, K, V>
+where
+ K: Send,
+ V: Send,
+{
}
-impl<K, V> Clone for IntoIter<K, V> where K: Clone, V: Clone {
+unsafe impl<'a, K, V> Send for IterMut<'a, 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<K, V> Send for IntoIter<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<'a, K, V> Sync for Iter<'a, 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,
+{
+}
+
+impl<'a, K, V> Clone for Iter<'a, K, V> {
+ fn clone(&self) -> Self {
+ Iter { ..*self }
+ }
+}
+
+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 @@
}
IntoIter {
- head: head,
- tail: tail,
+ head,
+ tail,
remaining: self.remaining,
marker: marker::PhantomData,
}
@@ -955,7 +1141,7 @@
fn next(&mut self) -> Option<(K, V)> {
if self.remaining == 0 {
- return None
+ return None;
}
self.remaining -= 1;
unsafe {
@@ -971,6 +1157,54 @@
}
}
+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<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<'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<'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 @@
}
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 @@
}
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 @@
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 @@
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<'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 @@
#[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> 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>>();
-}