// algo8-2.cpp 伙伴系統(tǒng)。實(shí)現(xiàn)算法8.2的程序
 #include"c1.h"
 #include"c8-2.h"
 #define N 100 // 占用塊個(gè)數(shù)的最大值
 Space r; // r為生成空間的首地址,全局量

 Space AllocBuddy(FreeList &avail,int n)
 { // avail[0..m]為可利用空間表,n為申請(qǐng)分配量,若有不小于n的空閑塊,
   // 則分配相應(yīng)的存儲(chǔ)塊,并返回其首地址;否則返回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 // 進(jìn)行分配
   {
     pa=avail[k].first; // 指向可分配子表的第一個(gè)結(jié)點(diǎn)
     pre=pa->llink; // 分別指向前驅(qū)和后繼
     suc=pa->rlink;
     if(pa==suc)
       avail[k].first=NULL; // 分配后該子表變成空表
     else // 從子表刪去*pa結(jié)點(diǎn)
     {
       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;
     } // 將剩余塊插入相應(yīng)子表
     pa->tag=1;
     pa->kval=k-(--i);
   }
   return pa;
 }

 Space buddy(Space p)
 { // 返回相對(duì)起始地址為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)
 { // 伙伴系統(tǒng)的回收算法 將p所指的釋放塊回收到可利用空間表pav中
   Space s;
   s=buddy(p); // 伙伴塊的起始地址
   while(s>=r&&s<r+pav[m].nodesize&&s->tag==0) // 歸并伙伴塊,伙伴塊起始地址在有效范圍內(nèi)且伙伴塊空閑
   { // 從鏈表上刪除該結(jié)點(diǎn)
     if(s->llink==s&&s->rlink==s) // 鏈表上僅此一個(gè)結(jié)點(diǎn)
       pav[s->kval].first=NULL; // 置此鏈表為空
     else // 鏈表上不止一個(gè)結(jié)點(diǎn)
     {
       s->llink->rlink=s->rlink; // 前驅(qū)的后繼為該結(jié)點(diǎn)的后繼
       s->rlink->llink=s->llink; // 后繼的前驅(qū)為該結(jié)點(diǎn)的前驅(qū)
       if(pav[s->kval].first==s) // s是鏈表的第一個(gè)結(jié)點(diǎn)
         pav[s->kval].first=s->rlink; // 表頭指向下一個(gè)結(jié)點(diǎn)
     } // 以下修改結(jié)點(diǎn)頭部
     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); // 下一個(gè)伙伴塊的起始地址
   }
   // 以下將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個(gè)可利用空間表不空
     {
       h=p[i].first; // h指向鏈表的第一個(gè)結(jié)點(diǎn)的頭部域(首地址)
       do
       {
         printf("塊的大小=%d 塊的首地址=%u ",int(pow(2,h->kval)),h); // 輸出結(jié)點(diǎn)信息
         printf("塊標(biāo)志=%d(0:空閑 1:占用)\n",h->tag);
         h=h->rlink; // 指向下一個(gè)結(jié)點(diǎn)的頭部域(首地址)
       }while(h!=p[i].first); // 沒到循環(huán)鏈表的表尾
     }
   }
 }

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

 void main()
 {
   int i,n;
   FreeList a;
   Space q[N]={NULL}; // q數(shù)組為占用塊的首地址
   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]; // 在最大鏈表中生成一個(gè)結(jié)點(diǎn)
   if(r) // 生成結(jié)點(diǎn)成功
   {
     r->llink=r->rlink=r; // 初始化該結(jié)點(diǎn)
     r->tag=0;
     r->kval=m;
     Print(a);
     PrintUser(q);
     n=100;
     q[0]=AllocBuddy(a,n); // 向a申請(qǐng)100個(gè)WORD的內(nèi)存(實(shí)際獲得128個(gè)WORD)
     printf("申請(qǐng)%d個(gè)字后，可利用空間為:\n",n);
     Print(a);
     PrintUser(q);
     n=200;
     q[1]=AllocBuddy(a,n); // 向a申請(qǐng)200個(gè)WORD的內(nèi)存(實(shí)際獲得256個(gè)WORD)
     printf("申請(qǐng)%d個(gè)字又",n);
     n=220;
     q[2]=AllocBuddy(a,n); // 向a申請(qǐng)220個(gè)WORD的內(nèi)存(實(shí)際獲得256個(gè)WORD)
     printf("申請(qǐng)%d個(gè)字后，可利用空間為:\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]，伙伴空閑，生成一個(gè)大結(jié)點(diǎn)
     printf("回收q[2]后，可利用空間為:\n");
     Print(a);
     PrintUser(q);
   }
   else
     printf("ERROR\n");
 }