/*可变分区回收算法
将回收的内存插入到自由主存队列中,供下次分配内存时使用.在本模拟程序中,自由主存队列的排序原则是按地址排列的(即低地址的可用空闲区间在队列前面,从而配套使用的放置策略就是首次适应法了).
分区回收有四种情况：
1.待回收区(以下称为自由块)与自由主存队列中有上邻空闲区,回收时直接将其大小加到其上邻空闲区的大小上即可.
2.自由块有下邻空闲区,此时需要将前驱的next指针改为指向自由块首址,而将自由块的next指针指向其下邻空闲区中的下一节点,同时合并大小.
3.自由块既有上邻区也有下邻区,此时需要将其上邻区的next指针指向自由块下邻区的next指向的地址,同时合并三个可用分区的大小.
4.自由块不存在空闲邻区,是独立的一块.此时将其插入到自由主存队列中即可.由于在合并分区的时候已经是以按地址来放置队列的,故无须再对队列中元素进行排序了.

模拟实现：
先分配256个字节作为模拟的主存(以下称虚主存),然后插入4个任务(即task1,task2,task3,task4).每个分区描述器占了6个字节,free_head是自由主存队列的头指针.回收分区时,每回收一次后,系统又重新复位了任务在虚主存中(便于模拟四次的回收情况).其中task1有上邻空闲区(属第1种情况),task2属第4种情况,task3属于第2种情况,task4属于第3种情况.输出信息时是从虚主存的低地址开始的,依次输出队列中的各可用空间(含分区描述器大小).
*/

/*本程序在TC2.0下编译通过——铁木箱子*/
#include<stdio.h>
#include<stdlib.h>
typedef struct PD  /* 分区描述器数据结构 */
{
 int flag;
 int size;
 struct PD *next;
}node,*LINK;
LINK free_head;
LINK task1,task2,task3,task4;  /* tasks */
char *p;

void Init()  /*初始化模拟内存内的任务和空闲区*/
{
 char *tmp;
 LINK cursor; /* temp pointer */
 tmp=p;
 task1=(LINK)(tmp+30);  /* 事先各作业的分配情况 */
 task2=(LINK)(tmp+70);
 task3=(LINK)(tmp+130);
 task4=(LINK)(tmp+196);
 task1->flag=1;task1->size=40;task1->next=NULL;
 task2->flag=1;task2->size=60;task2->next=NULL;
 task3->flag=1;task3->size=30;task3->next=NULL;
 task4->flag=1;task4->size=35;task4->next=NULL;

 free_head=(LINK)tmp;   /* free memory queue */
 cursor=free_head;
 cursor->flag=0;cursor->size=30;cursor->next=(LINK)(tmp+160);
 cursor=cursor->next;
 cursor->flag=0;cursor->size=36;cursor->next=(LINK)(tmp+231);
 cursor=cursor->next;
 cursor->flag=0;cursor->size=25;cursor->next=NULL;
}

void PrintInfo(int n)  /* 打印自由主存队列信息 */
{
 LINK temp;
 temp=free_head;
 printf("nAfter free task%d,free memory are:",n);
 while(temp)
    {
     printf("%-3d  ",temp->size);
     temp=temp->next;
    }
 printf("n");
}