From c71f720d9bf331c2922eafc35c27ccac05e94e5d Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Fri, 22 Jan 2016 14:34:10 +0100
Subject: Rename 'distance' -> 'displacement'

---
 src/libstd/collections/hash/map.rs   | 8 ++++----
 src/libstd/collections/hash/table.rs | 2 +-
 2 files changed, 5 insertions(+), 5 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 051829fbafb..820b47af715 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -393,7 +393,7 @@ fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
         None => return (retkey, retval)
     };
 
-    while gap.full().distance() != 0 {
+    while gap.full().displacement() != 0 {
         gap = match gap.shift() {
             Some(b) => b,
             None => break
@@ -423,7 +423,7 @@ fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
     // There can be at most `size - dib` buckets to displace, because
     // in the worst case, there are `size` elements and we already are
     // `distance` buckets away from the initial one.
-    let idx_end = starting_index + size - bucket.distance();
+    let idx_end = starting_index + size - bucket.displacement();
 
     loop {
         let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
@@ -446,7 +446,7 @@ fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
                 Full(bucket) => bucket
             };
 
-            let probe_ib = full_bucket.index() - full_bucket.distance();
+            let probe_ib = full_bucket.index() - full_bucket.displacement();
 
             bucket = full_bucket;
 
@@ -731,7 +731,7 @@ impl<K, V, S> HashMap<K, V, S>
         loop {
             bucket = match bucket.peek() {
                 Full(full) => {
-                    if full.distance() == 0 {
+                    if full.displacement() == 0 {
                         // This bucket occupies its ideal spot.
                         // It indicates the start of another "cluster".
                         bucket = full.into_bucket();
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 97cab94b67b..3a7ff0c1e22 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -370,7 +370,7 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> FullBucket<K, V, M> {
     ///
     /// In the cited blog posts above, this is called the "distance to
     /// initial bucket", or DIB. Also known as "probe count".
-    pub fn distance(&self) -> usize {
+    pub fn displacement(&self) -> usize {
         // Calculates the distance one has to travel when going from
         // `hash mod capacity` onwards to `idx mod capacity`, wrapping around
         // if the destination is not reached before the end of the table.
-- 
cgit 1.4.1-3-g733a5


From a619fdd2ad06c8aea1aa4f5043dfa243d5438b55 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Sat, 5 Mar 2016 22:11:15 +0100
Subject: Add `InternalEntry` for use in all searches.

---
 src/libstd/collections/hash/map.rs   | 268 ++++++++++++++---------------------
 src/libstd/collections/hash/table.rs |  18 +--
 2 files changed, 119 insertions(+), 167 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 820b47af715..91626b8d16b 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -9,7 +9,6 @@
 // except according to those terms.
 
 use self::Entry::*;
-use self::SearchResult::*;
 use self::VacantEntryState::*;
 
 use borrow::Borrow;
@@ -26,7 +25,6 @@ use super::table::{
     Bucket,
     EmptyBucket,
     FullBucket,
-    FullBucketImm,
     FullBucketMut,
     RawTable,
     SafeHash
@@ -342,10 +340,11 @@ pub struct HashMap<K, V, S = RandomState> {
 }
 
 /// Search for a pre-hashed key.
+#[inline]
 fn search_hashed<K, V, M, F>(table: M,
                              hash: SafeHash,
                              mut is_match: F)
-                             -> SearchResult<K, V, M> where
+                             -> InternalEntry<K, V, M> where
     M: Deref<Target=RawTable<K, V>>,
     F: FnMut(&K) -> bool,
 {
@@ -353,37 +352,50 @@ fn search_hashed<K, V, M, F>(table: M,
     // undefined behavior when Bucket::new gets the raw bucket in this
     // case, immediately return the appropriate search result.
     if table.capacity() == 0 {
-        return TableRef(table);
+        return InternalEntry::TableIsEmpty;
     }
 
-    let size = table.size();
+    let size = table.size() as isize;
     let mut probe = Bucket::new(table, hash);
-    let ib = probe.index();
+    let ib = probe.index() as isize;
 
-    while probe.index() != ib + size {
+    loop {
         let full = match probe.peek() {
-            Empty(b) => return TableRef(b.into_table()), // hit an empty bucket
-            Full(b) => b
+            Empty(bucket) => {
+                // Found a hole!
+                return InternalEntry::Vacant {
+                    hash: hash,
+                    elem: NoElem(bucket),
+                };
+            }
+            Full(bucket) => bucket
         };
 
-        if full.distance() + ib < full.index() {
+        let robin_ib = full.index() as isize - full.displacement() as isize;
+
+        if ib < robin_ib {
+            // Found a luckier bucket than me.
             // We can finish the search early if we hit any bucket
             // with a lower distance to initial bucket than we've probed.
-            return TableRef(full.into_table());
+            return InternalEntry::Vacant {
+                hash: hash,
+                elem: NeqElem(full, robin_ib as usize),
+            };
         }
 
         // If the hash doesn't match, it can't be this one..
         if hash == full.hash() {
             // If the key doesn't match, it can't be this one..
             if is_match(full.read().0) {
-                return FoundExisting(full);
+                return InternalEntry::Occupied {
+                    elem: full
+                };
             }
         }
 
         probe = full.next();
+        assert!(probe.index() as isize != ib + size + 1);
     }
-
-    TableRef(probe.into_table())
 }
 
 fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
@@ -462,25 +474,6 @@ fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
     }
 }
 
-/// A result that works like Option<FullBucket<..>> but preserves
-/// the reference that grants us access to the table in any case.
-enum SearchResult<K, V, M> {
-    // This is an entry that holds the given key:
-    FoundExisting(FullBucket<K, V, M>),
-
-    // There was no such entry. The reference is given back:
-    TableRef(M)
-}
-
-impl<K, V, M> SearchResult<K, V, M> {
-    fn into_option(self) -> Option<FullBucket<K, V, M>> {
-        match self {
-            FoundExisting(bucket) => Some(bucket),
-            TableRef(_) => None
-        }
-    }
-}
-
 impl<K, V, S> HashMap<K, V, S>
     where K: Eq + Hash, S: BuildHasher
 {
@@ -491,20 +484,20 @@ impl<K, V, S> HashMap<K, V, S>
     /// Search for a key, yielding the index if it's found in the hashtable.
     /// If you already have the hash for the key lying around, use
     /// search_hashed.
-    fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> Option<FullBucketImm<'a, K, V>>
+    #[inline]
+    fn search<'a, Q: ?Sized>(&'a self, q: &Q) -> InternalEntry<K, V, &'a RawTable<K, V>>
         where K: Borrow<Q>, Q: Eq + Hash
     {
         let hash = self.make_hash(q);
         search_hashed(&self.table, hash, |k| q.eq(k.borrow()))
-            .into_option()
     }
 
-    fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> Option<FullBucketMut<'a, K, V>>
+    #[inline]
+    fn search_mut<'a, Q: ?Sized>(&'a mut self, q: &Q) -> InternalEntry<K, V, &'a mut RawTable<K, V>>
         where K: Borrow<Q>, Q: Eq + Hash
     {
         let hash = self.make_hash(q);
         search_hashed(&mut self.table, hash, |k| q.eq(k.borrow()))
-            .into_option()
     }
 
     // The caller should ensure that invariants by Robin Hood Hashing hold.
@@ -824,53 +817,19 @@ impl<K, V, S> HashMap<K, V, S>
     ///
     /// If the key already exists, the hashtable will be returned untouched
     /// and a reference to the existing element will be returned.
-    fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> &mut V {
-        self.insert_or_replace_with(hash, k, v, |_, _, _, _| ())
-    }
-
-    fn insert_or_replace_with<'a, F>(&'a mut self,
-                                     hash: SafeHash,
-                                     k: K,
-                                     v: V,
-                                     mut found_existing: F)
-                                     -> &'a mut V where
-        F: FnMut(&mut K, &mut V, K, V),
-    {
-        // Worst case, we'll find one empty bucket among `size + 1` buckets.
-        let size = self.table.size();
-        let mut probe = Bucket::new(&mut self.table, hash);
-        let ib = probe.index();
-
-        loop {
-            let mut bucket = match probe.peek() {
-                Empty(bucket) => {
-                    // Found a hole!
-                    return bucket.put(hash, k, v).into_mut_refs().1;
-                }
-                Full(bucket) => bucket
-            };
-
-            // hash matches?
-            if bucket.hash() == hash {
-                // key matches?
-                if k == *bucket.read_mut().0 {
-                    let (bucket_k, bucket_v) = bucket.into_mut_refs();
-                    debug_assert!(k == *bucket_k);
-                    // Key already exists. Get its reference.
-                    found_existing(bucket_k, bucket_v, k, v);
-                    return bucket_v;
-                }
+    fn insert_hashed_nocheck(&mut self, hash: SafeHash, k: K, v: V) -> Option<V> {
+        let entry = search_hashed(&mut self.table, hash, |key| *key == k).into_entry(k);
+        match entry {
+            Some(Occupied(mut elem)) => {
+                Some(elem.insert(v))
             }
-
-            let robin_ib = bucket.index() as isize - bucket.distance() as isize;
-
-            if (ib as isize) < robin_ib {
-                // Found a luckier bucket than me. Better steal his spot.
-                return robin_hood(bucket, robin_ib as usize, hash, k, v);
+            Some(Vacant(elem)) => {
+                elem.insert(v);
+                None
+            }
+            None => {
+                unreachable!()
             }
-
-            probe = bucket.next();
-            assert!(probe.index() != ib + size + 1);
         }
     }
 
@@ -997,9 +956,7 @@ impl<K, V, S> HashMap<K, V, S>
     pub fn entry(&mut self, key: K) -> Entry<K, V> {
         // Gotta resize now.
         self.reserve(1);
-
-        let hash = self.make_hash(&key);
-        search_entry_hashed(&mut self.table, hash, key)
+        self.search_mut(&key).into_entry(key).expect("unreachable")
     }
 
     /// Returns the number of elements in the map.
@@ -1102,7 +1059,7 @@ impl<K, V, S> HashMap<K, V, S>
     pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
         where K: Borrow<Q>, Q: Hash + Eq
     {
-        self.search(k).map(|bucket| bucket.into_refs().1)
+        self.search(k).into_occupied_bucket().map(|bucket| bucket.into_refs().1)
     }
 
     /// Returns true if the map contains a value for the specified key.
@@ -1125,7 +1082,7 @@ impl<K, V, S> HashMap<K, V, S>
     pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
         where K: Borrow<Q>, Q: Hash + Eq
     {
-        self.search(k).is_some()
+        self.search(k).into_occupied_bucket().is_some()
     }
 
     /// Returns a mutable reference to the value corresponding to the key.
@@ -1150,7 +1107,7 @@ impl<K, V, S> HashMap<K, V, S>
     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
         where K: Borrow<Q>, Q: Hash + Eq
     {
-        self.search_mut(k).map(|bucket| bucket.into_mut_refs().1)
+        self.search_mut(k).into_occupied_bucket().map(|bucket| bucket.into_mut_refs().1)
     }
 
     /// Inserts a key-value pair into the map.
@@ -1181,12 +1138,7 @@ impl<K, V, S> HashMap<K, V, S>
     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
         let hash = self.make_hash(&k);
         self.reserve(1);
-
-        let mut retval = None;
-        self.insert_or_replace_with(hash, k, v, |_, val_ref, _, val| {
-            retval = Some(replace(val_ref, val));
-        });
-        retval
+        self.insert_hashed_nocheck(hash, k, v)
     }
 
     /// Removes a key from the map, returning the value at the key if the key
@@ -1214,54 +1166,7 @@ impl<K, V, S> HashMap<K, V, S>
             return None
         }
 
-        self.search_mut(k).map(|bucket| pop_internal(bucket).1)
-    }
-}
-
-fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
-        -> Entry<'a, K, V>
-{
-    // Worst case, we'll find one empty bucket among `size + 1` buckets.
-    let size = table.size();
-    let mut probe = Bucket::new(table, hash);
-    let ib = probe.index();
-
-    loop {
-        let bucket = match probe.peek() {
-            Empty(bucket) => {
-                // Found a hole!
-                return Vacant(VacantEntry {
-                    hash: hash,
-                    key: k,
-                    elem: NoElem(bucket),
-                });
-            },
-            Full(bucket) => bucket
-        };
-
-        // hash matches?
-        if bucket.hash() == hash {
-            // key matches?
-            if k == *bucket.read().0 {
-                return Occupied(OccupiedEntry{
-                    elem: bucket,
-                });
-            }
-        }
-
-        let robin_ib = bucket.index() as isize - bucket.distance() as isize;
-
-        if (ib as isize) < robin_ib {
-            // Found a luckier bucket than me. Better steal his spot.
-            return Vacant(VacantEntry {
-                hash: hash,
-                key: k,
-                elem: NeqElem(bucket, robin_ib as usize),
-            });
-        }
-
-        probe = bucket.next();
-        assert!(probe.index() != ib + size + 1);
+        self.search_mut(k).into_occupied_bucket().map(|bucket| pop_internal(bucket).1)
     }
 }
 
@@ -1382,18 +1287,46 @@ pub struct Drain<'a, K: 'a, V: 'a> {
     inner: iter::Map<table::Drain<'a, K, V>, fn((SafeHash, K, V)) -> (K, V)>
 }
 
-/// A view into a single occupied location in a HashMap.
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
-    elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
+enum InternalEntry<K, V, M> {
+    Occupied {
+        elem: FullBucket<K, V, M>,
+    },
+    Vacant {
+        hash: SafeHash,
+        elem: VacantEntryState<K, V, M>,
+    },
+    TableIsEmpty,
 }
 
-/// A view into a single empty location in a HashMap.
-#[stable(feature = "rust1", since = "1.0.0")]
-pub struct VacantEntry<'a, K: 'a, V: 'a> {
-    hash: SafeHash,
-    key: K,
-    elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
+impl<K, V, M> InternalEntry<K, V, M> {
+    #[inline]
+    fn into_occupied_bucket(self) -> Option<FullBucket<K, V, M>> {
+        match self {
+            InternalEntry::Occupied { elem } => Some(elem),
+            _ => None,
+        }
+    }
+}
+
+impl<'a, K, V> InternalEntry<K, V, &'a mut RawTable<K, V>> {
+    #[inline]
+    fn into_entry(self, key: K) -> Option<Entry<'a, K, V>> {
+        match self {
+            InternalEntry::Occupied { elem } => {
+                Some(Occupied(OccupiedEntry {
+                    elem: elem
+                }))
+            }
+            InternalEntry::Vacant { hash, elem } => {
+                Some(Vacant(VacantEntry {
+                    hash: hash,
+                    key: key,
+                    elem: elem,
+                }))
+            }
+            InternalEntry::TableIsEmpty => None
+        }
+    }
 }
 
 /// A view into a single location in a map, which may be vacant or occupied.
@@ -1412,6 +1345,20 @@ pub enum Entry<'a, K: 'a, V: 'a> {
     ),
 }
 
+/// A view into a single occupied location in a HashMap.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
+    elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
+}
+
+/// A view into a single empty location in a HashMap.
+#[stable(feature = "rust1", since = "1.0.0")]
+pub struct VacantEntry<'a, K: 'a, V: 'a> {
+    hash: SafeHash,
+    key: K,
+    elem: VacantEntryState<K, V, &'a mut RawTable<K, V>>,
+}
+
 /// Possible states of a VacantEntry.
 enum VacantEntryState<K, V, M> {
     /// The index is occupied, but the key to insert has precedence,
@@ -1703,7 +1650,7 @@ impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
     type Key = K;
 
     fn get(&self, key: &Q) -> Option<&K> {
-        self.search(key).map(|bucket| bucket.into_refs().0)
+        self.search(key).into_occupied_bucket().map(|bucket| bucket.into_refs().0)
     }
 
     fn take(&mut self, key: &Q) -> Option<K> {
@@ -1711,18 +1658,21 @@ impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
             return None
         }
 
-        self.search_mut(key).map(|bucket| pop_internal(bucket).0)
+        self.search_mut(key).into_occupied_bucket().map(|bucket| pop_internal(bucket).0)
     }
 
     fn replace(&mut self, key: K) -> Option<K> {
         let hash = self.make_hash(&key);
         self.reserve(1);
 
-        let mut retkey = None;
-        self.insert_or_replace_with(hash, key, (), |key_ref, _, key, _| {
-            retkey = Some(replace(key_ref, key));
-        });
-        retkey
+        match search_hashed(&mut self.table, hash, |k| *k == key) {
+            InternalEntry::Occupied { mut elem } => {
+                Some(mem::replace(elem.read_mut().0, key))
+            }
+            _ => {
+                None
+            }
+        }
     }
 }
 
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 3a7ff0c1e22..1a29c2c159a 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -180,6 +180,8 @@ impl<K, V> RawBucket<K, V> {
     }
 }
 
+// Uncomment dead code when it's needed.
+
 // Buckets hold references to the table.
 impl<K, V, M> FullBucket<K, V, M> {
     /// Borrow a reference to the table.
@@ -201,17 +203,17 @@ impl<K, V, M> EmptyBucket<K, V, M> {
     pub fn table(&self) -> &M {
         &self.table
     }
-    /// Move out the reference to the table.
-    pub fn into_table(self) -> M {
-        self.table
-    }
+    // /// Move out the reference to the table.
+    // pub fn into_table(self) -> M {
+    //     self.table
+    // }
 }
 
 impl<K, V, M> Bucket<K, V, M> {
-    /// Move out the reference to the table.
-    pub fn into_table(self) -> M {
-        self.table
-    }
+    // /// Move out the reference to the table.
+    // pub fn into_table(self) -> M {
+    //     self.table
+    // }
     /// Get the raw index.
     pub fn index(&self) -> usize {
         self.idx
-- 
cgit 1.4.1-3-g733a5


From f8b8c3ae6b78829d576c70fb056f988a3a37b27c Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Fri, 22 Jan 2016 14:50:28 +0100
Subject: Refactor fn Bucket::next

---
 src/libstd/collections/hash/table.rs | 22 +++++++---------------
 1 file changed, 7 insertions(+), 15 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 1a29c2c159a..7db89dcd128 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -270,22 +270,14 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> Bucket<K, V, M> {
 
     /// Modifies the bucket pointer in place to make it point to the next slot.
     pub fn next(&mut self) {
-        // Branchless bucket iteration step.
-        // As we reach the end of the table...
-        // We take the current idx:          0111111b
-        // Xor it by its increment:        ^ 1000000b
-        //                               ------------
-        //                                   1111111b
-        // Then AND with the capacity:     & 1000000b
-        //                               ------------
-        // to get the backwards offset:      1000000b
-        // ... and it's zero at all other times.
-        let maybe_wraparound_dist = (self.idx ^ (self.idx + 1)) & self.table.capacity();
-        // Finally, we obtain the offset 1 or the offset -cap + 1.
-        let dist = 1 - (maybe_wraparound_dist as isize);
-
         self.idx += 1;
-
+        let range = self.table.capacity();
+        // This code is branchless thanks to a conditional move.
+        let dist = if self.idx & (range - 1) == 0 {
+            1 - range as isize
+        } else {
+            1
+        };
         unsafe {
             self.raw = self.raw.offset(dist);
         }
-- 
cgit 1.4.1-3-g733a5


From 37785608092c995731bc4e90014668b164a8d560 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Sat, 5 Mar 2016 22:20:59 +0100
Subject: Refactor fn robin_hood

---
 src/libstd/collections/hash/map.rs   | 29 ++++++++++----------
 src/libstd/collections/hash/table.rs | 52 +++++++++++++++++++++++++++---------
 2 files changed, 53 insertions(+), 28 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 91626b8d16b..c83c432fc95 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -421,24 +421,30 @@ fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
 /// to recalculate it.
 ///
 /// `hash`, `k`, and `v` are the elements to "robin hood" into the hashtable.
-fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
+fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
                         mut ib: usize,
                         mut hash: SafeHash,
-                        mut k: K,
-                        mut v: V)
+                        mut key: K,
+                        mut val: V)
                         -> &'a mut V {
     let starting_index = bucket.index();
     let size = {
         let table = bucket.table(); // FIXME "lifetime too short".
         table.size()
     };
+    // Save the *starting point*.
+    let mut bucket = bucket.stash();
     // There can be at most `size - dib` buckets to displace, because
     // in the worst case, there are `size` elements and we already are
-    // `distance` buckets away from the initial one.
+    // `displacement` buckets away from the initial one.
     let idx_end = starting_index + size - bucket.displacement();
 
     loop {
-        let (old_hash, old_key, old_val) = bucket.replace(hash, k, v);
+        let (old_hash, old_key, old_val) = bucket.replace(hash, key, val);
+        hash = old_hash;
+        key = old_key;
+        val = old_val;
+
         loop {
             let probe = bucket.next();
             assert!(probe.index() != idx_end);
@@ -446,14 +452,10 @@ fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
             let full_bucket = match probe.peek() {
                 Empty(bucket) => {
                     // Found a hole!
-                    let b = bucket.put(old_hash, old_key, old_val);
+                    let bucket = bucket.put(hash, key, val);
                     // Now that it's stolen, just read the value's pointer
-                    // right out of the table!
-                    return Bucket::at_index(b.into_table(), starting_index)
-                               .peek()
-                               .expect_full()
-                               .into_mut_refs()
-                               .1;
+                    // right out of the table! Go back to the *starting point*.
+                    return bucket.into_table().into_mut_refs().1;
                 },
                 Full(bucket) => bucket
             };
@@ -465,9 +467,6 @@ fn robin_hood<'a, K: 'a, V: 'a>(mut bucket: FullBucketMut<'a, K, V>,
             // Robin hood! Steal the spot.
             if ib < probe_ib {
                 ib = probe_ib;
-                hash = old_hash;
-                k = old_key;
-                v = old_val;
                 break;
             }
         }
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 7db89dcd128..e3acbc96fda 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -220,6 +220,28 @@ impl<K, V, M> Bucket<K, V, M> {
     }
 }
 
+impl<K, V, M> Deref for FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> {
+    type Target = RawTable<K, V>;
+    fn deref(&self) -> &RawTable<K, V> {
+        &self.table
+    }
+}
+
+impl<K, V, M> DerefMut for FullBucket<K, V, M> where M: DerefMut<Target=RawTable<K, V>> {
+    fn deref_mut(&mut self) -> &mut RawTable<K, V> {
+        &mut self.table
+    }
+}
+
+
+/// `Put` is implemented for types which provide access to a table and cannot be invalidated
+///  by filling a bucket. A similar implementation for `Take` is possible.
+pub trait Put {}
+impl<K, V> Put for RawTable<K, V> {}
+impl<'t, K, V> Put for &'t mut RawTable<K, V> {}
+impl<K, V, M: Put> Put for Bucket<K, V, M> {}
+impl<K, V, M: Put> Put for FullBucket<K, V, M> {}
+
 impl<K, V, M: Deref<Target=RawTable<K, V>>> Bucket<K, V, M> {
     pub fn new(table: M, hash: SafeHash) -> Bucket<K, V, M> {
         Bucket::at_index(table, hash.inspect() as usize)
@@ -320,7 +342,7 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> EmptyBucket<K, V, M> {
     }
 }
 
-impl<K, V, M: Deref<Target=RawTable<K, V>> + DerefMut> EmptyBucket<K, V, M> {
+impl<K, V, M> EmptyBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefMut + Put {
     /// Puts given key and value pair, along with the key's hash,
     /// into this bucket in the hashtable. Note how `self` is 'moved' into
     /// this function, because this slot will no longer be empty when
@@ -359,6 +381,16 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> FullBucket<K, V, M> {
         }
     }
 
+    /// Duplicates the current position. This can be useful for operations
+    /// on two or more buckets.
+    pub fn stash(self) -> FullBucket<K, V, Self> {
+        FullBucket {
+            raw: self.raw,
+            idx: self.idx,
+            table: self,
+        }
+    }
+
     /// Get the distance between this bucket and the 'ideal' location
     /// as determined by the key's hash stored in it.
     ///
@@ -389,12 +421,14 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> FullBucket<K, V, M> {
     }
 }
 
-impl<K, V, M: Deref<Target=RawTable<K, V>> + DerefMut> FullBucket<K, V, M> {
+// We don't need a `Take` trait currently. This is why a mutable reference
+// to the table is required.
+impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> {
     /// Removes this bucket's key and value from the hashtable.
     ///
     /// This works similarly to `put`, building an `EmptyBucket` out of the
     /// taken bucket.
-    pub fn take(mut self) -> (EmptyBucket<K, V, M>, K, V) {
+    pub fn take(mut self) -> (EmptyBucket<K, V, &'t mut RawTable<K, V>>, K, V) {
         self.table.size -= 1;
 
         unsafe {
@@ -410,7 +444,9 @@ impl<K, V, M: Deref<Target=RawTable<K, V>> + DerefMut> FullBucket<K, V, M> {
             )
         }
     }
+}
 
+impl<K, V, M> FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefMut {
     pub fn replace(&mut self, h: SafeHash, k: K, v: V) -> (SafeHash, K, V) {
         unsafe {
             let old_hash = ptr::replace(self.raw.hash as *mut SafeHash, h);
@@ -455,16 +491,6 @@ impl<'t, K, V, M: Deref<Target=RawTable<K, V>> + DerefMut + 't> FullBucket<K, V,
     }
 }
 
-impl<K, V, M> BucketState<K, V, M> {
-    // For convenience.
-    pub fn expect_full(self) -> FullBucket<K, V, M> {
-        match self {
-            Full(full) => full,
-            Empty(..) => panic!("Expected full bucket")
-        }
-    }
-}
-
 impl<K, V, M: Deref<Target=RawTable<K, V>>> GapThenFull<K, V, M> {
     #[inline]
     pub fn full(&self) -> &FullBucket<K, V, M> {
-- 
cgit 1.4.1-3-g733a5


From c20cd8fac97fe4d4594d6f78b3adb0e9b171c3bf Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Mon, 8 Feb 2016 13:05:16 +0100
Subject: Use consistent syntax

---
 src/libstd/collections/hash/table.rs | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index e3acbc96fda..3c61faae8ea 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -466,7 +466,7 @@ impl<K, V, M> FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefM
     }
 }
 
-impl<'t, K, V, M: Deref<Target=RawTable<K, V>> + 't> FullBucket<K, V, M> {
+impl<'t, K, V, M> FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + 't {
     /// Exchange a bucket state for immutable references into the table.
     /// Because the underlying reference to the table is also consumed,
     /// no further changes to the structure of the table are possible;
@@ -480,7 +480,7 @@ impl<'t, K, V, M: Deref<Target=RawTable<K, V>> + 't> FullBucket<K, V, M> {
     }
 }
 
-impl<'t, K, V, M: Deref<Target=RawTable<K, V>> + DerefMut + 't> FullBucket<K, V, M> {
+impl<'t, K, V, M> FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefMut + 't {
     /// This works similarly to `into_refs`, exchanging a bucket state
     /// for mutable references into the table.
     pub fn into_mut_refs(self) -> (&'t mut K, &'t mut V) {
@@ -491,7 +491,7 @@ impl<'t, K, V, M: Deref<Target=RawTable<K, V>> + DerefMut + 't> FullBucket<K, V,
     }
 }
 
-impl<K, V, M: Deref<Target=RawTable<K, V>>> GapThenFull<K, V, M> {
+impl<K, V, M> GapThenFull<K, V, M> where M: Deref<Target=RawTable<K, V>> {
     #[inline]
     pub fn full(&self) -> &FullBucket<K, V, M> {
         &self.full
-- 
cgit 1.4.1-3-g733a5


From 0adcd641149bd32cb3d6d7ea8a8140322e500ae1 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Sat, 5 Mar 2016 13:07:38 +0100
Subject: Add tests

---
 src/libstd/collections/hash/map.rs | 42 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index c83c432fc95..86d7aef3d58 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -1706,6 +1706,20 @@ mod test_map {
         assert_eq!(*m.get(&2).unwrap(), 4);
     }
 
+    #[test]
+    fn test_clone() {
+        let mut m = HashMap::new();
+        assert_eq!(m.len(), 0);
+        assert!(m.insert(1, 2).is_none());
+        assert_eq!(m.len(), 1);
+        assert!(m.insert(2, 4).is_none());
+        assert_eq!(m.len(), 2);
+        let m2 = m.clone();
+        assert_eq!(*m2.get(&1).unwrap(), 2);
+        assert_eq!(*m2.get(&2).unwrap(), 4);
+        assert_eq!(m2.len(), 2);
+    }
+
     thread_local! { static DROP_VECTOR: RefCell<Vec<isize>> = RefCell::new(Vec::new()) }
 
     #[derive(Hash, PartialEq, Eq)]
@@ -1797,7 +1811,7 @@ mod test_map {
     }
 
     #[test]
-    fn test_move_iter_drops() {
+    fn test_into_iter_drops() {
         DROP_VECTOR.with(|v| {
             *v.borrow_mut() = vec![0; 200];
         });
@@ -1862,11 +1876,35 @@ mod test_map {
     }
 
     #[test]
-    fn test_empty_pop() {
+    fn test_empty_remove() {
         let mut m: HashMap<isize, bool> = HashMap::new();
         assert_eq!(m.remove(&0), None);
     }
 
+    #[test]
+    fn test_empty_entry() {
+        let mut m: HashMap<isize, bool> = HashMap::new();
+        match m.entry(0) {
+            Occupied(_) => panic!(),
+            Vacant(_) => {}
+        }
+        assert!(*m.entry(0).or_insert(true));
+        assert_eq!(m.len(), 1);
+    }
+
+    #[test]
+    fn test_empty_iter() {
+        let mut m: HashMap<isize, bool> = HashMap::new();
+        assert_eq!(m.drain().next(), None);
+        assert_eq!(m.keys().next(), None);
+        assert_eq!(m.values().next(), None);
+        assert_eq!(m.iter().next(), None);
+        assert_eq!(m.iter_mut().next(), None);
+        assert_eq!(m.len(), 0);
+        assert!(m.is_empty());
+        assert_eq!(m.into_iter().next(), None);
+    }
+
     #[test]
     fn test_lots_of_insertions() {
         let mut m = HashMap::new();
-- 
cgit 1.4.1-3-g733a5


From d67cf45d2222fdde16d935dead18a8be4b080060 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Sat, 5 Mar 2016 22:18:51 +0100
Subject: Turn 2 assertions into debug assertions

---
 src/libstd/collections/hash/map.rs | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 86d7aef3d58..6f044958618 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -394,7 +394,7 @@ fn search_hashed<K, V, M, F>(table: M,
         }
 
         probe = full.next();
-        assert!(probe.index() as isize != ib + size + 1);
+        debug_assert!(probe.index() as isize != ib + size + 1);
     }
 }
 
@@ -447,7 +447,7 @@ fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
 
         loop {
             let probe = bucket.next();
-            assert!(probe.index() != idx_end);
+            debug_assert!(probe.index() != idx_end);
 
             let full_bucket = match probe.peek() {
                 Empty(bucket) => {
-- 
cgit 1.4.1-3-g733a5


From ef874310f2c11671e96fd700aceb9dcbc44db983 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Sun, 6 Mar 2016 12:24:18 +0100
Subject: fix Recover::replace

---
 src/libstd/collections/hash/map.rs | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 6f044958618..8fb703e8fb8 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -1668,8 +1668,13 @@ impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
             InternalEntry::Occupied { mut elem } => {
                 Some(mem::replace(elem.read_mut().0, key))
             }
-            _ => {
-                None
+            other => {
+                if let Some(Vacant(vacant)) = other.into_entry(key) {
+                    vacant.insert(());
+                    None
+                } else {
+                    unreachable!()
+                }
             }
         }
     }
-- 
cgit 1.4.1-3-g733a5


From 6a1ccf8a86a0753cfbec3ad659b4f3ed58a95867 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Thu, 17 Mar 2016 23:11:22 +0100
Subject: fixup Cleaner Recover::replace

---
 src/libstd/collections/hash/map.rs | 26 +++++++++++++++-----------
 1 file changed, 15 insertions(+), 11 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index 8fb703e8fb8..e149a5131fe 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -1313,6 +1313,7 @@ impl<'a, K, V> InternalEntry<K, V, &'a mut RawTable<K, V>> {
         match self {
             InternalEntry::Occupied { elem } => {
                 Some(Occupied(OccupiedEntry {
+                    key: Some(key),
                     elem: elem
                 }))
             }
@@ -1347,6 +1348,7 @@ pub enum Entry<'a, K: 'a, V: 'a> {
 /// A view into a single occupied location in a HashMap.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
+    key: Option<K>,
     elem: FullBucket<K, V, &'a mut RawTable<K, V>>,
 }
 
@@ -1552,6 +1554,12 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> {
     pub fn remove(self) -> V {
         pop_internal(self.elem).1
     }
+    /// Returns a key that was used for search.
+    ///
+    /// The key was retained for further use.
+    fn take_key(&mut self) -> Option<K> {
+        self.key.take()
+    }
 }
 
 impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V> {
@@ -1661,20 +1669,16 @@ impl<K, S, Q: ?Sized> super::Recover<Q> for HashMap<K, (), S>
     }
 
     fn replace(&mut self, key: K) -> Option<K> {
-        let hash = self.make_hash(&key);
         self.reserve(1);
 
-        match search_hashed(&mut self.table, hash, |k| *k == key) {
-            InternalEntry::Occupied { mut elem } => {
-                Some(mem::replace(elem.read_mut().0, key))
+        match self.entry(key) {
+            Occupied(mut occupied) => {
+                let key = occupied.take_key().unwrap();
+                Some(mem::replace(occupied.elem.read_mut().0, key))
             }
-            other => {
-                if let Some(Vacant(vacant)) = other.into_entry(key) {
-                    vacant.insert(());
-                    None
-                } else {
-                    unreachable!()
-                }
+            Vacant(vacant) => {
+                vacant.insert(());
+                None
             }
         }
     }
-- 
cgit 1.4.1-3-g733a5


From c21d97550336481728702ccc30522c7020e820d8 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Mon, 21 Mar 2016 23:53:55 +0100
Subject: f dead code

---
 src/libstd/collections/hash/table.rs | 10 ----------
 1 file changed, 10 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 3c61faae8ea..851a8601c24 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -180,8 +180,6 @@ impl<K, V> RawBucket<K, V> {
     }
 }
 
-// Uncomment dead code when it's needed.
-
 // Buckets hold references to the table.
 impl<K, V, M> FullBucket<K, V, M> {
     /// Borrow a reference to the table.
@@ -203,17 +201,9 @@ impl<K, V, M> EmptyBucket<K, V, M> {
     pub fn table(&self) -> &M {
         &self.table
     }
-    // /// Move out the reference to the table.
-    // pub fn into_table(self) -> M {
-    //     self.table
-    // }
 }
 
 impl<K, V, M> Bucket<K, V, M> {
-    // /// Move out the reference to the table.
-    // pub fn into_table(self) -> M {
-    //     self.table
-    // }
     /// Get the raw index.
     pub fn index(&self) -> usize {
         self.idx
-- 
cgit 1.4.1-3-g733a5


From c9b3cd47e290d7831120b6a95767802265adfd08 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Tue, 22 Mar 2016 09:45:51 +0100
Subject: f Put and DerefMut

---
 src/libstd/collections/hash/table.rs | 40 +++++++++++++++++++++++-------------
 1 file changed, 26 insertions(+), 14 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index 851a8601c24..f3ed2737c87 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -217,20 +217,30 @@ impl<K, V, M> Deref for FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>
     }
 }
 
-impl<K, V, M> DerefMut for FullBucket<K, V, M> where M: DerefMut<Target=RawTable<K, V>> {
-    fn deref_mut(&mut self) -> &mut RawTable<K, V> {
-        &mut self.table
+/// `Put` is implemented for types which provide access to a table and cannot be invalidated
+///  by filling a bucket. A similar implementation for `Take` is possible.
+pub trait Put<K, V> {
+    unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V>;
+}
+
+
+impl<'t, K, V> Put<K, V> for &'t mut RawTable<K, V> {
+    unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
+        *self
     }
 }
 
+impl<K, V, M> Put<K, V> for Bucket<K, V, M> where M: Put<K, V> {
+    unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
+        self.table.borrow_table_mut()
+    }
+}
 
-/// `Put` is implemented for types which provide access to a table and cannot be invalidated
-///  by filling a bucket. A similar implementation for `Take` is possible.
-pub trait Put {}
-impl<K, V> Put for RawTable<K, V> {}
-impl<'t, K, V> Put for &'t mut RawTable<K, V> {}
-impl<K, V, M: Put> Put for Bucket<K, V, M> {}
-impl<K, V, M: Put> Put for FullBucket<K, V, M> {}
+impl<K, V, M> Put<K, V> for FullBucket<K, V, M> where M: Put<K, V> {
+    unsafe fn borrow_table_mut(&mut self) -> &mut RawTable<K, V> {
+        self.table.borrow_table_mut()
+    }
+}
 
 impl<K, V, M: Deref<Target=RawTable<K, V>>> Bucket<K, V, M> {
     pub fn new(table: M, hash: SafeHash) -> Bucket<K, V, M> {
@@ -332,7 +342,7 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> EmptyBucket<K, V, M> {
     }
 }
 
-impl<K, V, M> EmptyBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefMut + Put {
+impl<K, V, M> EmptyBucket<K, V, M> where M: Put<K, V> {
     /// Puts given key and value pair, along with the key's hash,
     /// into this bucket in the hashtable. Note how `self` is 'moved' into
     /// this function, because this slot will no longer be empty when
@@ -346,9 +356,9 @@ impl<K, V, M> EmptyBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + Deref
             *self.raw.hash = hash.inspect();
             ptr::write(self.raw.key, key);
             ptr::write(self.raw.val, value);
-        }
 
-        self.table.size += 1;
+            self.table.borrow_table_mut().size += 1;
+        }
 
         FullBucket { raw: self.raw, idx: self.idx, table: self.table }
     }
@@ -436,7 +446,7 @@ impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> {
     }
 }
 
-impl<K, V, M> FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefMut {
+impl<K, V, M> FullBucket<K, V, M> where M: Put<K, V> {
     pub fn replace(&mut self, h: SafeHash, k: K, v: V) -> (SafeHash, K, V) {
         unsafe {
             let old_hash = ptr::replace(self.raw.hash as *mut SafeHash, h);
@@ -446,7 +456,9 @@ impl<K, V, M> FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefM
             (old_hash, old_key, old_val)
         }
     }
+}
 
+impl<K, V, M> FullBucket<K, V, M> where M: Deref<Target=RawTable<K, V>> + DerefMut {
     /// Gets mutable references to the key and value at a given index.
     pub fn read_mut(&mut self) -> (&mut K, &mut V) {
         unsafe {
-- 
cgit 1.4.1-3-g733a5


From 64adca717fe0f1fac851e9d09972adecf21bf662 Mon Sep 17 00:00:00 2001
From: Piotr Czarnecki <pioczarn@gmail.com>
Date: Tue, 22 Mar 2016 12:52:31 +0100
Subject: f clarification, docs

---
 src/libstd/collections/hash/map.rs   | 5 +++++
 src/libstd/collections/hash/table.rs | 7 +++++--
 2 files changed, 10 insertions(+), 2 deletions(-)

(limited to 'src/libstd')

diff --git a/src/libstd/collections/hash/map.rs b/src/libstd/collections/hash/map.rs
index e149a5131fe..3fb843dc7e1 100644
--- a/src/libstd/collections/hash/map.rs
+++ b/src/libstd/collections/hash/map.rs
@@ -455,6 +455,11 @@ fn robin_hood<'a, K: 'a, V: 'a>(bucket: FullBucketMut<'a, K, V>,
                     let bucket = bucket.put(hash, key, val);
                     // Now that it's stolen, just read the value's pointer
                     // right out of the table! Go back to the *starting point*.
+                    //
+                    // This use of `into_table` is misleading. It turns the
+                    // bucket, which is a FullBucket on top of a
+                    // FullBucketMut, into just one FullBucketMut. The "table"
+                    // refers to the inner FullBucketMut in this context.
                     return bucket.into_table().into_mut_refs().1;
                 },
                 Full(bucket) => bucket
diff --git a/src/libstd/collections/hash/table.rs b/src/libstd/collections/hash/table.rs
index f3ed2737c87..5802a1fd265 100644
--- a/src/libstd/collections/hash/table.rs
+++ b/src/libstd/collections/hash/table.rs
@@ -421,8 +421,9 @@ impl<K, V, M: Deref<Target=RawTable<K, V>>> FullBucket<K, V, M> {
     }
 }
 
-// We don't need a `Take` trait currently. This is why a mutable reference
-// to the table is required.
+// We take a mutable reference to the table instead of accepting anything that
+// implements `DerefMut` to prevent fn `take` from being called on `stash`ed
+// buckets.
 impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> {
     /// Removes this bucket's key and value from the hashtable.
     ///
@@ -446,6 +447,8 @@ impl<'t, K, V> FullBucket<K, V, &'t mut RawTable<K, V>> {
     }
 }
 
+// This use of `Put` is misleading and restrictive, but safe and sufficient for our use cases
+// where `M` is a full bucket or table reference type with mutable access to the table.
 impl<K, V, M> FullBucket<K, V, M> where M: Put<K, V> {
     pub fn replace(&mut self, h: SafeHash, k: K, v: V) -> (SafeHash, K, V) {
         unsafe {
-- 
cgit 1.4.1-3-g733a5