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
23 treeNode* NewTreeNode(treeNode* left, treeNode* right, long item)
27 new = (treeNode*)malloc(sizeof(treeNode));
37 long ItemCheck(treeNode* tree)
39 if (tree->left == NULL)
42 return tree->item + ItemCheck(tree->left) - ItemCheck(tree->right);
46 treeNode* BottomUpTree(long item, unsigned depth)
51 BottomUpTree(2 * item - 1, depth - 1),
52 BottomUpTree(2 * item, depth - 1),
56 return NewTreeNode(NULL, NULL, item);
57 } /* BottomUpTree() */
60 void DeleteTree(treeNode* tree)
62 if (tree->left != NULL)
64 DeleteTree(tree->left);
65 DeleteTree(tree->right);
72 int main(int argc, char* argv[])
74 unsigned N, depth, minDepth, maxDepth, stretchDepth;
75 treeNode *stretchTree, *longLivedTree, *tempTree;
79 printf("Using default input %d\n", N);
86 if ((minDepth + 2) > N)
87 maxDepth = minDepth + 2;
91 stretchDepth = maxDepth + 1;
93 stretchTree = BottomUpTree(0, stretchDepth);
96 "stretch tree of depth %u\t check: %li\n",
98 ItemCheck(stretchTree)
101 DeleteTree(stretchTree);
103 longLivedTree = BottomUpTree(0, maxDepth);
105 for (depth = minDepth; depth <= maxDepth; depth += 2)
107 long i, iterations, check;
109 iterations = pow(2, maxDepth - depth + minDepth);
113 for (i = 1; i <= iterations; i++)
115 tempTree = BottomUpTree(i, depth);
116 check += ItemCheck(tempTree);
117 DeleteTree(tempTree);
119 tempTree = BottomUpTree(-i, depth);
120 check += ItemCheck(tempTree);
121 DeleteTree(tempTree);
122 } /* for(i = 1...) */
126 "%li\t trees of depth %u\t check: %li\n",
131 } /* for(depth = minDepth...) */
135 "long lived tree of depth %u\t check: %li\n",
137 ItemCheck(longLivedTree)