// 首次適應算法.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;  //內存塊首地址
		int Lenth;   //塊長度
		bool State;  //0 代表是空閑塊，1 代表是已分配塊
		mem *prior;
		mem *next;
		}*Head,*Tail;

typedef struct job JOB;
typedef struct mem MEM;

void DispFreeMem(MEM *pr) /*建立進程顯示函數,用于顯示當前進程*/ 
{ 
	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) /*建立進程顯示函數,用于顯示當前進程*/ 
{ 
	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,*temp2,*p=NULL;
	char Name[10];
	int Lenth;
	int min=30000;

	printf("\n Name of the job:   "); 
	scanf("%s",Name);  
	printf("\n The space of this job:(K)   ");
	scanf("%d",&Lenth);
	getchar();
	temp2=Head->next;
	while(temp2!=Tail)  //查找足夠大的空閑塊來分配
	{	
		if(temp2->State==0&&temp2->Lenth>=Lenth)
		{
			if(temp2->Lenth<min)
			{
				p=temp2;
				min=temp2->Lenth;
			}
		}
		temp2=temp2->next;
	}
	if(p==NULL)     //沒有足夠的空間分配給當前作業
	{	
		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)	//空閑塊空間比所需空間大，則分裂為兩個結點
	{
		temp=GetSpace(MEM);
		strcpy(temp->Name,Name);  //添加新結點的相關參數
		temp->MemAdr=p->MemAdr;
		//printf("\n \t\t!!!! The allotted address of job %s is: %d !!!!\n",Name,temp->MemAdr);
		temp->Lenth=Lenth;
		temp->State=1;

		p->prior->next=temp;  //插入新結點
		temp->prior=p->prior;
		temp->next=p;
		p->prior=temp;

		p->MemAdr=p->MemAdr+temp->Lenth; //修改分裂后的剩余結點信息
		p->Lenth -= temp->Lenth;
	}
	else	//否則只需直接把作業填進空閑塊即可
	{
		strcpy(p->Name,Name);
		p->State=1;
	}
}

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)  //查找需要釋放的作業
		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)  
	{  //將要釋放的內存塊的前后內存塊都為空閑，合并
		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)
		{  //將要釋放的內存塊的后內存塊為空閑，合并
			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)
		{  //將要釋放的內存塊的前內存塊為空閑，合并
			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)
		{  //將要釋放的內存塊的前后內存塊都不為空閑，無需合并
			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);   //顯示空閑鏈的狀態
					DispNotFreeMem(Head->next);//顯示作業占用內存狀況
					break;
		case '2':	Reclaim();
					DispFreeMem(Head->next);   //顯示空閑鏈的狀態
					DispNotFreeMem(Head->next);//顯示作業占用內存狀況
					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()/*主函數*/
{
	MEM *s;
	printf("Please input the total number the memory:(K)   ");
	s=GetSpace(MEM);     //創建空閑鏈表
	scanf("%d",&s->Lenth);
	getchar();
	strcpy(s->Name,"NULL");
	s->MemAdr=0;s->State=0;
	//初始化空閑鏈的頭尾結點
	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;	
	Choice();	//進入主菜單進行相應操作	
}