Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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>
- /*
- * Funzione "merge" che ha in ingresso gli indici di un array con le rispettive lunghezze
- * così da fingere due array differenti.
- * Esegue un riordinamento tra le celle
- */
- void merge(float *left, int llength, float *right, int rlength){
- //memoria temporanea allocata per gli array
- float *ltmp = (float *) malloc(llength * sizeof(float));
- float *rtmp = (float *) malloc(rlength * sizeof(float));
- //puntatori in memoria temporanea ad elementi che verranno ordinati
- float *ll = ltmp;
- float *rr = rtmp;
- float *result = left;
- //Copia dei riferimenti degli array nella locazione temporanea
- memcpy(ltmp, left, llength * sizeof(float));
- memcpy(rtmp, right, rlength * sizeof(float));
- while (llength > 0 && rlength > 0){
- //merge del primo elemento di sinistra nel array principale
- //se è inferiore o uguale dell'elemento a destra
- if (*ll <= *rr) {
- *result = *ll;
- ++ll;
- --llength;
- }
- //altrimenti merge del primo elemento da destra nel array principale
- //se è più piccolo dell'elemento a sinistra
- else {
- *result = *rr;
- ++rr;
- --rlength;
- }
- ++result;//incremento indice
- }
- //tutti gli elementi sia di sinistra che di destra del array temporaneo
- //sono stati inseriti ordinati nel array principale
- //vengono ora re-immesso nel array principale il resto del array temporaneo sinistro e destro
- if (llength > 0)
- while (llength > 0) {
- *result = *ll;
- ++result;
- ++ll;
- --llength;
- }
- else
- while (rlength > 0) {
- *result = *rr;
- ++result;
- ++rr;
- --rlength;
- }
- //rilascio memoria usata per array temporanei
- free(ltmp);
- free(rtmp);
- }
- /*
- * Funzione "mergeSort" che ha in ingresso un array con la rispettiva lunghezza
- * Genera due processi, ognuno dei quali invoca questa stessa funzione "mergeSort"
- * sulla metà del array a lui assegnata.
- * Infine invoca la funzione "merge".
- */
- void mergeSort(float *arr, int l){
- //check lunghezza array per uscita ricorsione
- if(l < 2) return;
- int middle = l/2; //indice metà array
- int llength = l-middle; //lunghezza totale array a cui sottraggo l'indice mediano
- int status; //per gestire le waitpid()
- //pipe
- int pipeSx[2]; //pipe nella quale il figlio sinistro legge e scrive, assieme al padre
- pipe(pipeSx);
- int pipeDx[2]; //pipe nella quale il figlio destro legge e scrive, assieme al padre
- pipe(pipeDx);
- int lchild; //intero contenente il file descriptor del figlio sinistro
- int rchild; //intero contenente il file descriptor del figlio destro
- /*
- * inizio figlio SINISTRO
- */
- lchild = fork(); //creazione figlio
- //check corretta creazione figlio
- if (lchild < 0) {
- perror("fork");
- exit(1);
- }
- if(lchild == 0){
- float n; //intero di supporto per lettura e scrittura da pipe
- float *sx; //riferimento per array
- //allocazione memoria per contenere l'array usato dal figlio
- sx= malloc(llength * sizeof(float));
- //ciclo di lettura pipe, precedentemente scritta dal padre, con salvataggio in array
- for(int i = 0; i<llength; i++){
- read(pipeSx[0], &n, sizeof(float));
- sx[i] = n;
- }
- //esecuzione mergeSort
- mergeSort(sx, llength);
- //ciclo di scrittura pipe, che verrà letta dal padre
- for(int i = 0; i<llength; i++){
- n = sx[i];
- write(pipeSx[1], &n, sizeof(int));
- }
- free(sx); //libero memoria allocata
- exit(0);
- }
- /*
- * fine figlio SINISTRO
- */
- /*
- * codice del padre dopo aver creato il figlio sinistro
- */
- else{
- /*
- * inizio figlio DESTRO
- */
- rchild = fork(); //creazione figlio
- //check corretta creazione figlio
- if (lchild < 0) {
- perror("fork");
- exit(1);
- }
- if(rchild == 0){
- float n; //intero di supporto per lettura e scrittura da pipe
- float *dx; //riferimento per array
- //allocazione memoria per contenere l'array usato dal figlio
- dx= malloc(middle * sizeof(float));
- //ciclo di lettura pipe, precedentemente scritta dal padre, con salvataggio in array
- for(int i = 0; i<middle; i++){
- read(pipeDx[0], &n, sizeof(float));
- dx[i] = n;
- }
- //esecuzione mergeSort
- mergeSort(dx, middle);
- //ciclo di scrittura pipe, che verrà letta dal padre
- for(int i = 0; i<middle; i++){
- n = dx[i];
- write(pipeDx[1], &n, sizeof(float));
- }
- free(dx); //libero memoria allocata
- exit(0);
- }
- /*
- * fine figlio DESTRO
- */
- /*
- * continuazione del padre
- */
- //riferimenti array per contenere dati letti/scritti pipe
- float *rL, *rR;
- rL= arr;
- rR= arr+llength;
- float n,t; //interi di supporto per lettura e scrittura da pipe
- //cicli per scrivere l'array sulle pipe dei figli
- for(int i = 0; i<llength; i++){
- n = rL[i];
- write(pipeSx[1], &n, sizeof(float));
- }
- for(int i = 0; i<middle; i++){
- t = rR[i];
- write(pipeDx[1], &t, sizeof(float));
- }
- //attesa della terminazione dei figli
- waitpid(lchild,&status,0);
- waitpid(rchild,&status,0);
- //cicli per leggere le pipe dai figli
- for(int i = 0; i<llength; i++){
- read(pipeSx[0], &n, sizeof(float));
- rL[i] = n;
- }
- for(int i = 0; i<middle; i++){
- read(pipeDx[0], &t, sizeof(float));
- rR[i] = t;
- }
- //richiamo funzione per riordinare l'array
- //con i rispettivi indici passati per argomento
- merge(rL, llength, rR, middle);
- }
- }
- int main (int argc, char *argv[]) {
- //check argomenti da prompt
- if (argc != 5) {
- printf("usage: %s <filename>\n", argv[0]);
- return 1;
- }
- //riferimenti per file.txt di input e output
- FILE *file_in, *file_out;
- //apertura stream input con check a seguire
- if(atoi(argv[2]) ==1 && atoi(argv[4]) == 2){
- file_in = fopen(argv[1], "r");
- if(file_in == NULL){
- printf("Errore apertura file\n");
- return 0;
- }
- }
- else if(atoi(argv[2]) == 2 && atoi(argv[4]) == 1){
- file_in = fopen(argv[3], "r");
- if(file_in == NULL){
- printf("Errore apertura file\n");
- return 0;
- }
- }
- float *array = NULL; //array su cui inserire i dati input
- int length = 0; //lungheza array
- char data_in[1000]; //intero di supporto per inserimento da file.txt ad array
- //importazione dati da input
- while (fscanf(file_in, "%s", &data_in) != EOF) {
- float supporto = atof(data_in);
- if(supporto==0){ }
- else{
- ++length;
- array = (float *) realloc(array, length * sizeof(float));
- array[length - 1] = supporto;
- }
- }
- fclose(file_in); //chiusura file input
- printf("Elementi letti dall'input: %d\n", length);
- mergeSort(array, length);
- printf("Fine mergeSort\n");
- //scrivo l'array post mergesort su file
- if(atoi(argv[2]) ==2 && atoi(argv[4]) == 1){
- file_out = fopen(argv[1], "w");
- if(file_out == NULL){
- printf("Errore apertura file\n");
- return 0;
- }
- }
- else if(atoi(argv[2]) == 1 && atoi(argv[4]) == 2){
- file_out = fopen(argv[3], "w");
- if(file_out == NULL){
- printf("Errore apertura file\n");
- return 0;
- }
- }
- for(int i=0; i< length; i++){
- int verifica = array[i];
- if(verifica == array[i]){
- fprintf(file_out, "%i\n", (int)array[i]);
- }
- else{
- fprintf(file_out, "%1.3f\n", array[i]);
- }
- }
- printf("\n");
- fclose(file_out);
- free(array); //liberazione array
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement