my_malloc.c

lunix下用c编写malloc函数

#include <unistd.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 1024
static Header* Moresys(unsigned int nu);
void* Malloc(unsigned int nbytes);
void Free(void *ap);

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) {
		base.s.next = free_list = prev = &base;
		base.s.size = 1;
	}
	for (p = prev->s.next; ; p = p->s.next, prev = p) {
		if (p->s.size >= nunits) {
			if (p->s.size <= (nunits + 1))
				prev->s.next = p->s.next;
			else {
				p->s.size -= nunits;
				p += p->s.size;
				p->s.size = nunits;
			}
			free_list = prev;
			return(void *)(p+1);
		}
		if(p == free_list)
		if((p = Moresys(nunits)) == NULL)
		return NULL;
	}
}

static Header* Moresys(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)
		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->s.size += bp->s.size;
		p->s.next = bp->s.next;
	}
	else 
		p->s.next = bp;
	
	free_list = p;
}


void
print_list(void)
{
	Header *p;
	int i = 0;
	printf("base: %X, base.next: %X, base.next.next: %X, free: %X\n", 
	&base, base.s.next, base.s.next->s.next, free_list);
	for (p = base.s.next; p != &base; p = p->s.next) {
		i++;
		printf("block %d, size=%d", i, p->s.size);
		if(p > free_list)
			printf(" It is not searched after this point. \n");
		else
			printf(" It is a searched free block!\n");
	}
}
	
main()
{
	char *p[200];
	int i;
	
	for(i = 0; i < 20; i++ ) {
		p[i] = (char *)Malloc(8);
		printf("malloc %d, %X\n", i , p[i]);
		print_list();
	}
	
	for (i =0; i < 20; i++) {
		Free(p[i]);
		printf("free %d\n", i);
		print_list();
	}
	return;
}