1 /* The Computer Language Shootout Benchmarks
2 http://shootout.alioth.debian.org/
4 contributed by Kevin Carson
6 gcc -O3 -fomit-frame-pointer -funroll-loops -static binary-trees.c -lm
7 icc -O3 -ip -unroll -static binary-trees.c -lm
24 treeNode* NewTreeNode(treeNode* left, treeNode* right, long item)
28 new = (treeNode*)malloc(sizeof(treeNode));
38 long ItemCheck(treeNode* tree)
40 if (tree->left == NULL)
43 return tree->item + ItemCheck(tree->left) - ItemCheck(tree->right);
47 treeNode* BottomUpTree(long item, unsigned depth)
52 BottomUpTree(2 * item - 1, depth - 1),
53 BottomUpTree(2 * item, depth - 1),
57 return NewTreeNode(NULL, NULL, item);
58 } /* BottomUpTree() */
61 void DeleteTree(treeNode* tree)
63 if (tree->left != NULL)
65 DeleteTree(tree->left);
66 DeleteTree(tree->right);
73 int main(int argc, char* argv[])
75 unsigned N, depth, minDepth, maxDepth, stretchDepth;
76 treeNode *stretchTree, *longLivedTree, *tempTree;
80 printf("Using default input %d\n", N);
87 if ((minDepth + 2) > N)
88 maxDepth = minDepth + 2;
92 stretchDepth = maxDepth + 1;
94 stretchTree = BottomUpTree(0, stretchDepth);
97 "stretch tree of depth %u\t check: %li\n",
99 ItemCheck(stretchTree)
102 DeleteTree(stretchTree);
104 longLivedTree = BottomUpTree(0, maxDepth);
106 for (depth = minDepth; depth <= maxDepth; depth += 2)
108 long i, iterations, check;
110 iterations = pow(2, maxDepth - depth + minDepth);
114 for (i = 1; i <= iterations; i++)
116 tempTree = BottomUpTree(i, depth);
117 check += ItemCheck(tempTree);
118 DeleteTree(tempTree);
120 tempTree = BottomUpTree(-i, depth);
121 check += ItemCheck(tempTree);
122 DeleteTree(tempTree);
123 } /* for(i = 1...) */
127 "%li\t trees of depth %u\t check: %li\n",
132 } /* for(depth = minDepth...) */
136 "long lived tree of depth %u\t check: %li\n",
138 ItemCheck(longLivedTree)