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->next != 0 && current->size next;
}

if (current->size 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->next = current->next;
return current + 1;
}

//current->size > nblocks
current->size -= nblocks;
current+= current->size;
current->size = nblocks;
return current + 1;
}

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

block->size += nextBlock->size;
block->next = nextBlock->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->next = 0;
_dTail = released;
return;
}

//find where released is located in the free list
while (after->next != 0 && after next;
}

if (after next = 0;
after->next = released - _dBuffer;
coalesce(after);
return;
}

if (before == NULL) //released chunk before the beginnin

I think this is a bug:

if (current->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->next;

    else
        prev->next = current->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.

StackExchange Code Review Q#19635, answer score: 7