diff options
Diffstat (limited to 'test/bench/binary-tree.c')
| -rw-r--r-- | test/bench/binary-tree.c | 165 |
1 files changed, 0 insertions, 165 deletions
diff --git a/test/bench/binary-tree.c b/test/bench/binary-tree.c deleted file mode 100644 index 1b4070406..000000000 --- a/test/bench/binary-tree.c +++ /dev/null @@ -1,165 +0,0 @@ -/* -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 <malloc.h> -#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() */ |