#include <unistd.h>
#include "my_malloc.h"
static Header base; /* 定义空闲链头,存储块划分的最小单位 */
static Header *free_list = NULL; /* 定义空闲链查询起始指针 free_list */
/* Malloc: 通用存储区分配函数 */
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 = 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;
return (void *)(p + 1);
}
if (p == free_list)
if ( (p = morecore(nunits)) == NULL)
return NULL;
} /* end for */
}
/* morecore: 向操作系统申请更多内存*/
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;
}
/* Free:回收自由空区 */
void
Free(void *ap)
{
Header *bp, *p;
bp = (Header *)ap - 1; /*指向空区的 header */
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; p->s.next != free_list; p = p->s.next) {
i++;
printf("block %d, size=%d", i, p->s.size);
if (p > free_list)
printf(" This point is not searched during the allocation!\n");
else
printf(" It is unused block (free)!\n");
}
}