#include<sys/types.h> // pid_t
#include<stdlib.h> // atoi
#include<stdio.h> // scanf, printf, fprintf, snprintf
#include<unistd.h> // fork, execvp
#include<sys/wait.h> // wait

#define MAXN (50)

// Die Eingabematrizen A und B
// im Format A[Zeile][Spalte]
int A[MAXN][MAXN];
int B[MAXN][MAXN];

// Die zu berechnende Matrix E = A*B
int E[MAXN][MAXN];

// Die Zuordnung Kind-PID -> Matrixeintrag
pid_t children[MAXN][MAXN];

// Ein Puffer fuer die Argumente von vmult mit je max. 19 Zeichen,
// genug fuer Integer-Werte
char vmultbuffer[2*MAXN+2][20];

// Funktion, um eine Matrix von der Standardeingabe zu lesen
void read_matrix(int *M, int spalten, int zeilen) {
	for(int i = 0; i<zeilen; ++i) {
		for(int j = 0; j<spalten; ++j) {
			int scan = scanf("%d", (M+j+(i*MAXN)));
			if(scan == 0) {
				fprintf(stderr, "Konnte nicht genug Werte fuer eine %dx%d-Matrix lesen!\n", zeilen, spalten);
				exit(2);
			} else if(scan == EOF) {
				perror("scanf");
				exit(3);
			}
		}
	}
}

// Schreibt eine Matrix auf die Standardausgabe
void print_matrix(int *M, int spalten, int zeilen) {
	for(int i = 0; i<zeilen; ++i) {
		for(int j = 0; j<spalten; ++j) {
			printf("%4d", *(M+j+(i*MAXN)));
		}
		printf("\n");
	}
}

int main(int argc, char *argv[]) {
	// Die Dimension der Matrix
	int n;
	// Die maximale Anzahl an Kindprozessen
	int maxchildren = 5;
	// Die momentane Anzahl an Kindprozessen
	int currentchildren = 0;
	// Die Anzahl der insgesamt bereits in Auftrag gegebenen Eintraege von E
	int jobs = 0;
	// Ein Array von Zeigern auf die Eintraege des Puffers vmultbuffer
	char *vmultargv[2*MAXN+2];

	// Initialisiere Zeiger auf die richtigen Adressen:
	for(int i = 0; i<(2*MAXN+2); ++i) {
		vmultargv[i] = (char*)&vmultbuffer[i];
	}

	// Die maximale Anzahl Kinder muss ggf. veraendert werden
	if(argc > 1) {
		maxchildren = atoi(argv[1]);
	}

	// Lies die Dimension der Matrix ein
	int scan = scanf("%d", &n);
	if(scan == 0) {
		fprintf(stderr, "Konnte die Dimension der Matrix nicht lesen!\n");
		exit(1);
	} else if (scan == EOF) {
		perror("scanf");
		exit(1);
	}

	// Lies die erste Matrix ein:
	read_matrix((int*)A, n, n);
	
	// Lies die zweite Matrix ein:
	read_matrix((int*)B, n, n);

	// Initialisiere E und children
	for(int z = 0; z<n; ++z) {
		for(int s = 0; s<n; ++s) {
			E[z][s] = -1;
			children[z][s] = 0;
		}
	}


	// Schleife zur parallelen Berechnung
	while(currentchildren > 0 || jobs < n*n) {
		// Falls gerade ein Prozess frei und was zu tun ist,
		// weise neue Aufgabe zu
		if(currentchildren < maxchildren && jobs < n*n) {
			// Suche freien Eintrag auf sehr ineffektive Art und Weise -
			// O(n^2) in Laudau-Notation - fuer diese Aufgabe ist das aber schon OK
			int zfrei,sfrei;
			for(int z=0; z<n; ++z) {
				for(int s=0; s<n; ++s) {
					if(E[z][s] == -1 && children[z][s] == 0) {
						zfrei = z;
						sfrei = s;
						z=s=n; // Verlasse Schleifen
					}
				}
			}
			
			// Bereite die Argumente fuer vmult vor
			vmultargv[0] = "vmult"; // Programmname
			vmultargv[2*n+1] = NULL; // Terminierung der Argumentliste
			for(int i = 0; i<n; i++)	{
				// Eintrag i der Zeile zfrei von A
				snprintf(vmultargv[i+1], 20, "%d", A[zfrei][i]);		
				// Eintrag i der Spalte sfrei von B
				snprintf(vmultargv[i+n+1], 20, "%d", B[i][sfrei]);
			}

			// Jetzt liegt die korrekte Argumentliste vor, nun koennen wir
			// endlich forken
			pid_t pid = fork();
			if(pid < 0)	perror("fork")	, exit(5);
			if(pid == 0) {
				// Wir sind das Kind
				// zu Testzwecken kann man hier noch ein sleep(1); einbauen
				execvp("vmult", vmultargv);
				// Wenn exec zurueckkehrt, ist ein Fehler aufgetreten
				perror("execvp");
				exit(255);
			} else {
				// Wir sind der Elternprozess
				// PID speichern
				children[zfrei][sfrei] = pid;
				// Kindzaehler erhoehen
				++currentchildren;
				// Jobs erhoehen
				++jobs;
			}
		}

		// Falls alle Prozesse belegt sind oder es keine neuen
		// Aufgaben mehr gibt, warten wir auf ein Kind
		if(currentchildren == maxchildren || jobs == n*n) {
			int status, signal_nummer, exit_status;
			pid_t pid = wait(&status);
			if(pid < 0) perror("wait"), exit(6);

			// Signalnummer und Exitstatus extrahieren. Siehe Skript bzw. Manpage.
			// Alternativ ginge das ueber die Makros WIFEXITED, WEXITSTATUS, etc.
			// Diese stehen in wait(3HEAD)
			signal_nummer = status & 0x7f;
			exit_status = (status >> 8) & 0xff;

			// Finde den passenden Eintrag zur PID auf sehr ineffektive Art und Weise -
			// O(n^2) in Laudau-Notation - fuer diese Aufgabe ist das aber schon OK
			int zeile, spalte;
			for(int z = 0; z<n; ++z) {
				for(int s = 0; s<n; ++s) {
					if(children[z][s] == pid) {
						zeile = z;
						spalte = s;
						z=s=n;
					}
				}
			}

			if(signal_nummer != 0 || exit_status == 255) {
				fprintf(stderr, "Fehler bei der Matrixberechnung (%d/%d): Signal %d, Exitstatus %d\n", zeile, spalte, signal_nummer, exit_status);
				exit(7);
			} else {
				// Jetzt haben wir Zeile und Spalte
				E[zeile][spalte] = exit_status;
				// Anzahl Kinder dekrementieren
				--currentchildren;
			}
		}
	}

	print_matrix((int*)E, n, n);
}