equeue.cpp

处理机调度

#include "PCB.h"
#include "EQueue.h"
#include <stdlib.h>
#include <stdio.h>

	pQueue createNullQueue()
	{
		pQueue tmpQueue;
		/*not a good handle below*/
		tmpQueue=(pQueue)malloc(sizeof(ptrQueue));
		tmpQueue->head=NULL;
		tmpQueue->rear=NULL;
		return tmpQueue;
	}
	
	pQueue createNullQueueWithHead()
	{
		pQueue tmpQueue;
		/*not a good handle below*/
		tmpQueue=(pQueue)malloc(sizeof(ptrQueue));
		tmpQueue->emptyHead=(PtrQueueType)malloc(sizeof(QueueDataType));
		tmpQueue->head=NULL;
		tmpQueue->rear=NULL;
	
		return tmpQueue;
	}
	
	int isEmpty(pQueue inQueue)
	{
		return inQueue->head==NULL;//Correction: here at the last node ,after dequeue ,the rear may not be null
	}
	
	PtrQueueType deQueue(pQueue inQueue)
	{
		PtrQueueType tmpQueue;
		
		if(isEmpty(inQueue)||inQueue==NULL)
			{
				printf("in deQueue,inQueue is null\n");
				return NULL;
			}
		
		tmpQueue=inQueue->head;
		inQueue->head=inQueue->head->next;
		inQueue->emptyHead->next=inQueue->head;
		return tmpQueue;
	}
	
	void enQueue(pQueue inQueue,PtrQueueType inNode)
	{
		if(inQueue==NULL||inNode==NULL)
			{
				printf("in enQueue,inQueue is null\n");
				return ;
			}
		
		if(inQueue->rear==NULL&&inQueue->head==NULL)//first node to be created.
		{
				inQueue->rear=(PtrQueueType)malloc(sizeof(QueueDataType));
				inQueue->rear=inNode;
				inQueue->head=inQueue->rear;
				inQueue->emptyHead->next=inQueue->head;
		}
		else
		{
			/*Correction : use the rear->next for the new enqueue's pos*/
			inQueue->rear->next=(PtrQueueType)malloc(sizeof(QueueDataType));
			inQueue->rear->next=inNode;	
			inQueue->rear=inQueue->rear->next;
			inQueue->rear->next=NULL;
		}
	}
	
	/*attention :this insert algorithm has effects only on the queue with an empty head*/
	void insert(pQueue inQueue,PtrQueueType inNode)
	{
			PtrQueueType p;
			
			if(inQueue==NULL||inNode==NULL)
			{
				printf("in insert,inQueue is null\n");
				return ;
			}
			
			p=inQueue->emptyHead;
			
			while(p->next!=NULL&&p->next->priorityNum<=inNode->priorityNum)
				p=p->next;
			
			/*maybe will have errors when stop at p->next==null*/	
			if(p==inQueue->emptyHead)/*Correction Adjust to the head*/
			{
					inNode->next=p->next;	
					p->next=inNode;
					inQueue->head=inNode;
			}
			else
			{
					inNode->next=p->next;	
					p->next=inNode;
			}
		

			//Correction: To Adjust the rear
			while(p->next!=NULL)
				p=p->next;
			inQueue->rear=p;
		}