/* algo8-1.c 邊界標識法。實現算法8.1的程序 */
 #include"c1.h"
 #include"c8-1.h"
 #define MAX 1000 /* 可利用空間的大小(以WORD的字節數為單位) */
 #define e 10 /* 塊的最小尺寸-1(以WORD的字節數為單位) */

 Space AllocBoundTag(Space *pav,int n) /* 算法8.1(首次擬合法) */
 { /* 若有不小于n的空閑塊,則分配相應的存儲塊,并返回其首地址;否則返回NULL */
   /* 若分配后可利用空間表不空，則pav指向表中剛分配過的結點的后繼結點 */
   Space p,f;
   for(p=*pav;p&&p->size<n&&p->rlink!=*pav;p=p->rlink); /* 查找不小于n的空閑塊 */
   if(!p||p->size<n) /* 找不到，返回空指針 */
     return NULL;
   else /* p指向找到的空閑塊 */
   {
     f=FootLoc(p); /* 指向底部 */
     *pav=p->rlink; /* pav指向*p結點的后繼結點 */
     if(p->size-n<=e) /* 整塊分配，不保留<=e的剩余量 */
     {
       if(*pav==p) /* 可利用空間表變為空表 */
         *pav=NULL;
       else /* 在表中刪除分配的結點 */
       {
         (*pav)->a.llink=p->a.llink;
         p->a.llink->rlink=*pav;
       }
       p->tag=f->tag=1; /* 修改分配結點的頭部和底部標志 */
     }
     else /* 分配該塊的后n個字(高地址部分) */
     {
       f->tag=1; /* 修改分配塊的底部標志 */
       p->size-=n; /* 置剩余塊大小 */
       f=FootLoc(p); /* 指向剩余塊底部 */
       f->tag=0; /* 設置剩余塊底部 */
       f->a.uplink=p;
       p=f+1; /* 指向分配塊頭部 */
       p->tag=1; /* 設置分配塊頭部 */
       p->size=n;
     }
     return p; /* 返回分配塊首地址 */
   }
 }

 void Reclaim(Space *pav,Space *p)
 { /* 邊界標識法的回收算法 */
   Space s=(*p-1)->a.uplink,t=*p+(*p)->size; /* s、t分別指向釋放塊的左、右鄰塊(空閑時)的首地址 */
   int l=(*p-1)->tag,r=(*p+(*p)->size)->tag; /* l、r分別指示釋放塊的左、右鄰塊是否空閑 */
   if(!*pav) /* 可利用空間表空 */
   { /* 將釋放塊加入到pav所指的可利用空間表中 */
     *pav=(*p)->a.llink=(*p)->rlink=*p; /* 頭部域的兩個指針及pav均指向釋放塊 */
     (*p)->tag=0; /* 修改頭部域塊標志為空閑 */
     (FootLoc(*p))->a.uplink=*p; /* 修改尾部域 */
     (FootLoc(*p))->tag=0;
   }
   else /* 可利用空間表不空 */
   {
     if(l==1&&r==1) /* 左右鄰區均為占用塊 */
     {
       (*p)->tag=0; /* 修改頭部域塊標志為空閑 */
       (FootLoc(*p))->a.uplink=*p; /* 修改尾部域 */
       (FootLoc(*p))->tag=0;
       (*pav)->a.llink->rlink=*p; /* 將p所指結點(剛釋放的結點)插在pav所指結點之前 */
       (*p)->a.llink=(*pav)->a.llink;
       (*p)->rlink=*pav;
       (*pav)->a.llink=*p;
       *pav=*p; /* 修改pav,令剛釋放的結點為下次分配時的最先查詢的結點 */
     }
     else if(l==0&&r==1) /* 左鄰區為空閑塊,右鄰區為占用塊 */
     { /* 合并左鄰塊和釋放塊 */
       s=(*p-1)->a.uplink; /* 左鄰空閑塊的頭部地址 */
       s->size+=(*p)->size; /* 設置新的空閑塊大小 */
       t=FootLoc(*p); /* 設置新的空閑塊底部 */
       t->a.uplink=s;
       t->tag=0;
     }
     else if(l==1&&r==0) /* 右鄰區為空閑塊,左鄰區為占用塊 */
     { /* 合并右鄰塊和釋放塊 */
       (*p)->tag=0; /* P為合并后的結點頭部地址 */
       (*p)->a.llink=t->a.llink; /* p的前驅為原t的前驅 */
       (*p)->a.llink->rlink=*p; /* p的前驅的后繼為p */
       (*p)->rlink=t->rlink; /* p的后繼為原t的后繼 */
       (*p)->rlink->a.llink=*p; /* p的后繼的前驅為p */
       (*p)->size+=t->size; /* 新的空閑塊的大小 */
       (FootLoc(t))->a.uplink=*p; /* 底部(原t的底部)指針指向新結點的頭部 */
       if(*pav==t) /* 可利用空間表的頭指針指向t(t已不是空閑結點首地址了) */
         *pav=*p; /* 修改pav,令剛釋放的結點為下次分配時的最先查詢的結點 */
     }
     else /* 左右鄰區均為空閑塊 */
     {
       s->size+=(*p)->size+t->size; /* 設置新結點的大小 */
       t->a.llink->rlink=t->rlink; /* 刪去右鄰空閑塊結點 */
       t->rlink->a.llink=t->a.llink;
       (FootLoc(t))->a.uplink=s; /* 新結點底部(原t的底部)指針指向其頭部 */
       if(*pav==t) /* 可利用空間表的頭指針指向t(t已不是空閑結點首地址了) */
         *pav=s; /* 修改pav,令剛釋放的結點為下次分配時的最先查詢的結點 */
     }
   }
   *p=NULL; /* 令剛釋放的結點的指針為空 */
 }

 void Print(Space p)
 { /* 輸出p所指的可利用空間表 */
   Space h,f;
   if(p) /* 可利用空間表不空 */
   {
     h=p; /* h指向第一個結點的頭部域(首地址) */
     f=FootLoc(h); /* f指向第一個結點的底部域 */
     do
     {
       printf("塊的大小=%d 塊的首地址=%u ",h->size,f->a.uplink); /* 輸出結點信息 */
       printf("塊標志=%d(0:空閑 1:占用) 鄰塊首地址=%u\n",h->tag,f+1);
       h=h->rlink; /* 指向下一個結點的頭部域(首地址) */
       f=FootLoc(h); /* f指向下一個結點的底部域 */
     }while(h!=p); /* 沒到循環鏈表的表尾 */
   }
 }

 void PrintUser(Space p[])
 { /* 輸出p數組所指的已分配空間 */
   int i;
   for(i=0;i<MAX/e;i++)
     if(p[i]) /* 指針不為0(指向一個占用塊) */
     {
       printf("塊%d的首地址=%u ",i,p[i]); /* 輸出結點信息 */
       printf("塊的大小=%d 塊頭標志=%d(0:空閑 1:占用)",p[i]->size,p[i]->tag);
       printf(" 塊尾標志=%d\n",(FootLoc(p[i]))->tag);
     }
 }

 void main()
 {
   Space pav,p; /* 空閑塊指針 */
   Space v[MAX/e]={NULL}; /* 占用塊指針數組(初始化為空) */
   int n;
   printf("結構體WORD為%d個字節\n",sizeof(WORD));
   p=(WORD*)malloc((MAX+2)*sizeof(WORD)); /* 申請大小為MAX*sizeof(WORD)個字節的空間 */
   p->tag=1; /* 設置低址邊界,以防查找左右鄰塊時出錯 */
   pav=p+1; /* 可利用空間表的表頭 */
   pav->rlink=pav->a.llink=pav; /* 初始化可利用空間(一個整塊) */
   pav->tag=0;
   pav->size=MAX;
   p=FootLoc(pav); /* p指向底部域 */
   p->a.uplink=pav;
   p->tag=0;
   (p+1)->tag=1; /* 設置高址邊界,以防查找左右鄰塊時出錯 */
   printf("初始化后，可利用空間表為:\n");
   Print(pav);
   n=300;
   v[0]=AllocBoundTag(&pav,n);
   printf("分配%u個存儲空間后，可利用空間表為:\n",n);
   Print(pav);
   PrintUser(v);
   n=450;
   v[1]=AllocBoundTag(&pav,n);
   printf("分配%u個存儲空間后，pav為:\n",n);
   Print(pav);
   PrintUser(v);
   n=300; /* 分配不成功 */
   v[2]=AllocBoundTag(&pav,n);
   printf("分配%u個存儲空間后(不成功)，pav為:\n",n);
   Print(pav);
   PrintUser(v);
   n=242; /* 分配整個塊(250) */
   v[2]=AllocBoundTag(&pav,n);
   printf("分配%u個存儲空間后(整塊分配)，pav為:\n",n);
   Print(pav);
   PrintUser(v);
   printf("回收v[0](%d)后(當pav空時回收)，pav為:\n",v[0]->size);
   Reclaim(&pav,&v[0]); /* pav為空 */
   Print(pav);
   PrintUser(v);
   printf("1按回車鍵繼續");
   getchar();
   printf("回收v[2](%d)后(左右鄰區均為占用塊),pav為:\n",v[2]->size);
   Reclaim(&pav,&v[2]); /* 左右鄰區均為占用塊 */
   Print(pav);
   PrintUser(v);
   n=270; /* 查找空間足夠大的塊 */
   v[0]=AllocBoundTag(&pav,n);
   printf("分配%u個存儲空間后(查找空間足夠大的塊)，pav為:\n",n);
   Print(pav);
   PrintUser(v);
   n=30; /* 在當前塊上分配 */
   v[2]=AllocBoundTag(&pav,n);
   printf("分配%u個存儲空間后(在當前塊上分配)，pav為:\n",n);
   Print(pav);
   PrintUser(v);
   printf("回收v[1](%d)后(右鄰區為空閑塊,左鄰區為占用塊)，pav為:\n",v[1]->size);
   Reclaim(&pav,&v[1]); /* 右鄰區為空閑塊,左鄰區為占用塊 */
   Print(pav);
   PrintUser(v);
   printf("2按回車鍵繼續");
   getchar();
   printf("回收v[0](%d)后(左鄰區為空閑塊,右鄰區為占用塊)，pav為:\n",v[0]->size);
   Reclaim(&pav,&v[0]); /* 左鄰區為空閑塊,右鄰區為占用塊 */
   Print(pav);
   PrintUser(v);
   printf("回收v[2](%d)后(左右鄰區均為空閑塊),pav為:\n",v[2]->size);
   Reclaim(&pav,&v[2]); /* 左右鄰區均為空閑塊 */
   Print(pav);
   PrintUser(v);
 }