pcblist.h

自己写的操作系统的实验：处理机调度模拟及内存分配模拟二合一小程序。

#ifndef PCBLIST_H
#define PCBLIST_H

/*hasa not isa,良好的链表应该这样吧*/
//template<class T>
//class Cnode
//{
//public:
//	T* prep;
//	T*  nextp;
//	T data;
//};

template<class T>
class Clist
{
public:
	T* head;
	T* end;
public:
	int count;
public:
	Clist():count(0){end=new T;head=end;}
	void push_back(T*);
	void insert_before(T* inpcb,T* nextpcb);
	T* pop(T*);
	T* pop_front();
	T* findp(int id);
	void remove(T*);
	//void swap(T*,T*);
	void sort();
	void clear();
	~Clist();
};
#endif

template<class T>
Clist<T>::~Clist()
{
	clear();
}

template<class T>
void Clist<T>::clear()
{
	if( count )
	{
		T* tp=head;
		T* p=tp;
		while( tp=tp->nextp )
		{
			delete p;
			p=tp;
		}
		count=0;
		head=end;
	}
}

template<class T>
void Clist<T>::push_back(T* p)
{
	if( head==end )
	{
		head=p;
		p->nextp=end;
		end->prep=p;
	}
	else
	{
		p->nextp=end;
		p->prep=end->prep;
		end->prep->nextp=p;
		end->prep=p;
	}
	++count;
}

template<class T>
void Clist<T>::insert_before(T* inpcb,T* nextpcb)
{
	if( head==nextpcb )
	{
		inpcb->nextp=head;
		inpcb->prep=NULL;
		head->prep=inpcb;
		head=head->prep;
		++count;
	}
	else if( end==nextpcb )
			push_back(inpcb);
	else
	{
		inpcb->nextp=nextpcb;
		inpcb->prep=nextpcb->prep;
		nextpcb->prep->nextp=inpcb;
		nextpcb->prep=inpcb;
		++count;
	}
}

template<class T>
T* Clist<T>::pop(T* p)
{
	if( p==head )
	{
		head=p->nextp;
		p->nextp->prep=NULL;
	}
	else
	{
		p->prep->nextp=p->nextp;
		p->nextp->prep=p->prep;
	}
	p->prep=p->nextp=NULL;
	--count;
	return p;
}

template<class T>
T* Clist<T>::pop_front()
{
	return pop(head);
}

template<class T>
void Clist<T>::remove(T* p)
{
	pop(p);
	delete p;
}

template<class T>
T* Clist<T>::findp(int id)
{
	if( this->head==end ) return NULL;
	else
	{
		T* p=head;
		while( p->pid!=id ) p=p->nextp;
		if( p==end ) return NULL;
		return p;
	}
}
//template<class T>
//void Clist<T>::swap(T* a,T* b)
//{
//	T* p1;
//	if( a==b )
//		return;
//	a->nextp->prep=b;
//	a->prep->nextp=b;
//	b->nextp->prep=a;
//	b->prep->nextp=a;
//	p1=a->nextp;
//	a->nextp=b->nextp;
//	b->nextp=p1;
//	p1=a->prep;
//	a->prep=b->prep;
//	b->prep=p1;
//}
//直接插入排序以减少排序次数
template<class T>
void Clist<T>::sort()
{
	T* ap;
	T* bp=head;
	T* tp;
	while( bp!=end && bp->nextp!=end )
	{
		ap=bp->nextp;
		if( *ap>*bp && ap!=end )
		{
			//if:如果ap的优先级比头结点还大就直接插在头部
			//else:判断插入位置，并插入
			if( *head<*ap ) 
			{
				pop(ap);
				insert_before(ap,head);	
			}
			else
			{
				tp=bp->prep;
				while( *tp<*ap && tp!=head )
					tp=tp->prep;
				pop(ap);
				insert_before(ap,tp->nextp);
			}
		}
		else
			bp=bp->nextp;
	}
}