c - 从 K&R 书中解释 free 的实现

Question

这是 K&R 书中 malloc/free 实现的摘录。我很难理解 free 函数，尤其是 for 循环中的 if 语句:if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) 。如果p >= p->s.ptr为 true，那么 p 一定是空闲链表中的最后一个节点，因为它是一个循环链表，现在 p->s.ptr必须指向基本 header (记住有一个定义的列表 header static Header base; )。那么如何bp < p->s.ptr是真实的？有人可以解释一下吗？

/* free: put block ap in free list */
void free(void *ap)
{
    Header *bp, *p;

    bp = (Header *)ap - 1;    /* point to block header */
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;  /* freed block at start or end of arena */

    if (bp + bp->s.size == p->s.ptr) {  /* join to upper nbr */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;
    if (p + p->s.size == bp) {          /* join to lower nbr */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}

Answer 1

第一个循环试图找到即将被释放的 block 之前的空闲 block 。它只是遍历已经释放的 block ，而不是所有 block 。

有两种情况需要考虑。下一个空闲 block 要么出现在当前空闲 block 之后(通常情况)，要么下一个 block 回绕到开头。

如果下一个空闲 block 位于当前空闲 block 之后，那么我们需要检查我们正在释放的 block 是否位于当前 block 和下一个 block 之间。然而，如果下一个空闲 block 回绕，那么由于列表的循环性质，我们必须查看要释放的 block 是在当前 block 之后还是在下一个 block 之前。

请注意，空闲列表是空闲 block 的列表，因此您所说的if是检查即将被释放的 block (但尚未释放!)位于已释放的第一个 block 之前，这是完全有可能的。