#include #include #include "tree.h" /* The original code, where `CONSISTENT_ORDER` and `tree_node` versus `backward_tree_node` are selected by modifying the source. */ int CONSISTENT_ORDER = 0; static tree_node *make_tree(int depth) { tree_node *tn; static tree_node *prev = NULL; tn = malloc(sizeof(tree_node)); tn->value = depth; if (depth > 0) { if (CONSISTENT_ORDER) { tn->left = make_tree(depth - 1); tn->right = make_tree(depth - 1); } else { if (depth & 0x1) { tn->left = make_tree(depth - 1); tn->right = make_tree(depth - 1); } else { tn->right = make_tree(depth - 1); tn->left = make_tree(depth - 1); } } } else { tn->left = NULL; tn->right = NULL; } return tn; } static long tree_sum(tree_node *tn) { if (tn == NULL) return 0; else { long sum = tn->value; sum += tree_sum(tn->left); sum += tree_sum(tn->right); return sum; } } static long backward_tree_sum(tree_node *tn) { if (tn == NULL) return 0; else { long sum = tn->value; sum += backward_tree_sum(tn->right); sum += backward_tree_sum(tn->left); return sum; } } #define BM_TREE_DEPTH 23 #define BM_ITERS 10 int main() { tree_node *tn; int i; long sum = 0; tn = make_tree(BM_TREE_DEPTH); for (i = 0; i < BM_ITERS; i++) { /* Pick one of the sum functions: */ sum += tree_sum(tn); } printf("%ld\n", sum); return 0; }