2011-10-14

Hand-made allocator

Today I was asked at interview to write my own allocator in ANSI C. Pretty strange task as for me. You need some time to debug and doing that at paper is awful. So I've put simple single-listed allocator without merging free space. And of course I forgot to hanle some simple cases.

Let's see how it should look:
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>


#define N 10240

char mem[N];

typedef struct chunk_header_s
{
    struct chunk_header_s *link;
    size_t size;
    char data[0];
} chunk_header;

void init_alloc()
{
    chunk_header *c = (chunk_header*)(mem + sizeof(chunk_header*));
    c->link = NULL;
    c->size = sizeof(mem) - sizeof(chunk_header*) - sizeof(chunk_header);
    *(chunk_header**)mem = c;
}

void *alloc(size_t size)
{
    chunk_header *pc = NULL, *c = *(chunk_header**)mem;
    while (c != NULL && c->size < size) pc = c, c = c->link;
    if (c == NULL) return NULL;
    if (c->size >= (size + sizeof(chunk_header))) // split
    {
        chunk_header *nc = (chunk_header*)(c->data + size);
        nc->size = c->size - size - sizeof(*nc);
        nc->link = c->link;
        c->size = size;
        c->link = nc;
    }
    // link prev free chunk to next free chunk
    if (pc == NULL) *(chunk_header**)mem = c->link;
    else
    {
        assert(pc->link == c);
        pc->link = c->link;
    }
   
    // link this chunk to prev free
    c->link = pc;

    return c->data;
}

void release(void *ptr)
{
    assert(ptr != NULL);

    chunk_header *c = (chunk_header*)((char*)ptr - sizeof(chunk_header));
    assert(c->link == NULL || c->link < c);

    // backward scan for prev free
    chunk_header *nc;
    chunk_header *pc = c->link;
    while (pc != NULL && pc->link < pc) pc = pc->link;

    if (pc == NULL) // not found?
    {
        // try full forward scan
        nc = *(chunk_header**)mem;
        while(nc != NULL && nc < c) pc = nc, nc = nc->link;
    }

    {
        // fix all allocated chunks that is out of sync
        chunk_header *bc = c->link;
        while(bc != NULL && bc->link < bc && pc < bc) // only those that is after last free before current
        {
            nc = bc;
            bc = bc->link;
            nc->link = pc; // point to real prev free (even if it is NULL)
        }
    }

    if (pc == NULL) // all free chunks is after current
    {
        nc = *(chunk_header**)mem;
    }
    else // found free chunk before this one
    {
        assert(pc < c);
        nc = pc->link;
    }

    if (nc == NULL) // no free chunks after current
    {
        c->link = NULL;
    }
    else
    {
        // link or merge with next free chunk
        assert(c < nc);
        if ((c->data + c->size) == (char*)nc) // merge with next
        {
            c->link = nc->link;
            c->size += sizeof(*nc) + nc->size;
        }
        else // just insert before it
        {
            c->link = nc;
        }
    }

    if (pc == NULL) // no previous free chunk
    {
        *(chunk_header**)mem = c; // update head
    }
    else // there is one
    {
        // so try to merge
        if ((pc->data + pc->size) == (char*)c) // merge with prev
        {
            pc->link = c->link;
            pc->size += sizeof(*c) + c->size;
        }
        else // insert after prev
        {
            pc->link = c;
        }
    }
}
 
And this is yet simple functional variant. Do they really expect me to write this on the paper?..