// 功能:
//   《計算機操作系統》實驗
//   首次適應性算法
//   摸擬 動態分區 存儲管理方式的主存 分配 和 回收
////////////////////////////////////////////////////////////

 

#include "iostream.h"
#include "iomanip.h"

#define ERR_NOFREEAREA 1
#define ERR_NOADEQUACYAREA 2
#define ERR_ALLOCATED 4

#define ERR_NOJOBS 1
#define ERR_NOSUCHJOB 2
#define ERR_RECLAIMED 4


typedef struct tagUsedNode
{
 long address;
 long length;
 int flag; //作業名
 struct tagUsedNode *next;
} USED_AREA , *USED_TABLE;

typedef struct tagFreeNode
{
 long address;
 long length;
 struct tagFreeNode *next;
} FREE_AREA , *FREE_TABLE;

//空閑區、作業區鏈表
USED_TABLE usedTable = NULL;
FREE_TABLE freeTable = NULL;


//給作業分配空間
//jobname: 作業名
//jobsize: 作業所需空間大小
int Allocate( int jobname , long jobsize )
{
 //如果沒有空閑區
 if( freeTable == NULL )
  return ERR_NOFREEAREA;
 FREE_TABLE p = freeTable;
 FREE_TABLE q = p;
 //找首次適應空閑區
 while( p != NULL && p->length < jobsize )
 {
  q = p;
  p = p->next;
 }
 //如果找不到有足夠空間的分區
 if( p == NULL )
  return ERR_NOADEQUACYAREA;

 USED_TABLE x = new USED_AREA;
 x->address = p->address;
 x->length = jobsize;
 x->flag = jobname;
 x->next = NULL;

 //如果該分區大于作業需求，空間大小減去作業大小
 if( p->length > jobsize )
 {
  p->length -= jobsize;
  p->address += jobsize;
 }
 //如果該分區等于作業大小，刪除該分區
 else
 {
  if( p == freeTable )
   freeTable = NULL;
  else
   q->next = p->next;
  delete p;
 }
 //作業加入“作業表”中
 USED_TABLE r = usedTable;
 USED_TABLE t = r;

 while( r != NULL && r->address < x->address )
 {
  t = r;
  r = r->next;
 }
 
 if( usedTable == NULL )
  usedTable = x;
 else
 {
  x->next = r;
  t->next = x;
 }

 return ERR_ALLOCATED;
}


//回收作業空間
//jobname: 作業名
int Reclaim( int jobname )
{
 if( usedTable == NULL )
  return ERR_NOJOBS;
 USED_TABLE p = usedTable;
 USED_TABLE q = p;
 while( p != NULL && p->flag != jobname )
 {
  q = p;
  p = p->next;
 }
 //如果沒有該作業
 if( p == NULL )
  return ERR_NOSUCHJOB;
 //回收后的空間加入到空閑區
 FREE_TABLE r = freeTable;
 FREE_TABLE t = r;
 FREE_TABLE x;
 while( r != NULL && r->address < p->address )
 {
  t = r;
  r = r->next;
 }

 x = new FREE_AREA;
 x->address = p->address;
 x->length = p->length;
 x->next = NULL;

 if( r == freeTable )
 {
  x->next = r;
  freeTable = x;
  t = freeTable;
 }
 else
 {
  x->next = r;
  t->next = x;
 }
 //合并分區
 while( t->next != NULL && t->address + t->length == t->next->address )
 {
  t->length += t->next->length;
  r = t->next;
  t->next = t->next->next;
  delete r;
 }
 //刪除該作業
 if( p == usedTable )
 {
  usedTable = usedTable->next;
 }
 else
  q->next = p->next;
 delete p;

 return ERR_RECLAIMED;
}

int Init()
{
 freeTable = new FREE_AREA;
 freeTable->address = 0;
 freeTable->length = 1024;
 freeTable->next = NULL;
 return 1;
}

void jobrequest()
{
 int jobname;
 int jobsize;

 cout<<"...................."<<endl;
 cout<<"作業名: ";
 cin >> jobname;
 cout<<"作業長度: ";
 cin >> jobsize;

 if( Allocate( jobname , jobsize ) == ERR_ALLOCATED )
  cout<<"該作業已成功獲得所需空間"<<endl;
 else
  cout<<"該作業沒有獲得所需空間"<<endl;
 cout<<"...................."<<endl;
}

void jobreclaim()
{
 int jobname;
 cout<<"...................."<<endl;
 cout<<"作業名: ";
 cin >>jobname;
 int result = Reclaim( jobname );
 if(  result == ERR_RECLAIMED )
  cout<<"該作業已成功回收"<<endl;
 else if( result == ERR_NOSUCHJOB || result == ERR_NOJOBS )
  cout<<"系統沒有作業或該作業不存在"<<endl;
 cout<<"...................."<<endl;
}

void freeTablePrint()
{
 cout<<"........................................"<<endl;
 cout<<setw(10)<<"address"<<setw(10)<<"length"<<setw(10)<<"state"<<endl<<endl;
 FREE_TABLE p = freeTable;
 USED_TABLE q = usedTable;
 int x , y;
 while( p || q )
 {
  if( p )
   x = p->address;
  else
   x = 0x7fffffff;
  if( q )
   y = q->address;
  else
   y = 0x7fffffff;

  if( x < y )
  {
   cout<<setw(10)<<p->address<<setw(10)<<p->length<<setw(10)<<"空閑"<<endl;
   p = p->next;
  }
  if( x > y )
  {
   cout<<setw(10)<<q->address<<setw(10)<<q->length<<setw(10)<<"已分配"<<setw(10)<<"ID="<<q->flag<<endl;
   q = q->next;
  }
 }
 cout<<"........................................"<<endl;

}

void main()
{
 Init();

 int choose;
 bool exitFlag = false;
 while( !exitFlag )
 {
  cout<<"選擇功能項 ( 0 -　退出   1 - 分配主存  2 - 回收主存  3 - 顯示主存 )"<<endl;
  cout<<">";
  cin>>choose;
  switch( choose )
  {
  case 0:
   exitFlag = true;
   break;
  case 1:
   jobrequest();
   break;
  case 2:
   jobreclaim();
   break;
  case 3:
   freeTablePrint();
   break;
  }
 }
}