Distributed Algorithms, Chang and Roberts

C Code

Main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include “list.c”

void main()
{
int i,megethos,id,num_arx,*arx,*temp,j,vrethike,k,messages;
char state[5];
typos_deikti prodeiktis;
typos_deikti *riza;

        printf(“Doste to megethos tou daktiliou:\n”);
scanf(“%d”,&megethos);

        riza=malloc(megethos*sizeof(typos_deikti));
dimiourgia(riza);
prodeiktis=NULL;

        sprintf(state,”sleep”);
id = 1;
eisagogi(riza,state,id,prodeiktis);
prodeiktis = *riza;

        for(i=0;i<megethos-1;i++)
{
id++;
//id=id*rand();
eisagogi(riza,state,id,prodeiktis);
proxorise(&prodeiktis);
}

        prodeiktis = *riza;
for(i=0;i<megethos;i++)
{
printf(“Komvos %d : “,i);
printf(“ID = %d “,node_id(prodeiktis));
printf(“State = %s\n”,periexomeno(prodeiktis));
proxorise(&prodeiktis);
}

        printf(“\nEpilextikan tixaia oi parakato komvoi arxikopoiites:\n”);
num_arx=fmod(rand(),megethos);
arx=malloc(num_arx*sizeof(int));
temp=malloc(num_arx*sizeof(int));
for(i=0;i<num_arx;i++)
{
arx[i] = fmod(rand(),megethos);
for(j=0;j<num_arx;j++)
{
if(temp[j]==arx[i])
{
vrethike=1;
break;
}
else
{
vrethike=0;
}
}

            if(vrethike==0)
{
temp[i] = arx[i];
printf(“%d\n”,arx[i]);

                prodeiktis = *riza;
for(k=0;k<arx[i];k++)
{
proxorise(&prodeiktis);
}
sprintf(prodeiktis->state,”candi”);
}
else
{
i–;
}
}

        ////////////////TEST – NODE CANDIDATES//////////
/*prodeiktis = *riza;
for(i=0;i<megethos;i++)
{
sprintf(prodeiktis->state,”sleep”);
proxorise(&prodeiktis);
}

        prodeiktis = *riza;
for(i=0;i<3;i++)
{
sprintf(prodeiktis->state,”candi”);
proxorise(&prodeiktis);
}*/
///////////////////////////////////////////

        printf(“\n”);
//////////////////DEBUG////////////////////////////
prodeiktis = *riza;
for(i=0;i<megethos;i++)
{
printf(“Komvos %d : “,i);
printf(“ID = %d “,node_id(prodeiktis));
printf(“State = %s\n”,periexomeno(prodeiktis));
proxorise(&prodeiktis);
}
//////////////////DEBUG////////////////////////////
vrethike =0;
messages=0;
prodeiktis = *riza;
while(vrethike==0)
{
for(i=0;i<megethos-1;i++)
{
//ean den einai arxikopoiitis apla proothei to minima
if(strcmp(prodeiktis->state,”sleep”)==0)
{
if(prodeiktis->temp!=prodeiktis->tok)
{
vrethike = send(prodeiktis->temp ,prodeiktis->epomenos);
messages++;
}
}
//ean einai arxikopoitis
if(strcmp(prodeiktis->state,”candi”)==0)
{
vrethike = send(prodeiktis->tok ,prodeiktis->epomenos);
messages++;
if(prodeiktis->temp>prodeiktis->tok)
{
prodeiktis->tok = prodeiktis->temp;
}
}
if(vrethike==1)
{
break;
}
proxorise(&prodeiktis);
}

            if(vrethike==1)
{
break;
}

            //////Kikliki Lista -> o teleutaios komvos send sti riza////////

            //ean den einai arxikopoiitis apla proothei to minima
if(strcmp(prodeiktis->state,”sleep”)==0)
{
if(prodeiktis->temp!=prodeiktis->tok)
{
vrethike = send(prodeiktis->temp ,*riza);
messages++;
}
}
//ean einai arxikopoitis
if(strcmp(prodeiktis->state,”candi”)==0)
{
vrethike = send(prodeiktis->tok ,*riza);
messages++;
if(prodeiktis->temp>prodeiktis->tok)
{
prodeiktis->tok = prodeiktis->temp;
}
}

            if(vrethike==1)
{
break;
}

            ///Epistrofi sti riza – ksekinaei o epomenos kiklos me tis nees times
prodeiktis = *riza;
if(strcmp(prodeiktis->state,”candi”)==0)
{
if(prodeiktis->temp>prodeiktis->tok)
{
prodeiktis->tok = prodeiktis->temp;
}
}
}

        printf(“\n”);
//////////////////APOTELESMATA////////////////////////////
prodeiktis = *riza;
for(i=0;i<megethos;i++)
{
if(strcmp(prodeiktis->state,”leade”)==0)
{
printf(“Komvos %d : “,i);
printf(“ID = %d “,node_id(prodeiktis));
printf(“State = %s\n”,periexomeno(prodeiktis));
}
proxorise(&prodeiktis);
}

        printf(“Arithmos Minimaton = %d\n\n”,messages);
//////////////////APOTELESMATA////////////////////////////
}

List.c

/*************************************************************************
Αρχείο Υλoπoίησης    : list.c
Σκοπός                : Υλοποίηση με δείκτες ΑΤΔ, κυκλικά Συνδεδεμένη Λίστα
**************************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef char   typos_stoixeiou;
typedef struct typos_komvou *typos_deikti;
typedef struct typos_komvou
{
typos_stoixeiou state[5];
typos_deikti epomenos;
int id;
int tok;
int temp;
};
typos_deikti lista;

void dimiourgia(typos_deikti *lista);
int keni(typos_deikti lista);
void proxorise(typos_deikti *p);
typos_stoixeiou *periexomeno(typos_deikti p);
void diagrafi(typos_deikti *lista, typos_deikti prodeiktis);

void eisagogi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id,typos_deikti prodeiktis);
void eisagogi_arxi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id);
void eisagogi_meta(typos_deikti prodeiktis,typos_stoixeiou *stoixeio,int id);

int node_id(typos_deikti p);
int send(int tok,typos_deikti p);

void dimiourgia(typos_deikti *lista)
{
/*
*    Πρo:         καμία
*    Μέτά:         Δημιoυργία κενής συνδεδεμένης λίστα
*/
*lista = NULL;
}

int keni(typos_deikti lista)
{
/*
*    Πρo:         Δημιoυργία λίστας
*    Μέτά:        επιστρέφει 1 αν η λίστα είναι κενή, διαφoρετικά 0
*/
return ( lista == NULL );
}

void proxorise(typos_deikti *p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        Ο δείκτης p δείχνει στον επόμενο κόμβο στην λίστα
*/
*p = (*p)->epomenos;
}

typos_stoixeiou *periexomeno(typos_deikti p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        επιστρέφει τα δεδομένα στον κόμβο που δείχνει ο p
*/
return (p->state);
}

int node_id(typos_deikti p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        επιστρέφει τα δεδομένα στον κόμβο που δείχνει ο p
*/
return (p->id);
}

int send(int tok,typos_deikti p)
{
/*
*    Πρo:         Ο δείκτης p δείχνει ένα κόμβο στην λίστα
*    Μέτά:        επιστρέφει τα δεδομένα στον κόμβο που δείχνει ο p
*/
if(p->id == tok)
{
sprintf(p->state,”leade”);
return 1;
}
p->temp = tok;

    return 0;

}

void eisagogi_meta(typos_deikti prodeiktis,typos_stoixeiou *stoixeio,int id)
{
/*
*    Πρo:         Δημιoυργία λίστα
*    Μέτά:         Ο κόμβος με τα δεδομένα stoixeio έχει εισαχθεί
*                μετά τον κόμβο που δείχνει ο prodeiktis
*/    int i;
typedef struct
{
typos_stoixeiou state[5];
typos_deikti epomenos;
int id;
int tok;
int temp;
}typos_komvou;
typos_deikti prosorinos; /*Δείχνει τον νέο κόμβο που πρόκειτε να εισαχθεί*/

    prosorinos = (typos_deikti)malloc(sizeof(typos_komvou));
if ( prosorinos == NULL )
{
fprintf(stderr,”Η μνήμη είναι γεμάτη\n”);
exit(-1);
}
for(i=0;i<5;i++)
prosorinos->state[i] = stoixeio[i];
prosorinos->state[i] = ‘\0’;
prosorinos->id = id;
prosorinos->tok = id;
prosorinos->temp = id;
prosorinos->epomenos = prodeiktis->epomenos;
prodeiktis->epomenos = prosorinos;
}

void eisagogi_arxi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id)
{
/*
*    Πρo:         O δείκτης p δείχνει ττην αρχή της λίστας
*    Μέτά:         Ο κόμβος με τα δεδομένα stoixeio έχει εισαχθεί
*                πριν τον κόμβο που εδείχνει ο p, ο p δείχνει πλέον την νέα αρχή της λίστας
*/
int i;
typedef struct
{
typos_stoixeiou state[5];
typos_deikti epomenos;
int id;
int tok;
int temp;
}typos_komvou;
typos_deikti prosorinos; /*Δείχνει τον νέο κόμβο που πρόκειτε να εισαχθεί*/

    prosorinos = (typos_deikti)malloc(sizeof(typos_komvou));
if ( prosorinos == NULL )
{
fprintf(stderr,”Η μνήμη είναι γεμάτη\n”);
exit(-1);
}
for(i=0;i<5;i++)
prosorinos->state[i] = stoixeio[i];
prosorinos->state[i] = ‘\0’;
prosorinos->id = id;
prosorinos->tok = id;
prosorinos->temp = id;
prosorinos->epomenos = *lista;
*lista = prosorinos;
}

void eisagogi(typos_deikti *lista,typos_stoixeiou *stoixeio,int id,typos_deikti prodeiktis)
{
/*
*    Πρo:         Ο prodeiktis δείχνει ένα κόμβο στην λίστα ή είναι NULL
*    Μέτά:         Αν ο prodeiktis είναι NULL τοτε ο κόμβος με τα δεδομένα
*                stoixeio έχει εισαχθεί στην αρχή της λίστας αλλιώς ο εισάγεται μετά
*                τον κόμβο που δείχνει ο prodeiktis
*/
if (keni(prodeiktis)) /*εισαγωγή στην αρχή της λίστας*/
eisagogi_arxi(lista,stoixeio,id);
else
eisagogi_meta(prodeiktis,stoixeio,id);
}