Auto merge of #31684 - tmiasko:alternate-stack, r=alexcrichton

[rust.git] / src / libcollections / btree / map.rs

diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs
index 2375a63fbd700e311c6b76bab2478ffd6f6ae8bd..7207e7b151c1eae3966022d942574d4cc9a672c2 100644 (file)
--- a/src/libcollections/btree/map.rs
+++ b/src/libcollections/btree/map.rs
@@ -12,6 +12,7 @@
 use core::fmt::Debug;
 use core::hash::{Hash, Hasher};
 use core::iter::FromIterator;
+use core::marker::PhantomData;
 use core::ops::Index;
 use core::{fmt, intrinsics, mem, ptr};
 
@@ -158,7 +159,8 @@ fn take(&mut self, key: &Q) -> Option<K> {
             Found(handle) => {
                 Some(OccupiedEntry {
                     handle: handle,
-                    length: &mut self.length
+                    length: &mut self.length,
+                    _marker: PhantomData,
                 }.remove_kv().0)
             },
             GoDown(_) => None
@@ -172,7 +174,8 @@ fn replace(&mut self, key: K) -> Option<K> {
                 VacantEntry {
                     key: key,
                     handle: handle,
-                    length: &mut self.length
+                    length: &mut self.length,
+                    _marker: PhantomData,
                 }.insert(());
                 None
             }
@@ -223,7 +226,10 @@ pub struct Range<'a, K: 'a, V: 'a> {
 /// A mutable iterator over a sub-range of BTreeMap's entries.
 pub struct RangeMut<'a, K: 'a, V: 'a> {
     front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
-    back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>
+    back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+
+    // Be invariant in `K` and `V`
+    _marker: PhantomData<&'a mut (K, V)>,
 }
 
 /// A view into a single entry in a map, which may either be vacant or occupied.
@@ -247,7 +253,10 @@ pub enum Entry<'a, K: 'a, V: 'a> {
 pub struct VacantEntry<'a, K: 'a, V: 'a> {
     key: K,
     handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
-    length: &'a mut usize
+    length: &'a mut usize,
+
+    // Be invariant in `K` and `V`
+    _marker: PhantomData<&'a mut (K, V)>,
 }
 
 /// An occupied Entry.
@@ -259,7 +268,10 @@ pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
         marker::LeafOrInternal
     >, marker::KV>,
 
-    length: &'a mut usize
+    length: &'a mut usize,
+
+    // Be invariant in `K` and `V`
+    _marker: PhantomData<&'a mut (K, V)>,
 }
 
 impl<K: Ord, V> BTreeMap<K, V> {
@@ -363,9 +375,10 @@ pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<
     ///
     /// If the map did not have this key present, `None` is returned.
     ///
-    /// If the map did have this key present, the key is not updated, the
-    /// value is updated and the old value is returned.
-    /// See the [module-level documentation] for more.
+    /// If the map did have this key present, the value is updated, and the old
+    /// value is returned. The key is not updated, though; this matters for
+    /// types that can be `==` without being identical. See the [module-level
+    /// documentation] for more.
     ///
     /// [module-level documentation]: index.html#insert-and-complex-keys
     ///
@@ -415,7 +428,8 @@ pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q:
             Found(handle) => {
                 Some(OccupiedEntry {
                     handle: handle,
-                    length: &mut self.length
+                    length: &mut self.length,
+                    _marker: PhantomData,
                 }.remove())
             },
             GoDown(_) => None
@@ -568,7 +582,8 @@ pub fn range_mut<Min: ?Sized + Ord, Max: ?Sized + Ord>(&mut self,
 
         RangeMut {
             front: front,
-            back: back
+            back: back,
+            _marker: PhantomData
         }
     }
 
@@ -593,12 +608,14 @@ pub fn entry(&mut self, key: K) -> Entry<K, V> {
         match search::search_tree(self.root.as_mut(), &key) {
             Found(handle) => Occupied(OccupiedEntry {
                 handle: handle,
-                length: &mut self.length
+                length: &mut self.length,
+                _marker: PhantomData,
             }),
             GoDown(handle) => Vacant(VacantEntry {
                 key: key,
                 handle: handle,
-                length: &mut self.length
+                length: &mut self.length,
+                _marker: PhantomData,
             })
         }
     }
@@ -1178,7 +1195,7 @@ unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
 }
 
 impl<K, V> BTreeMap<K, V> {
-    /// Gets an iterator over the entries of the map.
+    /// Gets an iterator over the entries of the map, sorted by key.
     ///
     /// # Examples
     ///
@@ -1186,9 +1203,9 @@ impl<K, V> BTreeMap<K, V> {
     /// use std::collections::BTreeMap;
     ///
     /// let mut map = BTreeMap::new();
-    /// map.insert(1, "a");
-    /// map.insert(2, "b");
     /// map.insert(3, "c");
+    /// map.insert(2, "b");
+    /// map.insert(1, "a");
     ///
     /// for (key, value) in map.iter() {
     ///     println!("{}: {}", key, value);
@@ -1208,7 +1225,7 @@ pub fn iter(&self) -> Iter<K, V> {
         }
     }
 
-    /// Gets a mutable iterator over the entries of the map.
+    /// Gets a mutable iterator over the entries of the map, sorted by key.
     ///
     /// # Examples
     ///
@@ -1235,12 +1252,13 @@ pub fn iter_mut(&mut self) -> IterMut<K, V> {
             range: RangeMut {
                 front: first_leaf_edge(root1),
                 back: last_leaf_edge(root2),
+                _marker: PhantomData,
             },
             length: self.length
         }
     }
 
-    /// Gets an iterator over the keys of the map.
+    /// Gets an iterator over the keys of the map, in sorted order.
     ///
     /// # Examples
     ///
@@ -1248,8 +1266,8 @@ pub fn iter_mut(&mut self) -> IterMut<K, V> {
     /// use std::collections::BTreeMap;
     ///
     /// let mut a = BTreeMap::new();
-    /// a.insert(1, "a");
     /// a.insert(2, "b");
+    /// a.insert(1, "a");
     ///
     /// let keys: Vec<_> = a.keys().cloned().collect();
     /// assert_eq!(keys, [1, 2]);
@@ -1259,7 +1277,7 @@ pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
         Keys { inner: self.iter() }
     }
 
-    /// Gets an iterator over the values of the map.
+    /// Gets an iterator over the values of the map, in order by key.
     ///
     /// # Examples
     ///
@@ -1267,11 +1285,11 @@ pub fn keys<'a>(&'a self) -> Keys<'a, K, V> {
     /// use std::collections::BTreeMap;
     ///
     /// let mut a = BTreeMap::new();
-    /// a.insert(1, "a");
-    /// a.insert(2, "b");
+    /// a.insert(1, "hello");
+    /// a.insert(2, "goodbye");
     ///
     /// let values: Vec<&str> = a.values().cloned().collect();
-    /// assert_eq!(values, ["a", "b"]);
+    /// assert_eq!(values, ["hello", "goodbye"]);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn values<'a>(&'a self) -> Values<'a, K, V> {