source code
/* The Computer Language Benchmarks Game
* https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
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
*reset*
*/
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct tn {
struct tn* left;
struct tn* right;
} treeNode;
treeNode* NewTreeNode(treeNode* left, treeNode* right)
{
treeNode* new;
new = (treeNode*)malloc(sizeof(treeNode));
new->left = left;
new->right = right;
return new;
} /* NewTreeNode() */
long ItemCheck(treeNode* tree)
{
if (tree->left == NULL)
return 1;
else
return 1 + ItemCheck(tree->left) + ItemCheck(tree->right);
} /* ItemCheck() */
treeNode* BottomUpTree(unsigned depth)
{
if (depth > 0)
return NewTreeNode
(
BottomUpTree(depth - 1),
BottomUpTree(depth - 1)
);
else
return NewTreeNode(NULL, NULL);
} /* 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(stretchDepth);
printf
(
"stretch tree of depth %u\t check: %li\n",
stretchDepth,
ItemCheck(stretchTree)
);
DeleteTree(stretchTree);
longLivedTree = BottomUpTree(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(depth);
check += ItemCheck(tempTree);
DeleteTree(tempTree);
} /* for(i = 1...) */
printf
(
"%li\t trees of depth %u\t check: %li\n",
iterations,
depth,
check
);
} /* for(depth = minDepth...) */
printf
(
"long lived tree of depth %u\t check: %li\n",
maxDepth,
ItemCheck(longLivedTree)
);
return 0;
} /* main() */
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
13.2.0-23ubuntu4
Mon, 03 Jun 2024 22:07:18 GMT
MAKE:
/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -march=ivybridge binarytrees.c -o binarytrees.gcc_run -lm
rm binarytrees.c
2.92s to complete and log all make actions
COMMAND LINE:
./binarytrees.gcc_run 21
PROGRAM OUTPUT:
stretch tree of depth 22 check: 8388607
2097152 trees of depth 4 check: 65011712
524288 trees of depth 6 check: 66584576
131072 trees of depth 8 check: 66977792
32768 trees of depth 10 check: 67076096
8192 trees of depth 12 check: 67100672
2048 trees of depth 14 check: 67106816
512 trees of depth 16 check: 67108352
128 trees of depth 18 check: 67108736
32 trees of depth 20 check: 67108832
long lived tree of depth 21 check: 4194303