malloc / free implementation Purpose: Educational
Requirement: Given 64KB of memory, implement your own malloc and free
Method: First-Fit




struct Header 
{
    unsigned short next; //in blocks of sizeof(Header)
    unsigned short size; //in blocks of sizeof(Header)
};

static Header* _dBuffer;
static Header* _dTail;

static public void dInit()
{
    _dBuffer = getMemBlock(64 * 1024);
    _dTail = _dBuffer;
}

static public void* dMalloc(unsigned short nbytes)
{
    if (_dTail == NULL) //empty free list
        return NULL;

    Header* prev = NULL;
    Header* current = _dTail;

    // below is equivalent to ceil((nbytes + sizeof(Header)) / sizeof(Header))
    int nblocks = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1; 
    while (current-&gt;next != 0 &amp;&amp; current-&gt;size &lt; nblocks)
    {
        prev = current;
        current = _dBuffer + current-&gt;next;
    }

    if (current-&gt;size &lt; nblocks) 
        //we've reached the end of the free list without finding a chunk big enough 
        return NULL;

    if (current-&gt;size == nblocks) 
    {
        //we've found an exact match, remove the chunk from the free list
        if (prev == NULL) //remove the first chunk
            _dTail = NULL;
        else
            prev-&gt;next = current-&gt;next;
        return current + 1;
    }

    //current-&gt;size &gt; nblocks
    current-&gt;size -= nblocks;
    current+= current-&gt;size;
    current-&gt;size = nblocks;
    return current + 1;
}

static bool coalesce(Header* block)
{
    Header* nextBlock = _dBuffer + block-&gt;next;
    if (block + block-&gt;size != nextBlock)
        return false;

    block-&gt;size += nextBlock-&gt;size;
    block-&gt;next = nextBlock-&gt;next;
    return true;
}

static public void dFree(void* p) 
{
    Header* released = (Header*)p - 1;
    Header* before = NULL;
    Header* after = _dTail;

    if (_dTail == NULL) //the free list is empty
    {
        released-&gt;next = 0;
        _dTail = released;
        return;
    }

    //find where released is located in the free list
    while (after-&gt;next != 0 &amp;&amp; after &lt; released) 
    {
        before = after;
        after = _dBuffer + after-&gt;next;
    }

    if (after &lt; released) //released chunk after the end of the free list
    {
        released-&gt;next = 0;
        after-&gt;next = released - _dBuffer;
        coalesce(after);
        return;
    }

    if (before == NULL) //released chunk before the beginning of the free list
    {
        released-&gt;next = _dTail - _dBuffer;
        _dTail = released;
        coalesce(released);
        return;
    }

    //released chunk is somewhere in the middle of the list
    released-&gt;next = before-&gt;next;
    before-&gt;next = released - _dBuffer;
    if (coalesce(before)) //before was coalesced with released
        coalesce(before); //now try to coalesce it with after
    else
        coalesce(released); //otherwise, try coalescing released with after
}
I think this is a bug:

if (current-&gt;size == nblocks) 
{
    //we've found an exact match, remove the chunk from the free list
    if (prev == NULL) //remove the first chunk
        _dTail = NULL;
        ^^^^^^^^^^^^^^^
        You are just removing the head of the list
        Not NULL(ing) the list.
        I think the line should be:

        _dTail = current-&gt;next;

    else
        prev-&gt;next = current-&gt;next;
    return current + 1;
}


The only thing I don't like is:

unsigned short next; //in blocks of sizeof(Header)


This because you have to keep doing maths to covert it to/from a pointer. I think your code would become much simpler if you just convert this too:

Header* next; // next block in list


I would also remove the assert:

assert(nbytes % sizeof(Header) == 0);


and replace it with code to move the size up.

if (nbytes % sizeof(Header) != 0)
{
    nbytes += (sizeof(Header) - (nbytes % sizeof(Header)));
}


I think you can simplify your code by quite a bit by using sentinel values on your list. See this answer about lists read the bit about sentinals and how it makes things easier.