diff options
Diffstat (limited to '')
-rw-r--r-- | dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree.c | 166 |
1 files changed, 166 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree.c b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree.c new file mode 100644 index 0000000..a909246 --- /dev/null +++ b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/shootout/binary-tree.c @@ -0,0 +1,166 @@ +// +build ignore + +/* +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() */ |