release.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/*******************************************/
/*         基于边界标识法的回收算法        */
/*  文件名：release.c  函数名：release()   */
/*******************************************/
#include <stdio.h>
#include <stdlib.h>
#include "noder.h"
void release (noder * pav,noder *p)
{/*pav为可利用空间表的表头指针，p为要释放的占用块的首地址*/
  char ch;
  int n,n1;
  noder *q,*s,*f,*t,*q1;
  if ((p-1)->head.tag==1 && (p+p->head.size+2)->head.tag==1) ch='0';
  if ((p-1)->head.tag==0 && (p+p->head.size+2)->head.tag==1) ch='1';
  if ((p-1)->head.tag==1 && (p+p->head.size+2)->head.tag==0) ch='2';
  if ((p-1)->head.tag==0 && (p+p->head.size+2)->head.tag==0) ch='3';
  switch(ch)
  { case '0':  /*左、右邻区为占用块，新的空闲块插入在pav所指结点之前*/
          q=pav->head.llink; /* q为pav所指结点的前趋结点地址*/
          q->head.rlink=p;
          p->head.llink=q;
          p->head.tag=0;
          p->head.rlink=pav;
          pav->head.llink=p;
          (p+1+p->head.size)->foot.uplink=p;
          (p+1+p->head.size)->foot.tag=0;
          pav=p;/*令刚释放的结点为下次分配时最先查询的结点*/
          break;
     case '1':  /*左邻为空闲块，右邻为占用块*/
          n=p->head.size;  /*n为释放块的大小*/
          s=(p-1)->foot.uplink;  /*s为左邻空闲块的头部地址*/
          s->head.size+=n+2;   /*设置新的空闲块大小*/
          f=s+1+s->head.size;
          f->foot.uplink=s;
          f->foot.tag=0;            /*设置新空闲块的底部*/
          break;
     case '2':  /*右邻为空闲块，左邻区为占用块*/
          t=p+p->head.size+2;/*t为右邻空闲块的头部地址*/
          p->head.tag=0; /*p为合并后结点的头部地址*/
          q=t->head.llink; /*q为t结点的前趋结点的头部地址*/
          p->head.llink=q;
          p->head.rlink=p;
          q1=t->head.rlink;/*q1为t结点的后继结点的头部地址*/
          p->head.rlink=q1;
          q1->head.llink=p;
          p->head.size+=t->head.size+2;
          (t+t->head.size+1)->foot.uplink=p;/*底部指针指向新结点头部*/
          break; 
     case '3':   /*左、右邻区均为空闲块*/
          n=p->head.size;   /*n为释放区大小*/
          s=(p-1)->foot.uplink;/*左邻区的头部地址*/
          t=p+p->head.size+2;/*右邻区的头部地址*/
          n1=s->head.size+n+2+t->head.size+2;
          /*n1为新结点中space的大小*/
          s->head.size=n1;
          q=t->head.llink;
          q1=t->head.rlink;
          q->head.rlink=q1;
          q1->head.llink=q;  /*删去右邻结点*/
          (t+t->head.size+1)->foot.uplink=s;
          /*使新结点底部指针指向新结点头部*/
          break;
     }
}