Parallel Ranking List

A. First Edition

I am practicing with multi-thread.

B.The problem

The problem is quite unusual, I mean unimaginable. Say we have a link list and suddenly we are becoming crazy to want to 

dismantle our link list to make them parallel, for example, to save them in an array. However, before breaking the link

we would like to know their ranks or their position in the link list in order to put them in array in an appropriate

order. So, this is the question and more particularly, Professor Probst thinks we are rich enough to waste some

resources to assign each node in list with a thread to solve the problem in a multi-thread manner. 

The following is the original link list:

[index:1, rank:1]-->[index:2, rank:1]-->[index:4, rank:1]-->[index:0, rank:1]-->[index:3, rank:1]

Finally you break the list to make them all at same level, say in an array with appropriate rank being calculated for each.

now print the result
index:0, randk:2
index:1, randk:5
index:2, randk:4
index:3, randk:1
index:4, randk:3
Press any key to continue

There are many ways to do this job and for multi-threading environment, you have to have necessary protection of 

critical section. See one node's rank can be easily calculated by adding its next node's rank to itself provided

that its next node is not writing its rank. That is to say, you must make sure that adding rank of your next node

would not be concurrent with changing the position of your next node. Then the rank you are adding is sure the 

correct one. Using a simple lock to ensure it.

D.The major functions

E.Further improvement

F.File listing

1. main.cpp (main)

file name: main.h

#include <iostream>
#include <time.h>
#include <windows.h>

using namespace std;

const int MaxListNode=20;

struct Node
{
	int rank;
	int index;
	Node* next;
};

Node nodes[MaxListNode];
bool added[MaxListNode]={false};

Node* head=NULL, *tail=NULL;

HANDLE worker[MaxListNode];

void initialize();

void addNode(int index);

void printList();

DWORD WINAPI run(void* param);

HANDLE mutex;
int counter=0;

int demon[MaxListNode];

void interrupt(int index);

int main()
{
	srand(time(0));
	initialize();
	printList();
	for (int i=0; i<MaxListNode; i++)
	{
		ResumeThread(worker[i]);
	}
	while (counter<MaxListNode)
	{
		Sleep(0);
	}
	cout<<"now print the result\n";
	for (i=0; i<MaxListNode; i++)
	{
		cout<<"index:"<<nodes[i].index<<", randk:"<<nodes[i].rank<<endl;
	}

	return 0;
}

void printList()
{
	Node* ptr=head;
	while (ptr!=NULL)
	{
		cout<<"index:"<<ptr->index<<", rank:"<<ptr->rank<<"\n";
		ptr=ptr->next;
	}
}


void addNode(int index)
{
	if (head==NULL)
	{
		head=tail=&nodes[index];
	}
	else
	{
		tail->next=&nodes[index];
		tail=&nodes[index];
	}
}

void initialize()
{
	int count=0, index;
	for (int i=0; i<MaxListNode; i++)
	{
		nodes[i].index=i;
		nodes[i].rank=1;
		nodes[i].next=NULL;
		demon[i]=rand()%10;
		worker[i]=CreateThread(NULL, 0, run, (void*)&nodes[i], CREATE_SUSPENDED , NULL);
	}
	while (count<MaxListNode)
	{
		index=rand()%MaxListNode;
		if (added[index])
		{
			continue;
		}
		added[index]=true;
		addNode(index);
		count++;
	}
	mutex=CreateMutex(NULL, false, NULL);
	
}

bool acquire(Node* ptr)
{
	WaitForSingleObject(mutex, INFINITE);
	if (ptr==NULL)
	{
		ReleaseMutex(mutex);
		return true;
	}
	int index=ptr->index;
	if (added[index])//means old
	{
		added[index]=false;
		ReleaseMutex(mutex);
		return true;
	}
	//means it is locked: false
	ReleaseMutex(mutex);
	return false;
}

void release(Node* ptr)
{
	WaitForSingleObject(mutex, INFINITE);
	if (ptr!=NULL)
	{		
		added[ptr->index]=true;		
	}
	ReleaseMutex(mutex);
}

void interrupt(int index)
{
	if (demon[index]<4)
	{
		Sleep(0);
	}
}

DWORD WINAPI run(void* param)		
{
	while (true)
	{
		if (acquire((Node*)param))
		{
			//WaitForSingleObject(mutex, INFINITE);
			interrupt(((Node*)param)->index);
			Node* ptr=((Node*)param)->next;
			interrupt(((Node*)param)->index);
			if (acquire(ptr))
			{
				interrupt(((Node*)param)->index);
				if (ptr==NULL)
				{					
					counter++;
					release(ptr);
					release((Node*)param);
					break;				
				}
				else
				{
					((Node*)param)->rank+=ptr->rank;
					((Node*)param)->next=ptr->next;	
					
				}
				interrupt(((Node*)param)->index);
				release(ptr);				
			}
			interrupt(((Node*)param)->index);
			release((Node*)param);
		}
		Sleep(0);
	}
	return 0;
}
			

The input is something like following:

Here is the result:

index:16, rank:1
index:11, rank:1
index:7, rank:1
index:12, rank:1
index:6, rank:1
index:13, rank:1
index:14, rank:1
index:8, rank:1
index:1, rank:1
index:17, rank:1
index:10, rank:1
index:2, rank:1
index:18, rank:1
index:0, rank:1
index:15, rank:1
index:5, rank:1
index:9, rank:1
index:19, rank:1
index:3, rank:1
index:4, rank:1
now print the result
index:0, randk:7
index:1, randk:12
index:2, randk:9
index:3, randk:2
index:4, randk:1
index:5, randk:5
index:6, randk:16
index:7, randk:18
index:8, randk:13
index:9, randk:4
index:10, randk:10
index:11, randk:19
index:12, randk:17
index:13, randk:15
index:14, randk:14
index:15, randk:6
index:16, randk:20
index:17, randk:11
index:18, randk:8
index:19, randk:3
Press any key to continue