// 首次適應(yīng)算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h> 
#include <conio.h>
#include <string.h>

#define GetSpace(type) (type*)malloc(sizeof(type)) 

#define NULL 0
#define SIZE 0  //定義可以分割空閑塊的差值 

struct mem {
		char Name[10];
		int MemAdr;  //內(nèi)存塊首地址
		int Lenth;   //塊長度
		bool State;  //0 代表是空閑塊，1 代表是已分配塊
		mem *prior;
		mem *next;
		}*Head,*Tail,*PriDis;

typedef struct job JOB;
typedef struct mem MEM;

void DispFreeMem(MEM *pr) /*建立進(jìn)程顯示函數(shù),用于顯示當(dāng)前進(jìn)程*/ 
{ 
	int i=0;
	printf("\n******************************************");
	printf("\n\n The state of free memory:");
	printf("\n Chunk Num \t FirAddress \t Lenth(K)");  //顯示空閑塊的首地址以及大小
	while(pr!=Tail)
	{
		if(pr->State==0)
		{
			printf("\n %d \t\t %d \t\t %d K",i,pr->MemAdr,pr->Lenth);
			i++;
		}
		pr=pr->next;
	}
} 

void DispNotFreeMem(MEM *pr) /*建立進(jìn)程顯示函數(shù),用于顯示當(dāng)前進(jìn)程*/ 
{ 
	printf("\n******************************************");
	printf("\n\n The state of not free memory:");
	printf("\n Job Name \t FirAddress \t Lenth(K)");  //顯示空閑塊的首地址以及大小
	while(pr!=Tail)
	{
		if(pr->State==1)
		{
			printf("\n %s \t\t %d \t\t %d K",pr->Name,pr->MemAdr,pr->Lenth);
		}
		pr=pr->next;
	}
	printf("\n\n******************************************");
}

void Distribute()
{
	MEM *temp,*p;
	char Name[10];
	int Lenth;
	bool Flag=0;
	printf("\n Name of the job:   "); 
	scanf("%s",Name);  
	printf("\n The space of this job:(K)   ");
	scanf("%d",&Lenth);
	getchar();
	p=PriDis;	//從上一次分配成功的后一個(gè)空閑塊開始查找
	do{		//查找足夠大的空閑塊來分配
		if(p->State==0&&p->Lenth>=Lenth) 
			break;
		else
		{
			if(p->next!=Tail)
				p=p->next;
			else
			{
				p=Head->next;
				Flag=1;
			}
		}
	}while(p!=PriDis);
	if(Flag&&p==PriDis)     //沒有足夠的空間分配給當(dāng)前作業(yè)
	{	
		printf("\n\t\tThe free memory is not enough for this job!!\n");
		printf("\nPlease press any key to continue......\n");
		getchar();
		return; 
	}
	if((p->Lenth-Lenth)>SIZE) //如果空閑塊比作業(yè)所需空間大，則分裂結(jié)點(diǎn)
	{
		temp=GetSpace(MEM);
		strcpy(temp->Name,Name);  //添加新結(jié)點(diǎn)的相關(guān)參數(shù)
		temp->MemAdr=p->MemAdr;
		//printf("\n \t\t!!!! The allotted address of job %s is: %d !!!!\n",j->Name,temp->MemAdr);
		temp->Lenth=Lenth;
		temp->State=1;

		p->prior->next=temp;  //插入新結(jié)點(diǎn)
		temp->prior=p->prior;
		temp->next=p;
		p->prior=temp;

		p->MemAdr=p->MemAdr+temp->Lenth; //修改分裂后的剩余結(jié)點(diǎn)信息
		p->Lenth -= temp->Lenth;
		PriDis=p;
	}
	else    //否則不用分裂，直接把整個(gè)空閑塊分配給作業(yè)
	{
		strcpy(p->Name,Name);
		p->State=1;
		if(p->next!=Tail)
			PriDis=p->next;
		else
			PriDis=Head->next;
		//printf("\n \t\t!!!! The allotted address of job %s is: %d !!!!\n",j->Name,p->MemAdr);
	}
}

void Reclaim()
{
	MEM *temp1,*temp2,*p;
	char Name[10];
	printf("\n Name of the job:   "); 
	scanf("%s",Name);
	getchar();
	p=Head->next;
	while(p!=Tail&&strcmp(p->Name,Name)!=0)  //查找需要釋放的作業(yè)
		p=p->next;	
	if(p==Tail)
	{
		printf("\n\t\tThis job is not in the memory!!");
		printf("\nPlease press any key to continue......\n");
		getchar();
		return; 
	}
	if(p->prior->State==0&&p->next->State==0)  
	{  //將要釋放的內(nèi)存塊的前后內(nèi)存塊都為空閑，合并
		if(PriDis==p->next)		//合并后要修改指向下一次應(yīng)分配的空閑塊的
			PriDis=p->prior;	//指針，適應(yīng)循環(huán)首次適應(yīng)算法的要求
		temp1=p;
		temp2=p->next;
		p->prior->next=temp2->next;
		temp2->next->prior=p->prior;
		p->prior->Lenth += temp1->Lenth + temp2->Lenth;
		free(temp1);
		free(temp2);
	}
	else if(p->prior->State==1&&p->next->State==0)
		{  //將要釋放的內(nèi)存塊的后內(nèi)存塊為空閑，合并
			if(PriDis==p->next)  //合并后要修改指向下一次應(yīng)分配的空閑塊的
				PriDis=p;        //指針，適應(yīng)循環(huán)首次適應(yīng)算法的要求
			temp2=p->next;
			p->next=temp2->next;
			temp2->next->prior=p;
			strcpy(p->Name,"NULL");
			p->Lenth += temp2->Lenth;
			p->State=0;
			free(temp2);
		}
	else if(p->prior->State==0&&p->next->State==1)
		{  //將要釋放的內(nèi)存塊的前內(nèi)存塊為空閑，合并
			temp1=p;
			p->prior->next=p->next;
			p->next->prior=p->prior;
			p->prior->Lenth += p->Lenth;
			free(temp1);
		}
	else if(p->prior->State==1&&p->next->State==1)
		{  //將要釋放的內(nèi)存塊的前后內(nèi)存塊都不為空閑，無需合并
			strcpy(p->Name,"NULL");
			p->State=0;
		}
}

void Choice()
{
	char CH;
	MEM *temp1,*temp2;
	temp1=Head;
	temp2=Head->next;
	while(1)
	{
		
		printf("\n		------------------");
		printf("\n		| 1.Apply a job  |");
		printf("\n		| 2.Cancel a job |");
		printf("\n		| 3.Exit	 |");
		printf("\n		------------------");
		printf("\n\n	Please make a choice:	");
		scanf("%c",&CH);
		switch(CH)
		{
		case '1':	Distribute();
					DispFreeMem(Head->next);   //顯示空閑鏈的狀態(tài)
					DispNotFreeMem(Head->next);//顯示作業(yè)占用內(nèi)存狀況
					break;
		case '2':	Reclaim();
					DispFreeMem(Head->next);   //顯示空閑鏈的狀態(tài)
					DispNotFreeMem(Head->next);//顯示作業(yè)占用內(nèi)存狀況
					break;
		case '3':	while(temp1!=NULL)
					{
						free(temp1);
						temp1=temp2;
						if(temp2!=NULL)
							temp2=temp2->next;
					}
					return;
		}
		printf("\nPlease press any key to continue......\n");
		getchar();
	}
}

void main()/*主函數(shù)*/
{
	MEM *s;
	printf("Please input the total number the memory:(K)   ");
	s=GetSpace(MEM);     //創(chuàng)建空閑鏈表
	scanf("%d",&s->Lenth);
	getchar();
	strcpy(s->Name,"NULL");
	s->MemAdr=0;s->State=0;
	//初始化空閑鏈的頭尾結(jié)點(diǎn)
	Head=GetSpace(MEM);	Tail=GetSpace(MEM);  
	Head->next=s;	Tail->next=NULL;
	s->prior=Head;	s->next=Tail;
	Tail->prior=s;
	Head->State=Tail->State=1;
	PriDis=Head->next;//第一次分配空閑塊時(shí)，PriDis指向第一個(gè)空閑塊
	Choice();	//進(jìn)入主菜單進(jìn)行相應(yīng)操作	
}