第八章 動態存儲管理
typedef struct {
char *start;
int size;
} fmblock; //空閒塊類型
char *Malloc_Fdlf(int n)//遵循最後分配者最先釋放規則的內存分配算法
{
while(Gettop(S { Pop(S,b); Push(T,b); //從棧頂逐個取出空閒塊進行比較 } if(StackEmpty(S)) return NULL; //沒有大小足夠的空閒塊 Pop(S,b); b.size-=n; if(b.size) Push(S,{b.start+n,b.size});//分割空閒塊 while(!StackEmpty(T)) { Pop(T,a); Push(S,a); } //恢復原來次序 return b.start; }//Malloc_Fdlf mem_init()//初始化過程 { ... InitStack(S);InitStack(T); //S和T的元素都是fmblock類型 Push(S,{MemStart,MemLen}); //一開始,棧中只有一個內存整塊 ... }//main 8.12 void Free_Fdlf(char *addr,int n)//與上一題對應的釋放算法 { while(Gettop(S,b)&&b.start
{ Pop(S,b); Push(T,b); } //在按地址排序的棧中找到合適的插入位置 if(Gettop(T,b)&&(b.start+b.size==addr)) //可以與上鄰塊合並 { Pop(T,b); addr=b.start;n+=b.size; } if(Gettop(S,b)&&(addr+n==b.start)) //可以與下鄰塊合並 { Pop(S,b); n+=b.size; } Push(S,{addr,n}); //插入到空閒塊棧中 while(!StackEmpty(T)) { Pop(T,b); Push(S,b); } //恢復原來次序 }//Free_Fdlf 8.13 void Free_BT(Space &pav,Space p)//在邊界標識法的動態存儲管理系統中回收空閒塊p { n=p->size; f=p+n-1; //f指向空閒塊底部 if((p-1)->tag&&(f+1)->tag) //回收塊上下鄰塊均為占用塊 { p->tag=0;f->tag=0; f->uplink=p; if(!pav) { p->llink=p; p->rlink=p; } else { q=pav->llink; p->llink=q;p->rlink=pav; q->rlink=p;pav->llink=p; } pav=p; }//if else if(!(p-1)->tag&&(f+1)->tag) //上鄰塊為空閒塊 { q=(p-1)->uplink; q->size+=n; f->uplink=q; f->tag=0; } else if((p-1)->tag&&!(f+1)->tag) //下鄰塊為空閒塊 { q=f+1; s=q->llink;t=q->rlink; p->llink=s;p->rlink=t; s->rlink=p;t->llink=p; p->size+=q->size; (q+q->size-1)->uplink=p; p->tag=0; } else //上下鄰塊均為空閒塊 { s=(p-1)->uplink; t=f+1; s->size+=n+t->size; t->llink->rlink=t->rlink; t->rlink->llink=t->llink; (t+t->size-1)->uplink=s; } }//Free_BT,該算法在課本裡有詳細的描述. 8.14 void Free_BS(freelist &avail,char *addr,int n)//伙伴系統的空閒塊回收算法 { buddy=addr%(2*n)?(addr-n):(addr+n); //求回收塊的伙伴地址 addr->tag=0; addr->kval=n; for(i=0;avail[i].nodesize if(!avail[i].first) //尚沒有該大小的空閒塊 { addr->llink=addr; addr->rlink=addr; avail[i].first=addr; //作為唯一一個該大小的空閒塊 } else { for(p=avail[i].first;p!=buddy&&p!=avail[i].first;p=p->rlink);//尋找伙伴 if(p==buddy) //伙伴為空閒塊,此時進行合並 { if(p->rlink==p) avail[i].first=NULL;//伙伴是此大小的唯一空閒塊 else { p->llink->rlink=p->rlink; p->rlink->llink=p->llink; } //從空閒塊鏈中刪去伙伴 new=addr>p?p:addr; //合並後的新塊首址 Free_BS(avail,new,2*n); //遞歸地回收新塊 }//if else //伙伴為占用塊,此時插入空閒塊鏈頭部 { q=p->rlink; p->rlink=addr;addr->llink=p; q->llink=addr;addr->rlink=q; } }//else }//Free_BS 8.15 FBList *MakeList(char *highbound,char *lowbound)//把堆結構存儲的的所有空閒塊鏈接成可利用空間表,並返回表頭指針 { p=lowbound; while(p->tag&&p if(p>=highbound) return NULL; //沒有空閒塊 head=p; for(q=p;p if(!p->tag) { q->next=p; q=p; }//if p->next=NULL; return head; //返回頭指針 }//MakeList 8.16 void Mem_Contract(Heap &H)//對堆H執行存儲緊縮 { q=MemStart;j=0; for(i=0;i if(H.list[i].stadr->tag) { s=H.list[i].length; p=H.list[i].stadr; for(k=0;k H.list[j].stadr=q; H.list[j].length=s; //緊縮占用空間表 j++; } }//Mem_Contract
From:http://tw.wingwit.com/Article/program/sjjg/201311/23561.html