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 static
  24 treeNode* NewTreeNode(treeNode* left, treeNode* right, long item)
  25 {
  26     treeNode*    new;
  27
  28     new = (treeNode*)malloc(sizeof(treeNode));
  29
  30     new->left = left;
  31     new->right = right;
  32     new->item = item;
  33
  34     return new;
  35 } /* NewTreeNode() */
  36
  37 static
  38 long ItemCheck(treeNode* tree)
  39 {
  40     if (tree->left == NULL)
  41         return tree->item;
  42     else
  43         return tree->item + ItemCheck(tree->left) - ItemCheck(tree->right);
  44 } /* ItemCheck() */
  45
  46 static
  47 treeNode* BottomUpTree(long item, unsigned depth)
  48 {
  49     if (depth > 0)
  50         return NewTreeNode
  51         (
  52             BottomUpTree(2 * item - 1, depth - 1),
  53             BottomUpTree(2 * item, depth - 1),
  54             item
  55         );
  56     else
  57         return NewTreeNode(NULL, NULL, item);
  58 } /* BottomUpTree() */
  59
  60 static
  61 void DeleteTree(treeNode* tree)
  62 {
  63     if (tree->left != NULL)
  64     {
  65         DeleteTree(tree->left);
  66         DeleteTree(tree->right);
  67     }
  68
  69     free(tree);
  70 } /* DeleteTree() */
  71
  72
  73 int main(int argc, char* argv[])
  74 {
  75     unsigned   N, depth, minDepth, maxDepth, stretchDepth;
  76     treeNode   *stretchTree, *longLivedTree, *tempTree;
  77
  78     if(argc < 2) {
  79         N = 10;
  80         printf("Using default input %d\n", N);
  81     } else {
  82         N = atol(argv[1]);
  83     }
  84
  85     minDepth = 4;
  86
  87     if ((minDepth + 2) > N)
  88         maxDepth = minDepth + 2;
  89     else
  90         maxDepth = N;
  91
  92     stretchDepth = maxDepth + 1;
  93
  94     stretchTree = BottomUpTree(0, stretchDepth);
  95     printf
  96     (
  97         "stretch tree of depth %u\t check: %li\n",
  98         stretchDepth,
  99         ItemCheck(stretchTree)
 100     );
 101
 102     DeleteTree(stretchTree);
 103
 104     longLivedTree = BottomUpTree(0, maxDepth);
 105
 106     for (depth = minDepth; depth <= maxDepth; depth += 2)
 107     {
 108         long    i, iterations, check;
 109
 110         iterations = pow(2, maxDepth - depth + minDepth);
 111
 112         check = 0;
 113
 114         for (i = 1; i <= iterations; i++)
 115         {
 116             tempTree = BottomUpTree(i, depth);
 117             check += ItemCheck(tempTree);
 118             DeleteTree(tempTree);
 119
 120             tempTree = BottomUpTree(-i, depth);
 121             check += ItemCheck(tempTree);
 122             DeleteTree(tempTree);
 123         } /* for(i = 1...) */
 124
 125         printf
 126         (
 127             "%li\t trees of depth %u\t check: %li\n",
 128             iterations * 2,
 129             depth,
 130             check
 131         );
 132     } /* for(depth = minDepth...) */
 133
 134     printf
 135     (
 136         "long lived tree of depth %u\t check: %li\n",
 137         maxDepth,
 138         ItemCheck(longLivedTree)
 139     );
 140
 141     return 0;
 142 } /* main() */