dllist.cc

nachos下线程与同步的实验

#include <iostream.h>
#include <stdlib.h>
#include "thread.h"
#include "system.h"
#include "dllist.h"


extern int testnum;

DouListElement::DouListElement(int item)  //初始化函数
{
	key = item;
	next = pre = NULL;
}

DouList::DouList()   //链表构造函数
{
	head = new DouListElement(0);       //创建头尾节点     

	tail = new DouListElement(0);
	
	lock = new Lock("list lock");//NULL有问题~"list lock"

  	listEmpty = new Condition("list empty cond");//("list empty cond");
	
	head->pre = tail->next = NULL;     //初始化

	head->next = tail;

	tail->pre =  head;
}

DouList::~DouList()   //析构函数
{
	while(!IsEmpty())   //删除节点
		LastDelete();

	delete head;

	delete tail;

	delete lock;
	
	delete listEmpty;

	head = tail = NULL;
}

int DouList::IsEmpty()                   //判断链表是否为空
{
	if(head->next == tail)
		return 1;
	else
		return 0;
}

void DouList::Append(DouListElement *item) //在链表的结尾增加一个节点
{
	if(IsEmpty())            //链表为空
	{
		head->next = item;

		item->pre = head;

		tail->pre = item;

		item->next = tail;
	}
	else
	{
		(tail->pre)->next = item;

		item->pre = tail->pre;

		tail->pre = item;

		item->next = tail;

	}
}

void DouList::PreAppend(DouListElement *item) //在链表的头部增加一个节点
{
	if(IsEmpty())  //链表为空
	{
		head->next = item;

		item->pre = head;

		tail->pre = item;

		item->next = tail;
	}
	else
	{
		head->next->pre = item;

		item->next = head->next;

		head->next = item;

		item->pre = head;
	}
}

void DouList::LastDelete()                //在链表结尾删除一个节点  
{
	if(IsEmpty())        //如果链表为空，打印出错信息
	{
		cout<<"DouList is Empty~"<<endl;
		return ;
	}
	else
	{
		tail->pre = (tail->pre)->pre;

		delete (tail->pre)->next;
		
		(tail->pre)->next = tail;
	}
}

void DouList::FistDelete(int which,int i)                //在链表头部删除一个节点  
{
        int k;
	
	lock->Acquire();
	
	while(IsEmpty())        //如果链表为空，打印出错信息 该成while
		
           listEmpty->Wait(lock);
			
      
               // k=head->next->key;  else 去掉了
                //if(testnum==2&&which==0&&i==3)没用吧
                     //  cout<<"************"<<head->next->next->key<<endl;                
		head->next = head->next->next;

               if(testnum==3&&which==0&&i==1)
                  currentThread->Yield();
               
               k=head->next->pre->key;

		delete head->next->pre;

                 if(testnum==2&&which==0&&i==2)
                     currentThread->Yield();

		head->next->pre = head;
               
                 cout<<"The Thread "<<which<< " Delete the number "<<k<<endl;

                 if(testnum==2&&i==1&&which==0)
                  
                   currentThread->Yield();

                if(testnum==4&&which==1&&i==1)
                      currentThread->Yield();

	lock->Release();
}

void DouList::PrintList()        //打印链表
{
	//lock->Acquire();//没必要吧

	DouListElement *p = head->next;

	if(IsEmpty())
	{
		cout<<"The DouList is empty!"<<endl;
		return ;
	}

	for (int i = 1; p != tail; p = p->next,i++)
		cout<<"Num "<<i<<" of the DouList: "<<p->key<<" "<<endl;

	cout<<endl;

	//lock->Release();//没必要吧
}

int DouList::GetNumOfItem()      //取得链表中节点个数 
{
	int i = 0;
	DouListElement *p = head->next;

	for(; p != tail; p = p->next,i++);

	return i;
}

void DouList::Insert(DouListElement *item,int which,int i)           //在链表中正序插入一个元素
{
	DouListElement *p;
	
	cout << "Thread" << which << "be to go into single insert!" << endl ;

	lock->Acquire();

	cout << "Thread" << which << "go into single insert!" << endl;
		
	for(p = head; p->next != tail && p->next->key < item->key; p = p->next);

	//Insert(p,item,which,i);
	
	p->next->pre=item;

    	if(testnum==1&&which==0&&i==3)
			currentThread->Yield();

    	item->next=p->next;

     	if(testnum==4&&which==1&&i==1)
       			currentThread->Yield();

    	item->pre=p;

     	if(testnum==2&&which==1&&i==1)
			currentThread->Yield();

    	p->next=item;

	cout<<"The Thread "<<which<<" Insert the number "<<item->key<<endl;

    	if((testnum==1||testnum==2)&&which==1&&i==1)
			currentThread->Yield();
    
	if(testnum==3&&which==1&&i==1)
       			currentThread->Yield();

    	if(testnum==4&&which==0&&i==5)
     			currentThread->Yield();

	listEmpty->Signal(lock);//增添的	
	lock->Release();
	cout << "Lock Released by thread" << which << endl; 

}