Davantage de tests

git-svn-id: https://yquem.inria.fr/compcert/svn/compcert/trunk@104 fca1b0fc-160b-0410-b1d3-a4f43f01ea2e

1 files changed, 164 insertions, 0 deletions

diff --git a/test/c/binarytrees.c b/test/c/binarytrees.c
new file mode 100644
index 00000000..0c5bf375
--- /dev/null
+++ b/test/c/binarytrees.c
@@ -0,0 +1,164 @@
+/* The Computer Language Shootout Benchmarks
+   http://shootout.alioth.debian.org/
+
+   contributed by Kevin Carson
+   compilation:
+       gcc -O3 -fomit-frame-pointer -funroll-loops -static binary-trees.c -lm
+       icc -O3 -ip -unroll -static binary-trees.c -lm
+*/
+
+#include <malloc.h>
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+
+typedef struct tn {
+    struct tn*    left;
+    struct tn*    right;
+    long          item;
+} treeNode;
+
+
+treeNode* NewTreeNode(treeNode* left, treeNode* right, long item)
+{
+    treeNode*    new;
+
+    new = (treeNode*)malloc(sizeof(treeNode));
+
+    new->left = left;
+    new->right = right;
+    new->item = item;
+
+    return new;
+} /* NewTreeNode() */
+
+
+long ItemCheck(treeNode* tree)
+{
+    if (tree->left == NULL)
+        return tree->item;
+    else
+        return tree->item + ItemCheck(tree->left) - ItemCheck(tree->right);
+} /* ItemCheck() */
+
+
+treeNode* BottomUpTree(long item, unsigned depth)
+{
+    if (depth > 0)
+        return NewTreeNode
+        (
+            BottomUpTree(2 * item - 1, depth - 1),
+            BottomUpTree(2 * item, depth - 1),
+            item
+        );
+    else
+        return NewTreeNode(NULL, NULL, item);
+} /* BottomUpTree() */
+
+
+void DeleteTree(treeNode* tree)
+{
+    if (tree->left != NULL)
+    {
+        DeleteTree(tree->left);
+        DeleteTree(tree->right);
+    }
+
+    free(tree);
+} /* DeleteTree() */
+
+
+int main(int argc, char* argv[])
+{
+    unsigned   N, depth, minDepth, maxDepth, stretchDepth;
+    treeNode   *stretchTree, *longLivedTree, *tempTree;
+
+    N = argc < 2 ? 16 : atol(argv[1]);
+
+    minDepth = 4;
+
+    if ((minDepth + 2) > N)
+        maxDepth = minDepth + 2;
+    else
+        maxDepth = N;
+
+    stretchDepth = maxDepth + 1;
+
+    stretchTree = BottomUpTree(0, stretchDepth);
+    printf
+    (
+        "stretch tree of depth %u\t check: %li\n",
+        stretchDepth,
+        ItemCheck(stretchTree)
+    );
+
+    DeleteTree(stretchTree);
+
+    longLivedTree = BottomUpTree(0, maxDepth);
+
+    for (depth = minDepth; depth <= maxDepth; depth += 2)
+    {
+        long    i, iterations, check;
+
+        iterations = pow(2, maxDepth - depth + minDepth);
+
+        check = 0;
+
+        for (i = 1; i <= iterations; i++)
+        {
+            tempTree = BottomUpTree(i, depth);
+            check += ItemCheck(tempTree);
+            DeleteTree(tempTree);
+
+            tempTree = BottomUpTree(-i, depth);
+            check += ItemCheck(tempTree);
+            DeleteTree(tempTree);
+        } /* for(i = 1...) */
+
+        printf
+        (
+            "%li\t trees of depth %u\t check: %li\n",
+            iterations * 2,
+            depth,
+            check
+        );
+    } /* for(depth = minDepth...) */
+
+    printf
+    (
+        "long lived tree of depth %u\t check: %li\n",
+        maxDepth,
+        ItemCheck(longLivedTree)
+    );
+
+    return 0;
+} /* main() */
+
+/******
+ build & benchmark results
+
+BUILD COMMANDS FOR: binarytrees.gcc
+
+Thu Sep 14 00:25:13 PDT 2006
+
+/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -funroll-loops -march=pentium4 -lm binarytrees.c -o binarytrees.gcc_run
+
+=================================================================
+COMMAND LINE (%A is single numeric argument):
+
+binarytrees.gcc_run %A
+N=16
+
+PROGRAM OUTPUT
+==============
+stretch tree of depth 17	 check: -1
+131072	 trees of depth 4	 check: -131072
+32768	 trees of depth 6	 check: -32768
+8192	 trees of depth 8	 check: -8192
+2048	 trees of depth 10	 check: -2048
+512	 trees of depth 12	 check: -512
+128	 trees of depth 14	 check: -128
+32	 trees of depth 16	 check: -32
+long lived tree of depth 16	 check: -1
+*********/