//11.1	實(shí)驗(yàn)一代碼：
#include "basic.h"
#include <iostream>
using namespace std;
#include "string.h"

pnode *proot;//進(jìn)程樹鏈表根結(jié)點(diǎn)
pnode *plink;//進(jìn)程樹鏈表指針


bool isExistPc(int pcid)
{
	pnode *p;
	for(p=plink; p; p=p->next)//遍歷進(jìn)程樹鏈表
	{	
		if(p->node->pid == pcid)//進(jìn)程存在		
			return true;//退出		
	}
	return false;
}

//create process of *para
int createpc(int *para)
{
	//add your code
	pnode *p,*p1,*pp;

	for(p=plink; p; p=p->next)//遍歷進(jìn)程樹鏈表
	{		
		if(p->node->pid == para[1]) //找到了新加入進(jìn)程的父進(jìn)程pid
		{
			pp = p;//保存該父進(jìn)程結(jié)點(diǎn)的鏈表指針
		}
	}
	
	//創(chuàng)建新進(jìn)程
	p1 = new pnode;//分配新進(jìn)程結(jié)構(gòu)空間（每次動態(tài)創(chuàng)建PCB）
	p1->node=new pcb;//創(chuàng)建空白PCB
	p1->node->pid = para[0]; //寫入新進(jìn)程PID
	p1->node->ppid = para[1];//寫入新進(jìn)程的父進(jìn)程PPID
	p1->node->prio = para[2];//寫入新進(jìn)程的優(yōu)先級PRIO
	p1->node->resource = 0;//獲得資源數(shù)
	p1->node->state = -1;//進(jìn)入等待隊(duì)列(-1等待，1執(zhí)行，0執(zhí)行完畢)
	p1->node->tottime = 0;//等待總時(shí)間
	p1->sub = NULL;//最老子進(jìn)程
	p1->next = NULL;
	p1->brother = NULL;//最大的弟弟進(jìn)程	 

	//add to process tree
	if(!pp->sub)//直接加入到父進(jìn)程結(jié)點(diǎn)下，作為其父進(jìn)程的第一個(gè)孩子
	{
		pp->sub = p1;//鏈表中為連接新結(jié)點(diǎn)的父親結(jié)點(diǎn)保存其新孩子指針
		p1->linkpp = pp;//鏈表中為新孩子保存連接他的父親指針
	}
	else//加入到兄弟結(jié)點(diǎn)最后（即父進(jìn)程結(jié)點(diǎn)下的孩子結(jié)點(diǎn)最后）
	{
		for(p=pp->sub;p->brother;p=p->brother);
		{
			p->brother=p1;//鏈表中為連接新結(jié)點(diǎn)的兄弟結(jié)點(diǎn)保存其新兄弟指針
			p1->linkpp=p;//鏈表中為新兄弟保存連接他的兄弟指針
		}
	}

	// add to process link
	for(p=plink; p->next; p=p->next);//連接原來在新結(jié)點(diǎn)后面的進(jìn)程樹(為新進(jìn)程分配內(nèi)存空間和棧空間)
		p->next=p1;	

	return 0;
}


//show process detail
void showdetail()
{
	//add your code
	pnode *p,*p1;
	p = plink;
	for( ; p; )
	{
		//先打印父親結(jié)點(diǎn)
		printf("%d(prio %d):    ",p->node->pid,p->node->prio);
		p1 = p->sub;//指向其下一個(gè)孩子進(jìn)程
		
		//然后打印該父親的孩子進(jìn)程的兄弟
		for(;p1;)
		{
			printf("%d(prio %d)    ",p1->node->pid,p1->node->prio);
			p1 = p1->brother;//指向其下一個(gè)兄弟進(jìn)程
		}
		printf("\n");

		//再打印新的父親結(jié)點(diǎn)
		p = p->next;
	}
	printf("\n");
}


//create process of *para
void SetPcExe(int *para)//執(zhí)行位于就緒隊(duì)列隊(duì)首的某進(jìn)程
{
	pnode *p;
	///////////////////////__就緒即cpu與資源可獲得

___///////////////////////////////////////////////////	
	for(p=plink; p; p=p->next)//遍歷進(jìn)程樹鏈表(模擬單處理機(jī)，執(zhí)行某進(jìn)程前先獲得空閑cpu)
	{
		if(p->node->state == 1 && p->node->pid!=para[0])//若存在其它進(jìn)程正在被處理
		{
			p->node->state = 0;//模擬單處理機(jī):該進(jìn)程執(zhí)行完畢，并釋放cpu。
			cout<<"原來正在運(yùn)行的進(jìn)程id為 "<<p->node->pid<<" 已經(jīng)執(zhí)行完畢；";
			if( p->node->resource!=0)//擁有資源
			{
				p->node->resource = 0;//釋放該進(jìn)程占有的資源
				cout<<"并釋放所有占有的資源!\n";				
			}				
			
			break;//單處理機(jī)釋放一次，cpu便空閑了。該進(jìn)程可以獲得cpu
		}		
	}
	//////////////////////////////////////////////////////////////////////////
	
	for(p=plink; p; p=p->next)//遍歷進(jìn)程樹鏈表
	{
		if(p->node->pid == para[0])//若存在將被處理的進(jìn)程(且假設(shè)該進(jìn)程已是就緒隊(duì)首)
		{   //修改PCB
			p->node->resource = 8;//獲得8個(gè)資源(實(shí)際應(yīng)該是取資源地址)
			p->node->state = 1;//該進(jìn)程處于執(zhí)行狀態(tài)
			cout<<"進(jìn)程號為"<<p->node->pid<<"的進(jìn)程已經(jīng)獲得8個(gè)資源并處于執(zhí)行狀態(tài)\n";
			break;
		}		
	}
}


void DelPcTree(pnode *t)//遞歸刪除樹及鏈表里面t的所有子孫進(jìn)程(包括t)，并釋放pcb內(nèi)存空間
{
	if(t == NULL)
		return;
	
	pnode *q = t->sub,*p;//q為t的最老孩子結(jié)點(diǎn)鏈表指針
	while(q!=NULL)//q存在孩子
	{
		p = q->brother;//保存q的兄弟指針為p(導(dǎo)致后序遍歷)
		DelPcTree(q);//后根遍歷(查找并刪除)q的所有子孫進(jìn)程

		if (t->node->state==1)//處于執(zhí)行狀態(tài)
		{
			t->node->state = 0;//置為停止?fàn)顟B(tài)
			cout<<"id為 "<<t->node->pid<<" 的進(jìn)程已經(jīng)停止執(zhí)行狀態(tài)；";
			if( t->node->resource!=0)//擁有資源
			{
				t->node->resource = 0;//釋放該進(jìn)程占有的資源
				cout<<"并成功釋放占有的所有資源!\n";				
			}				
			//(資源的信號量++)
			//判斷是否有新進(jìn)程可獲得資源和cpu并調(diào)用下一個(gè)進(jìn)程
		}

		q = p;//后根遍歷刪除q的所有子孫進(jìn)程	
	}

	pnode *temp;
	for(temp=plink; temp!=NULL; temp=temp->next) 
	{
		if(temp->next == t) //find parent pcb 
		{ 
			temp->next = t->next; //刪除單鏈表里的進(jìn)程結(jié)點(diǎn)
		}
	}

	delete t;//釋放進(jìn)程的原動態(tài)申請的空白pcb及鏈表空間
}


int deletepc(int para)//刪除id為para的進(jìn)程
{	
	//判斷并保存要刪除進(jìn)程的鏈表指針p1
	pnode *p,*p1; 
	int pflag=0,sflag;  
	for(p=plink; p; p=p->next) //遍歷尋找
	{
		if(p->node->pid == para) //find parent pcb 
		{ 
			sflag=1; 
			p1 = p; //p1為要刪除的進(jìn)程id的鏈表指針			
		}
	}
	if(!sflag) //sflag==0
	{ 
		printf("pid %d 還沒有被創(chuàng)建!\n",para); 
		return -3;
	}


	//從樹的父親及兄弟級刪除該進(jìn)程
	bool delpcintree = false;
	for(p=plink;p&&!delpcintree;p=p->next) 
	{
		if(p->node->pid == p1->node->ppid) //找到要刪除的p1的父進(jìn)程p 
		{ 
			if (p->sub==p1)//要刪除的進(jìn)程為其父進(jìn)程的第一孩子
			{
				p->sub = p1->brother;
				delpcintree=true;
			}
			else if (p->sub!=p1)//要刪除的進(jìn)程為其父進(jìn)程的非第一孩子
			{
				for(pnode*tmp=p->sub; tmp!=NULL; tmp=tmp->brother)//遍歷其父進(jìn)程的孩子進(jìn)程
				{
					if (tmp->brother->node->pid == p1->node->pid) //找到要刪除進(jìn)程的哥

哥進(jìn)程tmp
					{
						tmp->brother = p1->brother;//刪除該進(jìn)程
						delpcintree=true;
						break;
					}
				}		
			}	
		}
	}	
	
	DelPcTree(p1);//要刪除進(jìn)程的鏈表指針p1
	return 0;
}


void CreateTree()
{
	int pc[10][3];
	pc[0][0] = 1;	pc[1][0] = 2;	pc[2][0] = 3;	pc[3][0] = 4;	pc[4][0] = 5;
	pc[0][1] = 0;	pc[1][1] = 0;	pc[2][1] = 0;	pc[3][1] = 2;	pc[4][1] = 2;
	pc[0][2] = 1;	pc[1][2] = 1;	pc[2][2] = 1;	pc[3][2] = 4;	pc[4][2] = 4;
	
	pc[5][0] = 6;	pc[6][0] = 7;	pc[7][0] = 8;	pc[8][0] = 9;	pc[9][0] = 10;
	pc[5][1] = 4;	pc[6][1] = 6;	pc[7][1] = 5;	pc[8][1] = 6;	pc[9][1] = 2;
	pc[5][2] = 6;	pc[6][2] = 1;	pc[7][2] = 2;	pc[8][2] = 2;	pc[9][2] = 2;

	int *para;
	for (int i=0; i<=9; i++)
	{
		para = pc[i];//獲得參數(shù) [1 0 2]	
		//		cout << pc[i][0]<<" "<< pc[i][1]<<" "<<pc[i][2]<<endl;
		//		continue;		
		createpc(pc[i]);//創(chuàng)建進(jìn)程
		cout <<"進(jìn)程 ("<< para[0]<<","<< para[1]<<","<< para[2]<<") 創(chuàng)建成功!\n";		
	}
}

void help()//顯示幫助信息
{
	cout<<" 1.顯示當(dāng)前進(jìn)程樹 show \t 2.創(chuàng)建進(jìn)程 cpc(id,pid,prio)\t 3.命令提示help\n 4.進(jìn)程刪除 del(id)

\t";
	cout<<" 5.執(zhí)行進(jìn)程 exe(id)\t\t 6.退出 exit\n\n";
}

//don't change
void main()
{
	initerror();//初始化錯(cuò)誤信息
	short cflag,pflag;
	char cmdstr[32]; 
	
	//創(chuàng)建根進(jìn)程(0,-1,0)
	proot = new pnode;//申請新進(jìn)程對象空間
	proot->node=new pcb;//創(chuàng)建空白進(jìn)程
	proot->node->pid=0;//根進(jìn)程PID
	proot->node->ppid=-1;//父進(jìn)程pPID
	proot->node->prio=0;//根進(jìn)程優(yōu)先級prio
	proot->next=NULL;//鏈表指針
	proot->sub=NULL;//根進(jìn)程的子進(jìn)程
	proot->brother=NULL;//根進(jìn)程的兄弟進(jìn)程
	plink = proot;

	CreateTree();//初始化一顆樹！！！！！！！！

	help();//顯示幫助信息
	
	for(;;)
	{
		cflag = 0;//error comannd
		pflag = 0;//error parameter
		char str[20]="";
		printf("cmd:");
		scanf("%s",cmdstr);//輸入命令	
		
		//exit the programe	
		if(!strcmp(cmdstr,"exit"))  
			break;
		
		if(!strcmp(cmdstr,"help"))  //顯示幫助信息
		{
			help();
			continue;
		}
		
		//顯示當(dāng)前進(jìn)程樹
		if(!strcmp(cmdstr,"show"))
		{
			cflag = 1;
			pflag = 1;
			showdetail();
			continue;
		}
	
		strncpy(str,cmdstr,3);//把輸入命令的前3個(gè)字符賦給str,因?yàn)椴恍枰袛鄥?shù)	
		
		//創(chuàng)建進(jìn)程
		if(!strcmp(str,"cpc"))
		{
			int *para;
			char *s, *pcid;
			s = strstr(cmdstr,"cpc");//"cpc"在cmdstr中第一次出現(xiàn)的位置
			
			if(s)//input is create process
			{
				cflag=1;
				para = (int *)malloc(3);
				pcid = substr(s,instr(s,'(')+1,strlen(s)-2);//getparameter [1,0,2]
				para = strtoarray(pcid);//獲得參數(shù) [1 0 2]	
				if(!isExistPc(para[0]))//新進(jìn)程還沒有被創(chuàng)建(為新進(jìn)程申請獲得唯一的數(shù)字標(biāo)識

符)
				{
					if(isExistPc(para[1]))////找到了新加入進(jìn)程的父進(jìn)程
					{
						createpc(para);//創(chuàng)建進(jìn)程
						cout <<"進(jìn)程("<< para[0]<<","<< para[1]<<","<< para[2]<<") 

創(chuàng)建成功!\n\n";
						pflag = 1;	
						continue;
					}
					cout <<"The process' parent id = "<<para[1]<<"is not exsit!\n\n";
					continue;
				}
				cout <<"The process id = "<<para[0]<<"is already exsit!\n\n";
				continue;
			}		
			
			else if(!pflag)
				geterror(1);
		}

		//執(zhí)行進(jìn)程
		if (!strcmp(str,"exe") )
		{			
			int *para;
			char *s, *s1;
			s = strstr(cmdstr,"exe");			
			if(s)
			{
				cflag = 1;
				para = (int *)malloc(3);				
				s1 = substr(s,instr(s,'(')+1,strlen(s)-2);
				para = strtoarray(s1);
				SetPcExe(para);//執(zhí)行進(jìn)程
				continue;
			}
		}

		if (!strcmp(str,"del") ) //delete process
		{
			int *para;
			char *s, *s1;
			s = strstr(cmdstr,"del");//delete process
			
			if(s)
			{
				cflag=1;
				para = (int *)malloc(3);
				s1 = substr(s,instr(s,'(')+1,strlen(s)-2);
				para = strtoarray(s1);

				if( isExistPc(para[0]) )//要刪除的進(jìn)程存在
				{	
					if (para[0] == 0) 
					{
						cout << "你沒有權(quán)限來刪除根進(jìn)程!\n\n";
						continue;
					}
					
					cout << "刪除前的進(jìn)程樹為:\n\n";
					showdetail();
					deletepc(para[0]);
					cout <<"id為 "<< para[0]<<" 的進(jìn)程結(jié)束成功!"<<"\n刪除后的進(jìn)程樹

為:\n\n";
					showdetail();
					continue;				
				}

				cout <<"你要刪除的進(jìn)程 "<< para[0]<<" 不存在 !\n\n";
				continue;
			}
		}
		
		if(!cflag)
			geterror(0);		
	}
}