文档.txt

内 存 的 申 请 与 释 放 简单的程序

///////////////////////////////////////MALLOC.H/////////////////


#include <stdlib.h>
typedef long Align;
union header {
	struct {
		union header *next;
		unsigned int size;
	} s;
	Align x;
};
typedef union header Header;
#define NALLOC 14
static Header *morecore(unsigned int nu);
void *Malloc(unsigned int nbytes);
void Free(void *ap);



////////////////////////////////MALLOC.C//////////////////////


#include <unistd.h>
#include "Malloc.h"
static Header base;
static Header *free_list=NULL;

void *Malloc(unsigned int nbytes)
{
	Header *p,*prev;
	unsigned int nunits;
	nunits=(nbytes+sizeof(Header)-1)/sizeof(Header)+1;
		if((prev=free_list)==NULL){	//pre指针复位
			base.s.next=free_list=prev=&base;/*初始化哨兵*/
			base.s.size=0;
		}
		for (p=prev->s.next;	;prev=p,p=p->s.next)
                {
			if(p->s.size>=nunits)
                          {
				if(p->s.size==nunits)
					prev->s.next=p->s.next;
			        else
				{
					p->s.size-=nunits;
					p+=p->s.size;
					p->s.size=nunits;//要测试这里是否运行！
				}
				free_list=prev;//移动free指针
				return(void*)(p+1);
			}
			if(p==free_list)
				if((p=morecore(nunits))==NULL)//p=free
					return NULL;
		}
}
static Header *morecore(unsigned int nu)
{
	char *cp;
	Header *up;
	if (nu<NALLOC)
	nu=NALLOC;
	cp=sbrk(nu * sizeof(Header));
	printf("sbrk:%x--%x\n",cp,cp+nu * sizeof(Header));
	if(cp==(char*)-1)
		return NULL;
	up=(Header *)cp;
	up->s.size=nu;
	Free(up+1);//认作一个回收的空闲区，并链接，实际上起到链接新区的目的
	return free_list;
}
void Free(void *ap)
{
	Header *bp,*p;
	bp=(Header *)ap-1;//找到哨兵
	for (p=free_list; !(bp>p && bp<p->s.next);p=p->s.next)//找到合适的位置，使p在bp的前一个空闲
		if (p>=p->s.next && (bp>p || bp<p->s.next))//（新建时在哨兵或空闲连的末尾。）
			break;
	if(bp+bp->s.size==p->s.next)//在新空闲区下面是否有原空闲区
	{
		bp->s.size+=p->s.next->s.size;
		bp->s.next=p->s.next->s.next;	//若有则两个相连合并
	}
	else
		bp->s.next=p->s.next;	//（新建时赋尾指针。）若没有原空闲则直接链接。

	if(p+p->s.size==bp)	//p的下一个是否是bp
	{
		p->s.size+=bp->s.size;
		p->s.next=bp->s.next;	//若是则两个相连合并
	}
	else
		p->s.next=bp;	//（新建时将新空间链接上。）若不是则直接链接。

	free_list=p;	//（新建时重新赋free指针，下移。）将free移动到刚处理过的空闲上。
}
void print_list(void)
{
	Header * p;
	int i=0;
	printf("base:%x,base.nest:%x,base.next.next:%x,free:%x\n",&base, base.s.next,base.s.next->s.next,free_list); 
	for(p=&base;p->s.next !=free_list;p=p->s.next){
		i++;
		printf("block %d,size=%d",i,p->s.size);
		if(p>free_list)
			printf("It is not searched afrer this point.\n");
		else
			printf("It is a searched free block!\n");
	}
}





///////////////////////////TEXT.C//////////////////////////


#include"Malloc.h"
void main(void)
{
	char *p[200];
	int i;
	for(i=0;i<5;i++){
		p[i]=(char*)Malloc(80);
		printf("malloc %d,%x\n",i,p[i]);
		print_list();
	}
	for(i=4;i>=0;i--){
		Free(p[i]);
		printf("free %d\n",i);
		print_list();
	}
}






/////////////////////////result/////////////////////////////



sbrk:10010cec--10010d5c
mallod 0,10010d0c
base:10010c60,base.nest:10010cec,base.next.next:10010c60,free:10010c60
block 1,size=0It is a searched free block!

sbrk:10010d5c--10010dcc
mallod 1,10010d7c
base:10010c60,base.nest:10010cec,base.next.next:10010d5c,free:10010cec

sbrk:10010dcc--10010e3c
mallod 2,10010dec
base:10010c60,base.nest:10010cec,base.next.next:10010d5c,free:10010d5c
block 1,size=0It is a searched free block!

free 2
base:10010c60,base.nest:10010cec,base.next.next:10010d5c,free:10010dcc
block 1,size=0It is a searched free block!
block 2,size=3It is a searched free block!

free 1
base:10010c60,base.nest:10010cec,base.next.next:10010d5c,free:10010d5c
block 1,size=0It is a searched free block!

free 0
base:10010c60,base.nest:10010cec,base.next.next:10010c60,free:10010cec