title: Explain this implementation of free from the K&R book
body: <p>This is an excerpt from malloc/free implementation on K&amp;R book. I am having great difficulty in understanding the free function, especially the if statement in the for loop: <code>if (p >= p->s.ptr &amp;&amp; (bp > p || bp &lt; p->s.ptr))</code>. If <code>p >= p->s.ptr</code> is true, then p must be the last node in the free list, since it is a circular list, now <code>p->s.ptr</code> must point to the base header (Remember therer is a list header defined <code>static Header base;</code>). So how can <code>bp &lt; p->s.ptr</code> be true? Can somebody please explain it?</p>
  
  <pre><code>/* 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 &gt; p &amp;&amp; bp &lt; p-&gt;s.ptr); p = p-&gt;s.ptr)
          if (p &gt;= p-&gt;s.ptr &amp;&amp; (bp &gt; p || bp &lt; p-&gt;s.ptr))
              break;  /* freed block at start or end of arena */
  
      if (bp + bp-&gt;s.size == p-&gt;s.ptr) {  /* join to upper nbr */
          bp-&gt;s.size += p-&gt;s.ptr-&gt;s.size;
          bp-&gt;s.ptr = p-&gt;s.ptr-&gt;s.ptr;
      } else
          bp-&gt;s.ptr = p-&gt;s.ptr;
      if (p + p-&gt;s.size == bp) {          /* join to lower nbr */
          p-&gt;s.size += bp-&gt;s.size;
          p-&gt;s.ptr = bp-&gt;s.ptr;
      } else
          p-&gt;s.ptr = bp;
      freep = p;
  }
  </code></pre>