///////////////////////////////////////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指針復(fù)位
			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;//要測(cè)試這里是否運(yùn)行！
				}
				free_list=prev;//移動(dòng)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);//認(rèn)作一個(gè)回收的空閑區(qū)，并鏈接，實(shí)際上起到鏈接新區(qū)的目的
	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的前一個(gè)空閑
		if (p>=p->s.next && (bp>p || bp<p->s.next))//（新建時(shí)在哨兵或空閑連的末尾。）
			break;
	if(bp+bp->s.size==p->s.next)//在新空閑區(qū)下面是否有原空閑區(qū)
	{
		bp->s.size+=p->s.next->s.size;
		bp->s.next=p->s.next->s.next;	//若有則兩個(gè)相連合并
	}
	else
		bp->s.next=p->s.next;	//（新建時(shí)賦尾指針。）若沒(méi)有原空閑則直接鏈接。

	if(p+p->s.size==bp)	//p的下一個(gè)是否是bp
	{
		p->s.size+=bp->s.size;
		p->s.next=bp->s.next;	//若是則兩個(gè)相連合并
	}
	else
		p->s.next=bp;	//（新建時(shí)將新空間鏈接上。）若不是則直接鏈接。

	free_list=p;	//（新建時(shí)重新賦free指針，下移。）將free移動(dòng)到剛處理過(guò)的空閑上。
}
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