时间戳

首页 > 解决方案 > K&R 第 8.7 节 for free() 中的循环

c - K&R 第 8.7 节 for free() 中的循环

问题描述

在 K&R(2nd) 第 8.7 节中，我认为 free() 中有一个意想不到的无限循环，它的测试部分似乎是错误的。
我插入了四个 // 评论。malloc() 有一个，morecore() 有另一个，free() 有其他的。

typedef long Align;

union header {
    struct {
        union header* ptr;
        unsigned size;
    }s;
    Align x;
};

typedef union header Header;

static Header base;
static Header *freep = NULL;

/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned  nunits;

    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
    if ((prevp = freep) == NULL) {          /* no free list yet */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {          /* big enough */
            if (p->s.size == nunits)        /* exactly */
                prevp->s.ptr = p->s.ptr;
            else {                          /* allocate tail end */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p + 1);
        }
        if (p == freep)                      /* wrapped around free list */
            // base.s.ptr = &base, freep == &base
            if ((p = morecore(nunits)) == NULL)
                return NULL;                 /* none left */
    }
}

#define NALLOC 1024     /* minimum #units to requst */

/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
    char *cp, *sbrk(int);
    Header *up;

    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)      /* no space at all */
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    // base.s.ptr = &base, freep == &base
    free((void *)(up+1));
    return freep;
}

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

    bp = (Header *)ap - 1;  /* point to block header */
    // base.s.ptr = &base, freep == &base
    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 */
    // for (p = freep; !(0); )\
            if (p >= s.ptr && (0))\
                break;

    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;
}

我想说的是

void free(void *ap) {
/* ... */
   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 */
/* ... */
}

这个 for 循环是无限的。因为与和的每个值bp > p && bp < p->s.ptr相同。并且什么都不做。指向，指向自身。所以不会改变的值。 此外，指针指向 sbrk() 接收到的内存头。可以比较吗？ 我认为函数 free() 只有在我们已经使用 malloc() 获得了一个有效的内存块并调用它来释放它时才有意义。morecore() 中的函数调用和 free() 的主体不匹配（我认为）。 Q1。为什么for循环是无限的？ Q2。比较是否有效0pp->s.ptr&basep = p->s.ptrpbasebase.s.ptrbp > p && bp < p->s.ptr
bpbpp
free((void *)(up+1));


bpp在那个for循环中？如果是这样，如何以及在哪里放置bp（指向由 sbrk() 分配的内存）？

标签： ckernighan-and-ritchie

解决方案

Q1。为什么for循环是无限的？

不，它不是无限的。

void free(void *ap) {
/* ... */
   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 */
/* ... */
}

当base.s.ptr = &base和时freep == &base，上面的代码与

void free(void *ap) {
/* ... */
   for (p = freep; !(0); p = p->s.ptr)
        if (1 && (1))
            break;  /* freed block at start or end of arena */
/* ... */
}

（我对运算符的含义感到困惑||。我认为bp > p || bp < p->s.ptr应该与0我提出问题时相同。）

Q2。在该 for 循环中将 bp 与 p 进行比较是否有效？如果是这样，bp（指向由 sbrk() 分配的内存）是如何以及在哪里放置的？

是的，比较这两者是有效的。sbrk() 返回前一个程序中断值。所以bp和p是可比的。

推荐阅读