dllist.cc

nachos下并发程序设计。编写双向链表并演示并发错误。包含文件Makefile.common、main.cc、threadtest.cc、dllist-driver.cc、dllist.cc、dll

#include "dllist.h"
#include <iostream>
#include "system.h"
#include <cstdio>
#include <cstdlib>
#include <ctime>
//#include "thread.h"
//extern int testnum;
//extern Thread *currentThread;

DLLElement::DLLElement(void *itemPtr,int sortKey)
{
	key=sortKey;
	next=NULL;
	prev=NULL;
	item=itemPtr;
}

DLList::DLList()
{
	first=NULL;
	last=NULL;
}

bool DLList::IsEmpty()
{
	if(first == NULL)
		return true;
	return false;
}

DLList::~DLList()
{
	if(!IsEmpty())
	{
		while(first!=last)
		{
			DLLElement *p=first;
			first=first->next;
			delete p;
		}
		delete first;
	}
}

void DLList::Prepend(void *item)
{
	if (IsEmpty())
	{
		DLLElement *element = new DLLElement(item,0);
		last=first=element;
	}
	else
	{
		DLLElement *element= new DLLElement(item,(first->key-1));
		element->next=first;
		first->prev=element;
		first=element;
	}
}

void DLList::Append(void *item)
{
	if(IsEmpty())
	{
		DLLElement *element=new DLLElement(item,0);
		first=element;
		last=first;
	}
	else
	{
		int key = last->key+1;
		DLLElement *element = new DLLElement(item,key);
		last->next=element;
		element->prev=last;
		last=element;
	}
}

void* DLList::Remove(int *keyPtr)
{
	if(IsEmpty())
	{
		keyPtr=NULL;
		return NULL;
	}
	else
	{
		//DLLElement *rm=first;
		//if(testnum == 3) currentThread->Yield();//what's meaning?
		//void *thing=first->item;
		*keyPtr = first->key;
		/*if(first ==last)
			last=first=NULL;
		else
		{
			first=first->next;
			first->prev=NULL;
		}
		delete rm;
		return thing;*/
		return SortedRemove(*keyPtr);
	}
}

void DLList::SortedInsert(void *item, int sortKey)
{
	DLLElement *element = new DLLElement (item,sortKey);
	if(IsEmpty())
	{
		first=last=element;
	}
	else
	{
		if(first->key>sortKey)
		{
                        if(Flag==4)
                        {
                           printf("\tSortedInser Interrupt\n");
                           currentThread->Yield();
                        }
			element->next=first;
			first->prev=element;
			element->prev=NULL;
			first=element;
		}
		else
		{
			DLLElement* head=first;
			while(head->next!=NULL)
			{
				if(sortKey<head->next->key)
				{
                                         if(Flag==4)
                                        {
                                          printf("\tSortedInser Interrupt\n");
                                          currentThread->Yield();
                                        }

					element->next=head->next;
					element->prev=head;
					head->next->prev=element;
					head->next=element;
					return;
				}
				else
					head=head->next;
			}

                          if(Flag==4)
                        {
                            printf("\tSortedInser Interrupt\n");
                            currentThread->Yield();
                         }

			head->next=element;
			element->prev=head;
			element->next=NULL;
			last=last->next;
		}
	}
}

void* DLList::SortedRemove(int sortKey)
{
	if(IsEmpty())return NULL;
	/*if(first->key==sortKey)
	{
		DLLElement *rm=first;
		void * thing=first->item;
		first=first->next;
		first->prev=NULL;
		delete rm;
		return thing;
	}
	else
	{*/
		DLLElement * head1=first;
		DLLElement * head2=first;
		while((head1!=NULL)&&(head1->key!=sortKey))
		{
			head2=head1;
			head1=head1->next;
		}
                 if(Flag==5)
                {
                   printf("\tSortedRemove  Interrupt\n");
                   currentThread->Yield();
                 }
		if(head1==NULL)return NULL;
		else if(head1==first)
		{
			DLLElement *rm=first;
			void *thing=first->item;
			first=first->next;
	        if(first==NULL)
			{
				first=last=NULL;
				delete rm;
				return thing;
			}
			else
			{
				first->prev=NULL;
				delete rm;
				return thing;
			}
		}
		else
		{
			void *thing=head1->item;
			head2->next=head1->next;
			if(head1->next!=NULL)
				head1->next->prev=head2;
			else last=head2;
			delete head1;
			return thing;
		}
	//}
}