run.c

#include "run.h"
#define uint_64 unsigned long long

void put_in_buffer_1(char *c, struct buffer_rc *ptr){
    /*
    Ajout d'un element dans le buffer 1
    Pré : *c un pointeur de type 'char', *ptr un pointeur vers une structure 'buffer_rc'
    Post : /
    */
    ptr->tab[ptr->head] = malloc(sizeof(char)*(strlen(c) + 1)); //allocation de la taille de la chaine
    if(ptr->tab[ptr->head] ==NULL){return;}
    strcpy(ptr->tab[ptr->head],c);          
    ptr->len++;                             //augmenter l'espace occupé de 1
    ptr->head = (ptr->head + 1)%ptr->size;  //faire avancer le pointeur de 1 (modulo N pour ne pas dépasser N)
}

char *get_from_buffer_1(struct buffer_rc *ptr){
    /*
    Récupération d'une chaine de caractères dans le buffer 1
    Pré : *ptr un pointeur vers une structure 'buffer_rc'
    Post : un pointeur vers la chaine de caractères récupérée
    */
    char *result;
    result = ptr->tab[ptr->tail];
    ptr->tab[ptr->tail] = NULL;
    ptr->len--;                     
    ptr->tail = (ptr->tail + 1)%ptr->size;

    return result;
}

void put_in_buffer_2(struct queue *ptr, struct buffer_cw *buf){
    /*
    Ajout d'un element dans le buffer 2
    Pré : *ptr un pointeur vers une liste, *buf un pointeur vers uen structure 'buffer_cw'
    Post : /
    */
    buf->tab[buf->head] = ptr;
    buf->len++;        
    buf->head = (buf->head + 1)%buf->size;
}

queue_t *get_from_buffer_2(struct buffer_cw *buf){
    /*
    récupération d'une liste dans le buffer 2
    Pré : *buf un pointeur vers une structure 'buffer_cw'
    Post : un pointeur vers la liste récupérée dans le buffer 'buf'
    */
    struct queue *result;
    result = buf->tab[buf->tail];
    buf->tab[buf->tail] = NULL;
    buf->len--;  //diminue l'espace occupé par le buffer
    buf->tail = (buf->tail + 1)%buf->size;

    return result;
}

int is_div(uint_64 number, uint_64 i) {
    /* 
    Vérifie si i est un diviseur de number 
    Pré : number et i des entiers
    Post : 1 si number est divisible par i, 0 sinon
    */
    if (i == 0){return 0;}

    return (number % i == 0) ;
}

uint_64 modpow (uint_64 base, uint_64 exp, uint_64 mod){
    /* 
    algorithme d'exponentiation modulaire (calcul de puissances entières)
    Pré : base, exp et mod des entiers
    Post : renvoie base^exp modulo (mod)
    */
    uint_64 result = 1;
    while (exp > 0)
    {
        if ((exp & 1) > 0) {
            result = (result * base) % mod;
        }
        exp >>= 1;      
        base = (base * base) % mod;
    }
    return result;
}

uint_64* randomiser (int k, uint_64 N){
    /* 
    Génération de nombres aléatoires
    Pré : k et N des entiers
    Post : un pointeur vers k entiers compris entre 1 et N 
    */
    uint_64 *result;
    result = malloc(sizeof(uint_64)*k);
    srand(time(NULL));                  // initialisation du générateur de nombre aléatoire par la fonction time
    for (int i = 0; i < k; i++)
    {
        result[i] = rand() % (N-1) +1;  
    }
    return result;
}

int is_prime (uint_64 number){
    /*
    Vérifie si number est premier au moyen du test de Fermat
    Pré : number un entier
    Post : 1 si number est premier, 0 sinon
    */
    uint_64 *random;
    int k;
    if (number <= 20){k = number-1;}
    else{k = 20;}
    random = randomiser(k,number); // génère k nombres aléatoires
    for (int i = 0; i < k; i++)
    {
        if (modpow(random[i],number-1,number) == 1)  //test de Fermat
        {
            continue;                         //tant qu'on pas montré que number était composé on continue   
        }
        else{
            free(random);
            return 0;            
            }

    }
    free(random);
    return 1;
}

void enqueue(queue_t* q, uint_64 val){
    /* 
    Ajoute un nouveau noeud contenant val à la queue
    Pré : q un pointeur vers la liste de type 'queue_t', val un entier
     */
    struct node *ptr;
    ptr = malloc(sizeof(node_t));
    if (ptr == NULL){return;}
    ptr->value = val;
    if (q->size == 0)               //cas où la liste est vide
    {
        q->tail = ptr;
        ptr->next = ptr;
    }
    else{                           //cas de base
        ptr->next = q->tail->next;
        q->tail->next = ptr;
    }
    q->size++;
}

queue_t* prime_divs(uint_64 number){
    /*
    calcule et crée la liste des diviseurs premiers d'un nombre
    Pré : number un entier
    Post : un pointeur de type 'queue_t' vers la liste des diviseurs premiers de nummber
    */
    queue_t *ptr;              //création de la liste
    ptr = malloc(sizeof(queue_t));
    if (ptr == NULL){
        free(ptr);
        return NULL;}
    ptr->size = 0;
    ptr->final = 0;
    for (uint_64 i = 2; i <= number/2; i++){
        if (is_div(number, i) && is_prime(i) == 1){
            enqueue(ptr,i);     //si i est diviseur de number et premier, il est ajouté à la liste
        }
    }
    enqueue(ptr,number);        //le nombre à factoriser est également rajouté à la liste

    return ptr;

}

void *writing(void *param){
    /*
    Ecriture dans le fichier de sortie
    Pré : param un pointeur de type 'void'
    Post : //
    */
    struct buffer_cw *param1 = (struct buffer_cw *) param;  
    int stop = 0;   //compteur des threads de calculs ayant fini de travailler

    while(1){
        sem_wait(&full2);
        pthread_mutex_lock(&mutex2);
        queue_t *pr_divs = get_from_buffer_2(param);    //récupération de la liste de diviseurs
        pthread_mutex_unlock(&mutex2);
        sem_post(&empty2);

        if (pr_divs->final == 1)        //si la liste est finale (insérée par un thread de calcul en fin de traavil)
        {
            if (stop == N-1)            //si tous les threads de calcul ont fini
            {           
                free(pr_divs);
                free(param1->tab);
                return NULL;
            }
            free(pr_divs);
            stop++;                     //un thread de calcul supplémentaire a fini de travailler
        }
        else
        {
            FILE *file2 = param1->file2;
            node_t *current;
            current = pr_divs->tail;
            current = current->next;
            fprintf(file2,"%llu",current->value);    //écriture du nombre à factoriser
            node_t *toFree = current;
            current = current->next;

            for (int i = 1; i < pr_divs->size; i++)
            {
                free(toFree);
                toFree = current;
                fprintf(file2," %llu",current->value);   //écriture des diviseurs premiers
                current = current->next;
            }
            fputc('\n',file2);
            free(pr_divs->tail);
            free(pr_divs);
        }
    }
    return NULL;
}

void *calculating(void *param){
    /*
    Récupère les chaines du buffer 1, effectue les calculs et replace les listes de diviseurs dans le buffer 2
    Pré : param, un pointeur de type 'void'
    Post : /
    */
    struct buffer_rccw *param1 = (struct buffer_rccw *) param;
    struct buffer_rc *buffer_1 = param1->struct1;
    struct buffer_cw *buffer_2 = param1->struct2;

    while(1){
        sem_wait(&full1);
        pthread_mutex_lock(&mutex1);
        char *chaine = get_from_buffer_1(buffer_1);     //Récupération de la chaine
        pthread_mutex_unlock(&mutex1);
        sem_post(&empty1);
        
        if (strcmp("stop",chaine) == 0) // arrêt des threads de calcul
        {
            struct queue *final;
            final = malloc(sizeof(queue_t));
            if (final == NULL){return NULL;}
            final->final = 1;           //pour indiquer au thread d'écriture qu'il a fini de travailler
            
            sem_wait(&empty2);
            pthread_mutex_lock(&mutex2);
            put_in_buffer_2(final,buffer_2);    //insertion dans le buffer 2
            pthread_mutex_unlock(&mutex2);
            sem_post(&full2);
            
            free(chaine);

            return NULL;
        }
        uint_64 number;
        number = strtoll(chaine,NULL,0); //conversion de la chaine en long long
        if (number != 0 || strcmp("0\n",chaine) == 0)   //au cas où la conversion échoue
        {
        struct queue *pr_divs;
        pr_divs = prime_divs(number);

        sem_wait(&empty2);
        pthread_mutex_lock(&mutex2);
        put_in_buffer_2(pr_divs,buffer_2);      //insertion dans le buffer 2
        pthread_mutex_unlock(&mutex2);
        sem_post(&full2);

        free(chaine);
        }
    }
    return NULL;
}

void *reading (void *param){
    /*
    Fonction qui lit un fichier d'entrée
    Pré : param, un pointeur de type 'void'
    Post : /
    */
    struct buffer_rc *param1= (struct buffer_rc *) param;
    char chaine[30];
    FILE *input;
    input = param1->file1;

    while (fgets(chaine,30,input) != NULL){

        sem_wait(&empty1);
        pthread_mutex_lock(&mutex1);
        put_in_buffer_1(chaine,param1);            //insère chaque ligne dans le buffer 1
        pthread_mutex_unlock(&mutex1);
        sem_post(&full1);
    }

    for (int i = 0; i < N; i++)
    {
        sem_wait(&empty1);
        pthread_mutex_lock(&mutex1);
        put_in_buffer_1("stop\0",param1);            //insère autant de chaine "stop" que de threads de calcul
        pthread_mutex_unlock(&mutex1);
        sem_post(&full1);
    }
    return NULL;
}

void sem_1_initializer(struct buffer_rc *buf){
    /*
    Initialisation du sémaphore du buffer 1
    Pré : buf, pointeur vers une structure 'buffer_rc'
    Post : /
    */
    pthread_mutex_init(&mutex1,NULL);
    sem_init(&empty1,0,buf->size);
    sem_init(&full1,0,0);

}

void sem_2_initializer (struct buffer_cw *buf){
    /*
    Initialisation du sémaphore du buffer 2
    Pré : buf, pointeur vers une structure 'buffer_cw'
    Post : /
    */
    pthread_mutex_init(&mutex2,NULL);
    sem_init(&empty2,0,buf->size);
    sem_init(&full2,0,0);
}


struct buffer_rc * buff_init_1(FILE *file1){
    /*
    Initialisation du buffer 1
    Pré : file1, un pointeur de type 'FILE'
    Post : pointeur vers une structure 'buffer_rc'
    */
    struct buffer_rc *ptr1;
    ptr1 = malloc(sizeof(struct buffer_rc));
    if (ptr1 == NULL){
        free(ptr1);
        return NULL;}
    ptr1->tab = malloc(2*N*sizeof(char*));  //tableau de taille 2*N
    ptr1->size = 2*N;
    ptr1->len = 0;
    ptr1->head = 0;
    ptr1->tail = 0;
    ptr1->file1 = file1;

    return ptr1;
}

struct buffer_cw * buff_init_2(FILE *file2){
    /*
    Initialisation du buffer 2
    Pré : file1, un pointeur de type 'FILE'
    Post : pointeur vers une structure 'buffer_cw'
    */
    struct buffer_cw *ptr2;
    ptr2 = malloc(sizeof(struct buffer_cw));
    if (ptr2 == NULL){return NULL;}
    ptr2->tab = malloc(2*N*sizeof(struct queue*));  //tableau de taille 2*N
    ptr2->size = 2*N;
    ptr2->len = 0;
    ptr2->head = 0;
    ptr2->tail = 0;
    ptr2->file2 = file2;

    return ptr2;
}

struct buffer_rccw *buff_init_12(struct buffer_rc *ptr1,struct buffer_cw *ptr2){
    /* 
    Initialisation d'une structure contenat des pointeurs vers les deux buffer pouvant être passée en argument à 'calculating'
    Pré : ptr1 un pointeur vers une structure 'buffer_rc' et ptr2 un pointeur vers une structure 'buffer_cw'
    Post : pointeur vers une structure 'buffer_rccw'
    */
    struct buffer_rccw *ptr3;
    ptr3 = malloc(sizeof(struct buffer_rccw));
    if (ptr3 == NULL){return NULL;}
    ptr3->struct1 = ptr1;       //pointeur vers le buffer 1
    ptr3->struct2 = ptr2;       //pointeur vers le buffer 2

    return ptr3;
}

int thread_create_join(struct buffer_rc *ptr1,struct buffer_cw *ptr2,struct buffer_rccw *ptr3){
    /*
    Création et point de rencontre des threads de lecture, calcul et écriture
    Pré : ptr1 un pointeur vers une structure buffer_rc, ptr2 un pointeur vers une strucure 'buffer_cw', ptr3 un pointeur vers une structure buffer_rccw
    Post : -1 en cas d'erreur, 0 sinon
    */
    pthread_t reader;
    pthread_t calculators[N];
    pthread_t writer;
    int err;
    err=pthread_create(&reader,NULL,&reading,ptr1); //le buffer 1 est passé en argument à 'reading'
    if(err != 0){return -1;}

    for (int i = 0; i < N; i++)     //N threads de calcul
    {
        err=pthread_create(&calculators[i],NULL,&calculating,ptr3); //les deux buffers sont passés en argument à 'calculating'
        if(err != 0){return -1;}
    }
    err = pthread_create(&writer,NULL,&writing,ptr2); //le buffer 2 est passé en argument à 'writing'
    if(err != 0){return -1;}

    err = pthread_join(reader,NULL);
    if(err != 0){return -1;}
    for (int i = 0; i < N; i++)
    {
        err = pthread_join(calculators[i],NULL);
        if(err != 0){return -1;}
    }
    err = pthread_join(writer,NULL);
    if(err != 0){return -1;}

    return 0;
}

void mut_sem_destroy(void){
    /* 
    Destruction des sémaphores
    Pré : /
    Post : /
    */
    pthread_mutex_destroy(&mutex1);
    pthread_mutex_destroy(&mutex2);
    sem_destroy(&full1);
    sem_destroy(&full2);
    sem_destroy(&empty1);
    sem_destroy(&empty2);
}

int run (char *input,char *output, int n_threads){
    /* 
    Fonction qui gère l'exécution du programme
    Pré : input et output des chaines de caractères, n_threads un entier
    Post : -1 en cas d'erreur, 0 sinon
    */
    N = n_threads;
    printf("Lancement du programme avec %d threads \n",N);

    FILE *file1;
    FILE *file2;

    file1 = fopen(input,"r");
    if (file1 == NULL){
        printf("Sorry, file %s doesn't exist ): \n",input);
        return -1;}

    file2 = fopen(output,"w+");
    if (file2 == NULL){
        fclose(file1);
        return -1;
    }
    struct buffer_rc *ptr1 = buff_init_1(file1);
    struct buffer_cw *ptr2 = buff_init_2(file2);
    struct buffer_rccw *ptr3 = buff_init_12(ptr1,ptr2);

    sem_1_initializer(ptr1);
    sem_2_initializer(ptr2);
    int err;
    err = thread_create_join(ptr1,ptr2,ptr3);
    mut_sem_destroy();

    fclose(file1);
    fclose(file2);
    free(ptr1->tab);
    free(ptr1);
    free(ptr2);
    free(ptr3);

    if (err == -1){return -1;}
    return EXIT_SUCCESS;
}