objqueue.cpp

自己动手写操作系统源代码,不可多得的代码

//***********************************************************************/
//    Author                    : Garry
//    Original Date             : Oct,18 2004
//    Module Name               : objqueue.cpp
//    Module Funciton           : 
//                                This module countains Object Queue's implementation code.
//    Last modified Author      :
//    Last modified Date        :
//    Last modified Content     :
//                                1.
//                                2.
//    Lines number              :
//***********************************************************************/

#ifndef __STDAFX_H__
#include "StdAfx.h"
#endif

//
//Insert an element into Priority Queue.
//This routine insert an common object into priority queue,it's position in the queue is
//determined by the object's priority(dwPriority parameter).
//

static BOOL InsertIntoQueue(__COMMON_OBJECT* lpThis,__COMMON_OBJECT* lpObject,DWORD dwPriority)
{
	__PRIORITY_QUEUE_ELEMENT*    lpQueueElement  =  NULL;
	__PRIORITY_QUEUE_ELEMENT*    lpPrevElement   =  NULL;
	__PRIORITY_QUEUE_ELEMENT*    lpNextElement   =  NULL;
	__PRIORITY_QUEUE*            lpPriorityQueue =  NULL;
	BOOL                         bResult         =  FALSE;
	DWORD                        dwFlags         = 0L;
	//BYTE                         strThread[12];
	//DWORD                        dwThread;

	if((NULL == lpThis) || (NULL == lpObject))
		return bResult;

	lpQueueElement = (__PRIORITY_QUEUE_ELEMENT*)
		KMemAlloc(sizeof(__PRIORITY_QUEUE_ELEMENT),KMEM_SIZE_TYPE_ANY);
	if(NULL == lpQueueElement)  //Failed to allocate memory.
	{
		//dwThread = (DWORD)KernelThreadManager.lpCurrentKernelThread;
		//Hex2Str(dwThread,strThread);
		PrintLine("InsertIntoQueue: Can not allocate memory.");
		//PrintLine("The current kernel thread is :");
		//PrintLine(strThread);
//__DEADLOOP:
		//goto __DEADLOOP;

		goto __TERMINAL;
	}

	lpQueueElement->lpObject      = lpObject;    //Initialize the queue element.
	lpQueueElement->dwPriority    = dwPriority;
	lpQueueElement->lpNextElement = NULL;
	lpQueueElement->lpPrevElement = NULL;

	lpPriorityQueue = (__PRIORITY_QUEUE*)lpThis;

	//ENTER_CRITICAL_SECTION();
	__ENTER_CRITICAL_SECTION(NULL,dwFlags);
	if(NULL == lpPriorityQueue->lpElementHeader)    //If the priority queue is empty.
	{
		//DisableInterrupt();
		lpPriorityQueue->lpElementHeader = lpQueueElement;
		lpPriorityQueue->dwCurrElementNum ++;
		//EnableInterrupt();
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		bResult = TRUE;
		goto __TERMINAL;
	}

	lpPrevElement = lpPriorityQueue->lpElementHeader;
	lpNextElement = lpPrevElement;
	while(lpPrevElement->dwPriority >= dwPriority)    //To find the correct position.
	{
		lpNextElement = lpPrevElement;
		lpPrevElement = lpPrevElement->lpNextElement;
		if(NULL == lpPrevElement)
			break;
	}
	if(NULL == lpPrevElement)  //This newly object should be the last object.
	{
		//DisableInterrupt();
		lpNextElement->lpNextElement  = lpQueueElement;
		lpQueueElement->lpPrevElement = lpNextElement;
		lpPriorityQueue->dwCurrElementNum ++;
		//EnableInterrupt();
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		bResult = TRUE;
		goto __TERMINAL;
	}
	if(lpPrevElement == lpNextElement)  //This newly object should be the first object in the
		                                //current queue.
	{
		//DisableInterrupt();
		lpQueueElement->lpNextElement    = lpPrevElement;
		lpPrevElement->lpPrevElement     = lpQueueElement;
		lpPriorityQueue->lpElementHeader = lpQueueElement;
		lpPriorityQueue->dwCurrElementNum ++;
		//EnableInterrupt();
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		bResult = TRUE;
		goto __TERMINAL;
	}
	else    //The object is not the first object,is not the last object too.
	{
		//DisableInterrupt();
		lpQueueElement->lpNextElement = lpPrevElement;
		lpQueueElement->lpPrevElement = lpNextElement;
		lpPrevElement->lpPrevElement  = lpQueueElement;
		lpNextElement->lpNextElement  = lpQueueElement;
		lpPriorityQueue->dwCurrElementNum ++;
		//EnableInterrupt();
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		bResult = TRUE;
		goto __TERMINAL;
	}

__TERMINAL:
	return bResult;
}

//
//Delete an element from Priority Queue.
//This routine searchs the queue,to find the object to be deleted,
//if find,delete the object from priority queue,returns TRUE,else,
//returns FALSE.
//If the object is inserted into this queue for many times,this
//operation only deletes one time.
//

static BOOL DeleteFromQueue(__COMMON_OBJECT* lpThis,__COMMON_OBJECT* lpObject)
{
	__PRIORITY_QUEUE_ELEMENT*  lpFirstElement    = NULL;
	__PRIORITY_QUEUE_ELEMENT*  lpSecondElement   = NULL;
	__PRIORITY_QUEUE_ELEMENT*  lpCurrElement     = NULL;
	__PRIORITY_QUEUE*          lpPriorityQueue   = NULL;
	BOOL                       bResult           = FALSE;
	DWORD                      dwFlags           = 0L;

	if((NULL == lpThis) || (NULL == lpObject)) //Parameters check.
		goto __TERMINAL;

	lpPriorityQueue = (__PRIORITY_QUEUE*)lpThis;
	//lpCurrElement = lpPriorityQueue->lpElementHeader;
	//ENTER_CRITICAL_SECTION();
	__ENTER_CRITICAL_SECTION(NULL,dwFlags);
	lpFirstElement = lpPriorityQueue->lpElementHeader;

	if(NULL == lpFirstElement)  //If the queue does not countain any object,terminal.
	{
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		goto __TERMINAL;
	}

	while(lpFirstElement->lpObject != lpObject)
	{
		lpFirstElement = lpFirstElement->lpNextElement;
		if(NULL == lpFirstElement)
			break;
	}

	if(NULL == lpFirstElement)  //The queue does not countain the object.
	{
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		goto __TERMINAL;
	}

	if(NULL == lpFirstElement->lpPrevElement)  //If the object to be deleted is the first
		                                       //object of the current priority queue.
	{
		//DisableInterrupt();
		if(lpFirstElement->lpNextElement != NULL)    //Not the last element.
		{
			lpPriorityQueue->lpElementHeader = lpFirstElement->lpNextElement;
			lpFirstElement->lpNextElement->lpPrevElement = NULL;
		}
		else    //This is the last element.
			lpPriorityQueue->lpElementHeader = NULL;

		lpPriorityQueue->dwCurrElementNum --;
		//EnableInterrupt();
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		KMemFree((LPVOID)lpFirstElement,KMEM_SIZE_TYPE_ANY,0L);  //Free the memory.
		bResult = TRUE;
		goto __TERMINAL;
	}
	if(NULL == lpFirstElement->lpNextElement)  //The object to be deleted is the last object.
	{
		//DisableInterrupt();
		lpFirstElement->lpPrevElement->lpNextElement = NULL;
		lpPriorityQueue->dwCurrElementNum --;
		//EnableInterrupt();
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		KMemFree((LPVOID)lpFirstElement,KMEM_SIZE_TYPE_ANY,0L);
		bResult = TRUE;
		goto __TERMINAL;
	}
	else    //The object to be deleted is not the first,is not the last too.
	{
		//DisableInterrupt();
		lpFirstElement->lpNextElement->lpPrevElement = lpFirstElement->lpPrevElement;
		lpFirstElement->lpPrevElement->lpNextElement = lpFirstElement->lpNextElement;
		lpPriorityQueue->dwCurrElementNum --;
		//EnableInterrupt();
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		KMemFree((LPVOID)lpFirstElement,KMEM_SIZE_TYPE_ANY,0L);
		bResult = TRUE;
	}

__TERMINAL:
	return bResult;
}

//
//Get the header element from Priority Queue.
//This routine get the first(header) object of the priority queue,
//and release the memory this element occupies.
//

static __COMMON_OBJECT* GetHeaderElement(__COMMON_OBJECT* lpThis,DWORD* lpPriority)
{
	__COMMON_OBJECT*          lpCommonObject    = NULL;
	__PRIORITY_QUEUE*         lpPriorityQueue   = NULL;
	__PRIORITY_QUEUE_ELEMENT* lpQueueElement    = NULL;
	DWORD                     dwFlags           = 0L;

	if(NULL == lpThis)
		return NULL;

	lpPriorityQueue = (__PRIORITY_QUEUE*)lpThis;

	//ENTER_CRITICAL_SECTION();
	__ENTER_CRITICAL_SECTION(NULL,dwFlags);
	lpQueueElement = lpPriorityQueue->lpElementHeader;
	if(NULL == lpQueueElement)    //The queue is empty.
	{
		if(lpPriority != NULL)
			*lpPriority = 0L;
		//LEAVE_CRITICAL_SECTION();
		__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
		return NULL;
	}

	lpPriorityQueue->lpElementHeader = lpQueueElement->lpNextElement;  //Update the queue's
	                                                                   //element header.
	lpPriorityQueue->lpElementHeader->lpPrevElement = NULL;            //Set to NULL indicates the
	                                                                   //first element.

	lpCommonObject = lpQueueElement->lpObject;
	if(lpPriority != NULL)
	{
		*lpPriority = lpQueueElement->dwPriority;    //Return the priority value.
	}
	//LEAVE_CRITICAL_SECTION();
	__LEAVE_CRITICAL_SECTION(NULL,dwFlags);
	KMemFree((LPVOID)lpQueueElement,KMEM_SIZE_TYPE_ANY,0L);  //Release the queue element.

	return lpCommonObject;
}

//Initialize routine of the Priority Queue.
BOOL PriQueueInitialize(__COMMON_OBJECT* lpThis)
{
	__PRIORITY_QUEUE*                lpPriorityQueue     = NULL;
	BOOL                             bResult             = FALSE;

	if(NULL == lpThis)           //Parameter check.
		return bResult;

	//Initialize the Priority Queue.
	lpPriorityQueue = (__PRIORITY_QUEUE*)lpThis;
	lpPriorityQueue->lpElementHeader  = NULL;
	lpPriorityQueue->dwCurrElementNum = 0L;
	lpPriorityQueue->InsertIntoQueue  = InsertIntoQueue;
	lpPriorityQueue->DeleteFromQueue  = DeleteFromQueue;
	lpPriorityQueue->GetHeaderElement = GetHeaderElement;
	bResult = TRUE;

	return bResult;
}

//
//Uninitialize routine of Priority Queue.
//This routine frees all memory this priority queue occupies.
//

VOID PriQueueUninitialize(__COMMON_OBJECT* lpThis)
{
	__PRIORITY_QUEUE_ELEMENT*    lpFirstElement    = NULL;
	__PRIORITY_QUEUE_ELEMENT*    lpSecondElement   = NULL;
	__PRIORITY_QUEUE*            lpPriorityQueue   = NULL;

	if(NULL == lpThis)
		return;

	lpPriorityQueue = (__PRIORITY_QUEUE*)lpThis;
	lpFirstElement  = lpPriorityQueue->lpElementHeader;
	if(NULL == lpFirstElement)
		return;

	while(lpFirstElement)  //Release the memory this priority queue occupies.
	{
		lpSecondElement = lpFirstElement;
		lpFirstElement  = lpFirstElement->lpNextElement;
		KMemFree((LPVOID)lpSecondElement,KMEM_SIZE_TYPE_ANY,0L);  //Free the memory.
	}
}