Improvement of shootout-binarytrees.rs

Part of #18085

Instead of using an Enum, we use a struct with Option<&Tree> as leaves. It allow
to limit a lot of allocation.

before:
```
texitoi@vaio:~/dev/benchmarksgame-rs$ time ./bin/binary-trees-orig 20
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1

real	0m3.860s
user	0m11.032s
sys	0m3.572s
```
after:
```
texitoi@vaio:~/dev/benchmarksgame-rs$ time ./bin/binary-trees 20
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1

real	0m2.824s
user	0m9.224s
sys	0m1.428s
```

1 files changed, 21 insertions, 17 deletions

diff --git a/src/test/bench/shootout-binarytrees.rs b/src/test/bench/shootout-binarytrees.rs
index fad5e174644..58e2430b0ff 100644
--- a/src/test/bench/shootout-binarytrees.rs
+++ b/src/test/bench/shootout-binarytrees.rs
@@ -44,26 +44,30 @@ use std::iter::range_step;
 use std::thread::Thread;
 use arena::TypedArena;
 
-enum Tree<'a> {
-    Nil,
-    Node(&'a Tree<'a>, &'a Tree<'a>, int)
+struct Tree<'a> {
+    l: Option<&'a Tree<'a>>,
+    r: Option<&'a Tree<'a>>,
+    i: i32
 }
 
-fn item_check(t: &Tree) -> int {
+fn item_check(t: &Option<&Tree>) -> i32 {
     match *t {
-        Tree::Nil => 0,
-        Tree::Node(l, r, i) => i + item_check(l) - item_check(r)
+        None => 0,
+        Some(&Tree { ref l, ref r, i }) => i + item_check(l) - item_check(r)
     }
 }
 
-fn bottom_up_tree<'r>(arena: &'r TypedArena<Tree<'r>>, item: int, depth: int)
-                  -> &'r Tree<'r> {
+fn bottom_up_tree<'r>(arena: &'r TypedArena<Tree<'r>>, item: i32, depth: i32)
+                  -> Option<&'r Tree<'r>> {
     if depth > 0 {
-        arena.alloc(Tree::Node(bottom_up_tree(arena, 2 * item - 1, depth - 1),
-                               bottom_up_tree(arena, 2 * item, depth - 1),
-                               item))
+        let t: &Tree<'r> = arena.alloc(Tree {
+            l: bottom_up_tree(arena, 2 * item - 1, depth - 1),
+            r: bottom_up_tree(arena, 2 * item, depth - 1),
+            i: item
+        });
+        Some(t)
     } else {
-        arena.alloc(Tree::Nil)
+        None
     }
 }
 
@@ -86,7 +90,7 @@ fn main() {
         let tree = bottom_up_tree(&arena, 0, depth);
 
         println!("stretch tree of depth {}\t check: {}",
-                 depth, item_check(tree));
+                 depth, item_check(&tree));
     }
 
     let long_lived_arena = TypedArena::new();
@@ -94,14 +98,14 @@ fn main() {
 
     let messages = range_step(min_depth, max_depth + 1, 2).map(|depth| {
             use std::num::Int;
-            let iterations = 2i.pow((max_depth - depth + min_depth) as uint);
+            let iterations = 2.pow((max_depth - depth + min_depth) as usize);
             Thread::scoped(move|| {
                 let mut chk = 0;
-                for i in range(1, iterations + 1) {
+                for i in 1 .. iterations + 1 {
                     let arena = TypedArena::new();
                     let a = bottom_up_tree(&arena, i, depth);
                     let b = bottom_up_tree(&arena, -i, depth);
-                    chk += item_check(a) + item_check(b);
+                    chk += item_check(&a) + item_check(&b);
                 }
                 format!("{}\t trees of depth {}\t check: {}",
                         iterations * 2, depth, chk)
@@ -113,5 +117,5 @@ fn main() {
     }
 
     println!("long lived tree of depth {}\t check: {}",
-             max_depth, item_check(long_lived_tree));
+             max_depth, item_check(&long_lived_tree));
 }