/*
 *                   Towers of Hanoi by Threads
 * 
 *  Copyright (C) 2004  NIIBE Yutaka  <gniibe@fsij.org>
 * 
 *  $Id: towers-of-hanoi.c,v 1.3 2004/03/04 12:41:38 gniibe Exp $
 * 
 *  This program 'Towers of Hanoi by Threads' is free software; you can
 *  redistribute it and/or modify it under the terms of the GNU General
 *  Public License as published by the Free Software Foundation; either
 *  version 2 or (at your option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

#define MAXDISK 64

struct port {
	enum { NONE, SYN, ACK, ESTABLISHED, FIN } status;
	pthread_mutex_t mutex;
	pthread_cond_t cv;
	int value;
} ports[3];

static int towers[3];
static int disks[MAXDISK];

static int direction;

static int
forward(int n)
{
	if (direction)
		return (n + 2) % 3;
	else
		return (n + 1) % 3;
}

static int
exchange(int tower, int value)
{
	struct port *p = ports + tower;
	int r;

	pthread_mutex_lock(&p->mutex);
	if (p->status == NONE) {
		p->status = SYN;
		p->value = value;
		while (p->status == SYN)
			pthread_cond_wait(&p->cv, &p->mutex);
		r = p->value;
		p->status = ESTABLISHED;
		pthread_cond_signal(&p->cv);
	} else if (p->status == SYN) {
		r = p->value;
		p->value = value;
		p->status = ACK;
		pthread_cond_signal(&p->cv);
	} else	/* Something wrong happened */
		abort();
	pthread_mutex_unlock(&p->mutex);
	return r;
}

static void
synchronize(int tower)
{
	struct port *p = ports + tower;

	pthread_mutex_lock(&p->mutex);
	while (p->status == ACK)
		pthread_cond_wait(&p->cv, &p->mutex);

	if (p->status == ESTABLISHED) {
		p->status = FIN;
		while (p->status == FIN)
			pthread_cond_wait(&p->cv, &p->mutex);
	} else if (p->status == FIN) {
		p->status = NONE;
		pthread_cond_signal(&p->cv);
	} else	/* Something wrong happened */
		abort();
	pthread_mutex_unlock(&p->mutex);
}

static int
do_hanoi(int tower, int mode)
{
	int d0, d1, d2;
	int t;

	d0 = towers[tower];
	if (mode)
		t = forward(tower);
	else
		t = tower;

	d1 = exchange(t, d0);
	if (d0 <= d1) {
		if (d0 == d1) {
			if (!mode)
				exchange(forward(tower), -1);
			return 1;
		}
		d2 = disks[d0];
		towers[tower] = d2;
		if (mode)
			printf ("Move disk%d from %d to %d\n", d0, tower, t);
		else
			printf ("Move disk%d from %d to %d\n", d0, tower, forward(forward(tower)));
		synchronize(t);
	} else {
		if (d1 < 0)
			return 1;
		synchronize(t);
		disks[d1] = d0;
		towers[tower] = d1;
	}

	return 0;
}

static void *
hanoi(void *args)
{
	int tower = *(int *)args;
	int mode = 0;
	int done = 0;

	if (tower == forward(forward(0)))
		mode = 1;

	while (!done) {
		done = do_hanoi(tower, mode); 
		mode = !mode;
	}
	pthread_exit (NULL);
}

int
main(int argc, char **argv)
{
	int i, n;
	pthread_t thread[3];
	int thread_args[3];

	if (argc != 2) {
		printf("Usage: %s N\n", argv[0]);
		exit (1);
	}
	n = atoi(argv[1]);

	if (n < 1 || n > 64) {
		printf("N should be 1<=N<=64 (%d).\n", n);
		exit (1);
	}

	for (i=0; i < n; i++)
		disks[i] = i+1;
	towers[0] = 0;
	towers[1] = n;
	towers[2] = n;

	direction = n%2;

	for (i=0; i<3; i++) {
		pthread_mutex_init(&ports[i].mutex, NULL);
		pthread_cond_init(&ports[i].cv, NULL);
		ports[i].status = NONE;
		thread_args[i] = i;
	}

	for (i=0; i<3; i++)
		pthread_create(&thread[i], NULL, hanoi, thread_args + i);

	for (i=0; i<3; i++)
		pthread_join(thread[i], NULL);

	exit(0);
}