// algo8-2.cpp 伙伴系統。實現算法8.2的程序
 #include"c1.h"
 #include"c8-2.h"
 #define N 100 // 占用塊個數的最大值
 Space r; // r為生成空間的首地址,全局量

 Space AllocBuddy(FreeList &avail,int n)
 { // avail[0..m]為可利用空間表,n為申請分配量,若有不小于n的空閑塊,
   // 則分配相應的存儲塊,并返回其首地址;否則返回NULL。算法8.2
   int i,k;
   Space pa,pi,pre,suc;
   for(k=0;k<=m&&(avail[k].nodesize<n+1||!avail[k].first);++k); // 查找滿足分配要求的子表
   if(k>m) // 分配失敗，返回NULL
     return NULL;
   else // 進行分配
   {
     pa=avail[k].first; // 指向可分配子表的第一個結點
     pre=pa->llink; // 分別指向前驅和后繼
     suc=pa->rlink;
     if(pa==suc)
       avail[k].first=NULL; // 分配后該子表變成空表
     else // 從子表刪去*pa結點
     {
       pre->rlink=suc;
       suc->llink=pre;
       avail[k].first=suc;
     }
     for(i=1;avail[k-i].nodesize>=n+1;++i)
     {
       pi=pa+int(pow(2,k-i));
       pi->rlink=pi;
       pi->llink=pi;
       pi->tag=0;
       pi->kval=k-i;
       avail[k-i].first=pi;
     } // 將剩余塊插入相應子表
     pa->tag=1;
     pa->kval=k-(--i);
   }
   return pa;
 }

 Space buddy(Space p)
 { // 返回相對起始地址為p,塊大小為pow(2,k)的塊的伙伴地址
   if((p-r)%int(pow(2,p->kval+1))==0) // p為前塊
     return p+int(pow(2,p->kval));
   else // p為后塊
     return p-int(pow(2,p->kval));
 }

 void Reclaim(FreeList &pav,Space &p)
 { // 伙伴系統的回收算法 將p所指的釋放塊回收到可利用空間表pav中
   Space s;
   s=buddy(p); // 伙伴塊的起始地址
   while(s>=r&&s<r+pav[m].nodesize&&s->tag==0) // 歸并伙伴塊,伙伴塊起始地址在有效范圍內且伙伴塊空閑
   { // 從鏈表上刪除該結點
     if(s->llink==s&&s->rlink==s) // 鏈表上僅此一個結點
       pav[s->kval].first=NULL; // 置此鏈表為空
     else // 鏈表上不止一個結點
     {
       s->llink->rlink=s->rlink; // 前驅的后繼為該結點的后繼
       s->rlink->llink=s->llink; // 后繼的前驅為該結點的前驅
       if(pav[s->kval].first==s) // s是鏈表的第一個結點
         pav[s->kval].first=s->rlink; // 表頭指向下一個結點
     } // 以下修改結點頭部
     if((p-r)%int(pow(2,p->kval+1))==0) // p為前塊
       p->kval++;
     else // p為后塊
     {
       s->kval=p->kval+1;
       p=s; // p指向新塊首地址
     }
     s=buddy(p); // 下一個伙伴塊的起始地址
   }
   // 以下將p插到可利用空間表中
   p->tag=0;
   if(pav[p->kval].first==NULL) // 該鏈表空
     pav[p->kval].first=p->llink=p->rlink=p;
   else // 插在表頭
   {
     p->rlink=pav[p->kval].first;
     p->llink=p->rlink->llink;
     p->rlink->llink=p;
     p->llink->rlink=p;
     pav[p->kval].first=p;
   }
   p=NULL;
 }

 void Print(FreeList p)
 { // 輸出p中所有可利用空間表
   int i;
   Space h;
   for(i=0;i<=m;i++)
   {
     if(p[i].first) // 第i個可利用空間表不空
     {
       h=p[i].first; // h指向鏈表的第一個結點的頭部域(首地址)
       do
       {
         printf("塊的大小=%d 塊的首地址=%u ",int(pow(2,h->kval)),h); // 輸出結點信息
         printf("塊標志=%d(0:空閑 1:占用)\n",h->tag);
         h=h->rlink; // 指向下一個結點的頭部域(首地址)
       }while(h!=p[i].first); // 沒到循環鏈表的表尾
     }
   }
 }

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

 void main()
 {
   int i,n;
   FreeList a;
   Space q[N]={NULL}; // q數組為占用塊的首地址
   printf("sizeof(WORD)=%u m=%u int(pow(2,m))=%u\n",sizeof(WORD),m,int(pow(2,m)));
   for(i=0;i<=m;i++) // 初始化a
   {
     a[i].nodesize=int(pow(2,i));
     a[i].first=NULL;
   }
   r=a[m].first=new WORD[a[m].nodesize]; // 在最大鏈表中生成一個結點
   if(r) // 生成結點成功
   {
     r->llink=r->rlink=r; // 初始化該結點
     r->tag=0;
     r->kval=m;
     Print(a);
     PrintUser(q);
     n=100;
     q[0]=AllocBuddy(a,n); // 向a申請100個WORD的內存(實際獲得128個WORD)
     printf("申請%d個字后，可利用空間為:\n",n);
     Print(a);
     PrintUser(q);
     n=200;
     q[1]=AllocBuddy(a,n); // 向a申請200個WORD的內存(實際獲得256個WORD)
     printf("申請%d個字又",n);
     n=220;
     q[2]=AllocBuddy(a,n); // 向a申請220個WORD的內存(實際獲得256個WORD)
     printf("申請%d個字后，可利用空間為:\n",n);
     Print(a);
     PrintUser(q);
     Reclaim(a,q[1]); // 回收q[1]，伙伴不空閑
     printf("回收q[1]后，可利用空間為:\n");
     Print(a);
     PrintUser(q);
     Reclaim(a,q[0]); // 回收q[0]，伙伴空閑
     printf("回收q[0]后，可利用空間為:\n");
     Print(a);
     PrintUser(q);
     Reclaim(a,q[2]); // 回收q[2]，伙伴空閑，生成一個大結點
     printf("回收q[2]后，可利用空間為:\n");
     Print(a);
     PrintUser(q);
   }
   else
     printf("ERROR\n");
 }