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?..
#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;
}
}
}
В вор мне ноги! Какой умный человек придумал такое на собеседовании? И, интересно, что они хотели увидеть в результате?
ReplyDeleteА нельзя ли отправить этим людям, предложившим эту задачу, ссылку на этот постик?
Ну задачка меня удивила, в принципе. По началу, даже, показалось что должна хорошо показать как человек разбирается в таких вещах. Но после написания alloc'а в первом приближении - стало лень.
ReplyDeleteКто придумал - не знаю. Их было двое. Что они хотели увидеть - меня тоже интересует. Мне показалось, что они ожидали что-то другое. А когда давали задание, то сказали что самая большая проблема - это отсутствие std::map или что-то в этом роде. Ну может ещё напишут и можно будет спросить.
Boost.Interprocess allocation algorithms - that's what I found yesterday when looked for IPC.
ReplyDelete