Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>
/* Stampa i valori dell'array passato per copia. */
void display(int array[], int length)
{
int i;
printf(">");
for (i = 0; i < length; i++)
printf(" %d", array[i]);
printf("\n");
}
/* Merge per i processi padri */
void merge(int *left, int llength, int *right, int rlength)
{
/* Memoria temporanea per i sottoarray. */
int *ltmp = (int *) malloc(llength * sizeof(int));
int *rtmp = (int *) malloc(rlength * sizeof(int));
/*
* Puntatori agli elementi di cui fare il merge nella memoria temporanea.
*/
int *ll = ltmp;
int *rr = rtmp;
int *result = left;
/*
* Copia degli elementi dell'array di cui fare il merge nella memoria temporanea.
*/
memcpy(ltmp, left, llength * sizeof(int));
memcpy(rtmp, right, rlength * sizeof(int));
while (llength > 0 && rlength > 0) {
if (*ll <= *rr) {
/*
* Mette l'elemento puntato sulla sinistra nell'array result
* se è minore o uguale a quello puntato sulla destra.
*/
*result = *ll;
++ll;
--llength;
} else {
/*
* Mette l'elemento puntato sulla destra nell'array result
* se è minore o uguale a quello puntato sulla sinistra.
*/
*result = *rr;
++rr;
--rlength;
}
++result;
}
/* Tutti gli elementi dell'array di destra o sinistra sono stati copiati nell'array result.
* Mette i rimanenti dall'array di sinistra o destra nel'array result.
*/
if (llength > 0)
while (llength > 0) {
/* Metto quelli del temporaneo di sinistra. */
*result = *ll;
++result;
++ll;
--llength;
}
else
while (rlength > 0) {
/* Metto quelli del temporaneo di destra. */
*result = *rr;
++result;
++rr;
--rlength;
}
/* Rilascio la memoria dei temporanei. */
free(ltmp);
free(rtmp);
}
void mergesort(int array[], int length, int* lcp, int* lpc,int* rcp, int* rpc)
{
/* Indice di mezzo*/
int middle;
//read array passed from the parent?
/*
* Puntatori all'inizio del primo e del secondo array su cui fare la merge.
*/
int *left, *right;
/* Lunghezza del sottoarray di sinistra. */
int llength;
int lchild = -1;
int rchild = -1;
int status;
if (length <= 1)
return;
middle = length / 2;
llength = length - middle;
write(lpc[1], array , llength);
write(rpc[1], array+middle+1 , length-llength);
lchild = fork();
if (lchild < 0) {
perror("fork");
exit(1);
}
if (lchild == 0) { //Sottoarray di sinistra
read(lpc[0], left , llength);
display(left, llength);
mergesort(left, llength, lcp, lpc, rcp, rpc);
write(lcp[1], left, llength);
exit(0);
} else {
rchild = fork();
if (rchild < 0) {
perror("fork");
exit(1);
}
if (rchild == 0) { //Sottoarray di destra
read(rpc[0], right , middle);
//display(right, middle);
mergesort(right, middle, lcp, lpc, rcp, rpc);
write(rcp[1], right, middle);
exit(0);
}
}
waitpid(lchild, &status, 0);
read(lcp[0], left , llength);
waitpid(rchild, &status, 0);
read(rcp[0], right , middle);
merge(left, llength, right, middle);
write(lcp[1], array, middle);
write(rcp[1], array+middle+1, middle);
}
int main(int argc, char *argv[])
{
int *array = NULL;
int *arraysupp = NULL;
int length = 0;
FILE *fh;
int data;
int lcp[2], lpc[2], rcp[2], rpc[2];
int i;
if (argc != 2) {
printf("usage: %s <filename>\n", argv[0]);
return 1;
}
/* Initialize data. */
printf("attempting to sort file: %s\n", argv[1]);
fh = fopen(argv[1], "r");
if (fh == NULL) {
printf("error opening file\n");
return 0;
}
while (fscanf(fh, "%d", &data) != EOF) {
++length;
array = (int *) realloc(array, length * sizeof(int));
array[length - 1] = data;
}
fclose(fh);
printf("%d elements read\n", length);
/*
* Copy the data to be sorted from the local memory into the shared memory.
*/
// cp: for child -> parent
// pc: for parent -> child
if (pipe(lcp) == -1){
perror("pipe");
exit(1);
}
if (pipe(lpc) == -1){
perror("pipe");
exit(1);
}
if (pipe(rcp) == -1){
perror("pipe");
exit(1);
}
if (pipe(rpc) == -1){
perror("pipe");
exit(1);
}
display(array, length);
mergesort(array, length, lpc, lcp, rpc, rcp);
read(cp[0], array , length);
//display(array, length);
return 0;
}