// The Computer Language Benchmarks Game
// http://shootout.alioth.debian.org/
// By bearophile, optimized for simplicity, quite slow

// Run: testgc.exe xx yy
// xx: alloc depth, default is 14
// yy: how many threads, default is 1
// Ex: testgc.exe 18 4

import core.thread;
import core.memory;

import std.perf;
import std.stdio;
import std.conv;
import std.string;

import std.c.time;
import std.c.stdio;

class TreeNode 
{
    int item;
    TreeNode left, right;

    this(int item, TreeNode left =null, TreeNode right =null) 
	{
        this.item = item;
        this.left = left;
        this.right = right;
    }
	~this()
	{
		if (left !is null)
		{
			delete left;
			delete right;
		}
	}

    int check() const
	{
        if (left !is null)
			return (item + left.check - right.check);
		else
			return item;
    }

	static TreeNode makeTree(int item, int depth)
	{
	    if (depth > 0)
	        return new TreeNode(	item, 
									makeTree(2*item-1, depth-1), 
									makeTree(2*item, depth-1)	);
	    else
	        return new TreeNode(item);
	}
}

int fetch_job(int step)(int*)
{
	asm
	{
		naked;
		mov		ECX,	EAX;	// last var pass on EAX
		mov		EAX,	step;
		lock;
		xadd	[ECX],	EAX;	// EAX = old value
		ret;
	}
}

void main(string[] args) 
{
    int n = (args.length >= 2) ? toInt(args[1]) : 14;
	int nthreads = (args.length >= 3) ? toInt(args[2]) : 1;

    const minDepth = 4;
    int maxDepth = (minDepth + 2) > n ? minDepth + 2 : n;

    GC.disable;

    scope pc = new PerformanceCounter;
    pc.start;

	{
		scope stretchTree = TreeNode.makeTree(0, maxDepth + 1);
		writefln("stretch tree of depth ", maxDepth + 1, "\t check: ", stretchTree.check);
	}

	{
	    scope longLivedTree = TreeNode.makeTree(0, maxDepth);

		{
			scope string[] result = new string[maxDepth +1];
			scope Thread[] threads = new Thread[nthreads];
			int current_depth = minDepth;
			
			foreach (ref t; threads)
			{
				t = new Thread(
				{
					int depth;
					while ((depth = fetch_job!(2)(&current_depth)) <= maxDepth)
				    //for (int depth = minDepth; depth <= maxDepth; depth += 2) 
					{
				        int iterations = 1 << (maxDepth - depth + minDepth);
				        int check = 0;

				        for (int i = 1; i <= iterations; i++)
						{
							scope lt = TreeNode.makeTree(i, depth);
							scope rt = TreeNode.makeTree(-i, depth);
				            check += lt.check + rt.check;
						}

						result[depth] = format("%d\t trees of depth %d\t check: %d\n", iterations * 2, depth, check);
				    }
				});
				
				t.start;
			}

			foreach (t; threads)
				t.join();
			
			foreach (str; result)
				writef(str);
		}
		
	    writefln("long lived tree of depth ", maxDepth, "\t check: ", longLivedTree.check);
	}

    pc.stop;
    writefln("\nTiming: ", pc.milliseconds, " ms with ", nthreads, " threads");
}