auto merge of #15540 : Gankro/rust/master, r=huonw

Removing recursion from TreeMap implementation, because we don't have TCO. No need to add ```O(logn)``` extra stack frames to search in a tree.

I find it curious that ```find_mut``` and ```find``` basically duplicated the same logic, but in different ways (iterative vs recursive), possibly to maneuvre around mutability rules, but that's a more fundamental issue to deal with elsewhere.

Thanks to acrichto for the magic trick to appease borrowck (another issue to deal with elsewhere).

1 files changed, 15 insertions, 17 deletions

diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs
index c1d782991b4..4a7fcd6786f 100644
--- a/src/libcollections/treemap.rs
+++ b/src/libcollections/treemap.rs
@@ -89,7 +89,7 @@ impl<K: Ord, V> Mutable for TreeMap<K, V> {
 
 impl<K: Ord, V> Map<K, V> for TreeMap<K, V> {
     fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
-        let mut current: &'a Option<Box<TreeNode<K, V>>> = &self.root;
+        let mut current = &self.root;
         loop {
             match *current {
               Some(ref r) => {
@@ -108,7 +108,20 @@ impl<K: Ord, V> Map<K, V> for TreeMap<K, V> {
 impl<K: Ord, V> MutableMap<K, V> for TreeMap<K, V> {
     #[inline]
     fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
-        find_mut(&mut self.root, key)
+        let mut current = &mut self.root;
+        loop {
+            let temp = current; // hack to appease borrowck
+            match *temp {
+              Some(ref mut r) => {
+                match key.cmp(&r.key) {
+                  Less => current = &mut r.left,
+                  Greater => current = &mut r.right,
+                  Equal => return Some(&mut r.value)
+                }
+              }
+              None => return None
+            }
+        }
     }
 
     fn swap(&mut self, key: K, value: V) -> Option<V> {
@@ -840,21 +853,6 @@ fn split<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
     }
 }
 
-fn find_mut<'r, K: Ord, V>(node: &'r mut Option<Box<TreeNode<K, V>>>,
-                                key: &K)
-                             -> Option<&'r mut V> {
-    match *node {
-      Some(ref mut x) => {
-        match key.cmp(&x.key) {
-          Less => find_mut(&mut x.left, key),
-          Greater => find_mut(&mut x.right, key),
-          Equal => Some(&mut x.value),
-        }
-      }
-      None => None
-    }
-}
-
 fn insert<K: Ord, V>(node: &mut Option<Box<TreeNode<K, V>>>,
                           key: K, value: V) -> Option<V> {
     match *node {