auto merge of #17378 : Gankro/rust/hashmap-entry, r=aturon

Deprecates the `find_or_*` family of "internal mutation" methods on `HashMap` in
favour of the "external mutation" Entry API as part of RFC 60. Part of #17320,
but this still needs to be done on the rest of the maps. However they don't have
any internal mutation methods defined, so they can be done without deprecating
or breaking anything. Work on `BTree` is part of the complete rewrite in #17334.

The implemented API deviates from the API described in the RFC in two key places:

* `VacantEntry.set` yields a mutable reference to the inserted element to avoid code
duplication where complex logic needs to be done *regardless* of whether the entry
was vacant or not.
* `OccupiedEntry.into_mut` was added so that it is possible to return a reference
into the map beyond the lifetime of the Entry itself, providing functional parity
to `VacantEntry.set`.

This allows the full find_or_insert functionality to be implemented using this API.
A PR will be submitted to the RFC to amend this.

[breaking-change]

16 files changed, 386 insertions, 50 deletions

diff --git a/src/librustc/driver/config.rs b/src/librustc/driver/config.rs
index 6068926fc9b..daa4a6ad752 100644
--- a/src/librustc/driver/config.rs
+++ b/src/librustc/driver/config.rs
@@ -31,6 +31,7 @@ use syntax::parse;
 use syntax::parse::token::InternedString;
 
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 use getopts::{optopt, optmulti, optflag, optflagopt};
 use getopts;
 use std::cell::{RefCell};
@@ -804,8 +805,11 @@ pub fn build_session_options(matches: &getopts::Matches) -> Options {
             Some(s) => s,
             None => early_error("--extern value must be of the format `foo=bar`"),
         };
-        let locs = externs.find_or_insert(name.to_string(), Vec::new());
-        locs.push(location.to_string());
+
+        match externs.entry(name.to_string()) {
+            Vacant(entry) => { entry.set(vec![location.to_string()]); },
+            Occupied(mut entry) => { entry.get_mut().push(location.to_string()); },
+        }
     }
 
     let crate_name = matches.opt_str("crate-name");
diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index 3919bf6bb94..b812073c3a8 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -36,6 +36,7 @@ use lint::{Context, LintPass, LintArray};
 
 use std::cmp;
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 use std::slice;
 use std::{i8, i16, i32, i64, u8, u16, u32, u64, f32, f64};
 use syntax::abi;
@@ -1203,6 +1204,7 @@ impl UnusedMut {
     fn check_unused_mut_pat(&self, cx: &Context, pats: &[P<ast::Pat>]) {
         // collect all mutable pattern and group their NodeIDs by their Identifier to
         // avoid false warnings in match arms with multiple patterns
+
         let mut mutables = HashMap::new();
         for p in pats.iter() {
             pat_util::pat_bindings(&cx.tcx.def_map, &**p, |mode, id, _, path1| {
@@ -1210,8 +1212,10 @@ impl UnusedMut {
                 match mode {
                     ast::BindByValue(ast::MutMutable) => {
                         if !token::get_ident(ident).get().starts_with("_") {
-                            mutables.insert_or_update_with(ident.name.uint(),
-                                vec!(id), |_, old| { old.push(id); });
+                            match mutables.entry(ident.name.uint()) {
+                                Vacant(entry) => { entry.set(vec![id]); },
+                                Occupied(mut entry) => { entry.get_mut().push(id); },
+                            }
                         }
                     }
                     _ => {
diff --git a/src/librustc/metadata/creader.rs b/src/librustc/metadata/creader.rs
index 342a42fbb26..e2d997a93fe 100644
--- a/src/librustc/metadata/creader.rs
+++ b/src/librustc/metadata/creader.rs
@@ -24,6 +24,7 @@ use plugin::load::PluginMetadata;
 
 use std::rc::Rc;
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 use syntax::ast;
 use syntax::abi;
 use syntax::attr;
@@ -82,7 +83,10 @@ fn dump_crates(cstore: &CStore) {
 fn warn_if_multiple_versions(diag: &SpanHandler, cstore: &CStore) {
     let mut map = HashMap::new();
     cstore.iter_crate_data(|cnum, data| {
-        map.find_or_insert_with(data.name(), |_| Vec::new()).push(cnum);
+        match map.entry(data.name()) {
+            Vacant(entry) => { entry.set(vec![cnum]); },
+            Occupied(mut entry) => { entry.get_mut().push(cnum); },
+        }
     });
 
     for (name, dupes) in map.into_iter() {
diff --git a/src/librustc/metadata/loader.rs b/src/librustc/metadata/loader.rs
index f63705bfb99..dc97b6c0df8 100644
--- a/src/librustc/metadata/loader.rs
+++ b/src/librustc/metadata/loader.rs
@@ -237,6 +237,7 @@ use std::slice;
 use std::string;
 
 use std::collections::{HashMap, HashSet};
+use std::collections::hashmap::{Occupied, Vacant};
 use flate;
 use time;
 
@@ -428,15 +429,18 @@ impl<'a> Context<'a> {
                 return FileDoesntMatch
             };
             info!("lib candidate: {}", path.display());
-            let slot = candidates.find_or_insert_with(hash.to_string(), |_| {
-                (HashSet::new(), HashSet::new())
-            });
+
+            let slot = match candidates.entry(hash.to_string()) {
+                Occupied(entry) => entry.into_mut(),
+                Vacant(entry) => entry.set((HashSet::new(), HashSet::new())),
+            };
             let (ref mut rlibs, ref mut dylibs) = *slot;
             if rlib {
                 rlibs.insert(fs::realpath(path).unwrap());
             } else {
                 dylibs.insert(fs::realpath(path).unwrap());
             }
+
             FileMatches
         });
 
diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs
index 8c7c8eda2d2..98d2cefac0f 100644
--- a/src/librustc/middle/const_eval.rs
+++ b/src/librustc/middle/const_eval.rs
@@ -28,6 +28,7 @@ use syntax::visit;
 use syntax::{ast, ast_map, ast_util};
 
 use std::rc::Rc;
+use std::collections::hashmap::Vacant;
 
 //
 // This pass classifies expressions by their constant-ness.
@@ -321,7 +322,10 @@ pub fn const_expr_to_pat(tcx: &ty::ctxt, expr: &Expr) -> P<Pat> {
 
         ExprCall(ref callee, ref args) => {
             let def = tcx.def_map.borrow().get_copy(&callee.id);
-            tcx.def_map.borrow_mut().find_or_insert(expr.id, def);
+            match tcx.def_map.borrow_mut().entry(expr.id) {
+              Vacant(entry) => { entry.set(def); }
+              _ => {}
+            };
             let path = match def {
                 def::DefStruct(def_id) => def_to_path(tcx, def_id),
                 def::DefVariant(_, variant_did, _) => def_to_path(tcx, variant_did),
diff --git a/src/librustc/middle/resolve.rs b/src/librustc/middle/resolve.rs
index 7d88ba57ad7..2c18c450eb6 100644
--- a/src/librustc/middle/resolve.rs
+++ b/src/librustc/middle/resolve.rs
@@ -59,6 +59,7 @@ use syntax::visit;
 use syntax::visit::Visitor;
 
 use std::collections::{HashMap, HashSet};
+use std::collections::hashmap::{Occupied, Vacant};
 use std::cell::{Cell, RefCell};
 use std::mem::replace;
 use std::rc::{Rc, Weak};
@@ -2815,10 +2816,13 @@ impl<'a> Resolver<'a> {
         let is_public = import_directive.is_public;
 
         let mut import_resolutions = module_.import_resolutions.borrow_mut();
-        let dest_import_resolution = import_resolutions.find_or_insert_with(name, |_| {
-            // Create a new import resolution from this child.
-            ImportResolution::new(id, is_public)
-        });
+        let dest_import_resolution = match import_resolutions.entry(name) {
+            Occupied(entry) => entry.into_mut(),
+            Vacant(entry) => {
+                // Create a new import resolution from this child.
+                entry.set(ImportResolution::new(id, is_public))
+            }
+        };
 
         debug!("(resolving glob import) writing resolution `{}` in `{}` \
                to `{}`",
@@ -6026,19 +6030,21 @@ impl<'a> Resolver<'a> {
         assert!(match lp {LastImport{..} => false, _ => true},
                 "Import should only be used for `use` directives");
         self.last_private.insert(node_id, lp);
-        self.def_map.borrow_mut().insert_or_update_with(node_id, def, |_, old_value| {
+
+        match self.def_map.borrow_mut().entry(node_id) {
             // Resolve appears to "resolve" the same ID multiple
             // times, so here is a sanity check it at least comes to
             // the same conclusion! - nmatsakis
-            if def != *old_value {
+            Occupied(entry) => if def != *entry.get() {
                 self.session
                     .bug(format!("node_id {:?} resolved first to {:?} and \
                                   then {:?}",
                                  node_id,
-                                 *old_value,
+                                 *entry.get(),
                                  def).as_slice());
-            }
-        });
+            },
+            Vacant(entry) => { entry.set(def); },
+        }
     }
 
     fn enforce_default_binding_mode(&mut self,
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index f1499cb9166..3014eb35e22 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -48,6 +48,7 @@ use std::mem;
 use std::ops;
 use std::rc::Rc;
 use std::collections::{HashMap, HashSet};
+use std::collections::hashmap::{Occupied, Vacant};
 use arena::TypedArena;
 use syntax::abi;
 use syntax::ast::{CrateNum, DefId, FnStyle, Ident, ItemTrait, LOCAL_CRATE};
@@ -4566,9 +4567,10 @@ pub fn lookup_field_type(tcx: &ctxt,
         node_id_to_type(tcx, id.node)
     } else {
         let mut tcache = tcx.tcache.borrow_mut();
-        let pty = tcache.find_or_insert_with(id, |_| {
-            csearch::get_field_type(tcx, struct_id, id)
-        });
+        let pty = match tcache.entry(id) {
+            Occupied(entry) => entry.into_mut(),
+            Vacant(entry) => entry.set(csearch::get_field_type(tcx, struct_id, id)),
+        };
         pty.ty
     };
     t.subst(tcx, substs)
diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs
index 821cf629d83..8d6369bdbe1 100644
--- a/src/librustc/middle/typeck/check/mod.rs
+++ b/src/librustc/middle/typeck/check/mod.rs
@@ -121,6 +121,7 @@ use util::nodemap::{DefIdMap, FnvHashMap, NodeMap};
 
 use std::cell::{Cell, RefCell};
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 use std::mem::replace;
 use std::rc::Rc;
 use syntax::abi;
@@ -1991,11 +1992,14 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
          */
 
         let mut region_obligations = self.inh.region_obligations.borrow_mut();
-        let v = region_obligations.find_or_insert_with(self.body_id,
-                                                       |_| Vec::new());
-        v.push(RegionObligation { sub_region: r,
+        let region_obligation = RegionObligation { sub_region: r,
                                   sup_type: ty,
-                                  origin: origin });
+                                  origin: origin };
+
+        match region_obligations.entry(self.body_id) {
+            Vacant(entry) => { entry.set(vec![region_obligation]); },
+            Occupied(mut entry) => { entry.get_mut().push(region_obligation); },
+        }
     }
 
     pub fn add_obligations_for_parameters(&self,
diff --git a/src/librustc/middle/typeck/check/regionmanip.rs b/src/librustc/middle/typeck/check/regionmanip.rs
index 8bcbe4b7929..db9877698a3 100644
--- a/src/librustc/middle/typeck/check/regionmanip.rs
+++ b/src/librustc/middle/typeck/check/regionmanip.rs
@@ -18,6 +18,7 @@ use middle::ty_fold::TypeFolder;
 use syntax::ast;
 
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 use util::ppaux::Repr;
 
 // Helper functions related to manipulating region types.
@@ -35,7 +36,10 @@ pub fn replace_late_bound_regions_in_fn_sig(
             debug!("region r={}", r.to_string());
             match r {
                 ty::ReLateBound(s, br) if s == fn_sig.binder_id => {
-                    *map.find_or_insert_with(br, |_| mapf(br))
+                    * match map.entry(br) {
+                        Vacant(entry) => entry.set(mapf(br)),
+                        Occupied(entry) => entry.into_mut(),
+                    }
                 }
                 _ => r
             }
diff --git a/src/librustdoc/html/render.rs b/src/librustdoc/html/render.rs
index fe7b1be3eca..b2cef48af4c 100644
--- a/src/librustdoc/html/render.rs
+++ b/src/librustdoc/html/render.rs
@@ -34,6 +34,7 @@
 //! both occur before the crate is rendered.
 
 use std::collections::{HashMap, HashSet};
+use std::collections::hashmap::{Occupied, Vacant};
 use std::fmt;
 use std::io::fs::PathExtensions;
 use std::io::{fs, File, BufferedWriter, MemWriter, BufferedReader};
@@ -802,9 +803,10 @@ impl DocFolder for Cache {
             clean::ImplItem(ref i) => {
                 match i.trait_ {
                     Some(clean::ResolvedPath{ did, .. }) => {
-                        let v = self.implementors.find_or_insert_with(did, |_| {
-                            Vec::new()
-                        });
+                        let v = match self.implementors.entry(did) {
+                            Vacant(entry) => entry.set(Vec::with_capacity(1)),
+                            Occupied(entry) => entry.into_mut(),
+                        };
                         v.push(Implementor {
                             def_id: item.def_id,
                             generics: i.generics.clone(),
@@ -999,9 +1001,10 @@ impl DocFolder for Cache {
 
                         match did {
                             Some(did) => {
-                                let v = self.impls.find_or_insert_with(did, |_| {
-                                    Vec::new()
-                                });
+                                let v = match self.impls.entry(did) {
+                                    Vacant(entry) => entry.set(Vec::with_capacity(1)),
+                                    Occupied(entry) => entry.into_mut(),
+                                };
                                 v.push(Impl {
                                     impl_: i,
                                     dox: dox,
@@ -2143,7 +2146,10 @@ fn build_sidebar(m: &clean::Module) -> HashMap<String, Vec<String>> {
             None => continue,
             Some(ref s) => s.to_string(),
         };
-        let v = map.find_or_insert_with(short.to_string(), |_| Vec::new());
+        let v = match map.entry(short.to_string()) {
+            Vacant(entry) => entry.set(Vec::with_capacity(1)),
+            Occupied(entry) => entry.into_mut(),
+        };
         v.push(myname);
     }
 
diff --git a/src/librustdoc/lib.rs b/src/librustdoc/lib.rs
index f8eb40a3894..237a88ded71 100644
--- a/src/librustdoc/lib.rs
+++ b/src/librustdoc/lib.rs
@@ -31,6 +31,7 @@ extern crate time;
 use std::io;
 use std::io::{File, MemWriter};
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 use serialize::{json, Decodable, Encodable};
 use externalfiles::ExternalHtml;
 
@@ -340,7 +341,10 @@ fn parse_externs(matches: &getopts::Matches) -> Result<core::Externs, String> {
                 return Err("--extern value must be of the format `foo=bar`".to_string());
             }
         };
-        let locs = externs.find_or_insert(name.to_string(), Vec::new());
+        let locs = match externs.entry(name.to_string()) {
+            Vacant(entry) => entry.set(Vec::with_capacity(1)),
+            Occupied(entry) => entry.into_mut(),
+        };
         locs.push(location.to_string());
     }
     Ok(externs)
diff --git a/src/libstd/collections/hashmap/map.rs b/src/libstd/collections/hashmap/map.rs
index b0604e13163..6b9c76e1568 100644
--- a/src/libstd/collections/hashmap/map.rs
+++ b/src/libstd/collections/hashmap/map.rs
@@ -20,16 +20,19 @@ use hash::{Hash, Hasher, RandomSipHasher};
 use iter::{Iterator, FromIterator, Extendable};
 use iter;
 use mem::replace;
+use mem;
 use num;
 use ops::{Deref, DerefMut};
 use option::{Some, None, Option};
 use result::{Ok, Err};
 use ops::Index;
+use core::result::Result;
 
 use super::table;
 use super::table::{
     Bucket,
     Empty,
+    EmptyBucket,
     Full,
     FullBucket,
     FullBucketImm,
@@ -328,11 +331,11 @@ fn search_hashed<K: Eq, V, M: Deref<RawTable<K, V>>>(table: M, hash: &SafeHash,
     search_hashed_generic(table, hash, |k_| *k == *k_)
 }
 
-fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> V {
-    let (empty, _k, retval) = starting_bucket.take();
+fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> (K, V) {
+    let (empty, retkey, retval) = starting_bucket.take();
     let mut gap = match empty.gap_peek() {
         Some(b) => b,
-        None => return retval
+        None => return (retkey, retval)
     };
 
     while gap.full().distance() != 0 {
@@ -343,7 +346,7 @@ fn pop_internal<K, V>(starting_bucket: FullBucketMut<K, V>) -> V {
     }
 
     // Now we've done all our shifting. Return the value we grabbed earlier.
-    return retval;
+    return (retkey, retval);
 }
 
 /// Perform robin hood bucket stealing at the given `bucket`. You must
@@ -567,7 +570,8 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V, H>
         self.make_some_room(potential_new_size);
 
         self.search_mut(k).map(|bucket| {
-            pop_internal(bucket)
+            let (_k, val) = pop_internal(bucket);
+            val
         })
     }
 }
@@ -852,12 +856,28 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         self.insert_hashed_nocheck(hash, k, v)
     }
 
+    /// Deprecated: use `entry` as follows instead:
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    /// use std::collections::hashmap::{Occupied, Vacant};
+    ///
+    /// let mut map = HashMap::new();
+    ///
+    /// let result = match map.entry("a") {
+    ///     Vacant(entry) => entry.set(1i),
+    ///     Occupied(entry) => entry.into_mut(),
+    /// };
+    /// assert_eq!(*result, 1);
+    /// ```
+    ///
     /// Return the value corresponding to the key in the map, or insert
     /// and return the value if it doesn't exist.
     ///
     /// # Example
     ///
     /// ```
+    /// #![allow(deprecated)]
     /// use std::collections::HashMap;
     /// let mut map = HashMap::new();
     ///
@@ -867,16 +887,34 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// // Find the existing key
     /// assert_eq!(*map.find_or_insert("a", -2), 1);
     /// ```
+    #[deprecated = "use entry instead"]
+    #[allow(deprecated)]
     pub fn find_or_insert(&mut self, k: K, v: V) -> &mut V {
         self.find_with_or_insert_with(k, v, |_k, _v, _a| (), |_k, a| a)
     }
 
+    /// Deprecated: use `entry` as follows instead:
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    /// use std::collections::hashmap::{Occupied, Vacant};
+    ///
+    /// let mut map = HashMap::new();
+    ///
+    /// let result = match map.entry("a") {
+    ///     Vacant(entry) => entry.set(1i),
+    ///     Occupied(entry) => entry.into_mut(),
+    /// };
+    /// assert_eq!(*result, 1);
+    /// ```
+    ///
     /// Return the value corresponding to the key in the map, or create,
     /// insert, and return a new value if it doesn't exist.
     ///
     /// # Example
     ///
     /// ```
+    /// #![allow(deprecated)]
     /// use std::collections::HashMap;
     /// let mut map = HashMap::new();
     ///
@@ -886,11 +924,31 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// // Find the existing key
     /// assert_eq!(*map.find_or_insert_with(2, |&key| key as uint), 10);
     /// ```
+    #[deprecated = "use entry instead"]
+    #[allow(deprecated)]
     pub fn find_or_insert_with<'a>(&'a mut self, k: K, f: |&K| -> V)
                                -> &'a mut V {
         self.find_with_or_insert_with(k, (), |_k, _v, _a| (), |k, _a| f(k))
     }
 
+    /// Deprecated: use `entry` as follows instead:
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    /// use std::collections::hashmap::{Occupied, Vacant};
+    ///
+    /// let mut map = HashMap::new();
+    ///
+    /// let result = match map.entry("a") {
+    ///     Vacant(entry) => entry.set(1u),
+    ///     Occupied(mut entry) => {
+    ///         *entry.get_mut() += 1;
+    ///         entry.into_mut()
+    ///     }
+    /// };
+    /// assert_eq!(*result, 1);
+    /// ```
+    ///
     /// Insert a key-value pair into the map if the key is not already present.
     /// Otherwise, modify the existing value for the key.
     /// Returns the new or modified value for the key.
@@ -898,6 +956,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// # Example
     ///
     /// ```
+    /// #![allow(deprecated)]
     /// use std::collections::HashMap;
     /// let mut map = HashMap::new();
     ///
@@ -908,6 +967,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert_eq!(*map.insert_or_update_with("a", 9, |_key, val| *val = 7), 7);
     /// assert_eq!(map["a"], 7);
     /// ```
+    #[deprecated = "use entry instead"]
     pub fn insert_or_update_with<'a>(
                                  &'a mut self,
                                  k: K,
@@ -921,6 +981,24 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         self.insert_or_replace_with(hash, k, v, |kref, vref, _v| f(kref, vref))
     }
 
+    /// Deprecated: use `entry` as follows instead:
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    /// use std::collections::hashmap::{Occupied, Vacant};
+    ///
+    /// let mut map = HashMap::new();
+    ///
+    /// let result = match map.entry("a") {
+    ///     Vacant(entry) => entry.set(1u),
+    ///     Occupied(mut entry) => {
+    ///         *entry.get_mut() += 1;
+    ///         entry.into_mut()
+    ///     }
+    /// };
+    /// assert_eq!(*result, 1);
+    /// ```
+    ///
     /// Modify and return the value corresponding to the key in the map, or
     /// insert and return a new value if it doesn't exist.
     ///
@@ -934,6 +1012,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// # Example
     ///
     /// ```
+    /// #![allow(deprecated)]
     /// use std::collections::HashMap;
     ///
     /// // map some strings to vectors of strings
@@ -965,6 +1044,7 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// assert_eq!(map["b key"], vec!["new value"]);
     /// assert_eq!(map["z key"], vec!["new value", "value"]);
     /// ```
+    #[deprecated = "use entry instead"]
     pub fn find_with_or_insert_with<'a, A>(&'a mut self,
                                            k: K,
                                            a: A,
@@ -1124,7 +1204,8 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
 
         match self.search_equiv_mut(k) {
             Some(bucket) => {
-                Some(pop_internal(bucket))
+                let (_k, val) = pop_internal(bucket);
+                Some(val)
             }
             _ => None
         }
@@ -1254,6 +1335,68 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
             inner: self.table.into_iter().map(|(_, k, v)| (k, v))
         }
     }
+
+    /// Gets the given key's corresponding entry in the map for in-place manipulation
+    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V> {
+        // Gotta resize now, and we don't know which direction, so try both?
+        let size = self.table.size();
+        self.make_some_room(size + 1);
+        if size > 0 {
+            self.make_some_room(size - 1);
+        }
+
+        let hash = self.make_hash(&key);
+        search_entry_hashed(&mut self.table, hash, key)
+    }
+}
+
+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
+        };
+
+        if bucket.hash() == hash {
+            let is_eq = {
+                let (bucket_k, _) = bucket.read();
+                k == *bucket_k
+            };
+
+            if is_eq {
+                return Occupied(OccupiedEntry{
+                    elem: bucket,
+                });
+            }
+        }
+
+        let robin_ib = bucket.index() as int - bucket.distance() as int;
+
+        if (ib as int) < 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 uint),
+            });
+        }
+
+        probe = bucket.next();
+        assert!(probe.index() != ib + size + 1);
+    }
 }
 
 impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
@@ -1354,6 +1497,35 @@ pub struct MoveEntries<K, V> {
     inner: iter::Map<'static, (SafeHash, K, V), (K, V), table::MoveEntries<K, V>>
 }
 
+/// A view into a single occupied location in a HashMap
+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
+pub struct VacantEntry<'a, K:'a, V:'a> {
+    hash: SafeHash,
+    key: K,
+    elem: VacantEntryState<K,V, &'a mut RawTable<K, V>>,
+}
+
+/// A view into a single location in a map, which may be vacant or occupied
+pub enum Entry<'a, K:'a, V:'a> {
+    /// An occupied Entry
+    Occupied(OccupiedEntry<'a, K, V>),
+    /// A vacant Entry
+    Vacant(VacantEntry<'a, K, V>),
+}
+
+/// Possible states of a VacantEntry
+enum VacantEntryState<K, V, M> {
+    /// The index is occupied, but the key to insert has precedence,
+    /// and will kick the current one out on insertion
+    NeqElem(FullBucket<K, V, M>, uint),
+    /// The index is genuinely vacant
+    NoElem(EmptyBucket<K, V, M>),
+}
+
 impl<'a, K, V> Iterator<(&'a K, &'a V)> for Entries<'a, K, V> {
     #[inline]
     fn next(&mut self) -> Option<(&'a K, &'a V)> {
@@ -1387,6 +1559,57 @@ impl<K, V> Iterator<(K, V)> for MoveEntries<K, V> {
     }
 }
 
+impl<'a, K, V> OccupiedEntry<'a, K, V> {
+    /// Gets a reference to the value in the entry
+    pub fn get(&self) -> &V {
+        let (_, v) = self.elem.read();
+        v
+    }
+
+    /// Gets a mutable reference to the value in the entry
+    pub fn get_mut(&mut self) -> &mut V {
+        let (_, v) = self.elem.read_mut();
+        v
+    }
+
+    /// Converts the OccupiedEntry into a mutable reference to the value in the entry
+    /// with a lifetime bound to the map itself
+    pub fn into_mut(self) -> &'a mut V {
+        let (_, v) = self.elem.into_mut_refs();
+        v
+    }
+
+    /// Sets the value of the entry, and returns the entry's old value
+    pub fn set(&mut self, mut value: V) -> V {
+        let old_value = self.get_mut();
+        mem::swap(&mut value, old_value);
+        value
+    }
+
+    /// Takes the value out of the entry, and returns it
+    pub fn take(self) -> V {
+        let (_, _, v) = self.elem.take();
+        v
+    }
+}
+
+impl<'a, K, V> VacantEntry<'a, K, V> {
+    /// Sets the value of the entry with the VacantEntry's key,
+    /// and returns a mutable reference to it
+    pub fn set(self, value: V) -> &'a mut V {
+        match self.elem {
+            NeqElem(bucket, ib) => {
+                robin_hood(bucket, ib, self.hash, self.key, value)
+            }
+            NoElem(bucket) => {
+                let full = bucket.put(self.hash, self.key, value);
+                let (_, v) = full.into_mut_refs();
+                v
+            }
+        }
+    }
+}
+
 /// HashMap keys iterator
 pub type Keys<'a, K, V> =
     iter::Map<'static, (&'a K, &'a V), &'a K, Entries<'a, K, V>>;
@@ -1417,6 +1640,7 @@ mod test_map {
     use prelude::*;
 
     use super::HashMap;
+    use super::{Occupied, Vacant};
     use cmp::Equiv;
     use hash;
     use iter::{Iterator,range_inclusive,range_step_inclusive};
@@ -2027,4 +2251,56 @@ mod test_map {
 
         map[4];
     }
+
+    #[test]
+    fn test_entry(){
+        let xs = [(1i, 10i), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)];
+
+        let mut map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
+
+        // Existing key (insert)
+        match map.entry(1) {
+            Vacant(_) => unreachable!(),
+            Occupied(mut view) => {
+                assert_eq!(view.get(), &10);
+                assert_eq!(view.set(100), 10);
+            }
+        }
+        assert_eq!(map.find(&1).unwrap(), &100);
+        assert_eq!(map.len(), 6);
+
+
+        // Existing key (update)
+        match map.entry(2) {
+            Vacant(_) => unreachable!(),
+            Occupied(mut view) => {
+                let v = view.get_mut();
+                let new_v = (*v) * 10;
+                *v = new_v;
+            }
+        }
+        assert_eq!(map.find(&2).unwrap(), &200);
+        assert_eq!(map.len(), 6);
+
+        // Existing key (take)
+        match map.entry(3) {
+            Vacant(_) => unreachable!(),
+            Occupied(view) => {
+                assert_eq!(view.take(), 30);
+            }
+        }
+        assert_eq!(map.find(&3), None);
+        assert_eq!(map.len(), 5);
+
+
+        // Inexistent key (insert)
+        match map.entry(10) {
+            Occupied(_) => unreachable!(),
+            Vacant(view) => {
+                assert_eq!(*view.set(1000), 1000);
+            }
+        }
+        assert_eq!(map.find(&10).unwrap(), &1000);
+        assert_eq!(map.len(), 6);
+    }
 }
diff --git a/src/libstd/collections/hashmap/mod.rs b/src/libstd/collections/hashmap/mod.rs
index b5612ce0f07..6508d4609f1 100644
--- a/src/libstd/collections/hashmap/mod.rs
+++ b/src/libstd/collections/hashmap/mod.rs
@@ -14,6 +14,11 @@ pub use self::map::HashMap;
 pub use self::map::Entries;
 pub use self::map::MutEntries;
 pub use self::map::MoveEntries;
+pub use self::map::Entry;
+pub use self::map::Occupied;
+pub use self::map::Vacant;
+pub use self::map::OccupiedEntry;
+pub use self::map::VacantEntry;
 pub use self::map::Keys;
 pub use self::map::Values;
 pub use self::map::INITIAL_CAPACITY;
diff --git a/src/libsyntax/ext/mtwt.rs b/src/libsyntax/ext/mtwt.rs
index 2c94db52967..6fe4f5b324c 100644
--- a/src/libsyntax/ext/mtwt.rs
+++ b/src/libsyntax/ext/mtwt.rs
@@ -20,6 +20,7 @@ use ast::{Ident, Mrk, Name, SyntaxContext};
 use std::cell::RefCell;
 use std::rc::Rc;
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 
 /// The SCTable contains a table of SyntaxContext_'s. It
 /// represents a flattened tree structure, to avoid having
@@ -65,10 +66,10 @@ pub fn apply_mark(m: Mrk, ctxt: SyntaxContext) -> SyntaxContext {
 /// Extend a syntax context with a given mark and sctable (explicit memoization)
 fn apply_mark_internal(m: Mrk, ctxt: SyntaxContext, table: &SCTable) -> SyntaxContext {
     let key = (ctxt, m);
-    let new_ctxt = |_: &(SyntaxContext, Mrk)|
-                   idx_push(&mut *table.table.borrow_mut(), Mark(m, ctxt));
-
-    *table.mark_memo.borrow_mut().find_or_insert_with(key, new_ctxt)
+    * match table.mark_memo.borrow_mut().entry(key) {
+        Vacant(entry) => entry.set(idx_push(&mut *table.table.borrow_mut(), Mark(m, ctxt))),
+        Occupied(entry) => entry.into_mut(),
+    }
 }
 
 /// Extend a syntax context with a given rename
@@ -83,10 +84,11 @@ fn apply_rename_internal(id: Ident,
                        ctxt: SyntaxContext,
                        table: &SCTable) -> SyntaxContext {
     let key = (ctxt, id, to);
-    let new_ctxt = |_: &(SyntaxContext, Ident, Name)|
-                   idx_push(&mut *table.table.borrow_mut(), Rename(id, to, ctxt));
 
-    *table.rename_memo.borrow_mut().find_or_insert_with(key, new_ctxt)
+    * match table.rename_memo.borrow_mut().entry(key) {
+        Vacant(entry) => entry.set(idx_push(&mut *table.table.borrow_mut(), Rename(id, to, ctxt))),
+        Occupied(entry) => entry.into_mut(),
+    }
 }
 
 /// Apply a list of renamings to a context
diff --git a/src/libtest/stats.rs b/src/libtest/stats.rs
index 854bf7f5a42..72c61f3afc7 100644
--- a/src/libtest/stats.rs
+++ b/src/libtest/stats.rs
@@ -11,6 +11,7 @@
 #![allow(missing_doc)]
 
 use std::collections::hashmap;
+use std::collections::hashmap::{Occupied, Vacant};
 use std::fmt::Show;
 use std::hash::Hash;
 use std::io;
@@ -442,7 +443,10 @@ pub fn write_boxplot<T: Float + Show + FromPrimitive>(
 pub fn freq_count<T: Iterator<U>, U: Eq+Hash>(mut iter: T) -> hashmap::HashMap<U, uint> {
     let mut map: hashmap::HashMap<U,uint> = hashmap::HashMap::new();
     for elem in iter {
-        map.insert_or_update_with(elem, 1, |_, count| *count += 1);
+        match map.entry(elem) {
+            Occupied(mut entry) => { *entry.get_mut() += 1; },
+            Vacant(entry) => { entry.set(1); },
+        }
     }
     map
 }
diff --git a/src/liburl/lib.rs b/src/liburl/lib.rs
index b5ffdef22e9..0b227b68ca8 100644
--- a/src/liburl/lib.rs
+++ b/src/liburl/lib.rs
@@ -23,6 +23,7 @@
 #![feature(default_type_params)]
 
 use std::collections::HashMap;
+use std::collections::hashmap::{Occupied, Vacant};
 use std::fmt;
 use std::from_str::FromStr;
 use std::hash;
@@ -342,8 +343,10 @@ pub fn decode_form_urlencoded(s: &[u8])
                         key: String,
                         value: String) {
         if key.len() > 0 && value.len() > 0 {
-            let values = map.find_or_insert_with(key, |_| vec!());
-            values.push(value);
+            match map.entry(key) {
+                Vacant(entry) => { entry.set(vec![value]); },
+                Occupied(mut entry) => { entry.get_mut().push(value); },
+            }
         }
     }