nsz Git - libfirm/blob - ir/be/test/langshootout/bintree.c

   1 /* The Computer Language Shootout Benchmarks
   2    http://shootout.alioth.debian.org/
   3
   4    contributed by Kevin Carson
   5    compilation:
   6        gcc -O3 -fomit-frame-pointer -funroll-loops -static binary-trees.c -lm
   7        icc -O3 -ip -unroll -static binary-trees.c -lm
   8 */
   9
  10 #include <malloc.h>
  11 #include <math.h>
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14
  15
  16 typedef struct tn {
  17     struct tn*    left;
  18     struct tn*    right;
  19     long          item;
  20 } treeNode;
  21
  22
  23 treeNode* NewTreeNode(treeNode* left, treeNode* right, long item)
  24 {
  25     treeNode*    new;
  26
  27     new = (treeNode*)malloc(sizeof(treeNode));
  28
  29     new->left = left;
  30     new->right = right;
  31     new->item = item;
  32
  33     return new;
  34 } /* NewTreeNode() */
  35
  36
  37 long ItemCheck(treeNode* tree)
  38 {
  39     if (tree->left == NULL)
  40         return tree->item;
  41     else
  42         return tree->item + ItemCheck(tree->left) - ItemCheck(tree->right);
  43 } /* ItemCheck() */
  44
  45
  46 treeNode* BottomUpTree(long item, unsigned depth)
  47 {
  48     if (depth > 0)
  49         return NewTreeNode
  50         (
  51             BottomUpTree(2 * item - 1, depth - 1),
  52             BottomUpTree(2 * item, depth - 1),
  53             item
  54         );
  55     else
  56         return NewTreeNode(NULL, NULL, item);
  57 } /* BottomUpTree() */
  58
  59
  60 void DeleteTree(treeNode* tree)
  61 {
  62     if (tree->left != NULL)
  63     {
  64         DeleteTree(tree->left);
  65         DeleteTree(tree->right);
  66     }
  67
  68     free(tree);
  69 } /* DeleteTree() */
  70
  71
  72 int main(int argc, char* argv[])
  73 {
  74     unsigned   N, depth, minDepth, maxDepth, stretchDepth;
  75     treeNode   *stretchTree, *longLivedTree, *tempTree;
  76
  77     if(argc < 2) {
  78         N = 10;
  79         printf("Using default input %d\n", N);
  80     } else {
  81         N = atol(argv[1]);
  82     }
  83
  84     minDepth = 4;
  85
  86     if ((minDepth + 2) > N)
  87         maxDepth = minDepth + 2;
  88     else
  89         maxDepth = N;
  90
  91     stretchDepth = maxDepth + 1;
  92
  93     stretchTree = BottomUpTree(0, stretchDepth);
  94     printf
  95     (
  96         "stretch tree of depth %u\t check: %li\n",
  97         stretchDepth,
  98         ItemCheck(stretchTree)
  99     );
 100
 101     DeleteTree(stretchTree);
 102
 103     longLivedTree = BottomUpTree(0, maxDepth);
 104
 105     for (depth = minDepth; depth <= maxDepth; depth += 2)
 106     {
 107         long    i, iterations, check;
 108
 109         iterations = pow(2, maxDepth - depth + minDepth);
 110
 111         check = 0;
 112
 113         for (i = 1; i <= iterations; i++)
 114         {
 115             tempTree = BottomUpTree(i, depth);
 116             check += ItemCheck(tempTree);
 117             DeleteTree(tempTree);
 118
 119             tempTree = BottomUpTree(-i, depth);
 120             check += ItemCheck(tempTree);
 121             DeleteTree(tempTree);
 122         } /* for(i = 1...) */
 123
 124         printf
 125         (
 126             "%li\t trees of depth %u\t check: %li\n",
 127             iterations * 2,
 128             depth,
 129             check
 130         );
 131     } /* for(depth = minDepth...) */
 132
 133     printf
 134     (
 135         "long lived tree of depth %u\t check: %li\n",
 136         maxDepth,
 137         ItemCheck(longLivedTree)
 138     );
 139
 140     return 0;
 141 } /* main() */