1 files changed, 102 insertions, 0 deletions
diff --git a/src/main/java/org/linaro/benchmarks/benchmarksgame/binarytrees.java b/src/main/java/org/linaro/benchmarks/benchmarksgame/binarytrees.java
new file mode 100644
index 0000000..8ce6f1c
--- /dev/null
+++ b/src/main/java/org/linaro/benchmarks/benchmarksgame/binarytrees.java
@@ -0,0 +1,102 @@
+/*
+ * This benchmark has been ported from "The Computer Language Benchmarks Game" suite and slightly
+ * modified to fit the benchmarking framework.
+ *
+ * The original file is `binarytrees/binarytrees.java-2.java` from the archive
+ * available at
+ * http://benchmarksgame.alioth.debian.org/download/benchmarksgame-sourcecode.zip.
+ * See LICENSE file in the same folder (BSD 3-clause)
+ *
+ * The Computer Language Benchmarks Game
+ * http://benchmarksgame.alioth.debian.org/
+ *
+ * contributed by Jarkko Miettinen
+ */
+
+/*
+ * Description:     Allocate and deallocate many many binary trees.
+ * Main Focus:      TODO
+ *
+ */
+
+package org.linaro.benchmarks.benchmarksgame;
+
+import java.util.ArrayList;
+import java.util.Date;
+import java.util.SortedSet;
+import java.util.TreeSet;
+import org.openjdk.jmh.annotations.*;
+import java.util.concurrent.TimeUnit;
+
+@BenchmarkMode(Mode.AverageTime)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Benchmark)
+
+// CHECKSTYLE.OFF: .*
+public class binarytrees {
+
+   private static final int PREDEFINED_DEPTH = 10;
+   private final static int minDepth = 4;
+
+   public int old_main(){
+      int n = 0;
+      int maxDepth = (minDepth + 2 > PREDEFINED_DEPTH) ? minDepth + 2 : PREDEFINED_DEPTH;
+      int stretchDepth = maxDepth + 1;
+
+      int check = (TreeNode.bottomUpTree(0,stretchDepth)).itemCheck();
+
+      TreeNode longLivedTree = TreeNode.bottomUpTree(0,maxDepth);
+
+      for (int depth=minDepth; depth<=maxDepth; depth+=2){
+         int iterations = 1 << (maxDepth - depth + minDepth);
+         check = 0;
+
+         for (int i=1; i<=iterations; i++){
+            check += (TreeNode.bottomUpTree(i,depth)).itemCheck();
+            check += (TreeNode.bottomUpTree(-i,depth)).itemCheck();
+         }
+      }
+      return check;
+   }
+
+
+   private static class TreeNode
+   {
+      private TreeNode left, right;
+      private int item;
+
+      TreeNode(int item){
+         this.item = item;
+      }
+
+      private static TreeNode bottomUpTree(int item, int depth){
+         if (depth>0){
+            return new TreeNode(
+                  bottomUpTree(2*item-1, depth-1)
+                  , bottomUpTree(2*item, depth-1)
+                  , item
+            );
+         }
+         else {
+            return new TreeNode(item);
+         }
+      }
+
+      TreeNode(TreeNode left, TreeNode right, int item){
+         this.left = left;
+         this.right = right;
+         this.item = item;
+      }
+
+      private int itemCheck(){
+         // if necessary deallocate here
+         if (left==null) return item;
+         else return item + left.itemCheck() - right.itemCheck();
+      }
+   }
+  // CHECKSTYLE.ON: .*
+  @Benchmark
+  public void jmhTimeBinaryTrees() {
+    old_main();
+  }
+}