treemap: cut down on swap_unwrap in remove

Performance before:

    std::treemap::TreeMap
                   sequential_ints 0.083971 s
                       random_ints 0.095861 s
                       delete_ints 0.083931 s
                sequential_strings 0.278272 s
                    random_strings 0.240286 s
                    delete_strings 0.173581 s

Performance after:

    std::treemap::TreeMap
                   sequential_ints 0.083297 s
                       random_ints 0.097644 s
                       delete_ints 0.052602 s
                sequential_strings 0.287326 s
                    random_strings 0.242372 s
                    delete_strings 0.142269 s

1 files changed, 21 insertions, 15 deletions

diff --git a/src/libstd/treemap.rs b/src/libstd/treemap.rs
index c100d8ca85d..d3583828f9a 100644
--- a/src/libstd/treemap.rs
+++ b/src/libstd/treemap.rs
@@ -626,7 +626,7 @@ fn insert<K: Ord, V>(node: &mut Option<~TreeNode<K, V>>, key: K,
 }
 
 fn remove<K: Ord, V>(node: &mut Option<~TreeNode<K, V>>, key: &K) -> bool {
-    fn heir_swap<K: Ord, V>(node: &mut TreeNode<K, V>,
+    fn heir_swap<K: Ord, V>(node: &mut ~TreeNode<K, V>,
                             child: &mut Option<~TreeNode<K, V>>) {
         // *could* be done without recursion, but it won't borrow check
         do child.mutate |mut child| {
@@ -640,15 +640,15 @@ fn remove<K: Ord, V>(node: &mut Option<~TreeNode<K, V>>, key: &K) -> bool {
         }
     }
 
-    if node.is_none() {
+    match *node {
+      None => {
         return false // bottom of tree
-    } else {
-        let mut save = node.swap_unwrap();
-
-        let removed = if save.key < *key {
-            remove(&mut save.right, key)
+      }
+      Some(ref mut save) => {
+        let (removed, this) = if save.key < *key {
+            (remove(&mut save.right, key), false)
         } else if *key < save.key {
-            remove(&mut save.left, key)
+            (remove(&mut save.left, key), false)
         } else {
             if save.left.is_some() {
                 if save.right.is_some() {
@@ -662,16 +662,22 @@ fn remove<K: Ord, V>(node: &mut Option<~TreeNode<K, V>>, key: &K) -> bool {
                     save.left = Some(left);
                     remove(&mut save.left, key);
                 } else {
-                    save = save.left.swap_unwrap();
+                    *save = save.left.swap_unwrap();
                 }
+                (true, false)
             } else if save.right.is_some() {
-                save = save.right.swap_unwrap();
+                *save = save.right.swap_unwrap();
+                (true, false)
             } else {
-                return true // leaf
+                (true, true)
             }
-            true
         };
 
+        if this {
+            *node = None;
+            return true;
+        }
+
         let left_level = save.left.map_default(0, |x| x.level);
         let right_level = save.right.map_default(0, |x| x.level);
 
@@ -683,7 +689,7 @@ fn remove<K: Ord, V>(node: &mut Option<~TreeNode<K, V>>, key: &K) -> bool {
                 do save.right.mutate |mut x| { x.level = save.level; x }
             }
 
-            skew(&mut save);
+            skew(save);
 
             match save.right {
               Some(ref mut right) => {
@@ -696,15 +702,15 @@ fn remove<K: Ord, V>(node: &mut Option<~TreeNode<K, V>>, key: &K) -> bool {
               None => ()
             }
 
-            split(&mut save);
+            split(save);
             match save.right {
               Some(ref mut x) => { split(x) },
               None => ()
             }
         }
 
-        *node = Some(save);
         removed
+      }
     }
 }