/* a full binary tree of depth D. checksum is the node count, 8191.
   malloc: one malloc per node, then a recursive free. same shape as new().
   arena: one buffer, a bump pointer, no allocator inside the loop.
   usage: trees malloc|arena REPS */
#include <stdio.h>
#include <stdlib.h>

enum { D = 12, EXPECT = 8191 };

typedef struct node {
	struct node *left, *right;
} node;

static node *make(int d)
{
	node *n = (node *)malloc(sizeof *n);
	if (d > 0) {
		n->left = make(d - 1);
		n->right = make(d - 1);
	} else
		n->left = n->right = 0;
	return n;
}

static int check(const node *n)
{
	if (!n->left) return 1;
	return 1 + check(n->left) + check(n->right);
}

static void destroy(node *n)
{
	if (!n) return;
	destroy(n->left);
	destroy(n->right);
	free(n);
}

static node *bump;

static node *make_at(int d)
{
	node *n = bump++;
	if (d > 0) {
		n->left = make_at(d - 1);
		n->right = make_at(d - 1);
	} else
		n->left = n->right = 0;
	return n;
}

int main(int argc, char **argv)
{
	int reps, r = 0, k, arena, nodes;
	node *buf = 0;
	if (argc != 3) return 2;
	arena = argv[1][0] == 'a';
	reps = atoi(argv[2]);
	nodes = (1 << (D + 1)) - 1;
	if (arena) {
		buf = malloc((size_t)nodes * sizeof *buf);
		if (!buf) return 3;
	}
	for (k = 0; k < reps; k++) {
		if (arena) {
			node *root;
			bump = buf;
			root = make_at(D);
			r = check(root);
			__asm__ __volatile__("" : "+r"(r) : "r"(root) : "memory");
		} else {
			node *root = make(D);
			r = check(root);
			__asm__ __volatile__("" : "+r"(r) : "r"(root) : "memory");
			destroy(root);
		}
	}
	if (r != EXPECT) {
		fprintf(stderr, "bad %d\n", r);
		return 1;
	}
	printf("%d\n", r);
	free(buf);
	return 0;
}