dllist.cc

这是一个关于操作系统进程调度的实验

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include "system.h"
#include "dllist.h"
extern int Flag;



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



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



DLList::~DLList()
{
	while( !IsEmpty() )
		Remove( &first->key );
}




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




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




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




void * DLList::Remove( int * keyPtr )
{
	if( IsEmpty() )
		return NULL;
	*keyPtr = first->key;
	if( Flag == 5 )
	{
		printf("\tRemove interrupt!\n");
		currentThread->Yield();
	}
	return SortedRemove( *keyPtr );
}

void DLList::SortedInsert( void * item, int sortKey )
{
	DLLElement * temp = new DLLElement( item, sortKey );
	DLLElement * ptr1, * ptr2;
	
	if( IsEmpty() )
	{
		first = temp;
		last = temp;
	}
	else
	{
		for( ptr1 = first, ptr2 = NULL; ptr1 != NULL && ptr1->key < sortKey; ptr2 = ptr1, ptr1 = ptr1->next )
			;
		if( Flag == 3 )
		{
			printf("\tSortedInsert interrupt!\n");
			currentThread->Yield();
		}
		if( ptr1 != NULL )
		{
			if( ptr2 != NULL )
			{
				temp->next = ptr1;
				temp->prev = ptr2;
				ptr2->next = temp;
				ptr1->prev = temp;
			}
			else
			{
				temp->next = first;
				first->prev = temp;
				first = temp;
			}
		}
		else
		{
			temp->prev = ptr2;
			ptr2->next = temp;
			last = temp;
		}
	}
}




void * DLList::SortedRemove( int sortKey )
{
	DLLElement * element1, * element2;
	void * thing;
	
	if( IsEmpty() )
		return NULL;
	for( element1 = first, element2 = NULL; element1 != NULL; element2 = element1, element1 = element1->next )
	{
		if( element1->key == sortKey )
			break;
	}
		if( Flag == 4 )
	{
		printf("\tSortedRemove interrupt!\n");
		currentThread->Yield();
	}
	if( element1 != NULL )
	{
		if( element1->next && element2 )
		{
			element1->next->prev = element1->prev;
			element2->next = element1->next;
			element1->next = NULL;
			element1->prev = NULL;
		}
		else if( element1->next ==NULL && element2 ==NULL )//in the head and only him
			first = last = NULL;	
		else if( element2 == NULL )//in the head
		{
			element1->next->prev = NULL;
			first = element1->next;
		}
		else//in the tail
		{
		    element2->next = NULL;
		    last = element2;
		}
		thing = element1->item;
		delete element1;
		return thing;
	}
	else
		return NULL;
}