#include #include #define BM_TREE_DEPTH 23 #define BM_ITERS 10 typedef struct tree_node { long value; struct tree_node *left; struct tree_node *right; struct tree_node *next; } tree_node; /* If CONSISTENT_ORDER, then always allocate left tree before right tree: */ #define CONSISTENT_ORDER 1 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 || (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; } /* For list_sum: */ tn->next = NULL; if (prev) prev->next = tn; prev = tn; return tn; } /* Sums the tree by cheating, since tree nodes have been linked into a list by make_tree(): */ long list_sum(tree_node *tn) { long sum = 0; while (tn != NULL) { sum += tn->value; tn = tn->next; } return sum; } 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; } } 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; } } long local_right_tree_sum(tree_node *tn) { if (tn == NULL) return 0; else { long sum = tn->value; tree_node *right = tn->right; sum += local_right_tree_sum(tn->left); sum += local_right_tree_sum(right); return sum; } } /* Make sure our manual stack is deep enough to handle the benchmark: */ #define STACK_DEPTH (BM_TREE_DEPTH * 4) long stack_tree_sum(tree_node *tn) { tree_node *stack[STACK_DEPTH]; int stack_pos = 0; long sum = 0; stack[stack_pos++] = tn; while (stack_pos) { tn = stack[--stack_pos]; if (tn) { sum += tn->value; stack[stack_pos++] = tn->left; stack[stack_pos++] = tn->right; } } return sum; } long sort_stack_tree_sum(tree_node *tn) { tree_node *stack[STACK_DEPTH]; int stack_pos = 0; long sum = 0; stack[stack_pos++] = tn; while (stack_pos) { tn = stack[--stack_pos]; if (tn) { sum += tn->value; if ((uintptr_t)tn->left < (uintptr_t)tn->right) { stack[stack_pos++] = tn->right; stack[stack_pos++] = tn->left; } else { stack[stack_pos++] = tn->left; stack[stack_pos++] = tn->right; } } } return sum; } int main() { tree_node *tn; int i; long sum; 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; }