/* algo8-2.c 伙伴系統。實現算法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數組所指的已分配空間 */
   int i;
   for(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=(WORD*)malloc(a[m].nodesize*sizeof(WORD)); /* 在最大鏈表中生成一個結點 */
   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");
 }