Code:
#include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<list>
#include<pthread.h>
#include<cstring>
using namespace std;
pthread_mutex_t listlock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t pathlock = PTHREAD_MUTEX_INITIALIZER;
#define _NODES 8
typedef struct{
int id;
char msg[10];
} thread_parm_t;
struct Node
{
pthread_mutex_t f_lock;
thread_parm_t *data;
vector<int> edges;
bool msg_received;
};
list<struct Node*> sub_graph;
//list<Node*>::iterator it;
char get_node_name(int );
void find_neighbours(struct Node* );
void node_alloc(thread_parm_t *p) // allocate the object
{
struct Node *nd;
if((nd = (struct Node *)malloc(sizeof(struct Node))) != NULL)
{
if(pthread_mutex_init(&nd -> f_lock, NULL) != 0)
{
free(nd);
exit(1);
}
//*** locking
pthread_mutex_lock(&nd -> f_lock);
nd -> data = p;
nd -> msg_received = true;
find_neighbours(nd);
//*** unlocking
pthread_mutex_unlock(&nd -> f_lock);
//*** locking
pthread_mutex_lock(&listlock);
sub_graph.push_back(nd);
//*** unlocking
pthread_mutex_unlock(&listlock);\
return;
}
else{
cout << "Memory allocation failed...\n";
exit(1);
}
}
int path[_NODES][_NODES] = {
{ 0, 1, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 1, 1, 0, 0, 0 },
{ 1, 0, 0, 1, 0, 1, 0, 0 },
{ 1, 1, 1, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 1, 0, 1, 1 },
{ 0, 0, 0, 0, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 1, 1, 0 }
};
char get_node_name(int index)
{
char c;
switch(index)
{
case 0: c = 'A';
break;
case 1: c = 'B';
break;
case 2: c = 'C';
break;
case 3: c = 'D';
break;
case 4: c = 'E';
break;
case 5: c = 'F';
break;
case 6: c = 'G';
break;
case 7: c = 'H';
break;
}//end of switch
return c;
}
void find_neighbours(struct Node *nd)
{
//*** locking
pthread_mutex_lock(&pathlock);
pthread_mutex_lock(&nd -> f_lock);
//***
int index = nd -> data -> id;
for(int j=0; j < _NODES; j++){
if(path[index][j]){
nd->edges.push_back(j);
}
}//end of for
//*** unlocking
pthread_mutex_unlock(&nd -> f_lock);
pthread_mutex_unlock(&pathlock);
//***
}
struct Node* get_subgraph_node(int index)
{
struct Node* nd;
//*** locking
pthread_mutex_lock(&listlock);
//***
list<Node*>::iterator it;
for(it=sub_graph.begin(); it!=sub_graph.end(); it++)
{
//*** locking
pthread_mutex_lock(&(*it) -> f_lock);
//***
if((*it) -> data -> id == index)
{
if((nd = (struct Node *)malloc(sizeof(struct Node))) != NULL){
//*** locking
pthread_mutex_lock(&nd -> f_lock);
//***
nd -> data -> id = (*it) -> data -> id;
nd -> edges = (*it) -> edges;
nd -> msg_received = (*it) -> msg_received;
//*** unlocking
pthread_mutex_unlock(&nd -> f_lock);
pthread_mutex_unlock(&listlock);
//***
return nd;
}
}
}//end of for
//*** unlocking
pthread_mutex_unlock(&listlock);
//***
return NULL;
}
void print_sub_graph()
{
list<Node*>::iterator it;
for(it=sub_graph.begin(); it!=sub_graph.end(); it++)
{
cout << " MSG Received MESSAGE\n\n";
cout << " " << (*it)->msg_received; cout << " ";
cout << (*it)->data->msg;
cout << "\n\n... finding neighbours ...\n";
int cap = (*it)->edges.size();
cout << "... " << cap << " edges found ...\n";
for(int index = 0; index < cap; index++){
cout << " " << get_node_name((*it)->data->id) << " --> " << get_node_name((*it)->edges[index]);
cout << endl;
}
cout << "\n\n\n";
}
}
bool search_subgraph(int index)
{
list<Node*>::iterator it;
pthread_mutex_lock(&listlock);
for(it=sub_graph.begin(); it!=sub_graph.end(); it++)
{
pthread_mutex_lock(&(*it) -> f_lock);
if((*it) -> data -> id == index)
pthread_mutex_unlock(&(*it) -> f_lock);
pthread_mutex_unlock(&listlock);
return true;
}
pthread_mutex_unlock(&listlock);
return false;
}
void *thr_func(void *arg)
{
// find adjacent vertices of the current node, if they do not exist in the sub_graph
// allocate memory and new vertices to the sub_graph list, then create new thread
thread_parm_t *tmp;
thread_parm_t *p = (thread_parm_t *)arg;
struct Node *nd, *vertex;
struct timespec in, out;
int index, random;
in.tv_sec = 0;
in.tv_nsec = 100000;
vertex = NULL;
// no locking for getting size()
while(1)
{
pthread_t tid;
if((sub_graph.size() != _NODES))
{
nd = get_subgraph_node(p -> id);
//get a random neighbour
srand((unsigned)time(0));
//*** locking
pthread_mutex_lock(&nd -> f_lock);
//***
index = rand() % (int)nd -> edges.size();
random = nd -> edges.at(index);
//*** unlocking
pthread_mutex_unlock(&nd -> f_lock);
//***
if(!search_subgraph(random))
{
//new vertex allocation
tmp -> id = random;
for(int i = 0; i < 10; i++)
tmp -> msg[i] = p -> msg[i];
node_alloc(tmp);
pthread_create(&tid, NULL, thr_func, (void *)tmp);
}
else
{/*
vertex = get_subgraph_node(random);
if(vertex != NULL){
//sleep(1);
nanosleep(&in, &out);
continue;
}*/
}
}
else
{
cout << "\n\nmessage disseminated to " << sub_graph.size() << " nodes\n";
//*** destroying structure lock
//***
print_sub_graph();
exit(0);
}//end of else
}//while
}
int main(int argc, char **argv)
{
struct Node *nd;
pthread_t tid;
thread_parm_t *parm = NULL;
//sending message to the first node
parm = (thread_parm_t *)malloc(sizeof(thread_parm_t));
strcpy(parm->msg, "purple");
parm->id = 0;
node_alloc(parm);
pthread_create(&tid, NULL, thr_func, (void *)parm);
//Only waiting for the first thread to terminate
pthread_join(tid, NULL);
return 0;
}
