// philosopher.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>

const int NUM_PHILOSOPHERS = 5;
const int NUM_CHOPSTICKS = NUM_PHILOSOPHERS;
const int NUM_ROUNDS = 6;

int g_bGreedy;
int g_bCompute;
int g_nTLS;


void OutputDebug(const TCHAR * format, ...);


int ThisPhilosopher()
{
    return (int)TlsGetValue(g_nTLS);
}

void MyWaitForSingleObject(HANDLE handle, DWORD dwMilliseconds, const TCHAR * szName)
{
    UINT nID = ThisPhilosopher();
    if (INFINITE == dwMilliseconds)
    {
        OutputDebug(TEXT("#%d waiting forever on %s %08lx\n"), nID, szName, handle);
    }
    DWORD r = WaitForSingleObject(handle, dwMilliseconds);
    switch (r)
    {
        case WAIT_OBJECT_0:
            break;
        case WAIT_ABANDONED:
            OutputDebug(TEXT("#%d wait on %s: WAIT_ABANDONED\n"), nID, szName);
            break;
        case WAIT_TIMEOUT:
            OutputDebug(TEXT("#%d wait on %s: WAIT_TIMEOUT\n"), nID, szName);
            break;
        case WAIT_FAILED:
            OutputDebug(TEXT("#%d wait on %s: WAIT_FAILED, last error %d\n"), nID, szName, GetLastError());
            break;
        default:
            OutputDebug(TEXT("#%d wait on %s: unexpected return %d, last error %d\n"), nID, szName, r, GetLastError());
            break;
    }
}

void MyReleaseMutex(HANDLE handle, const TCHAR * szName)
{
    if (!ReleaseMutex(handle))
    {
        OutputDebug(TEXT("#%d release on %s: failed, last error %d\n"), ThisPhilosopher(), szName, GetLastError());
    }
}

void MySleep(DWORD dwMilliseconds)
{
    if (INFINITE == dwMilliseconds)
    {
        OutputDebug(TEXT("#%d sleeping forever"), ThisPhilosopher());
        // actually, until no other thread of equal priority is runnable
    }
    Sleep(dwMilliseconds);
}


DWORD WINAPI Chef(LPVOID lpvoid);
DWORD WINAPI Philosopher(LPVOID lpPhilosopherID);

int WINAPI WinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPTSTR    lpCmdLine,
                     int       nCmdShow)
{
	
	HANDLE arrChopsticks[NUM_CHOPSTICKS];
	HANDLE arrPhilosophers[NUM_PHILOSOPHERS];
	HANDLE hChef = 0;
	
#ifdef ICECAP
#pragma message("ICECAP enabled!")
	OutputDebug(TEXT("ICECAP enabled!"));
#endif

    g_nTLS = TlsAlloc();
    if (g_nTLS  < 0 )
    {
        OutputDebug(TEXT("TLS alloc failed, last error %d\n"), GetLastError());
        return 0;
    }
    TlsSetValue(g_nTLS, (LPVOID)-1);

    OutputDebug(TEXT("Waiter is setting table for %d philosophers and %d chopsticks\n"), NUM_PHILOSOPHERS, NUM_CHOPSTICKS);
    OutputDebug(TEXT("[Command line: '%s', Infinite: %d]\n"), lpCmdLine, INFINITE);


	// Philosopher #1 will be greedy if there is a command line
	// parameter of length 1
	g_bGreedy = (NULL != lpCmdLine) && (1 == _tcslen(lpCmdLine));
    if (g_bGreedy)
    {
        OutputDebug(TEXT("(Philospher #1 is being greedy)\n"));
    }

	// Low priority "computation" thread if there is a command line
	// parameter of length 2
	g_bCompute = (NULL != lpCmdLine) && (2 == _tcslen(lpCmdLine));

	int i;
	for(i = 0; i < NUM_CHOPSTICKS; i++)
	{
		TCHAR szName[50];
		_stprintf(szName, TEXT("Chopstick%d"), i);
        OutputDebug(TEXT("Setting table with %s\n"), szName);
		arrChopsticks[i] = CreateMutex(NULL, FALSE, szName);
        OutputDebug(TEXT("%s == %08lx\n"), szName, arrChopsticks[i]);

		if(arrChopsticks[i] == NULL)
		{
            OutputDebug(TEXT("Couldn't create %s\n"), szName);
			return 0;
		}
	}

    OutputDebug(TEXT("The philosophers arrive\n"));

	for(i = 0; i < NUM_PHILOSOPHERS; i++)
	{
		arrPhilosophers[i] = CreateThread(NULL, 0, Philosopher, (void*)i, 0, NULL);
        OutputDebug(TEXT("#%d == %08lx\n"), i, arrPhilosophers[i]);

		if(arrPhilosophers[i] == NULL)
		{
            OutputDebug(TEXT("Couldn't create philosopher #%d\n"), i);
			return 0;
		}
	}

	if (g_bCompute)
	{
		OutputDebug(TEXT("Chef is busy computing in the kitchen\n"));
		hChef = CreateThread(NULL, 0, Chef, (void*)0, 0, NULL);
		SetThreadPriority(hChef, THREAD_PRIORITY_LOWEST);
		OutputDebug(TEXT("Chef == %08lx\n"), hChef);
	}

    OutputDebug(TEXT("Waiter is waiting for the end of dinner\n"));

	for(i = 0; i < NUM_PHILOSOPHERS; i++)
	{
        OutputDebug(TEXT("Waiter is waiting for #%d (%08lx) to finish\n"), i, arrPhilosophers[i]);

		MyWaitForSingleObject(arrPhilosophers[i], INFINITE, TEXT("Thread handle"));

        OutputDebug(TEXT("Waiter discovers that #%d has finished\n"), i);

		CloseHandle(arrPhilosophers[i]);
	}

    OutputDebug(TEXT("Waiter is cleaning table after dinner\n"));

	for(i = 0; i < NUM_CHOPSTICKS; i++)
	{
		CloseHandle(arrChopsticks[i]);
	}

	if (g_bCompute)
	{
		OutputDebug(TEXT("Waiting for Chef to finish\n"));
		MyWaitForSingleObject(hChef, INFINITE, TEXT("Chef thread handle"));
		CloseHandle(hChef);
	}

	return 0;
}

void PonderNothingness()
{
    OutputDebug(TEXT("#%d PonderNothingness\n"), ThisPhilosopher());

    MySleep(1000);
}

void Eat(HANDLE hLeft, HANDLE hRight)
{
    OutputDebug(TEXT("#%d Eating\n"), ThisPhilosopher());

	MyWaitForSingleObject(hRight, INFINITE, TEXT("right chopstick"));
	MyWaitForSingleObject(hLeft,  INFINITE, TEXT("left chopstick"));
	MySleep(500);
	MyReleaseMutex(hLeft,  TEXT("left chopstick"));
	MyReleaseMutex(hRight, TEXT("right chopstick"));
}

void GreedyEat(HANDLE hLeft, HANDLE hRight)
{
    OutputDebug(TEXT("#%d Greedy eating\n"), ThisPhilosopher());

	MyWaitForSingleObject(hRight, INFINITE, TEXT("right chopstick"));
	MyWaitForSingleObject(hLeft,  INFINITE, TEXT("left chopstick"));
	MySleep(INFINITE);
	MyReleaseMutex(hLeft,  TEXT("left chopstick"));
	MyReleaseMutex(hRight, TEXT("right chopstick"));	


}

DWORD WINAPI Philosopher(LPVOID lpPhilosopherID)
{
	UINT nID = (UINT)lpPhilosopherID;
	HANDLE hChopstickRight, hChopstickLeft;
	TCHAR szNameRight[50], szNameLeft[50];

    TlsSetValue(g_nTLS, lpPhilosopherID);

	_stprintf(szNameRight, TEXT("Chopstick%d"), nID);
	_stprintf(szNameLeft,  TEXT("Chopstick%d"), (nID + 1) % NUM_CHOPSTICKS);

	hChopstickRight = CreateMutex(NULL, FALSE, szNameRight);
	hChopstickLeft  = CreateMutex(NULL, FALSE, szNameLeft);

    OutputDebug(TEXT("#%d eats with chopsticks %s and %s\n"), nID, szNameRight, szNameLeft);

    for(int x = 0; x < NUM_ROUNDS; x++)
	{
		PonderNothingness();
        ((g_bGreedy && (nID == 1)) ? GreedyEat : Eat) (hChopstickLeft, hChopstickRight);
	}

    OutputDebug(TEXT("#%d leaves the table\n"), nID);

	return 0;
}


// Well known Ackerman's Function
// ack(0,q) == 2q
// ack(1,q) == 2**q
// ack(2,q) == 2**2**2**...**2 (height-q stack of 2's)
// ... each level does the operation from the previous level q times
// ... so ack(4,4) is really large ...
//long Ackerman(long i, long j)
//{
//	if (i == 0)
//		return j + 1;
//	else if (i > 0 && j == 0)
//		return Ackerman(i-1, 1);
//	else
//		return Ackerman(i-1, Ackerman(i, j-1));
//}


long AckAck0(long i, long j);
long AckAck1(long i, long j);
long AckAck2(long i, long j);

int g_nDepth;
int g_nDepths[3];
int g_nMaxDepth;
int g_nMaxDepths[3];

struct CDepth
{
	int m_d;
	CDepth(int d) : m_d(d)
	{
		g_nDepth++;
		g_nDepths[d]++;
		g_nMaxDepth=max(g_nMaxDepth,g_nDepth);
		g_nMaxDepths[d]=max(g_nMaxDepths[d],g_nDepths[d]);
	}
	~CDepth()
	{
		g_nDepth--;
		g_nDepths[m_d]--;
	}
	static Init()
	{
		g_nDepth = g_nMaxDepth = 0;
		for (int i = 0; i < 3; i++)
			g_nDepths[i] = g_nMaxDepths[i] = 0;
	}
	static Dump()
	{
		OutputDebug(TEXT("Max cooking depth = %d\n"), g_nMaxDepth);
		for (int i = 0; i < 3; i++)
			OutputDebug(TEXT("Max cooking depth%d = %d\n"), i, g_nMaxDepths[i]);
	}
};

long AckAck0(long i, long j)
{
	CDepth d(0);
	if (i == 0)
		return j + 1;
	else if (i > 0 && j == 0)
		return AckAck0(i-1, 1);
	else
		return AckAck1(i-1, AckAck2(i, j-1));
}

long AckAck1(long i, long j)
{
	CDepth d(1);
	if (i == 0)
		return j + 1;
	else if (i > 0 && j == 0)
		return AckAck0(i-1, 1);
	else
		return AckAck1(i-1, AckAck2(i, j-1));
}

long AckAck2(long i, long j)
{
	CDepth d(2);
	if (i == 0)
		return j + 1;
	else if (i > 0 && j == 0)
		return AckAck0(i-1, 1);
	else
		return AckAck1(i-1, AckAck2(i, j-1));
}

void Cook()
{
	(void)AckAck0(2,4);
}



#define TIME_TO_COMPUTE 30000	// milliseconds = 30 sec
DWORD WINAPI Chef(LPVOID lpvoid)
{
	OutputDebug(TEXT("Chef starts cooking Ackerman's function"));

	CDepth::Init();
	DWORD dwStartCount = GetTickCount();
	while ((dwStartCount + TIME_TO_COMPUTE) > GetTickCount())
	{
		Cook();
	}
	CDepth::Dump();

	OutputDebug(TEXT("Chef done cooking Ackerman's function"));

	return 0;
}

void OutputDebug(const TCHAR * format, ...)
{
    TCHAR sz[300];

    va_list args;
    va_start(args, format);
    _vsntprintf(sz, 300-1, format, args);
    OutputDebugString(sz);
    va_end(args);
}