#include<stdio.h>
#include<stdlib.h>
#define MEM 600
struct free_node//the node of free space;
{
	free_node *front;//the node before it;
	int fe_head_address;//the head address of free space;
	int fe_tail_address;//the tail address of free space;
	int fe_size;//the size of free space;
	free_node *next;//the node after it;
};
struct allocated_node
{
	int process_ID;//the ID of the process which has been allocated;
	int allo_head_address;//the head address of the allocated space;
	int allo_tail_address;//the tail address of the allocated space;
	int allo_size;//the size of the allocated space;
	allocated_node *next;//the next node;
};
typedef free_node fre;
typedef allocated_node allocated;
fre * fe_first=0;
fre * fe_tail=0;
fre * f_sign=0;
allocated * allo_first=0;
allocated * allo_tail=0;
allocated * a_sign=0;
int temp_head=0;//
void init(void);
bool check_if_free(int);
bool check_if_allocated(int);
void firstfit_allocate(int);
void bestfit_allocate(int);
void addrevise(int,int);
void freerevise();
void print();
void firstfit_free( );
void bestfit_free();
void sort_sign();
void insert();
void menu1(void);
void menu2(void);

void menu1(void)
{
	printf("You can choose one method to manage you memeory.\n");
	
	printf("*************************************\n");
	printf("*****1-first fit algorithm***********\n");
	printf("*****2-best  fit algorithm***********\n");
	printf("*****3-quit               ***********\n");
}

void menu2(void)
{
	printf("Now you can allocate and free the memory!\n");
	printf("please input (1,2,3)\n");
	printf("**************************************\n");
	printf("1-require allocating memory for process\n");
	printf("2-free the allocated memory for process\n");
	printf("3-back\n");
}
void init(void)
{
	fe_first=(fre *)malloc(sizeof(fre));
	fe_tail=fe_first;
	fe_first->fe_size=MEM;
	fe_first->next=NULL;
	fe_first->front=NULL;
	fe_first->fe_head_address=0;
	fe_first->fe_tail_address=MEM-1;
	fe_first->fe_size=MEM;
	allo_first=allo_tail=NULL;
}
bool check_if_free(int r_size)
{
	f_sign=fe_first;
	while(f_sign!=NULL)
	{
		if(f_sign->fe_size>=r_size)return true;
		f_sign=f_sign->next;
	}
	return false;
}
bool check_if_allocated(int r_id)
{
	a_sign=allo_first;
	while(a_sign!=NULL)
	{
		if(a_sign->process_ID==r_id)return true;
		a_sign=a_sign->next;
    }
	return false;
}
void firstfit_allocate(int r_size)
{
    if(f_sign==fe_first)
	{
		if(f_sign->fe_size==r_size)
		{fe_first=f_sign->next;
		if(fe_first!=NULL)
		{fe_first->front=NULL;}
		}
		else{
			temp_head=f_sign->fe_head_address;
			f_sign->fe_head_address=f_sign->fe_head_address+r_size;
			f_sign->fe_size=f_sign->fe_size-r_size;
		}
	}
	else if(f_sign==fe_tail)
	{
        if(f_sign->fe_size==r_size)
		{
			fe_tail=f_sign->front;
			fe_tail->next=NULL;
		}else{
			temp_head=f_sign->fe_head_address;
           f_sign->fe_head_address=f_sign->fe_head_address+r_size;
			f_sign->fe_size=f_sign->fe_size-r_size;}
	}
	else
	{
		if(f_sign->fe_size==r_size)
		{
			f_sign->next->front=f_sign->front;
			f_sign->front->next=f_sign->next;
		}else{
			temp_head=f_sign->fe_head_address;
            f_sign->fe_head_address=f_sign->fe_head_address+r_size;
			f_sign->fe_size=f_sign->fe_size-r_size;}
	}
}
void addrevise(int id,int r_size)
{
   if(allo_first==NULL)
   {
	   allo_first=(allocated *)malloc(sizeof(allocated));
	   allo_first->process_ID=id;
	   allo_first->allo_size=r_size;
	   allo_first->allo_head_address=temp_head;
	   allo_first->allo_tail_address=f_sign->fe_head_address-1;
	   allo_first->next=NULL;
	   allo_tail=allo_first;
   }
   else
   {
	   allo_tail->next=(allocated *)malloc(sizeof(allocated));
	   allo_tail=allo_tail->next;
	   allo_tail->process_ID=id;
	   allo_tail->allo_size=r_size;
	   allo_tail->allo_head_address=temp_head;
	   if(fe_first==0){allo_tail->allo_tail_address=MEM-1;}
	   else{
		   allo_tail->allo_tail_address=f_sign->fe_head_address-1;}
	   allo_tail->next=NULL;
   }
   if(f_sign->fe_size+r_size==r_size)//this bug takes me 1 hour!!!my god!!
   {
      free(f_sign);
      f_sign=NULL;
   }
}
void print()
{
	printf("allocated space:\n");
	allocated * p=allo_first;
	if(p==NULL)printf("0\n");
	while(p!=NULL)
	{
		printf("the head address:%d\n",p->allo_head_address);
		printf("the end address:%d\n",p->allo_tail_address);
		printf("the length of the area:%d\n",p->allo_size);
		printf("the ID of the process:%d\n",p->process_ID);
		p=p->next;
	}
	printf("free space:\n");
	fre * fp=fe_first;
	if(fp==NULL)printf("0");
	while(fp!=NULL)
	{
        printf("the head address:%d\n",fp->fe_head_address);
		printf("the end address:%d\n",fp->fe_tail_address);
		printf("the length of the free area:%d\n",fp->fe_size);
		fp=fp->next;
	}
}
void firstfit_free( )
{
	fre * p=0;
	if(fe_first==NULL)
	{
		fe_first=(fre *)malloc(sizeof(fre));
		fe_first->fe_head_address=a_sign->allo_head_address;
		fe_first->fe_size=a_sign->allo_size;
		fe_first->fe_tail_address=a_sign->allo_tail_address;
		fe_first->front=NULL;
		fe_first->next=NULL;
		fe_tail=fe_first;
	}
	else{
	if(a_sign->allo_tail_address<fe_first->fe_head_address)
	{
		
      if(a_sign->allo_tail_address+1==fe_first->fe_head_address)
	  {
		  fe_first->fe_head_address=a_sign->allo_head_address;
		  fe_first->fe_size+=a_sign->allo_size;
	  }
	  
	  else
	  {
          p=(fre *)malloc(sizeof(fre));
		  p->fe_head_address=a_sign->allo_head_address;
		  p->fe_tail_address=a_sign->allo_tail_address;
		  p->fe_size=a_sign->allo_size;
		  p->front=NULL;
		  p->next=fe_first;
		  fe_first->front=p;
		  fe_first=p;
	  }
	}
	else if(a_sign->allo_head_address>fe_tail->fe_tail_address)
	{
		if(a_sign->allo_head_address==fe_tail->fe_tail_address+1)
		{
			fe_tail->fe_tail_address=a_sign->allo_tail_address;
			fe_tail->fe_size+=a_sign->allo_size;
		}
		else
		{
			p=(fre *)malloc(sizeof(fre));
			p->fe_head_address=a_sign->allo_head_address;
			p->fe_tail_address=a_sign->allo_tail_address;
			p->fe_size=a_sign->allo_size;
			p->next=NULL;
			p->front=fe_tail;
			fe_tail->next=p;
			fe_tail=p;
		}
	}
	else
	{
		if((fe_first==fe_tail)&&fe_first->fe_tail_address==a_sign->allo_head_address+1)
		{
		  fe_first->fe_tail_address=a_sign->allo_tail_address;
          fe_first->fe_size+=a_sign->allo_size;
		  return;
		}
		fre * move=fe_first;
		bool tool=true;
		while(tool)
		{
		if((a_sign->allo_head_address<move->next->fe_head_address)&&
				(a_sign->allo_head_address>move->fe_head_address)){
			if(	(move->fe_tail_address+1==a_sign->allo_head_address)&&
				(a_sign->allo_tail_address+1==move->next->fe_head_address))
			{
				move->fe_size=move->fe_size+move->next->fe_size+a_sign->allo_size;
				move->fe_tail_address=move->next->fe_tail_address;
				p=move->next;
				move->next=move->next->next;
				if(p->next!=NULL){
					move->next->front=move;}
				free(p);
				p=0;
				tool=false;
			}
			else if(tool&&(move->fe_tail_address+1==a_sign->allo_head_address))
			{
				move->fe_size+=a_sign->allo_size;
				move->fe_tail_address=a_sign->allo_tail_address;
				tool=false;
			}
			else if(tool&&(a_sign->allo_tail_address+1==move->next->fe_head_address))
			{
				move->next->fe_head_address=a_sign->allo_head_address;
				move->next->fe_size+=a_sign->allo_size;
				tool=false;
			}
			else if(tool)
			{
				p=(fre *)malloc(sizeof(fre));
				p->next=move->next;
				move->next->front=p;
				move->next=p;
				p->front=move;
				p->fe_head_address=a_sign->allo_head_address;
				p->fe_size=a_sign->allo_size;
				p->fe_tail_address=a_sign->allo_tail_address;
				tool=false;
			}
			
			}
          move=move->next;
		}

	}
	}
  
}



void bestfit_free()
{
	fre * left=NULL;
	fre * right=NULL;
	fre * move=fe_first;
	while(move!=NULL)
	{
		if(move->fe_tail_address+1==a_sign->allo_head_address)
			left=move;
		if(a_sign->allo_tail_address+1==move->fe_head_address)
			right=move;
		move=move->next;
	}