| /* |
| Redistribution and use in source and binary forms, with or without |
| modification, are permitted provided that the following conditions are met: |
| |
| * Redistributions of source code must retain the above copyright |
| notice, this list of conditions and the following disclaimer. |
| |
| * Redistributions in binary form must reproduce the above copyright |
| notice, this list of conditions and the following disclaimer in the |
| documentation and/or other materials provided with the distribution. |
| |
| * Neither the name of "The Computer Language Benchmarks Game" nor the |
| name of "The Computer Language Shootout Benchmarks" nor the names of |
| its contributors may be used to endorse or promote products derived |
| from this software without specific prior written permission. |
| |
| THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
| LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
| CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
| SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
| INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
| CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
| POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| /* 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 <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 = 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() */ |