allocbuddy.cpp

伙伴系统:avail[0..m]为可利用空间表, n为申请分配量, 若有不小于n的空闲块, 则分配相应的存储块, 并返回其首地址,否则返回NULL

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define m 3
typedef int OtherType;
typedef struct WORD {
	WORD *llink;
	int tag;
	int kval;
	WORD *rlink;
	OtherType other;
}WORD,head,*Space;
typedef struct HeadNode {
	int nodesize;
	WORD *first;
}FreeList[m+1];

Space AllocBuddy(FreeList &avail, int n) 
{
	//avail[0..m]为可利用空间表, n为申请分配量, 若有不小于n的空闲块, 
	//则分配相应的存储块, 并返回其首地址,否则返回NULL
	int k,i;
	WORD *pa,*pre,*suc,*pi;
	for(k=0; k<=m && (avail[k].nodesize<n+1 || !avail[k].first); ++k);//查找满足分配要求的子表 
	if(k>m) return NULL;//分配失败,返回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;
	}//将剩余块Insert相应子表
	pa->tag=1; 
	pa->kval=k-(--i); 
	return pa;
}

int main(void)
{
	FreeList avail;
	int i;
	WORD *p;
	for(i=0;i<=m;i++)
	{
		avail[i].first=NULL;
		avail[i].nodesize=int(pow(2,i));
		
	}
	p=(WORD *)malloc(int(pow(2,m))*sizeof(WORD));
	if(!p) exit(OVERFLOW);
	p->kval=m;
	p->llink=p;
	p->rlink=p;
	p->tag=0;
	avail[m].first=p;	
	AllocBuddy(avail,1);
	printf("Hello,world!\n");
	return 0;
}