title: Explain this implementation of malloc from the K&R book
body: <p>This is an excerpt from the book on C by <em>Kernighan and Ritchie</em>. It shows how to implement a version of <code>malloc</code>. Although well commented, I am having great difficulty in understanding it. Can somebody please explain it?</p>
  
  <pre><code>typedef long Align; /* for alignment to long boundary */
  union header { /* block header */
  struct {
  union header *ptr; /* next block if on free list */
  unsigned size; /* size of this block */
  } s;
  Align x; /* force alignment of blocks */
  };
  typedef union header Header;
  
  static Header base; /* empty list to get started */
  static Header *freep = NULL; /* start of free list */
  /* 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 = freeptr = prevptr = &amp;base;
        base.s.size = 0;
     }
     for (p = prevp-&gt;s.ptr; ; prevp = p, p = p-&gt;s.ptr) {
        if (p-&gt;s.size &gt;= nunits) { /* big enough */
          if (p-&gt;s.size == nunits) /* exactly */
             prevp-&gt;s.ptr = p-&gt;s.ptr;
          else { /* allocate tail end */
             p-&gt;s.size -= nunits;
             p += p-&gt;s.size;
             p-&gt;s.size = nunits
               }
          freep = prevp;
          return (void *)(p+1);
        }
        if (p == freep) /* wrapped around free list */
           if ((p = morecore(nunits)) == NULL)
               return NULL; /* none left */
        }
  }
  
  #define NALLOC 1024 /* minimum #units to request */
  /* morecore: ask system for more memory */
  
  static Header *morecore(unsigned nu)
  {
  
    char *cp, *sbrk(int);
    Header *up;
  
    if (nu &lt; NALLOC)
      nu = NALLOC;
  
    cp = sbrk(nu * sizeof(Header));
  
    if (cp == (char *) -1) /* no space at all */
      return NULL;
  
    up = (Header *) cp;
    up-&gt;s.size = nu;
    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 */
    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;size == p-&gt;s.ptr) {
      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;size == bp) {
      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>