首先是参考书上第598-602页代码,但是照搬书上的代码只有六十多分(默认的也有七十多)。
注意到书上P594页说,下一次适配很可能比首次适配内存利用率高,尤其是当链表前面布满了许多小碎片的时候,但在有些情况下,下一次适配不及首次适配,书上的代码采用的是首次适配,因此尝试下一次适配。
两者最大的差别就在于find_fit函数,首先给出书上的首次适配函数:
//首次适配,书本P619答案
static void *find_fit(size_t size)
{
void *bp;
for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){
if(!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))){
return bp;
}
}
return NULL;
}
为了实现下一次适配,我们要多定义一个全局变量:
static char *pre_listp;
这个全局变量的更新规则是:首先mm_init时候要更新,然后place的时候要更新,这两个是必须的,也是下一次适配的要求,此外当free的时候也更新这个值效果好一些。
这样就可以重写find_fit函数了:
//下一次适配
static void *find_fit(size_t asize)
{
char *bp = pre_listp;
size_t alloc; //这个块是否分配了
size_t size; //这个块多大
while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue; //分配了继续找
size = GET_SIZE(HDRP(bp));
if (size < asize) continue; //没分配看大小
return bp;
}
bp = heap_listp; //如果后面没找到,可能在前面
while (bp != pre_listp) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue;
size = GET_SIZE(HDRP(bp));
if (size < asize) continue;
return bp;
}
return NULL;
}
这样测试出来能有80多分。